3 files changed, 33 insertions, 24 deletions

diff --git a/src/hasher.rs b/src/hasher.rs
index 845127f..18a65b4 100644
--- a/src/hasher.rs
+++ b/src/hasher.rs
@@ -5,7 +5,7 @@ use sha2::Digest;
 /// 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 {
+pub trait Hasher: Send + Sync {
     /// Hashes a sequence of bytes and returns the resulting hash as a hexadecimal string.
     fn hash(&self, input: &[u8]) -> String;
 }
diff --git a/src/merkletree.rs b/src/merkletree.rs
index c8962f4..c3c9fd7 100644
--- a/src/merkletree.rs
+++ b/src/merkletree.rs
@@ -2,6 +2,7 @@
 //! with binary Merkle trees using custom hashers.
 
 use crate::{hasher::Hasher, node::Node};
+use rayon::prelude::*;
 
 /// A binary Merkle tree implementation.
 ///
@@ -37,7 +38,7 @@ impl MerkleTree {
     where
         I: IntoIterator<Item = T>,
         T: AsRef<[u8]>,
-        H: Hasher + 'static,
+        H: Hasher + 'static + std::marker::Sync,
     {
         let owned_data: Vec<T> = data.into_iter().collect();
         let data_slices: Vec<&[u8]> = owned_data.iter().map(|item| item.as_ref()).collect();
@@ -62,7 +63,7 @@ impl MerkleTree {
     /// Constructs the internal nodes of the tree from the leaves upward and computes the root.
     fn build<H>(hasher: H, nodes: Vec<Node>) -> Self
     where
-        H: Hasher + 'static,
+        H: Hasher + 'static + std::marker::Sync,
     {
         let leaves = nodes.clone();
         let mut current_level = nodes;
@@ -76,19 +77,21 @@ impl MerkleTree {
             }
 
             next_level.clear();
+            next_level = current_level
+                .par_chunks(2)
+                .map(|pair| {
+                    let (left, right) = (&pair[0], &pair[1]);
 
-            for pair in current_level.chunks(2) {
-                let (left, right) = (&pair[0], &pair[1]);
+                    let (left_hash, right_hash) = (left.hash().as_bytes(), right.hash().as_bytes());
 
-                let (left_hash, right_hash) = (left.hash().as_bytes(), right.hash().as_bytes());
+                    let mut buffer = Vec::with_capacity(left_hash.len() + right_hash.len());
+                    buffer.extend_from_slice(left_hash);
+                    buffer.extend_from_slice(right_hash);
 
-                let mut buffer = Vec::<u8>::with_capacity(left_hash.len() + right_hash.len());
-                buffer.extend_from_slice(left_hash);
-                buffer.extend_from_slice(right_hash);
-
-                let hash = hasher.hash(&buffer);
-                next_level.push(Node::new_internal(hash, left.clone(), right.clone()));
-            }
+                    let hash = hasher.hash(&buffer);
+                    Node::new_internal(hash, left.clone(), right.clone())
+                })
+                .collect();
 
             std::mem::swap(&mut current_level, &mut next_level);
             height += 1;
diff --git a/src/proof.rs b/src/proof.rs
index d835b87..af0af94 100644
--- a/src/proof.rs
+++ b/src/proof.rs
@@ -4,6 +4,7 @@ use crate::{
     hasher::Hasher,
     node::{Node, NodeChildType},
 };
+use rayon::prelude::*;
 
 /// Represents a single step in a Merkle proof path.
 #[derive(Debug, Clone)]
@@ -77,6 +78,7 @@ where
         let mut path = Vec::new();
         let mut current_index = index;
         let mut current_level = self.leaves.clone();
+        let mut next_level = Vec::with_capacity((current_level.len() + 1) / 2);
 
         // Buildthe proof by walking up the tree
         while current_level.len() > 1 {
@@ -104,20 +106,24 @@ where
             });
 
             // Move to the next level
-            let mut next_level = Vec::new();
-            for pair in current_level.chunks(2) {
-                let (left, right) = (&pair[0], &pair[1]);
+            next_level.clear();
+            next_level = current_level
+                .par_chunks(2)
+                .map(|pair| {
+                    let (left, right) = (&pair[0], &pair[1]);
 
-                let (left_hash, right_hash) = (left.hash().as_bytes(), right.hash().as_bytes());
+                    let (left_hash, right_hash) = (left.hash().as_bytes(), right.hash().as_bytes());
 
-                let mut buffer = Vec::<u8>::with_capacity(left_hash.len() + right_hash.len());
-                buffer.extend_from_slice(left_hash);
-                buffer.extend_from_slice(right_hash);
+                    let mut buffer = Vec::with_capacity(left_hash.len() + right_hash.len());
+                    buffer.extend_from_slice(left_hash);
+                    buffer.extend_from_slice(right_hash);
 
-                let hash = self.hasher.hash(&buffer);
-                next_level.push(Node::new_internal(hash, left.clone(), right.clone()));
-            }
-            current_level = next_level;
+                    let hash = self.hasher.hash(&buffer);
+                    Node::new_internal(hash, left.clone(), right.clone())
+                })
+                .collect();
+
+            std::mem::swap(&mut current_level, &mut next_level);
             current_index /= 2;
         }