From c4eeb0db2219e63801ce566b7724e849c74e0fed Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Mon, 16 Jun 2025 11:49:45 +0200 Subject: Remove `src/merkle` folder --- src/lib.rs | 3 +- src/merkle/merkletree.rs | 111 ------------------------------ src/merkle/mod.rs | 69 ------------------- src/merkle/node.rs | 96 -------------------------- src/merkletree.rs | 174 +++++++++++++++++++++++++++++++++++++++++++++++ src/node.rs | 96 ++++++++++++++++++++++++++ 6 files changed, 272 insertions(+), 277 deletions(-) delete mode 100644 src/merkle/merkletree.rs delete mode 100644 src/merkle/mod.rs delete mode 100644 src/merkle/node.rs create mode 100644 src/merkletree.rs create mode 100644 src/node.rs (limited to 'src') diff --git a/src/lib.rs b/src/lib.rs index 58e328b..e71c875 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -2,4 +2,5 @@ //! with pluggable hash functions. pub mod hasher; -pub mod merkle; +pub mod merkletree; +pub mod node; diff --git a/src/merkle/merkletree.rs b/src/merkle/merkletree.rs deleted file mode 100644 index 4a6a214..0000000 --- a/src/merkle/merkletree.rs +++ /dev/null @@ -1,111 +0,0 @@ -//! Provides the MerkleTree structure and associated methods for creating and interacting -//! with binary Merkle trees using custom hashers. - -use crate::{hasher::Hasher, merkle::node::Node}; - -/// A binary Merkle tree implementation. -/// -/// Merkle trees are hash-based data structures used for secure and efficient data verification. -/// Each leaf node contains the hash of a data item, and each internal node contains the hash -/// of the concatenation of its children's hashes. -#[derive(Debug)] -pub struct MerkleTree { - /// Leaf nodes at the base of the tree (may include a duplicate for even pairing). - leaves: Vec, - /// Height of the tree (number of levels including root). - height: usize, - /// Root node of the Merkle tree. - root: Node, -} - -impl MerkleTree { - /// Creates a new `MerkleTree` from a collection of data items and a hash function. - /// - /// # Arguments - /// - /// * `hasher` - A reference to an implementation of the `Hasher` trait. - /// * `data` - A vector of values to be converted into leaf nodes. - /// - /// # Panics - /// - /// Panics if the `data` vector is empty. - /// - /// # Notes - /// - /// If the number of leaf nodes is odd, the last node is duplicated to ensure all internal - /// nodes have exactly two children. - pub fn new(hasher: &dyn Hasher, data: I) -> Self - where - I: IntoIterator, - T: AsRef<[u8]>, - { - let owned_data: Vec = data.into_iter().collect(); - let data_slices: Vec<&[u8]> = owned_data.iter().map(|item| item.as_ref()).collect(); - - assert!( - !data_slices.is_empty(), - "Merkle Tree requires at least one element" - ); - - let mut leaves: Vec = data_slices - .iter() - .map(|x| Node::new_leaf(hasher, x)) - .collect(); - - if leaves.len() % 2 != 0 { - leaves.push(leaves[leaves.len() - 1].clone()); - } - - Self::build(hasher, leaves) - } - - /// Constructs the internal nodes of the tree from the leaves upward and computes the root. - fn build(hasher: &dyn Hasher, mut nodes: Vec) -> Self { - let leaves = nodes.clone(); - let mut height = 0; - - while nodes.len() > 1 { - if nodes.len() % 2 != 0 { - // duplicate last node to make the count even - nodes.push(nodes[nodes.len() - 1].clone()); - } - - let mut next_level = Vec::new(); - for pair in nodes.chunks(2) { - let (left, right) = (pair[0].clone(), pair[1].clone()); - - next_level.push(Node::new_internal(hasher, left, right)); - } - nodes = next_level; - height += 1; - } - - let root = nodes.remove(0); - - MerkleTree { - leaves, - height: height + 1, - root, - } - } - - /// Returns the height (number of levels) of the tree. - pub fn height(&self) -> usize { - self.height - } - - /// Returns true if the tree has no leaves (should never happen if `new()` was used). - pub fn is_empty(&self) -> bool { - self.len() == 0 - } - - /// Returns the number of leaf nodes in the tree. - pub fn len(&self) -> usize { - self.leaves.len() - } - - /// Returns the root node of the tree. - pub fn root(&self) -> Node { - self.root.clone() - } -} diff --git a/src/merkle/mod.rs b/src/merkle/mod.rs deleted file mode 100644 index 2ce316c..0000000 --- a/src/merkle/mod.rs +++ /dev/null @@ -1,69 +0,0 @@ -//! High-level module for Merkle tree functionality. -//! -//! Re-exports the Merkle tree and node modules for external use. - -pub mod merkletree; -pub mod node; - -#[cfg(test)] -mod tests { - use crate::hasher::*; - - use super::*; - - #[test] - fn test_merkle_tree_with_default_hasher() { - let data = &["hello".as_bytes(), "world".as_bytes()]; - let tree = merkletree::MerkleTree::new(&DummyHasher, data); - - assert_eq!(tree.height(), 2); - assert_eq!(tree.root().hash(), "0xc0ff3"); - } - - #[test] - #[cfg(feature = "sha256")] - fn test_merkle_tree_hashing() { - let data = &["hello".as_bytes(), "world".as_bytes()]; - let tree = merkletree::MerkleTree::new(&SHA256Hasher, data); - - assert_eq!(tree.height(), 2); - assert_eq!( - tree.root().hash(), - "15e178b71fae8849ee562c9cc0d7ea322fba6cd495411329d47234479167cc8b" - ); - } - - #[test] - #[cfg(feature = "sha256")] - fn test_merkle_tree_single_leaf() { - let data = &["hello".as_bytes()]; - let tree = merkletree::MerkleTree::new(&SHA256Hasher, data); - - assert_eq!(tree.height(), 2); - assert_eq!(tree.len(), 2); - assert_eq!( - tree.root().hash(), - "286d189fda11bf4e906b6973a173009f47ede16532f1bae726223f8ee155d73b" - ); - } - - #[test] - #[cfg(feature = "sha256")] - fn test_merkle_tree_with_10_elements() { - let inputs = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]; - let data: Vec<&[u8]> = inputs.iter().map(|s| s.as_bytes()).collect(); - - let tree = merkletree::MerkleTree::new(&SHA256Hasher, &data); - - assert_eq!(tree.height(), 5); // 10 elements padded to 16 → log2(16) + 1 = 5 - - // You can print the root hash if you're unsure what it should be: - println!("Merkle root hash: {}", tree.root().hash()); - - // If you know the expected hash, use: - assert_eq!( - tree.root().hash(), - "9da1ff0dfa79217bdbea9ec96407b1e693646cc493f64059fa27182a37cadf94" - ); - } -} diff --git a/src/merkle/node.rs b/src/merkle/node.rs deleted file mode 100644 index cef5c1f..0000000 --- a/src/merkle/node.rs +++ /dev/null @@ -1,96 +0,0 @@ -//! Contains node definitions for Merkle trees, including leaf and internal node structures. - -use crate::hasher::Hasher; - -/// Enum representing the type of a Merkle tree node. -#[derive(Debug, Clone)] -pub enum NodeType { - /// A leaf node that contains no children. - Leaf, - /// An internal node that has two children. - Internal(Box, Box), -} - -impl NodeType { - /// 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), - } - } - - /// 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), - } - } -} - -/// Represents a node in a Merkle tree, either leaf or internal. -#[derive(Debug, Clone)] -pub struct Node { - /// Hash value stored at the node. - hash: String, - /// Type of the node: leaf or internal. - kind: NodeType, - /// Data in bytes. - data: Vec, -} - -impl Node { - /// Constructs a new leaf node from input data. - /// - /// # Arguments - /// - /// * `hasher` - A reference to a hashing strategy. - /// * `data` - The data to be hashed and stored as a leaf. - pub fn new_leaf(hasher: &dyn Hasher, data: &[u8]) -> Self { - let hash = hasher.hash(data); - Self { - hash, - data: data.to_vec(), - kind: NodeType::Leaf, - } - } - - /// Constructs a new internal node from two child nodes. - /// - /// # Arguments - /// - /// * `hasher` - A reference to a hashing strategy. - /// * `left` - Left child node. - /// * `right` - Right child node. - /// - /// # Behavior - /// - /// The internal node hash is computed as the hash of the concatenated children's hashes. - pub fn new_internal(hasher: &dyn Hasher, left: Node, right: Node) -> Self { - let mut buffer = Vec::::new(); - buffer.extend_from_slice(left.hash().as_bytes()); - buffer.extend_from_slice(right.hash().as_bytes()); - let hash = hasher.hash(&buffer); - Self { - hash, - data: buffer, - kind: NodeType::Internal(Box::new(left), Box::new(right)), - } - } - - /// Returns a reference to the hash of the node. - pub fn hash(&self) -> &str { - &self.hash - } - - /// Returns the data value in bytes format. - pub fn data(&self) -> &[u8] { - &self.data - } - - /// Returns a reference to the node's type (leaf or internal). - pub fn kind(&self) -> &NodeType { - &self.kind - } -} diff --git a/src/merkletree.rs b/src/merkletree.rs new file mode 100644 index 0000000..6173c2f --- /dev/null +++ b/src/merkletree.rs @@ -0,0 +1,174 @@ +//! Provides the MerkleTree structure and associated methods for creating and interacting +//! with binary Merkle trees using custom hashers. + +use crate::{hasher::Hasher, node::Node}; + +/// A binary Merkle tree implementation. +/// +/// Merkle trees are hash-based data structures used for secure and efficient data verification. +/// Each leaf node contains the hash of a data item, and each internal node contains the hash +/// of the concatenation of its children's hashes. +#[derive(Debug)] +pub struct MerkleTree { + /// Leaf nodes at the base of the tree (may include a duplicate for even pairing). + leaves: Vec, + /// Height of the tree (number of levels including root). + height: usize, + /// Root node of the Merkle tree. + root: Node, +} + +impl MerkleTree { + /// Creates a new `MerkleTree` from a collection of data items and a hash function. + /// + /// # Arguments + /// + /// * `hasher` - A reference to an implementation of the `Hasher` trait. + /// * `data` - A vector of values to be converted into leaf nodes. + /// + /// # Panics + /// + /// Panics if the `data` vector is empty. + /// + /// # Notes + /// + /// If the number of leaf nodes is odd, the last node is duplicated to ensure all internal + /// nodes have exactly two children. + pub fn new(hasher: &dyn Hasher, data: I) -> Self + where + I: IntoIterator, + T: AsRef<[u8]>, + { + let owned_data: Vec = data.into_iter().collect(); + let data_slices: Vec<&[u8]> = owned_data.iter().map(|item| item.as_ref()).collect(); + + assert!( + !data_slices.is_empty(), + "Merkle Tree requires at least one element" + ); + + let mut leaves: Vec = data_slices + .iter() + .map(|x| Node::new_leaf(hasher, x)) + .collect(); + + if leaves.len() % 2 != 0 { + leaves.push(leaves[leaves.len() - 1].clone()); + } + + Self::build(hasher, leaves) + } + + /// Constructs the internal nodes of the tree from the leaves upward and computes the root. + fn build(hasher: &dyn Hasher, mut nodes: Vec) -> Self { + let leaves = nodes.clone(); + let mut height = 0; + + while nodes.len() > 1 { + if nodes.len() % 2 != 0 { + // duplicate last node to make the count even + nodes.push(nodes[nodes.len() - 1].clone()); + } + + let mut next_level = Vec::new(); + for pair in nodes.chunks(2) { + let (left, right) = (pair[0].clone(), pair[1].clone()); + + next_level.push(Node::new_internal(hasher, left, right)); + } + nodes = next_level; + height += 1; + } + + let root = nodes.remove(0); + + MerkleTree { + leaves, + height: height + 1, + root, + } + } + + /// Returns the height (number of levels) of the tree. + pub fn height(&self) -> usize { + self.height + } + + /// Returns true if the tree has no leaves (should never happen if `new()` was used). + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Returns the number of leaf nodes in the tree. + pub fn len(&self) -> usize { + self.leaves.len() + } + + /// Returns the root node of the tree. + pub fn root(&self) -> Node { + self.root.clone() + } +} + +#[cfg(test)] +mod tests { + use crate::hasher::*; + + use super::*; + + #[test] + fn test_merkle_tree_with_default_hasher() { + let data = &["hello".as_bytes(), "world".as_bytes()]; + let tree = MerkleTree::new(&DummyHasher, data); + + assert_eq!(tree.height(), 2); + assert_eq!(tree.root().hash(), "0xc0ff3"); + } + + #[test] + #[cfg(feature = "sha256")] + fn test_merkle_tree_hashing() { + let data = &["hello".as_bytes(), "world".as_bytes()]; + let tree = MerkleTree::new(&SHA256Hasher, data); + + assert_eq!(tree.height(), 2); + assert_eq!( + tree.root().hash(), + "15e178b71fae8849ee562c9cc0d7ea322fba6cd495411329d47234479167cc8b" + ); + } + + #[test] + #[cfg(feature = "sha256")] + fn test_merkle_tree_single_leaf() { + let data = &["hello".as_bytes()]; + let tree = MerkleTree::new(&SHA256Hasher, data); + + assert_eq!(tree.height(), 2); + assert_eq!(tree.len(), 2); + assert_eq!( + tree.root().hash(), + "286d189fda11bf4e906b6973a173009f47ede16532f1bae726223f8ee155d73b" + ); + } + + #[test] + #[cfg(feature = "sha256")] + fn test_merkle_tree_with_10_elements() { + let inputs = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]; + let data: Vec<&[u8]> = inputs.iter().map(|s| s.as_bytes()).collect(); + + let tree = MerkleTree::new(&SHA256Hasher, &data); + + assert_eq!(tree.height(), 5); // 10 elements padded to 16 → log2(16) + 1 = 5 + + // You can print the root hash if you're unsure what it should be: + println!("Merkle root hash: {}", tree.root().hash()); + + // If you know the expected hash, use: + assert_eq!( + tree.root().hash(), + "9da1ff0dfa79217bdbea9ec96407b1e693646cc493f64059fa27182a37cadf94" + ); + } +} diff --git a/src/node.rs b/src/node.rs new file mode 100644 index 0000000..cef5c1f --- /dev/null +++ b/src/node.rs @@ -0,0 +1,96 @@ +//! Contains node definitions for Merkle trees, including leaf and internal node structures. + +use crate::hasher::Hasher; + +/// Enum representing the type of a Merkle tree node. +#[derive(Debug, Clone)] +pub enum NodeType { + /// A leaf node that contains no children. + Leaf, + /// An internal node that has two children. + Internal(Box, Box), +} + +impl NodeType { + /// 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), + } + } + + /// 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), + } + } +} + +/// Represents a node in a Merkle tree, either leaf or internal. +#[derive(Debug, Clone)] +pub struct Node { + /// Hash value stored at the node. + hash: String, + /// Type of the node: leaf or internal. + kind: NodeType, + /// Data in bytes. + data: Vec, +} + +impl Node { + /// Constructs a new leaf node from input data. + /// + /// # Arguments + /// + /// * `hasher` - A reference to a hashing strategy. + /// * `data` - The data to be hashed and stored as a leaf. + pub fn new_leaf(hasher: &dyn Hasher, data: &[u8]) -> Self { + let hash = hasher.hash(data); + Self { + hash, + data: data.to_vec(), + kind: NodeType::Leaf, + } + } + + /// Constructs a new internal node from two child nodes. + /// + /// # Arguments + /// + /// * `hasher` - A reference to a hashing strategy. + /// * `left` - Left child node. + /// * `right` - Right child node. + /// + /// # Behavior + /// + /// The internal node hash is computed as the hash of the concatenated children's hashes. + pub fn new_internal(hasher: &dyn Hasher, left: Node, right: Node) -> Self { + let mut buffer = Vec::::new(); + buffer.extend_from_slice(left.hash().as_bytes()); + buffer.extend_from_slice(right.hash().as_bytes()); + let hash = hasher.hash(&buffer); + Self { + hash, + data: buffer, + kind: NodeType::Internal(Box::new(left), Box::new(right)), + } + } + + /// Returns a reference to the hash of the node. + pub fn hash(&self) -> &str { + &self.hash + } + + /// Returns the data value in bytes format. + pub fn data(&self) -> &[u8] { + &self.data + } + + /// Returns a reference to the node's type (leaf or internal). + pub fn kind(&self) -> &NodeType { + &self.kind + } +} -- cgit v1.2.3-71-g8e6c