Documentation
¶
Index ¶
- func BuildMerkleTreeStore(transactions []*types.Tx, witness bool) []*hash.Hash
- func BuildParentsMerkleTreeStore(parents []*hash.Hash) []*hash.Hash
- func BuildTokenBalanceMerkleTreeStore(balance []*hash.Hash) []*hash.Hash
- func CalcMerkleRoot(txns []*types.Transaction) *hash.Hash
- func HashMerkleBranches(left *hash.Hash, right *hash.Hash) *hash.Hash
- func ValidateWitnessCommitment(blk *types.SerializedBlock) error
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BuildMerkleTreeStore ¶
buildMerkleTreeStore creates a merkle tree from a slice of transactions, stores it using a linear array, and returns a slice of the backing array. A linear array was chosen as opposed to an actual tree structure since it uses about half as much memory. The following describes a merkle tree and how it is stored in a linear array.
A merkle tree is a tree in which every non-leaf node is the hash of its children nodes. A diagram depicting how this works for transactions where h(x) is a blake256 hash follows:
root = h1234 = h(h12 + h34)
/ \
h12 = h(h1 + h2) h34 = h(h3 + h4)
/ \ / \
h1 = h(tx1) h2 = h(tx2) h3 = h(tx3) h4 = h(tx4)
The above stored as a linear array is as follows:
[h1 h2 h3 h4 h12 h34 root]
As the above shows, the merkle root is always the last element in the array.
The number of inputs is not always a power of two which results in a balanced tree structure as above. In that case, parent nodes with no children are also zero and parent nodes with only a single left node are calculated by concatenating the left node with itself before hashing. Since this function uses nodes that are pointers to the hashes, empty nodes will be nil.
func BuildParentsMerkleTreeStore ¶
BuildParentsMerkleTreeStore creates a merkle tree from a slice of block parents, stores it using a linear array, and returns a slice of the backing array. A linear array was chosen as opposed to an actual tree structure since it uses about half as much memory. The following describes a merkle tree and how it is stored in a linear array.
A merkle tree is a tree in which every non-leaf node is the hash of its children nodes. A diagram depicting how this works for block parents where h(x) is a blake256 hash follows:
root = h1234 = h(h12 + h34)
/ \
h12 = h(h1 + h2) h34 = h(h3 + h4)
/ \ / \
h1 = h(tx1) h2 = h(tx2) h3 = h(tx3) h4 = h(tx4)
The above stored as a linear array is as follows:
[h1 h2 h3 h4 h12 h34 root]
As the above shows, the merkle root is always the last element in the array.
The number of inputs is not always a power of two which results in a balanced tree structure as above. In that case, parent nodes with no children are also zero and parent nodes with only a single left node are calculated by concatenating the left node with itself before hashing. Since this function uses nodes that are pointers to the hashes, empty nodes will be nil.
func BuildTokenBalanceMerkleTreeStore ¶ added in v0.10.1
func CalcMerkleRoot ¶
func CalcMerkleRoot(txns []*types.Transaction) *hash.Hash
func HashMerkleBranches ¶ added in v0.10.1
HashMerkleBranches takes two hashes, treated as the left and right tree nodes, and returns the hash of their concatenation. This is a helper function used to aid in the generation of a merkle tree.
func ValidateWitnessCommitment ¶
func ValidateWitnessCommitment(blk *types.SerializedBlock) error
Types ¶
This section is empty.
Source Files