use crate::hashing::{sha256, Sha256Digest};
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MerkleTree {
root: Sha256Digest,
leaves: Vec<Sha256Digest>,
}
impl MerkleTree {
pub fn new(leaves: Vec<Sha256Digest>) -> Self {
assert!(!leaves.is_empty(), "MerkleTree requires at least one leaf");
let root = Self::build_tree(leaves.clone());
Self { root, leaves }
}
fn build_tree(mut leaves: Vec<Sha256Digest>) -> Sha256Digest {
if leaves.len() == 1 {
return leaves[0];
}
if leaves.len() % 2 == 1 {
leaves.push(*leaves.last().unwrap());
}
let mut parents = Vec::with_capacity(leaves.len() / 2);
for chunk in leaves.chunks(2) {
let combined = format!("{}{}", chunk[0].to_hex(), chunk[1].to_hex());
parents.push(sha256(combined.as_bytes()));
}
Self::build_tree(parents)
}
pub fn root(&self) -> &Sha256Digest {
&self.root
}
pub fn leaves(&self) -> &[Sha256Digest] {
&self.leaves
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::hashing::sha256;
#[test]
fn merkle_single_leaf() {
let leaf = sha256(b"hello");
let tree = MerkleTree::new(vec![leaf]);
assert_eq!(tree.root(), &leaf);
}
#[test]
fn merkle_two_leaves() {
let a = sha256(b"a");
let b = sha256(b"b");
let tree = MerkleTree::new(vec![a, b]);
let expected = sha256(format!("{}{}", a.to_hex(), b.to_hex()).as_bytes());
assert_eq!(tree.root(), &expected);
}
#[test]
fn merkle_three_leaves() {
let a = sha256(b"a");
let b = sha256(b"b");
let c = sha256(b"c");
let tree = MerkleTree::new(vec![a, b, c]);
let combined = format!("{}{}{}", a.to_hex(), b.to_hex(), c.to_hex());
let expected = sha256(combined.as_bytes());
assert_eq!(tree.root(), &expected);
}
}