pub enum Node {
Inner(InnerNode),
Leaf(LeafNode),
}Expand description
An enum representing the types of nodes in the indexed Merkle Tree.
This enum allows for the differentiation between inner and leaf nodes in the tree,
facilitating operations like traversal, insertion, and proof generation.
It encapsulates either an InnerNode or a LeafNode, depending on the node’s position
and role in the tree.
Variants:
Inner(InnerNode): An inner node of the tree, containing references to child nodes.Leaf(LeafNode): A leaf node, containing the actual data (hash of its metadata).
Variants§
Implementations§
Source§impl Node
impl Node
Sourcepub const HEAD: Hash
pub const HEAD: Hash
This constant represents the smallest possible value in the field Fp for the BLS12-381 curve.
In the context of a Merkle tree with 256-bit SHA-256 hash outputs, this value is used to designate the first element or a null value. This is because the smallest possible value that can be generated by SHA-256 is zero, which is also the smallest value in the field Fp for the BLS12-381 curve.
The value HEAD is used in the following ways:
- As the starting point or initial value in the Merkle tree.
- As a placeholder for empty or null nodes.
Sourcepub const TAIL: Hash
pub const TAIL: Hash
This constant represents the largest possible value in the field Fp for the BLS12-381 curve.
In the context of a Merkle tree with 256-bit SHA-256 hash outputs, this value is used to designate the last element. This is because we need to ensure that all values are within the field Fp for the BLS12-381 curve, and the largest possible value that we can use is just below the modulus.
The value TAIL is used in the following ways:
- As the next pointer from the largest label in the current Merkle tree.
- As the next pointer from inactive leaf nodes, effectively “pointing” to it.
The specific value of TAIL is:
0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000000
This ensures that no value in the Merkle tree exceeds the modulus, maintaining proper order and integrity within the BLS12-381 field.
Sourcepub fn new_leaf(is_left: bool, label: Hash, value: Hash, next: Hash) -> Self
pub fn new_leaf(is_left: bool, label: Hash, value: Hash, next: Hash) -> Self
Convenience method for creating a new leaf node.
See LeafNode::new for more information.
Sourcepub fn new_inner(left: Node, right: Node, index: usize) -> Self
pub fn new_inner(left: Node, right: Node, index: usize) -> Self
Convenience method for creating a new inner node.
See InnerNode::new for more information.
Sourcepub fn get_hash(&self) -> Hash
pub fn get_hash(&self) -> Hash
Returns the hash of the node.
This function returns the hash of either an inner node or a leaf node, depending on the node type.
Sourcepub fn is_left_sibling(&self) -> bool
pub fn is_left_sibling(&self) -> bool
Determines if the node is a left sibling.
This function checks whether the node (either inner or leaf) is a left sibling in its parent node’s context. This information is important in the tree’s traversal and structure maintenance, ensuring the correct positioning and integrity of the nodes.
Sourcepub fn is_active(&self) -> bool
pub fn is_active(&self) -> bool
Determines if the node is active.
For inner nodes, this function always returns true. For leaf nodes, it checks the active flag.
This method is important to understand the current state of a node within the tree,
especially for insert operations to recognize the need for capacity duplication of the tree if necessary.
Sourcepub fn get_next(&self) -> Hash
pub fn get_next(&self) -> Hash
Returns the next node identifier.
This function retrieves the next node identifier for a leaf node, or returns the TAIL identifier
if the node is not a leaf. This is useful for traversing linked lists of leaf nodes.
Sourcepub fn set_next(&mut self, next: Hash)
pub fn set_next(&mut self, next: Hash)
Sets the next node identifier.
This function sets the next node identifier for a leaf node. This is important for maintaining
the linked list structure of leaf nodes within the tree, enabling efficient traversal and modifications.
Sourcepub fn get_label(&self) -> Hash
pub fn get_label(&self) -> Hash
Returns the label of the node.
This function retrieves the label for a leaf node, or returns the EMPTY_HASH identifier
if the node is not a leaf. This is useful for accessing the label of leaf nodes within the tree,
which may represent some data or key associated with that node.
Sourcepub fn set_left_sibling_value(&mut self, is_left: bool)
pub fn set_left_sibling_value(&mut self, is_left: bool)
Sets the left sibling status of the node.
This function updates whether the node (inner or leaf) is considered a left sibling. This is crucial for maintaining the structural integrity of the tree, especially when nodes are inserted or reorganized.
Sourcepub fn add_left(&mut self, left: Arc<Self>)
pub fn add_left(&mut self, left: Arc<Self>)
Attaches a node as the left child of an inner node.
This function sets the provided node as the left child of the current inner node.
§Arguments
left- AnArc<Self>pointing to the node to be set as the left child.
Sourcepub fn add_right(&mut self, right: Arc<Self>)
pub fn add_right(&mut self, right: Arc<Self>)
Attaches a node as the right child of an inner node.
This function sets the provided node as the right child of the current inner node.
§Arguments
right- AnArc<Self>pointing to the node to be set as the right child.
Sourcepub fn update_next_pointer(existing_node: &mut Self, new_node: &Self)
pub fn update_next_pointer(existing_node: &mut Self, new_node: &Self)
Updates the ‘next’ pointer of a leaf node.
This function is used to update the reference to the next node in the indexed Merkle Tree.
§Arguments
existing_node- The leaf node to update.new_node- The new node whose label will be used for the ‘next’ pointer.
Sourcepub fn generate_hash(&mut self)
pub fn generate_hash(&mut self)
Generates and updates the hash for the node.
@todo: Deprecate this function by creating proper constructors for the nodes
This function computes the hash of a node based on its type and properties. For an inner node, the hash is generated from the concatenated hashes of its left and right children in form of: SHA256(left_child_hash || right_child_hash) For a leaf node, the hash is based on its label, value, and the reference to the next node in the tree: SHA256(label || value || next)