Struct miden_crypto::merkle::PartialMerkleTree

pub struct PartialMerkleTree { /* private fields */ }

A partial Merkle tree with NodeIndex keys and 4-element RpoDigest leaf values. Partial Merkle Tree allows to create Merkle Tree by providing Merkle paths of different lengths.

The root of the tree is recomputed on each new leaf update.

Implementations

impl PartialMerkleTree

pub const MIN_DEPTH: u8 = 1u8

Minimum supported depth.

pub const MAX_DEPTH: u8 = 64u8

Maximum supported depth.

pub fn new() -> Self

Returns a new empty PartialMerkleTree.

pub fn with_paths<I>(paths: I) -> Result<Self, MerkleError>where I: IntoIterator<Item = (u64, RpoDigest, MerklePath)>,

Appends the provided paths iterator into the set.

Analogous to Self::add_path.

pub fn with_leaves<R, I>(entries: R) -> Result<Self, MerkleError>where R: IntoIterator<IntoIter = I>, I: Iterator<Item = (NodeIndex, RpoDigest)> + ExactSizeIterator,

Returns a new PartialMerkleTree instantiated with leaves map as specified by the provided entries.

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 an insufficient set of nodes.

pub fn root(&self) -> RpoDigest

Returns the root of this Merkle tree.

pub fn max_depth(&self) -> u8

Returns the depth of this Merkle tree.

pub fn get_node(&self, index: NodeIndex) -> Result<RpoDigest, MerkleError>

Returns a node at the specified NodeIndex.

Errors

Returns an error if the specified NodeIndex is not contained in the nodes map.

pub fn is_leaf(&self, index: NodeIndex) -> bool

Returns true if provided index contains in the leaves set, false otherwise.

pub fn to_paths(&self) -> Vec<(NodeIndex, ValuePath)>

Returns a vector of paths from every leaf to the root.

pub fn get_path(&self, index: NodeIndex) -> Result<MerklePath, MerkleError>

Returns a Merkle path from the node at the specified index to the root.

The node itself is not included in the path.

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.
• the specified index is not contained in the nodes map.

pub fn leaves(&self) -> impl Iterator<Item = (NodeIndex, RpoDigest)> + '_

Returns an iterator over the leaves of this PartialMerkleTree.

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

Returns an iterator over the inner nodes of this Merkle tree.

pub fn add_path( &mut self, index_value: u64, value: RpoDigest, path: MerklePath ) -> Result<(), MerkleError>

Adds the nodes of the specified Merkle path to this PartialMerkleTree. The index_value and value parameters specify the leaf node at which the path starts.

Errors

Returns an error if:

• The depth of the specified node_index is greater than 64 or smaller than 1.
• The specified path is not consistent with other paths in the set (i.e., resolves to a different root).

pub fn update_leaf( &mut self, index: u64, value: Word ) -> Result<RpoDigest, MerkleError>

Updates value of the leaf at the specified index returning the old leaf value. By default the specified index is assumed to belong to the deepest layer. If the considered node does not belong to the tree, the first node on the way to the root will be changed.

By default the specified index is assumed to belong to the deepest layer. If the considered node does not belong to the tree, the first node on the way to the root will be changed.

This also recomputes all hashes between the leaf and the root, updating the root itself.

Errors

Returns an error if:

• The specified index is greater than the maximum number of nodes on the deepest layer.

pub fn print(&self) -> Result<String, Error>

Utility to visualize a PartialMerkleTree in text.

Trait Implementations

impl Clone for PartialMerkleTree

fn clone(&self) -> PartialMerkleTree

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for PartialMerkleTree

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

Formats the value using the given formatter.

impl Default for PartialMerkleTree

fn default() -> Self

Returns the “default value” for a type.

impl Deserializable for PartialMerkleTree

fn read_from<R: ByteReader>( source: &mut R ) -> Result<Self, DeserializationError>

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>, 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<T: KvMap<RpoDigest, StoreNode>> From<&PartialMerkleTree> for MerkleStore<T>

fn from(value: &PartialMerkleTree) -> Self

Converts to this type from the input type.

impl PartialEq for PartialMerkleTree

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

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

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 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 PartialMerkleTree

impl StructuralEq for PartialMerkleTree

impl StructuralPartialEq for PartialMerkleTree