Struct miden_objects::crypto::merkle::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.

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) -> RpoDigest

Returns the root 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 leaves( &self ) -> impl Iterator<Item = (LeafIndex<miden_crypto::::merkle::smt::full::{impl#0}::leaves::{opaque#0}::{constant#0}>, &SmtLeaf)>

Returns an iterator over the leaves of this Smt.

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

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

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.

Trait Implementations

impl Clone for Smt

fn clone(&self) -> Smt

Returns a copy 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<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

This method tests for self and other values to be equal, and is used by ==.

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

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

impl Eq for Smt

impl StructuralPartialEq for Smt