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(
122 &[postorder[2], postorder[5]].concat(),
123 ));
124 postorder.push(LEAVES[4]);
125 postorder.push(LEAVES[5]);
126 postorder.push(*Rpo256::hash_elements(&[LEAVES[4], LEAVES[5]].concat()));
127 postorder.push(LEAVES[6]);
128
129 let mut mmr = Mmr::new();
130 assert_eq!(mmr.forest(), 0);
131 assert_eq!(mmr.nodes.len(), 0);
132
133 mmr.add(LEAVES[0]);
134 assert_eq!(mmr.forest(), 1);
135 assert_eq!(mmr.nodes.len(), 1);
136 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
137
138 let acc = mmr.accumulator();
139 assert_eq!(acc.num_leaves, 1);
140 assert_eq!(acc.peaks, &[postorder[0]]);
141
142 mmr.add(LEAVES[1]);
143 assert_eq!(mmr.forest(), 2);
144 assert_eq!(mmr.nodes.len(), 3);
145 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
146
147 let acc = mmr.accumulator();
148 assert_eq!(acc.num_leaves, 2);
149 assert_eq!(acc.peaks, &[postorder[2]]);
150
151 mmr.add(LEAVES[2]);
152 assert_eq!(mmr.forest(), 3);
153 assert_eq!(mmr.nodes.len(), 4);
154 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
155
156 let acc = mmr.accumulator();
157 assert_eq!(acc.num_leaves, 3);
158 assert_eq!(acc.peaks, &[postorder[2], postorder[3]]);
159
160 mmr.add(LEAVES[3]);
161 assert_eq!(mmr.forest(), 4);
162 assert_eq!(mmr.nodes.len(), 7);
163 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
164
165 let acc = mmr.accumulator();
166 assert_eq!(acc.num_leaves, 4);
167 assert_eq!(acc.peaks, &[postorder[6]]);
168
169 mmr.add(LEAVES[4]);
170 assert_eq!(mmr.forest(), 5);
171 assert_eq!(mmr.nodes.len(), 8);
172 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
173
174 let acc = mmr.accumulator();
175 assert_eq!(acc.num_leaves, 5);
176 assert_eq!(acc.peaks, &[postorder[6], postorder[7]]);
177
178 mmr.add(LEAVES[5]);
179 assert_eq!(mmr.forest(), 6);
180 assert_eq!(mmr.nodes.len(), 10);
181 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
182
183 let acc = mmr.accumulator();
184 assert_eq!(acc.num_leaves, 6);
185 assert_eq!(acc.peaks, &[postorder[6], postorder[9]]);
186
187 mmr.add(LEAVES[6]);
188 assert_eq!(mmr.forest(), 7);
189 assert_eq!(mmr.nodes.len(), 11);
190 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
191
192 let acc = mmr.accumulator();
193 assert_eq!(acc.num_leaves, 7);
194 assert_eq!(acc.peaks, &[postorder[6], postorder[9], postorder[10]]);
195}
196
197#[test]
198fn test_mmr_open() {
199 let mmr: Mmr = LEAVES.into();
200 let h01: Word = Rpo256::hash_elements(&LEAVES[0..2].concat()).into();
201 let h23: Word = Rpo256::hash_elements(&LEAVES[2..4].concat()).into();
202
203 // node at pos 7 is the root
204 assert!(
205 mmr.open(7).is_err(),
206 "Element 7 is not in the tree, result should be None"
207 );
208
209 // node at pos 6 is the root
210 let empty: MerklePath = MerklePath::new(vec![]);
211 let opening = mmr
212 .open(6)
213 .expect("Element 6 is contained in the tree, expected an opening result.");
214 assert_eq!(opening.merkle_path, empty);
215 assert_eq!(opening.forest, mmr.forest);
216 assert_eq!(opening.position, 6);
217 assert!(
218 mmr.accumulator().verify(LEAVES[6], opening),
219 "MmrProof should be valid for the current accumulator."
220 );
221
222 // nodes 4,5 are detph 1
223 let root_to_path = MerklePath::new(vec![LEAVES[4]]);
224 let opening = mmr
225 .open(5)
226 .expect("Element 5 is contained in the tree, expected an opening result.");
227 assert_eq!(opening.merkle_path, root_to_path);
228 assert_eq!(opening.forest, mmr.forest);
229 assert_eq!(opening.position, 5);
230 assert!(
231 mmr.accumulator().verify(LEAVES[5], opening),
232 "MmrProof should be valid for the current accumulator."
233 );
234
235 let root_to_path = MerklePath::new(vec![LEAVES[5]]);
236 let opening = mmr
237 .open(4)
238 .expect("Element 4 is contained in the tree, expected an opening result.");
239 assert_eq!(opening.merkle_path, root_to_path);
240 assert_eq!(opening.forest, mmr.forest);
241 assert_eq!(opening.position, 4);
242 assert!(
243 mmr.accumulator().verify(LEAVES[4], opening),
244 "MmrProof should be valid for the current accumulator."
245 );
246
247 // nodes 0,1,2,3 are detph 2
248 let root_to_path = MerklePath::new(vec![LEAVES[2], h01]);
249 let opening = mmr
250 .open(3)
251 .expect("Element 3 is contained in the tree, expected an opening result.");
252 assert_eq!(opening.merkle_path, root_to_path);
253 assert_eq!(opening.forest, mmr.forest);
254 assert_eq!(opening.position, 3);
255 assert!(
256 mmr.accumulator().verify(LEAVES[3], opening),
257 "MmrProof should be valid for the current accumulator."
258 );
259
260 let root_to_path = MerklePath::new(vec![LEAVES[3], h01]);
261 let opening = mmr
262 .open(2)
263 .expect("Element 2 is contained in the tree, expected an opening result.");
264 assert_eq!(opening.merkle_path, root_to_path);
265 assert_eq!(opening.forest, mmr.forest);
266 assert_eq!(opening.position, 2);
267 assert!(
268 mmr.accumulator().verify(LEAVES[2], opening),
269 "MmrProof should be valid for the current accumulator."
270 );
271
272 let root_to_path = MerklePath::new(vec![LEAVES[0], h23]);
273 let opening = mmr
274 .open(1)
275 .expect("Element 1 is contained in the tree, expected an opening result.");
276 assert_eq!(opening.merkle_path, root_to_path);
277 assert_eq!(opening.forest, mmr.forest);
278 assert_eq!(opening.position, 1);
279 assert!(
280 mmr.accumulator().verify(LEAVES[1], opening),
281 "MmrProof should be valid for the current accumulator."
282 );
283
284 let root_to_path = MerklePath::new(vec![LEAVES[1], h23]);
285 let opening = mmr
286 .open(0)
287 .expect("Element 0 is contained in the tree, expected an opening result.");
288 assert_eq!(opening.merkle_path, root_to_path);
289 assert_eq!(opening.forest, mmr.forest);
290 assert_eq!(opening.position, 0);
291 assert!(
292 mmr.accumulator().verify(LEAVES[0], opening),
293 "MmrProof should be valid for the current accumulator."
294 );
295}
296
297#[test]
298fn test_mmr_get() {
299 let mmr: Mmr = LEAVES.into();
300 assert_eq!(
301 mmr.get(0).unwrap(),
302 LEAVES[0],
303 "value at pos 0 must correspond"
304 );
305 assert_eq!(
306 mmr.get(1).unwrap(),
307 LEAVES[1],
308 "value at pos 1 must correspond"
309 );
310 assert_eq!(
311 mmr.get(2).unwrap(),
312 LEAVES[2],
313 "value at pos 2 must correspond"
314 );
315 assert_eq!(
316 mmr.get(3).unwrap(),
317 LEAVES[3],
318 "value at pos 3 must correspond"
319 );
320 assert_eq!(
321 mmr.get(4).unwrap(),
322 LEAVES[4],
323 "value at pos 4 must correspond"
324 );
325 assert_eq!(
326 mmr.get(5).unwrap(),
327 LEAVES[5],
328 "value at pos 5 must correspond"
329 );
330 assert_eq!(
331 mmr.get(6).unwrap(),
332 LEAVES[6],
333 "value at pos 6 must correspond"
334 );
335 assert!(mmr.get(7).is_err());
336}
337
338#[test]
339fn test_mmr_invariants() {
340 let mut mmr = Mmr::new();
341 for v in 1..=1028 {
342 mmr.add(int_to_node(v));
343 let accumulator = mmr.accumulator();
344 assert_eq!(
345 v as usize,
346 mmr.forest(),
347 "MMR leaf count must increase by one on every add"
348 );
349 assert_eq!(
350 v as usize, accumulator.num_leaves,
351 "MMR and its accumulator must match leaves count"
352 );
353 assert_eq!(
354 accumulator.num_leaves.count_ones() as usize,
355 accumulator.peaks.len(),
356 "bits on leaves must match the number of peaks"
357 );
358
359 let expected_nodes: usize = TrueBitPositionIterator::new(mmr.forest())
360 .map(|bit_pos| nodes_in_forest(1 << bit_pos))
361 .sum();
362
363 assert_eq!(
364 expected_nodes,
365 mmr.nodes.len(),
366 "the sum of every tree size must be equal to the number of nodes in the MMR (forest: {:b})",
367 mmr.forest(),
368 );
369 }
370}
371
372#[test]
373fn test_bit_position_iterator() {
374 assert_eq!(TrueBitPositionIterator::new(0).count(), 0);
375 assert_eq!(TrueBitPositionIterator::new(0).rev().count(), 0);
376
377 assert_eq!(
378 TrueBitPositionIterator::new(1).collect::<Vec<u32>>(),
379 vec![0]
380 );
381 assert_eq!(
382 TrueBitPositionIterator::new(1).rev().collect::<Vec<u32>>(),
383 vec![0],
384 );
385
386 assert_eq!(
387 TrueBitPositionIterator::new(2).collect::<Vec<u32>>(),
388 vec![1]
389 );
390 assert_eq!(
391 TrueBitPositionIterator::new(2).rev().collect::<Vec<u32>>(),
392 vec![1],
393 );
394
395 assert_eq!(
396 TrueBitPositionIterator::new(3).collect::<Vec<u32>>(),
397 vec![0, 1],
398 );
399 assert_eq!(
400 TrueBitPositionIterator::new(3).rev().collect::<Vec<u32>>(),
401 vec![1, 0],
402 );
403
404 assert_eq!(
405 TrueBitPositionIterator::new(0b11010101).collect::<Vec<u32>>(),
406 vec![0, 2, 4, 6, 7],
407 );
408 assert_eq!(
409 TrueBitPositionIterator::new(0b11010101)
410 .rev()
411 .collect::<Vec<u32>>(),
412 vec![7, 6, 4, 2, 0],
413 );
414}
415
416#[test]
417fn test_mmr_inner_nodes() {
418 let mmr: Mmr = LEAVES.into();
419 let nodes: Vec<InnerNodeInfo> = mmr.inner_nodes().collect();
420
421 let h01 = *Rpo256::hash_elements(&[LEAVES[0], LEAVES[1]].concat());
422 let h23 = *Rpo256::hash_elements(&[LEAVES[2], LEAVES[3]].concat());
423 let h0123 = *Rpo256::hash_elements(&[h01, h23].concat());
424 let h45 = *Rpo256::hash_elements(&[LEAVES[4], LEAVES[5]].concat());
425 let postorder = vec![
426 InnerNodeInfo {
427 value: h01,
428 left: LEAVES[0],
429 right: LEAVES[1],
430 },
431 InnerNodeInfo {
432 value: h23,
433 left: LEAVES[2],
434 right: LEAVES[3],
435 },
436 InnerNodeInfo {
437 value: h0123,
438 left: h01,
439 right: h23,
440 },
441 InnerNodeInfo {
442 value: h45,
443 left: LEAVES[4],
444 right: LEAVES[5],
445 },
446 ];
447
448 assert_eq!(postorder, nodes);
449}
450
451#[test]
452fn test_mmr_hash_peaks() {
453 let mmr: Mmr = LEAVES.into();
454 let peaks = mmr.accumulator();
455
456 let first_peak = *Rpo256::merge(&[
457 Rpo256::hash_elements(&[LEAVES[0], LEAVES[1]].concat()),
458 Rpo256::hash_elements(&[LEAVES[2], LEAVES[3]].concat()),
459 ]);
460 let second_peak = *Rpo256::hash_elements(&[LEAVES[4], LEAVES[5]].concat());
461 let third_peak = LEAVES[6];
462
463 // minimum length is 16
464 let mut expected_peaks = [first_peak, second_peak, third_peak].to_vec();
465 expected_peaks.resize(16, [ZERO; WORD_SIZE]);
466 assert_eq!(
467 peaks.hash_peaks(),
468 *Rpo256::hash_elements(&expected_peaks.as_slice().concat())
469 );
470}
471
472#[test]
473fn test_mmr_peaks_hash_less_than_16() {
474 let mut peaks = Vec::new();
475
476 for i in 0..16 {
477 peaks.push(int_to_node(i));
478 let accumulator = MmrPeaks {
479 num_leaves: (1 << peaks.len()) - 1,
480 peaks: peaks.clone(),
481 };
482
483 // minimum length is 16
484 let mut expected_peaks = peaks.clone();
485 expected_peaks.resize(16, [ZERO; WORD_SIZE]);
486 assert_eq!(
487 accumulator.hash_peaks(),
488 *Rpo256::hash_elements(&expected_peaks.as_slice().concat())
489 );
490 }
491}
492
493#[test]
494fn test_mmr_peaks_hash_odd() {
495 let peaks: Vec<_> = (0..=17).map(|i| int_to_node(i)).collect();
496
497 let accumulator = MmrPeaks {
498 num_leaves: (1 << peaks.len()) - 1,
499 peaks: peaks.clone(),
500 };
501
502 // odd length bigger than 16 is padded to the next even nubmer
503 let mut expected_peaks = peaks.clone();
504 expected_peaks.resize(18, [ZERO; WORD_SIZE]);
505 assert_eq!(
506 accumulator.hash_peaks(),
507 *Rpo256::hash_elements(&expected_peaks.as_slice().concat())
508 );
509}
510
511mod property_tests {
512 use super::leaf_to_corresponding_tree;
513 use proptest::prelude::*;
514
515 proptest! {
516 #[test]
517 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)) {
518 let last_pos = leaves - 1;
519 let lowest_bit = leaves.trailing_zeros();
520
521 assert_eq!(
522 leaf_to_corresponding_tree(last_pos, leaves),
523 Some(lowest_bit),
524 );
525 }
526 }
527
528 proptest! {
529 #[test]
530 fn test_contained_tree_is_always_power_of_two((leaves, pos) in any::<usize>().prop_flat_map(|v| (Just(v), 0..v))) {
531 let tree = leaf_to_corresponding_tree(pos, leaves).expect("pos is smaller than leaves, there should always be a corresponding tree");
532 let mask = 1usize << tree;
533
534 assert!(tree < usize::BITS, "the result must be a bit in usize");
535 assert!(mask & leaves != 0, "the result should be a tree in leaves");
536 }
537 }
538}