Sparse Merkle Trees

Sparse Merkle Trees — Nethereum.Merkle

When to Use This

Use this skill when a user wants to:

• Build a sparse Merkle tree for ZK circuit inputs (Circom, Halo2, Noir)
• Use Poseidon hashing for circuit-friendly Merkle trees
• Build Celestia-compatible sparse Merkle trees
• Create membership or non-membership proofs for privacy pools or anonymous voting
• Persist large Merkle trees with lazy node loading

Required Packages

dotnet add package Nethereum.Merkle
dotnet add package Nethereum.Util

Core Concept

SparseMerkleBinaryTree<T> is a binary sparse Merkle tree where:

• Keys are converted to bit paths for tree traversal
• Leaves store value hashes at the key's path
• Empty subtrees have a fixed hash (no storage needed)
• Root hash is deterministic regardless of insertion order

The ISmtHasher interface controls hashing. Three built-in strategies:

Poseidon SMT for ZK Circuits

The most common use case — a Poseidon-based tree whose root can be used directly as a public input in Circom proofs:

using Nethereum.Merkle.Sparse;
using Nethereum.Util.ByteArrayConvertors;

var smt = new SparseMerkleBinaryTree<byte[]>(
    new PoseidonSmtHasher(),
    new ByteArrayToByteArrayConvertor(),
    new IdentitySmtKeyHasher(256));

smt.Put(key1, value1);
smt.Put(key2, value2);
var root = smt.ComputeRoot();  // Circom-compatible root hash

var value = smt.Get(key1);
smt.Delete(key1);

Poseidon hash details:

• Leaf: Poseidon(key, value, 1) using CircomT3 (3 inputs)
• Node: Poseidon(left, right) using CircomT2 (2 inputs)

Celestia-Compatible SMT

var smt = new SparseMerkleBinaryTree<byte[]>(
    new CelestiaSmtHasher(),
    new ByteArrayToByteArrayConvertor());

smt.Put(key, value);
var root = smt.ComputeRoot();

Hash formulas:

• Leaf: SHA256(0x00 || path || SHA256(value))
• Node: SHA256(0x01 || leftHash || rightHash)

Persistent Storage (Async API)

For trees that survive process restarts:

var storage = new InMemorySmtNodeStorage();
var smt = new SparseMerkleBinaryTree<byte[]>(
    new PoseidonSmtHasher(),
    new ByteArrayToByteArrayConvertor(),
    new IdentitySmtKeyHasher(256),
    storage: storage);

await smt.PutAsync(key1, value1);
await smt.PutAsync(key2, value2);
var root = await smt.ComputeRootAsync();
await smt.FlushAsync();  // Persist all nodes

// Later — reload from storage
var smt2 = new SparseMerkleBinaryTree<byte[]>(
    new PoseidonSmtHasher(),
    new ByteArrayToByteArrayConvertor(),
    new IdentitySmtKeyHasher(256),
    storage: storage);
await smt2.LoadRootAsync(root);  // Lazy-loads nodes on demand

Batch Operations

var entries = new Dictionary<byte[], byte[]>
{
    { key1, value1 },
    { key2, value2 },
    { key3, value3 }
};

smt.PutBatch(entries);           // Sync
await smt.PutBatchAsync(entries); // Async

Console.WriteLine($"Leaves: {smt.LeafCount}");

Key Path Strategies

Node Serialization (SmtNodeCodec)

For custom storage backends:

byte[] encoded = SmtNodeCodec.EncodeLeaf(path, valueBytes);
SmtNodeCodec.DecodeLeaf(encoded, out var path, out var value);

byte[] branch = SmtNodeCodec.EncodeBranch(leftHash, rightHash);
SmtNodeCodec.DecodeBranch(branch, 32, out var left, out var right);

bool isLeaf = SmtNodeCodec.IsLeaf(data);
bool isBranch = SmtNodeCodec.IsBranch(data);

Common Gotchas

• The tree root is deterministic — insertion order doesn't matter
• PoseidonSmtHasher uses LSB-first bit ordering, CelestiaSmtHasher uses MSB-first
• InMemorySmtNodeStorage is thread-safe (ConcurrentDictionary) but for production use, implement ISmtNodeStorage with a database backend
• IdentitySmtKeyHasher requires keys to be the exact bit length specified — use Sha256SmtKeyHasher for variable-length keys

For full documentation, see: https://docs.nethereum.com/docs/consensus-and-cryptography/guide-sparse-merkle-zk