Struct indexed_merkle_tree::tree::IndexedMerkleTree

source ·

pub struct IndexedMerkleTree {
    pub nodes: Vec<Node>,
}

Expand description

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.

Fields§

§nodes: Vec<Node>

Implementations§

source §

impl IndexedMerkleTree

source

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

Creates a new IndexedMerkleTree from a given nodes vector.

§Arguments

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

§Returns

A Result<Self, MerkleTreeError> representing the initialized tree or an error.

source

pub fn new_with_size(size: usize) -> Result<Self, MerkleTreeError>

Creates a new IndexedMerkleTree of a given size

§Arguments

size - The number of nodes in the tree.

§Returns

A Result<Self, MerkleTreeError> representing the initialized tree or an error.

source

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

§Returns

The current root node of the Indexed Merkle tree.

source

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

§Returns

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

source

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.

source

pub fn find_leaf_by_label(&self, label: &Hash) -> 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.

source

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.

source

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

Generates a membership proof 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.

source

pub fn generate_non_membership_proof( &self, node: &Node, ) -> Result<NonMembershipProof, 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<NonMembershipProof, MerkleTreeError> containing the non-membership proof and the index of the “closest” valid node, or an error.

source

pub fn update_node( &mut self, index: usize, new_node: Node, ) -> Result<UpdateProof, MerkleTreeError>

Updates the node with the given index in the merkle tree, returning the update proof.

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, MerkleTreeError> containing the the old root, the old proof, the new root and the new proof.

source

pub fn insert_node( &mut self, new_node: &mut Node, ) -> Result<InsertProof, MerkleTreeError>

Inserts a node into the merkle tree, returning the insertion proof.

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.