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