diff options
| -rw-r--r-- | src/hasher.rs | 72 | ||||
| -rw-r--r-- | src/lib.rs | 1 | ||||
| -rw-r--r-- | src/merkletree.rs | 57 | ||||
| -rw-r--r-- | src/node.rs | 17 | ||||
| -rw-r--r-- | src/proof.rs | 140 |
5 files changed, 234 insertions, 53 deletions
diff --git a/src/hasher.rs b/src/hasher.rs index 38d6567..77a8450 100644 --- a/src/hasher.rs +++ b/src/hasher.rs @@ -1,8 +1,5 @@ //! 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. @@ -14,6 +11,7 @@ pub trait Hasher { /// A dummy hasher used for testing or demonstration purposes. /// /// Always returns a static hash value. +#[derive(Clone)] pub struct DummyHasher; impl Hasher for DummyHasher { @@ -23,37 +21,51 @@ impl Hasher for DummyHasher { } #[cfg(feature = "sha256")] -/// A hasher implementation using the SHA-256 cryptographic hash function. -pub struct SHA256Hasher; +mod hasher_sha256 { + use super::*; + use sha2::{Digest, Sha256}; -#[cfg(feature = "sha256")] -impl Hasher for SHA256Hasher { - fn hash(&self, input: &[u8]) -> String { - let mut hasher = Sha256::new(); - hasher.update(input); - hex::encode(hasher.finalize()) - } -} + #[derive(Clone)] + /// A hasher implementation using the SHA-256 cryptographic hash function. + pub struct SHA256Hasher; -#[cfg(all(test, feature = "sha256"))] -mod tests { - use super::*; + impl SHA256Hasher { + pub fn new() -> Self { + Self {} + } + } - #[test] - fn test_sha256_hasher_with_known_input() { - let hasher = SHA256Hasher; - let input = "hello".as_bytes(); - let expected_hash = "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824"; - let actual_hash = hasher.hash(input); - assert_eq!(actual_hash, expected_hash); + impl Hasher for SHA256Hasher { + fn hash(&self, input: &[u8]) -> String { + let mut hasher = Sha256::new(); + hasher.update(input); + hex::encode(hasher.finalize()) + } } - #[test] - fn test_sha256_hasher_empty_string() { - let hasher = SHA256Hasher; - let input = &[]; - let expected_hash = "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"; - let actual_hash = hasher.hash(input); - assert_eq!(actual_hash, expected_hash); + #[cfg(test)] + mod tests { + use super::*; + + #[test] + fn test_sha256_hasher_with_known_input() { + let hasher = SHA256Hasher; + let input = "hello".as_bytes(); + let expected_hash = "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824"; + let actual_hash = hasher.hash(input); + assert_eq!(actual_hash, expected_hash); + } + + #[test] + fn test_sha256_hasher_empty_string() { + let hasher = SHA256Hasher; + let input = &[]; + let expected_hash = "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"; + let actual_hash = hasher.hash(input); + assert_eq!(actual_hash, expected_hash); + } } } + +#[cfg(feature = "sha256")] +pub use hasher_sha256::*; @@ -4,3 +4,4 @@ pub mod hasher; pub mod merkletree; pub mod node; +pub mod proof; diff --git a/src/merkletree.rs b/src/merkletree.rs index 6173c2f..9d2ff84 100644 --- a/src/merkletree.rs +++ b/src/merkletree.rs @@ -8,7 +8,6 @@ use crate::{hasher::Hasher, node::Node}; /// 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>, @@ -34,10 +33,11 @@ impl MerkleTree { /// /// 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<I, T>(hasher: &dyn Hasher, data: I) -> Self + pub fn new<I, T, H>(hasher: H, data: I) -> Self where I: IntoIterator<Item = T>, T: AsRef<[u8]>, + H: Hasher + 'static, { let owned_data: Vec<T> = data.into_iter().collect(); let data_slices: Vec<&[u8]> = owned_data.iter().map(|item| item.as_ref()).collect(); @@ -49,7 +49,7 @@ impl MerkleTree { let mut leaves: Vec<Node> = data_slices .iter() - .map(|x| Node::new_leaf(hasher, x)) + .map(|data| Node::new_leaf(data, hasher.hash(data))) .collect(); if leaves.len() % 2 != 0 { @@ -60,7 +60,10 @@ impl MerkleTree { } /// 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 { + fn build<H>(hasher: H, mut nodes: Vec<Node>) -> Self + where + H: Hasher + 'static, + { let leaves = nodes.clone(); let mut height = 0; @@ -74,7 +77,11 @@ impl MerkleTree { for pair in nodes.chunks(2) { let (left, right) = (pair[0].clone(), pair[1].clone()); - next_level.push(Node::new_internal(hasher, left, right)); + let mut buffer = Vec::<u8>::new(); + buffer.extend_from_slice(left.hash().as_bytes()); + buffer.extend_from_slice(right.hash().as_bytes()); + let hash = hasher.hash(&buffer); + next_level.push(Node::new_internal(&buffer, hash, left, right)); } nodes = next_level; height += 1; @@ -112,14 +119,14 @@ impl MerkleTree { #[cfg(test)] mod tests { - use crate::hasher::*; - use super::*; + use crate::hasher::*; + use crate::proof::*; #[test] fn test_merkle_tree_with_default_hasher() { let data = &["hello".as_bytes(), "world".as_bytes()]; - let tree = MerkleTree::new(&DummyHasher, data); + let tree = MerkleTree::new(DummyHasher, data); assert_eq!(tree.height(), 2); assert_eq!(tree.root().hash(), "0xc0ff3"); @@ -129,7 +136,7 @@ mod tests { #[cfg(feature = "sha256")] fn test_merkle_tree_hashing() { let data = &["hello".as_bytes(), "world".as_bytes()]; - let tree = MerkleTree::new(&SHA256Hasher, data); + let tree = MerkleTree::new(SHA256Hasher::new(), data); assert_eq!(tree.height(), 2); assert_eq!( @@ -142,7 +149,7 @@ mod tests { #[cfg(feature = "sha256")] fn test_merkle_tree_single_leaf() { let data = &["hello".as_bytes()]; - let tree = MerkleTree::new(&SHA256Hasher, data); + let tree = MerkleTree::new(SHA256Hasher::new(), data); assert_eq!(tree.height(), 2); assert_eq!(tree.len(), 2); @@ -158,7 +165,7 @@ mod tests { 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); + let tree = MerkleTree::new(SHA256Hasher::new(), &data); assert_eq!(tree.height(), 5); // 10 elements padded to 16 → log2(16) + 1 = 5 @@ -171,4 +178,32 @@ mod tests { "9da1ff0dfa79217bdbea9ec96407b1e693646cc493f64059fa27182a37cadf94" ); } + + #[test] + fn test_proof_generation_and_verification_dummy() { + let hasher = DummyHasher; + let data = vec!["a", "b", "c", "d"]; + let tree = MerkleTree::new(hasher.clone(), data.clone()); + let proofer = DefaultProofer::new(hasher.clone(), tree.leaves.clone()); + + for (index, item) in data.iter().enumerate() { + let proof = proofer.generate(index).unwrap(); + + assert!(proofer.verify(&proof, item, tree.root().hash(), &hasher)); + } + } + #[test] + #[cfg(feature = "sha256")] + fn test_proof_generation_and_verification_sha256() { + let hasher = SHA256Hasher::new(); + let data = vec!["a", "b", "c", "d"]; + let tree = MerkleTree::new(hasher.clone(), data.clone()); + let proofer = DefaultProofer::new(hasher.clone(), tree.leaves.clone()); + + for (index, item) in data.iter().enumerate() { + let proof = proofer.generate(index).unwrap(); + + assert!(proofer.verify(&proof, item, tree.root().hash(), &hasher)); + } + } } diff --git a/src/node.rs b/src/node.rs index cef5c1f..0bd0549 100644 --- a/src/node.rs +++ b/src/node.rs @@ -1,9 +1,7 @@ //! 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)] +#[derive(Clone)] pub enum NodeType { /// A leaf node that contains no children. Leaf, @@ -30,7 +28,7 @@ impl NodeType { } /// Represents a node in a Merkle tree, either leaf or internal. -#[derive(Debug, Clone)] +#[derive(Clone)] pub struct Node { /// Hash value stored at the node. hash: String, @@ -47,8 +45,7 @@ impl Node { /// /// * `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); + pub fn new_leaf(data: &[u8], hash: String) -> Self { Self { hash, data: data.to_vec(), @@ -67,14 +64,10 @@ impl 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::<u8>::new(); - buffer.extend_from_slice(left.hash().as_bytes()); - buffer.extend_from_slice(right.hash().as_bytes()); - let hash = hasher.hash(&buffer); + pub fn new_internal(data: &[u8], hash: String, left: Node, right: Node) -> Self { Self { hash, - data: buffer, + data: data.to_vec(), kind: NodeType::Internal(Box::new(left), Box::new(right)), } } diff --git a/src/proof.rs b/src/proof.rs new file mode 100644 index 0000000..82f4a77 --- /dev/null +++ b/src/proof.rs @@ -0,0 +1,140 @@ +//! Merkle tree proof and verification implementation + +use crate::{hasher::Hasher, node::Node}; + +/// Represents a single step in a Merkle proof path +#[derive(Debug, Clone)] +pub struct ProofNode { + /// 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, +} + +/// 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 + pub path: Vec<ProofNode>, + /// The index of the leaf node this proof corresponds to + pub leaf_index: usize, +} + +pub trait Proofer { + /// Generates a Merkle proof for the data at the specified index + /// + /// # Arguments + /// + /// * `index` - The index of the leaf node to generate a proof for + /// + /// # Returns + /// + /// `Some(MerkleProof)` if the index is valid, `None` otherwise + fn generate(&self, index: usize) -> Option<MerkleProof>; + + /// Verifies that a piece of data exists in the tree using a Merkle proof/ + /// + /// # Arguments + /// + /// * `proof` - The Merkle proof. + /// * `data` - The original data to verify. + /// * `root_hash` - The expected root hash of the tree. + /// * `hasher` - The hasher used to construct the tree. + /// + /// # Returns + /// + /// `true` if the proof is valid and the data exists in the tree, `false` otherwise + fn verify<T>(&self, proof: &MerkleProof, data: T, root_hash: &str, hasher: &dyn Hasher) -> bool + where + T: AsRef<[u8]>; +} + +pub struct DefaultProofer { + hasher: Box<dyn Hasher>, + leaves: Vec<Node>, +} + +impl DefaultProofer { + pub fn new<T: Hasher + 'static>(hasher: T, leaves: Vec<Node>) -> Self { + Self { + hasher: Box::new(hasher), + leaves, + } + } +} + +impl Proofer for DefaultProofer { + fn generate(&self, index: usize) -> Option<MerkleProof> { + if index >= self.leaves.len() { + return None; + } + + let mut path = Vec::new(); + let mut current_index = index; + let mut current_level = self.leaves.clone(); + + // Buildthe proof by walking up the tree + while current_level.len() > 1 { + // Ensure even number of nodes at this level + if current_level.len() % 2 != 0 { + current_level.push(current_level[current_level.len() - 1].clone()); + } + + // Find the sibling of the current node + let sibling_index = if current_index % 2 == 0 { + current_index + 1 // Right sibling + } else { + current_index - 1 // Left sibling + }; + + let is_left = sibling_index < current_index; + path.push(ProofNode { + hash: current_level[sibling_index].hash().to_string(), + is_left, + }); + + // Move to the next level + let mut next_level = Vec::new(); + for pair in current_level.chunks(2) { + let (left, right) = (pair[0].clone(), pair[1].clone()); + + let mut buffer = Vec::<u8>::new(); + buffer.extend_from_slice(left.hash().as_bytes()); + buffer.extend_from_slice(right.hash().as_bytes()); + let hash = self.hasher.hash(&buffer); + next_level.push(Node::new_internal(&buffer, hash, left, right)); + } + current_level = next_level; + current_index /= 2; + } + + Some(MerkleProof { + path, + leaf_index: index, + }) + } + + fn verify<T>(&self, proof: &MerkleProof, data: T, root_hash: &str, hasher: &dyn Hasher) -> bool + where + T: AsRef<[u8]>, + { + // Start with the hash of the data + let mut current_hash = hasher.hash(data.as_ref()); + + // 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()) + }; + } + + // Check if the computed root matches the expected root + current_hash == root_hash + } +} |