merkle

Documentation

Index

• Variables
• func Root(hashes []*[sha256.Size]byte) *[sha256.Size]byte
• func Tree(hashes []*[sha256.Size]byte) []*[sha256.Size]byte
• func VerifyAuthPath(mb *Branch) (*[sha256.Size]byte, error)
• type Branch
  • func AuthPath(leaves []*[sha256.Size]byte, hash *[sha256.Size]byte) *Branch

Variables

var (
	ErrEmpty = errors.New("empty merkle branch")
)

Functions

func Root

func Root(hashes []*[sha256.Size]byte) *[sha256.Size]byte

Root returns only the merkle root of an array of digests.

func Tree

func Tree(hashes []*[sha256.Size]byte) []*[sha256.Size]byte

Tree 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 fonero 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.

We always sort the incoming hashes array in order to always generate the same merkle tree regardless of input order.

func VerifyAuthPath

func VerifyAuthPath(mb *Branch) (*[sha256.Size]byte, error)

VerifyAuthPath takes a Branch and ensures that it is a valid tree.

Types

type Branch

type Branch struct {
	NumLeaves uint32              // Nuber of leaves
	Hashes    [][sha256.Size]byte // Merkle branch
	Flags     []byte              // Bitmap of merkle tree
}

Branch is a cooked merkle authentication path that can be transmitted over a wire and can be verified on the other end.

func AuthPath

func AuthPath(leaves []*[sha256.Size]byte, hash *[sha256.Size]byte) *Branch

AuthPath returns a Merkle tree authentication path.