1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

//! Crypto implementations for the instructions

use fuel_merkle::binary::root_calculator::MerkleRootCalculator as MerkleTree;
use fuel_types::Bytes32;

/// Calculate a binary merkle root with in-memory storage
pub fn ephemeral_merkle_root<L, I>(leaves: I) -> Bytes32
where
    L: AsRef<[u8]>,
    I: Iterator<Item = L> + ExactSizeIterator,
{
    let mut tree = MerkleTree::new();
    leaves.for_each(|l| tree.push(l.as_ref()));
    tree.root().into()
}

#[test]
#[cfg(feature = "random")]
fn ephemeral_merkle_root_returns_the_expected_root() {
    use fuel_crypto::Hasher;
    use rand::{
        rngs::StdRng,
        Rng,
        SeedableRng,
    };

    use alloc::{
        vec,
        vec::Vec,
    };

    use crate::prelude::*;

    let mut rng = StdRng::seed_from_u64(2322u64);

    const LEAF_PREFIX: u8 = 0x00;
    const NODE_PREFIX: u8 = 0x01;

    // Test for 0 leaves
    //
    // Expected root is `h()`
    let empty: Vec<Address> = vec![];

    let root = ephemeral_merkle_root(empty.iter());
    let empty = Hasher::default().digest();

    assert_eq!(empty, root);

    // Test for 5 leaves
    let a: Address = rng.gen();
    let b: Address = rng.gen();
    let c: Address = rng.gen();
    let d: Address = rng.gen();
    let e: Address = rng.gen();

    let initial = [a, b, c, d, e];

    let a = Hasher::default().chain([LEAF_PREFIX]).chain(a).digest();
    let b = Hasher::default().chain([LEAF_PREFIX]).chain(b).digest();
    let c = Hasher::default().chain([LEAF_PREFIX]).chain(c).digest();
    let d = Hasher::default().chain([LEAF_PREFIX]).chain(d).digest();
    let e = Hasher::default().chain([LEAF_PREFIX]).chain(e).digest();

    let a = Hasher::default()
        .chain([NODE_PREFIX])
        .extend_chain([a, b])
        .digest();
    let b = Hasher::default()
        .chain([NODE_PREFIX])
        .extend_chain([c, d])
        .digest();
    let c = e;

    let a = Hasher::default()
        .chain([NODE_PREFIX])
        .extend_chain([a, b])
        .digest();
    let b = c;

    let root = Hasher::default()
        .chain([NODE_PREFIX])
        .extend_chain([a, b])
        .digest();
    let root_p = ephemeral_merkle_root(initial.iter());

    assert_eq!(root, root_p);
}