Struct Smt

pub struct Smt { /* private fields */ }

Sparse Merkle tree mapping 256-bit keys to 256-bit values. Both keys and values are represented by 4 field elements.

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.

Implementations

impl Smt

pub const EMPTY_VALUE: [BaseElement; 4]

The default value used to compute the hash of empty leaves

pub fn new() -> Smt

Returns a new Smt.

All leaves in the returned tree are set to Self::EMPTY_VALUE.

pub fn with_entries( entries: impl IntoIterator<Item = (RpoDigest, [BaseElement; 4])>, ) -> Result<Smt, MerkleError>

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 fn from_raw_parts( inner_nodes: BTreeMap<NodeIndex, InnerNode>, leaves: BTreeMap<u64, SmtLeaf>, root: RpoDigest, ) -> Smt

Returns a new Smt instantiated from already computed leaves and nodes.

This function performs minimal consistency checking. It is the caller’s responsibility to ensure the passed arguments are correct and consistent with each other.

Panics

With debug assertions on, this function panics if root does not match the root node in inner_nodes.

pub const fn depth(&self) -> u8

Returns the depth of the tree

pub fn root(&self) -> RpoDigest

Returns the root of the tree

pub fn num_leaves(&self) -> usize

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.

pub fn num_entries(&self) -> usize

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 as counting the number of entries requires iterating over all leaves of the tree.

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

Returns the leaf to which key maps

pub fn get_value(&self, key: &RpoDigest) -> [BaseElement; 4]

Returns the value associated with key

pub fn open(&self, key: &RpoDigest) -> 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) -> bool

Returns a boolean value indicating whether the SMT is empty.

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

Returns an iterator over the leaves of this Smt in arbitrary order.

pub fn entries(&self) -> impl Iterator<Item = &(RpoDigest, [BaseElement; 4])>

Returns an iterator over the key-value pairs of this Smt in arbitrary order.

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

Returns an iterator over the inner nodes of this Smt.

pub fn insert( &mut self, key: RpoDigest, value: [BaseElement; 4], ) -> [BaseElement; 4]

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.

pub fn compute_mutations( &self, kv_pairs: impl IntoIterator<Item = (RpoDigest, [BaseElement; 4])>, ) -> MutationSet<miden_crypto::::merkle::smt::full::{impl#0}::compute_mutations::{constant#1}, RpoDigest, [BaseElement; 4]>

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 = (RpoDigest::default(), Word::default());
let mutations = smt.compute_mutations(vec![pair]);
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::full::{impl#0}::apply_mutations::{constant#1}, RpoDigest, [BaseElement; 4]>, ) -> Result<(), MerkleError>

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::full::{impl#0}::apply_mutations_with_reversion::{constant#1}, RpoDigest, [BaseElement; 4]>, ) -> Result<MutationSet<miden_crypto::::merkle::smt::full::{impl#0}::apply_mutations_with_reversion::{constant#2}, RpoDigest, [BaseElement; 4]>, MerkleError>

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 Clone for Smt

fn clone(&self) -> Smt

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Smt

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

Formats the value using the given formatter.

impl Default for Smt

fn default() -> Smt

Returns the “default value” for a type.

impl Deserializable for Smt

fn read_from<R>(source: &mut R) -> Result<Smt, DeserializationError>

where R: ByteReader,

Reads a sequence of bytes from the provided source, attempts to deserialize these bytes into Self, and returns the result.

fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError>

Attempts to deserialize the provided bytes into Self and returns the result.

impl<T> From<&Smt> for MerkleStore<T>

where T: KvMap<RpoDigest, StoreNode>,

fn from(value: &Smt) -> MerkleStore<T>

Converts to this type from the input type.

impl PartialEq for Smt

fn eq(&self, other: &Smt) -> 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 Serializable for Smt

fn write_into<W>(&self, target: &mut W)

where W: ByteWriter,

Serializes self into bytes and writes these bytes into the target.

fn get_size_hint(&self) -> usize

Returns an estimate of how many bytes are needed to represent self.

fn to_bytes(&self) -> Vec<u8>

Serializes self into a vector of bytes.

impl Eq for Smt

impl StructuralPartialEq for Smt