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.

Once a partial SMT has been constructed, its root is set in stone. All subsequently added proofs or merkle paths must match that root, otherwise an error is returned.

Implementations

impl PartialSmt

pub fn new(root: Word) -> PartialSmt

Constructs a PartialSmt from a root.

All subsequently added proofs or paths must have the same root.

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

where I: IntoIterator<Item = SmtProof>,

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

If the provided iterator is empty, an empty PartialSmt is returned.

Errors

Returns an error if:

• the roots of the provided proofs are not the same.

pub fn root(&self) -> Word

Returns the root of the tree.

pub fn open(&self, key: &Word) -> 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: &Word) -> 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: &Word) -> Result<Word, 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: 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 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.
• inserting the key-value pair would exceed super::MAX_LEAF_ENTRIES (1024 entries) in the leaf.

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: SparseMerklePath, ) -> Result<(), MerkleError>

Adds a leaf and its sparse 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. 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 inner_node_indices(&self) -> impl Iterator<Item = (NodeIndex, InnerNode)>

Returns an iterator over the [InnerNode] and the respective NodeIndex 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 = &(Word, Word)>

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.

pub fn tracks_leaves(&self) -> bool

Returns a boolean value indicating whether the PartialSmt tracks any leaves.

Note that if a partial SMT does not track leaves, its root is not necessarily the empty SMT root, since it could have been constructed from a different root but without tracking any leaves.

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 a new, empty PartialSmt.

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

impl Deserializable for PartialSmt

fn read_from<R>(source: &mut R) -> Result<PartialSmt, 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 Eq for PartialSmt

impl From<Smt> for PartialSmt

fn from(smt: Smt) -> PartialSmt

Converts to this type from the input 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 Serializable for PartialSmt

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

where W: ByteWriter,

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

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

Serializes self into a vector of bytes.

fn get_size_hint(&self) -> usize

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

impl StructuralPartialEq for PartialSmt

impl TryFrom<PartialSmt> for PartialVault

fn try_from(partial_smt: PartialSmt) -> Result<Self, Self::Error>

Returns a new instance of a partial vault from the provided partial SMT.

Errors

Returns an error if:

• the provided SMT does not track only valid Assets.
• the vault key at which the asset is stored does not match the vault key derived from the asset.

type Error = PartialAssetVaultError

The type returned in the event of a conversion error.