use sha2::{Digest, Sha256};
pub const MERKLE_HASH_LEN: usize = 32;
pub const MERKLE_BLOCK_SIZE: usize = 16 * 1024;
pub fn hash_leaf(data: &[u8]) -> [u8; 32] {
let digest = Sha256::digest(data);
let mut out = [0u8; 32];
out.copy_from_slice(&digest);
out
}
pub fn hash_pair(left: &[u8; 32], right: &[u8; 32]) -> [u8; 32] {
let mut hasher = Sha256::new();
hasher.update(left);
hasher.update(right);
let digest = hasher.finalize();
let mut out = [0u8; 32];
out.copy_from_slice(&digest);
out
}
pub fn merkle_root(mut leaves: Vec<[u8; 32]>) -> [u8; 32] {
if leaves.is_empty() {
return [0u8; 32];
}
let n = leaves.len().next_power_of_two();
leaves.resize(n, [0u8; 32]);
while leaves.len() > 1 {
let mut next = Vec::with_capacity(leaves.len() / 2);
for pair in leaves.chunks(2) {
next.push(hash_pair(&pair[0], &pair[1]));
}
leaves = next;
}
leaves[0]
}
pub fn piece_hash_from_data(data: &[u8], block_size: usize) -> [u8; 32] {
let mut leaves = Vec::new();
for chunk in data.chunks(block_size) {
leaves.push(hash_leaf(chunk));
}
if leaves.is_empty() {
leaves.push(hash_leaf(&[]));
}
merkle_root(leaves)
}
pub fn piece_layers_byte_len(piece_count: u32) -> usize {
MERKLE_HASH_LEN * piece_count as usize
}
pub fn parse_piece_layer_hashes(raw: &[u8], piece_count: u32) -> Option<Vec<[u8; 32]>> {
let expected = piece_layers_byte_len(piece_count);
if raw.len() != expected {
return None;
}
let mut out = Vec::with_capacity(piece_count as usize);
for chunk in raw.chunks_exact(MERKLE_HASH_LEN) {
let mut hash = [0u8; 32];
hash.copy_from_slice(chunk);
out.push(hash);
}
Some(out)
}
pub fn pieces_root_from_layer(piece_hashes: &[[u8; 32]]) -> [u8; 32] {
merkle_root(piece_hashes.to_vec())
}
pub fn verify_pieces_root(raw: &[u8], piece_count: u32, expected_root: &[u8; 32]) -> bool {
let Some(leaves) = parse_piece_layer_hashes(raw, piece_count) else {
return false;
};
pieces_root_from_layer(&leaves) == *expected_root
}
pub fn build_piece_layers(piece_hashes: &[[u8; 32]]) -> Vec<u8> {
let mut out = Vec::with_capacity(piece_layers_byte_len(piece_hashes.len() as u32));
for hash in piece_hashes {
out.extend_from_slice(hash);
}
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn merkle_root_single_leaf() {
let leaf = hash_leaf(b"abc");
assert_eq!(merkle_root(vec![leaf]), leaf);
}
#[test]
fn merkle_root_two_leaves() {
let a = hash_leaf(b"a");
let b = hash_leaf(b"b");
assert_eq!(merkle_root(vec![a, b]), hash_pair(&a, &b));
}
#[test]
fn piece_hash_from_blocks() {
let data = vec![0u8; MERKLE_BLOCK_SIZE * 2 + 100];
let hash = piece_hash_from_data(&data, MERKLE_BLOCK_SIZE);
assert_ne!(hash, [0u8; 32]);
}
#[test]
fn piece_layers_are_concatenated_hashes() {
let a = hash_leaf(b"a");
let b = hash_leaf(b"b");
let layers = build_piece_layers(&[a, b]);
assert_eq!(layers.len(), 64);
assert_eq!(&layers[..32], &a);
assert_eq!(&layers[32..], &b);
assert!(verify_pieces_root(
&layers,
2,
&pieces_root_from_layer(&[a, b])
));
}
}