From 481e019242fa6d487b56c7d6832bd6bea8fc7321 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Mon, 16 Jun 2025 14:08:30 +0200 Subject: Use enumeration for left/right siblings --- src/node.rs | 22 +++++++++++----------- src/proof.rs | 54 ++++++++++++++++++++++++++++++++---------------------- 2 files changed, 43 insertions(+), 33 deletions(-) (limited to 'src') diff --git a/src/node.rs b/src/node.rs index 0bd0549..90481d0 100644 --- a/src/node.rs +++ b/src/node.rs @@ -2,27 +2,27 @@ /// Enum representing the type of a Merkle tree node. #[derive(Clone)] -pub enum NodeType { +pub enum NodeStatus { /// A leaf node that contains no children. Leaf, /// An internal node that has two children. Internal(Box, Box), } -impl NodeType { +impl NodeStatus { /// Returns a reference to the left child if the node is internal. pub fn left(&self) -> Option<&Node> { match self { - NodeType::Leaf => None, - NodeType::Internal(l, _) => Some(l), + NodeStatus::Leaf => None, + NodeStatus::Internal(l, _) => Some(l), } } /// Returns a reference to the right child if the node is internal. pub fn right(&self) -> Option<&Node> { match self { - NodeType::Leaf => None, - NodeType::Internal(_, r) => Some(r), + NodeStatus::Leaf => None, + NodeStatus::Internal(_, r) => Some(r), } } } @@ -33,7 +33,7 @@ pub struct Node { /// Hash value stored at the node. hash: String, /// Type of the node: leaf or internal. - kind: NodeType, + status: NodeStatus, /// Data in bytes. data: Vec, } @@ -49,7 +49,7 @@ impl Node { Self { hash, data: data.to_vec(), - kind: NodeType::Leaf, + status: NodeStatus::Leaf, } } @@ -68,7 +68,7 @@ impl Node { Self { hash, data: data.to_vec(), - kind: NodeType::Internal(Box::new(left), Box::new(right)), + status: NodeStatus::Internal(Box::new(left), Box::new(right)), } } @@ -83,7 +83,7 @@ impl Node { } /// Returns a reference to the node's type (leaf or internal). - pub fn kind(&self) -> &NodeType { - &self.kind + pub fn status(&self) -> &NodeStatus { + &self.status } } diff --git a/src/proof.rs b/src/proof.rs index 82f4a77..8f338d7 100644 --- a/src/proof.rs +++ b/src/proof.rs @@ -2,21 +2,30 @@ use crate::{hasher::Hasher, node::Node}; -/// Represents a single step in a Merkle proof path +/// Enum representing the type of the node child. +#[derive(Debug, Clone)] +pub enum NodeChildType { + /// Left child + Left, + /// Right child + Right, +} + +/// Represents a single step in a Merkle proof path. #[derive(Debug, Clone)] pub struct ProofNode { - /// The hash value of the sibling node + /// The hash value of the sibling node. pub hash: String, - /// Whether this sibling is on the left (true) or right (false) side - pub is_left: bool, + /// Whether this sibling is left or right + pub child_type: NodeChildType, } -/// A Merkle proof containing the path from a leaf to the root +/// A Merkle proof containing the path from a leaf to the root. #[derive(Debug)] pub struct MerkleProof { - /// The sequence of sibling hashes needed to reconstruct the path to root + /// The sequence of sibling hashes needed to reconstruct the path to root. pub path: Vec, - /// The index of the leaf node this proof corresponds to + /// The index of the leaf node this proof corresponds. pub leaf_index: usize, } @@ -25,14 +34,14 @@ pub trait Proofer { /// /// # Arguments /// - /// * `index` - The index of the leaf node to generate a proof for + /// * `index` - The index of the leaf node to generate a proof. /// /// # Returns /// - /// `Some(MerkleProof)` if the index is valid, `None` otherwise + /// `Some(MerkleProof)` if the index is valid, `None` otherwise. fn generate(&self, index: usize) -> Option; - /// Verifies that a piece of data exists in the tree using a Merkle proof/ + /// Verifies that a piece of data exists in the tree using a Merkle proof. /// /// # Arguments /// @@ -43,7 +52,7 @@ pub trait Proofer { /// /// # Returns /// - /// `true` if the proof is valid and the data exists in the tree, `false` otherwise + /// `true` if the proof is valid and the data exists in the tree, `false` otherwise. fn verify(&self, proof: &MerkleProof, data: T, root_hash: &str, hasher: &dyn Hasher) -> bool where T: AsRef<[u8]>; @@ -55,7 +64,7 @@ pub struct DefaultProofer { } impl DefaultProofer { - pub fn new(hasher: T, leaves: Vec) -> Self { + pub fn new(hasher: H, leaves: Vec) -> Self { Self { hasher: Box::new(hasher), leaves, @@ -87,10 +96,15 @@ impl Proofer for DefaultProofer { current_index - 1 // Left sibling }; - let is_left = sibling_index < current_index; + let child_type = if sibling_index < current_index { + NodeChildType::Left + } else { + NodeChildType::Right + }; + path.push(ProofNode { hash: current_level[sibling_index].hash().to_string(), - is_left, + child_type, }); // Move to the next level @@ -123,15 +137,11 @@ impl Proofer for DefaultProofer { // Walk up the tree using the proof path for proof_node in &proof.path { - current_hash = if proof_node.is_left { - // Sibling is on the left, current node is on the right - let combined = format!("{}{}", proof_node.hash, current_hash); - hasher.hash(combined.as_bytes()) - } else { - // Sibling is on the right, current node is on the left - let combined = format!("{}{}", current_hash, proof_node.hash,); - hasher.hash(combined.as_bytes()) + let combined: String = match proof_node.child_type { + NodeChildType::Left => format!("{}{}", proof_node.hash, current_hash), + NodeChildType::Right => format!("{}{}", current_hash, proof_node.hash), }; + current_hash = hasher.hash(combined.as_bytes()); } // Check if the computed root matches the expected root -- cgit v1.2.3-71-g8e6c