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 [][]byte, 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) 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) 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) 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 LeafFromBool ¶
func LeafFromBytes ¶
func LeafFromUint8 ¶
func LeafFromUint16 ¶
func LeafFromUint32 ¶
func LeafFromUint64 ¶
func LeavesFromUint64 ¶
func NewEmptyNode ¶
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 ¶
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)
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
}
func NewWrapper ¶
func NewWrapper() *Wrapper
func (*Wrapper) AppendBool ¶
func (*Wrapper) AppendBytes32 ¶
func (*Wrapper) AppendUint8 ¶
func (*Wrapper) AppendUint16 ¶
func (*Wrapper) AppendUint32 ¶
func (*Wrapper) AppendUint64 ¶
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 ¶
func (*Wrapper) FillUpTo32 ¶
func (w *Wrapper) FillUpTo32()
Source Files