Struct SparseMerkleTree

pub struct SparseMerkleTree<P> { /* private fields */ }

Paddable sparse Merkle tree.

Implementations

impl<P: Clone + Default + Mergeable + Paddable + ProofExtractable> SparseMerkleTree<P>

where <P as ProofExtractable>::ProofNode: Clone + Default + Eq + Mergeable + Serializable,

pub fn new(height: usize) -> SparseMerkleTree<P>

The constructor.

Panics if the input height exceeds MAX_HEIGHT.

pub fn new_merkle_tree(list: &[P]) -> SparseMerkleTree<P>

A simple Merkle tree constructor, where all items are added next to each other from left to right. Note that zero padding secret is used and the height depends on the input list size. Use this helper constructor only when simulating a plain Merkle tree.

pub fn get_height(&self) -> usize

Returns the height of the SMT.

pub fn get_nodes_num(&self) -> usize

Returns the number of nodes in the SMT.

pub fn get_node_by_ref(&self, link: usize) -> &TreeNode<P>

Returns the tree node by reference.

Panics if the reference is out of range.

pub fn get_node_raw_by_refs(&self, list: &[usize]) -> Vec<&P>

Returns the tree node by references.

Panics if the reference is out of range.

pub fn get_node_proof_by_refs(&self, list: &[usize]) -> Vec<P::ProofNode>

Returns the tree node by references.

Panics if the reference is out of range.

pub fn get_root_ref(&self) -> usize

Returns the reference to the root ndoe.

pub fn get_root_raw(&self) -> &P

Returns the raw data of the root.

pub fn get_root(&self) -> <P as ProofExtractable>::ProofNode

Returns the data of the root that is visible in the Merkle proof.

pub fn get_closest_ancestor_ref_index( &self, idx: &TreeIndex, ) -> (usize, TreeIndex)

pub fn get_leaf_by_index(&self, idx: &TreeIndex) -> Option<&TreeNode<P>>

Returns the tree node of a queried tree index.

Panics if the the height of the input index doesn’t match with the tree height.

If the node doesn’t exist, return None.

pub fn get_index_ref_pairs(&self) -> Vec<(TreeIndex, usize)>

Returns the index-reference pairs of all tree nodes in a BFS order.

pub fn get_index_node_pairs(&self) -> Vec<(TreeIndex, &TreeNode<P>)>

Returns the index-node pairs of all tree nodes.

pub fn get_leaves(&self) -> Vec<(TreeIndex, &TreeNode<P>)>

Returns the index-node pairs of all leaf nodes.

pub fn get_paddings(&self) -> Vec<(TreeIndex, &TreeNode<P>)>

Returns the index-node pairs of all padding nodes.

pub fn get_internals(&self) -> Vec<(TreeIndex, &TreeNode<P>)>

Returns the index-node pairs of all internal nodes.

pub fn check_index_list_validity( &self, list: &[(TreeIndex, P)], ) -> Option<TreeError>

Check if the tree indexes in the list are all valid and sorted.

If the height of some index doesn’t match with the height of the tree, return TreeError::HeightNotMatch.

If the indexes are not in order, return TreeError::IndexNotSorted.

If there are duplicated indexes in the list, return TreeError::IndexDuplicated.

pub fn construct_smt_nodes( &mut self, list: &[(TreeIndex, P)], secret: &Secret, ) -> Option<TreeError>

Construct SMT from the input list of sorted index-value pairs, index being the sorting key.

If the height of some index in the input list doesn’t match with the height of the tree, return TreeError::HeightNotMatch.

If the indexes in the input list are not in order, return TreeError::IndexNotSorted.

If there are duplicated indexes in the list, return TreeError::IndexDuplicated.

pub fn build(&mut self, list: &[(TreeIndex, P)], secret: &Secret)

Build SMT from the input list of sorted index-value pairs, index being the sorting key.

Panics if the input list is not valid.

pub fn update(&mut self, key: &TreeIndex, value: P, secret: &Secret)

Update the tree by modifying the leaf node of a certain tree index.

Panics if the height of the input index doesn’t match with that of the tree.

pub fn get_merkle_path_ref(&self, idx: &TreeIndex) -> Option<Vec<usize>>

Returns the references to the input leaf node and siblings of nodes long the Merkle path from the root to the leaf. The result is a list of references [leaf, sibling, ..., sibling].

If the input leaf node doesn’t exist, return None.

Panics if the height of the input index is different from the height of the tree.

pub fn get_merkle_path_ref_batch( &self, list: &[TreeIndex], ) -> Option<Vec<usize>>

Returns the references to the input leaves and siblings of nodes long the batched Merkle paths from the root to the leaves. The result is a list of references [leaf, ..., leaf, sibling, ..., sibling].

If the root or some input leaf node doesn’t exist, return None.

If the input list is empty, return an empty vector.

Panics if the input list is not valid.

pub fn get_closest_index_by_dir( &self, ancestor_ref: usize, ancestor_idx: TreeIndex, dir: ChildDir, ) -> Option<TreeIndex>

Returns the tree index of closest left/right (depending on input direction) node in the tree.

pub fn get_padding_proof_by_dir_index_ref_pairs( idx: &TreeIndex, dir: ChildDir, ) -> Vec<(TreeIndex, usize)>

Returns the index-reference pairs to necessary padding nodes to prove that the input index is the left/right (depending on the input direction) most real leaf in the tree. Note that the reference is the offset from the end of the sibling list.

pub fn get_padding_proof_batch_index_ref_pairs( left_idx: &TreeIndex, right_idx: &TreeIndex, ) -> Vec<(TreeIndex, usize)>

Returns the index-reference pairs to necessary padding nodes to prove that there are no other real leaf nodes between the input indexes in the tree. Note that the reference is the offset from the end of the sibling list.

Panics if the input indexes don’t have the same height or not in the right order.

Trait Implementations

impl<P: Debug> Debug for SparseMerkleTree<P>

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

Formats the value using the given formatter.

impl<P: Default> Default for SparseMerkleTree<P>

fn default() -> SparseMerkleTree<P>

Returns the “default value” for a type.