From 04891bbcaac75e887d57844548b61141cb6ebc07 Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
Date: Fri, 13 Jun 2025 13:29:29 +0200
Subject: Init

---
 src/merkle/merkletree.rs | 67 ++++++++++++++++++++++++++++++++++++++++++++++++
 src/merkle/mod.rs        | 35 +++++++++++++++++++++++++
 src/merkle/node.rs       | 56 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 158 insertions(+)
 create mode 100644 src/merkle/merkletree.rs
 create mode 100644 src/merkle/mod.rs
 create mode 100644 src/merkle/node.rs

(limited to 'src/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
+    }
+}
-- 
cgit v1.2.3-71-g8e6c