Sparse Merkle tree

SparseMerkleTree<H> models a fixed-depth 256-bit key space: 2²⁵⁶ leaf slots, almost all empty. It stores only non-empty nodes, precomputes the empty-subtree hash at every level, and compresses single-leaf subtrees into shortcut nodes (Buterin, 2018) and small subtrees into batch entries (Ouvrard, 2018/2019).

Use it for account state, key-value commitments, allowlists, and rollup state, especially when you must prove that a key is absent.

Keys and values

A key is [u8; 32]. If your natural key is longer or variable-length (an address, a user ID), hash it to 32 bytes first.
A value is any non-empty byte slice. The tree stores H::hash(value).

use merkle_core::prelude::*;
use merkle_variants::SparseMerkleTree;
use merkleforge_hash::Sha256;
 
/// Derive a 32-byte tree key from an arbitrary identifier.
fn key_for(id: &str) -> [u8; 32] {
    Sha256::hash(id.as_bytes())
}
 
fn main() -> Result<(), MerkleError> {
    let mut state = SparseMerkleTree::<Sha256>::new();
    assert_eq!(state.root(), None); // root() is None while empty
    assert_eq!(state.depth(), 256);
 
    state.insert(key_for("alice"), b"balance:100")?;
    state.insert(key_for("bob"), b"balance:250")?;
 
    // Inserting an existing key overwrites its value.
    state.insert(key_for("alice"), b"balance:90")?;
    assert_eq!(state.leaf_count(), 2);
 
    // get() returns the stored leaf *hash*, not the value.
    assert_eq!(state.get(key_for("alice")), Some(&Sha256::hash(b"balance:90")));
    assert_eq!(state.get(key_for("carol")), None);
 
    state.remove(key_for("bob"))?;
    assert_eq!(state.leaf_count(), 1);
    Ok(())
}

root() returns None for an empty tree. If you need the canonical root of an empty tree (for example as a genesis state), use empty_root().

Membership proofs

use merkle_variants::SparseMerkleTree;
use merkleforge_hash::Sha256;
 
fn main() -> Result<(), merkle_core::error::MerkleError> {
    let mut state = SparseMerkleTree::<Sha256>::new();
    let alice = [7_u8; 32];
    let bob = [9_u8; 32];
 
    state.insert(alice, b"balance:100")?;
    state.insert(bob, b"balance:250")?;
 
    let proof = state.generate_membership_proof(alice)?;
    let root = state.root().expect("state is not empty");
 
    assert!(proof.is_membership());
    assert_eq!(proof.siblings.len(), 256);
 
    // Checks the key, the value, and the path.
    assert!(SparseMerkleTree::<Sha256>::verify_membership(
        root,
        alice,
        b"balance:100",
        &proof,
    ));
    // The same proof does not verify for another key or value.
    assert!(!SparseMerkleTree::<Sha256>::verify_membership(root, bob, b"balance:100", &proof));
    assert!(!SparseMerkleTree::<Sha256>::verify_membership(root, alice, b"balance:999", &proof));
    Ok(())
}

A SparseMerkleProof<D> has three public fields: key, siblings (256 entries ordered leaf to root, with None for empty subtrees), and leaf (the stored leaf hash, or None).

Non-membership proofs

The same function proves absence. For a missing key, generate_membership_proof returns a proof with leaf: None, and the verifier rebuilds the root with H::empty() in the leaf slot.

use merkle_variants::SparseMerkleTree;
use merkleforge_hash::Sha256;
 
fn main() -> Result<(), merkle_core::error::MerkleError> {
    let mut state = SparseMerkleTree::<Sha256>::new();
    state.insert([1_u8; 32], b"registered")?;
 
    let missing = [2_u8; 32];
    let proof = state.generate_membership_proof(missing)?;
    let root = state.root().expect("non-empty");
 
    assert!(proof.is_non_membership());
    assert!(SparseMerkleTree::<Sha256>::verify_non_membership(root, missing, &proof));
 
    // A non-membership proof can't be replayed for a key that *is* present.
    let present = state.generate_membership_proof([1_u8; 32])?;
    assert!(!SparseMerkleTree::<Sha256>::verify_non_membership(root, [1_u8; 32], &present));
    Ok(())
}

Batch operations

batch_insert and batch_remove apply every change first, then recompute each affected node once (one-phase batch update, Ma et al.). For many updates this is much faster than a loop of single inserts.

use merkle_variants::SparseMerkleTree;
use merkleforge_hash::Sha256;
 
fn main() -> Result<(), merkle_core::error::MerkleError> {
    let mut batched = SparseMerkleTree::<Sha256>::new();
    let mut sequential = SparseMerkleTree::<Sha256>::new();
 
    let updates: Vec<([u8; 32], Vec<u8>)> = (0_u8..100)
        .map(|i| ([i; 32], format!("account:{i}").into_bytes()))
        .collect();
 
    batched.batch_insert(&updates)?;
    for (key, value) in &updates {
        sequential.insert(*key, value)?;
    }
    assert_eq!(batched.root(), sequential.root());
    assert_eq!(batched.leaf_count(), 100);
 
    // Remove several keys in one pass. Every key must exist.
    batched.batch_remove(&[[0_u8; 32], [1_u8; 32], [2_u8; 32]])?;
    assert_eq!(batched.leaf_count(), 97);
    Ok(())
}

Rules:

If a key appears more than once in batch_insert, the last value wins.
batch_insert fails with EmptyLeafData if any value is empty, before changing the tree.
batch_remove fails with UnsupportedOperation if any key is missing, before changing the tree.
Single remove of a missing key also returns UnsupportedOperation.

In the published benchmark run (2026-08-17), a 1,000-key batch insert took 20.33 ms versus 8.69 s for 1,000 sequential inserts. That run predates the v0.5.0 fix that makes single inserts recompute only the changed path, so today's sequential numbers are far lower; batching still saves work on shared ancestors. See Benchmarks.

Empty hashes and storage introspection

use merkle_core::prelude::*;
use merkle_variants::SparseMerkleTree;
use merkleforge_hash::Sha256;
 
fn main() -> Result<(), MerkleError> {
    let mut tree = SparseMerkleTree::<Sha256>::new();
 
    // Level 0 is the empty leaf; level 256 is the empty-tree root.
    assert_eq!(tree.empty_hash_at(0), &Sha256::empty());
    assert_eq!(tree.empty_root(), tree.empty_hash_at(256));
    assert_eq!(tree.empty_hashes().len(), 257);
 
    tree.insert([0xAB; 32], b"value")?;
    println!("materialized nodes: {}", tree.stored_node_count());
    println!("nodes written by last mutation: {}", tree.last_node_access_count());
    println!("estimate without batching: {}", tree.unbatched_node_count_estimate());
    Ok(())
}

The merkle_variants::sparse module also exports the constants SPARSE_TREE_DEPTH (256), EMPTY_HASH_LEVELS (257), and BATCH_DEPTH (4), and the helper bit_at(key, depth) that returns the path bit for a key at a depth (bit 0 is the high bit of key[0]).

Through the generic trait

SparseMerkleTree implements MerkleTree<H> by mapping leaf index i to a key whose last 8 bytes are i (big-endian). MerkleTree::generate_proof returns an ordinary MerkleProof with 256 path nodes. Prefer the key-addressed API above for real state.

Suggest changes to this page