rs-merkle-tree: a fast, fixed-depth Merkle tree with pluggable stores

A Merkle tree that stores every intermediate node is unusual. The design is explicit about what it trades away: intermediate leaves are stored so that proofs need not be calculated lazily, as the README puts it. rs-merkle-tree, whose Cargo metadata and copyright point to bilinearlabs while the repository is hosted under alrevuelta's GitHub account, does the opposite: it persists each level up to the root as leaves are added, so fetching a proof reads the DEPTH sibling nodes plus the leaf in one batched read, then fetches the root separately.

That design shows in the numbers. The README reports memory-store proofs at depth 32 coming back in about 196 nanoseconds on an M4 MacBook Pro; even the slowest backend listed (rocksdb) returns one in roughly 14 microseconds. Insertion throughput, by contrast, ranges from hundreds of thousands to tens of millions of elements per second depending on the store.

What it is

The crate exposes a generic MerkleTree<H, S, DEPTH> parameterized over three things: a hasher (Hasher trait), a storage backend (Store trait), and a compile-time depth. A convenience alias MerkleTree32 wires up Keccak256 with the in-memory store at depth 32.

Two constraints define the tree's shape:

• Fixed depth. Every proof is exactly [Node; DEPTH], so proof size never grows with leaf count.
• Append-only. Leaves are added sequentially from index zero and never modified. The README calls this out explicitly, and it keeps the write path simple: each call to add_leaves writes one contiguous run per level.

The public surface is small — new, add_leaves, root, num_leaves, proof, plus a verify_proof. A to_node! macro builds 32-byte nodes from hex strings for convenience in tests and examples.

How the write path works

add_leaves (in src/tree.rs) is where the performance work lives. Instead of hashing leaf by leaf, it processes one level at a time: the new leaves form a contiguous run at level 0, that run is paired into its parents at level 1, and so on up to the root.

pub fn add_leaves(&mut self, leaves: &[Node]) -> Result<(), MerkleError>

The comment in the source explains the payoff directly: hashing a level once instead of once per descendant leaf costs at most leaves + DEPTH hashes per call rather than leaves * DEPTH. Independent pairs on large levels are hashed in parallel on Rayon's global thread pool, but only above a threshold — below 64 hashes the scheduling overhead is not worth it (MIN_PARALLEL_HASHES = 64).

Two details keep this fast. First, each level goes to the store as one contiguous run via Store::put(level, start, nodes), so backends never have to sort out scattered positions. Second, intermediate levels live in two scratch buffers owned by the tree; a call only allocates when a batch is larger than every earlier one.

The hasher also gets a vectorized path. The Hasher trait provides a default hash_pairs, but Keccak256Hasher overrides it to feed batches through keccak_batch, which detects the widest SIMD backend the running CPU supports and splits work across lanes.

Pluggable storage

The Store trait is three methods: batched get(levels, indices), contiguous-run put(level, start, nodes), and get_num_leaves. Five implementations sit behind Cargo features so you only compile what you use:

• memory_store (default)
• sled_store
• sqlite_store
• rocksdb_store
• file_store — a flat store with one file per level, no database engine

The README's benchmark table shows the trade-off plainly. Memory and file stores insert at tens of millions of elements per second; rocksdb drops to about 4.4 million; sqlite and sled fall further still. Disk usage climbs in the same direction — memory uses none, while sled consumes over 1.6 GiB for five million leaves.

Two hash functions

Keccak256Hasher is built on keccak-batch. PoseidonHasher wraps light-poseidon, specifically the Poseidon BN254 Circom T3 variant, built on ark-bn254 and light-poseidon. The zero-node test vectors in src/tree.rs include both, with the Poseidon zeros cross-checked against zk-kit's lazy incremental Merkle tree contract.

Getting started

Add it as a dependency and pick your features:

[dependencies]
rs-merkle-tree = { version = "0.1.0", features = ["sled_store"] }

A minimal in-memory tree at depth 32, from the README:

use rs_merkle_tree::to_node;
use rs_merkle_tree::tree::MerkleTree32;

fn main() {
    let mut tree = MerkleTree32::default();
    tree.add_leaves(&[to_node!(
        "0x532c79f3ea0f4873946d1b14770eaa1c157255a003e73da987b858cc287b0482"
    )])
    .unwrap();

    println!("root: {:?}", tree.root().unwrap());
    println!("num leaves: {:?}", tree.num_leaves());
    println!("proof: {:?}", tree.proof(0).unwrap().proof);
}

Customizing the store and hasher means choosing a feature and naming the types explicitly:

let mut tree: MerkleTree<PoseidonHasher, RocksDbStore, 32> =
    MerkleTree::new(PoseidonHasher, RocksDbStore::new("rocksdb.db"));

Tests run with cargo test --all-features. Benchmarks need the all feature and a Python step:

cargo bench --features=all
python benchmarks.py

The Python script parses Criterion output into Markdown tables for proof time, runs an ignored disk-space test to measure store footprint, and captures the insertions benchmark's own printed table.

Who it is for

This is not a general-purpose Merkle tree. The fixed-depth, append-only design makes sense when you control the leaf count up front — workloads that need a fixed-size proof from an append-only tree. If you need dynamic leaves, variable-size proofs, or updates to existing values, this crate's constraints will fight you.

The eager storage is a real cost: five million leaves at depth 32 consume hundreds of megabytes to over a gigabyte on disk depending on backend. The README presents that as the price of fast proof retrieval rather than hiding it. For workloads where proofs are fetched far more often than leaves are added, it may be a fair trade.

The crate is early — version 0.1.0, MIT licensed, with several TODO comments in the source about overflow protection at very large depths and concurrency support. It targets exactly one job well: fast retrieval of constant-size Merkle proofs from an append-only tree.