diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Cargo.lock | 100 | ||||
| -rw-r--r-- | Cargo.toml | 9 | ||||
| -rw-r--r-- | src/hasher.rs | 42 | ||||
| -rw-r--r-- | src/lib.rs | 2 | ||||
| -rw-r--r-- | src/merkle/merkletree.rs | 67 | ||||
| -rw-r--r-- | src/merkle/mod.rs | 35 | ||||
| -rw-r--r-- | src/merkle/node.rs | 56 |
8 files changed, 312 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..ea8c4bf --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +/target diff --git a/Cargo.lock b/Cargo.lock new file mode 100644 index 0000000..1f281fc --- /dev/null +++ b/Cargo.lock @@ -0,0 +1,100 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "block-buffer" +version = "0.10.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3078c7629b62d3f0439517fa394996acacc5cbc91c5a20d8c658e77abd503a71" +dependencies = [ + "generic-array", +] + +[[package]] +name = "cfg-if" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9555578bc9e57714c812a1f84e4fc5b4d21fcb063490c624de019f7464c91268" + +[[package]] +name = "cpufeatures" +version = "0.2.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "59ed5838eebb26a2bb2e58f6d5b5316989ae9d08bab10e0e6d103e656d1b0280" +dependencies = [ + "libc", +] + +[[package]] +name = "crypto-common" +version = "0.1.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1bfb12502f3fc46cca1bb51ac28df9d618d813cdc3d2f25b9fe775a34af26bb3" +dependencies = [ + "generic-array", + "typenum", +] + +[[package]] +name = "digest" +version = "0.10.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9ed9a281f7bc9b7576e61468ba615a66a5c8cfdff42420a70aa82701a3b1e292" +dependencies = [ + "block-buffer", + "crypto-common", +] + +[[package]] +name = "generic-array" +version = "0.14.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "85649ca51fd72272d7821adaf274ad91c288277713d9c18820d8499a7ff69e9a" +dependencies = [ + "typenum", + "version_check", +] + +[[package]] +name = "hex" +version = "0.4.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7f24254aa9a54b5c858eaee2f5bccdb46aaf0e486a595ed5fd8f86ba55232a70" + +[[package]] +name = "libc" +version = "0.2.172" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d750af042f7ef4f724306de029d18836c26c1765a54a6a3f094cbd23a7267ffa" + +[[package]] +name = "mt" +version = "0.1.0" +dependencies = [ + "hex", + "sha2", +] + +[[package]] +name = "sha2" +version = "0.10.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a7507d819769d01a365ab707794a4084392c824f54a7a6a7862f8c3d0892b283" +dependencies = [ + "cfg-if", + "cpufeatures", + "digest", +] + +[[package]] +name = "typenum" +version = "1.18.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1dccffe3ce07af9386bfd29e80c0ab1a8205a2fc34e4bcd40364df902cfa8f3f" + +[[package]] +name = "version_check" +version = "0.9.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0b928f33d975fc6ad9f86c8f283853ad26bdd5b10b7f1542aa2fa15e2289105a" diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..95acfdf --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "mt" +author = "Santo Cariotti <santo@dcariotti.me>" +version = "0.1.0" +edition = "2024" + +[dependencies] +hex = "0.4.3" +sha2 = "0.10.9" diff --git a/src/hasher.rs b/src/hasher.rs new file mode 100644 index 0000000..028e73a --- /dev/null +++ b/src/hasher.rs @@ -0,0 +1,42 @@ +use sha2::{Digest, Sha256}; + +pub trait Hasher { + fn hash(&self, input: &str) -> String; +} + +pub struct DefaultHasher; + +impl Hasher for DefaultHasher { + fn hash(&self, input: &str) -> String { + let mut hasher = Sha256::new(); + hasher.update(input.as_bytes()); + hex::encode(hasher.finalize()) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_default_hasher_with_known_input() { + let hasher = DefaultHasher; + let input = "hello"; + let expected_hash = "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824"; + + let actual_hash = hasher.hash(input); + + assert_eq!(actual_hash, expected_hash); + } + + #[test] + fn test_default_hasher_empty_string() { + let hasher = DefaultHasher; + let input = ""; + let expected_hash = "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"; + + let actual_hash = hasher.hash(input); + + assert_eq!(actual_hash, expected_hash); + } +} diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..9e3b1d1 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,2 @@ +mod hasher; +mod merkle; diff --git a/src/merkle/merkletree.rs b/src/merkle/merkletree.rs new file mode 100644 index 0000000..58a7c75 --- /dev/null +++ b/src/merkle/merkletree.rs @@ -0,0 +1,67 @@ +use crate::{hasher::Hasher, merkle::node::Node}; + +#[derive(Debug)] +pub struct MerkleTree { + leafs: Vec<Node>, + height: usize, + root: Node, +} + +impl MerkleTree { + pub fn new<T: ToString>(hasher: &dyn Hasher, data: Vec<T>) -> Self { + assert!( + !data.is_empty(), + "Merkle Tree requires at least one element" + ); + + let mut leafs: Vec<Node> = data + .into_iter() + .map(|x| Node::new_leaf(hasher, x)) + .collect(); + if leafs.len() % 2 != 0 { + leafs.push(leafs[leafs.len() - 1].clone()); + } + + Self::build(hasher, leafs) + } + + fn build(hasher: &dyn Hasher, mut nodes: Vec<Node>) -> Self { + let leafs = nodes.clone(); + let mut height = 0; + + while nodes.len() > 1 { + let mut next_level = Vec::new(); + for pair in nodes.chunks(2) { + let left = pair[0].clone(); + let right = if pair.len() == 2 { + pair[1].clone() + } else { + left.clone() + }; + next_level.push(Node::new_internal(hasher, left, right)); + } + nodes = next_level; + height += 1; + } + + let root = nodes.remove(0); + + MerkleTree { + leafs, + height: height + 1, + root, + } + } + + pub fn height(&self) -> usize { + self.height + } + + pub fn len(&self) -> usize { + self.leafs.len() + } + + pub fn root(&self) -> Node { + self.root.clone() + } +} diff --git a/src/merkle/mod.rs b/src/merkle/mod.rs new file mode 100644 index 0000000..b6da2f9 --- /dev/null +++ b/src/merkle/mod.rs @@ -0,0 +1,35 @@ +mod merkletree; +mod node; + +#[cfg(test)] +mod tests { + use crate::hasher::DefaultHasher; + + use super::*; + + #[test] + fn test_merkle_tree_hashing() { + let data = vec!["a", "b", "c", "d"]; + let tree = merkletree::MerkleTree::new(&DefaultHasher, data); + + assert_eq!(tree.height(), 3); + + assert_eq!( + tree.root().hash(), + "58c89d709329eb37285837b042ab6ff72c7c8f74de0446b091b6a0131c102cfd" + ); + } + + #[test] + fn test_merkle_tree_single_leaf() { + let data = vec!["hello"]; + let tree = merkletree::MerkleTree::new(&DefaultHasher, data); + + assert_eq!(tree.height(), 2); + assert_eq!(tree.len(), 2); + assert_eq!( + tree.root().hash(), + "286d189fda11bf4e906b6973a173009f47ede16532f1bae726223f8ee155d73b" + ); + } +} diff --git a/src/merkle/node.rs b/src/merkle/node.rs new file mode 100644 index 0000000..9d552cd --- /dev/null +++ b/src/merkle/node.rs @@ -0,0 +1,56 @@ +use crate::hasher::Hasher; + +#[derive(Debug, Clone)] +enum NodeType { + Leaf, + Internal(Box<Node>, Box<Node>), +} + +impl NodeType { + pub fn left(&self) -> Option<&Box<Node>> { + match self { + NodeType::Leaf => None, + NodeType::Internal(l, _) => Some(l), + } + } + + pub fn right(&self) -> Option<&Box<Node>> { + match self { + NodeType::Leaf => None, + NodeType::Internal(_, r) => Some(r), + } + } +} + +#[derive(Debug, Clone)] +pub struct Node { + hash: String, + kind: NodeType, +} + +impl Node { + pub fn new_leaf<T: ToString>(hasher: &dyn Hasher, data: T) -> Self { + let hash = hasher.hash(&data.to_string()); + Self { + hash, + kind: NodeType::Leaf, + } + } + + pub fn new_internal(hasher: &dyn Hasher, left: Node, right: Node) -> Self { + let combined = format!("{}{}", left.hash, right.hash); + let hash = hasher.hash(&combined); + Self { + hash, + kind: NodeType::Internal(Box::new(left), Box::new(right)), + } + } + + pub fn hash(&self) -> &str { + &self.hash + } + + pub fn kind(&self) -> &NodeType { + &self.kind + } +} |