fuel_merkle/binary/
in_memory.rs

1use crate::{
2    binary::{
3        self,
4        Primitive,
5    },
6    common::{
7        Bytes32,
8        ProofSet,
9        StorageMap,
10    },
11    storage::Mappable,
12};
13
14/// The table of the Binary Merkle Tree's nodes. [`MerkleTree`] works with it as
15/// a binary array, where the storage key of the node is the `u64` index and
16/// value is the [`Node`](crate::binary::Node).
17#[derive(Debug, Clone)]
18pub struct NodesTable;
19
20impl Mappable for NodesTable {
21    type Key = Self::OwnedKey;
22    type OwnedKey = u64;
23    type OwnedValue = Primitive;
24    type Value = Self::OwnedValue;
25}
26
27type Storage = StorageMap<NodesTable>;
28type BinaryMerkleTree = binary::MerkleTree<NodesTable, Storage>;
29
30#[derive(Debug, Clone)]
31pub struct MerkleTree {
32    tree: BinaryMerkleTree,
33}
34
35impl MerkleTree {
36    pub fn new() -> Self {
37        Self {
38            tree: BinaryMerkleTree::new(Storage::new()),
39        }
40    }
41
42    pub fn push(&mut self, data: &[u8]) {
43        let _ = self.tree.push(data);
44    }
45
46    pub fn root(&self) -> Bytes32 {
47        self.tree.root()
48    }
49
50    pub fn prove(&self, proof_index: u64) -> Option<(Bytes32, ProofSet)> {
51        self.tree.prove(proof_index).ok()
52    }
53
54    pub fn reset(&mut self) {
55        self.tree.reset();
56    }
57}
58
59impl Default for MerkleTree {
60    fn default() -> Self {
61        Self::new()
62    }
63}
64
65#[cfg(test)]
66mod test {
67    use super::*;
68    use binary::{
69        empty_sum,
70        leaf_sum,
71        node_sum,
72    };
73    use fuel_merkle_test_helpers::TEST_DATA;
74
75    #[test]
76    fn root_returns_the_empty_root_for_0_leaves() {
77        let tree = MerkleTree::new();
78
79        let root = tree.root();
80        assert_eq!(root, empty_sum().clone());
81    }
82
83    #[test]
84    fn root_returns_the_merkle_root_for_1_leaf() {
85        let mut tree = MerkleTree::new();
86
87        let data = &TEST_DATA[0..1]; // 1 leaf
88        for datum in data.iter() {
89            tree.push(datum);
90        }
91
92        let leaf_0 = leaf_sum(data[0]);
93
94        let root = tree.root();
95        assert_eq!(root, leaf_0);
96    }
97
98    #[test]
99    fn root_returns_the_merkle_root_for_7_leaves() {
100        let mut tree = MerkleTree::new();
101
102        let data = &TEST_DATA[0..7]; // 7 leaves
103        for datum in data.iter() {
104            tree.push(datum);
105        }
106
107        //               07
108        //              /  \
109        //             /    \
110        //            /      \
111        //           /        \
112        //          /          \
113        //         /            \
114        //       03              11
115        //      /  \            /  \
116        //     /    \          /    \
117        //   01      05      09      \
118        //  /  \    /  \    /  \      \
119        // 00  02  04  06  08  10     12
120        // 00  01  02  03  04  05     06
121
122        let leaf_0 = leaf_sum(data[0]);
123        let leaf_1 = leaf_sum(data[1]);
124        let leaf_2 = leaf_sum(data[2]);
125        let leaf_3 = leaf_sum(data[3]);
126        let leaf_4 = leaf_sum(data[4]);
127        let leaf_5 = leaf_sum(data[5]);
128        let leaf_6 = leaf_sum(data[6]);
129
130        let node_1 = node_sum(&leaf_0, &leaf_1);
131        let node_5 = node_sum(&leaf_2, &leaf_3);
132        let node_3 = node_sum(&node_1, &node_5);
133        let node_9 = node_sum(&leaf_4, &leaf_5);
134        let node_11 = node_sum(&node_9, &leaf_6);
135        let node_7 = node_sum(&node_3, &node_11);
136
137        let root = tree.root();
138        assert_eq!(root, node_7);
139    }
140
141    #[test]
142    fn prove_returns_none_for_0_leaves() {
143        let tree = MerkleTree::new();
144
145        let proof = tree.prove(0);
146        assert!(proof.is_none());
147    }
148
149    #[test]
150    fn prove_returns_none_when_index_is_greater_than_number_of_leaves() {
151        let mut tree = MerkleTree::new();
152
153        let data = &TEST_DATA[0..5]; // 5 leaves
154        for datum in data.iter() {
155            tree.push(datum);
156        }
157
158        let proof = tree.prove(10);
159        assert!(proof.is_none());
160    }
161
162    #[test]
163    fn prove_returns_the_merkle_root_and_proof_set_for_1_leaf() {
164        let mut tree = MerkleTree::new();
165
166        let data = &TEST_DATA[0..1]; // 1 leaf
167        for datum in data.iter() {
168            tree.push(datum);
169        }
170
171        let leaf_0 = leaf_sum(data[0]);
172
173        {
174            let (root, proof_set) = tree.prove(0).unwrap();
175            assert_eq!(root, leaf_0);
176            assert!(proof_set.is_empty());
177        }
178    }
179
180    #[test]
181    fn prove_returns_the_merkle_root_and_proof_set_for_7_leaves() {
182        let mut tree = MerkleTree::new();
183
184        let data = &TEST_DATA[0..7]; // 7 leaves
185        for datum in data.iter() {
186            tree.push(datum);
187        }
188
189        //               07
190        //              /  \
191        //             /    \
192        //            /      \
193        //           /        \
194        //          /          \
195        //         /            \
196        //       03              11
197        //      /  \            /  \
198        //     /    \          /    \
199        //   01      05      09      \
200        //  /  \    /  \    /  \      \
201        // 00  02  04  06  08  10     12
202        // 00  01  02  03  04  05     06
203
204        let leaf_0 = leaf_sum(data[0]);
205        let leaf_1 = leaf_sum(data[1]);
206        let leaf_2 = leaf_sum(data[2]);
207        let leaf_3 = leaf_sum(data[3]);
208        let leaf_4 = leaf_sum(data[4]);
209        let leaf_5 = leaf_sum(data[5]);
210        let leaf_6 = leaf_sum(data[6]);
211
212        let node_1 = node_sum(&leaf_0, &leaf_1);
213        let node_5 = node_sum(&leaf_2, &leaf_3);
214        let node_3 = node_sum(&node_1, &node_5);
215        let node_9 = node_sum(&leaf_4, &leaf_5);
216        let node_11 = node_sum(&node_9, &leaf_6);
217        let node_7 = node_sum(&node_3, &node_11);
218
219        {
220            let (root, proof_set) = tree.prove(0).unwrap();
221            assert_eq!(root, node_7);
222            assert_eq!(proof_set[0], leaf_1);
223            assert_eq!(proof_set[1], node_5);
224            assert_eq!(proof_set[2], node_11);
225        }
226        {
227            let (root, proof_set) = tree.prove(1).unwrap();
228            assert_eq!(root, node_7);
229            assert_eq!(proof_set[0], leaf_0);
230            assert_eq!(proof_set[1], node_5);
231            assert_eq!(proof_set[2], node_11);
232        }
233        {
234            let (root, proof_set) = tree.prove(2).unwrap();
235            assert_eq!(root, node_7);
236            assert_eq!(proof_set[0], leaf_3);
237            assert_eq!(proof_set[1], node_1);
238            assert_eq!(proof_set[2], node_11);
239        }
240        {
241            let (root, proof_set) = tree.prove(3).unwrap();
242            assert_eq!(root, node_7);
243            assert_eq!(proof_set[0], leaf_2);
244            assert_eq!(proof_set[1], node_1);
245            assert_eq!(proof_set[2], node_11);
246        }
247        {
248            let (root, proof_set) = tree.prove(4).unwrap();
249            assert_eq!(root, node_7);
250            assert_eq!(proof_set[0], leaf_5);
251            assert_eq!(proof_set[1], leaf_6);
252            assert_eq!(proof_set[2], node_3);
253        }
254        {
255            let (root, proof_set) = tree.prove(5).unwrap();
256            assert_eq!(root, node_7);
257            assert_eq!(proof_set[0], leaf_4);
258            assert_eq!(proof_set[1], leaf_6);
259            assert_eq!(proof_set[2], node_3);
260        }
261        {
262            let (root, proof_set) = tree.prove(6).unwrap();
263            assert_eq!(root, node_7);
264            assert_eq!(proof_set[0], node_9);
265            assert_eq!(proof_set[1], node_3);
266        }
267    }
268}
fuel_merkle/binary/in_memory.rs

fuel_merkle/binary/
in_memory.rs
