monero_serai/
merkle.rs

1use std_shims::vec::Vec;
2
3use crate::primitives::keccak256;
4
5pub(crate) fn merkle_root(root: [u8; 32], leafs: &[[u8; 32]]) -> [u8; 32] {
6  match leafs.len() {
7    0 => root,
8    1 => keccak256([root, leafs[0]].concat()),
9    _ => {
10      let mut hashes = Vec::with_capacity(1 + leafs.len());
11      hashes.push(root);
12      hashes.extend(leafs);
13
14      // Monero preprocess this so the length is a power of 2
15      let mut high_pow_2 = 4; // 4 is the lowest value this can be
16      while high_pow_2 < hashes.len() {
17        high_pow_2 *= 2;
18      }
19      let low_pow_2 = high_pow_2 / 2;
20
21      // Merge right-most hashes until we're at the low_pow_2
22      {
23        let overage = hashes.len() - low_pow_2;
24        let mut rightmost = hashes.drain((low_pow_2 - overage) ..);
25        // This is true since we took overage from beneath and above low_pow_2, taking twice as
26        // many elements as overage
27        debug_assert_eq!(rightmost.len() % 2, 0);
28
29        let mut paired_hashes = Vec::with_capacity(overage);
30        while let Some(left) = rightmost.next() {
31          let right = rightmost.next().unwrap();
32          paired_hashes.push(keccak256([left.as_ref(), &right].concat()));
33        }
34        drop(rightmost);
35
36        hashes.extend(paired_hashes);
37        assert_eq!(hashes.len(), low_pow_2);
38      }
39
40      // Do a traditional pairing off
41      let mut new_hashes = Vec::with_capacity(hashes.len() / 2);
42      while hashes.len() > 1 {
43        let mut i = 0;
44        while i < hashes.len() {
45          new_hashes.push(keccak256([hashes[i], hashes[i + 1]].concat()));
46          i += 2;
47        }
48
49        hashes = new_hashes;
50        new_hashes = Vec::with_capacity(hashes.len() / 2);
51      }
52      hashes[0]
53    }
54  }
55}
monero_serai/merkle.rs

monero_serai/
merkle.rs
