Struct indexed_merkle_tree::IndexedMerkleTree

pub struct IndexedMerkleTree { /* private fields */ }

Represents an Indexed Merkle Tree.

This structure encapsulates a Merkle Tree where nodes are indexed, facilitating efficient updates and proofs, especially Non-Membership proofs.

Fields:

• nodes: A vector of Node elements, representing the nodes of the indexed Merkle Tree.

Implementations

impl IndexedMerkleTree

pub fn new(nodes: Vec<Node>) -> Result<Self, MerkleTreeError>

Creates a new IndexedMerkleTree from a given nodes vector.

Arguments

• nodes - A vector of nodes from which the Merkle tree will be built.

Returns

• Self - A new IndexedMerkleTree

pub fn calculate_empty_tree_commitment_from_size( size: usize ) -> Result<String, MerkleTreeError>

Calculates the commitment of an empty Merkle tree of a given size.

This function initializes an empty Indexed Merkle Tree with a specified number of nodes, all set to inactive except for the first one (so an active treeper definition). It then computes the tree’s commitment, which represents the root hash of the empty tree.

Arguments

• size - The number of nodes in the tree.

Returns

A Result<String, MerkleTreeError> representing the tree’s commitment or an error.

pub fn resort_nodes_by_input_order( nodes: Vec<Node>, input_order: Vec<String> ) -> Result<Vec<Node>, MerkleTreeError>

Resorts nodes based on a specified input order.

This function rearranges a given vector of nodes to match an input order defined by a vector of labels. It filters out inner nodes and so it sorts only leaf nodes based on their label’s position in the input vector.

Arguments

• nodes - A vector of Node elements to be sorted.
• input_order - A vector of strings representing the desired order of leaf labels.

Returns

A Result<Vec<Node>, MerkleTreeError> representing the sorted nodes or an error.

pub fn create_inner_node(left: Node, right: Node, index: usize) -> Node

Creates a new inner node in the Merkle Tree.

This function generates an inner node from two child nodes (left and right) and an index. The index determines the new node’s left sibling status. The hash for the inner node is calculated based on its children. This is crucial for constructing the tree and updating its structure.

Arguments

• left - The left child node.
• right - The right child node.
• index - The position index of the new node in the tree.

Returns

A Node representing the newly created inner node.

pub fn calculate_next_level(&mut self, current_nodes: Vec<Node>) -> Vec<Node>

Calculates the next level of the Merkle tree by aggregating the hash values of the current level nodes in pairs, creating new inner nodes and adding them to the indexed merkle tree nodes.

Arguments

• current_nodes - A vector of nodes representing the current level of the tree.

Returns

A vector of nodes representing the next level of the Merkle tree.

pub fn get_root(&self) -> Result<&Node, MerkleTreeError>

Returns

The current root node of the Indexed Merkle tree.

pub fn get_commitment(&self) -> Result<String, MerkleTreeError>

Returns

The current commitment (hash of the root node) of the Indexed Merkle tree.

pub fn find_node_index(&self, node: &Node) -> Option<usize>

Finds the index of a specific node in the indexed Merkle Tree.

This function searches through the tree’s nodes to find the index of a given node. It compares leaf nodes by label and inner nodes by hash. The function returns the node’s index if found, or None if the node is not present in the tree.

Arguments

• node - A reference to the Node whose index is being searched for.

Returns

An Option<usize> indicating the index of the node if found.

pub fn find_leaf_by_label(&self, label: &String) -> Option<Node>

Searches for a leaf node by its label in the indexed Merkle Tree.

This function iterates through the tree’s nodes to find a leaf node that matches the given label. If a matching leaf is found, it is returned, otherwise the function returns None.

Arguments

• label - A reference to the string label of the leaf node to find.

Returns

An Option<Node> representing the found leaf node, if any.

pub fn double_tree_size(&mut self)

Doubles the size of the Merkle Tree.

This function adds as many new inactive nodes to the tree as it currently contains, effectively doubling its size. This is necessary when no inactive node is available for the insertion of a new node. Each new node is marked inactive and initialized with default values.

pub fn generate_proof_of_membership( &self, index: usize ) -> Result<MerkleProof, MerkleTreeError>

Generates a proof of membership for a node at a given index in the indexed Merkle Tree.

This function constructs a path of hashes leading from a specific node to the root of the tree, serving as a merkle proof of the node’s membership in the tree. If the index is invalid, it returns an error, because the node doesnt exist and cant be proved as a member.

Arguments

• index - The index of the node in the tree for which the proof is to be generated.

Returns

A Result<MerkleProof, MerkleTreeError> containing the membership proof or an error.

pub fn generate_non_membership_proof( &self, node: &Node ) -> Result<(MerkleProof, Option<usize>), MerkleTreeError>

Generates a non-membership proof for a given node in the indexed Merkle Tree.

This function verifies that a node is not part of the tree. It does so by finding a place in the tree where the given node should exist based on its label and proving it is not there. Suitable for scenarios where proving the absence of data is required, e.g. important for guaranteeing uniqueness.

Arguments

• node - A reference to the Node for which the non-membership proof is required.

Returns

A Result<(MerkleProof, Option<usize>), MerkleTreeError> containing the non-membership proof and the index of the “closest” valid node, or an error.

pub fn generate_update_proof( self, index: usize, new_node: Node ) -> Result<(UpdateProof, Self), MerkleTreeError>

Generates a proof of update for a node at a given index in the indexed Merkle Tree.

This function first generates a proof of membership for the old node state, updates the node, recalculates the root, and then generates a new proof of membership for the updated node. It returns both the old and new proofs along with the updated tree.

Arguments

• index - The index of the node to be updated.
• new_node - The new state of the node.

Returns

A Result<(UpdateProof, Self), MerkleTreeError> containing the the old root, the old proof, the new root and the new proof, the updated tree.

pub fn generate_proof_of_insert( &mut self, new_node: &Node ) -> Result<(MerkleProof, UpdateProof, UpdateProof), MerkleTreeError>

Generates proofs required for inserting a node into the indexed Merkle Tree.

This function starts with a non-membership check to ensure that the index (i.e. the label) does not yet exist in the tree and thus to determine the index of the node to be changed. It then generates two update proofs: one for updating the next pointer of the existing node, and another for the actual insertion of the new node, i.e. updating an inactive and therefore empty leaf node. If there are no more empty leaf nodes, the capacity in the tree is doubled.

Arguments

• new_node - The new node to be inserted.

Returns

A Result<(MerkleProof, UpdateProof, UpdateProof), MerkleTreeError> containing the non-membership proof and two update proofs.

pub fn verify_update_proof((old_proof, new_proof): &UpdateProof) -> bool

Verifies an update proof in the indexed Merkle Tree.

This function checks both the old and new “state” proofs of a node to ensure that the update operation has been performed correctly and the tree’s integrity is maintained.

Arguments

• old_proof - The proof of the node’s state before the update.
• new_proof - The proof of the node’s state after the update.

Returns

true if both proofs are valid, false otherwise.

pub fn verify_insert_proof( non_membership_proof: &MerkleProof, first_proof: &UpdateProof, second_proof: &UpdateProof ) -> bool

Verifies the proofs associated with a node insertion in the indexed Merkle Tree.

This function confirms the non-membership of the node before insertion, and then verifies the two update proofs representing the tree’s state changes due to the insertion. Essential for validating insert operations in the tree.

Arguments

• non_membership_proof - The proof of the node’s non-membership before insertion.
• first_proof - The first update proof (pointer update of existing (“closest”) node).
• second_proof - The second update proof (update of empty inactive node with new values).

Returns

true if all proofs are valid, false otherwise.

Trait Implementations

impl Clone for IndexedMerkleTree

fn clone(&self) -> IndexedMerkleTree

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'de> Deserialize<'de> for IndexedMerkleTree

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Serialize for IndexedMerkleTree

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.