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.

depth
T  0                  Root
│  .                  /  \
│  1              left   right
│  .             /  \    /  \
│
│          .. .. .. .. .. .. .. ..
│
│  63
│           /  \        /   \           \
│  ￬       /    \      /     \           \
│  64   Leaf₀  Leaf₁  Leaf₂  Leaf₃  ...  Leaf₂⁶⁴₋₂³²
       0x0..0 0x0..1 0x0..2 0x0..3      0xFFFFFFFF00000000

The digest is 256 bits, or 4 field elements:
[elem₀, elem₁, elem₂, elem₃]
                        ↑
        Most significant element determines leaf
        index, mapping into the actual Leaf lookup
        table where the values are stored.

Zooming into a leaf, i.e. Leaf₁:
┌─────────────────────────────────────────────────┐
│            Leaf₁ (index: 0x0..1)                │
├─────────────────────────────────────────────────┤
│ Possible states:                                │
│                                                 │
│ 1. Empty leaf:                                  │
│    └─ hash = EMPTY_WORD                         │
│                                                 │
│ 2. Single entry:                                │
│    └─ (key₁, value₁)                            │
│    └─ hash = H(key₁, value₁)                    │
│                                                 │
│ 3. Multiple entries:                            │
│    └─ (key₁, value₁)                            │
│    └─ (key₂, value₂)                            │
│    └─ ...                                       │
│    └─ hash = H(key₁, value₁, key₂, value₂, ...) │
└─────────────────────────────────────────────────┘

Leaf states:
- Empty: hashes to EMPTY_WORD
- Non-empty: contains (key, value) pairs
             hash = H(key₁, value₁, key₂, value₂, ...)

Implementations

impl Smt

pub const EMPTY_VALUE: Word

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 = (Word, Word)>, ) -> 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.
• inserting a key-value pair would exceed MAX_LEAF_ENTRIES (1024 entries) in a leaf.

pub fn with_sorted_entries( entries: impl IntoIterator<Item = (Word, Word)>, ) -> Result<Smt, MerkleError>

Similar to with_entries but avoids the overhead of sorting if the entries are already sorted.

This only applies if the “concurrent” feature is enabled. Without the feature, the behavior is equivalent to with_entiries.

Errors

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

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

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.

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

Returns the leaf to which key maps

pub fn get_leaf_by_index( &self, index: LeafIndex<miden_crypto::::merkle::smt::full::{impl#0}::get_leaf_by_index::{constant#0}>, ) -> Option<SmtLeaf>

Returns the leaf corresponding to the provided index.

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) -> 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 = &(Word, Word)>

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 inner_node_indices(&self) -> impl Iterator<Item = (NodeIndex, InnerNode)>

Returns an iterator over the [InnerNode] and the respective NodeIndex of the Smt.

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::full::{impl#0}::compute_mutations::{constant#0}, Word, Word>, MerkleError>

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]).unwrap();
assert_eq!(mutations.root(), *EmptySubtreeRoots::entry(SMT_DEPTH, 0));
smt.apply_mutations(mutations).unwrap();
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}, Word, Word>, ) -> 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}, Word, Word>, ) -> Result<MutationSet<miden_crypto::::merkle::smt::full::{impl#0}::apply_mutations_with_reversion::{constant#2}, Word, Word>, 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 AccountTreeBackend for Smt

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<miden_protocol::::block::account_tree::backend::{impl#0}::leaves::{constant#0}>, 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<miden_protocol::::block::account_tree::backend::{impl#0}::apply_mutations::{constant#0}, Word, Word>, ) -> Result<(), <Smt as AccountTreeBackend>::Error>

Applies the given mutation set to the SMT.

fn apply_mutations_with_reversion( &mut self, set: MutationSet<miden_protocol::::block::account_tree::backend::{impl#0}::apply_mutations_with_reversion::{constant#0}, Word, Word>, ) -> Result<MutationSet<miden_protocol::::block::account_tree::backend::{impl#0}::apply_mutations_with_reversion::{constant#1}, Word, Word>, <Smt as AccountTreeBackend>::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<miden_protocol::::block::account_tree::backend::{impl#0}::compute_mutations::{constant#0}, Word, Word>, <Smt as AccountTreeBackend>::Error>

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

fn insert( &mut self, key: Word, value: Word, ) -> Result<Word, <Smt as AccountTreeBackend>::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 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 From<&Smt> for MerkleStore

fn from(value: &Smt) -> MerkleStore

Converts to this type from the input type.

impl NullifierTreeBackend for Smt

type Error = MerkleError

fn num_entries(&self) -> usize

Returns the number of entries in the SMT.

fn entries(&self) -> Box<dyn Iterator<Item = (Word, Word)> + '_>

Returns all entries in the SMT as an iterator over key-value 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<miden_protocol::::block::nullifier_tree::backend::{impl#0}::apply_mutations::{constant#0}, Word, Word>, ) -> Result<(), <Smt as NullifierTreeBackend>::Error>

Applies the given mutation set to the SMT.

fn compute_mutations( &self, updates: impl IntoIterator<Item = (Word, Word)>, ) -> Result<MutationSet<miden_protocol::::block::nullifier_tree::backend::{impl#0}::compute_mutations::{constant#0}, Word, Word>, <Smt as NullifierTreeBackend>::Error>

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

fn insert( &mut self, key: Word, value: NullifierBlock, ) -> Result<NullifierBlock, <Smt as NullifierTreeBackend>::Error>

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

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

Returns the value associated with the given key.

fn root(&self) -> Word

Returns the root of the SMT.

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