Struct PartialSmt

pub struct PartialSmt(/* private fields */);

A partial version of an Smt.

This type can track a subset of the key-value pairs of a full Smt and allows for updating those pairs to compute the new root of the tree, as if the updates had been done on the full tree. This is useful so that not all leaves have to be present and loaded into memory to compute an update.

To facilitate this, a partial SMT requires that the merkle paths of every key-value pair are added to the tree. This means this pair is considered “tracked” and can be updated.

An important caveat is that only pairs whose merkle paths were added can be updated. Attempting to update an untracked value will result in an error. See PartialSmt::insert for more details.

Implementations

impl PartialSmt

pub fn new() -> PartialSmt

Returns a new PartialSmt.

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

pub fn from_proofs<I>(proofs: I) -> Result<PartialSmt, MerkleError>

where I: IntoIterator<Item = SmtProof>,

Instantiates a new PartialSmt by calling PartialSmt::add_path for all SmtProofs in the provided iterator.

Errors

Returns an error if:

• the new root after the insertion of a (leaf, path) tuple does not match the existing root (except if the tree was previously empty).

pub fn root(&self) -> RpoDigest

Returns the root of the tree.

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

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.

Errors

Returns an error if:

• the key is not tracked by this partial SMT.

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

Returns the leaf to which key maps

Errors

Returns an error if:

• the key is not tracked by this partial SMT.

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

Returns the value associated with key.

Errors

Returns an error if:

• the key is not tracked by this partial SMT.

pub fn insert( &mut self, key: RpoDigest, value: [BaseElement; 4], ) -> Result<[BaseElement; 4], 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 Smt::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:

• the key and its merkle path were not previously added (using PartialSmt::add_path) to this PartialSmt, which means it is almost certainly incorrect to update its value. If an error is returned the tree is in the same state as before.

pub fn add_proof(&mut self, proof: SmtProof) -> Result<(), MerkleError>

Adds an SmtProof to this PartialSmt.

This is a convenience method which calls Self::add_path on the proof. See its documentation for details on errors.

pub fn add_path( &mut self, leaf: SmtLeaf, path: MerklePath, ) -> Result<(), MerkleError>

Adds a leaf and its merkle path to this PartialSmt.

If this function was called, any key that is part of the leaf can subsequently be updated to a new value and produce a correct new tree root.

Errors

Returns an error if:

• the new root after the insertion of the leaf and the path does not match the existing root (except when the first leaf is added). If an error is returned, the tree is left in an inconsistent state.

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

Returns an iterator over the inner nodes of the PartialSmt.

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

Returns an iterator over the tracked, non-empty leaves of the PartialSmt in arbitrary order.

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

Returns an iterator over the tracked leaves of the PartialSmt in arbitrary order.

Note that this includes empty leaves.

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

Returns an iterator over the tracked, non-empty key-value pairs of the PartialSmt in arbitrary order.

pub fn num_leaves(&self) -> usize

Returns the number of tracked leaves in this tree, which includes empty ones.

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 tracked, non-empty key-value pairs 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 is_empty(&self) -> bool

Returns a boolean value indicating whether the PartialSmt is empty.

Trait Implementations

impl Clone for PartialSmt

fn clone(&self) -> PartialSmt

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for PartialSmt

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

Formats the value using the given formatter.

impl Default for PartialSmt

fn default() -> PartialSmt

Returns the “default value” for a type.

impl PartialEq for PartialSmt

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

impl StructuralPartialEq for PartialSmt