diff options
| -rw-r--r-- | Cargo.lock | 1 | ||||
| -rw-r--r-- | Cargo.toml | 1 | ||||
| -rw-r--r-- | benches/bigfile.rs | 7 | ||||
| -rw-r--r-- | src/hasher.rs | 2 | ||||
| -rw-r--r-- | src/merkletree.rs | 27 | ||||
| -rw-r--r-- | src/proof.rs | 28 |
6 files changed, 40 insertions, 26 deletions
@@ -353,6 +353,7 @@ dependencies = [ "criterion", "hex", "rand", + "rayon", "sha2", "sha3", ] @@ -7,6 +7,7 @@ edition = "2024" [dependencies] blake3 = "1.8.2" hex = { version = "0.4.3" } +rayon = "1.10.0" sha2 = { version = "0.10.9" } sha3 = "0.10.8" diff --git a/benches/bigfile.rs b/benches/bigfile.rs index 3d2088d..f9752a1 100644 --- a/benches/bigfile.rs +++ b/benches/bigfile.rs @@ -46,7 +46,10 @@ fn cleanup_files(filenames: &Vec<String>) -> std::io::Result<()> { Ok(()) } -fn test_merkle_tree<H: Hasher + Clone + 'static>(hasher: H, files: &Vec<Vec<u8>>) { +fn test_merkle_tree<H: Hasher + Clone + 'static + std::marker::Sync>( + hasher: H, + files: &Vec<Vec<u8>>, +) { let tree = MerkleTree::new(hasher.clone(), files); let proofer = DefaultProofer::new(hasher, tree.leaves().clone()); let root = tree.root(); @@ -118,7 +121,7 @@ fn bench_large_merkle_tree_blake3(c: &mut Criterion) { group.sample_size(10); for size in [5, 10, 15] { group.bench_function( - format!("MerkleTree creation and validation with 10 nodes and Keccak256 algorithm. {size} MB per each file."), + format!("MerkleTree creation and validation with 10 nodes and Blake3 algorithm. {size} MB per each file."), |b| { let files = setup_files(&filenames, size).expect("failed to allocate new files"); 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; } |