Enum indexed_merkle_tree::node::Node

pub enum Node {
    Inner(InnerNode),
    Leaf(LeafNode),
}

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

Inner(InnerNode)

Leaf(LeafNode)

Implementations

impl Node

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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 - An Arc<Self> pointing to the node to be set as the left child.

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 - An Arc<Self> pointing to the node to be set as the right child.

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.

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 active status, label, value, and the reference to the next node in the tree: SHA256(active || label || value || next)

Trait Implementations

impl Clone for Node

fn clone(&self) -> Node

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Node

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

Formats the value using the given formatter.

impl Default for Node

fn default() -> Self

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for Node

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl PartialEq for Node

fn eq(&self, other: &Node) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for Node

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

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for Node

impl StructuralPartialEq for Node