Struct miden_core::crypto::merkle::MerkleStore

pub struct MerkleStore { /* private fields */ }

An in-memory data store for Merkle-lized 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::new();

// the store is initialized with the SMT empty nodes
assert_eq!(store.num_internal_nodes(), 255);

// populates the store with two merkle trees, common nodes are shared
store.add_merkle_tree([A, B, C, D, E, F, G, H0]);
store.add_merkle_tree([A, B, C, D, E, F, G, H1]);

// every leaf except the last are the same
for i in 0..7 {
    let d0 = store.get_node(ROOT0, NodeIndex::new(3, i)).unwrap();
    let d1 = store.get_node(ROOT1, NodeIndex::new(3, i)).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 d0 = store.get_path(ROOT0, NodeIndex::new(3, i)).unwrap();
    let d1 = store.get_path(ROOT1, NodeIndex::new(3, i)).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

impl MerkleStore

pub fn new() -> MerkleStore

Creates an empty MerkleStore instance.

pub fn with_merkle_tree<I>(self, leaves: I) -> Result<MerkleStore, MerkleError>where I: IntoIterator<Item = [BaseElement; 4]>,

Appends the provided merkle tree represented by its leaves to the set.

pub fn with_sparse_merkle_tree<R, I>( self, entries: R ) -> Result<MerkleStore, MerkleError>where R: IntoIterator<IntoIter = I>, I: Iterator<Item = (u64, [BaseElement; 4])> + ExactSizeIterator,

Appends the provided sparse merkle tree represented by its entries to the set.

pub fn with_merkle_path( self, index_value: u64, node: [BaseElement; 4], path: MerklePath ) -> Result<MerkleStore, MerkleError>

Appends the provided merkle path set.

pub fn with_merkle_paths<I>(self, paths: I) -> Result<MerkleStore, MerkleError>where I: IntoIterator<Item = (u64, [BaseElement; 4], MerklePath)>,

Appends the provided merkle path set.

pub fn num_internal_nodes(&self) -> usize

Return a count of the non-leaf nodes in the store.

pub fn get_node( &self, root: [BaseElement; 4], index: NodeIndex ) -> Result<[BaseElement; 4], MerkleError>

Returns the node at index rooted on the tree root.

Errors

This method can return the following errors:

• RootNotInStore if the root is not present in the store.
• NodeNotInStore if a node needed to traverse from root to index is not present in the store.

pub fn get_path( &self, root: [BaseElement; 4], 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 the root is not present in the store.
• NodeNotInStore if a node needed to traverse from root to index is not present in the store.

pub fn add_merkle_tree<I>( &mut self, leaves: I ) -> Result<[BaseElement; 4], MerkleError>where I: IntoIterator<Item = [BaseElement; 4]>,

Adds all the nodes of a Merkle tree represented by leaves.

This will instantiate a Merkle tree using leaves and include all the nodes into the store.

Errors

This method may return the following errors:

• DepthTooSmall if leaves is empty or contains only 1 element
• NumLeavesNotPowerOfTwo if the number of leaves is not a power-of-two

pub fn add_sparse_merkle_tree<R, I>( &mut self, entries: R ) -> Result<[BaseElement; 4], MerkleError>where R: IntoIterator<IntoIter = I>, I: Iterator<Item = (u64, [BaseElement; 4])> + ExactSizeIterator,

Adds all the nodes of a Sparse Merkle tree represented by entries.

This will instantiate a Sparse Merkle tree using entries and include all the nodes into the store.

Errors

This will return InvalidEntriesCount if the length of entries is not 63.

pub fn add_merkle_path( &mut self, index_value: u64, node: [BaseElement; 4], path: MerklePath ) -> Result<[BaseElement; 4], 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.

pub fn add_merkle_paths<I>( &mut self, paths: I ) -> Result<[BaseElement; 4], MerkleError>where I: IntoIterator<Item = (u64, [BaseElement; 4], 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.

Errors

Every path must resolve to the same root, otherwise this will return an ConflictingRoots error.

pub fn add_merkle_path_set( &mut self, path_set: &MerklePathSet ) -> Result<[BaseElement; 4], MerkleError>

Appends the provided MerklePathSet into the store.

For further reference, check MerkleStore::add_merkle_path.

pub fn set_node( &mut self, root: [BaseElement; 4], index: NodeIndex, value: [BaseElement; 4] ) -> Result<RootPath, MerkleError>

Sets a node to value.

Errors

This method can return the following errors:

• RootNotInStore if the root is not present in the store.
• NodeNotInStore if a node needed to traverse from root to index is not present in the store.

pub fn merge_roots( &mut self, root1: [BaseElement; 4], root2: [BaseElement; 4] ) -> Result<[BaseElement; 4], MerkleError>

Trait Implementations

impl Clone for MerkleStore

fn clone(&self) -> MerkleStore

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for MerkleStore

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

Formats the value using the given formatter.

impl Default for MerkleStore

fn default() -> MerkleStore

Returns the “default value” for a type.

impl Deserializable for MerkleStore

fn read_from<R>(source: &mut R) -> Result<MerkleStore, 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.

fn read_batch_from<R>( source: &mut R, num_elements: usize ) -> Result<Vec<Self, Global>, DeserializationError>where R: ByteReader,

Reads a sequence of bytes from the provided source, attempts to deserialize these bytes into a vector with the specified number of Self elements, and returns the result.

impl PartialEq<MerkleStore> for MerkleStore

fn eq(&self, other: &MerkleStore) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serializable for MerkleStore

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, Global>

Serializes self into a vector of bytes.

fn write_batch_into<W>(source: &[Self], target: &mut W)where W: ByteWriter,

Serializes all elements of the source and writes these bytes into the target.

fn get_size_hint(&self) -> usize

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

impl Eq for MerkleStore

impl StructuralEq for MerkleStore

impl StructuralPartialEq for MerkleStore