Struct SmtForest 

pub struct SmtForest { /* private fields */ }

An in-memory data collection of sparse Merkle trees (SMTs).

Each SMT in the forest is identified by its root hash. The forest stores all leaves of all SMTs in the forest, as well as all Merkle paths required to prove membership of any leaf in any SMT.

An empty tree root is always present in the forest.

Example usage:

use miden_crypto::{
    Felt, ONE, WORD_SIZE, Word, ZERO,
    merkle::{EmptySubtreeRoots, MAX_LEAF_ENTRIES, SMT_DEPTH, SmtForest},
};

// Create a new SMT forest
let mut forest = SmtForest::new();

// Insert a key-value pair into an SMT with an empty root
let empty_tree_root = *EmptySubtreeRoots::entry(SMT_DEPTH, 0);
let key = Word::new([ZERO; WORD_SIZE]);
let value = Word::new([ONE; WORD_SIZE]);
let new_root = forest.insert(empty_tree_root, key, value).unwrap();

// Insert multiple key-value pairs
let mut entries = Vec::new();
for i in 0..MAX_LEAF_ENTRIES {
    let key = Word::new([Felt::new(i as u64); WORD_SIZE]);
    let value = Word::new([Felt::new((i + 1) as u64); WORD_SIZE]);
    entries.push((key, value));
}
let new_root = forest.batch_insert(new_root, entries.into_iter()).unwrap();

// Open a proof for the inserted key
let proof = forest.open(new_root, key).unwrap();

// Prune SMTs to release memory used by their nodes and leaves
forest.pop_smts(vec![new_root]);

Implementations

impl SmtForest

pub fn new() -> SmtForest

Creates an empty SmtForest instance.

pub fn open(&self, root: Word, key: Word) -> Result<SmtProof, MerkleError>

Returns an opening for the specified key in the SMT with the specified root.

Returns an error if an SMT with this root is not in the forest, or if the forest does not have sufficient data to provide an opening for the specified key.

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

Inserts the specified key-value pair into an SMT with the specified root. This will also add a new root to the forest. Returns the new root.

Returns an error if an SMT with the specified root is not in the forest, these is not enough data in the forest to perform the insert, or if the insert would create a leaf with too many entries.

pub fn batch_insert( &mut self, root: Word, entries: impl IntoIterator<Item = (Word, Word)> + Clone, ) -> Result<Word, MerkleError>

Inserts the specified key-value pairs into an SMT with the specified root. This will also add a single new root to the forest for the entire batch of inserts. Returns the new root.

Returns an error if an SMT with the specified root is not in the forest, these is not enough data in the forest to perform the insert, or if the insert would create a leaf with too many entries.

pub fn pop_smts(&mut self, roots: impl IntoIterator<Item = Word>)

Removes the specified SMTs (identified by their roots) from the forest. Releases memory used by nodes and leaves that are no longer reachable. Roots not in the forest and empty trees are ignored.

Trait Implementations

impl Clone for SmtForest

fn clone(&self) -> SmtForest

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SmtForest

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

Formats the value using the given formatter.

impl Default for SmtForest

fn default() -> SmtForest

Returns the “default value” for a type.

impl PartialEq for SmtForest

fn eq(&self, other: &SmtForest) -> bool

Tests for self and other values to be equal, and is used by ==.

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 Eq for SmtForest

impl StructuralPartialEq for SmtForest