Struct MerkleTree

Source

pub struct MerkleTree { /* private fields */ }

Expand description

A Merkle tree with MiMC hash function.

This implementation is optimized for ZK-circuit compatibility and includes features like root history for handling concurrent on-chain insertions.

§Example

use stealth_lib::MerkleTree;

// Create a new tree with 20 levels
let mut tree = MerkleTree::new(20).unwrap();

// Insert leaves
let index = tree.insert(12345).unwrap();
assert_eq!(index, 0);

// Get the current root
let root = tree.root().unwrap();
println!("Root: {}", root);

§Capacity

A tree with n levels can hold 2^n leaves. The maximum supported depth is 255 levels, though practical trees typically use 20-32 levels.

Implementations§

Source §

impl MerkleTree

Source

pub fn new(levels: u8) -> Result<Self>

Creates a new empty Merkle tree with the specified number of levels.

§Arguments

levels - The depth of the tree. The tree can hold 2^levels leaves.

§Returns

A new MerkleTree or an error if the configuration is invalid.

§Errors

Returns Error::InvalidTreeConfig if levels is 0 or greater than 32.

§Example

use stealth_lib::MerkleTree;

let tree = MerkleTree::new(20).unwrap();
assert_eq!(tree.levels(), 20);
assert_eq!(tree.capacity(), 1 << 20);

Source

pub fn with_hasher(levels: u8, hasher: MimcHasher) -> Result<Self>

Creates a new Merkle tree with a custom hasher.

§Arguments

levels - The depth of the tree
hasher - Custom MiMC hasher configuration

§Example

use stealth_lib::{MerkleTree, hash::MimcHasher};

let hasher = MimcHasher::default();
let tree = MerkleTree::with_hasher(20, hasher).unwrap();

Source

pub fn levels(&self) -> u8

Returns the number of levels in the tree.

Source

pub fn capacity(&self) -> usize

Returns the maximum capacity of the tree.

This is 2^levels.

Source

pub fn len(&self) -> u32

Returns the current number of leaves in the tree.

Source

pub fn is_empty(&self) -> bool

Returns true if the tree is empty.

Source

pub fn hasher(&self) -> &MimcHasher

Returns a reference to the hasher used by this tree.

Source

pub fn root(&self) -> Option<u128>

Returns the current root hash of the tree.

Returns None only if the tree is in an invalid state (should not happen under normal usage).

§Example

use stealth_lib::MerkleTree;

let tree = MerkleTree::new(20).unwrap();
let root = tree.root().unwrap();
println!("Empty tree root: {}", root);

Source

pub fn insert(&mut self, leaf: u128) -> Result<u32>

Inserts a new leaf into the tree.

§Arguments

leaf - The leaf value to insert

§Returns

The index of the inserted leaf, or an error if the tree is full.

§Errors

Returns Error::TreeFull if the tree has reached its maximum capacity.

§Example

use stealth_lib::MerkleTree;

let mut tree = MerkleTree::new(20).unwrap();
let index = tree.insert(12345).unwrap();
assert_eq!(index, 0);

let index = tree.insert(67890).unwrap();
assert_eq!(index, 1);

Source

pub fn is_known_root(&self, root: u128) -> bool

Checks if a root hash is in the recent root history.

The tree maintains a circular buffer of recent roots to handle concurrent insertions in on-chain applications.

§Arguments

root - The root hash to check

§Returns

true if the root is in the history, false otherwise.

§Example

use stealth_lib::MerkleTree;

let mut tree = MerkleTree::new(20).unwrap();
let root_before = tree.root().unwrap();
tree.insert(12345).unwrap();
let root_after = tree.root().unwrap();

// Both roots are in history
assert!(tree.is_known_root(root_before));
assert!(tree.is_known_root(root_after));

// Random value is not
assert!(!tree.is_known_root(99999));

Source

pub fn get_last_root(&self) -> u128

👎Deprecated since 1.0.0: Use root() instead

Returns the last (current) root hash.

§Panics

Panics if the tree is in an invalid state (should not happen under normal usage). Prefer using root for fallible access.

Source

pub fn zeros(&self, level: u8) -> u128

Computes the zero hash at a given level.

Zero hashes represent empty subtrees at each level. This uses the same formula as the original Tornado Cash implementation: zeros(0) = 0, zeros(i) = mimc_sponge(zeros(i-1), 0, p).

Note: This is NOT the same as hash_left_right(zeros(i-1), zeros(i-1)). The formula is chosen for compatibility with existing ZK circuits.

Source

pub fn prove(&self, leaf_index: u32) -> Result<MerkleProof>

Generates a Merkle proof for the leaf at the given index.

§Arguments

leaf_index - The index of the leaf to prove

§Returns

A MerkleProof that can be used to verify inclusion.

§Errors

Returns Error::LeafIndexOutOfBounds if the index is invalid.

§Example

use stealth_lib::MerkleTree;

let mut tree = MerkleTree::new(20).unwrap();
tree.insert(12345).unwrap();
tree.insert(67890).unwrap();

let proof = tree.prove(0).unwrap();
let root = tree.root().unwrap();
assert!(proof.verify(root, &tree.hasher()));