poseidon2-merkle-go

Append-only incremental Merkle tree with Poseidon2 hashing over the BN254 scalar field.

This is a pure in-memory implementation of the frontier (incremental) Merkle tree algorithm used in Tornado Cash, Semaphore, and other zero-knowledge privacy protocols. It produces identical roots to the NixProtocol on-chain tree.

Features

• O(depth) insert — frontier approach stores one value per level
• O(depth) proof generation — sparse node storage enables Merkle path extraction
• Zero-allocation verification — VerifyProof allocates nothing
• Configurable depth — 1 to 40 levels (up to 2^40 leaves)
• Thread-safe wrapper — SafeTree with sync.RWMutex for concurrent access
• Batch insert — InsertBatch for high-throughput scenarios (single lock acquisition)
• Serialization — Marshal/Unmarshal for persistence and snapshots
• Structured errors — sentinel errors with errors.Is() support
• No storage dependencies — pure Go, no database or blockchain coupling

Installation

go get github.com/nixprotocol/poseidon2-merkle-go

Usage

package main

import (
    "fmt"

    "github.com/consensys/gnark-crypto/ecc/bn254/fr"
    merkle "github.com/nixprotocol/poseidon2-merkle-go"
)

func main() {
    // Create a depth-20 tree (up to 1M leaves)
    tree, err := merkle.New(20)
    if err != nil {
        panic(err)
    }

    // Insert a leaf
    var leaf fr.Element
    leaf.SetUint64(42)
    root, index, err := tree.Insert(leaf)
    if err != nil {
        panic(err)
    }
    fmt.Printf("Leaf %d, Root: %s\n", index, root.String())

    // Generate a Merkle inclusion proof
    proof, err := tree.Path(0)
    if err != nil {
        panic(err)
    }

    // Verify the proof
    valid := merkle.VerifyProof(proof, root, 20)
    fmt.Println("Valid:", valid) // true
}

Thread-safe usage

// SafeTree wraps Tree with sync.RWMutex for concurrent access
st, _ := merkle.NewSafe(20)

// Concurrent inserts are safe
go st.Insert(leaf1)
go st.Insert(leaf2)

// Batch insert — single lock acquisition for multiple leaves
root, firstIdx, err := st.InsertBatch(leaves)

Serialization

// Save tree state
data := tree.Marshal()
os.WriteFile("tree.snapshot", data, 0644)

// Restore tree state
data, _ := os.ReadFile("tree.snapshot")
tree, err := merkle.Unmarshal(data)

// Thread-safe variant
st, err := merkle.UnmarshalSafe(data)

Error handling

_, _, err := tree.Insert(leaf)
if errors.Is(err, merkle.ErrTreeFull) {
    // tree has reached 2^depth capacity
}

_, err := tree.Leaf(999)
if errors.Is(err, merkle.ErrIndexOutOfRange) {
    // index >= tree.Count()
}

API

Tree (single-threaded)

Function / Type	Description
New(depth) (*Tree, error)	Create an empty tree with the given depth (1–40)
Tree.Insert(leaf) (root, index, error)	Append a leaf, return new root and leaf index
Tree.Root() fr.Element	Current Merkle root
Tree.Path(index) (*Proof, error)	Generate inclusion proof for a leaf
Tree.Leaf(index) (fr.Element, error)	Retrieve a previously inserted leaf
Tree.Count() uint64	Number of inserted leaves
Tree.NextIndex() uint64	Index that will be assigned to the next leaf
Tree.Capacity() uint64	Maximum number of leaves (2^depth)
Tree.Depth() uint32	Tree depth
Tree.Marshal() []byte	Serialize tree state for persistence
Unmarshal(data) (*Tree, error)	Restore a tree from a snapshot
VerifyProof(proof, root, depth) bool	Verify a Merkle inclusion proof (standalone)
ZeroHash(level) fr.Element	Precomputed root of an empty subtree at the given level

SafeTree (thread-safe)

Function / Type	Description
NewSafe(depth) (*SafeTree, error)	Create a thread-safe empty tree
SafeTree.Insert(leaf) (root, index, error)	Append a leaf (exclusive lock)
SafeTree.InsertBatch(leaves) (root, firstIndex, error)	Append multiple leaves in one lock acquisition
SafeTree.Root() fr.Element	Current root (read lock)
SafeTree.Path(index) (*Proof, error)	Generate proof (read lock)
SafeTree.Leaf(index) (fr.Element, error)	Retrieve leaf (read lock)
SafeTree.Count() uint64	Leaf count (read lock)
SafeTree.NextIndex() uint64	Next index (read lock)
SafeTree.Capacity() uint64	Max leaves (read lock)
SafeTree.Depth() uint32	Tree depth (read lock)
SafeTree.Marshal() []byte	Serialize (read lock)
UnmarshalSafe(data) (*SafeTree, error)	Restore a thread-safe tree

Sentinel errors

Error	Returned by
ErrTreeFull	Insert, InsertBatch when tree is at capacity
ErrIndexOutOfRange	Leaf, Path when index >= count
ErrDepthOutOfRange	New, NewSafe when depth is 0 or > 40
ErrInvalidSnapshot	Unmarshal, UnmarshalSafe when data is malformed

All errors support errors.Is() and include contextual details in the message.

Algorithm

The tree uses the frontier approach (also called incremental Merkle tree):

1. Insert: Walk from leaf to root. At each level:
   • If current index is even (left child): store hash as frontier, pair with zero sibling
   • If current index is odd (right child): pair with stored frontier
2. Storage: Only one "frontier" value per level + sparse map of computed nodes
3. Proof: Look up sibling at each level from the sparse node map; missing nodes are zero subtrees

This matches the algorithm used in Tornado Cash, Semaphore, and the NixProtocol on-chain Cosmos SDK keeper.

Serialization Format

Marshal produces a binary snapshot with the following wire format:

[4]  magic "MKL1"
[4]  depth    (big-endian uint32)
[8]  count    (big-endian uint64)
[depth * 32]  frontier elements
[8]  numNodes (big-endian uint64)
for each node:
  [4]  level   (big-endian uint32)
  [8]  index   (big-endian uint64)
  [32] value   (fr.Element bytes)

Unmarshal validates all fields and returns ErrInvalidSnapshot for any malformed data.

Threat Model

What this library does

• Constructs append-only Merkle trees using Poseidon2 as the internal hash
• Generates Merkle inclusion proofs (sibling paths)
• Verifies proofs against a given root

Trust boundaries

Input	Trust level	Validation
Leaves to insert	Application data	Accepted as-is (any field element is valid)
Proof from untrusted source	Untrusted	VerifyProof validates all fields; returns false on any mismatch
Root from untrusted source	Untrusted	Application must compare against known-good roots
Serialized snapshot	Untrusted	Unmarshal validates magic, bounds, and structure

Assumptions

• Poseidon2 collision resistance: Tree security relies on poseidon2-go being collision-resistant
• Concurrency: Tree is NOT safe for concurrent writes — use SafeTree for concurrent access
• Append-only: Leaves cannot be updated or deleted after insertion

Out of scope

• Persistent storage (the tree is in-memory only; use Marshal/Unmarshal for persistence hooks)
• Nullifier tracking (application-level concern)
• Root history / race condition prevention (application-level concern)

Security Best Practices

1. Compare roots against a trusted source — VerifyProof only checks that the proof is internally consistent with the given root. Your application must verify the root itself is legitimate.

2. Use SafeTree for concurrent access — Tree is not safe for concurrent writes. SafeTree wraps it with a sync.RWMutex.

3. Use depth >= 20 for production — smaller depths limit the number of leaves and may be insufficient for real-world use.

4. Validate snapshots from untrusted sources — Unmarshal checks for structural validity but cannot detect semantically incorrect trees (e.g., wrong hashes). Only restore snapshots you trust.

Integration Guide

Client-side proof generation (for ZK circuits)

// Build tree from on-chain commitment events
tree, _ := merkle.New(32)
for _, commitment := range onChainCommitments {
    var leaf fr.Element
    leaf.SetBytes(commitment)
    tree.Insert(leaf)
}

// Generate proof for your leaf
proof, _ := tree.Path(myLeafIndex)

// Feed proof.Siblings and proof.Index into your ZK circuit
// as the Merkle path witness

High-throughput batch insertion

st, _ := merkle.NewSafe(32)

// InsertBatch acquires the lock once for all leaves
root, firstIdx, err := st.InsertBatch(commitments)

Persistence hooks

// Periodically snapshot the tree
data := tree.Marshal()
db.Put([]byte("merkle-snapshot"), data)

// On startup, restore from snapshot
data, _ := db.Get([]byte("merkle-snapshot"))
tree, err := merkle.Unmarshal(data)
// Continue inserting — the restored tree is fully functional

Verifying proofs off-chain

// Standalone verification — no tree instance needed
valid := merkle.VerifyProof(proof, expectedRoot, 32)

Cosmos SDK integration

For on-chain use, wrap the tree with a Cosmos SDK KVStore for persistence. See nix-cosmos for a reference implementation using the frontier approach with store-backed persistence, root history ring buffer, nullifier tracking, and duplicate commitment detection.

Performance

Benchmarks on Apple M1 Pro:

Operation	Depth	Time	Allocs
Insert	20	~254 µs	0
Insert	32	~402 µs	0
SafeTree.Insert	20	~260 µs	0
InsertBatch (100)	20	~25 ms	2
Path (proof gen)	20	~0.4 µs	2
VerifyProof	20	~236 µs	0
VerifyProof	32	~389 µs	0
Marshal (100 leaves)	20	~55 µs	2
Unmarshal (100 leaves)	20	~15 µs	3

Run benchmarks yourself:

go test -bench=. -benchmem

Testing

# Unit tests (98%+ coverage)
go test -v ./...

# Coverage report
go test -coverprofile=cover.out ./... && go tool cover -html=cover.out

# Fuzz testing
go test -fuzz=FuzzInsertAndVerify -fuzztime=30s
go test -fuzz=FuzzMarshalRoundTrip -fuzztime=30s
go test -fuzz=FuzzUnmarshal -fuzztime=30s
go test -fuzz=FuzzVerifyProof -fuzztime=30s

# Benchmarks
go test -bench=. -benchmem

Dependencies

Only two external dependencies:

• gnark-crypto — BN254 field arithmetic (fr.Element)
• poseidon2-go — Poseidon2 hash function

License

Apache 2.0 — See LICENSE.

Author

NixProtocol (GitHub)