merkletree

Documentation

Overview

Package merkletree is a binary SHA256 Merkle tree.

The binary Merkle tree contains two types of nodes: leaves (type 0x00) and intermediate nodes (type 0x01).

The leaf hash is a hash of its data, prefixed by a zero byte: `SHA256(0x00 || leaf)`.

The intermediate hash is a hash of the child hashes, prefixed by a one byte: `SHA256(0x01 || left || right)`

Construction

Solana consensus relies on deterministic construction of Merkle trees.

The "canoical" construction method arranges the tree into "layers" (identified by node distance to root), with the lowest layer always consisting of leaf nodes.

If the lowest layer contains more than one leaf, recursively construct upper layers of intermediate nodes that each hash a pair of two of the lower layer's nodes in order.

When any upper layer hashes an uneven amount of nodes, the last intermediate node shall hash the same lower node twice.

Index

• Constants
• func HashIntermediate(left *[32]byte, right *[32]byte) (out [32]byte)
• func HashLeaf(data []byte) (out [32]byte)
• type Nodes
  • func HashNodes(leaves [][]byte) (out Nodes)
  • func (n *Nodes) GetRoot() (out *[32]byte)

Constants

const (
	TypeLeaf         = 0x00
	TypeIntermediate = 0x01
)

One byte type prefix used as a hash domain.

Functions

func HashIntermediate

func HashIntermediate(left *[32]byte, right *[32]byte) (out [32]byte)

HashIntermediate returns the hash of an intermediate node.

func HashLeaf

func HashLeaf(data []byte) (out [32]byte)

HashLeaf returns the hash of a leaf node.

Types

type Nodes

type Nodes struct {
	NumLeaves uint
	Nodes     [][32]byte
}

Nodes stores the hashes of all nodes, excluding node type and content.

func HashNodes

func HashNodes(leaves [][]byte) (out Nodes)

HashNodes constructs proof data from a set of leaves.

Port of solana_merkle_tree::MerkleTree::new

func (*Nodes) GetRoot

func (n *Nodes) GetRoot() (out *[32]byte)

GetRoot returns the root hash. Returns zero if tree is empty.