use core::borrow::Borrow;
use alloc::boxed::Box;
use std::io;
use blake2::{
digest::{CustomizedInit as _, Update, Digest as _},
Blake2b256,
};
pub const EMPTY_TREE: [u8; 32] = [0; 32];
pub const LEAF_PERSONALIZATION: &[u8] = b"tributary leaf";
pub const BRANCH_PERSONALIZATION: &[u8] = b"tributary branch";
pub trait Digestible {
fn update(&self, digest: &mut (impl ?Sized + Update));
fn chain_update<U: Update>(&self, mut digest: U) -> U {
self.update(&mut digest);
digest
}
}
impl<B: ?Sized + AsRef<[u8]>> Digestible for B {
fn update(&self, digest: &mut (impl ?Sized + Update)) {
digest.update(self.as_ref());
}
}
pub(crate) struct DigestWriter<'digest, U: ?Sized + Update>(pub(crate) &'digest mut U);
impl<U: ?Sized + Update> io::Write for DigestWriter<'_, U> {
fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
self.0.update(buf);
Ok(buf.len())
}
fn flush(&mut self) -> io::Result<()> {
Ok(())
}
}
pub fn root<D: ?Sized + Digestible>(
leaves: impl IntoIterator<Item = impl Borrow<D>, IntoIter: ExactSizeIterator>,
) -> [u8; 32] {
let mut scratch = {
let leaves = leaves.into_iter();
let mut scratch = Box::<[[u8; 32]]>::new_uninit_slice(leaves.len());
let mut len = 0;
for (scratch, leaf) in scratch.iter_mut().zip(leaves) {
scratch.write(
leaf
.borrow()
.chain_update(Blake2b256::new_customized(LEAF_PERSONALIZATION))
.finalize()
.into(),
);
len += 1;
}
assert_eq!(scratch.len(), len, "`ExactSizeIterator::len` was incorrect");
unsafe { scratch.assume_init() }
};
let mut scratch = scratch.as_mut();
while scratch.len() > 1 {
let pairs = scratch.len() / 2;
for i in 0 .. pairs {
scratch[i] = Blake2b256::new_customized(BRANCH_PERSONALIZATION)
.chain_update(scratch[2 * i])
.chain_update(scratch[(2 * i) + 1])
.finalize()
.into();
}
let new_len = if (scratch.len() % 2) == 1 {
scratch[pairs] = *scratch.last().unwrap();
pairs + 1
} else {
pairs
};
scratch = &mut scratch[.. new_len];
}
scratch.first().copied().unwrap_or(EMPTY_TREE)
}
#[test]
fn merkle_tree_root() {
use alloc::{vec::Vec, vec};
use rand::{RngCore as _, rngs::OsRng};
fn root2(leaves: &[[u8; 64]]) -> [u8; 32] {
if leaves.is_empty() {
return [0; 32];
}
let mut leaves = leaves
.iter()
.map(|leaf| Blake2b256::new_customized(b"tributary leaf").chain_update(leaf).finalize())
.collect::<Vec<_>>();
while leaves.len() != 1 {
let (chunks, extra) = leaves.as_chunks::<2>();
let mut new_leaves = vec![];
for [l, r] in chunks {
new_leaves.push(
Blake2b256::new_customized(b"tributary branch")
.chain_update(l)
.chain_update(r)
.finalize(),
);
}
assert!(extra.len() <= 1);
for extra in extra {
new_leaves.push(*extra);
}
leaves = new_leaves;
}
leaves[0].into()
}
assert_eq!(root::<[u8; 0]>(&[]), root2(&[]));
for len in 1 .. 32 {
let mut leaves = vec![[0xff; 64]; len];
for leaf in &mut leaves {
OsRng.fill_bytes(leaf);
}
assert_eq!(root::<[u8; 64]>(leaves.iter()), root2(&leaves));
}
}