merkle

Documentation

Index

• func BuildMerkleTreeStore(txHashs []*types.Hash) []*types.Hash
• func CalcMerkleTreeRootHash(txHashs []*types.Hash) types.Hash
• func HashMerkleBranches(left *types.Hash, right *types.Hash) *types.Hash

Functions

func BuildMerkleTreeStore

func BuildMerkleTreeStore(txHashs []*types.Hash) []*types.Hash

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 bitcoin transactions where h(x) is a hash256 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 CalcMerkleTreeRootHash

func CalcMerkleTreeRootHash(txHashs []*types.Hash) types.Hash

CalcMerkleTreeRootHash calcute the merkle tree root hash for a slice of transactions

func HashMerkleBranches

func HashMerkleBranches(left *types.Hash, right *types.Hash) *types.Hash

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.