miden-crypto/src/merkle/mmr/tests.rs
src/merkle/mmr/tests.rsRaw
1use super::{
2 super::{InnerNodeInfo, Rpo256, RpoDigest, Vec},
3 bit::TrueBitPositionIterator,
4 full::high_bitmask,
5 leaf_to_corresponding_tree, nodes_in_forest, Mmr, MmrPeaks, PartialMmr,
6};
7use crate::{
8 merkle::{int_to_node, InOrderIndex, MerklePath, MerkleTree, MmrProof, NodeIndex},
9 Felt, Word,
10};
11
12#[test]
13fn test_position_equal_or_higher_than_leafs_is_never_contained() {
14 let empty_forest = 0;
15 for pos in 1..1024 {
16 // pos is index, 0 based
17 // tree is a length counter, 1 based
18 // so a valid pos is always smaller, not equal, to tree
19 assert_eq!(leaf_to_corresponding_tree(pos, pos), None);
20 assert_eq!(leaf_to_corresponding_tree(pos, pos - 1), None);
21 // and empty forest has no trees, so no position is valid
22 assert_eq!(leaf_to_corresponding_tree(pos, empty_forest), None);
23 }
24}
25
26#[test]
27fn test_position_zero_is_always_contained_by_the_highest_tree() {
28 for leaves in 1..1024usize {
29 let tree = leaves.ilog2();
30 assert_eq!(leaf_to_corresponding_tree(0, leaves), Some(tree));
31 }
32}
33
34#[test]
35fn test_leaf_to_corresponding_tree() {
36 assert_eq!(leaf_to_corresponding_tree(0, 0b0001), Some(0));
37 assert_eq!(leaf_to_corresponding_tree(0, 0b0010), Some(1));
38 assert_eq!(leaf_to_corresponding_tree(0, 0b0011), Some(1));
39 assert_eq!(leaf_to_corresponding_tree(0, 0b1011), Some(3));
40
41 // position one is always owned by the left-most tree
42 assert_eq!(leaf_to_corresponding_tree(1, 0b0010), Some(1));
43 assert_eq!(leaf_to_corresponding_tree(1, 0b0011), Some(1));
44 assert_eq!(leaf_to_corresponding_tree(1, 0b1011), Some(3));
45
46 // position two starts as its own root, and then it is merged with the left-most tree
47 assert_eq!(leaf_to_corresponding_tree(2, 0b0011), Some(0));
48 assert_eq!(leaf_to_corresponding_tree(2, 0b0100), Some(2));
49 assert_eq!(leaf_to_corresponding_tree(2, 0b1011), Some(3));
50
51 // position tree is merged on the left-most tree
52 assert_eq!(leaf_to_corresponding_tree(3, 0b0011), None);
53 assert_eq!(leaf_to_corresponding_tree(3, 0b0100), Some(2));
54 assert_eq!(leaf_to_corresponding_tree(3, 0b1011), Some(3));
55
56 assert_eq!(leaf_to_corresponding_tree(4, 0b0101), Some(0));
57 assert_eq!(leaf_to_corresponding_tree(4, 0b0110), Some(1));
58 assert_eq!(leaf_to_corresponding_tree(4, 0b0111), Some(1));
59 assert_eq!(leaf_to_corresponding_tree(4, 0b1000), Some(3));
60
61 assert_eq!(leaf_to_corresponding_tree(12, 0b01101), Some(0));
62 assert_eq!(leaf_to_corresponding_tree(12, 0b01110), Some(1));
63 assert_eq!(leaf_to_corresponding_tree(12, 0b01111), Some(1));
64 assert_eq!(leaf_to_corresponding_tree(12, 0b10000), Some(4));
65}
66
67#[test]
68fn test_high_bitmask() {
69 assert_eq!(high_bitmask(0), usize::MAX);
70 assert_eq!(high_bitmask(1), usize::MAX << 1);
71 assert_eq!(high_bitmask(usize::BITS - 2), 0b11usize.rotate_right(2));
72 assert_eq!(high_bitmask(usize::BITS - 1), 0b1usize.rotate_right(1));
73 assert_eq!(high_bitmask(usize::BITS), 0, "overflow should be handled");
74}
75
76#[test]
77fn test_nodes_in_forest() {
78 assert_eq!(nodes_in_forest(0b0000), 0);
79 assert_eq!(nodes_in_forest(0b0001), 1);
80 assert_eq!(nodes_in_forest(0b0010), 3);
81 assert_eq!(nodes_in_forest(0b0011), 4);
82 assert_eq!(nodes_in_forest(0b0100), 7);
83 assert_eq!(nodes_in_forest(0b0101), 8);
84 assert_eq!(nodes_in_forest(0b0110), 10);
85 assert_eq!(nodes_in_forest(0b0111), 11);
86 assert_eq!(nodes_in_forest(0b1000), 15);
87 assert_eq!(nodes_in_forest(0b1001), 16);
88 assert_eq!(nodes_in_forest(0b1010), 18);
89 assert_eq!(nodes_in_forest(0b1011), 19);
90}
91
92#[test]
93fn test_nodes_in_forest_single_bit() {
94 assert_eq!(nodes_in_forest(2usize.pow(0)), 2usize.pow(1) - 1);
95 assert_eq!(nodes_in_forest(2usize.pow(1)), 2usize.pow(2) - 1);
96 assert_eq!(nodes_in_forest(2usize.pow(2)), 2usize.pow(3) - 1);
97 assert_eq!(nodes_in_forest(2usize.pow(3)), 2usize.pow(4) - 1);
98
99 for bit in 0..(usize::BITS - 1) {
100 let size = 2usize.pow(bit + 1) - 1;
101 assert_eq!(nodes_in_forest(1usize << bit), size);
102 }
103}
104
105const LEAVES: [RpoDigest; 7] = [
106 int_to_node(0),
107 int_to_node(1),
108 int_to_node(2),
109 int_to_node(3),
110 int_to_node(4),
111 int_to_node(5),
112 int_to_node(6),
113];
114
115#[test]
116fn test_mmr_simple() {
117 let mut postorder = vec![
118 LEAVES[0],
119 LEAVES[1],
120 merge(LEAVES[0], LEAVES[1]),
121 LEAVES[2],
122 LEAVES[3],
123 merge(LEAVES[2], LEAVES[3]),
124 ];
125 postorder.push(merge(postorder[2], postorder[5]));
126 postorder.push(LEAVES[4]);
127 postorder.push(LEAVES[5]);
128 postorder.push(merge(LEAVES[4], LEAVES[5]));
129 postorder.push(LEAVES[6]);
130
131 let mut mmr = Mmr::new();
132 assert_eq!(mmr.forest(), 0);
133 assert_eq!(mmr.nodes.len(), 0);
134
135 mmr.add(LEAVES[0]);
136 assert_eq!(mmr.forest(), 1);
137 assert_eq!(mmr.nodes.len(), 1);
138 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
139
140 let acc = mmr.peaks(mmr.forest()).unwrap();
141 assert_eq!(acc.num_leaves(), 1);
142 assert_eq!(acc.peaks(), &[postorder[0]]);
143
144 mmr.add(LEAVES[1]);
145 assert_eq!(mmr.forest(), 2);
146 assert_eq!(mmr.nodes.len(), 3);
147 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
148
149 let acc = mmr.peaks(mmr.forest()).unwrap();
150 assert_eq!(acc.num_leaves(), 2);
151 assert_eq!(acc.peaks(), &[postorder[2]]);
152
153 mmr.add(LEAVES[2]);
154 assert_eq!(mmr.forest(), 3);
155 assert_eq!(mmr.nodes.len(), 4);
156 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
157
158 let acc = mmr.peaks(mmr.forest()).unwrap();
159 assert_eq!(acc.num_leaves(), 3);
160 assert_eq!(acc.peaks(), &[postorder[2], postorder[3]]);
161
162 mmr.add(LEAVES[3]);
163 assert_eq!(mmr.forest(), 4);
164 assert_eq!(mmr.nodes.len(), 7);
165 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
166
167 let acc = mmr.peaks(mmr.forest()).unwrap();
168 assert_eq!(acc.num_leaves(), 4);
169 assert_eq!(acc.peaks(), &[postorder[6]]);
170
171 mmr.add(LEAVES[4]);
172 assert_eq!(mmr.forest(), 5);
173 assert_eq!(mmr.nodes.len(), 8);
174 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
175
176 let acc = mmr.peaks(mmr.forest()).unwrap();
177 assert_eq!(acc.num_leaves(), 5);
178 assert_eq!(acc.peaks(), &[postorder[6], postorder[7]]);
179
180 mmr.add(LEAVES[5]);
181 assert_eq!(mmr.forest(), 6);
182 assert_eq!(mmr.nodes.len(), 10);
183 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
184
185 let acc = mmr.peaks(mmr.forest()).unwrap();
186 assert_eq!(acc.num_leaves(), 6);
187 assert_eq!(acc.peaks(), &[postorder[6], postorder[9]]);
188
189 mmr.add(LEAVES[6]);
190 assert_eq!(mmr.forest(), 7);
191 assert_eq!(mmr.nodes.len(), 11);
192 assert_eq!(mmr.nodes.as_slice(), &postorder[0..mmr.nodes.len()]);
193
194 let acc = mmr.peaks(mmr.forest()).unwrap();
195 assert_eq!(acc.num_leaves(), 7);
196 assert_eq!(acc.peaks(), &[postorder[6], postorder[9], postorder[10]]);
197}
198
199#[test]
200fn test_mmr_open() {
201 let mmr: Mmr = LEAVES.into();
202 let h01 = merge(LEAVES[0], LEAVES[1]);
203 let h23 = merge(LEAVES[2], LEAVES[3]);
204
205 // node at pos 7 is the root
206 assert!(
207 mmr.open(7, mmr.forest()).is_err(),
208 "Element 7 is not in the tree, result should be None"
209 );
210
211 // node at pos 6 is the root
212 let empty: MerklePath = MerklePath::new(vec![]);
213 let opening = mmr
214 .open(6, mmr.forest())
215 .expect("Element 6 is contained in the tree, expected an opening result.");
216 assert_eq!(opening.merkle_path, empty);
217 assert_eq!(opening.forest, mmr.forest);
218 assert_eq!(opening.position, 6);
219 assert!(
220 mmr.peaks(mmr.forest()).unwrap().verify(LEAVES[6], opening),
221 "MmrProof should be valid for the current accumulator."
222 );
223
224 // nodes 4,5 are depth 1
225 let root_to_path = MerklePath::new(vec![LEAVES[4]]);
226 let opening = mmr
227 .open(5, mmr.forest())
228 .expect("Element 5 is contained in the tree, expected an opening result.");
229 assert_eq!(opening.merkle_path, root_to_path);
230 assert_eq!(opening.forest, mmr.forest);
231 assert_eq!(opening.position, 5);
232 assert!(
233 mmr.peaks(mmr.forest()).unwrap().verify(LEAVES[5], opening),
234 "MmrProof should be valid for the current accumulator."
235 );
236
237 let root_to_path = MerklePath::new(vec![LEAVES[5]]);
238 let opening = mmr
239 .open(4, mmr.forest())
240 .expect("Element 4 is contained in the tree, expected an opening result.");
241 assert_eq!(opening.merkle_path, root_to_path);
242 assert_eq!(opening.forest, mmr.forest);
243 assert_eq!(opening.position, 4);
244 assert!(
245 mmr.peaks(mmr.forest()).unwrap().verify(LEAVES[4], opening),
246 "MmrProof should be valid for the current accumulator."
247 );
248
249 // nodes 0,1,2,3 are detph 2
250 let root_to_path = MerklePath::new(vec![LEAVES[2], h01]);
251 let opening = mmr
252 .open(3, mmr.forest())
253 .expect("Element 3 is contained in the tree, expected an opening result.");
254 assert_eq!(opening.merkle_path, root_to_path);
255 assert_eq!(opening.forest, mmr.forest);
256 assert_eq!(opening.position, 3);
257 assert!(
258 mmr.peaks(mmr.forest()).unwrap().verify(LEAVES[3], opening),
259 "MmrProof should be valid for the current accumulator."
260 );
261
262 let root_to_path = MerklePath::new(vec![LEAVES[3], h01]);
263 let opening = mmr
264 .open(2, mmr.forest())
265 .expect("Element 2 is contained in the tree, expected an opening result.");
266 assert_eq!(opening.merkle_path, root_to_path);
267 assert_eq!(opening.forest, mmr.forest);
268 assert_eq!(opening.position, 2);
269 assert!(
270 mmr.peaks(mmr.forest()).unwrap().verify(LEAVES[2], opening),
271 "MmrProof should be valid for the current accumulator."
272 );
273
274 let root_to_path = MerklePath::new(vec![LEAVES[0], h23]);
275 let opening = mmr
276 .open(1, mmr.forest())
277 .expect("Element 1 is contained in the tree, expected an opening result.");
278 assert_eq!(opening.merkle_path, root_to_path);
279 assert_eq!(opening.forest, mmr.forest);
280 assert_eq!(opening.position, 1);
281 assert!(
282 mmr.peaks(mmr.forest()).unwrap().verify(LEAVES[1], opening),
283 "MmrProof should be valid for the current accumulator."
284 );
285
286 let root_to_path = MerklePath::new(vec![LEAVES[1], h23]);
287 let opening = mmr
288 .open(0, mmr.forest())
289 .expect("Element 0 is contained in the tree, expected an opening result.");
290 assert_eq!(opening.merkle_path, root_to_path);
291 assert_eq!(opening.forest, mmr.forest);
292 assert_eq!(opening.position, 0);
293 assert!(
294 mmr.peaks(mmr.forest()).unwrap().verify(LEAVES[0], opening),
295 "MmrProof should be valid for the current accumulator."
296 );
297}
298
299#[test]
300fn test_mmr_open_older_version() {
301 let mmr: Mmr = LEAVES.into();
302
303 fn is_even(v: &usize) -> bool {
304 v & 1 == 0
305 }
306
307 // merkle path of a node is empty if there are no elements to pair with it
308 for pos in (0..mmr.forest()).filter(is_even) {
309 let forest = pos + 1;
310 let proof = mmr.open(pos, forest).unwrap();
311 assert_eq!(proof.forest, forest);
312 assert_eq!(proof.merkle_path.nodes(), []);
313 assert_eq!(proof.position, pos);
314 }
315
316 // openings match that of a merkle tree
317 let mtree: MerkleTree = LEAVES[..4].try_into().unwrap();
318 for forest in 4..=LEAVES.len() {
319 for pos in 0..4 {
320 let idx = NodeIndex::new(2, pos).unwrap();
321 let path = mtree.get_path(idx).unwrap();
322 let proof = mmr.open(pos as usize, forest).unwrap();
323 assert_eq!(path, proof.merkle_path);
324 }
325 }
326 let mtree: MerkleTree = LEAVES[4..6].try_into().unwrap();
327 for forest in 6..=LEAVES.len() {
328 for pos in 0..2 {
329 let idx = NodeIndex::new(1, pos).unwrap();
330 let path = mtree.get_path(idx).unwrap();
331 // account for the bigger tree with 4 elements
332 let mmr_pos = (pos + 4) as usize;
333 let proof = mmr.open(mmr_pos, forest).unwrap();
334 assert_eq!(path, proof.merkle_path);
335 }
336 }
337}
338
339/// Tests the openings of a simple Mmr with a single tree of depth 8.
340#[test]
341fn test_mmr_open_eight() {
342 let leaves = [
343 int_to_node(0),
344 int_to_node(1),
345 int_to_node(2),
346 int_to_node(3),
347 int_to_node(4),
348 int_to_node(5),
349 int_to_node(6),
350 int_to_node(7),
351 ];
352
353 let mtree: MerkleTree = leaves.as_slice().try_into().unwrap();
354 let forest = leaves.len();
355 let mmr: Mmr = leaves.into();
356 let root = mtree.root();
357
358 let position = 0;
359 let proof = mmr.open(position, mmr.forest()).unwrap();
360 let merkle_path = mtree.get_path(NodeIndex::new(3, position as u64).unwrap()).unwrap();
361 assert_eq!(proof, MmrProof { forest, position, merkle_path });
362 assert_eq!(proof.merkle_path.compute_root(position as u64, leaves[position]).unwrap(), root);
363
364 let position = 1;
365 let proof = mmr.open(position, mmr.forest()).unwrap();
366 let merkle_path = mtree.get_path(NodeIndex::new(3, position as u64).unwrap()).unwrap();
367 assert_eq!(proof, MmrProof { forest, position, merkle_path });
368 assert_eq!(proof.merkle_path.compute_root(position as u64, leaves[position]).unwrap(), root);
369
370 let position = 2;
371 let proof = mmr.open(position, mmr.forest()).unwrap();
372 let merkle_path = mtree.get_path(NodeIndex::new(3, position as u64).unwrap()).unwrap();
373 assert_eq!(proof, MmrProof { forest, position, merkle_path });
374 assert_eq!(proof.merkle_path.compute_root(position as u64, leaves[position]).unwrap(), root);
375
376 let position = 3;
377 let proof = mmr.open(position, mmr.forest()).unwrap();
378 let merkle_path = mtree.get_path(NodeIndex::new(3, position as u64).unwrap()).unwrap();
379 assert_eq!(proof, MmrProof { forest, position, merkle_path });
380 assert_eq!(proof.merkle_path.compute_root(position as u64, leaves[position]).unwrap(), root);
381
382 let position = 4;
383 let proof = mmr.open(position, mmr.forest()).unwrap();
384 let merkle_path = mtree.get_path(NodeIndex::new(3, position as u64).unwrap()).unwrap();
385 assert_eq!(proof, MmrProof { forest, position, merkle_path });
386 assert_eq!(proof.merkle_path.compute_root(position as u64, leaves[position]).unwrap(), root);
387
388 let position = 5;
389 let proof = mmr.open(position, mmr.forest()).unwrap();
390 let merkle_path = mtree.get_path(NodeIndex::new(3, position as u64).unwrap()).unwrap();
391 assert_eq!(proof, MmrProof { forest, position, merkle_path });
392 assert_eq!(proof.merkle_path.compute_root(position as u64, leaves[position]).unwrap(), root);
393
394 let position = 6;
395 let proof = mmr.open(position, mmr.forest()).unwrap();
396 let merkle_path = mtree.get_path(NodeIndex::new(3, position as u64).unwrap()).unwrap();
397 assert_eq!(proof, MmrProof { forest, position, merkle_path });
398 assert_eq!(proof.merkle_path.compute_root(position as u64, leaves[position]).unwrap(), root);
399
400 let position = 7;
401 let proof = mmr.open(position, mmr.forest()).unwrap();
402 let merkle_path = mtree.get_path(NodeIndex::new(3, position as u64).unwrap()).unwrap();
403 assert_eq!(proof, MmrProof { forest, position, merkle_path });
404 assert_eq!(proof.merkle_path.compute_root(position as u64, leaves[position]).unwrap(), root);
405}
406
407/// Tests the openings of Mmr with a 3 trees of depths 4, 2, and 1.
408#[test]
409fn test_mmr_open_seven() {
410 let mtree1: MerkleTree = LEAVES[..4].try_into().unwrap();
411 let mtree2: MerkleTree = LEAVES[4..6].try_into().unwrap();
412
413 let forest = LEAVES.len();
414 let mmr: Mmr = LEAVES.into();
415
416 let position = 0;
417 let proof = mmr.open(position, mmr.forest()).unwrap();
418 let merkle_path: MerklePath =
419 mtree1.get_path(NodeIndex::new(2, position as u64).unwrap()).unwrap();
420 assert_eq!(proof, MmrProof { forest, position, merkle_path });
421 assert_eq!(proof.merkle_path.compute_root(0, LEAVES[0]).unwrap(), mtree1.root());
422
423 let position = 1;
424 let proof = mmr.open(position, mmr.forest()).unwrap();
425 let merkle_path: MerklePath =
426 mtree1.get_path(NodeIndex::new(2, position as u64).unwrap()).unwrap();
427 assert_eq!(proof, MmrProof { forest, position, merkle_path });
428 assert_eq!(proof.merkle_path.compute_root(1, LEAVES[1]).unwrap(), mtree1.root());
429
430 let position = 2;
431 let proof = mmr.open(position, mmr.forest()).unwrap();
432 let merkle_path: MerklePath =
433 mtree1.get_path(NodeIndex::new(2, position as u64).unwrap()).unwrap();
434 assert_eq!(proof, MmrProof { forest, position, merkle_path });
435 assert_eq!(proof.merkle_path.compute_root(2, LEAVES[2]).unwrap(), mtree1.root());
436
437 let position = 3;
438 let proof = mmr.open(position, mmr.forest()).unwrap();
439 let merkle_path: MerklePath =
440 mtree1.get_path(NodeIndex::new(2, position as u64).unwrap()).unwrap();
441 assert_eq!(proof, MmrProof { forest, position, merkle_path });
442 assert_eq!(proof.merkle_path.compute_root(3, LEAVES[3]).unwrap(), mtree1.root());
443
444 let position = 4;
445 let proof = mmr.open(position, mmr.forest()).unwrap();
446 let merkle_path: MerklePath = mtree2.get_path(NodeIndex::new(1, 0u64).unwrap()).unwrap();
447 assert_eq!(proof, MmrProof { forest, position, merkle_path });
448 assert_eq!(proof.merkle_path.compute_root(0, LEAVES[4]).unwrap(), mtree2.root());
449
450 let position = 5;
451 let proof = mmr.open(position, mmr.forest()).unwrap();
452 let merkle_path: MerklePath = mtree2.get_path(NodeIndex::new(1, 1u64).unwrap()).unwrap();
453 assert_eq!(proof, MmrProof { forest, position, merkle_path });
454 assert_eq!(proof.merkle_path.compute_root(1, LEAVES[5]).unwrap(), mtree2.root());
455
456 let position = 6;
457 let proof = mmr.open(position, mmr.forest()).unwrap();
458 let merkle_path: MerklePath = [].as_ref().into();
459 assert_eq!(proof, MmrProof { forest, position, merkle_path });
460 assert_eq!(proof.merkle_path.compute_root(0, LEAVES[6]).unwrap(), LEAVES[6]);
461}
462
463#[test]
464fn test_mmr_get() {
465 let mmr: Mmr = LEAVES.into();
466 assert_eq!(mmr.get(0).unwrap(), LEAVES[0], "value at pos 0 must correspond");
467 assert_eq!(mmr.get(1).unwrap(), LEAVES[1], "value at pos 1 must correspond");
468 assert_eq!(mmr.get(2).unwrap(), LEAVES[2], "value at pos 2 must correspond");
469 assert_eq!(mmr.get(3).unwrap(), LEAVES[3], "value at pos 3 must correspond");
470 assert_eq!(mmr.get(4).unwrap(), LEAVES[4], "value at pos 4 must correspond");
471 assert_eq!(mmr.get(5).unwrap(), LEAVES[5], "value at pos 5 must correspond");
472 assert_eq!(mmr.get(6).unwrap(), LEAVES[6], "value at pos 6 must correspond");
473 assert!(mmr.get(7).is_err());
474}
475
476#[test]
477fn test_mmr_invariants() {
478 let mut mmr = Mmr::new();
479 for v in 1..=1028 {
480 mmr.add(int_to_node(v));
481 let accumulator = mmr.peaks(mmr.forest()).unwrap();
482 assert_eq!(v as usize, mmr.forest(), "MMR leaf count must increase by one on every add");
483 assert_eq!(
484 v as usize,
485 accumulator.num_leaves(),
486 "MMR and its accumulator must match leaves count"
487 );
488 assert_eq!(
489 accumulator.num_leaves().count_ones() as usize,
490 accumulator.peaks().len(),
491 "bits on leaves must match the number of peaks"
492 );
493
494 let expected_nodes: usize = TrueBitPositionIterator::new(mmr.forest())
495 .map(|bit_pos| nodes_in_forest(1 << bit_pos))
496 .sum();
497
498 assert_eq!(
499 expected_nodes,
500 mmr.nodes.len(),
501 "the sum of every tree size must be equal to the number of nodes in the MMR (forest: {:b})",
502 mmr.forest(),
503 );
504 }
505}
506
507#[test]
508fn test_bit_position_iterator() {
509 assert_eq!(TrueBitPositionIterator::new(0).count(), 0);
510 assert_eq!(TrueBitPositionIterator::new(0).rev().count(), 0);
511
512 assert_eq!(TrueBitPositionIterator::new(1).collect::<Vec<u32>>(), vec![0]);
513 assert_eq!(TrueBitPositionIterator::new(1).rev().collect::<Vec<u32>>(), vec![0],);
514
515 assert_eq!(TrueBitPositionIterator::new(2).collect::<Vec<u32>>(), vec![1]);
516 assert_eq!(TrueBitPositionIterator::new(2).rev().collect::<Vec<u32>>(), vec![1],);
517
518 assert_eq!(TrueBitPositionIterator::new(3).collect::<Vec<u32>>(), vec![0, 1],);
519 assert_eq!(TrueBitPositionIterator::new(3).rev().collect::<Vec<u32>>(), vec![1, 0],);
520
521 assert_eq!(
522 TrueBitPositionIterator::new(0b11010101).collect::<Vec<u32>>(),
523 vec![0, 2, 4, 6, 7],
524 );
525 assert_eq!(
526 TrueBitPositionIterator::new(0b11010101).rev().collect::<Vec<u32>>(),
527 vec![7, 6, 4, 2, 0],
528 );
529}
530
531#[test]
532fn test_mmr_inner_nodes() {
533 let mmr: Mmr = LEAVES.into();
534 let nodes: Vec<InnerNodeInfo> = mmr.inner_nodes().collect();
535
536 let h01 = Rpo256::merge(&[LEAVES[0], LEAVES[1]]);
537 let h23 = Rpo256::merge(&[LEAVES[2], LEAVES[3]]);
538 let h0123 = Rpo256::merge(&[h01, h23]);
539 let h45 = Rpo256::merge(&[LEAVES[4], LEAVES[5]]);
540 let postorder = vec![
541 InnerNodeInfo {
542 value: h01,
543 left: LEAVES[0],
544 right: LEAVES[1],
545 },
546 InnerNodeInfo {
547 value: h23,
548 left: LEAVES[2],
549 right: LEAVES[3],
550 },
551 InnerNodeInfo { value: h0123, left: h01, right: h23 },
552 InnerNodeInfo {
553 value: h45,
554 left: LEAVES[4],
555 right: LEAVES[5],
556 },
557 ];
558
559 assert_eq!(postorder, nodes);
560}
561
562#[test]
563fn test_mmr_peaks() {
564 let mmr: Mmr = LEAVES.into();
565
566 let forest = 0b0001;
567 let acc = mmr.peaks(forest).unwrap();
568 assert_eq!(acc.num_leaves(), forest);
569 assert_eq!(acc.peaks(), &[mmr.nodes[0]]);
570
571 let forest = 0b0010;
572 let acc = mmr.peaks(forest).unwrap();
573 assert_eq!(acc.num_leaves(), forest);
574 assert_eq!(acc.peaks(), &[mmr.nodes[2]]);
575
576 let forest = 0b0011;
577 let acc = mmr.peaks(forest).unwrap();
578 assert_eq!(acc.num_leaves(), forest);
579 assert_eq!(acc.peaks(), &[mmr.nodes[2], mmr.nodes[3]]);
580
581 let forest = 0b0100;
582 let acc = mmr.peaks(forest).unwrap();
583 assert_eq!(acc.num_leaves(), forest);
584 assert_eq!(acc.peaks(), &[mmr.nodes[6]]);
585
586 let forest = 0b0101;
587 let acc = mmr.peaks(forest).unwrap();
588 assert_eq!(acc.num_leaves(), forest);
589 assert_eq!(acc.peaks(), &[mmr.nodes[6], mmr.nodes[7]]);
590
591 let forest = 0b0110;
592 let acc = mmr.peaks(forest).unwrap();
593 assert_eq!(acc.num_leaves(), forest);
594 assert_eq!(acc.peaks(), &[mmr.nodes[6], mmr.nodes[9]]);
595
596 let forest = 0b0111;
597 let acc = mmr.peaks(forest).unwrap();
598 assert_eq!(acc.num_leaves(), forest);
599 assert_eq!(acc.peaks(), &[mmr.nodes[6], mmr.nodes[9], mmr.nodes[10]]);
600}
601
602#[test]
603fn test_mmr_hash_peaks() {
604 let mmr: Mmr = LEAVES.into();
605 let peaks = mmr.peaks(mmr.forest()).unwrap();
606
607 let first_peak = Rpo256::merge(&[
608 Rpo256::merge(&[LEAVES[0], LEAVES[1]]),
609 Rpo256::merge(&[LEAVES[2], LEAVES[3]]),
610 ]);
611 let second_peak = Rpo256::merge(&[LEAVES[4], LEAVES[5]]);
612 let third_peak = LEAVES[6];
613
614 // minimum length is 16
615 let mut expected_peaks = [first_peak, second_peak, third_peak].to_vec();
616 expected_peaks.resize(16, RpoDigest::default());
617 assert_eq!(peaks.hash_peaks(), Rpo256::hash_elements(&digests_to_elements(&expected_peaks)));
618}
619
620#[test]
621fn test_mmr_peaks_hash_less_than_16() {
622 let mut peaks = Vec::new();
623
624 for i in 0..16 {
625 peaks.push(int_to_node(i));
626
627 let num_leaves = (1 << peaks.len()) - 1;
628 let accumulator = MmrPeaks::new(num_leaves, peaks.clone()).unwrap();
629
630 // minimum length is 16
631 let mut expected_peaks = peaks.clone();
632 expected_peaks.resize(16, RpoDigest::default());
633 assert_eq!(
634 accumulator.hash_peaks(),
635 Rpo256::hash_elements(&digests_to_elements(&expected_peaks))
636 );
637 }
638}
639
640#[test]
641fn test_mmr_peaks_hash_odd() {
642 let peaks: Vec<_> = (0..=17).map(int_to_node).collect();
643
644 let num_leaves = (1 << peaks.len()) - 1;
645 let accumulator = MmrPeaks::new(num_leaves, peaks.clone()).unwrap();
646
647 // odd length bigger than 16 is padded to the next even number
648 let mut expected_peaks = peaks;
649 expected_peaks.resize(18, RpoDigest::default());
650 assert_eq!(
651 accumulator.hash_peaks(),
652 Rpo256::hash_elements(&digests_to_elements(&expected_peaks))
653 );
654}
655
656#[test]
657fn test_mmr_delta() {
658 let mmr: Mmr = LEAVES.into();
659 let acc = mmr.peaks(mmr.forest()).unwrap();
660
661 // original_forest can't have more elements
662 assert!(
663 mmr.get_delta(LEAVES.len() + 1, mmr.forest()).is_err(),
664 "Can not provide updates for a newer Mmr"
665 );
666
667 // if the number of elements is the same there is no change
668 assert!(
669 mmr.get_delta(LEAVES.len(), mmr.forest()).unwrap().data.is_empty(),
670 "There are no updates for the same Mmr version"
671 );
672
673 // missing the last element added, which is itself a tree peak
674 assert_eq!(mmr.get_delta(6, mmr.forest()).unwrap().data, vec![acc.peaks()[2]], "one peak");
675
676 // missing the sibling to complete the tree of depth 2, and the last element
677 assert_eq!(
678 mmr.get_delta(5, mmr.forest()).unwrap().data,
679 vec![LEAVES[5], acc.peaks()[2]],
680 "one sibling, one peak"
681 );
682
683 // missing the whole last two trees, only send the peaks
684 assert_eq!(
685 mmr.get_delta(4, mmr.forest()).unwrap().data,
686 vec![acc.peaks()[1], acc.peaks()[2]],
687 "two peaks"
688 );
689
690 // missing the sibling to complete the first tree, and the two last trees
691 assert_eq!(
692 mmr.get_delta(3, mmr.forest()).unwrap().data,
693 vec![LEAVES[3], acc.peaks()[1], acc.peaks()[2]],
694 "one sibling, two peaks"
695 );
696
697 // missing half of the first tree, only send the computed element (not the leaves), and the new
698 // peaks
699 assert_eq!(
700 mmr.get_delta(2, mmr.forest()).unwrap().data,
701 vec![mmr.nodes[5], acc.peaks()[1], acc.peaks()[2]],
702 "one sibling, two peaks"
703 );
704
705 assert_eq!(
706 mmr.get_delta(1, mmr.forest()).unwrap().data,
707 vec![LEAVES[1], mmr.nodes[5], acc.peaks()[1], acc.peaks()[2]],
708 "one sibling, two peaks"
709 );
710
711 assert_eq!(&mmr.get_delta(0, mmr.forest()).unwrap().data, acc.peaks(), "all peaks");
712}
713
714#[test]
715fn test_mmr_delta_old_forest() {
716 let mmr: Mmr = LEAVES.into();
717
718 // from_forest must be smaller-or-equal to to_forest
719 for version in 1..=mmr.forest() {
720 assert!(mmr.get_delta(version + 1, version).is_err());
721 }
722
723 // when from_forest and to_forest are equal, there are no updates
724 for version in 1..=mmr.forest() {
725 let delta = mmr.get_delta(version, version).unwrap();
726 assert!(delta.data.is_empty());
727 assert_eq!(delta.forest, version);
728 }
729
730 // test update which merges the odd peak to the right
731 for count in 0..(mmr.forest() / 2) {
732 // *2 because every iteration tests a pair
733 // +1 because the Mmr is 1-indexed
734 let from_forest = (count * 2) + 1;
735 let to_forest = (count * 2) + 2;
736 let delta = mmr.get_delta(from_forest, to_forest).unwrap();
737
738 // *2 because every iteration tests a pair
739 // +1 because sibling is the odd element
740 let sibling = (count * 2) + 1;
741 assert_eq!(delta.data, [LEAVES[sibling]]);
742 assert_eq!(delta.forest, to_forest);
743 }
744
745 let version = 4;
746 let delta = mmr.get_delta(1, version).unwrap();
747 assert_eq!(delta.data, [mmr.nodes[1], mmr.nodes[5]]);
748 assert_eq!(delta.forest, version);
749
750 let version = 5;
751 let delta = mmr.get_delta(1, version).unwrap();
752 assert_eq!(delta.data, [mmr.nodes[1], mmr.nodes[5], mmr.nodes[7]]);
753 assert_eq!(delta.forest, version);
754}
755
756#[test]
757fn test_partial_mmr_simple() {
758 let mmr: Mmr = LEAVES.into();
759 let peaks = mmr.peaks(mmr.forest()).unwrap();
760 let mut partial: PartialMmr = peaks.clone().into();
761
762 // check initial state of the partial mmr
763 assert_eq!(partial.peaks(), peaks);
764 assert_eq!(partial.forest(), peaks.num_leaves());
765 assert_eq!(partial.forest(), LEAVES.len());
766 assert_eq!(partial.peaks().num_peaks(), 3);
767 assert_eq!(partial.nodes.len(), 0);
768
769 // check state after adding tracking one element
770 let proof1 = mmr.open(0, mmr.forest()).unwrap();
771 let el1 = mmr.get(proof1.position).unwrap();
772 partial.track(proof1.position, el1, &proof1.merkle_path).unwrap();
773
774 // check the number of nodes increased by the number of nodes in the proof
775 assert_eq!(partial.nodes.len(), proof1.merkle_path.len());
776 // check the values match
777 let idx = InOrderIndex::from_leaf_pos(proof1.position);
778 assert_eq!(partial.nodes[&idx.sibling()], proof1.merkle_path[0]);
779 let idx = idx.parent();
780 assert_eq!(partial.nodes[&idx.sibling()], proof1.merkle_path[1]);
781
782 let proof2 = mmr.open(1, mmr.forest()).unwrap();
783 let el2 = mmr.get(proof2.position).unwrap();
784 partial.track(proof2.position, el2, &proof2.merkle_path).unwrap();
785
786 // check the number of nodes increased by a single element (the one that is not shared)
787 assert_eq!(partial.nodes.len(), 3);
788 // check the values match
789 let idx = InOrderIndex::from_leaf_pos(proof2.position);
790 assert_eq!(partial.nodes[&idx.sibling()], proof2.merkle_path[0]);
791 let idx = idx.parent();
792 assert_eq!(partial.nodes[&idx.sibling()], proof2.merkle_path[1]);
793}
794
795#[test]
796fn test_partial_mmr_update_single() {
797 let mut full = Mmr::new();
798 let zero = int_to_node(0);
799 full.add(zero);
800 let mut partial: PartialMmr = full.peaks(full.forest()).unwrap().into();
801
802 let proof = full.open(0, full.forest()).unwrap();
803 partial.track(proof.position, zero, &proof.merkle_path).unwrap();
804
805 for i in 1..100 {
806 let node = int_to_node(i);
807 full.add(node);
808 let delta = full.get_delta(partial.forest(), full.forest()).unwrap();
809 partial.apply(delta).unwrap();
810
811 assert_eq!(partial.forest(), full.forest());
812 assert_eq!(partial.peaks(), full.peaks(full.forest()).unwrap());
813
814 let proof1 = full.open(i as usize, full.forest()).unwrap();
815 partial.track(proof1.position, node, &proof1.merkle_path).unwrap();
816 let proof2 = partial.open(proof1.position).unwrap().unwrap();
817 assert_eq!(proof1.merkle_path, proof2.merkle_path);
818 }
819}
820
821#[test]
822fn test_mmr_add_invalid_odd_leaf() {
823 let mmr: Mmr = LEAVES.into();
824 let acc = mmr.peaks(mmr.forest()).unwrap();
825 let mut partial: PartialMmr = acc.clone().into();
826
827 let empty = MerklePath::new(Vec::new());
828
829 // None of the other leaves should work
830 for node in LEAVES.iter().cloned().rev().skip(1) {
831 let result = partial.track(LEAVES.len() - 1, node, &empty);
832 assert!(result.is_err());
833 }
834
835 let result = partial.track(LEAVES.len() - 1, LEAVES[6], &empty);
836 assert!(result.is_ok());
837}
838
839mod property_tests {
840 use super::leaf_to_corresponding_tree;
841 use proptest::prelude::*;
842
843 proptest! {
844 #[test]
845 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)) {
846 let last_pos = leaves - 1;
847 let lowest_bit = leaves.trailing_zeros();
848
849 assert_eq!(
850 leaf_to_corresponding_tree(last_pos, leaves),
851 Some(lowest_bit),
852 );
853 }
854 }
855
856 proptest! {
857 #[test]
858 fn test_contained_tree_is_always_power_of_two((leaves, pos) in any::<usize>().prop_flat_map(|v| (Just(v), 0..v))) {
859 let tree_bit = leaf_to_corresponding_tree(pos, leaves).expect("pos is smaller than leaves, there should always be a corresponding tree");
860 let mask = 1usize << tree_bit;
861
862 assert!(tree_bit < usize::BITS, "the result must be a bit in usize");
863 assert!(mask & leaves != 0, "the result should be a tree in leaves");
864 }
865 }
866}
867
868// HELPER FUNCTIONS
869// ================================================================================================
870
871fn digests_to_elements(digests: &[RpoDigest]) -> Vec<Felt> {
872 digests.iter().flat_map(Word::from).collect()
873}
874
875// short hand for the rpo hash, used to make test code more concise and easy to read
876fn merge(l: RpoDigest, r: RpoDigest) -> RpoDigest {
877 Rpo256::merge(&[l, r])
878}