From 5fb45710f57f95eec527958400f8ec0a049c5fe4 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Mon, 7 Jul 2025 17:14:12 +0200 Subject: Make tree for folders --- Cargo.toml | 4 ++-- examples/merkletree_blake3.rs | 14 ++---------- examples/proofer_blake3.rs | 24 ++++++-------------- src/fs.rs | 53 +++++++++++++++++++++++++++++++++++++++++++ src/lib.rs | 1 + src/merkletree.rs | 16 ++++++++++++- src/proof.rs | 30 +++++++++++++----------- 7 files changed, 97 insertions(+), 45 deletions(-) create mode 100644 src/fs.rs diff --git a/Cargo.toml b/Cargo.toml index 7bfe238..5410d2f 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -6,9 +6,9 @@ edition = "2024" [dependencies] blake3 = "1.8.2" -hex = { version = "0.4.3" } +hex = "0.4.3" rayon = "1.10.0" -sha2 = { version = "0.10.9" } +sha2 = "0.10.9" sha3 = "0.10.8" [dev-dependencies] diff --git a/examples/merkletree_blake3.rs b/examples/merkletree_blake3.rs index 7f30a76..77ff2a0 100644 --- a/examples/merkletree_blake3.rs +++ b/examples/merkletree_blake3.rs @@ -10,19 +10,9 @@ fn main() { } // Read file contents into a vector of bytes - let mut file_contents = Vec::new(); - for filename in &filenames { - match std::fs::read(filename) { - Ok(contents) => file_contents.push(contents), - Err(e) => { - eprintln!("Failed to read file '{}': {}", filename, e); - std::process::exit(1); - } - } - } - let hasher = Blake3Hasher::new(); - let tree = MerkleTree::new(hasher.clone(), file_contents.clone()); + + let tree = MerkleTree::from_paths(hasher, filenames); println!("{}", tree.root().hash()); } diff --git a/examples/proofer_blake3.rs b/examples/proofer_blake3.rs index ca38d6f..8db3999 100644 --- a/examples/proofer_blake3.rs +++ b/examples/proofer_blake3.rs @@ -1,5 +1,6 @@ use mt_rs::{ - hasher::{Blake3Hasher, Hasher}, + fs, + hasher::Blake3Hasher, node::Node, proof::{DefaultProofer, Proofer}, }; @@ -21,27 +22,16 @@ fn main() { std::process::exit(1); } - let mut nodes: Vec = Vec::new(); - for filename in &filenames { - match std::fs::read(filename) { - Ok(contents) => nodes.push(Node::new_leaf(Blake3Hasher::new().hash(&contents))), - Err(e) => { - eprintln!("Failed to read file '{}': {}", filename, e); - std::process::exit(1); - } - } - } - let hasher = Blake3Hasher::new(); + + let nodes: Vec = fs::hash_dir(hasher.clone(), filenames.clone()); + let first_node = nodes[0].clone(); + let proofer = DefaultProofer::new(hasher, nodes); let proof = proofer.generate(0).expect("Couldn't generate proof"); println!( "{}", - proofer.verify( - &proof, - std::fs::read(&filenames[0]).unwrap(), - &root_hash[..] - ) + proofer.verify_hash(&proof, first_node.hash().to_string(), &root_hash[..]) ); } diff --git a/src/fs.rs b/src/fs.rs new file mode 100644 index 0000000..cb8ce66 --- /dev/null +++ b/src/fs.rs @@ -0,0 +1,53 @@ +//! Provides the module used for filesystem operations made by this library. + +use std::path::Path; + +use crate::{hasher::Hasher, node::Node}; + +/// Reads the entire content of a file into a `Vec`. +/// +/// If the file cannot be read, an error message is printed to stderr, and the program exits. +/// +/// `path` is a reference to a `String` representing the path to the file. +fn read_file_content(path: &String) -> Vec { + match std::fs::read(path) { + Ok(contents) => contents, + Err(e) => { + eprintln!("Failed to read file '{}': {}", path, e); + std::process::exit(1); + } + } +} + +/// Recursively hashes the contents of files and directories. +/// +/// This function iterates through a list of filenames. For each file, it reads its content, +/// hashes it using the provided `Hasher`, and creates a leaf `Node`. If an entry is a directory, +/// it recursively calls itself to hash the directory's contents and extends the current +/// list of nodes with the results. +pub fn hash_dir(hasher: H, filenames: Vec) -> Vec +where + H: Hasher + 'static + std::marker::Sync + Clone, +{ + let mut nodes: Vec = vec![]; + for filename in &filenames { + let file = Path::new(filename); + if file.is_file() { + let hash = hasher.hash(read_file_content(filename).as_slice()); + + nodes.push(Node::new_leaf(hash)); + } else if file.is_dir() { + let mut filenames_in_dir: Vec = file + .read_dir() + .unwrap() + .map(|entry| String::from(entry.unwrap().path().to_str().unwrap())) + .collect(); + + filenames_in_dir.sort(); + + nodes.extend(hash_dir(hasher.clone(), filenames_in_dir)); + } + } + + nodes +} diff --git a/src/lib.rs b/src/lib.rs index b23f7d1..7252ebb 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -51,6 +51,7 @@ //! )); //! //! ``` +pub mod fs; pub mod hasher; pub mod merkletree; pub mod node; diff --git a/src/merkletree.rs b/src/merkletree.rs index c3c9fd7..fdbb5ac 100644 --- a/src/merkletree.rs +++ b/src/merkletree.rs @@ -1,7 +1,7 @@ //! Provides the MerkleTree structure and associated methods for creating and interacting //! with binary Merkle trees using custom hashers. -use crate::{hasher::Hasher, node::Node}; +use crate::{fs, hasher::Hasher, node::Node}; use rayon::prelude::*; /// A binary Merkle tree implementation. @@ -60,6 +60,20 @@ impl MerkleTree { Self::build(hasher, leaves) } + /// Construct a Merkletree from an iter of String-s. + pub fn from_paths(hasher: H, paths: Vec) -> Self + where + H: Hasher + 'static + std::marker::Sync + Clone, + { + let mut leaves = fs::hash_dir(hasher.clone(), paths); + + if leaves.len() % 2 != 0 { + leaves.push(leaves.last().unwrap().clone()); + } + + Self::build(hasher, leaves) + } + /// Constructs the internal nodes of the tree from the leaves upward and computes the root. fn build(hasher: H, nodes: Vec) -> Self where diff --git a/src/proof.rs b/src/proof.rs index af0af94..b6b5860 100644 --- a/src/proof.rs +++ b/src/proof.rs @@ -64,6 +64,21 @@ where pub fn new(hasher: H, leaves: Vec) -> Self { Self { hasher, leaves } } + + pub fn verify_hash(&self, proof: &MerkleProof, hash: String, root_hash: &str) -> bool { + let mut current_hash = hash; + // Walk up the tree using the proof path + for proof_node in &proof.path { + let combined: String = match proof_node.child_type { + NodeChildType::Left => format!("{}{}", proof_node.hash, current_hash), + NodeChildType::Right => format!("{}{}", current_hash, proof_node.hash), + }; + current_hash = self.hasher.hash(combined.as_bytes()); + } + + // Check if the computed root matches the expected root + current_hash == root_hash + } } impl Proofer for DefaultProofer @@ -138,19 +153,8 @@ where T: AsRef<[u8]>, { // Start with the hash of the data - let mut current_hash = self.hasher.hash(data.as_ref()); - - // Walk up the tree using the proof path - for proof_node in &proof.path { - let combined: String = match proof_node.child_type { - NodeChildType::Left => format!("{}{}", proof_node.hash, current_hash), - NodeChildType::Right => format!("{}{}", current_hash, proof_node.hash), - }; - current_hash = self.hasher.hash(combined.as_bytes()); - } - - // Check if the computed root matches the expected root - current_hash == root_hash + let hash: String = self.hasher.hash(data.as_ref()); + self.verify_hash(proof, hash, root_hash) } } -- cgit v1.2.3-71-g8e6c