miden-crypto/src/merkle/mmr/tests.rs
src/merkle/mmr/tests.rsRaw
1use super::bit::TrueBitPositionIterator;
2use super::full::{high_bitmask, leaf_to_corresponding_tree, nodes_in_forest};
3use super::{
4 super::{InnerNodeInfo, Vec, WORD_SIZE, ZERO},
5 Mmr, MmrPeaks, Rpo256, Word,
6};
7use crate::merkle::{int_to_node, MerklePath};
8
9#[test]
10fn test_position_equal_or_higher_than_leafs_is_never_contained() {
11 let empty_forest = 0;
12 for pos in 1..1024 {
13 // pos is index, 0 based
14 // tree is a length counter, 1 based
15 // so a valid pos is always smaller, not equal, to tree
16 assert_eq!(leaf_to_corresponding_tree(pos, pos), None);
17 assert_eq!(leaf_to_corresponding_tree(pos, pos - 1), None);
18 // and empty forest has no trees, so no position is valid
19 assert_eq!(leaf_to_corresponding_tree(pos, empty_forest), None);
20 }
21}
22
23#[test]
24fn test_position_zero_is_always_contained_by_the_highest_tree() {
25 for leaves in 1..1024usize {
26 let tree = leaves.ilog2();
27 assert_eq!(leaf_to_corresponding_tree(0, leaves), Some(tree));
28 }
29}
30
31#[test]
32fn test_leaf_to_corresponding_tree() {
33 assert_eq!(leaf_to_corresponding_tree(0, 0b0001), Some(0));
34 assert_eq!(leaf_to_corresponding_tree(0, 0b0010), Some(1));
35 assert_eq!(leaf_to_corresponding_tree(0, 0b0011), Some(1));
36 assert_eq!(leaf_to_corresponding_tree(0, 0b1011), Some(3));
37
38 // position one is always owned by the left-most tree
39 assert_eq!(leaf_to_corresponding_tree(1, 0b0010), Some(1));
40 assert_eq!(leaf_to_corresponding_tree(1, 0b0011), Some(1));
41 assert_eq!(leaf_to_corresponding_tree(1, 0b1011), Some(3));
42
43 // position two starts as its own root, and then it is merged with the left-most tree
44 assert_eq!(leaf_to_corresponding_tree(2, 0b0011), Some(0));
45 assert_eq!(leaf_to_corresponding_tree(2, 0b0100), Some(2));
46 assert_eq!(leaf_to_corresponding_tree(2, 0b1011), Some(3));
47
48 // position tree is merged on the left-most tree
49 assert_eq!(leaf_to_corresponding_tree(3, 0b0011), None);
50 assert_eq!(leaf_to_corresponding_tree(3, 0b0100), Some(2));
51 assert_eq!(leaf_to_corresponding_tree(3, 0b1011), Some(3));
52
53 assert_eq!(leaf_to_corresponding_tree(4, 0b0101), Some(0));
54 assert_eq!(leaf_to_corresponding_tree(4, 0b0110), Some(1));
55 assert_eq!(leaf_to_corresponding_tree(4, 0b0111), Some(1));
56 assert_eq!(leaf_to_corresponding_tree(4, 0b1000), Some(3));
57
58 assert_eq!(leaf_to_corresponding_tree(12, 0b01101), Some(0));
59 assert_eq!(leaf_to_corresponding_tree(12, 0b01110), Some(1));
60 assert_eq!(leaf_to_corresponding_tree(12, 0b01111), Some(1));
61 assert_eq!(leaf_to_corresponding_tree(12, 0b10000), Some(4));
62}
63
64#[test]
65fn test_high_bitmask() {
66 assert_eq!(high_bitmask(0), usize::MAX);
67 assert_eq!(high_bitmask(1), usize::MAX << 1);
68 assert_eq!(high_bitmask(usize::BITS - 2), 0b11usize.rotate_right(2));
69 assert_eq!(high_bitmask(usize::BITS - 1), 0b1usize.rotate_right(1));
70 assert_eq!(high_bitmask(usize::BITS), 0, "overflow should be handled");
71}
72
73#[test]
74fn test_nodes_in_forest() {
75 assert_eq!(nodes_in_forest(0b0000), 0);
76 assert_eq!(nodes_in_forest(0b0001), 1);
77 assert_eq!(nodes_in_forest(0b0010), 3);
78 assert_eq!(nodes_in_forest(0b0011), 4);
79 assert_eq!(nodes_in_forest(0b0100), 7);
80 assert_eq!(nodes_in_forest(0b0101), 8);
81 assert_eq!(nodes_in_forest(0b0110), 10);
82 assert_eq!(nodes_in_forest(0b0111), 11);
83 assert_eq!(nodes_in_forest(0b1000), 15);
84 assert_eq!(nodes_in_forest(0b1001), 16);
85 assert_eq!(nodes_in_forest(0b1010), 18);
86 assert_eq!(nodes_in_forest(0b1011), 19);
87}
88
89#[test]
90fn test_nodes_in_forest_single_bit() {
91 assert_eq!(nodes_in_forest(2usize.pow(0)), 2usize.pow(1) - 1);
92 assert_eq!(nodes_in_forest(2usize.pow(1)), 2usize.pow(2) - 1);
93 assert_eq!(nodes_in_forest(2usize.pow(2)), 2usize.pow(3) - 1);
94 assert_eq!(nodes_in_forest(2usize.pow(3)), 2usize.pow(4) - 1);
95
96 for bit in 0..(usize::BITS - 1) {
97 let size = 2usize.pow(bit + 1) - 1;
98 assert_eq!(nodes_in_forest(1usize << bit), size);
99 }
100}
101
102const LEAVES: [Word; 7] = [
103 int_to_node(0),
104 int_to_node(1),
105 int_to_node(2),
106 int_to_node(3),
107 int_to_node(4),
108 int_to_node(5),
109 int_to_node(6),
110];
111
112#[test]
113fn test_mmr_simple() {
114 let mut postorder = Vec::new();
115 postorder.push(LEAVES[0]);
116 postorder.push(LEAVES[1]);
117 postorder.push(*Rpo256::hash_elements(&[LEAVES[0], LEAVES[1]].concat()));
118 postorder.push(LEAVES[2]);
119 postorder.push(LEAVES[3]);
120 postorder.push(*Rpo256::hash_elements(&[LEAVES[2], LEAVES[3]].concat()));
121 postorder.push(*Rpo256::hash_elements(&[postorder[2], postorder[5]].concat()));
122 postorder.push(LEAVES[4]);
123 postorder.push(LEAVES[5]);
124 postorder.push(*Rpo256::hash_elements(&[LEAVES[4], LEAVES[5]].concat()));
125 postorder.push(LEAVES[6]);
126
127 let mut mmr = Mmr::new();
128 assert_eq!(mmr.forest(), 0);
129 assert_eq!(mmr.nodes.len(), 0);
130
131 mmr.add(LEAVES[0]);
132 assert_eq!(mmr.forest(), 1);
133 assert_eq!(mmr.nodes.len(), 1);
134 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
135
136 let acc = mmr.accumulator();
137 assert_eq!(acc.num_leaves, 1);
138 assert_eq!(acc.peaks, &[postorder[0]]);
139
140 mmr.add(LEAVES[1]);
141 assert_eq!(mmr.forest(), 2);
142 assert_eq!(mmr.nodes.len(), 3);
143 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
144
145 let acc = mmr.accumulator();
146 assert_eq!(acc.num_leaves, 2);
147 assert_eq!(acc.peaks, &[postorder[2]]);
148
149 mmr.add(LEAVES[2]);
150 assert_eq!(mmr.forest(), 3);
151 assert_eq!(mmr.nodes.len(), 4);
152 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
153
154 let acc = mmr.accumulator();
155 assert_eq!(acc.num_leaves, 3);
156 assert_eq!(acc.peaks, &[postorder[2], postorder[3]]);
157
158 mmr.add(LEAVES[3]);
159 assert_eq!(mmr.forest(), 4);
160 assert_eq!(mmr.nodes.len(), 7);
161 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
162
163 let acc = mmr.accumulator();
164 assert_eq!(acc.num_leaves, 4);
165 assert_eq!(acc.peaks, &[postorder[6]]);
166
167 mmr.add(LEAVES[4]);
168 assert_eq!(mmr.forest(), 5);
169 assert_eq!(mmr.nodes.len(), 8);
170 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
171
172 let acc = mmr.accumulator();
173 assert_eq!(acc.num_leaves, 5);
174 assert_eq!(acc.peaks, &[postorder[6], postorder[7]]);
175
176 mmr.add(LEAVES[5]);
177 assert_eq!(mmr.forest(), 6);
178 assert_eq!(mmr.nodes.len(), 10);
179 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
180
181 let acc = mmr.accumulator();
182 assert_eq!(acc.num_leaves, 6);
183 assert_eq!(acc.peaks, &[postorder[6], postorder[9]]);
184
185 mmr.add(LEAVES[6]);
186 assert_eq!(mmr.forest(), 7);
187 assert_eq!(mmr.nodes.len(), 11);
188 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
189
190 let acc = mmr.accumulator();
191 assert_eq!(acc.num_leaves, 7);
192 assert_eq!(acc.peaks, &[postorder[6], postorder[9], postorder[10]]);
193}
194
195#[test]
196fn test_mmr_open() {
197 let mmr: Mmr = LEAVES.into();
198 let h01: Word = Rpo256::hash_elements(&LEAVES[0..2].concat()).into();
199 let h23: Word = Rpo256::hash_elements(&LEAVES[2..4].concat()).into();
200
201 // node at pos 7 is the root
202 assert!(mmr.open(7).is_err(), "Element 7 is not in the tree, result should be None");
203
204 // node at pos 6 is the root
205 let empty: MerklePath = MerklePath::new(vec![]);
206 let opening = mmr
207 .open(6)
208 .expect("Element 6 is contained in the tree, expected an opening result.");
209 assert_eq!(opening.merkle_path, empty);
210 assert_eq!(opening.forest, mmr.forest);
211 assert_eq!(opening.position, 6);
212 assert!(
213 mmr.accumulator().verify(LEAVES[6], opening),
214 "MmrProof should be valid for the current accumulator."
215 );
216
217 // nodes 4,5 are detph 1
218 let root_to_path = MerklePath::new(vec![LEAVES[4]]);
219 let opening = mmr
220 .open(5)
221 .expect("Element 5 is contained in the tree, expected an opening result.");
222 assert_eq!(opening.merkle_path, root_to_path);
223 assert_eq!(opening.forest, mmr.forest);
224 assert_eq!(opening.position, 5);
225 assert!(
226 mmr.accumulator().verify(LEAVES[5], opening),
227 "MmrProof should be valid for the current accumulator."
228 );
229
230 let root_to_path = MerklePath::new(vec![LEAVES[5]]);
231 let opening = mmr
232 .open(4)
233 .expect("Element 4 is contained in the tree, expected an opening result.");
234 assert_eq!(opening.merkle_path, root_to_path);
235 assert_eq!(opening.forest, mmr.forest);
236 assert_eq!(opening.position, 4);
237 assert!(
238 mmr.accumulator().verify(LEAVES[4], opening),
239 "MmrProof should be valid for the current accumulator."
240 );
241
242 // nodes 0,1,2,3 are detph 2
243 let root_to_path = MerklePath::new(vec![LEAVES[2], h01]);
244 let opening = mmr
245 .open(3)
246 .expect("Element 3 is contained in the tree, expected an opening result.");
247 assert_eq!(opening.merkle_path, root_to_path);
248 assert_eq!(opening.forest, mmr.forest);
249 assert_eq!(opening.position, 3);
250 assert!(
251 mmr.accumulator().verify(LEAVES[3], opening),
252 "MmrProof should be valid for the current accumulator."
253 );
254
255 let root_to_path = MerklePath::new(vec![LEAVES[3], h01]);
256 let opening = mmr
257 .open(2)
258 .expect("Element 2 is contained in the tree, expected an opening result.");
259 assert_eq!(opening.merkle_path, root_to_path);
260 assert_eq!(opening.forest, mmr.forest);
261 assert_eq!(opening.position, 2);
262 assert!(
263 mmr.accumulator().verify(LEAVES[2], opening),
264 "MmrProof should be valid for the current accumulator."
265 );
266
267 let root_to_path = MerklePath::new(vec![LEAVES[0], h23]);
268 let opening = mmr
269 .open(1)
270 .expect("Element 1 is contained in the tree, expected an opening result.");
271 assert_eq!(opening.merkle_path, root_to_path);
272 assert_eq!(opening.forest, mmr.forest);
273 assert_eq!(opening.position, 1);
274 assert!(
275 mmr.accumulator().verify(LEAVES[1], opening),
276 "MmrProof should be valid for the current accumulator."
277 );
278
279 let root_to_path = MerklePath::new(vec![LEAVES[1], h23]);
280 let opening = mmr
281 .open(0)
282 .expect("Element 0 is contained in the tree, expected an opening result.");
283 assert_eq!(opening.merkle_path, root_to_path);
284 assert_eq!(opening.forest, mmr.forest);
285 assert_eq!(opening.position, 0);
286 assert!(
287 mmr.accumulator().verify(LEAVES[0], opening),
288 "MmrProof should be valid for the current accumulator."
289 );
290}
291
292#[test]
293fn test_mmr_get() {
294 let mmr: Mmr = LEAVES.into();
295 assert_eq!(mmr.get(0).unwrap(), LEAVES[0], "value at pos 0 must correspond");
296 assert_eq!(mmr.get(1).unwrap(), LEAVES[1], "value at pos 1 must correspond");
297 assert_eq!(mmr.get(2).unwrap(), LEAVES[2], "value at pos 2 must correspond");
298 assert_eq!(mmr.get(3).unwrap(), LEAVES[3], "value at pos 3 must correspond");
299 assert_eq!(mmr.get(4).unwrap(), LEAVES[4], "value at pos 4 must correspond");
300 assert_eq!(mmr.get(5).unwrap(), LEAVES[5], "value at pos 5 must correspond");
301 assert_eq!(mmr.get(6).unwrap(), LEAVES[6], "value at pos 6 must correspond");
302 assert!(mmr.get(7).is_err());
303}
304
305#[test]
306fn test_mmr_invariants() {
307 let mut mmr = Mmr::new();
308 for v in 1..=1028 {
309 mmr.add(int_to_node(v));
310 let accumulator = mmr.accumulator();
311 assert_eq!(v as usize, mmr.forest(), "MMR leaf count must increase by one on every add");
312 assert_eq!(
313 v as usize, accumulator.num_leaves,
314 "MMR and its accumulator must match leaves count"
315 );
316 assert_eq!(
317 accumulator.num_leaves.count_ones() as usize,
318 accumulator.peaks.len(),
319 "bits on leaves must match the number of peaks"
320 );
321
322 let expected_nodes: usize = TrueBitPositionIterator::new(mmr.forest())
323 .map(|bit_pos| nodes_in_forest(1 << bit_pos))
324 .sum();
325
326 assert_eq!(
327 expected_nodes,
328 mmr.nodes.len(),
329 "the sum of every tree size must be equal to the number of nodes in the MMR (forest: {:b})",
330 mmr.forest(),
331 );
332 }
333}
334
335#[test]
336fn test_bit_position_iterator() {
337 assert_eq!(TrueBitPositionIterator::new(0).count(), 0);
338 assert_eq!(TrueBitPositionIterator::new(0).rev().count(), 0);
339
340 assert_eq!(TrueBitPositionIterator::new(1).collect::<Vec<u32>>(), vec![0]);
341 assert_eq!(TrueBitPositionIterator::new(1).rev().collect::<Vec<u32>>(), vec![0],);
342
343 assert_eq!(TrueBitPositionIterator::new(2).collect::<Vec<u32>>(), vec![1]);
344 assert_eq!(TrueBitPositionIterator::new(2).rev().collect::<Vec<u32>>(), vec![1],);
345
346 assert_eq!(TrueBitPositionIterator::new(3).collect::<Vec<u32>>(), vec![0, 1],);
347 assert_eq!(TrueBitPositionIterator::new(3).rev().collect::<Vec<u32>>(), vec![1, 0],);
348
349 assert_eq!(
350 TrueBitPositionIterator::new(0b11010101).collect::<Vec<u32>>(),
351 vec![0, 2, 4, 6, 7],
352 );
353 assert_eq!(
354 TrueBitPositionIterator::new(0b11010101).rev().collect::<Vec<u32>>(),
355 vec![7, 6, 4, 2, 0],
356 );
357}
358
359#[test]
360fn test_mmr_inner_nodes() {
361 let mmr: Mmr = LEAVES.into();
362 let nodes: Vec<InnerNodeInfo> = mmr.inner_nodes().collect();
363
364 let h01 = *Rpo256::hash_elements(&[LEAVES[0], LEAVES[1]].concat());
365 let h23 = *Rpo256::hash_elements(&[LEAVES[2], LEAVES[3]].concat());
366 let h0123 = *Rpo256::hash_elements(&[h01, h23].concat());
367 let h45 = *Rpo256::hash_elements(&[LEAVES[4], LEAVES[5]].concat());
368 let postorder = vec![
369 InnerNodeInfo {
370 value: h01,
371 left: LEAVES[0],
372 right: LEAVES[1],
373 },
374 InnerNodeInfo {
375 value: h23,
376 left: LEAVES[2],
377 right: LEAVES[3],
378 },
379 InnerNodeInfo {
380 value: h0123,
381 left: h01,
382 right: h23,
383 },
384 InnerNodeInfo {
385 value: h45,
386 left: LEAVES[4],
387 right: LEAVES[5],
388 },
389 ];
390
391 assert_eq!(postorder, nodes);
392}
393
394#[test]
395fn test_mmr_hash_peaks() {
396 let mmr: Mmr = LEAVES.into();
397 let peaks = mmr.accumulator();
398
399 let first_peak = *Rpo256::merge(&[
400 Rpo256::hash_elements(&[LEAVES[0], LEAVES[1]].concat()),
401 Rpo256::hash_elements(&[LEAVES[2], LEAVES[3]].concat()),
402 ]);
403 let second_peak = *Rpo256::hash_elements(&[LEAVES[4], LEAVES[5]].concat());
404 let third_peak = LEAVES[6];
405
406 // minimum length is 16
407 let mut expected_peaks = [first_peak, second_peak, third_peak].to_vec();
408 expected_peaks.resize(16, [ZERO; WORD_SIZE]);
409 assert_eq!(peaks.hash_peaks(), *Rpo256::hash_elements(&expected_peaks.as_slice().concat()));
410}
411
412#[test]
413fn test_mmr_peaks_hash_less_than_16() {
414 let mut peaks = Vec::new();
415
416 for i in 0..16 {
417 peaks.push(int_to_node(i));
418 let accumulator = MmrPeaks {
419 num_leaves: (1 << peaks.len()) - 1,
420 peaks: peaks.clone(),
421 };
422
423 // minimum length is 16
424 let mut expected_peaks = peaks.clone();
425 expected_peaks.resize(16, [ZERO; WORD_SIZE]);
426 assert_eq!(
427 accumulator.hash_peaks(),
428 *Rpo256::hash_elements(&expected_peaks.as_slice().concat())
429 );
430 }
431}
432
433#[test]
434fn test_mmr_peaks_hash_odd() {
435 let peaks: Vec<_> = (0..=17).map(|i| int_to_node(i)).collect();
436
437 let accumulator = MmrPeaks {
438 num_leaves: (1 << peaks.len()) - 1,
439 peaks: peaks.clone(),
440 };
441
442 // odd length bigger than 16 is padded to the next even nubmer
443 let mut expected_peaks = peaks.clone();
444 expected_peaks.resize(18, [ZERO; WORD_SIZE]);
445 assert_eq!(
446 accumulator.hash_peaks(),
447 *Rpo256::hash_elements(&expected_peaks.as_slice().concat())
448 );
449}
450
451mod property_tests {
452 use super::leaf_to_corresponding_tree;
453 use proptest::prelude::*;
454
455 proptest! {
456 #[test]
457 fn test_last_position_is_always_contained_in_the_last_tree(leaves in any::<usize>().prop_filter("cant have an empty tree", |v| *v != 0)) {
458 let last_pos = leaves - 1;
459 let lowest_bit = leaves.trailing_zeros();
460
461 assert_eq!(
462 leaf_to_corresponding_tree(last_pos, leaves),
463 Some(lowest_bit),
464 );
465 }
466 }
467
468 proptest! {
469 #[test]
470 fn test_contained_tree_is_always_power_of_two((leaves, pos) in any::<usize>().prop_flat_map(|v| (Just(v), 0..v))) {
471 let tree = leaf_to_corresponding_tree(pos, leaves).expect("pos is smaller than leaves, there should always be a corresponding tree");
472 let mask = 1usize << tree;
473
474 assert!(tree < usize::BITS, "the result must be a bit in usize");
475 assert!(mask & leaves != 0, "the result should be a tree in leaves");
476 }
477 }
478}