Init

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
+    }
+}