Documentation
¶
Overview ¶
Package treeproof provides Merkle tree construction and proof generation for SSZ structures.
This package enables the construction of complete Merkle trees from SSZ-encoded data structures, supporting both traditional binary trees and progressive trees for advanced use cases. It provides functionality for generating and verifying Merkle proofs against generalized indices.
Key features:
- Binary tree construction: Standard SSZ merkleization for fixed-size containers
- Progressive tree construction: Advanced merkleization for containers with optional fields
- Proof generation: Single and multi-proof generation for any tree node
- Proof verification: Standalone verification of generated proofs
- Tree visualization: Debug-friendly tree structure display with generalized indices
The package supports the generalized index system used in Ethereum 2.0 for addressing nodes within Merkle trees, enabling efficient proof generation for any field or value within complex data structures.
Index ¶
- func VerifyMultiproof(root []byte, proof, leaves [][]byte, indices []int) (bool, error)
- func VerifyProof(root []byte, proof *Proof) (bool, error)
- type CompressedMultiproof
- type Multiproof
- type Node
- func EmptyLeaf() *Node
- func LeafFromBool(b bool) *Node
- func LeafFromBytes(b []byte) *Node
- func LeafFromUint8(i uint8) *Node
- func LeafFromUint16(i uint16) *Node
- func LeafFromUint32(i uint32) *Node
- func LeafFromUint64(i uint64) *Node
- func LeavesFromUint64(items []uint64) []*Node
- func NewEmptyNode(zeroOrderHash []byte) *Node
- func NewNodeWithLR(left, right *Node) *Node
- func NewNodeWithValue(value []byte) *Node
- func TreeFromChunks(chunks [][]byte) (*Node, error)
- func TreeFromNodes(leaves []*Node, limit int) (*Node, error)
- func TreeFromNodesProgressive(leaves []*Node) (*Node, error)
- func TreeFromNodesProgressiveWithActiveFields(leaves []*Node, activeFields []byte) (*Node, error)
- func TreeFromNodesProgressiveWithMixin(leaves []*Node, num int) (*Node, error)
- func TreeFromNodesWithMixin(leaves []*Node, num, limit int) (*Node, error)
- func (n *Node) Get(index int) (*Node, error)
- func (n *Node) Hash() []byte
- func (n *Node) IsEmpty() bool
- func (n *Node) IsLeaf() bool
- func (n *Node) Left() *Node
- func (n *Node) Prove(index int) (*Proof, error)
- func (n *Node) ProveMulti(indices []int) (*Multiproof, error)
- func (n *Node) Right() *Node
- func (n *Node) Show(maxDepth int)
- func (n *Node) Value() []byte
- type Proof
- type Wrapper
- func (w *Wrapper) AddBytes(b []byte)
- func (w *Wrapper) AddEmpty()
- func (w *Wrapper) AddNode(n *Node)
- func (w *Wrapper) AddUint8(i uint8)
- func (w *Wrapper) AddUint16(i uint16)
- func (w *Wrapper) AddUint32(i uint32)
- func (w *Wrapper) AddUint64(i uint64)
- func (w *Wrapper) Append(i []byte)
- func (w *Wrapper) AppendBool(b bool)
- func (w *Wrapper) AppendBytes32(b []byte)
- func (w *Wrapper) AppendUint8(i uint8)
- func (w *Wrapper) AppendUint16(i uint16)
- func (w *Wrapper) AppendUint32(i uint32)
- func (w *Wrapper) AppendUint64(i uint64)
- func (w *Wrapper) Collapse()
- func (w *Wrapper) Commit(i int)
- func (w *Wrapper) CommitProgressive(i int)
- func (w *Wrapper) CommitProgressiveWithActiveFields(i int, activeFields []byte)
- func (w *Wrapper) CommitProgressiveWithMixin(i, num int)
- func (w *Wrapper) CommitWithMixin(i, num, limit int)
- func (w *Wrapper) CurrentIndex() int
- func (w *Wrapper) FillUpTo32()
- func (w *Wrapper) Hash() []byte
- func (w *Wrapper) HashRoot() ([32]byte, error)
- func (w *Wrapper) Index() int
- func (w *Wrapper) Merkleize(indx int)
- func (w *Wrapper) MerkleizeProgressive(indx int)
- func (w *Wrapper) MerkleizeProgressiveWithActiveFields(indx int, activeFields []byte)
- func (w *Wrapper) MerkleizeProgressiveWithMixin(indx int, num uint64)
- func (w *Wrapper) MerkleizeWithMixin(indx int, num, limit uint64)
- func (w *Wrapper) Node() *Node
- func (w *Wrapper) PutBitlist(bb []byte, maxSize uint64)
- func (w *Wrapper) PutBool(b bool)
- func (w *Wrapper) PutBytes(b []byte)
- func (w *Wrapper) PutProgressiveBitlist(bb []byte)
- func (w *Wrapper) PutUint8(i uint8)
- func (w *Wrapper) PutUint16(i uint16)
- func (w *Wrapper) PutUint32(i uint32)
- func (w *Wrapper) PutUint64(i uint64)
- func (w *Wrapper) PutUint64Array(b []uint64, maxCapacity ...uint64)
- func (w *Wrapper) StartTree(_ sszutils.TreeType) int
- func (w *Wrapper) WithTemp(fn func(tmp []byte) []byte)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func VerifyMultiproof ¶
VerifyMultiproof verifies a proof for multiple leaves against the given root.
The arguments provided to this function need to adhere to some ordering rules, otherwise a successful verification is not guaranteed even if the client holds correct data:
1. `leaves` and `indices` have same order, i.e. `leaves[i]` is the leaf at `indices[i]`;
2. `proofs` are sorted in descending order according to their generalised indices.
For a better understanding of "2.", consider the following the tree:
. . . * = intermediate hash (i.e. an element of `proof`) . * * . x = leaf x x . . . . x *
In the example above, we have three intermediate hashes in position 5, 6 and 15. Let's call such hashes "*5", "*6" and "*15" respectively. Then, when calling this function `proof` should be ordered as [*15, *6, *5].
Types ¶
type CompressedMultiproof ¶
type CompressedMultiproof struct {
Indices []int
Leaves [][]byte
Hashes [][]byte
ZeroLevels []int // Stores the level for every omitted zero hash in the proof
}
CompressedMultiproof represents a compressed merkle proof of several leaves. Compression is achieved by omitting zero hashes (and their hashes). `ZeroLevels` contains information which helps the verifier fill in those hashes.
func (*CompressedMultiproof) Decompress ¶
func (c *CompressedMultiproof) Decompress() *Multiproof
Decompress returns a new multiproof, filling in the omitted zero hashes. See `CompressedMultiProof` for more info.
type Multiproof ¶
type Multiproof struct {
Indices []int // Generalized indices of proven leaves
Leaves [][]byte // 32-byte leaf values (ordered by Indices)
Hashes [][]byte // Shared verification hashes
}
Multiproof represents an efficient Merkle proof for multiple leaves.
Instead of generating separate proofs for each leaf, a multiproof consolidates the verification data by sharing common intermediate hashes. This is more efficient when proving multiple values from the same tree.
Fields:
- Indices: The generalized indices of all leaves being proven
- Leaves: The 32-byte values at the specified indices (same order as Indices)
- Hashes: Shared set of hashes needed to verify all leaves
func (*Multiproof) Compress ¶
func (p *Multiproof) Compress() *CompressedMultiproof
Compress returns a new proof with zero hashes omitted. See `CompressedMultiproof` for more info.
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node represents a single node in a Merkle tree constructed from SSZ data.
Each node can be either a leaf node (containing actual data) or a branch node (containing the hash of its children). The tree structure follows SSZ merkleization rules and supports both binary and progressive tree layouts.
For leaf nodes:
- left and right are nil
- value contains the 32-byte leaf data
For branch nodes:
- left and right point to child nodes
- value contains the computed hash of children (cached after first calculation)
The isEmpty field indicates whether this is a "zero" node used for padding incomplete trees to maintain proper binary tree structure.
func EmptyLeaf ¶
func EmptyLeaf() *Node
EmptyLeaf creates a leaf node containing 32 zero bytes, representing an empty or unset value in the Merkle tree.
func LeafFromBool ¶
LeafFromBool creates a 32-byte leaf node from a boolean value, encoded as 0x01 (true) or 0x00 (false) in the first byte with 31 bytes zero-padded.
func LeafFromBytes ¶
LeafFromBytes creates a 32-byte leaf node from a byte slice. If the slice is shorter than 32 bytes, it is right-padded with zeros. Panics if the slice exceeds 32 bytes.
func LeafFromUint8 ¶
LeafFromUint8 creates a 32-byte leaf node from a uint8 value, stored in the first byte with the remaining 31 bytes zero-padded.
func LeafFromUint16 ¶
LeafFromUint16 creates a 32-byte leaf node from a uint16 value, encoded as little-endian in the first 2 bytes with the remaining 30 bytes zero-padded.
func LeafFromUint32 ¶
LeafFromUint32 creates a 32-byte leaf node from a uint32 value, encoded as little-endian in the first 4 bytes with the remaining 28 bytes zero-padded.
func LeafFromUint64 ¶
LeafFromUint64 creates a 32-byte leaf node from a uint64 value, encoded as little-endian in the first 8 bytes with the remaining 24 bytes zero-padded.
func LeavesFromUint64 ¶
LeavesFromUint64 packs a slice of uint64 values into leaf nodes, with 4 values per 32-byte leaf (8 bytes each, little-endian). The final leaf is zero-padded if the number of items is not a multiple of 4.
func NewEmptyNode ¶
NewEmptyNode creates an empty (zero-padding) tree node with the given precomputed zero-order hash. Empty nodes represent unused positions in the binary tree and are marked with isEmpty=true for efficient proof compression.
func NewNodeWithLR ¶
NewNodeWithLR initializes a branch node.
func NewNodeWithValue ¶
NewNodeWithValue initializes a leaf node.
func TreeFromChunks ¶
TreeFromChunks constructs a tree from leaf values. The number of leaves should be a power of 2.
func TreeFromNodes ¶
TreeFromNodes constructs a tree from leaf nodes. This is useful for merging subtrees. The limit should be a power of 2. Adjacent sibling nodes will be filled with zero order hashes that have been precomputed based on the tree depth.
func TreeFromNodesProgressive ¶
TreeFromNodesProgressive constructs a progressive tree from leaf nodes. This implements the progressive merkleization algorithm where chunks are split using base_size pattern (1, 4, 16, 64...) rather than even binary splits. Based on subtree_fill_progressive from remerkleable.
func TreeFromNodesProgressiveWithActiveFields ¶
TreeFromNodesProgressiveWithActiveFields constructs a progressive tree with active fields bitvector. The progressive tree is created first, then mixed with the active fields.
func TreeFromNodesProgressiveWithMixin ¶
TreeFromNodesProgressiveWithMixin constructs a progressive tree with length mixin. The progressive tree is created first, then mixed with the length value.
func TreeFromNodesWithMixin ¶
TreeFromNodesWithMixin constructs a Merkle tree from leaves and mixes in the element count as a right sibling of the root. This is the standard SSZ merkleization for lists, where the tree root is hash(merkle_root || length). The limit is rounded up to the next power of two if not already one.
func (*Node) Hash ¶
Hash returns the hash of the subtree with the given Node as its root. If root has no children, it returns root's value (not its hash).
func (*Node) Prove ¶
Prove returns a list of sibling values and hashes needed to compute the root hash for a given general index.
func (*Node) ProveMulti ¶
func (n *Node) ProveMulti(indices []int) (*Multiproof, error)
ProveMulti generates a Multiproof for the given set of generalized indices. It collects the leaf values at each index and the minimal set of auxiliary hashes needed to reconstruct the root. Returns an error if any index cannot be found in the tree.
func (*Node) Show ¶
Show displays the tree structure in a human-readable format for debugging.
This method prints the complete tree hierarchy starting from this node, showing generalized indices, hash values, and the tree structure. It's particularly useful for understanding how SSZ data maps to tree nodes and for debugging proof generation.
Parameters:
- maxDepth: Maximum depth to display (0 for unlimited depth)
Output format:
- INDEX: The generalized index of each node
- HASH: 32-byte hash for branch nodes (computed from children)
- VALUE: 32-byte data for leaf nodes (actual SSZ field data)
- EMPTY: Indicates zero-padding nodes with their depth level
- LEFT/RIGHT: Tree structure showing child relationships
Example output:
--- Show node ---
INDEX: 1
HASH: a1b2c3d4...
LEFT:
INDEX: 2
VALUE: e5f6g7h8...
RIGHT:
INDEX: 3
HASH: i9j0k1l2...
LEFT:
INDEX: 6
VALUE: m3n4o5p6...
RIGHT:
INDEX: 7
EMPTY: true (depth: 0)
type Proof ¶
type Proof struct {
Index int // Generalized index of the proven leaf
Leaf []byte // 32-byte leaf value
Hashes [][]byte // Sibling hashes for verification path
}
Proof represents a Merkle proof for a single leaf against a generalized index.
A Merkle proof consists of the leaf value and a sequence of sibling hashes needed to reconstruct the path from the leaf to the root. The proof can be verified independently to confirm that the leaf value exists at the specified generalized index within the tree.
Fields:
- Index: The generalized index of the leaf being proven
- Leaf: The 32-byte value at the specified index
- Hashes: Ordered sequence of sibling hashes for the path to root
type Wrapper ¶
type Wrapper struct {
// contains filtered or unexported fields
}
Wrapper implements the sszutils.HashWalker interface to construct a complete Merkle tree instead of computing a single hash. This allows generating proofs for any field within an SSZ structure by building the tree during the same traversal that would normally produce only the hash tree root.
Usage:
w := treeproof.NewWrapper() // Use w as a HashWalker (e.g., via DynSsz.HashTreeRootWith or generated code) myStruct.HashTreeRootWithDyn(specs, w) tree := w.Node() proof, _ := tree.Prove(generalizedIndex)
func NewWrapper ¶
func NewWrapper() *Wrapper
NewWrapper creates a new Wrapper ready to construct a Merkle tree. The wrapper starts with an empty node list and pre-allocated scratch buffers.
func (*Wrapper) AddBytes ¶
AddBytes adds a byte slice as a leaf node (<=32 bytes) or as a merkleized subtree of 32-byte chunks (>32 bytes).
func (*Wrapper) AddEmpty ¶
func (w *Wrapper) AddEmpty()
AddEmpty adds an empty (all-zeros) leaf node to the wrapper's node list.
func (*Wrapper) Append ¶
Append appends raw bytes to the internal buffer. These bytes are converted to leaf nodes when a Merkleize method is called.
func (*Wrapper) AppendBool ¶
AppendBool appends a single-byte boolean (0x00 or 0x01) to the internal buffer.
func (*Wrapper) AppendBytes32 ¶
AppendBytes32 appends the given bytes to the internal buffer and pads with zeros to the next 32-byte boundary via FillUpTo32.
func (*Wrapper) AppendUint8 ¶
AppendUint8 appends a single byte to the internal buffer.
func (*Wrapper) AppendUint16 ¶
AppendUint16 appends a little-endian uint16 (2 bytes) to the internal buffer.
func (*Wrapper) AppendUint32 ¶
AppendUint32 appends a little-endian uint32 (4 bytes) to the internal buffer.
func (*Wrapper) AppendUint64 ¶
AppendUint64 appends a little-endian uint64 (8 bytes) to the internal buffer.
func (*Wrapper) Collapse ¶ added in v1.3.0
func (w *Wrapper) Collapse()
Collapse is a no-op for the tree proof wrapper.
func (*Wrapper) Commit ¶
Commit constructs a binary Merkle tree from all nodes added since index i, replaces those nodes with the resulting subtree root, and adds it back to the node list.
func (*Wrapper) CommitProgressive ¶
CommitProgressive creates a progressive tree from nodes
func (*Wrapper) CommitProgressiveWithActiveFields ¶
CommitProgressiveWithActiveFields creates a progressive tree with active fields bitvector
func (*Wrapper) CommitProgressiveWithMixin ¶
CommitProgressiveWithMixin creates a progressive tree with length mixin
func (*Wrapper) CommitWithMixin ¶
CommitWithMixin constructs a binary Merkle tree from nodes since index i with a length mixin, used for SSZ list merkleization.
func (*Wrapper) CurrentIndex ¶ added in v1.3.0
CurrentIndex returns the current buffer index (debug only)
func (*Wrapper) FillUpTo32 ¶
func (w *Wrapper) FillUpTo32()
FillUpTo32 pads the internal buffer with zero bytes so its length is a multiple of 32. This ensures proper 32-byte chunk alignment for leaf nodes.
func (*Wrapper) HashRoot ¶
HashRoot returns the 32-byte hash tree root of the constructed tree. This implements the HashWalker interface's final step, producing the same root hash that a regular Hasher would compute.
func (*Wrapper) Index ¶
Index returns the current number of nodes in the wrapper's node list. This value is used as a checkpoint for subsequent Merkleize calls to identify which nodes should be combined into a subtree.
func (*Wrapper) Merkleize ¶
Merkleize flushes any buffered bytes as leaf nodes, then constructs a binary Merkle tree from all nodes added since the checkpoint index indx. The resulting subtree replaces those nodes as a single tree node.
func (*Wrapper) MerkleizeProgressive ¶
MerkleizeProgressive flushes buffered bytes, then constructs a progressive Merkle tree from nodes since indx using the progressive split pattern (base sizes 1, 4, 16, 64...) instead of even binary splits.
func (*Wrapper) MerkleizeProgressiveWithActiveFields ¶
MerkleizeProgressiveWithActiveFields flushes buffered bytes, constructs a progressive Merkle tree from nodes since indx, and mixes in the active fields bitvector as a right sibling. This is used for stable/progressive containers.
func (*Wrapper) MerkleizeProgressiveWithMixin ¶
MerkleizeProgressiveWithMixin flushes buffered bytes, constructs a progressive Merkle tree from nodes since indx, and mixes in the element count (num) as a right sibling.
func (*Wrapper) MerkleizeWithMixin ¶
MerkleizeWithMixin flushes buffered bytes, constructs a binary Merkle tree from nodes since indx, and mixes in the element count (num) as a right sibling. This implements SSZ list merkleization: hash(merkle_root || length).
func (*Wrapper) Node ¶
Node returns the single root node of the constructed Merkle tree. Panics if the wrapper does not contain exactly one node, which indicates incomplete merkleization.
func (*Wrapper) PutBitlist ¶
PutBitlist parses a bitlist (with sentinel bit), creates leaf nodes from the data, and merkleizes them with a length mixin. The maxSize parameter determines the tree limit for proper padding.
func (*Wrapper) PutBytes ¶
PutBytes adds a byte slice as one or more 32-byte leaf nodes. If the slice exceeds 32 bytes, it is split into chunks and merkleized into a subtree.
func (*Wrapper) PutProgressiveBitlist ¶
PutProgressiveBitlist parses a bitlist (with sentinel bit), creates leaf nodes from the data, and merkleizes them using the progressive tree algorithm with a length mixin.
func (*Wrapper) PutUint64Array ¶
PutUint64Array appends all uint64 values as buffered bytes, pads to 32-byte alignment, and merkleizes. If maxCapacity is provided, the result is merkleized with a length mixin (list semantics); otherwise it uses fixed-size merkleization (vector semantics).
Source Files