treeproof

package
v1.1.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 8, 2025 License: Apache-2.0 Imports: 11 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

func VerifyMultiproof 

func VerifyMultiproof(root []byte, proof [][]byte, leaves [][]byte, indices []int) (bool, error)

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].

func VerifyProof 

func VerifyProof(root []byte, proof *Proof) (bool, error)

VerifyProof verifies a single merkle branch. It's more efficient than VerifyMultiproof for proving one leaf.

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

func LeafFromBool 

func LeafFromBool(b bool) *Node

func LeafFromBytes 

func LeafFromBytes(b []byte) *Node

func LeafFromUint8 

func LeafFromUint8(i uint8) *Node

func LeafFromUint16 

func LeafFromUint16(i uint16) *Node

func LeafFromUint32 

func LeafFromUint32(i uint32) *Node

func LeafFromUint64 

func LeafFromUint64(i uint64) *Node

func LeavesFromUint64 

func LeavesFromUint64(items []uint64) []*Node

func NewEmptyNode 

func NewEmptyNode(zeroOrderHash []byte) *Node

func NewNodeWithLR 

func NewNodeWithLR(left, right *Node) *Node

NewNodeWithLR initializes a branch node.

func NewNodeWithValue 

func NewNodeWithValue(value []byte) *Node

NewNodeWithValue initializes a leaf node.

func TreeFromChunks 

func TreeFromChunks(chunks [][]byte) (*Node, error)

TreeFromChunks constructs a tree from leaf values. The number of leaves should be a power of 2.

func TreeFromNodes 

func TreeFromNodes(leaves []*Node, limit int) (*Node, error)

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 

func TreeFromNodesProgressive(leaves []*Node) (*Node, error)

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 

func TreeFromNodesProgressiveWithActiveFields(leaves []*Node, activeFields []byte) (*Node, error)

TreeFromNodesProgressiveWithActiveFields constructs a progressive tree with active fields bitvector. The progressive tree is created first, then mixed with the active fields.

func TreeFromNodesProgressiveWithMixin 

func TreeFromNodesProgressiveWithMixin(leaves []*Node, num int) (*Node, error)

TreeFromNodesProgressiveWithMixin constructs a progressive tree with length mixin. The progressive tree is created first, then mixed with the length value.

func TreeFromNodesWithMixin 

func TreeFromNodesWithMixin(leaves []*Node, num, limit int) (*Node, error)

func (*Node) Get 

func (n *Node) Get(index int) (*Node, error)

Get fetches a node with the given general index.

func (*Node) Hash 

func (n *Node) Hash() []byte

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) IsEmpty 

func (n *Node) IsEmpty() bool

IsEmpty returns true if this node represents zero-padding.

func (*Node) IsLeaf 

func (n *Node) IsLeaf() bool

IsLeaf returns true if this node has no children (is a leaf node).

func (*Node) Left 

func (n *Node) Left() *Node

Left returns the left child node, or nil if this is a leaf.

func (*Node) Prove 

func (n *Node) Prove(index int) (*Proof, error)

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) Right 

func (n *Node) Right() *Node

Right returns the right child node, or nil if this is a leaf.

func (*Node) Show 

func (n *Node) Show(maxDepth int)

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)

func (*Node) Value 

func (n *Node) Value() []byte

Value returns the raw 32-byte value stored in this node.

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) AddBytes 

func (w *Wrapper) AddBytes(b []byte)

func (*Wrapper) AddEmpty 

func (w *Wrapper) AddEmpty()

func (*Wrapper) AddNode 

func (w *Wrapper) AddNode(n *Node)

func (*Wrapper) AddUint8 

func (w *Wrapper) AddUint8(i uint8)

func (*Wrapper) AddUint16 

func (w *Wrapper) AddUint16(i uint16)

func (*Wrapper) AddUint32 

func (w *Wrapper) AddUint32(i uint32)

func (*Wrapper) AddUint64 

func (w *Wrapper) AddUint64(i uint64)

func (*Wrapper) Append 

func (w *Wrapper) Append(i []byte)

func (*Wrapper) AppendBool 

func (w *Wrapper) AppendBool(b bool)

func (*Wrapper) AppendBytes32 

func (w *Wrapper) AppendBytes32(b []byte)

func (*Wrapper) AppendUint8 

func (w *Wrapper) AppendUint8(i uint8)

func (*Wrapper) AppendUint16 

func (w *Wrapper) AppendUint16(i uint16)

func (*Wrapper) AppendUint32 

func (w *Wrapper) AppendUint32(i uint32)

func (*Wrapper) AppendUint64 

func (w *Wrapper) AppendUint64(i uint64)

func (*Wrapper) Commit 

func (w *Wrapper) Commit(i int)

func (*Wrapper) CommitProgressive 

func (w *Wrapper) CommitProgressive(i int)

CommitProgressive creates a progressive tree from nodes

func (*Wrapper) CommitProgressiveWithActiveFields 

func (w *Wrapper) CommitProgressiveWithActiveFields(i int, activeFields []byte)

CommitProgressiveWithActiveFields creates a progressive tree with active fields bitvector

func (*Wrapper) CommitProgressiveWithMixin 

func (w *Wrapper) CommitProgressiveWithMixin(i, num int)

CommitProgressiveWithMixin creates a progressive tree with length mixin

func (*Wrapper) CommitWithMixin 

func (w *Wrapper) CommitWithMixin(i, num, limit int)

func (*Wrapper) FillUpTo32 

func (w *Wrapper) FillUpTo32()

func (*Wrapper) Hash 

func (w *Wrapper) Hash() []byte

func (*Wrapper) HashRoot 

func (w *Wrapper) HashRoot() ([32]byte, error)

func (*Wrapper) Index 

func (w *Wrapper) Index() int

func (*Wrapper) Merkleize 

func (w *Wrapper) Merkleize(indx int)

func (*Wrapper) MerkleizeProgressive 

func (w *Wrapper) MerkleizeProgressive(indx int)

func (*Wrapper) MerkleizeProgressiveWithActiveFields 

func (w *Wrapper) MerkleizeProgressiveWithActiveFields(indx int, activeFields []byte)

func (*Wrapper) MerkleizeProgressiveWithMixin 

func (w *Wrapper) MerkleizeProgressiveWithMixin(indx int, num uint64)

func (*Wrapper) MerkleizeWithMixin 

func (w *Wrapper) MerkleizeWithMixin(indx int, num, limit uint64)

func (*Wrapper) Node 

func (w *Wrapper) Node() *Node

func (*Wrapper) PutBitlist 

func (w *Wrapper) PutBitlist(bb []byte, maxSize uint64)

func (*Wrapper) PutBool 

func (w *Wrapper) PutBool(b bool)

func (*Wrapper) PutBytes 

func (w *Wrapper) PutBytes(b []byte)

func (*Wrapper) PutProgressiveBitlist 

func (w *Wrapper) PutProgressiveBitlist(bb []byte)

func (*Wrapper) PutUint8 

func (w *Wrapper) PutUint8(i uint8)

func (*Wrapper) PutUint16 

func (w *Wrapper) PutUint16(i uint16)

func (*Wrapper) PutUint32 

func (w *Wrapper) PutUint32(i uint32)

func (*Wrapper) PutUint64 

func (w *Wrapper) PutUint64(i uint64)

func (*Wrapper) PutUint64Array 

func (w *Wrapper) PutUint64Array(b []uint64, maxCapacity ...uint64)

func (*Wrapper) WithTemp 

func (w *Wrapper) WithTemp(fn func(tmp []byte) []byte)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.