diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/hasher.rs | 14 | ||||
| -rw-r--r-- | src/lib.rs | 3 | ||||
| -rw-r--r-- | src/merkle/merkletree.rs | 32 | ||||
| -rw-r--r-- | src/merkle/mod.rs | 6 | ||||
| -rw-r--r-- | src/merkle/node.rs | 29 |
5 files changed, 78 insertions, 6 deletions
diff --git a/src/hasher.rs b/src/hasher.rs index 898393f..a26dd3c 100644 --- a/src/hasher.rs +++ b/src/hasher.rs @@ -1,10 +1,19 @@ +//! Provides hashing abstractions and implementations including SHA256 and a default dummy hasher. + #[cfg(feature = "sha256")] use sha2::{Digest, Sha256}; +/// A trait representing a generic hash function. +/// +/// This allows the Merkle tree to use any hash function that conforms to this interface. pub trait Hasher { + /// Hashes an input string and returns the resulting hash as a hexadecimal string. fn hash(&self, input: &str) -> String; } +/// A dummy hasher used for testing or demonstration purposes. +/// +/// Always returns a static hash value. pub struct DefaultHasher; impl Hasher for DefaultHasher { @@ -14,6 +23,7 @@ impl Hasher for DefaultHasher { } #[cfg(feature = "sha256")] +/// A hasher implementation using the SHA-256 cryptographic hash function. pub struct SHA256Hasher; #[cfg(feature = "sha256")] @@ -34,9 +44,7 @@ mod tests { let hasher = SHA256Hasher; let input = "hello"; let expected_hash = "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824"; - let actual_hash = hasher.hash(input); - assert_eq!(actual_hash, expected_hash); } @@ -45,9 +53,7 @@ mod tests { let hasher = SHA256Hasher; let input = ""; let expected_hash = "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"; - let actual_hash = hasher.hash(input); - assert_eq!(actual_hash, expected_hash); } } @@ -1,2 +1,5 @@ +//! This library provides modular components to build and verify binary Merkle trees +//! with pluggable hash functions. + pub mod hasher; pub mod merkle; diff --git a/src/merkle/merkletree.rs b/src/merkle/merkletree.rs index 812e300..fc2879a 100644 --- a/src/merkle/merkletree.rs +++ b/src/merkle/merkletree.rs @@ -1,13 +1,39 @@ +//! 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<Node>, + /// 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<T: ToString>(hasher: &dyn Hasher, data: Vec<T>) -> Self { assert!( !data.is_empty(), @@ -18,6 +44,7 @@ impl MerkleTree { .into_iter() .map(|x| Node::new_leaf(hasher, x)) .collect(); + if leaves.len() % 2 != 0 { leaves.push(leaves[leaves.len() - 1].clone()); } @@ -25,6 +52,7 @@ impl MerkleTree { 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<Node>) -> Self { let leaves = nodes.clone(); let mut height = 0; @@ -48,18 +76,22 @@ impl MerkleTree { } } + /// 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 index 1fea22f..4a6e46f 100644 --- a/src/merkle/mod.rs +++ b/src/merkle/mod.rs @@ -1,3 +1,7 @@ +//! High-level module for Merkle tree functionality. +//! +//! Re-exports the Merkle tree and node modules for external use. + pub mod merkletree; pub mod node; @@ -13,7 +17,6 @@ mod tests { let tree = merkletree::MerkleTree::new(&DefaultHasher, data); assert_eq!(tree.height(), 3); - assert_eq!(tree.root().hash(), "0xc0ff3"); } @@ -24,7 +27,6 @@ mod tests { let tree = merkletree::MerkleTree::new(&SHA256Hasher, data); assert_eq!(tree.height(), 3); - assert_eq!( tree.root().hash(), "58c89d709329eb37285837b042ab6ff72c7c8f74de0446b091b6a0131c102cfd" diff --git a/src/merkle/node.rs b/src/merkle/node.rs index 19cf8d4..0e5e904 100644 --- a/src/merkle/node.rs +++ b/src/merkle/node.rs @@ -1,12 +1,18 @@ +//! 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<Node>, Box<Node>), } 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, @@ -14,6 +20,7 @@ impl NodeType { } } + /// Returns a reference to the right child if the node is internal. pub fn right(&self) -> Option<&Node> { match self { NodeType::Leaf => None, @@ -22,13 +29,22 @@ impl NodeType { } } +/// 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, } 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<T: ToString>(hasher: &dyn Hasher, data: T) -> Self { let hash = hasher.hash(&data.to_string()); Self { @@ -37,6 +53,17 @@ impl Node { } } + /// 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 combined = format!("{}{}", left.hash, right.hash); let hash = hasher.hash(&combined); @@ -46,10 +73,12 @@ impl Node { } } + /// Returns a reference to the hash of the node. pub fn hash(&self) -> &str { &self.hash } + /// Returns a reference to the node's type (leaf or internal). pub fn kind(&self) -> &NodeType { &self.kind } |