monero_oxide/
merkle.rs

1use crate::primitives::keccak256;
2
3/// Calculates the Merkle root for the given leaves.
4///
5/// Equivalent to `tree_hash` in monero-core:
6/// https://github.com/monero-project/monero/blob/893916ad091a92e765ce3241b94e706ad012b62a
7///   /src/crypto/tree-hash.c#L62
8///
9/// Monero's Merkle trees have two notable properties:
10///  1) Merkle trees are unbalanced, causing each leaf to only be included once with a unique
11///     index, without introducing padding.
12///  2) The leaves of a Merkle tree are not distinguished from its branches. This would allow
13///     proving a branch as a leaf, or claiming a leaf is a branch. In order to safely perform
14///     proofs with a tree's root, the amount of leaves within the Merkle tree MUST be known.
15///     Thankfully, Monero uses this to commit to the transactions within a block when calculating
16///     its hash, and the amount of transactions is additionally committed to. Alternatively, one
17///     could assume every valid transaction's serialization will be longer than 64 bytes.
18///
19/// This function accepts a mutable slice for the leaves, using it as scratch space for the
20/// computation of the leaves. The value of this scratch space is undefined after the operation
21/// completes.
22///
23/// This function returns [`None`] if the tree is empty and [`Some`] otherwise.
24pub fn merkle_root(mut leaves: impl AsMut<[[u8; 32]]>) -> Option<[u8; 32]> {
25  let mut leaves = leaves.as_mut();
26
27  let mut pair_buf = [0; 64];
28  let mut pair = |left: &[u8; 32], right: &[u8; 32]| {
29    pair_buf[.. 32].copy_from_slice(left);
30    pair_buf[32 ..].copy_from_slice(right);
31    keccak256(pair_buf)
32  };
33
34  match leaves.len() {
35    0 => None,
36    1 => Some(leaves[0]),
37    2 => Some(pair(&leaves[0], &leaves[1])),
38    _ => {
39      // First, we find the first power of two less than or equal to the amount of leaves
40      let mut low_pow_2 = {
41        let highest_bit_set = usize::BITS - leaves.len().leading_zeros();
42        // This won't underflow as we know _a_ bit is set
43        1 << (highest_bit_set - 1)
44      };
45
46      while leaves.len() != 1 {
47        /*
48          If the amount of leaves is a power of two, reduce to the next power of two (where "next"
49          is defined as "next smaller").
50
51          This condition will only be false for the first iteration, if the amount of leaves input
52          isn't a power of two. Then, `low_pow_2` will already be the next power of two to reduce
53          to.
54        */
55        if leaves.len() == low_pow_2 {
56          low_pow_2 >>= 1;
57        }
58
59        // How many leaves we have to pair off in order to reduce to the next power of two
60        let overage = leaves.len() - low_pow_2;
61        // This choice of `start` means `leaves[start ..].len() == (2 * overage)`
62        let start = low_pow_2 - overage;
63        for i in 0 .. overage {
64          // Take the next pair of leaves
65          let left = leaves[start + (2 * i)];
66          let right = leaves[start + (2 * i) + 1];
67          // Write the branch to its new index
68          leaves[start + i] = pair(&left, &right);
69        }
70        // Truncate now that we've performed the initial pairing off
71        leaves = &mut leaves[.. low_pow_2];
72      }
73
74      Some(leaves[0])
75    }
76  }
77}
monero_oxide/merkle.rs

monero_oxide/
merkle.rs
