monero_oxide/
merkle.rs

1use std_shims::vec::Vec;
2
3use crate::primitives::keccak256;
4
5/// Calculates the Merkle root of the given tree.
6///
7/// Equivalent to `tree_hash` in monero-core:
8/// https://github.com/monero-project/monero/blob/893916ad091a92e765ce3241b94e706ad012b62a
9///   /src/crypto/tree-hash.c#L62
10///
11/// This function returns [`None`] if the tree is empty.
12pub fn merkle_root(mut leafs: Vec<[u8; 32]>) -> Option<[u8; 32]> {
13  match leafs.len() {
14    0 => None,
15    1 => Some(leafs[0]),
16    2 => Some(keccak256([leafs[0], leafs[1]].concat())),
17    _ => {
18      // Monero preprocess this so the length is a power of 2
19      let mut high_pow_2 = 4; // 4 is the lowest value this can be
20      while high_pow_2 < leafs.len() {
21        high_pow_2 *= 2;
22      }
23      let low_pow_2 = high_pow_2 / 2;
24
25      // Merge right-most hashes until we're at the low_pow_2
26      {
27        let overage = leafs.len() - low_pow_2;
28        let mut rightmost = leafs.drain((low_pow_2 - overage) ..);
29        // This is true since we took overage from beneath and above low_pow_2, taking twice as
30        // many elements as overage
31        debug_assert_eq!(rightmost.len() % 2, 0);
32
33        let mut paired_hashes = Vec::with_capacity(overage);
34        while let Some(left) = rightmost.next() {
35          let right = rightmost.next().expect("rightmost is of even length");
36          paired_hashes.push(keccak256([left.as_ref(), &right].concat()));
37        }
38        drop(rightmost);
39
40        leafs.extend(paired_hashes);
41        assert_eq!(leafs.len(), low_pow_2);
42      }
43
44      // Do a traditional pairing off
45      let mut new_hashes = Vec::with_capacity(leafs.len() / 2);
46      while leafs.len() > 1 {
47        let mut i = 0;
48        while i < leafs.len() {
49          new_hashes.push(keccak256([leafs[i], leafs[i + 1]].concat()));
50          i += 2;
51        }
52
53        leafs = new_hashes;
54        new_hashes = Vec::with_capacity(leafs.len() / 2);
55      }
56      Some(leafs[0])
57    }
58  }
59}
monero_oxide/merkle.rs

monero_oxide/
merkle.rs
