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}