Type Definition
pub struct LeanIMT<H: Hasher, const N: usize, const MAX_DEPTH: usize>
Generic Parameters
Hash function implementing the Hasher trait
Branching factor (compile-time constant, must be ≥ 2)
Maximum tree depth (compile-time constant, must be ≥ 1)
The branching factor N determines how many children each internal node can have. Common values are:
N=2 for binary treesN=3 for ternary treesN=4 for quaternary trees
Constructor
new
pub fn new(hasher: H) -> Self
The hash function to use for computing internal nodes
A new empty tree instance
use rotortree::{LeanIMT, Blake3Hasher};
let tree = LeanIMT::<Blake3Hasher, 2, 32>::new(Blake3Hasher);
Methods
insert
// Without concurrent feature
pub fn insert(&mut self, leaf: Hash) -> Result<Hash, TreeError>
// With concurrent feature
pub fn insert(&self, leaf: Hash) -> Result<Hash, TreeError>
The 32-byte hash to insert as a leaf
The new Merkle root after insertion, or an error if the operation fails
TreeError::MaxDepthExceeded if inserting would exceed MAX_DEPTHTreeError::CapacityExceeded if the tree size would overflow u64
use rotortree::{LeanIMT, Blake3Hasher};
let mut tree = LeanIMT::<Blake3Hasher, 2, 32>::new(Blake3Hasher);
let leaf = [0u8; 32];
let root = tree.insert(leaf)?;
println!("New root: {:?}", root);
insert_many
// Without concurrent feature
pub fn insert_many(&mut self, leaves: &[Hash]) -> Result<Hash, TreeError>
// With concurrent feature
pub fn insert_many(&self, leaves: &[Hash]) -> Result<Hash, TreeError>
insert repeatedly.
Slice of 32-byte hashes to insert
The new Merkle root after batch insertion
TreeError::EmptyBatch if the slice is emptyTreeError::MaxDepthExceeded if the batch would exceed MAX_DEPTHTreeError::CapacityExceeded if the tree size would overflow
let mut tree = LeanIMT::<Blake3Hasher, 2, 32>::new(Blake3Hasher);
let leaves = vec![[1u8; 32], [2u8; 32], [3u8; 32]];
let root = tree.insert_many(&leaves)?;
With the parallel feature enabled, insert_many automatically parallelizes hash computation using Rayon when the batch size exceeds the configured threshold.
root
pub fn root(&self) -> Option<Hash>
None if the tree is empty.
The 32-byte root hash, or None for an empty tree
let root = tree.root();
if let Some(hash) = root {
println!("Root: {:?}", hash);
} else {
println!("Tree is empty");
}
size
pub fn size(&self) -> u64
let count = tree.size();
println!("Tree has {} leaves", count);
depth
pub fn depth(&self) -> usize
The tree depth (0 for a single-leaf or empty tree)
let d = tree.depth();
println!("Tree depth: {}", d);
For an N-ary tree with size leaves, the depth is approximately log_N(size). A single leaf has depth 0.
snapshot
pub fn snapshot(&self) -> TreeSnapshot<N, MAX_DEPTH>
return
TreeSnapshot<N, MAX_DEPTH>
An immutable snapshot that shares structure with the tree via Arc
let snapshot = tree.snapshot();
// The snapshot remains valid even if the tree is modified
tree.insert([99u8; 32])?;
// Snapshot still represents the old state
let proof = snapshot.generate_proof(0)?;
Snapshots use structural sharing via Arc, making them very cheap to create. Multiple snapshots can coexist with minimal memory overhead.
Concurrency
With the concurrent feature enabled:
LeanIMT wraps internal state in parking_lot::RwLock- All methods take
&self instead of &mut self
- Multiple threads can safely insert concurrently
- Readers can take lock-free snapshots
use std::sync::Arc;
use std::thread;
let tree = Arc::new(LeanIMT::<Blake3Hasher, 2, 32>::new(Blake3Hasher));
let handles: Vec<_> = (0..4)
.map(|i| {
let tree = Arc::clone(&tree);
thread::spawn(move || {
tree.insert([i as u8; 32]).unwrap();
})
})
.collect();
for h in handles {
h.join().unwrap();
}
println!("Final size: {}", tree.size());
Memory Layout
The tree uses a chunked storage format with structural sharing:
- Leaf level and internal levels stored in 128-hash chunks
- Chunks grouped into 256-chunk segments
- Segments frozen into immutable
Arc on completion
- Snapshots share immutable segments with zero-copy
See Architecture for details.