Skip to main content
This guide walks you through creating your first n-ary lean incremental Merkle tree, inserting leaves, and generating proofs.

​
Basic In-Memory Tree

1

Import dependencies

use rotortree::{LeanIMT, Blake3Hasher, TreeHasher};
2

Create a tree

Create a tree with N=4 branching factor and MAX_DEPTH=20:
let mut tree = LeanIMT::<Blake3Hasher, 4, 20>::new(Blake3Hasher);
The branching factor (N) and maximum depth are compile-time constants. Choose values that match your capacity needs.
3

Insert a single leaf

let leaf = [1u8; 32];
let root = tree.insert(leaf).unwrap();
println!("Root after insert: {:?}", root);
4

Insert multiple leaves

For batch insertions, use insert_many:
let leaves: Vec<[u8; 32]> = (0..1000u32)
    .map(|i| {
        let mut h = [0u8; 32];
        h[..4].copy_from_slice(&i.to_le_bytes());
        h
    })
    .collect();
let root = tree.insert_many(&leaves).unwrap();
insert_many is significantly faster than individual inserts, especially with the parallel feature enabled.
5

Generate and verify a proof

// Take a snapshot for proof generation
let snap = tree.snapshot();

// Generate proof for leaf at index 0
let proof = snap.generate_proof(0).unwrap();

// Verify the proof
let th = TreeHasher::new(Blake3Hasher);
assert!(proof.verify(&th).unwrap());
println!("Proof verified successfully!");

​
Complete Example

Here’s a complete working example: 
use rotortree::{LeanIMT, Blake3Hasher, TreeHasher};

fn main() {
    // Create tree with N=4, MAX_DEPTH=20
    let mut tree = LeanIMT::<Blake3Hasher, 4, 20>::new(Blake3Hasher);
    
    // Insert a single leaf
    let leaf = [1u8; 32];
    let root = tree.insert(leaf).unwrap();
    
    // Batch insert 1000 leaves
    let leaves: Vec<[u8; 32]> = (0..1000u32)
        .map(|i| {
            let mut h = [0u8; 32];
            h[..4].copy_from_slice(&i.to_le_bytes());
            h
        })
        .collect();
    let root = tree.insert_many(&leaves).unwrap();
    
    // Generate and verify proof
    let snap = tree.snapshot();
    let proof = snap.generate_proof(0).unwrap();
    let th = TreeHasher::new(Blake3Hasher);
    assert!(proof.verify(&th).unwrap());
    
    println!("All operations completed successfully!");
}

​
Tree with Persistence

For production applications, enable WAL-backed persistence:
1

Enable the storage feature

Cargo.toml
[dependencies]
rotortree = { version = "0.15.0", features = ["storage"] }
2

Configure and open the tree

use rotortree::{
    Blake3Hasher, RotorTree, RotorTreeConfig, TreeHasher,
    FlushPolicy, CheckpointPolicy, TieringConfig,
};
use std::path::PathBuf;

let config = RotorTreeConfig {
    path: PathBuf::from("/tmp/my-tree"),
    flush_policy: FlushPolicy::default(), // fsync every 10ms
    checkpoint_policy: CheckpointPolicy::default(), // manual
    tiering: TieringConfig::default(), // all in memory
    verify_checkpoint: true, // recompute root on recovery
};

// Opens existing WAL or creates a new one
let tree = RotorTree::<Blake3Hasher, 4, 20>::open(Blake3Hasher, config).unwrap();
3

Insert with durability

// Insert and get a durability token
let (root, token) = tree.insert([42u8; 32]).unwrap();
token.wait(); // Blocks until the entry is fsynced

// Or insert + wait for fsync in one call
let root = tree.insert_durable([43u8; 32]).unwrap();
4

Generate proofs (same as in-memory)

// Lock-free snapshot
let snap = tree.snapshot();
let proof = snap.generate_proof(0).unwrap();
let th = TreeHasher::new(Blake3Hasher);
assert!(proof.verify(&th).unwrap());
5

Graceful shutdown

tree.flush().unwrap();
tree.close().unwrap();
// (also flushes + releases file lock on drop)

​
Configuration Options

​
Flush Policies

FlushPolicy::Interval(Duration::from_millis(10))

​
Checkpoint Policies

Checkpointing materializes WAL state to data files and allows WAL truncation: 
CheckpointPolicy::Manual
// Caller calls checkpoint() explicitly

​
Tiering Configuration

Control which tree levels stay in memory vs get memory-mapped: 
// Keep everything in memory (best performance)
TieringConfig { pin_above_level: 0 }

// Memory-map everything after checkpoint (minimal memory)
TieringConfig { pin_above_level: usize::MAX } // default

// Memory-map levels below 5
TieringConfig { pin_above_level: 5 }

​
Advanced: Light Client Consistency Proofs

RotorTree supports efficient consistency proofs for light clients. Here’s how a light client can track an inclusion proof without transferring all leaves: 
use rotortree::{LeanIMT, Blake3Hasher, TreeHasher, ConsistencyProof};

// Bootstrap: receive initial leaves from full node
let mut tree = LeanIMT::<Blake3Hasher, 4, 14>::new(Blake3Hasher);
tree.insert_many(&initial_leaves).unwrap();
let snap = tree.snapshot();
let mut tracked_proof = snap.generate_proof(tracked_leaf_index).unwrap();

// Later: receive consistency proof for new batch
let old_size = snap.size();
let old_root = snap.root().unwrap();

// ... (full node inserts more leaves and generates consistency proof)

// Verify the tree transition
let th = TreeHasher::new(Blake3Hasher);
assert!(consistency_proof.verify_transition(&th, old_root).unwrap());

// Update the tracked inclusion proof WITHOUT receiving new leaves
let updated_proof = consistency_proof
    .update_inclusion_proof(&tracked_proof, &th)
    .unwrap();

assert!(updated_proof.verify(&th).unwrap());
tracked_proof = updated_proof;
For a complete working example, see examples/light_client.rs in the repository.

​
Performance Tips

Use parallel for large batches

Enable the parallel feature and use insert_many for batches of 1000+ leaves.

Tune branching factor

Higher N reduces depth but increases node size. N=4 or N=8 works well for most cases.

Manual flush for blockchain

Use FlushPolicy::Manual and flush after each block to align with your consensus layer.

Memory-map for large trees

Use TieringConfig::pin_above_level to tier cold levels to disk when trees exceed available RAM.

​
Important Design Considerations

RotorTree is a research experiment and makes many tradeoffs. It is not suitable for production as-is.

Nullifier Deduplication

Use a separate key-value database to ensure you don’t insert the same nullifier twice. RotorTree is append-only.

Field Constraints

Constrain node values to your finite field before insertion if using in zero-knowledge circuits.

Prehashed Leaves

RotorTree assumes leaves are already hashed. It provides partial RFC 6962 support for internal nodes only.

​
Next Steps

API Reference

Explore the complete API documentation

Configuration

Learn about tuning parameters and environment variables

Examples

View complete example applications

Benchmarks

Review performance benchmarks (~380 benchmarks)

Build docs developers (and LLMs) love

Get started for freeTalk to us