pub struct SimpleSmt<const DEPTH: u8> { /* private fields */ }
Expand description
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§
source§impl<const DEPTH: u8> SimpleSmt<DEPTH>
impl<const DEPTH: u8> SimpleSmt<DEPTH>
sourcepub const EMPTY_VALUE: Word = _
pub const EMPTY_VALUE: Word = _
The default value used to compute the hash of empty leaves
sourcepub fn new() -> Result<Self, MerkleError>
pub fn new() -> Result<Self, MerkleError>
sourcepub fn with_leaves(
entries: impl IntoIterator<Item = (u64, Word)>,
) -> Result<Self, MerkleError>
pub fn with_leaves( entries: impl IntoIterator<Item = (u64, Word)>, ) -> Result<Self, 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.
sourcepub fn with_contiguous_leaves(
entries: impl IntoIterator<Item = Word>,
) -> Result<Self, MerkleError>
pub fn with_contiguous_leaves( entries: impl IntoIterator<Item = Word>, ) -> Result<Self, MerkleError>
Wrapper around SimpleSmt::with_leaves
which inserts leaves at contiguous indices
starting at index 0.
sourcepub fn num_leaves(&self) -> usize
pub fn num_leaves(&self) -> usize
Returns the number of non-empty leaves in this tree.
sourcepub fn get_leaf(&self, key: &LeafIndex<DEPTH>) -> Word
pub fn get_leaf(&self, key: &LeafIndex<DEPTH>) -> Word
Returns the leaf at the specified index.
sourcepub fn get_node(&self, index: NodeIndex) -> Result<RpoDigest, MerkleError>
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.
sourcepub fn open(&self, key: &LeafIndex<DEPTH>) -> ValuePath
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.
sourcepub fn leaves(&self) -> impl Iterator<Item = (u64, &Word)>
pub fn leaves(&self) -> impl Iterator<Item = (u64, &Word)>
Returns an iterator over the leaves of this SimpleSmt.
sourcepub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_
pub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_
Returns an iterator over the inner nodes of this SimpleSmt.
sourcepub fn insert(&mut self, key: LeafIndex<DEPTH>, value: Word) -> Word
pub fn insert(&mut self, key: LeafIndex<DEPTH>, value: Word) -> Word
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.
sourcepub fn compute_mutations(
&self,
kv_pairs: impl IntoIterator<Item = (LeafIndex<DEPTH>, Word)>,
) -> MutationSet<DEPTH, LeafIndex<DEPTH>, Word>
pub fn compute_mutations( &self, kv_pairs: impl IntoIterator<Item = (LeafIndex<DEPTH>, Word)>, ) -> MutationSet<DEPTH, LeafIndex<DEPTH>, Word>
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,
SimpleSmt::apply_mutations()
can be called in order to commit these changes to the
Merkle tree, or drop()
to discard them.
§Example
let mut smt: SimpleSmt<3> = SimpleSmt::new().unwrap();
let pair = (LeafIndex::default(), Word::default());
let mutations = smt.compute_mutations(vec![pair]);
assert_eq!(mutations.root(), *EmptySubtreeRoots::entry(3, 0));
smt.apply_mutations(mutations);
assert_eq!(smt.root(), *EmptySubtreeRoots::entry(3, 0));
sourcepub fn apply_mutations(
&mut self,
mutations: MutationSet<DEPTH, LeafIndex<DEPTH>, Word>,
) -> Result<(), MerkleError>
pub fn apply_mutations( &mut self, mutations: MutationSet<DEPTH, LeafIndex<DEPTH>, Word>, ) -> Result<(), MerkleError>
Apply the prospective mutations computed with SimpleSmt::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 alloc::vec::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.
sourcepub fn set_subtree<const SUBTREE_DEPTH: u8>(
&mut self,
subtree_insertion_index: u64,
subtree: SimpleSmt<SUBTREE_DEPTH>,
) -> Result<RpoDigest, MerkleError>
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§
source§impl<T: KvMap<RpoDigest, StoreNode>, const DEPTH: u8> From<&SimpleSmt<DEPTH>> for MerkleStore<T>
impl<T: KvMap<RpoDigest, StoreNode>, const DEPTH: u8> From<&SimpleSmt<DEPTH>> for MerkleStore<T>
impl<const DEPTH: u8> Eq for SimpleSmt<DEPTH>
impl<const DEPTH: u8> StructuralPartialEq for SimpleSmt<DEPTH>
Auto Trait Implementations§
impl<const DEPTH: u8> Freeze for SimpleSmt<DEPTH>
impl<const DEPTH: u8> RefUnwindSafe for SimpleSmt<DEPTH>
impl<const DEPTH: u8> Send for SimpleSmt<DEPTH>
impl<const DEPTH: u8> Sync for SimpleSmt<DEPTH>
impl<const DEPTH: u8> Unpin for SimpleSmt<DEPTH>
impl<const DEPTH: u8> UnwindSafe for SimpleSmt<DEPTH>
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§unsafe fn clone_to_uninit(&self, dst: *mut T)
unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)