miden-crypto/src/merkle/store/tests.rs
src/merkle/store/tests.rsRaw
1use super::{
2 Deserializable, EmptySubtreeRoots, MerkleError, MerklePath, MerkleStore, NodeIndex, RpoDigest,
3 Serializable,
4};
5use crate::{
6 hash::rpo::Rpo256,
7 merkle::{digests_to_words, int_to_leaf, int_to_node, MerklePathSet, MerkleTree, SimpleSmt},
8 Felt, Word, WORD_SIZE,
9};
10
11#[cfg(feature = "std")]
12use std::error::Error;
13
14// TEST DATA
15// ================================================================================================
16
17const KEYS4: [u64; 4] = [0, 1, 2, 3];
18const VALUES4: [RpoDigest; 4] = [int_to_node(1), int_to_node(2), int_to_node(3), int_to_node(4)];
19
20const VALUES8: [RpoDigest; 8] = [
21 int_to_node(1),
22 int_to_node(2),
23 int_to_node(3),
24 int_to_node(4),
25 int_to_node(5),
26 int_to_node(6),
27 int_to_node(7),
28 int_to_node(8),
29];
30
31// TESTS
32// ================================================================================================
33
34#[test]
35fn test_root_not_in_store() -> Result<(), MerkleError> {
36 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
37 let store = MerkleStore::from(&mtree);
38 assert_eq!(
39 store.get_node(VALUES4[0], NodeIndex::make(mtree.depth(), 0)),
40 Err(MerkleError::RootNotInStore(VALUES4[0])),
41 "Leaf 0 is not a root"
42 );
43 assert_eq!(
44 store.get_path(VALUES4[0], NodeIndex::make(mtree.depth(), 0)),
45 Err(MerkleError::RootNotInStore(VALUES4[0])),
46 "Leaf 0 is not a root"
47 );
48
49 Ok(())
50}
51
52#[test]
53fn test_merkle_tree() -> Result<(), MerkleError> {
54 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
55 let store = MerkleStore::from(&mtree);
56
57 // STORE LEAVES ARE CORRECT -------------------------------------------------------------------
58 // checks the leaves in the store corresponds to the expected values
59 assert_eq!(
60 store.get_node(mtree.root(), NodeIndex::make(mtree.depth(), 0)),
61 Ok(VALUES4[0]),
62 "node 0 must be in the tree"
63 );
64 assert_eq!(
65 store.get_node(mtree.root(), NodeIndex::make(mtree.depth(), 1)),
66 Ok(VALUES4[1]),
67 "node 1 must be in the tree"
68 );
69 assert_eq!(
70 store.get_node(mtree.root(), NodeIndex::make(mtree.depth(), 2)),
71 Ok(VALUES4[2]),
72 "node 2 must be in the tree"
73 );
74 assert_eq!(
75 store.get_node(mtree.root(), NodeIndex::make(mtree.depth(), 3)),
76 Ok(VALUES4[3]),
77 "node 3 must be in the tree"
78 );
79
80 // STORE LEAVES MATCH TREE --------------------------------------------------------------------
81 // sanity check the values returned by the store and the tree
82 assert_eq!(
83 mtree.get_node(NodeIndex::make(mtree.depth(), 0)),
84 store.get_node(mtree.root(), NodeIndex::make(mtree.depth(), 0)),
85 "node 0 must be the same for both MerkleTree and MerkleStore"
86 );
87 assert_eq!(
88 mtree.get_node(NodeIndex::make(mtree.depth(), 1)),
89 store.get_node(mtree.root(), NodeIndex::make(mtree.depth(), 1)),
90 "node 1 must be the same for both MerkleTree and MerkleStore"
91 );
92 assert_eq!(
93 mtree.get_node(NodeIndex::make(mtree.depth(), 2)),
94 store.get_node(mtree.root(), NodeIndex::make(mtree.depth(), 2)),
95 "node 2 must be the same for both MerkleTree and MerkleStore"
96 );
97 assert_eq!(
98 mtree.get_node(NodeIndex::make(mtree.depth(), 3)),
99 store.get_node(mtree.root(), NodeIndex::make(mtree.depth(), 3)),
100 "node 3 must be the same for both MerkleTree and MerkleStore"
101 );
102
103 // STORE MERKLE PATH MATCHS ==============================================================
104 // assert the merkle path returned by the store is the same as the one in the tree
105 let result = store.get_path(mtree.root(), NodeIndex::make(mtree.depth(), 0)).unwrap();
106 assert_eq!(
107 VALUES4[0], result.value,
108 "Value for merkle path at index 0 must match leaf value"
109 );
110 assert_eq!(
111 mtree.get_path(NodeIndex::make(mtree.depth(), 0)),
112 Ok(result.path),
113 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
114 );
115
116 let result = store.get_path(mtree.root(), NodeIndex::make(mtree.depth(), 1)).unwrap();
117 assert_eq!(
118 VALUES4[1], result.value,
119 "Value for merkle path at index 0 must match leaf value"
120 );
121 assert_eq!(
122 mtree.get_path(NodeIndex::make(mtree.depth(), 1)),
123 Ok(result.path),
124 "merkle path for index 1 must be the same for the MerkleTree and MerkleStore"
125 );
126
127 let result = store.get_path(mtree.root(), NodeIndex::make(mtree.depth(), 2)).unwrap();
128 assert_eq!(
129 VALUES4[2], result.value,
130 "Value for merkle path at index 0 must match leaf value"
131 );
132 assert_eq!(
133 mtree.get_path(NodeIndex::make(mtree.depth(), 2)),
134 Ok(result.path),
135 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
136 );
137
138 let result = store.get_path(mtree.root(), NodeIndex::make(mtree.depth(), 3)).unwrap();
139 assert_eq!(
140 VALUES4[3], result.value,
141 "Value for merkle path at index 0 must match leaf value"
142 );
143 assert_eq!(
144 mtree.get_path(NodeIndex::make(mtree.depth(), 3)),
145 Ok(result.path),
146 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
147 );
148
149 Ok(())
150}
151
152#[test]
153fn test_empty_roots() {
154 let store = MerkleStore::default();
155 let mut root = RpoDigest::default();
156
157 for depth in 0..255 {
158 root = Rpo256::merge(&[root; 2]);
159 assert!(
160 store.get_node(root, NodeIndex::make(0, 0)).is_ok(),
161 "The root of the empty tree of depth {depth} must be registered"
162 );
163 }
164}
165
166#[test]
167fn test_leaf_paths_for_empty_trees() -> Result<(), MerkleError> {
168 let store = MerkleStore::default();
169
170 // Starts at 1 because leafs are not included in the store.
171 // Ends at 64 because it is not possible to represent an index of a depth greater than 64,
172 // because a u64 is used to index the leaf.
173 for depth in 1..64 {
174 let smt = SimpleSmt::new(depth)?;
175
176 let index = NodeIndex::make(depth, 0);
177 let store_path = store.get_path(smt.root(), index)?;
178 let smt_path = smt.get_path(index)?;
179 assert_eq!(
180 store_path.value,
181 RpoDigest::default(),
182 "the leaf of an empty tree is always ZERO"
183 );
184 assert_eq!(
185 store_path.path, smt_path,
186 "the returned merkle path does not match the computed values"
187 );
188 assert_eq!(
189 store_path.path.compute_root(depth.into(), RpoDigest::default()).unwrap(),
190 smt.root(),
191 "computed root from the path must match the empty tree root"
192 );
193 }
194
195 Ok(())
196}
197
198#[test]
199fn test_get_invalid_node() {
200 let mtree =
201 MerkleTree::new(digests_to_words(&VALUES4)).expect("creating a merkle tree must work");
202 let store = MerkleStore::from(&mtree);
203 let _ = store.get_node(mtree.root(), NodeIndex::make(mtree.depth(), 3));
204}
205
206#[test]
207fn test_add_sparse_merkle_tree_one_level() -> Result<(), MerkleError> {
208 let keys2: [u64; 2] = [0, 1];
209 let leaves2: [Word; 2] = [int_to_leaf(1), int_to_leaf(2)];
210 let smt = SimpleSmt::with_leaves(1, keys2.into_iter().zip(leaves2.into_iter())).unwrap();
211 let store = MerkleStore::from(&smt);
212
213 let idx = NodeIndex::make(1, 0);
214 assert_eq!(smt.get_node(idx).unwrap(), leaves2[0].into());
215 assert_eq!(store.get_node(smt.root(), idx).unwrap(), smt.get_node(idx).unwrap());
216
217 let idx = NodeIndex::make(1, 1);
218 assert_eq!(smt.get_node(idx).unwrap(), leaves2[1].into());
219 assert_eq!(store.get_node(smt.root(), idx).unwrap(), smt.get_node(idx).unwrap());
220
221 Ok(())
222}
223
224#[test]
225fn test_sparse_merkle_tree() -> Result<(), MerkleError> {
226 let smt = SimpleSmt::with_leaves(
227 SimpleSmt::MAX_DEPTH,
228 KEYS4.into_iter().zip(digests_to_words(&VALUES4).into_iter()),
229 )
230 .unwrap();
231
232 let store = MerkleStore::from(&smt);
233
234 // STORE LEAVES ARE CORRECT ==============================================================
235 // checks the leaves in the store corresponds to the expected values
236 assert_eq!(
237 store.get_node(smt.root(), NodeIndex::make(smt.depth(), 0)),
238 Ok(VALUES4[0]),
239 "node 0 must be in the tree"
240 );
241 assert_eq!(
242 store.get_node(smt.root(), NodeIndex::make(smt.depth(), 1)),
243 Ok(VALUES4[1]),
244 "node 1 must be in the tree"
245 );
246 assert_eq!(
247 store.get_node(smt.root(), NodeIndex::make(smt.depth(), 2)),
248 Ok(VALUES4[2]),
249 "node 2 must be in the tree"
250 );
251 assert_eq!(
252 store.get_node(smt.root(), NodeIndex::make(smt.depth(), 3)),
253 Ok(VALUES4[3]),
254 "node 3 must be in the tree"
255 );
256 assert_eq!(
257 store.get_node(smt.root(), NodeIndex::make(smt.depth(), 4)),
258 Ok(RpoDigest::default()),
259 "unmodified node 4 must be ZERO"
260 );
261
262 // STORE LEAVES MATCH TREE ===============================================================
263 // sanity check the values returned by the store and the tree
264 assert_eq!(
265 smt.get_node(NodeIndex::make(smt.depth(), 0)),
266 store.get_node(smt.root(), NodeIndex::make(smt.depth(), 0)),
267 "node 0 must be the same for both SparseMerkleTree and MerkleStore"
268 );
269 assert_eq!(
270 smt.get_node(NodeIndex::make(smt.depth(), 1)),
271 store.get_node(smt.root(), NodeIndex::make(smt.depth(), 1)),
272 "node 1 must be the same for both SparseMerkleTree and MerkleStore"
273 );
274 assert_eq!(
275 smt.get_node(NodeIndex::make(smt.depth(), 2)),
276 store.get_node(smt.root(), NodeIndex::make(smt.depth(), 2)),
277 "node 2 must be the same for both SparseMerkleTree and MerkleStore"
278 );
279 assert_eq!(
280 smt.get_node(NodeIndex::make(smt.depth(), 3)),
281 store.get_node(smt.root(), NodeIndex::make(smt.depth(), 3)),
282 "node 3 must be the same for both SparseMerkleTree and MerkleStore"
283 );
284 assert_eq!(
285 smt.get_node(NodeIndex::make(smt.depth(), 4)),
286 store.get_node(smt.root(), NodeIndex::make(smt.depth(), 4)),
287 "node 4 must be the same for both SparseMerkleTree and MerkleStore"
288 );
289
290 // STORE MERKLE PATH MATCHS ==============================================================
291 // assert the merkle path returned by the store is the same as the one in the tree
292 let result = store.get_path(smt.root(), NodeIndex::make(smt.depth(), 0)).unwrap();
293 assert_eq!(
294 VALUES4[0], result.value,
295 "Value for merkle path at index 0 must match leaf value"
296 );
297 assert_eq!(
298 smt.get_path(NodeIndex::make(smt.depth(), 0)),
299 Ok(result.path),
300 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
301 );
302
303 let result = store.get_path(smt.root(), NodeIndex::make(smt.depth(), 1)).unwrap();
304 assert_eq!(
305 VALUES4[1], result.value,
306 "Value for merkle path at index 1 must match leaf value"
307 );
308 assert_eq!(
309 smt.get_path(NodeIndex::make(smt.depth(), 1)),
310 Ok(result.path),
311 "merkle path for index 1 must be the same for the MerkleTree and MerkleStore"
312 );
313
314 let result = store.get_path(smt.root(), NodeIndex::make(smt.depth(), 2)).unwrap();
315 assert_eq!(
316 VALUES4[2], result.value,
317 "Value for merkle path at index 2 must match leaf value"
318 );
319 assert_eq!(
320 smt.get_path(NodeIndex::make(smt.depth(), 2)),
321 Ok(result.path),
322 "merkle path for index 2 must be the same for the MerkleTree and MerkleStore"
323 );
324
325 let result = store.get_path(smt.root(), NodeIndex::make(smt.depth(), 3)).unwrap();
326 assert_eq!(
327 VALUES4[3], result.value,
328 "Value for merkle path at index 3 must match leaf value"
329 );
330 assert_eq!(
331 smt.get_path(NodeIndex::make(smt.depth(), 3)),
332 Ok(result.path),
333 "merkle path for index 3 must be the same for the MerkleTree and MerkleStore"
334 );
335
336 let result = store.get_path(smt.root(), NodeIndex::make(smt.depth(), 4)).unwrap();
337 assert_eq!(
338 RpoDigest::default(),
339 result.value,
340 "Value for merkle path at index 4 must match leaf value"
341 );
342 assert_eq!(
343 smt.get_path(NodeIndex::make(smt.depth(), 4)),
344 Ok(result.path),
345 "merkle path for index 4 must be the same for the MerkleTree and MerkleStore"
346 );
347
348 Ok(())
349}
350
351#[test]
352fn test_add_merkle_paths() -> Result<(), MerkleError> {
353 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
354
355 let i0 = 0;
356 let p0 = mtree.get_path(NodeIndex::make(2, i0)).unwrap();
357
358 let i1 = 1;
359 let p1 = mtree.get_path(NodeIndex::make(2, i1)).unwrap();
360
361 let i2 = 2;
362 let p2 = mtree.get_path(NodeIndex::make(2, i2)).unwrap();
363
364 let i3 = 3;
365 let p3 = mtree.get_path(NodeIndex::make(2, i3)).unwrap();
366
367 let paths = [
368 (i0, VALUES4[i0 as usize], p0),
369 (i1, VALUES4[i1 as usize], p1),
370 (i2, VALUES4[i2 as usize], p2),
371 (i3, VALUES4[i3 as usize], p3),
372 ];
373
374 let mut store = MerkleStore::default();
375 store.add_merkle_paths(paths.clone()).expect("the valid paths must work");
376
377 let depth = 2;
378 let set = MerklePathSet::new(depth).with_paths(paths).unwrap();
379
380 // STORE LEAVES ARE CORRECT ==============================================================
381 // checks the leaves in the store corresponds to the expected values
382 assert_eq!(
383 store.get_node(set.root(), NodeIndex::make(set.depth(), 0)),
384 Ok(VALUES4[0]),
385 "node 0 must be in the set"
386 );
387 assert_eq!(
388 store.get_node(set.root(), NodeIndex::make(set.depth(), 1)),
389 Ok(VALUES4[1]),
390 "node 1 must be in the set"
391 );
392 assert_eq!(
393 store.get_node(set.root(), NodeIndex::make(set.depth(), 2)),
394 Ok(VALUES4[2]),
395 "node 2 must be in the set"
396 );
397 assert_eq!(
398 store.get_node(set.root(), NodeIndex::make(set.depth(), 3)),
399 Ok(VALUES4[3]),
400 "node 3 must be in the set"
401 );
402
403 // STORE LEAVES MATCH SET ================================================================
404 // sanity check the values returned by the store and the set
405 assert_eq!(
406 set.get_node(NodeIndex::make(set.depth(), 0)),
407 store.get_node(set.root(), NodeIndex::make(set.depth(), 0)),
408 "node 0 must be the same for both SparseMerkleTree and MerkleStore"
409 );
410 assert_eq!(
411 set.get_node(NodeIndex::make(set.depth(), 1)),
412 store.get_node(set.root(), NodeIndex::make(set.depth(), 1)),
413 "node 1 must be the same for both SparseMerkleTree and MerkleStore"
414 );
415 assert_eq!(
416 set.get_node(NodeIndex::make(set.depth(), 2)),
417 store.get_node(set.root(), NodeIndex::make(set.depth(), 2)),
418 "node 2 must be the same for both SparseMerkleTree and MerkleStore"
419 );
420 assert_eq!(
421 set.get_node(NodeIndex::make(set.depth(), 3)),
422 store.get_node(set.root(), NodeIndex::make(set.depth(), 3)),
423 "node 3 must be the same for both SparseMerkleTree and MerkleStore"
424 );
425
426 // STORE MERKLE PATH MATCHS ==============================================================
427 // assert the merkle path returned by the store is the same as the one in the set
428 let result = store.get_path(set.root(), NodeIndex::make(set.depth(), 0)).unwrap();
429 assert_eq!(
430 VALUES4[0], result.value,
431 "Value for merkle path at index 0 must match leaf value"
432 );
433 assert_eq!(
434 set.get_path(NodeIndex::make(set.depth(), 0)),
435 Ok(result.path),
436 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
437 );
438
439 let result = store.get_path(set.root(), NodeIndex::make(set.depth(), 1)).unwrap();
440 assert_eq!(
441 VALUES4[1], result.value,
442 "Value for merkle path at index 0 must match leaf value"
443 );
444 assert_eq!(
445 set.get_path(NodeIndex::make(set.depth(), 1)),
446 Ok(result.path),
447 "merkle path for index 1 must be the same for the MerkleTree and MerkleStore"
448 );
449
450 let result = store.get_path(set.root(), NodeIndex::make(set.depth(), 2)).unwrap();
451 assert_eq!(
452 VALUES4[2], result.value,
453 "Value for merkle path at index 0 must match leaf value"
454 );
455 assert_eq!(
456 set.get_path(NodeIndex::make(set.depth(), 2)),
457 Ok(result.path),
458 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
459 );
460
461 let result = store.get_path(set.root(), NodeIndex::make(set.depth(), 3)).unwrap();
462 assert_eq!(
463 VALUES4[3], result.value,
464 "Value for merkle path at index 0 must match leaf value"
465 );
466 assert_eq!(
467 set.get_path(NodeIndex::make(set.depth(), 3)),
468 Ok(result.path),
469 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
470 );
471
472 Ok(())
473}
474
475#[test]
476fn wont_open_to_different_depth_root() {
477 let empty = EmptySubtreeRoots::empty_hashes(64);
478 let a = [Felt::new(1); 4];
479 let b = [Felt::new(2); 4];
480
481 // Compute the root for a different depth. We cherry-pick this specific depth to prevent a
482 // regression to a bug in the past that allowed the user to fetch a node at a depth lower than
483 // the inserted path of a Merkle tree.
484 let mut root = Rpo256::merge(&[a.into(), b.into()]);
485 for depth in (1..=63).rev() {
486 root = Rpo256::merge(&[root, empty[depth]]);
487 }
488 let root = RpoDigest::from(root);
489
490 // For this example, the depth of the Merkle tree is 1, as we have only two leaves. Here we
491 // attempt to fetch a node on the maximum depth, and it should fail because the root shouldn't
492 // exist for the set.
493 let mtree = MerkleTree::new(vec![a, b]).unwrap();
494 let store = MerkleStore::from(&mtree);
495 let index = NodeIndex::root();
496 let err = store.get_node(root, index).err().unwrap();
497 assert_eq!(err, MerkleError::RootNotInStore(root));
498}
499
500#[test]
501fn store_path_opens_from_leaf() {
502 let a = [Felt::new(1); 4];
503 let b = [Felt::new(2); 4];
504 let c = [Felt::new(3); 4];
505 let d = [Felt::new(4); 4];
506 let e = [Felt::new(5); 4];
507 let f = [Felt::new(6); 4];
508 let g = [Felt::new(7); 4];
509 let h = [Felt::new(8); 4];
510
511 let i = Rpo256::merge(&[a.into(), b.into()]);
512 let j = Rpo256::merge(&[c.into(), d.into()]);
513 let k = Rpo256::merge(&[e.into(), f.into()]);
514 let l = Rpo256::merge(&[g.into(), h.into()]);
515
516 let m = Rpo256::merge(&[i.into(), j.into()]);
517 let n = Rpo256::merge(&[k.into(), l.into()]);
518
519 let root = Rpo256::merge(&[m.into(), n.into()]);
520
521 let mtree = MerkleTree::new(vec![a, b, c, d, e, f, g, h]).unwrap();
522 let store = MerkleStore::from(&mtree);
523 let path = store.get_path(root, NodeIndex::make(3, 1)).unwrap().path;
524
525 let expected = MerklePath::new([a.into(), j.into(), n.into()].to_vec());
526 assert_eq!(path, expected);
527}
528
529#[test]
530fn test_set_node() -> Result<(), MerkleError> {
531 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
532 let mut store = MerkleStore::from(&mtree);
533 let value = int_to_node(42);
534 let index = NodeIndex::make(mtree.depth(), 0);
535 let new_root = store.set_node(mtree.root(), index, value)?.root;
536 assert_eq!(store.get_node(new_root, index), Ok(value), "Value must have changed");
537
538 Ok(())
539}
540
541#[test]
542fn test_constructors() -> Result<(), MerkleError> {
543 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
544 let store = MerkleStore::from(&mtree);
545
546 let depth = mtree.depth();
547 let leaves = 2u64.pow(depth.into());
548 for index in 0..leaves {
549 let index = NodeIndex::make(depth, index);
550 let value_path = store.get_path(mtree.root(), index)?;
551 assert_eq!(mtree.get_path(index)?, value_path.path);
552 }
553
554 let depth = 32;
555 let smt = SimpleSmt::with_leaves(
556 depth,
557 KEYS4.into_iter().zip(digests_to_words(&VALUES4).into_iter()),
558 )
559 .unwrap();
560 let store = MerkleStore::from(&smt);
561 let depth = smt.depth();
562
563 for key in KEYS4 {
564 let index = NodeIndex::make(depth, key);
565 let value_path = store.get_path(smt.root(), index)?;
566 assert_eq!(smt.get_path(index)?, value_path.path);
567 }
568
569 let d = 2;
570 let paths = [
571 (0, VALUES4[0], mtree.get_path(NodeIndex::make(d, 0)).unwrap()),
572 (1, VALUES4[1], mtree.get_path(NodeIndex::make(d, 1)).unwrap()),
573 (2, VALUES4[2], mtree.get_path(NodeIndex::make(d, 2)).unwrap()),
574 (3, VALUES4[3], mtree.get_path(NodeIndex::make(d, 3)).unwrap()),
575 ];
576
577 let mut store1 = MerkleStore::default();
578 store1.add_merkle_paths(paths.clone())?;
579
580 let mut store2 = MerkleStore::default();
581 store2.add_merkle_path(0, VALUES4[0], mtree.get_path(NodeIndex::make(d, 0))?)?;
582 store2.add_merkle_path(1, VALUES4[1], mtree.get_path(NodeIndex::make(d, 1))?)?;
583 store2.add_merkle_path(2, VALUES4[2], mtree.get_path(NodeIndex::make(d, 2))?)?;
584 store2.add_merkle_path(3, VALUES4[3], mtree.get_path(NodeIndex::make(d, 3))?)?;
585 let set = MerklePathSet::new(d).with_paths(paths).unwrap();
586
587 for key in [0, 1, 2, 3] {
588 let index = NodeIndex::make(d, key);
589 let value_path1 = store1.get_path(set.root(), index)?;
590 let value_path2 = store2.get_path(set.root(), index)?;
591 assert_eq!(value_path1, value_path2);
592
593 let index = NodeIndex::make(d, key);
594 assert_eq!(set.get_path(index)?, value_path1.path);
595 }
596
597 Ok(())
598}
599
600#[test]
601fn node_path_should_be_truncated_by_midtier_insert() {
602 let key = 0b11010010_11001100_11001100_11001100_11001100_11001100_11001100_11001100_u64;
603
604 let mut store = MerkleStore::new();
605 let root: RpoDigest = EmptySubtreeRoots::empty_hashes(64)[0];
606
607 // insert first node - works as expected
608 let depth = 64;
609 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
610 let index = NodeIndex::new(depth, key).unwrap();
611 let root = store.set_node(root, index, node).unwrap().root;
612 let result = store.get_node(root, index).unwrap();
613 let path = store.get_path(root, index).unwrap().path;
614 assert_eq!(node, result);
615 assert_eq!(path.depth(), depth);
616 assert!(path.verify(index.value(), result, &root));
617
618 // flip the first bit of the key and insert the second node on a different depth
619 let key = key ^ (1 << 63);
620 let key = key >> 8;
621 let depth = 56;
622 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
623 let index = NodeIndex::new(depth, key).unwrap();
624 let root = store.set_node(root, index, node).unwrap().root;
625 let result = store.get_node(root, index).unwrap();
626 let path = store.get_path(root, index).unwrap().path;
627 assert_eq!(node, result);
628 assert_eq!(path.depth(), depth);
629 assert!(path.verify(index.value(), result, &root));
630
631 // attempt to fetch a path of the second node to depth 64
632 // should fail because the previously inserted node will remove its sub-tree from the set
633 let key = key << 8;
634 let index = NodeIndex::new(64, key).unwrap();
635 assert!(store.get_node(root, index).is_err());
636}
637
638#[test]
639fn get_leaf_depth_works_depth_64() {
640 let mut store = MerkleStore::new();
641 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(64)[0];
642 let key = u64::MAX;
643
644 // this will create a rainbow tree and test all opening to depth 64
645 for d in 0..64 {
646 let k = key & (u64::MAX >> d);
647 let node = RpoDigest::from([Felt::new(k); WORD_SIZE]);
648 let index = NodeIndex::new(64, k).unwrap();
649
650 // assert the leaf doesn't exist before the insert. the returned depth should always
651 // increment with the paths count of the set, as they are insersecting one another up to
652 // the first bits of the used key.
653 assert_eq!(d, store.get_leaf_depth(root, 64, k).unwrap());
654
655 // insert and assert the correct depth
656 root = store.set_node(root, index, node).unwrap().root;
657 assert_eq!(64, store.get_leaf_depth(root, 64, k).unwrap());
658 }
659}
660
661#[test]
662fn get_leaf_depth_works_with_incremental_depth() {
663 let mut store = MerkleStore::new();
664 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(64)[0];
665
666 // insert some path to the left of the root and assert it
667 let key = 0b01001011_10110110_00001101_01110100_00111011_10101101_00000100_01000001_u64;
668 assert_eq!(0, store.get_leaf_depth(root, 64, key).unwrap());
669 let depth = 64;
670 let index = NodeIndex::new(depth, key).unwrap();
671 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
672 root = store.set_node(root, index, node).unwrap().root;
673 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
674
675 // flip the key to the right of the root and insert some content on depth 16
676 let key = 0b11001011_10110110_00000000_00000000_00000000_00000000_00000000_00000000_u64;
677 assert_eq!(1, store.get_leaf_depth(root, 64, key).unwrap());
678 let depth = 16;
679 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
680 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
681 root = store.set_node(root, index, node).unwrap().root;
682 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
683
684 // attempt the sibling of the previous leaf
685 let key = 0b11001011_10110111_00000000_00000000_00000000_00000000_00000000_00000000_u64;
686 assert_eq!(16, store.get_leaf_depth(root, 64, key).unwrap());
687 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
688 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
689 root = store.set_node(root, index, node).unwrap().root;
690 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
691
692 // move down to the next depth and assert correct behavior
693 let key = 0b11001011_10110100_00000000_00000000_00000000_00000000_00000000_00000000_u64;
694 assert_eq!(15, store.get_leaf_depth(root, 64, key).unwrap());
695 let depth = 17;
696 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
697 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
698 root = store.set_node(root, index, node).unwrap().root;
699 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
700}
701
702#[test]
703fn get_leaf_depth_works_with_depth_8() {
704 let mut store = MerkleStore::new();
705 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(8)[0];
706
707 // insert some random, 8 depth keys. `a` diverges from the first bit
708 let a = 0b01101001_u64;
709 let b = 0b10011001_u64;
710 let c = 0b10010110_u64;
711 let d = 0b11110110_u64;
712
713 for k in [a, b, c, d] {
714 let index = NodeIndex::new(8, k).unwrap();
715 let node = RpoDigest::from([Felt::new(k); WORD_SIZE]);
716 root = store.set_node(root, index, node).unwrap().root;
717 }
718
719 // assert all leaves returns the inserted depth
720 for k in [a, b, c, d] {
721 assert_eq!(8, store.get_leaf_depth(root, 8, k).unwrap());
722 }
723
724 // flip last bit of a and expect it to return the the same depth, but for an empty node
725 assert_eq!(8, store.get_leaf_depth(root, 8, 0b01101000_u64).unwrap());
726
727 // flip fourth bit of a and expect an empty node on depth 4
728 assert_eq!(4, store.get_leaf_depth(root, 8, 0b01111001_u64).unwrap());
729
730 // flip third bit of a and expect an empty node on depth 3
731 assert_eq!(3, store.get_leaf_depth(root, 8, 0b01001001_u64).unwrap());
732
733 // flip second bit of a and expect an empty node on depth 2
734 assert_eq!(2, store.get_leaf_depth(root, 8, 0b00101001_u64).unwrap());
735
736 // flip fourth bit of c and expect an empty node on depth 4
737 assert_eq!(4, store.get_leaf_depth(root, 8, 0b10000110_u64).unwrap());
738
739 // flip second bit of d and expect an empty node on depth 3 as depth 2 conflicts with b and c
740 assert_eq!(3, store.get_leaf_depth(root, 8, 0b10110110_u64).unwrap());
741
742 // duplicate the tree on `a` and assert the depth is short-circuited by such sub-tree
743 let index = NodeIndex::new(8, a).unwrap();
744 root = store.set_node(root, index, root).unwrap().root;
745 assert_eq!(Err(MerkleError::DepthTooBig(9)), store.get_leaf_depth(root, 8, a));
746}
747
748// SUBSET EXTRACTION
749// ================================================================================================
750
751#[test]
752fn mstore_subset() {
753 // add a Merkle tree of depth 3 to the store
754 let mtree = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
755 let mut store = MerkleStore::default();
756 let empty_store_num_nodes = store.nodes.len();
757 store.extend(mtree.inner_nodes());
758
759 // build 3 subtrees contained within the above Merkle tree; note that subtree2 is a subset
760 // of subtree1
761 let subtree1 = MerkleTree::new(digests_to_words(&VALUES8[..4])).unwrap();
762 let subtree2 = MerkleTree::new(digests_to_words(&VALUES8[2..4])).unwrap();
763 let subtree3 = MerkleTree::new(digests_to_words(&VALUES8[6..])).unwrap();
764
765 // --- extract all 3 subtrees ---------------------------------------------
766
767 let substore = store.subset([subtree1.root(), subtree2.root(), subtree3.root()].iter());
768
769 // number of nodes should increase by 4: 3 nodes form subtree1 and 1 node from subtree3
770 assert_eq!(substore.nodes.len(), empty_store_num_nodes + 4);
771
772 // make sure paths that all subtrees are in the store
773 check_mstore_subtree(&substore, &subtree1);
774 check_mstore_subtree(&substore, &subtree2);
775 check_mstore_subtree(&substore, &subtree3);
776
777 // --- extract subtrees 1 and 3 -------------------------------------------
778 // this should give the same result as above as subtree2 is nested withing subtree1
779
780 let substore = store.subset([subtree1.root(), subtree3.root()].iter());
781
782 // number of nodes should increase by 4: 3 nodes form subtree1 and 1 node from subtree3
783 assert_eq!(substore.nodes.len(), empty_store_num_nodes + 4);
784
785 // make sure paths that all subtrees are in the store
786 check_mstore_subtree(&substore, &subtree1);
787 check_mstore_subtree(&substore, &subtree2);
788 check_mstore_subtree(&substore, &subtree3);
789}
790
791fn check_mstore_subtree(store: &MerkleStore, subtree: &MerkleTree) {
792 for (i, value) in subtree.leaves() {
793 let index = NodeIndex::new(subtree.depth(), i).unwrap();
794 let path1 = store.get_path(subtree.root(), index).unwrap();
795 assert_eq!(*path1.value, *value);
796
797 let path2 = subtree.get_path(index).unwrap();
798 assert_eq!(path1.path, path2);
799 }
800}
801
802// SERIALIZATION
803// ================================================================================================
804
805#[cfg(feature = "std")]
806#[test]
807fn test_serialization() -> Result<(), Box<dyn Error>> {
808 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
809 let store = MerkleStore::from(&mtree);
810 let decoded = MerkleStore::read_from_bytes(&store.to_bytes()).expect("deserialization failed");
811 assert_eq!(store, decoded);
812 Ok(())
813}