miden-crypto/src/merkle/smt/full/tests.rs
src/merkle/smt/full/tests.rsRaw
1use alloc::{collections::BTreeMap, vec::Vec};
2
3use super::{Felt, LeafIndex, NodeIndex, Rpo256, RpoDigest, Smt, SmtLeaf, EMPTY_WORD, SMT_DEPTH};
4use crate::{
5 merkle::{
6 smt::{NodeMutation, SparseMerkleTree},
7 EmptySubtreeRoots, MerkleStore, MutationSet,
8 },
9 utils::{Deserializable, Serializable},
10 Word, ONE, WORD_SIZE,
11};
12// SMT
13// --------------------------------------------------------------------------------------------
14
15/// This test checks that inserting twice at the same key functions as expected. The test covers
16/// only the case where the key is alone in its leaf
17#[test]
18fn test_smt_insert_at_same_key() {
19 let mut smt = Smt::default();
20 let mut store: MerkleStore = MerkleStore::default();
21
22 assert_eq!(smt.root(), *EmptySubtreeRoots::entry(SMT_DEPTH, 0));
23
24 let key_1: RpoDigest = {
25 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
26
27 RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)])
28 };
29 let key_1_index: NodeIndex = LeafIndex::<SMT_DEPTH>::from(key_1).into();
30
31 let value_1 = [ONE; WORD_SIZE];
32 let value_2 = [ONE + ONE; WORD_SIZE];
33
34 // Insert value 1 and ensure root is as expected
35 {
36 let leaf_node = build_empty_or_single_leaf_node(key_1, value_1);
37 let tree_root = store.set_node(smt.root(), key_1_index, leaf_node).unwrap().root;
38
39 let old_value_1 = smt.insert(key_1, value_1);
40 assert_eq!(old_value_1, EMPTY_WORD);
41
42 assert_eq!(smt.root(), tree_root);
43 }
44
45 // Insert value 2 and ensure root is as expected
46 {
47 let leaf_node = build_empty_or_single_leaf_node(key_1, value_2);
48 let tree_root = store.set_node(smt.root(), key_1_index, leaf_node).unwrap().root;
49
50 let old_value_2 = smt.insert(key_1, value_2);
51 assert_eq!(old_value_2, value_1);
52
53 assert_eq!(smt.root(), tree_root);
54 }
55}
56
57/// This test checks that inserting twice at the same key functions as expected. The test covers
58/// only the case where the leaf type is `SmtLeaf::Multiple`
59#[test]
60fn test_smt_insert_at_same_key_2() {
61 // The most significant u64 used for both keys (to ensure they map to the same leaf)
62 let key_msb: u64 = 42;
63
64 let key_already_present: RpoDigest =
65 RpoDigest::from([2_u32.into(), 2_u32.into(), 2_u32.into(), Felt::new(key_msb)]);
66 let key_already_present_index: NodeIndex =
67 LeafIndex::<SMT_DEPTH>::from(key_already_present).into();
68 let value_already_present = [ONE + ONE + ONE; WORD_SIZE];
69
70 let mut smt =
71 Smt::with_entries(core::iter::once((key_already_present, value_already_present))).unwrap();
72 let mut store: MerkleStore = {
73 let mut store = MerkleStore::default();
74
75 let leaf_node = build_empty_or_single_leaf_node(key_already_present, value_already_present);
76 store
77 .set_node(*EmptySubtreeRoots::entry(SMT_DEPTH, 0), key_already_present_index, leaf_node)
78 .unwrap();
79 store
80 };
81
82 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, Felt::new(key_msb)]);
83 let key_1_index: NodeIndex = LeafIndex::<SMT_DEPTH>::from(key_1).into();
84
85 assert_eq!(key_1_index, key_already_present_index);
86
87 let value_1 = [ONE; WORD_SIZE];
88 let value_2 = [ONE + ONE; WORD_SIZE];
89
90 // Insert value 1 and ensure root is as expected
91 {
92 // Note: key_1 comes first because it is smaller
93 let leaf_node = build_multiple_leaf_node(&[
94 (key_1, value_1),
95 (key_already_present, value_already_present),
96 ]);
97 let tree_root = store.set_node(smt.root(), key_1_index, leaf_node).unwrap().root;
98
99 let old_value_1 = smt.insert(key_1, value_1);
100 assert_eq!(old_value_1, EMPTY_WORD);
101
102 assert_eq!(smt.root(), tree_root);
103 }
104
105 // Insert value 2 and ensure root is as expected
106 {
107 let leaf_node = build_multiple_leaf_node(&[
108 (key_1, value_2),
109 (key_already_present, value_already_present),
110 ]);
111 let tree_root = store.set_node(smt.root(), key_1_index, leaf_node).unwrap().root;
112
113 let old_value_2 = smt.insert(key_1, value_2);
114 assert_eq!(old_value_2, value_1);
115
116 assert_eq!(smt.root(), tree_root);
117 }
118}
119
120/// This test ensures that the root of the tree is as expected when we add/remove 3 items at 3
121/// different keys. This also tests that the merkle paths produced are as expected.
122#[test]
123fn test_smt_insert_and_remove_multiple_values() {
124 fn insert_values_and_assert_path(
125 smt: &mut Smt,
126 store: &mut MerkleStore,
127 key_values: &[(RpoDigest, Word)],
128 ) {
129 for &(key, value) in key_values {
130 let key_index: NodeIndex = LeafIndex::<SMT_DEPTH>::from(key).into();
131
132 let leaf_node = build_empty_or_single_leaf_node(key, value);
133 let tree_root = store.set_node(smt.root(), key_index, leaf_node).unwrap().root;
134
135 let _ = smt.insert(key, value);
136
137 assert_eq!(smt.root(), tree_root);
138
139 let expected_path = store.get_path(tree_root, key_index).unwrap();
140 assert_eq!(smt.open(&key).into_parts().0, expected_path.path);
141 }
142 }
143 let mut smt = Smt::default();
144 let mut store: MerkleStore = MerkleStore::default();
145
146 assert_eq!(smt.root(), *EmptySubtreeRoots::entry(SMT_DEPTH, 0));
147
148 let key_1: RpoDigest = {
149 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
150
151 RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)])
152 };
153
154 let key_2: RpoDigest = {
155 let raw = 0b_11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111_u64;
156
157 RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)])
158 };
159
160 let key_3: RpoDigest = {
161 let raw = 0b_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000_u64;
162
163 RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)])
164 };
165
166 let value_1 = [ONE; WORD_SIZE];
167 let value_2 = [ONE + ONE; WORD_SIZE];
168 let value_3 = [ONE + ONE + ONE; WORD_SIZE];
169
170 // Insert values in the tree
171 let key_values = [(key_1, value_1), (key_2, value_2), (key_3, value_3)];
172 insert_values_and_assert_path(&mut smt, &mut store, &key_values);
173
174 // Remove values from the tree
175 let key_empty_values = [(key_1, EMPTY_WORD), (key_2, EMPTY_WORD), (key_3, EMPTY_WORD)];
176 insert_values_and_assert_path(&mut smt, &mut store, &key_empty_values);
177
178 let empty_root = *EmptySubtreeRoots::entry(SMT_DEPTH, 0);
179 assert_eq!(smt.root(), empty_root);
180
181 // an empty tree should have no leaves or inner nodes
182 assert!(smt.leaves.is_empty());
183 assert!(smt.inner_nodes.is_empty());
184}
185
186/// This tests that inserting the empty value does indeed remove the key-value contained at the
187/// leaf. We insert & remove 3 values at the same leaf to ensure that all cases are covered (empty,
188/// single, multiple).
189#[test]
190fn test_smt_removal() {
191 let mut smt = Smt::default();
192
193 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
194
195 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
196 let key_2: RpoDigest =
197 RpoDigest::from([2_u32.into(), 2_u32.into(), 2_u32.into(), Felt::new(raw)]);
198 let key_3: RpoDigest =
199 RpoDigest::from([3_u32.into(), 3_u32.into(), 3_u32.into(), Felt::new(raw)]);
200
201 let value_1 = [ONE; WORD_SIZE];
202 let value_2 = [2_u32.into(); WORD_SIZE];
203 let value_3: [Felt; 4] = [3_u32.into(); WORD_SIZE];
204
205 // insert key-value 1
206 {
207 let old_value_1 = smt.insert(key_1, value_1);
208 assert_eq!(old_value_1, EMPTY_WORD);
209
210 assert_eq!(smt.get_leaf(&key_1), SmtLeaf::Single((key_1, value_1)));
211 }
212
213 // insert key-value 2
214 {
215 let old_value_2 = smt.insert(key_2, value_2);
216 assert_eq!(old_value_2, EMPTY_WORD);
217
218 assert_eq!(
219 smt.get_leaf(&key_2),
220 SmtLeaf::Multiple(vec![(key_1, value_1), (key_2, value_2)])
221 );
222 }
223
224 // insert key-value 3
225 {
226 let old_value_3 = smt.insert(key_3, value_3);
227 assert_eq!(old_value_3, EMPTY_WORD);
228
229 assert_eq!(
230 smt.get_leaf(&key_3),
231 SmtLeaf::Multiple(vec![(key_1, value_1), (key_2, value_2), (key_3, value_3)])
232 );
233 }
234
235 // remove key 3
236 {
237 let old_value_3 = smt.insert(key_3, EMPTY_WORD);
238 assert_eq!(old_value_3, value_3);
239
240 assert_eq!(
241 smt.get_leaf(&key_3),
242 SmtLeaf::Multiple(vec![(key_1, value_1), (key_2, value_2)])
243 );
244 }
245
246 // remove key 2
247 {
248 let old_value_2 = smt.insert(key_2, EMPTY_WORD);
249 assert_eq!(old_value_2, value_2);
250
251 assert_eq!(smt.get_leaf(&key_2), SmtLeaf::Single((key_1, value_1)));
252 }
253
254 // remove key 1
255 {
256 let old_value_1 = smt.insert(key_1, EMPTY_WORD);
257 assert_eq!(old_value_1, value_1);
258
259 assert_eq!(smt.get_leaf(&key_1), SmtLeaf::new_empty(key_1.into()));
260 }
261}
262
263/// This tests that we can correctly calculate prospective leaves -- that is, we can construct
264/// correct [`SmtLeaf`] values for a theoretical insertion on a Merkle tree without mutating or
265/// cloning the tree.
266#[test]
267fn test_prospective_hash() {
268 let mut smt = Smt::default();
269
270 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
271
272 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
273 let key_2: RpoDigest =
274 RpoDigest::from([2_u32.into(), 2_u32.into(), 2_u32.into(), Felt::new(raw)]);
275 // Sort key_3 before key_1, to test non-append insertion.
276 let key_3: RpoDigest =
277 RpoDigest::from([0_u32.into(), 0_u32.into(), 0_u32.into(), Felt::new(raw)]);
278
279 let value_1 = [ONE; WORD_SIZE];
280 let value_2 = [2_u32.into(); WORD_SIZE];
281 let value_3: [Felt; 4] = [3_u32.into(); WORD_SIZE];
282
283 // insert key-value 1
284 {
285 let prospective =
286 smt.construct_prospective_leaf(smt.get_leaf(&key_1), &key_1, &value_1).hash();
287 smt.insert(key_1, value_1);
288
289 let leaf = smt.get_leaf(&key_1);
290 assert_eq!(
291 prospective,
292 leaf.hash(),
293 "prospective hash for leaf {leaf:?} did not match actual hash",
294 );
295 }
296
297 // insert key-value 2
298 {
299 let prospective =
300 smt.construct_prospective_leaf(smt.get_leaf(&key_2), &key_2, &value_2).hash();
301 smt.insert(key_2, value_2);
302
303 let leaf = smt.get_leaf(&key_2);
304 assert_eq!(
305 prospective,
306 leaf.hash(),
307 "prospective hash for leaf {leaf:?} did not match actual hash",
308 );
309 }
310
311 // insert key-value 3
312 {
313 let prospective =
314 smt.construct_prospective_leaf(smt.get_leaf(&key_3), &key_3, &value_3).hash();
315 smt.insert(key_3, value_3);
316
317 let leaf = smt.get_leaf(&key_3);
318 assert_eq!(
319 prospective,
320 leaf.hash(),
321 "prospective hash for leaf {leaf:?} did not match actual hash",
322 );
323 }
324
325 // remove key 3
326 {
327 let old_leaf = smt.get_leaf(&key_3);
328 let old_value_3 = smt.insert(key_3, EMPTY_WORD);
329 assert_eq!(old_value_3, value_3);
330 let prospective_leaf =
331 smt.construct_prospective_leaf(smt.get_leaf(&key_3), &key_3, &old_value_3);
332
333 assert_eq!(
334 old_leaf.hash(),
335 prospective_leaf.hash(),
336 "removing and prospectively re-adding a leaf didn't yield the original leaf:\
337 \n original leaf: {old_leaf:?}\
338 \n prospective leaf: {prospective_leaf:?}",
339 );
340 }
341
342 // remove key 2
343 {
344 let old_leaf = smt.get_leaf(&key_2);
345 let old_value_2 = smt.insert(key_2, EMPTY_WORD);
346 assert_eq!(old_value_2, value_2);
347 let prospective_leaf =
348 smt.construct_prospective_leaf(smt.get_leaf(&key_2), &key_2, &old_value_2);
349
350 assert_eq!(
351 old_leaf.hash(),
352 prospective_leaf.hash(),
353 "removing and prospectively re-adding a leaf didn't yield the original leaf:\
354 \n original leaf: {old_leaf:?}\
355 \n prospective leaf: {prospective_leaf:?}",
356 );
357 }
358
359 // remove key 1
360 {
361 let old_leaf = smt.get_leaf(&key_1);
362 let old_value_1 = smt.insert(key_1, EMPTY_WORD);
363 assert_eq!(old_value_1, value_1);
364 let prospective_leaf =
365 smt.construct_prospective_leaf(smt.get_leaf(&key_1), &key_1, &old_value_1);
366 assert_eq!(
367 old_leaf.hash(),
368 prospective_leaf.hash(),
369 "removing and prospectively re-adding a leaf didn't yield the original leaf:\
370 \n original leaf: {old_leaf:?}\
371 \n prospective leaf: {prospective_leaf:?}",
372 );
373 }
374}
375
376/// This tests that we can perform prospective changes correctly.
377#[test]
378fn test_prospective_insertion() {
379 let mut smt = Smt::default();
380
381 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
382
383 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
384 let key_2: RpoDigest =
385 RpoDigest::from([2_u32.into(), 2_u32.into(), 2_u32.into(), Felt::new(raw)]);
386 // Sort key_3 before key_1, to test non-append insertion.
387 let key_3: RpoDigest =
388 RpoDigest::from([0_u32.into(), 0_u32.into(), 0_u32.into(), Felt::new(raw)]);
389
390 let value_1 = [ONE; WORD_SIZE];
391 let value_2 = [2_u32.into(); WORD_SIZE];
392 let value_3: [Felt; 4] = [3_u32.into(); WORD_SIZE];
393
394 let root_empty = smt.root();
395
396 let root_1 = {
397 smt.insert(key_1, value_1);
398 smt.root()
399 };
400
401 let root_2 = {
402 smt.insert(key_2, value_2);
403 smt.root()
404 };
405
406 let root_3 = {
407 smt.insert(key_3, value_3);
408 smt.root()
409 };
410
411 // Test incremental updates.
412
413 let mut smt = Smt::default();
414
415 let mutations = smt.compute_mutations(vec![(key_1, value_1)]);
416 assert_eq!(mutations.root(), root_1, "prospective root 1 did not match actual root 1");
417 let revert = apply_mutations(&mut smt, mutations);
418 assert_eq!(smt.root(), root_1, "mutations before and after apply did not match");
419 assert_eq!(revert.old_root, smt.root(), "reverse mutations old root did not match");
420 assert_eq!(revert.root(), root_empty, "reverse mutations new root did not match");
421 assert_eq!(
422 revert.new_pairs,
423 BTreeMap::from_iter([(key_1, EMPTY_WORD)]),
424 "reverse mutations pairs did not match"
425 );
426 assert_eq!(
427 revert.node_mutations,
428 smt.inner_nodes.keys().map(|key| (*key, NodeMutation::Removal)).collect(),
429 "reverse mutations inner nodes did not match"
430 );
431
432 let mutations = smt.compute_mutations(vec![(key_2, value_2)]);
433 assert_eq!(mutations.root(), root_2, "prospective root 2 did not match actual root 2");
434 let mutations =
435 smt.compute_mutations(vec![(key_3, EMPTY_WORD), (key_2, value_2), (key_3, value_3)]);
436 assert_eq!(mutations.root(), root_3, "mutations before and after apply did not match");
437 let old_root = smt.root();
438 let revert = apply_mutations(&mut smt, mutations);
439 assert_eq!(revert.old_root, smt.root(), "reverse mutations old root did not match");
440 assert_eq!(revert.root(), old_root, "reverse mutations new root did not match");
441 assert_eq!(
442 revert.new_pairs,
443 BTreeMap::from_iter([(key_2, EMPTY_WORD), (key_3, EMPTY_WORD)]),
444 "reverse mutations pairs did not match"
445 );
446
447 // Edge case: multiple values at the same key, where a later pair restores the original value.
448 let mutations = smt.compute_mutations(vec![(key_3, EMPTY_WORD), (key_3, value_3)]);
449 assert_eq!(mutations.root(), root_3);
450 let old_root = smt.root();
451 let revert = apply_mutations(&mut smt, mutations);
452 assert_eq!(smt.root(), root_3);
453 assert_eq!(revert.old_root, smt.root(), "reverse mutations old root did not match");
454 assert_eq!(revert.root(), old_root, "reverse mutations new root did not match");
455 assert_eq!(
456 revert.new_pairs,
457 BTreeMap::from_iter([(key_3, value_3)]),
458 "reverse mutations pairs did not match"
459 );
460
461 // Test batch updates, and that the order doesn't matter.
462 let pairs =
463 vec![(key_3, value_2), (key_2, EMPTY_WORD), (key_1, EMPTY_WORD), (key_3, EMPTY_WORD)];
464 let mutations = smt.compute_mutations(pairs);
465 assert_eq!(
466 mutations.root(),
467 root_empty,
468 "prospective root for batch removal did not match actual root",
469 );
470 let old_root = smt.root();
471 let revert = apply_mutations(&mut smt, mutations);
472 assert_eq!(smt.root(), root_empty, "mutations before and after apply did not match");
473 assert_eq!(revert.old_root, smt.root(), "reverse mutations old root did not match");
474 assert_eq!(revert.root(), old_root, "reverse mutations new root did not match");
475 assert_eq!(
476 revert.new_pairs,
477 BTreeMap::from_iter([(key_1, value_1), (key_2, value_2), (key_3, value_3)]),
478 "reverse mutations pairs did not match"
479 );
480
481 let pairs = vec![(key_3, value_3), (key_1, value_1), (key_2, value_2)];
482 let mutations = smt.compute_mutations(pairs);
483 assert_eq!(mutations.root(), root_3);
484 smt.apply_mutations(mutations).unwrap();
485 assert_eq!(smt.root(), root_3);
486}
487
488#[test]
489fn test_mutations_revert() {
490 let mut smt = Smt::default();
491
492 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, Felt::new(1)]);
493 let key_2: RpoDigest =
494 RpoDigest::from([2_u32.into(), 2_u32.into(), 2_u32.into(), Felt::new(2)]);
495 let key_3: RpoDigest =
496 RpoDigest::from([0_u32.into(), 0_u32.into(), 0_u32.into(), Felt::new(3)]);
497
498 let value_1 = [ONE; WORD_SIZE];
499 let value_2 = [2_u32.into(); WORD_SIZE];
500 let value_3 = [3_u32.into(); WORD_SIZE];
501
502 smt.insert(key_1, value_1);
503 smt.insert(key_2, value_2);
504
505 let mutations =
506 smt.compute_mutations(vec![(key_1, EMPTY_WORD), (key_2, value_1), (key_3, value_3)]);
507
508 let original = smt.clone();
509
510 let revert = smt.apply_mutations_with_reversion(mutations).unwrap();
511 assert_eq!(revert.old_root, smt.root(), "reverse mutations old root did not match");
512 assert_eq!(revert.root(), original.root(), "reverse mutations new root did not match");
513
514 smt.apply_mutations(revert).unwrap();
515
516 assert_eq!(smt, original, "SMT with applied revert mutations did not match original SMT");
517}
518
519#[test]
520fn test_mutation_set_serialization() {
521 let mut smt = Smt::default();
522
523 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, Felt::new(1)]);
524 let key_2: RpoDigest =
525 RpoDigest::from([2_u32.into(), 2_u32.into(), 2_u32.into(), Felt::new(2)]);
526 let key_3: RpoDigest =
527 RpoDigest::from([0_u32.into(), 0_u32.into(), 0_u32.into(), Felt::new(3)]);
528
529 let value_1 = [ONE; WORD_SIZE];
530 let value_2 = [2_u32.into(); WORD_SIZE];
531 let value_3 = [3_u32.into(); WORD_SIZE];
532
533 smt.insert(key_1, value_1);
534 smt.insert(key_2, value_2);
535
536 let mutations =
537 smt.compute_mutations(vec![(key_1, EMPTY_WORD), (key_2, value_1), (key_3, value_3)]);
538
539 let serialized = mutations.to_bytes();
540 let deserialized =
541 MutationSet::<SMT_DEPTH, RpoDigest, Word>::read_from_bytes(&serialized).unwrap();
542
543 assert_eq!(deserialized, mutations, "deserialized mutations did not match original");
544
545 let revert = smt.apply_mutations_with_reversion(mutations).unwrap();
546
547 let serialized = revert.to_bytes();
548 let deserialized =
549 MutationSet::<SMT_DEPTH, RpoDigest, Word>::read_from_bytes(&serialized).unwrap();
550
551 assert_eq!(deserialized, revert, "deserialized mutations did not match original");
552}
553
554/// Tests that 2 key-value pairs stored in the same leaf have the same path
555#[test]
556fn test_smt_path_to_keys_in_same_leaf_are_equal() {
557 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
558
559 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
560 let key_2: RpoDigest =
561 RpoDigest::from([2_u32.into(), 2_u32.into(), 2_u32.into(), Felt::new(raw)]);
562
563 let value_1 = [ONE; WORD_SIZE];
564 let value_2 = [2_u32.into(); WORD_SIZE];
565
566 let smt = Smt::with_entries([(key_1, value_1), (key_2, value_2)]).unwrap();
567
568 assert_eq!(smt.open(&key_1), smt.open(&key_2));
569}
570
571/// Tests that an empty leaf hashes to the empty word
572#[test]
573fn test_empty_leaf_hash() {
574 let smt = Smt::default();
575
576 let leaf = smt.get_leaf(&RpoDigest::default());
577 assert_eq!(leaf.hash(), EMPTY_WORD.into());
578}
579
580/// Tests that `get_value()` works as expected
581#[test]
582fn test_smt_get_value() {
583 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, ONE]);
584 let key_2: RpoDigest = RpoDigest::from([2_u32, 2_u32, 2_u32, 2_u32]);
585
586 let value_1 = [ONE; WORD_SIZE];
587 let value_2 = [2_u32.into(); WORD_SIZE];
588
589 let smt = Smt::with_entries([(key_1, value_1), (key_2, value_2)]).unwrap();
590
591 let returned_value_1 = smt.get_value(&key_1);
592 let returned_value_2 = smt.get_value(&key_2);
593
594 assert_eq!(value_1, returned_value_1);
595 assert_eq!(value_2, returned_value_2);
596
597 // Check that a key with no inserted value returns the empty word
598 let key_no_value = RpoDigest::from([42_u32, 42_u32, 42_u32, 42_u32]);
599
600 assert_eq!(EMPTY_WORD, smt.get_value(&key_no_value));
601}
602
603/// Tests that `entries()` works as expected
604#[test]
605fn test_smt_entries() {
606 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, ONE]);
607 let key_2: RpoDigest = RpoDigest::from([2_u32, 2_u32, 2_u32, 2_u32]);
608
609 let value_1 = [ONE; WORD_SIZE];
610 let value_2 = [2_u32.into(); WORD_SIZE];
611
612 let smt = Smt::with_entries([(key_1, value_1), (key_2, value_2)]).unwrap();
613
614 let mut entries = smt.entries();
615
616 // Note: for simplicity, we assume the order `(k1,v1), (k2,v2)`. If a new implementation
617 // switches the order, it is OK to modify the order here as well.
618 assert_eq!(&(key_1, value_1), entries.next().unwrap());
619 assert_eq!(&(key_2, value_2), entries.next().unwrap());
620 assert!(entries.next().is_none());
621}
622
623/// Tests that `EMPTY_ROOT` constant generated in the `Smt` equals to the root of the empty tree of
624/// depth 64
625#[test]
626fn test_smt_check_empty_root_constant() {
627 // get the root of the empty tree of depth 64
628 let empty_root_64_depth = EmptySubtreeRoots::empty_hashes(64)[0];
629
630 assert_eq!(empty_root_64_depth, Smt::EMPTY_ROOT);
631}
632
633// SMT LEAF
634// --------------------------------------------------------------------------------------------
635
636#[test]
637fn test_empty_smt_leaf_serialization() {
638 let empty_leaf = SmtLeaf::new_empty(LeafIndex::new_max_depth(42));
639
640 let mut serialized = empty_leaf.to_bytes();
641 // extend buffer with random bytes
642 serialized.extend([1, 2, 3, 4, 5]);
643 let deserialized = SmtLeaf::read_from_bytes(&serialized).unwrap();
644
645 assert_eq!(empty_leaf, deserialized);
646}
647
648#[test]
649fn test_single_smt_leaf_serialization() {
650 let single_leaf = SmtLeaf::new_single(
651 RpoDigest::from([10_u32, 11_u32, 12_u32, 13_u32]),
652 [1_u32.into(), 2_u32.into(), 3_u32.into(), 4_u32.into()],
653 );
654
655 let mut serialized = single_leaf.to_bytes();
656 // extend buffer with random bytes
657 serialized.extend([1, 2, 3, 4, 5]);
658 let deserialized = SmtLeaf::read_from_bytes(&serialized).unwrap();
659
660 assert_eq!(single_leaf, deserialized);
661}
662
663#[test]
664fn test_multiple_smt_leaf_serialization_success() {
665 let multiple_leaf = SmtLeaf::new_multiple(vec![
666 (
667 RpoDigest::from([10_u32, 11_u32, 12_u32, 13_u32]),
668 [1_u32.into(), 2_u32.into(), 3_u32.into(), 4_u32.into()],
669 ),
670 (
671 RpoDigest::from([100_u32, 101_u32, 102_u32, 13_u32]),
672 [11_u32.into(), 12_u32.into(), 13_u32.into(), 14_u32.into()],
673 ),
674 ])
675 .unwrap();
676
677 let mut serialized = multiple_leaf.to_bytes();
678 // extend buffer with random bytes
679 serialized.extend([1, 2, 3, 4, 5]);
680 let deserialized = SmtLeaf::read_from_bytes(&serialized).unwrap();
681
682 assert_eq!(multiple_leaf, deserialized);
683}
684
685// HELPERS
686// --------------------------------------------------------------------------------------------
687
688fn build_empty_or_single_leaf_node(key: RpoDigest, value: Word) -> RpoDigest {
689 if value == EMPTY_WORD {
690 SmtLeaf::new_empty(key.into()).hash()
691 } else {
692 SmtLeaf::Single((key, value)).hash()
693 }
694}
695
696fn build_multiple_leaf_node(kv_pairs: &[(RpoDigest, Word)]) -> RpoDigest {
697 let elements: Vec<Felt> = kv_pairs
698 .iter()
699 .flat_map(|(key, value)| {
700 let key_elements = key.into_iter();
701 let value_elements = (*value).into_iter();
702
703 key_elements.chain(value_elements)
704 })
705 .collect();
706
707 Rpo256::hash_elements(&elements)
708}
709
710/// Applies mutations with and without reversion to the given SMT, comparing resulting SMTs,
711/// returning mutation set for reversion.
712fn apply_mutations(
713 smt: &mut Smt,
714 mutation_set: MutationSet<SMT_DEPTH, RpoDigest, Word>,
715) -> MutationSet<SMT_DEPTH, RpoDigest, Word> {
716 let mut smt2 = smt.clone();
717
718 let reversion = smt.apply_mutations_with_reversion(mutation_set.clone()).unwrap();
719 smt2.apply_mutations(mutation_set).unwrap();
720
721 assert_eq!(&smt2, smt);
722
723 reversion
724}