vc-shared 0.1.0

Canonical JSON, SHA256 hashing, and Merkle root utilities for Visual Compiler
Documentation
//! Merkle tree implementation for deterministic lineage hashing.
//!
//! This module provides a Merkle tree builder that produces a root hash
//! from a list of leaf hashes. The order of leaves is preserved as given.

use crate::hashing::{sha256, Sha256Digest};

/// A Merkle tree built from a list of leaves.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MerkleTree {
    root: Sha256Digest,
    leaves: Vec<Sha256Digest>,
}

impl MerkleTree {
    /// Builds a Merkle tree from the given leaves.
    ///
    /// # Panics
    /// - If `leaves` is empty.
    /// - The order of leaves is preserved; caller is responsible for canonical ordering.
    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)
    }

    /// Returns the Merkle root hash.
    pub fn root(&self) -> &Sha256Digest {
        &self.root
    }

    /// Returns the leaves in their original order.
    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);
    }
}