Struct miden_crypto::merkle::MerkleStore
source · pub struct MerkleStore<T: KvMap<RpoDigest, StoreNode> = BTreeMap<RpoDigest, StoreNode>> { /* private fields */ }
Expand description
An in-memory data store for Merkelized data.
This is a in memory data store for Merkle trees, this store allows all the nodes of multiple trees to live as long as necessary and without duplication, this allows the implementation of space efficient persistent data structures.
Example usage:
let mut store: MerkleStore = MerkleStore::new();
// the store is initialized with the SMT empty nodes
assert_eq!(store.num_internal_nodes(), 255);
let tree1 = MerkleTree::new(vec![A, B, C, D, E, F, G, H0]).unwrap();
let tree2 = MerkleTree::new(vec![A, B, C, D, E, F, G, H1]).unwrap();
// populates the store with two merkle trees, common nodes are shared
store.extend(tree1.inner_nodes());
store.extend(tree2.inner_nodes());
// every leaf except the last are the same
for i in 0..7 {
let idx0 = NodeIndex::new(3, i).unwrap();
let d0 = store.get_node(ROOT0, idx0).unwrap();
let idx1 = NodeIndex::new(3, i).unwrap();
let d1 = store.get_node(ROOT1, idx1).unwrap();
assert_eq!(d0, d1, "Both trees have the same leaf at pos {i}");
}
// The leafs A-B-C-D are the same for both trees, so are their 2 immediate parents
for i in 0..4 {
let idx0 = NodeIndex::new(3, i).unwrap();
let d0 = store.get_path(ROOT0, idx0).unwrap();
let idx1 = NodeIndex::new(3, i).unwrap();
let d1 = store.get_path(ROOT1, idx1).unwrap();
assert_eq!(d0.path[0..2], d1.path[0..2], "Both sub-trees are equal up to two levels");
}
// Common internal nodes are shared, the two added trees have a total of 30, but the store has
// only 10 new entries, corresponding to the 10 unique internal nodes of these trees.
assert_eq!(store.num_internal_nodes() - 255, 10);
Implementations§
source§impl<T: KvMap<RpoDigest, StoreNode>> MerkleStore<T>
impl<T: KvMap<RpoDigest, StoreNode>> MerkleStore<T>
sourcepub fn new() -> MerkleStore<T>
pub fn new() -> MerkleStore<T>
Creates an empty MerkleStore
instance.
sourcepub fn num_internal_nodes(&self) -> usize
pub fn num_internal_nodes(&self) -> usize
Return a count of the non-leaf nodes in the store.
sourcepub fn get_node(
&self,
root: RpoDigest,
index: NodeIndex
) -> Result<RpoDigest, MerkleError>
pub fn get_node( &self, root: RpoDigest, index: NodeIndex ) -> Result<RpoDigest, MerkleError>
Returns the node at index
rooted on the tree root
.
Errors
This method can return the following errors:
RootNotInStore
if theroot
is not present in the store.NodeNotInStore
if a node needed to traverse fromroot
toindex
is not present in the store.
sourcepub fn get_path(
&self,
root: RpoDigest,
index: NodeIndex
) -> Result<ValuePath, MerkleError>
pub fn get_path( &self, root: RpoDigest, index: NodeIndex ) -> Result<ValuePath, MerkleError>
Returns the node at the specified index
and its opening to the root
.
The path starts at the sibling of the target leaf.
Errors
This method can return the following errors:
RootNotInStore
if theroot
is not present in the store.NodeNotInStore
if a node needed to traverse fromroot
toindex
is not present in the store.
sourcepub fn get_leaf_depth(
&self,
root: RpoDigest,
tree_depth: u8,
index: u64
) -> Result<u8, MerkleError>
pub fn get_leaf_depth( &self, root: RpoDigest, tree_depth: u8, index: u64 ) -> Result<u8, MerkleError>
Returns the depth of the first leaf or an empty node encountered while traversing the tree from the specified root down according to the provided index.
The tree_depth
parameter specifies the depth of the tree rooted at root
. The
maximum value the argument accepts is u64::BITS.
Errors
Will return an error if:
- The provided root is not found.
- The provided
tree_depth
is greater than 64. - The provided
index
is not valid for a depth equivalent totree_depth
. - No leaf or an empty node was found while traversing the tree down to
tree_depth
.
sourcepub fn find_lone_leaf(
&self,
root: RpoDigest,
root_index: NodeIndex,
tree_depth: u8
) -> Result<Option<(NodeIndex, RpoDigest)>, MerkleError>
pub fn find_lone_leaf( &self, root: RpoDigest, root_index: NodeIndex, tree_depth: u8 ) -> Result<Option<(NodeIndex, RpoDigest)>, MerkleError>
Returns index and value of a leaf node which is the only leaf node in a subtree defined by the provided root. If the subtree contains zero or more than one leaf nodes None is returned.
The tree_depth
parameter specifies the depth of the parent tree such that root
is
located in this tree at root_index
. The maximum value the argument accepts is
u64::BITS.
Errors
Will return an error if:
- The provided root is not found.
- The provided
tree_depth
is greater than 64. - The provided
root_index
has depth greater thantree_depth
. - A lone node at depth
tree_depth
is not a leaf node.
sourcepub fn subset<I, R>(&self, roots: I) -> MerkleStore<T>where
I: Iterator<Item = R>,
R: Borrow<RpoDigest>,
pub fn subset<I, R>(&self, roots: I) -> MerkleStore<T>where I: Iterator<Item = R>, R: Borrow<RpoDigest>,
Returns a subset of this Merkle store such that the returned Merkle store contains all nodes which are descendants of the specified roots.
The roots for which no descendants exist in this Merkle store are ignored.
sourcepub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_
pub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_
Iterator over the inner nodes of the MerkleStore.
sourcepub fn non_empty_leaves(
&self,
root: RpoDigest,
max_depth: u8
) -> impl Iterator<Item = (NodeIndex, RpoDigest)> + '_
pub fn non_empty_leaves( &self, root: RpoDigest, max_depth: u8 ) -> impl Iterator<Item = (NodeIndex, RpoDigest)> + '_
Iterator over the non-empty leaves of the Merkle tree associated with the specified root
and max_depth
.
sourcepub fn add_merkle_path(
&mut self,
index: u64,
node: RpoDigest,
path: MerklePath
) -> Result<RpoDigest, MerkleError>
pub fn add_merkle_path( &mut self, index: u64, node: RpoDigest, path: MerklePath ) -> Result<RpoDigest, MerkleError>
Adds all the nodes of a Merkle path represented by path
, opening to node
. Returns the
new root.
This will compute the sibling elements determined by the Merkle path
and node
, and
include all the nodes into the store.
sourcepub fn add_merkle_paths<I>(&mut self, paths: I) -> Result<(), MerkleError>where
I: IntoIterator<Item = (u64, RpoDigest, MerklePath)>,
pub fn add_merkle_paths<I>(&mut self, paths: I) -> Result<(), MerkleError>where I: IntoIterator<Item = (u64, RpoDigest, MerklePath)>,
Adds all the nodes of multiple Merkle paths into the store.
This will compute the sibling elements for each Merkle path
and include all the nodes
into the store.
For further reference, check MerkleStore::add_merkle_path.
sourcepub fn set_node(
&mut self,
root: RpoDigest,
index: NodeIndex,
value: RpoDigest
) -> Result<RootPath, MerkleError>
pub fn set_node( &mut self, root: RpoDigest, index: NodeIndex, value: RpoDigest ) -> Result<RootPath, MerkleError>
Sets a node to value
.
Errors
This method can return the following errors:
RootNotInStore
if theroot
is not present in the store.NodeNotInStore
if a node needed to traverse fromroot
toindex
is not present in the store.
sourcepub fn merge_roots(
&mut self,
left_root: RpoDigest,
right_root: RpoDigest
) -> Result<RpoDigest, MerkleError>
pub fn merge_roots( &mut self, left_root: RpoDigest, right_root: RpoDigest ) -> Result<RpoDigest, MerkleError>
Merges two elements and adds the resulting node into the store.
Merges arbitrary values. They may be leafs, nodes, or a mixture of both.
sourcepub fn into_inner(self) -> T
pub fn into_inner(self) -> T
Returns the inner storage of this MerkleStore while consuming self
.
Trait Implementations§
source§impl<T: Clone + KvMap<RpoDigest, StoreNode>> Clone for MerkleStore<T>
impl<T: Clone + KvMap<RpoDigest, StoreNode>> Clone for MerkleStore<T>
source§fn clone(&self) -> MerkleStore<T>
fn clone(&self) -> MerkleStore<T>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl<T: KvMap<RpoDigest, StoreNode>> Deserializable for MerkleStore<T>
impl<T: KvMap<RpoDigest, StoreNode>> Deserializable for MerkleStore<T>
source§fn read_from<R: ByteReader>(
source: &mut R
) -> Result<Self, DeserializationError>
fn read_from<R: ByteReader>( source: &mut R ) -> Result<Self, DeserializationError>
source
, attempts to deserialize these bytes
into Self
, and returns the result. Read moresource§fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError>
fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError>
source§fn read_batch_from<R>(
source: &mut R,
num_elements: usize
) -> Result<Vec<Self>, DeserializationError>where
R: ByteReader,
fn read_batch_from<R>( source: &mut R, num_elements: usize ) -> Result<Vec<Self>, DeserializationError>where R: ByteReader,
source
, attempts to deserialize these bytes
into a vector with the specified number of Self
elements, and returns the result. Read moresource§impl<T: KvMap<RpoDigest, StoreNode>> Extend<InnerNodeInfo> for MerkleStore<T>
impl<T: KvMap<RpoDigest, StoreNode>> Extend<InnerNodeInfo> for MerkleStore<T>
source§fn extend<I: IntoIterator<Item = InnerNodeInfo>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = InnerNodeInfo>>(&mut self, iter: I)
source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)source§impl<T: KvMap<RpoDigest, StoreNode>> From<&MerkleTree> for MerkleStore<T>
impl<T: KvMap<RpoDigest, StoreNode>> From<&MerkleTree> for MerkleStore<T>
source§fn from(value: &MerkleTree) -> Self
fn from(value: &MerkleTree) -> Self
source§impl<T: KvMap<RpoDigest, StoreNode>> From<&PartialMerkleTree> for MerkleStore<T>
impl<T: KvMap<RpoDigest, StoreNode>> From<&PartialMerkleTree> for MerkleStore<T>
source§fn from(value: &PartialMerkleTree) -> Self
fn from(value: &PartialMerkleTree) -> Self
source§impl<T: KvMap<RpoDigest, StoreNode>> FromIterator<(RpoDigest, StoreNode)> for MerkleStore<T>
impl<T: KvMap<RpoDigest, StoreNode>> FromIterator<(RpoDigest, StoreNode)> for MerkleStore<T>
source§impl<T: KvMap<RpoDigest, StoreNode>> FromIterator<InnerNodeInfo> for MerkleStore<T>
impl<T: KvMap<RpoDigest, StoreNode>> FromIterator<InnerNodeInfo> for MerkleStore<T>
source§fn from_iter<I: IntoIterator<Item = InnerNodeInfo>>(iter: I) -> Self
fn from_iter<I: IntoIterator<Item = InnerNodeInfo>>(iter: I) -> Self
source§impl<T: PartialEq + KvMap<RpoDigest, StoreNode>> PartialEq for MerkleStore<T>
impl<T: PartialEq + KvMap<RpoDigest, StoreNode>> PartialEq for MerkleStore<T>
source§fn eq(&self, other: &MerkleStore<T>) -> bool
fn eq(&self, other: &MerkleStore<T>) -> bool
self
and other
values to be equal, and is used
by ==
.source§impl<T: KvMap<RpoDigest, StoreNode>> Serializable for MerkleStore<T>
impl<T: KvMap<RpoDigest, StoreNode>> Serializable for MerkleStore<T>
source§fn write_into<W: ByteWriter>(&self, target: &mut W)
fn write_into<W: ByteWriter>(&self, target: &mut W)
self
into bytes and writes these bytes into the target
.