merkle

Documentation

Index

• func BuildMerkleTreeStore(objects [][]byte) [][]byte
• func DoubleHashH(b []byte) []byte
• func GetMerkleRoot(objects [][]byte) []byte
• func HashMerkleBranches(left []byte, right []byte) []byte

Functions

func BuildMerkleTreeStore

func BuildMerkleTreeStore(objects [][]byte) [][]byte

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 double sha256 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.

The additional bool parameter indicates if we are generating the merkle tree using witness transaction id's rather than regular transaction id's. This also presents an additional case wherein the wtxid of the coinbase transaction is the zeroHash.

func DoubleHashH

func DoubleHashH(b []byte) []byte

DoubleHashH calculates hash(hash(b)) and returns the resulting bytes as a Hash

func GetMerkleRoot

func GetMerkleRoot(objects [][]byte) []byte

GetMerkleRoot calculate merkle root of several objects

func HashMerkleBranches

func HashMerkleBranches(left []byte, right []byte) []byte

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.