Add proofer

Also, avoid to request hasher on node creation

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::*;
diff --git a/src/lib.rs b/src/lib.rs
index e71c875..aaae31c 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -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
+    }
+}