indexed_merkle_tree/
node.rs

1use serde::{Deserialize, Serialize};
2
3#[cfg(not(feature = "std"))]
4extern crate alloc;
5
6#[cfg(not(feature = "std"))]
7use alloc::sync::Arc;
8#[cfg(feature = "std")]
9use std::sync::Arc;
10
11use crate::{sha256_mod, Hash};
12
13/// Represents an inner node in the indexed Merkle Tree.
14///
15/// This structure is used for non-leaf nodes in the tree, containing references to its
16/// left and right children along with its own hash value. There is no difference between
17/// inner nodes of an indexed Merkle Tree and a classic Merkle Tree.
18///
19/// Fields:
20/// - `hash`: The hash of the current node, derived from its children.
21/// - `is_left_sibling`: Indicates whether this node is a left child of its parent.
22/// - `left`: A reference-counted pointer to the left child node.
23/// - `right`: A reference-counted pointer to the right child node.
24#[derive(Serialize, Deserialize, Debug, Clone, PartialEq, Eq)]
25pub struct InnerNode {
26    pub hash: Hash,
27    pub is_left_sibling: bool,
28    pub left: Arc<Node>,
29    pub right: Arc<Node>,
30}
31
32impl InnerNode {
33    /// Creates a new inner node.
34    ///
35    /// This function generates an inner node from two child nodes (left and right) and an index.
36    /// The index determines the new node's left sibling status. The hash for the inner node is
37    /// calculated based on its children. This is crucial for constructing the tree and updating its structure.
38    ///
39    /// # Arguments
40    /// * `left` - The left child node.
41    /// * `right` - The right child node.
42    /// * `index` - The position index of the new node in the tree.
43    ///
44    /// # Returns
45    /// An `InnerNode` representing the newly created inner node.
46    pub fn new(left: Node, right: Node, index: usize) -> Self {
47        // we need to use the .as_ref() method to convert the Hash to a slice of bytes ([u8])
48        let hash = sha256_mod(&[left.get_hash().as_ref(), right.get_hash().as_ref()].concat());
49        InnerNode {
50            hash,
51            is_left_sibling: index % 2 == 0,
52            left: Arc::new(left),
53            right: Arc::new(right),
54        }
55    }
56}
57
58/// Represents a leaf node in the indexed Merkle Tree.
59///
60/// Leaf nodes contain the actual data stored in the tree structure as well as metadata that,
61/// among other things, ensures the integrity and order of the tree structure.
62/// Each leaf node contains a hash of its metadata consisting of a SHA256 value,
63/// a link to neighboring elements for efficient traversal and verification.
64/// The links lead to the label field which is also a SHA256 value, making it sortable, which is crucial for e.g. Non-Membership proofs.
65/// For more information see https://eprint.iacr.org/2021/1263.pdf.
66///
67/// Fields:
68/// - `hash`: The hash of the values below, expect of the is_left_sibling-value.
69/// - `is_left_sibling`: Indicates if this node is a left child in its parent node.
70/// - `value`: The actual data value stored in the node.
71/// - `label`: A unique identifier for the node. This is used to sort by size and to link nodes together.
72/// - `next`: A reference to the next node in the tree.
73#[derive(Serialize, Deserialize, Debug, Clone, PartialEq, Eq)]
74pub struct LeafNode {
75    pub hash: Hash,
76    pub is_left_sibling: bool,
77    pub value: Hash,
78    pub label: Hash,
79    pub next: Hash,
80}
81
82impl LeafNode {
83    /// Initializes a new leaf node with the specified properties.
84    ///
85    /// This function creates a leaf node with above defined attributes. The hash is generated based on
86    /// its label, value, and next pointer. Additionally, the node is marked as a left sibling or not.
87    ///
88    /// # Arguments
89    /// * `is_left` - Boolean indicating if this is a left sibling.
90    /// * `label` - Unique 256 bit identifier for the leaf.
91    /// * `value` - 256 Bit data value of the leaf.
92    /// * `next` - Reference to the next largest node (identified by the label value) in the sequence.
93    ///
94    /// # Returns
95    /// * A new leaf node with the specified properties.
96    pub fn new(is_left: bool, label: Hash, value: Hash, next: Hash) -> Self {
97        let hash = sha256_mod(&[label.as_ref(), value.as_ref(), next.as_ref()].concat());
98        LeafNode {
99            hash,
100            is_left_sibling: is_left,
101            value,
102            label,
103            next,
104        }
105    }
106
107    pub fn is_active(&self) -> bool {
108        self.next != Node::HEAD
109    }
110}
111
112impl Default for LeafNode {
113    fn default() -> Self {
114        LeafNode::new(false, Node::HEAD, Node::HEAD, Node::HEAD)
115    }
116}
117
118/// An enum representing the types of nodes in the indexed Merkle Tree.
119///
120/// This enum allows for the differentiation between inner and leaf nodes in the tree,
121/// facilitating operations like traversal, insertion, and proof generation.
122/// It encapsulates either an `InnerNode` or a `LeafNode`, depending on the node's position
123/// and role in the tree.
124///
125/// Variants:
126/// - `Inner(InnerNode)`: An inner node of the tree, containing references to child nodes.
127/// - `Leaf(LeafNode)`: A leaf node, containing the actual data (hash of its metadata).
128#[derive(Serialize, Deserialize, Debug, Clone, PartialEq, Eq)]
129pub enum Node {
130    Inner(InnerNode),
131    Leaf(LeafNode),
132}
133
134impl Default for Node {
135    fn default() -> Self {
136        Node::Leaf(LeafNode::default())
137    }
138}
139
140impl Node {
141    /// This constant represents the smallest possible value in the field Fp for the BLS12-381 curve.
142    ///
143    /// In the context of a Merkle tree with 256-bit SHA-256 hash outputs, this value is used to designate
144    /// the first element or a null value. This is because the smallest possible value that can be generated
145    /// by SHA-256 is zero, which is also the smallest value in the field Fp for the BLS12-381 curve.
146    ///
147    /// The value `HEAD` is used in the following ways:
148    /// - As the starting point or initial value in the Merkle tree.
149    /// - As a placeholder for empty or null nodes.
150    pub const HEAD: Hash = Hash::new([0; 32]);
151
152    /// This constant represents the largest possible value in the field Fp for the BLS12-381 curve.
153    ///
154    /// In the context of a Merkle tree with 256-bit SHA-256 hash outputs, this value is used to designate
155    /// the last element. This is because we need to ensure that all values are within the field Fp for the
156    /// BLS12-381 curve, and the largest possible value that we can use is just below the modulus.
157    ///
158    /// The value `TAIL` is used in the following ways:
159    /// - As the next pointer from the largest label in the current Merkle tree.
160    /// - As the next pointer from inactive leaf nodes, effectively "pointing" to it.
161    ///
162    /// The specific value of `TAIL` is:
163    ///
164    /// 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000000
165    ///
166    /// This ensures that no value in the Merkle tree exceeds the modulus, maintaining proper order
167    /// and integrity within the BLS12-381 field.
168    pub const TAIL: Hash = Hash::new([
169        0x73, 0xed, 0xa7, 0x53, 0x29, 0x9d, 0x7d, 0x48, 0x33, 0x39, 0xd8, 0x08, 0x09, 0xa1, 0xd8,
170        0x05, 0x53, 0xbd, 0xa4, 0x02, 0xff, 0xfe, 0x5b, 0xfe, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00,
171        0x00, 0x00,
172    ]);
173
174    /// Convenience method for creating a new leaf node.
175    /// See `LeafNode::new` for more information.
176    pub fn new_leaf(is_left: bool, label: Hash, value: Hash, next: Hash) -> Self {
177        Node::Leaf(LeafNode::new(is_left, label, value, next))
178    }
179
180    /// Convenience method for creating a new inner node.
181    /// See `InnerNode::new` for more information.
182    pub fn new_inner(left: Node, right: Node, index: usize) -> Self {
183        Node::Inner(InnerNode::new(left, right, index))
184    }
185
186    /// Returns the hash of the node.
187    ///
188    /// This function returns the hash of either an inner node or a leaf node, depending on the node type.
189    pub fn get_hash(&self) -> Hash {
190        match self {
191            Node::Inner(inner_node) => inner_node.hash,
192            Node::Leaf(leaf) => leaf.hash,
193        }
194    }
195
196    /// Determines if the node is a left sibling.
197    ///
198    /// This function checks whether the node (either inner or leaf) is a left sibling
199    /// in its parent node's context. This information is important in the tree's traversal
200    /// and structure maintenance, ensuring the correct positioning and integrity of the nodes.
201    pub fn is_left_sibling(&self) -> bool {
202        match self {
203            Node::Inner(inner_node) => inner_node.is_left_sibling,
204            Node::Leaf(leaf) => leaf.is_left_sibling,
205        }
206    }
207
208    /// Determines if the node is active.
209    ///
210    /// For inner nodes, this function always returns true. For leaf nodes, it checks the `active` flag.
211    /// This method is important to understand the current state of a node within the tree,
212    /// especially for insert operations to recognize the need for capacity duplication of the tree if necessary.
213    pub fn is_active(&self) -> bool {
214        match self {
215            Node::Inner(_) => true,
216            Node::Leaf(leaf) => leaf.is_active(),
217        }
218    }
219
220    /// Returns the `next` node identifier.
221    ///
222    /// This function retrieves the `next` node identifier for a leaf node, or returns the `TAIL` identifier
223    /// if the node is not a leaf. This is useful for traversing linked lists of leaf nodes.
224    pub fn get_next(&self) -> Hash {
225        match self {
226            Node::Leaf(leaf) => leaf.next,
227            _ => Node::TAIL,
228        }
229    }
230
231    /// Sets the `next` node identifier.
232    ///
233    /// This function sets the `next` node identifier for a leaf node. This is important for maintaining
234    /// the linked list structure of leaf nodes within the tree, enabling efficient traversal and modifications.
235    pub fn set_next(&mut self, next: Hash) {
236        if let Node::Leaf(leaf) = self {
237            leaf.next = next;
238        }
239    }
240
241    /// Returns the `label` of the node.
242    ///
243    /// This function retrieves the `label` for a leaf node, or returns the `EMPTY_HASH` identifier
244    /// if the node is not a leaf. This is useful for accessing the label of leaf nodes within the tree,
245    /// which may represent some data or key associated with that node.
246    pub fn get_label(&self) -> Hash {
247        match self {
248            Node::Leaf(leaf) => leaf.label,
249            _ => Node::HEAD,
250        }
251    }
252
253    /// Sets the left sibling status of the node.
254    ///
255    /// This function updates whether the node (inner or leaf) is considered a left sibling.
256    /// This is crucial for maintaining the structural integrity of the tree, especially when nodes
257    /// are inserted or reorganized.
258    pub fn set_left_sibling_value(&mut self, is_left: bool) {
259        match self {
260            Node::Inner(inner_node) => inner_node.is_left_sibling = is_left,
261            Node::Leaf(leaf) => leaf.is_left_sibling = is_left,
262        }
263    }
264
265    /// Attaches a node as the left child of an inner node.
266    ///
267    /// This function sets the provided node as the left child of the current inner node.
268    ///
269    /// # Arguments
270    /// * `left` - An `Arc<Self>` pointing to the node to be set as the left child.
271    pub fn add_left(&mut self, left: Arc<Self>) {
272        if let Node::Inner(inner) = self {
273            inner.left = left;
274        }
275    }
276
277    /// Attaches a node as the right child of an inner node.
278    ///
279    /// This function sets the provided node as the right child of the current inner node.
280    ///
281    /// # Arguments
282    /// * `right` - An `Arc<Self>` pointing to the node to be set as the right child.
283    pub fn add_right(&mut self, right: Arc<Self>) {
284        if let Node::Inner(inner) = self {
285            inner.right = right;
286        }
287    }
288
289    /// Updates the 'next' pointer of a leaf node.
290    ///
291    /// This function is used to update the reference to the next node in the indexed Merkle Tree.
292    ///
293    /// # Arguments
294    /// * `existing_node` - The leaf node to update.
295    /// * `new_node` - The new node whose label will be used for the 'next' pointer.
296    pub fn update_next_pointer(existing_node: &mut Self, new_node: &Self) {
297        if let Self::Leaf(ref mut existing_leaf) = existing_node {
298            if let Self::Leaf(new_leaf) = new_node {
299                existing_leaf.next = new_leaf.label;
300            }
301        }
302    }
303
304    /// Generates and updates the hash for the node.
305    ///
306    /// @todo: Deprecate this function by creating proper constructors for the nodes
307    ///
308    /// This function computes the hash of a node based on its type and properties.
309    /// For an inner node, the hash is generated from the concatenated hashes of its left and right children in form of:
310    ///     SHA256(left_child_hash || right_child_hash)
311    /// For a leaf node, the hash is based on its label, value, and the reference to the next node in the tree:
312    ///     SHA256(label || value || next)
313    pub fn generate_hash(&mut self) {
314        match self {
315            Node::Inner(node) => {
316                let hash = sha256_mod(
317                    &[
318                        node.left.get_hash().as_ref(),
319                        node.right.get_hash().as_ref(),
320                    ]
321                    .concat(),
322                );
323                node.hash = hash;
324            }
325            Node::Leaf(leaf) => {
326                let hash = sha256_mod(
327                    &[leaf.label.as_ref(), leaf.value.as_ref(), leaf.next.as_ref()].concat(),
328                );
329                leaf.hash = hash;
330            }
331        }
332    }
333}
334
335#[cfg(test)]
336mod tests {
337    use super::*;
338
339    #[test]
340    fn test_leaf_node_creation() {
341        let label = Hash::new([1; 32]);
342        let value = Hash::new([2; 32]);
343        let next = Hash::new([3; 32]);
344        let leaf = LeafNode::new(true, label, value, next);
345
346        assert!(leaf.is_active());
347        assert!(leaf.is_left_sibling);
348        assert_eq!(leaf.label, label);
349        assert_eq!(leaf.value, value);
350        assert_eq!(leaf.next, next);
351    }
352
353    #[test]
354    fn test_inner_node_creation() {
355        let left = Node::new_leaf(
356            true,
357            Hash::new([1; 32]),
358            Hash::new([2; 32]),
359            Hash::new([3; 32]),
360        );
361        let right = Node::new_leaf(
362            false,
363            Hash::new([4; 32]),
364            Hash::new([5; 32]),
365            Hash::new([6; 32]),
366        );
367        let inner = Node::new_inner(left.clone(), right.clone(), 0);
368
369        if let Node::Inner(inner_node) = inner {
370            assert!(inner_node.is_left_sibling);
371            assert_eq!(*inner_node.left, left);
372            assert_eq!(*inner_node.right, right);
373        } else {
374            panic!("Expected Inner node");
375        }
376    }
377
378    #[test]
379    fn test_node_is_active() {
380        let active_leaf = Node::new_leaf(
381            true,
382            Hash::new([1; 32]),
383            Hash::new([2; 32]),
384            Hash::new([3; 32]),
385        );
386        let inactive_leaf = Node::new_leaf(true, Node::HEAD, Node::HEAD, Node::HEAD);
387        let inner_node = Node::new_inner(active_leaf.clone(), inactive_leaf.clone(), 0);
388
389        assert!(active_leaf.is_active());
390        assert!(!inactive_leaf.is_active());
391        assert!(inner_node.is_active());
392    }
393
394    #[test]
395    fn test_node_get_next() {
396        let leaf = Node::new_leaf(
397            true,
398            Hash::new([1; 32]),
399            Hash::new([2; 32]),
400            Hash::new([3; 32]),
401        );
402        let inner = Node::new_inner(leaf.clone(), leaf.clone(), 0);
403
404        assert_eq!(leaf.get_next(), Hash::new([3; 32]));
405        assert_eq!(inner.get_next(), Node::TAIL);
406    }
407
408    #[test]
409    fn test_node_set_next() {
410        let mut leaf = Node::new_leaf(
411            true,
412            Hash::new([1; 32]),
413            Hash::new([2; 32]),
414            Hash::new([3; 32]),
415        );
416        let new_next = Hash::new([4; 32]);
417        leaf.set_next(new_next);
418
419        if let Node::Leaf(leaf_node) = leaf {
420            assert_eq!(leaf_node.next, new_next);
421        } else {
422            panic!("Expected Leaf node");
423        }
424    }
425
426    #[test]
427    fn test_node_update_next_pointer() {
428        let mut existing_node = Node::new_leaf(
429            true,
430            Hash::new([1; 32]),
431            Hash::new([2; 32]),
432            Hash::new([3; 32]),
433        );
434        let new_node = Node::new_leaf(
435            false,
436            Hash::new([4; 32]),
437            Hash::new([5; 32]),
438            Hash::new([6; 32]),
439        );
440
441        Node::update_next_pointer(&mut existing_node, &new_node);
442
443        if let Node::Leaf(leaf_node) = existing_node {
444            assert_eq!(leaf_node.next, Hash::new([4; 32]));
445        } else {
446            panic!("Expected Leaf node");
447        }
448    }
449
450    #[test]
451    fn test_node_generate_hash() {
452        let mut leaf = Node::new_leaf(
453            true,
454            Hash::new([1; 32]),
455            Hash::new([2; 32]),
456            Hash::new([3; 32]),
457        );
458        let original_hash = leaf.get_hash();
459
460        if let Node::Leaf(ref mut leaf_node) = leaf {
461            leaf_node.value = Hash::new([4; 32]);
462        }
463
464        leaf.generate_hash();
465        let new_hash = leaf.get_hash();
466
467        assert_ne!(original_hash, new_hash);
468    }
469}