Struct SparseMerkleTree 

pub struct SparseMerkleTree<DB: SMTDatabase> { /* private fields */ }

Sparse Merkle Tree implementation matching circomlibjs/smt.js Provides insert/update/delete/find helpers that operate entirely over BigInts so test harnesses can generate witnesses identical to the JavaScript reference implementation.

Implementations

impl<DB: SMTDatabase> SparseMerkleTree<DB>

pub fn new(db: DB, root: BigInt) -> Self

Create a new Sparse Merkle Tree

Arguments

• db - Database implementation for storing tree nodes
• root - Initial root value (typically BigInt::from(0) for empty tree)

Returns

Returns a new SparseMerkleTree instance.

pub fn root(&self) -> &BigInt

Get the current root of the tree

Returns

Returns a reference to the current root BigInt value.

pub fn update(&mut self, key: &BigInt, new_value: &BigInt) -> Result<SMTResult>

Update a key-value pair in the tree

Recomputes all nodes along the path and persists them in the backing database. This mirrors circomlibjs’ update logic where we first delete the old leaf and then rebuild the path with the new value while tracking every intermediate node for witnesses.

Arguments

• key - Key to update
• new_value - New value to associate with the key

Returns

Returns Ok(SMTResult) containing the old and new roots, siblings, and operation metadata, or an error if the key is not found or database operations fail.

pub fn delete(&mut self, key: &BigInt) -> Result<SMTResult>

Delete a key from the tree

Handles both sparse branches (single child) and mixed branches (two populated children). The logic follows smt.js closely: collapse empty branches while keeping collision nodes.

Arguments

• key - Key to delete from the tree

Returns

Returns Ok(SMTResult) containing the old and new roots, siblings, and operation metadata, or an error if the key does not exist or database operations fail.

pub fn insert(&mut self, key: &BigInt, value: &BigInt) -> Result<SMTResult>

Insert a new key-value pair

Builds any missing intermediate nodes so the resulting tree mirrors the JS SMT.

Arguments

• key - Key to insert
• value - Value to associate with the key

Returns

Returns Ok(SMTResult) containing the old and new roots, siblings, and operation metadata, or an error if the key already exists or database operations fail.

pub fn find(&self, key: &BigInt) -> Result<FindResult>

Find a key in the tree

Returns the Merkle siblings required to reconstruct the path in circuits/tests. Also surfaces whether the path ended in a leaf collision (non-existent key with same path).

Arguments

• key - Key to search for in the tree

Returns

Returns Ok(FindResult) containing whether the key was found, siblings along the path, and collision information, or an error if database operations fail.