Struct LargeSmt 

pub struct LargeSmt<S>
where
    S: SmtStorage,
{ /* private fields */ }

A large-scale Sparse Merkle tree mapping 256-bit keys to 256-bit values, backed by pluggable storage. Both keys and values are represented by 4 field elements.

Unlike the regular Smt, this implementation is designed for very large trees by using external storage (such as RocksDB) for the bulk of the tree data, while keeping only the upper levels (up to depth 24) in memory. This hybrid approach allows the tree to scale beyond memory limitations while maintaining good performance for common operations.

All leaves sit at depth 64. The most significant element of the key is used to identify the leaf to which the key maps.

A leaf is either empty, or holds one or more key-value pairs. An empty leaf hashes to the empty word. Otherwise, a leaf hashes to the hash of its key-value pairs, ordered by key first, value second.

The tree structure:

• Depths 0-23: Stored in memory as a flat array for fast access
• Depths 24-64: Stored in external storage organized as subtrees for efficient batch operations

Implementations

impl<S> LargeSmt<S>

where S: SmtStorage,

pub const EMPTY_VALUE: Word

The default value used to compute the hash of empty leaves.

pub const SUBTREE_DEPTHS: [u8; 5]

Subtree depths for the subtrees stored in storage.

pub fn new(storage: S) -> Result<LargeSmt<S>, LargeSmtError>

Returns a new LargeSmt backed by the provided storage.

The SMT’s root is fetched from the storage backend. If the storage is empty the SMT is initialized with the root of an empty tree. Otherwise, materializes in-memory nodes from the top subtrees.

Errors

Returns an error if fetching the root or initial in-memory nodes from the storage fails.

pub fn with_entries( storage: S, entries: impl IntoIterator<Item = (Word, Word)>, ) -> Result<LargeSmt<S>, LargeSmtError>

Returns a new Smt instantiated with leaves set as specified by the provided entries.

If the concurrent feature is enabled, this function uses a parallel implementation to process the entries efficiently, otherwise it defaults to the sequential implementation.

All leaves omitted from the entries list are set to Self::EMPTY_VALUE.

Errors

Returns an error if the provided entries contain multiple values for the same key.

pub const fn depth(&self) -> u8

Returns the depth of the tree

pub fn root(&self) -> Result<Word, LargeSmtError>

Returns the root of the tree

pub fn num_leaves(&self) -> Result<usize, LargeSmtError>

Returns the number of non-empty leaves in this tree.

Note that this may return a different value from Self::num_entries() as a single leaf may contain more than one key-value pair.

Errors

Returns an error if there is a storage error when retrieving the leaf count.

pub fn num_entries(&self) -> Result<usize, LargeSmtError>

Returns the number of key-value pairs with non-default values in this tree.

Note that this may return a different value from Self::num_leaves() as a single leaf may contain more than one key-value pair.

Also note that this is currently an expensive operation is counting the number of entries requires iterating over all leaves of the tree.

Errors

Returns an error if there is a storage error when retrieving the entry count.

pub fn get_leaf(&self, key: &Word) -> SmtLeaf

Returns the leaf to which key maps

pub fn get_value(&self, key: &Word) -> Word

Returns the value associated with key

pub fn open(&self, key: &Word) -> SmtProof

Returns an opening of the leaf associated with key. Conceptually, an opening is a Merkle path to the leaf, as well as the leaf itself.

pub fn is_empty(&self) -> Result<bool, LargeSmtError>

Returns a boolean value indicating whether the SMT is empty.

Errors

Returns an error if there is a storage error when retrieving the root or leaf count.

pub fn leaves( &self, ) -> Result<impl Iterator<Item = (LeafIndex<miden_crypto::::merkle::smt::large::{impl#0}::leaves::{constant#0}>, SmtLeaf)>, LargeSmtError>

Returns an iterator over the leaves of this Smt. Note: This iterator returns owned SmtLeaf values.

Errors

Returns an error if the storage backend fails to create the iterator.

pub fn entries( &self, ) -> Result<impl Iterator<Item = (Word, Word)>, LargeSmtError>

Returns an iterator over the key-value pairs of this Smt. Note: This iterator returns owned (Word, Word) tuples.

Errors

Returns an error if the storage backend fails to create the iterator.

pub fn inner_nodes( &self, ) -> Result<impl Iterator<Item = InnerNodeInfo>, LargeSmtError>

Returns an iterator over the inner nodes of this Smt.

Errors

Returns an error if the storage backend fails during iteration setup.

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

Inserts a value at the specified key, returning the previous value associated with that key. Recall that by definition, any key that hasn’t been updated is associated with Self::EMPTY_VALUE.

This also recomputes all hashes between the leaf (associated with the key) and the root, updating the root itself.

Errors

Returns an error if inserting the key-value pair would exceed MAX_LEAF_ENTRIES (1024 entries) in the leaf.

pub fn compute_mutations( &self, kv_pairs: impl IntoIterator<Item = (Word, Word)>, ) -> Result<MutationSet<miden_crypto::::merkle::smt::large::{impl#0}::compute_mutations::{constant#0}, Word, Word>, LargeSmtError>

where LargeSmt<S>: Sized + Sync,

Computes what changes are necessary to insert the specified key-value pairs into this Merkle tree, allowing for validation before applying those changes.

This method returns a MutationSet, which contains all the information for inserting kv_pairs into this Merkle tree already calculated, including the new root hash, which can be queried with MutationSet::root(). Once a mutation set is returned, Smt::apply_mutations() can be called in order to commit these changes to the Merkle tree, or drop() to discard them.

Example

let mut smt = Smt::new();
let pair = (Word::default(), Word::default());
let mutations = smt.compute_mutations(vec![pair]).expect("compute_mutations ok");
assert_eq!(mutations.root(), *EmptySubtreeRoots::entry(SMT_DEPTH, 0));
smt.apply_mutations(mutations);
assert_eq!(smt.root(), *EmptySubtreeRoots::entry(SMT_DEPTH, 0));

pub fn apply_mutations( &mut self, mutations: MutationSet<miden_crypto::::merkle::smt::large::{impl#0}::apply_mutations::{constant#0}, Word, Word>, ) -> Result<(), LargeSmtError>

Applies the prospective mutations computed with Smt::compute_mutations() to this tree.

Errors

If mutations was computed on a tree with a different root than this one, returns MerkleError::ConflictingRoots with a two-item Vec. The first item is the root hash the mutations were computed against, and the second item is the actual current root of this tree.

pub fn apply_mutations_with_reversion( &mut self, mutations: MutationSet<miden_crypto::::merkle::smt::large::{impl#0}::apply_mutations_with_reversion::{constant#0}, Word, Word>, ) -> Result<MutationSet<miden_crypto::::merkle::smt::large::{impl#0}::apply_mutations_with_reversion::{constant#1}, Word, Word>, LargeSmtError>

where LargeSmt<S>: Sized,

Applies the prospective mutations computed with Smt::compute_mutations() to this tree and returns the reverse mutation set.

Applying the reverse mutation sets to the updated tree will revert the changes.

Errors

If mutations was computed on a tree with a different root than this one, returns MerkleError::ConflictingRoots with a two-item Vec. The first item is the root hash the mutations were computed against, and the second item is the actual current root of this tree.

Trait Implementations

impl<Backend> AccountTreeBackend for LargeSmt<Backend>

where Backend: SmtStorage,

Available on crate feature std only.

type Error = MerkleError

fn num_leaves(&self) -> usize

Returns the number of leaves in the SMT.

fn leaves<'a>( &'a self, ) -> Box<dyn Iterator<Item = (LeafIndex<SMT_DEPTH>, SmtLeaf)> + 'a>

Returns all leaves in the SMT as an iterator over leaf index and leaf pairs.

fn open(&self, key: &Word) -> SmtProof

Opens the leaf at the given key, returning a Merkle proof.

fn apply_mutations( &mut self, set: MutationSet<SMT_DEPTH, Word, Word>, ) -> Result<(), Self::Error>

Applies the given mutation set to the SMT.

fn apply_mutations_with_reversion( &mut self, set: MutationSet<SMT_DEPTH, Word, Word>, ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error>

Applies the given mutation set to the SMT and returns the reverse mutation set.

fn compute_mutations( &self, updates: Vec<(Word, Word)>, ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error>

Computes the mutation set required to apply the given updates to the SMT.

fn insert(&mut self, key: Word, value: Word) -> Result<Word, Self::Error>

Inserts a key-value pair into the SMT, returning the previous value at that key.

fn get_value(&self, key: &Word) -> Word

Returns the value associated with the given key.

fn get_leaf(&self, key: &Word) -> SmtLeaf

Returns the leaf at the given key.

fn root(&self) -> Word

Returns the root of the SMT.

impl<S> Debug for LargeSmt<S>

where S: Debug + SmtStorage,

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl<S> PartialEq for LargeSmt<S>

where S: SmtStorage,

fn eq(&self, other: &LargeSmt<S>) -> bool

Compares two LargeSmt instances based on their root hash and metadata.

Note: This comparison only checks the root hash and counts, not the underlying storage contents. Two SMTs with the same root should be cryptographically equivalent, but this doesn’t verify the storage backends are identical.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<S> Eq for LargeSmt<S>

where S: SmtStorage,