Skip to main content

tributary_framework/
merkle.rs

1use core::borrow::Borrow;
2use alloc::boxed::Box;
3use std::io;
4
5use blake2::{
6  digest::{CustomizedInit as _, Update, Digest as _},
7  Blake2b256,
8};
9
10/// The representation of an empty tree.
11pub const EMPTY_TREE: [u8; 32] = [0; 32];
12/// The personalization string used to hash a leaf.
13pub const LEAF_PERSONALIZATION: &[u8] = b"tributary leaf";
14/// The personalization string used to for a branch's hash.
15pub const BRANCH_PERSONALIZATION: &[u8] = b"tributary branch";
16
17/// An item which can update a digest via [`blake2::digest::Update`].
18pub trait Digestible {
19  /// Update the digest with this value.
20  fn update(&self, digest: &mut (impl ?Sized + Update));
21  /// Update the digest with this value, returning the updated digest.
22  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
45/// Compute a Merkle tree's root.
46///
47/// This tree uses BLAKE2b-256 for its hash function. At the start, all leaves are hashed with a
48/// personalization of "tributary leaf". Branches are hashed with a personalization of
49/// "tributary branch".
50///
51/// If a level of the tree is uneven, the last hash is propagated as-is. This means leaves may be
52/// at distinct levels of the tree, but gives each leaf a unique path and does not include any
53/// magic leaves (such as the zero hash for padding).
54///
55/// If the tree is empty, an all-zero hash is returned. If the tree only had a single leaf, the
56/// leaf's hash will be the tree root (having calculated no branches).
57///
58/// This function runs in variable time and MAY panic or have undefined behavior if the iterator's
59/// size is incorrect.
60/*
61  TODO: Confirm this personalization matches vectors from the reference implementation.
62  https://github.com/monero-oxide/monero-oxide/pull/176 showed the `blake2` crate sometimes
63  differs due to API constraints.
64*/
65// TODO: [`core::iter::TrustedLen`]
66pub 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    /*
86      We just initialized each element according to `ExactSizeIterator::len` and asserted its
87      returned length was correct.
88    */
89    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}