open-standards/wai/wai-quantum/src/merkle.rs

//! The JWP Merkle floor, verbatim.
//!
//! Receipts in this crate bind their leaves with the same Merkle construction the
//! WAI worlds/provenance receipts use. The domain separators and tree shape are
//! reproduced **exactly** — every previously issued receipt and every published
//! conformance vector must still verify against this code.

const MERKLE_LEAF: &[u8] = b"moq-jwp:merkle-leaf\x01";
const MERKLE_NODE: &[u8] = b"moq-jwp:merkle-node\x01";

fn merkle_leaf(content_hash: &[u8; 32]) -> [u8; 32] {
    let mut h = blake3::Hasher::new();
    h.update(MERKLE_LEAF);
    h.update(content_hash);
    *h.finalize().as_bytes()
}

fn merkle_node(left: &[u8; 32], right: &[u8; 32]) -> [u8; 32] {
    let mut h = blake3::Hasher::new();
    h.update(MERKLE_NODE);
    h.update(left);
    h.update(right);
    *h.finalize().as_bytes()
}

/// Merkle root over `object_hashes` (odd levels duplicate the last node).
pub fn merkle_root(object_hashes: &[[u8; 32]]) -> [u8; 32] {
    if object_hashes.is_empty() {
        return [0u8; 32];
    }
    let mut level: Vec<[u8; 32]> = object_hashes.iter().map(merkle_leaf).collect();
    while level.len() > 1 {
        if level.len() % 2 == 1 {
            level.push(*level.last().unwrap());
        }
        level = level
            .chunks_exact(2)
            .map(|pair| merkle_node(&pair[0], &pair[1]))
            .collect();
    }
    level[0]
}