Struct miden_crypto::merkle::TieredSmt
source · pub struct TieredSmt { /* private fields */ }Expand description
Tiered (compacted) Sparse Merkle tree mapping 256-bit keys to 256-bit values. Both keys and values are represented by 4 field elements.
Leaves in the tree can exist only on specific depths called “tiers”. These depths are: 16, 32, 48, and 64. Initially, when a tree is empty, it is equivalent to an empty Sparse Merkle tree of depth 64 (i.e., leaves at depth 64 are set to [ZERO; 4]). As non-empty values are inserted into the tree they are added to the first available tier.
For example, when the first key-value pair is inserted, it will be stored in a node at depth 16 such that the 16 most significant bits of the key determine the position of the node at depth 16. If another value with a key sharing the same 16-bit prefix is inserted, both values move into the next tier (depth 32). This process is repeated until values end up at the bottom tier (depth 64). If multiple values have keys with a common 64-bit prefix, such key-value pairs are stored in a sorted list at the bottom tier.
To differentiate between internal and leaf nodes, node values are computed as follows:
- Internal nodes: hash(left_child, right_child).
- Leaf node at depths 16, 32, or 64: hash(key, value, domain=depth).
- Leaf node at depth 64: hash([key_0, value_0, …, key_n, value_n], domain=64).
Implementations§
source§impl TieredSmt
impl TieredSmt
sourcepub const TIER_DEPTHS: [u8; 4] = _
pub const TIER_DEPTHS: [u8; 4] = _
Depths at which leaves can exist in a tiered SMT.
sourcepub const EMPTY_VALUE: Word = super::EMPTY_WORD
pub const EMPTY_VALUE: Word = super::EMPTY_WORD
Value of an empty leaf.
sourcepub fn with_entries<R, I>(entries: R) -> Result<Self, MerkleError>where
R: IntoIterator<IntoIter = I>,
I: Iterator<Item = (RpoDigest, Word)> + ExactSizeIterator,
pub fn with_entries<R, I>(entries: R) -> Result<Self, MerkleError>where R: IntoIterator<IntoIter = I>, I: Iterator<Item = (RpoDigest, Word)> + ExactSizeIterator,
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 depth is 0 or greater than 64.
- The node with the specified index does not exists in the Merkle tree. This is possible when a leaf node with the same index prefix exists at a tier higher than the requested node.
sourcepub fn get_path(&self, index: NodeIndex) -> Result<MerklePath, MerkleError>
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 depth is 0 or greater than 64.
- The node with the specified index does not exists in the Merkle tree. This is possible when a leaf node with the same index prefix exists at a tier higher than the node to which the path is requested.
sourcepub fn get_value(&self, key: RpoDigest) -> Word
pub fn get_value(&self, key: RpoDigest) -> Word
Returns the value associated with the specified key.
If nothing was inserted into this tree for the specified key, [ZERO; 4] is returned.
sourcepub fn prove(&self, key: RpoDigest) -> TieredSmtProof
pub fn prove(&self, key: RpoDigest) -> TieredSmtProof
Returns a proof for a key-value pair defined by the specified key.
The proof can be used to attest membership of this key-value pair in a Tiered Sparse Merkle Tree defined by the same root as this tree.
sourcepub fn insert(&mut self, key: RpoDigest, value: Word) -> Word
pub fn insert(&mut self, key: RpoDigest, value: Word) -> Word
Inserts the provided value into the tree under the specified key and returns the value previously stored under this key.
If the value for the specified key was not previously set, [ZERO; 4] is returned.
sourcepub fn iter(&self) -> impl Iterator<Item = &(RpoDigest, Word)>
pub fn iter(&self) -> impl Iterator<Item = &(RpoDigest, Word)>
Returns an iterator over all key-value pairs in this TieredSmt.
sourcepub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_
pub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_
Returns an iterator over all inner nodes of this TieredSmt (i.e., nodes not at depths 16 32, 48, or 64).
The iterator order is unspecified.
sourcepub fn upper_leaves(
&self
) -> impl Iterator<Item = (RpoDigest, RpoDigest, Word)> + '_
pub fn upper_leaves( &self ) -> impl Iterator<Item = (RpoDigest, RpoDigest, Word)> + '_
Returns an iterator over upper leaves (i.e., depth = 16, 32, or 48) for this TieredSmt where each yielded item is a (node, key, value) tuple.
The iterator order is unspecified.
sourcepub fn upper_leaf_nodes(&self) -> impl Iterator<Item = (&NodeIndex, &RpoDigest)>
pub fn upper_leaf_nodes(&self) -> impl Iterator<Item = (&NodeIndex, &RpoDigest)>
Returns an iterator over upper leaves (i.e., depth = 16, 32, or 48) for this TieredSmt where each yielded item is a (node_index, value) tuple.
sourcepub fn bottom_leaves(
&self
) -> impl Iterator<Item = (RpoDigest, Vec<(RpoDigest, Word)>)> + '_
pub fn bottom_leaves( &self ) -> impl Iterator<Item = (RpoDigest, Vec<(RpoDigest, Word)>)> + '_
Returns an iterator over bottom leaves (i.e., depth = 64) of this TieredSmt.
Each yielded item consists of the hash of the leaf and its contents, where contents is a vector containing key-value pairs of entries storied in this leaf.
The iterator order is unspecified.