Merkle Tree on Go: generics and proof

Merkle Tree in Go: Implementation with Generics and Proof of Inclusion

In systems with millions of records, such as blockchains, verifying the presence of a specific element typically requires transmitting the entire dataset. Merkle Tree solves this problem: instead of a million transactions, only O(log N) hashes are needed—about 20 for a million elements. The structure is built as a binary tree, where each node hashes its children, and the root summarizes the entire set.

Example: transactions A, B, C, D. Directly hashing the entire set requires the client to have all data for verification. In the tree, the client receives neighboring hashes: H(B), H(CD)—and independently reconstructs the root hash from leaf A to the root.

Basic Interfaces and Node Types

Start with an interface for all tree nodes, supporting generics:

type Node[T any] interface {
    String() string
    StringIndent(level int) string
    AddChild(Node[T])
    GetBytes() []byte
    GetChildren() []Node[T]
}

Leaves store the value and its hash. For serializing any-type values, use CBOR—a deterministic format (RFC 8949), unlike JSON with unstable key order in maps.

type Leaf[T any] struct {
    Value     T
    ValueHash []byte
}

func NewLeaf[T any](value T, hash hash.Hash) (*Leaf[T], error) {
    hashedValue, err := valueToHash(value, hash)
    if err != nil {
        return nil, err
    }
    return &Leaf[T]{Value: value, ValueHash: hashedValue}, nil
}

func valueToHash(value any, hash hash.Hash) ([]byte, error) {
    encoded, err := cbor.Marshal(value)
    if err != nil {
        return nil, err
    }
    hash.Reset()
    hash.Write(encoded)
    return hash.Sum(nil), nil
}

Binary nodes aggregate left and right children:

type BinaryNode[T any] struct {
    Value []byte
    Right Node[T]
    Left  Node[T]
}

Building the Tree with a Hash Function Factory

The tree is managed by a structure with a factory for creating clean hash instances—hash.Hash has state, so pass a function:

type BinaryTree[T any] struct {
    newHash func() hash.Hash
}

func NewBinaryTree[T any](newHash func() hash.Hash) *BinaryTree[T] {
    return &BinaryTree[T]{newHash: newHash}
}

// Usage
tree := NewBinaryTree[string](sha256.New)

Construction: leaves hash values, internal nodes hash the concatenation of children's hashes. H(AB) = SHA256(H(A) + H(B)). The root is the final hash of the entire tree.

Merkle Proof: Generation and Verification

Proof of inclusion is a key mechanism. The client knows the target hash (H(A)) and the root hash. The server provides neighbor hashes along the path from the leaf to the root.

Generation Algorithm

• From the root, descend to the target leaf.
• At each level, save the hash of the sibling node (left or right, not part of the path).
• The proof is a list of these hashes.

Verification from bottom to top:

• Start with H(A).
• Sequentially hash with neighbors, alternating sides (left/right).
• Reach the root—a match confirms inclusion.

For 2^20 elements (a million), the proof is 20 hashes of 32 bytes each, ~640 bytes.

Advantages and Applications

• Logarithmic complexity: O(log N) for proof, ideal for SPV clients.
• Minimal traffic: Bitcoin SPV verifies transactions without the full block (500+ GB).

Applications:

• Bitcoin: Transaction root in the block header.
• Ethereum: State trie, transaction trie, receipt trie.
• Git: Tree objects in commits.
• IPFS: Content hash as the root of chunks.
• Certificate Transparency: Auditing SSL certificate logs.

Key Takeaways

• Merkle Tree proves inclusion in O(log N) without revealing other data.
• Use generics in Go for type safety; CBOR for deterministic hashing of any.
• Hash function factory prevents race conditions from hash.Hash state.
• Proof is generated from sibling hashes along the path from leaf to root.
• Efficient for distributed systems: blockchains, P2P storage.

— Editorial Team