tributary_framework/
merkle.rs1use core::borrow::Borrow;
2use alloc::boxed::Box;
3use std::io;
4
5use blake2::{
6 digest::{CustomizedInit as _, Update, Digest as _},
7 Blake2b256,
8};
9
10pub const EMPTY_TREE: [u8; 32] = [0; 32];
12pub const LEAF_PERSONALIZATION: &[u8] = b"tributary leaf";
14pub const BRANCH_PERSONALIZATION: &[u8] = b"tributary branch";
16
17pub trait Digestible {
19 fn update(&self, digest: &mut (impl ?Sized + Update));
21 fn chain_update<U: Update>(&self, mut digest: U) -> U {
23 self.update(&mut digest);
24 digest
25 }
26}
27
28impl<B: ?Sized + AsRef<[u8]>> Digestible for B {
29 fn update(&self, digest: &mut (impl ?Sized + Update)) {
30 digest.update(self.as_ref());
31 }
32}
33
34pub(crate) struct DigestWriter<'digest, U: ?Sized + Update>(pub(crate) &'digest mut U);
35impl<U: ?Sized + Update> io::Write for DigestWriter<'_, U> {
36 fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
37 self.0.update(buf);
38 Ok(buf.len())
39 }
40 fn flush(&mut self) -> io::Result<()> {
41 Ok(())
42 }
43}
44
45pub fn root<D: ?Sized + Digestible>(
67 leaves: impl IntoIterator<Item = impl Borrow<D>, IntoIter: ExactSizeIterator>,
68) -> [u8; 32] {
69 let mut scratch = {
70 let leaves = leaves.into_iter();
71 let mut scratch = Box::<[[u8; 32]]>::new_uninit_slice(leaves.len());
72 let mut len = 0;
73 for (scratch, leaf) in scratch.iter_mut().zip(leaves) {
74 scratch.write(
75 leaf
76 .borrow()
77 .chain_update(Blake2b256::new_customized(LEAF_PERSONALIZATION))
78 .finalize()
79 .into(),
80 );
81 len += 1;
82 }
83 assert_eq!(scratch.len(), len, "`ExactSizeIterator::len` was incorrect");
84
85 unsafe { scratch.assume_init() }
90 };
91 let mut scratch = scratch.as_mut();
92
93 while scratch.len() > 1 {
94 let pairs = scratch.len() / 2;
95 for i in 0 .. pairs {
96 scratch[i] = Blake2b256::new_customized(BRANCH_PERSONALIZATION)
97 .chain_update(scratch[2 * i])
98 .chain_update(scratch[(2 * i) + 1])
99 .finalize()
100 .into();
101 }
102
103 let new_len = if (scratch.len() % 2) == 1 {
104 scratch[pairs] = *scratch.last().unwrap();
105 pairs + 1
106 } else {
107 pairs
108 };
109
110 scratch = &mut scratch[.. new_len];
111 }
112
113 scratch.first().copied().unwrap_or(EMPTY_TREE)
114}
115
116#[test]
117fn merkle_tree_root() {
118 use alloc::{vec::Vec, vec};
119 use rand::{RngCore as _, rngs::OsRng};
120
121 fn root2(leaves: &[[u8; 64]]) -> [u8; 32] {
122 if leaves.is_empty() {
123 return [0; 32];
124 }
125 let mut leaves = leaves
126 .iter()
127 .map(|leaf| Blake2b256::new_customized(b"tributary leaf").chain_update(leaf).finalize())
128 .collect::<Vec<_>>();
129
130 while leaves.len() != 1 {
131 let (chunks, extra) = leaves.as_chunks::<2>();
132 let mut new_leaves = vec![];
133 for [l, r] in chunks {
134 new_leaves.push(
135 Blake2b256::new_customized(b"tributary branch")
136 .chain_update(l)
137 .chain_update(r)
138 .finalize(),
139 );
140 }
141 assert!(extra.len() <= 1);
142 for extra in extra {
143 new_leaves.push(*extra);
144 }
145 leaves = new_leaves;
146 }
147
148 leaves[0].into()
149 }
150
151 assert_eq!(root::<[u8; 0]>(&[]), root2(&[]));
152 for len in 1 .. 32 {
153 let mut leaves = vec![[0xff; 64]; len];
154 for leaf in &mut leaves {
155 OsRng.fill_bytes(leaf);
156 }
157 assert_eq!(root::<[u8; 64]>(leaves.iter()), root2(&leaves));
158 }
159}