1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
// Copyright (C) 2019-2024 Algorand, Inc.
// This file is part of go-algorand
//
// go-algorand is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// go-algorand is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with go-algorand. If not, see <https://www.gnu.org/licenses/>.
package bookkeeping
import (
"fmt"
"github.com/algorand/go-algorand/crypto"
"github.com/algorand/go-algorand/crypto/merklearray"
"github.com/algorand/go-algorand/data/transactions"
"github.com/algorand/go-algorand/protocol"
)
// TxnMerkleTree returns a cryptographic commitment to the transactions in the
// block, along with their ApplyData, as a Merkle tree. This allows the
// caller to either extract the root hash (for inclusion in the block
// header), or to generate proofs of membership for transactions that are
// in this block.
func (block Block) TxnMerkleTree() (*merklearray.Tree, error) {
return merklearray.Build(&txnMerkleArray{block: block, hashType: crypto.Sha512_256}, crypto.HashFactory{HashType: crypto.Sha512_256})
}
// TxnMerkleTreeSHA256 returns a cryptographic commitment to the transactions in the
// block, along with their ApplyData, as a Merkle tree vector commitment, using SHA256. This allows the
// caller to either extract the root hash (for inclusion in the block
// header), or to generate proofs of membership for transactions that are
// in this block.
func (block Block) TxnMerkleTreeSHA256() (*merklearray.Tree, error) {
return merklearray.BuildVectorCommitmentTree(&txnMerkleArray{block: block, hashType: crypto.Sha256}, crypto.HashFactory{HashType: crypto.Sha256})
}
// txnMerkleArray is a representation of the transactions in this block,
// along with their ApplyData, as an array for the merklearray package.
type txnMerkleArray struct {
block Block
hashType crypto.HashType
}
// Length implements the merklearray.Array interface.
func (tma *txnMerkleArray) Length() uint64 {
return uint64(len(tma.block.Payset))
}
// Get implements the merklearray.Array interface.
func (tma *txnMerkleArray) Marshal(pos uint64) (crypto.Hashable, error) {
if pos >= uint64(len(tma.block.Payset)) {
return nil, fmt.Errorf("txnMerkleArray.Get(%d): out of bounds, payset size %d", pos, len(tma.block.Payset))
}
var elem txnMerkleElem
elem.hashType = tma.hashType
elem.stib = tma.block.Payset[pos]
stxn, _, err := tma.block.DecodeSignedTxn(elem.stib)
if err != nil {
return nil, err
}
elem.txn = stxn.Txn
return &elem, nil
}
func txnMerkleToRaw(txid [crypto.DigestSize]byte, stib [crypto.DigestSize]byte) (buf []byte) {
buf = make([]byte, 2*crypto.DigestSize)
copy(buf[:], txid[:])
copy(buf[crypto.DigestSize:], stib[:])
return
}
// txnMerkleElem represents a leaf in the Merkle tree of all transactions
// in a block.
type txnMerkleElem struct {
txn transactions.Transaction
stib transactions.SignedTxnInBlock
hashType crypto.HashType
}
func (tme *txnMerkleElem) RawLeaf() []byte {
if tme.hashType == crypto.Sha512_256 {
return txnMerkleToRaw(tme.txn.ID(), tme.stib.Hash())
}
// else: hashType == crypto.Sha256
return txnMerkleToRaw(tme.txn.IDSha256(), tme.stib.HashSHA256())
}
// ToBeHashed implements the crypto.Hashable interface.
func (tme *txnMerkleElem) ToBeHashed() (protocol.HashID, []byte) {
// The leaf contains two hashes: the transaction ID (hash of the
// transaction itself), and the hash of the entire SignedTxnInBlock.
return protocol.TxnMerkleLeaf, tme.RawLeaf()
}
// Hash implements an optimized version of crypto.HashObj(tme).
func (tme *txnMerkleElem) Hash() crypto.Digest {
return crypto.Hash(tme.HashRepresentation())
}
func (tme *txnMerkleElem) HashRepresentation() []byte {
var buf [len(protocol.TxnMerkleLeaf) + 2*crypto.DigestSize]byte
s := buf[:0]
s = append(s, protocol.TxnMerkleLeaf...)
s = append(s, tme.RawLeaf()...)
return s
}
|
