Struct miden_objects::crypto::merkle::SimpleSmt

pub struct SimpleSmt<const DEPTH: u8> { /* private fields */ }

A sparse Merkle tree with 64-bit keys and 4-element leaf values, without compaction.

The root of the tree is recomputed on each new leaf update.

Implementations

impl<const DEPTH: u8> SimpleSmt<DEPTH>

pub const EMPTY_VALUE: [BaseElement; 4] = _

The default value used to compute the hash of empty leaves

pub fn new() -> Result<SimpleSmt<DEPTH>, MerkleError>

Returns a new SimpleSmt.

All leaves in the returned tree are set to [ZERO; 4].

Errors

Returns an error if DEPTH is 0 or is greater than 64.

pub fn with_leaves( entries: impl IntoIterator<Item = (u64, [BaseElement; 4])>, ) -> Result<SimpleSmt<DEPTH>, MerkleError>

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

All leaves omitted from the entries list are set to [ZERO; 4].

Errors

Returns an error if:

• If the depth is 0 or is greater than 64.
• The number of entries exceeds the maximum tree capacity, that is 2^{depth}.
• The provided entries contain multiple values for the same key.

pub fn with_contiguous_leaves( entries: impl IntoIterator<Item = [BaseElement; 4]>, ) -> Result<SimpleSmt<DEPTH>, MerkleError>

Wrapper around SimpleSmt::with_leaves which inserts leaves at contiguous indices starting at index 0.

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.

pub fn get_leaf(&self, key: &LeafIndex<DEPTH>) -> [BaseElement; 4]

Returns the leaf at the specified index.

pub fn get_node(&self, index: NodeIndex) -> Result<RpoDigest, MerkleError>

Returns a node at the specified index.

Errors

Returns an error if the specified index has depth set to 0 or the depth is greater than the depth of this Merkle tree.

pub fn open(&self, key: &LeafIndex<DEPTH>) -> ValuePath

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 = (u64, &[BaseElement; 4])>

Returns an iterator over the leaves of this SimpleSmt.

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

Returns an iterator over the inner nodes of this SimpleSmt.

pub fn insert( &mut self, key: LeafIndex<DEPTH>, 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 EMPTY_WORD.

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

pub fn set_subtree<const SUBTREE_DEPTH: u8>( &mut self, subtree_insertion_index: u64, subtree: SimpleSmt<SUBTREE_DEPTH>, ) -> Result<RpoDigest, MerkleError>

Inserts a subtree at the specified index. The depth at which the subtree is inserted is computed as DEPTH - SUBTREE_DEPTH.

Returns the new root.

Trait Implementations

impl<const DEPTH: u8> Clone for SimpleSmt<DEPTH>

fn clone(&self) -> SimpleSmt<DEPTH>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<const DEPTH: u8> Debug for SimpleSmt<DEPTH>

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

Formats the value using the given formatter.

impl<T, const DEPTH: u8> From<&SimpleSmt<DEPTH>> for MerkleStore<T>

where T: KvMap<RpoDigest, StoreNode>,

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

Converts to this type from the input type.

impl<const DEPTH: u8> PartialEq for SimpleSmt<DEPTH>

fn eq(&self, other: &SimpleSmt<DEPTH>) -> 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<const DEPTH: u8> Eq for SimpleSmt<DEPTH>

impl<const DEPTH: u8> StructuralPartialEq for SimpleSmt<DEPTH>