miden-crypto/src/merkle/store/tests.rs
src/merkle/store/tests.rsRaw
1use super::*;
2use crate::{
3 hash::rpo::Rpo256,
4 merkle::{int_to_node, MerklePathSet},
5 Felt, Word, WORD_SIZE, ZERO,
6};
7
8const KEYS4: [u64; 4] = [0, 1, 2, 3];
9const LEAVES4: [Word; 4] = [
10 int_to_node(1),
11 int_to_node(2),
12 int_to_node(3),
13 int_to_node(4),
14];
15const EMPTY: Word = [ZERO; WORD_SIZE];
16
17#[test]
18fn test_root_not_in_store() -> Result<(), MerkleError> {
19 let mtree = MerkleTree::new(LEAVES4.to_vec())?;
20 let store = MerkleStore::default().with_merkle_tree(LEAVES4)?;
21 assert_eq!(
22 store.get_node(LEAVES4[0], NodeIndex::new(mtree.depth(), 0)),
23 Err(MerkleError::RootNotInStore(LEAVES4[0])),
24 "Leaf 0 is not a root"
25 );
26 assert_eq!(
27 store.get_path(LEAVES4[0], NodeIndex::new(mtree.depth(), 0)),
28 Err(MerkleError::RootNotInStore(LEAVES4[0])),
29 "Leaf 0 is not a root"
30 );
31
32 Ok(())
33}
34
35#[test]
36fn test_merkle_tree() -> Result<(), MerkleError> {
37 let mut store = MerkleStore::default();
38
39 let mtree = MerkleTree::new(LEAVES4.to_vec())?;
40 store.add_merkle_tree(LEAVES4.to_vec())?;
41
42 // STORE LEAVES ARE CORRECT ==============================================================
43 // checks the leaves in the store corresponds to the expected values
44 assert_eq!(
45 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 0)),
46 Ok(LEAVES4[0]),
47 "node 0 must be in the tree"
48 );
49 assert_eq!(
50 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 1)),
51 Ok(LEAVES4[1]),
52 "node 1 must be in the tree"
53 );
54 assert_eq!(
55 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 2)),
56 Ok(LEAVES4[2]),
57 "node 2 must be in the tree"
58 );
59 assert_eq!(
60 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 3)),
61 Ok(LEAVES4[3]),
62 "node 3 must be in the tree"
63 );
64
65 // STORE LEAVES MATCH TREE ===============================================================
66 // sanity check the values returned by the store and the tree
67 assert_eq!(
68 mtree.get_node(NodeIndex::new(mtree.depth(), 0)),
69 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 0)),
70 "node 0 must be the same for both MerkleTree and MerkleStore"
71 );
72 assert_eq!(
73 mtree.get_node(NodeIndex::new(mtree.depth(), 1)),
74 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 1)),
75 "node 1 must be the same for both MerkleTree and MerkleStore"
76 );
77 assert_eq!(
78 mtree.get_node(NodeIndex::new(mtree.depth(), 2)),
79 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 2)),
80 "node 2 must be the same for both MerkleTree and MerkleStore"
81 );
82 assert_eq!(
83 mtree.get_node(NodeIndex::new(mtree.depth(), 3)),
84 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 3)),
85 "node 3 must be the same for both MerkleTree and MerkleStore"
86 );
87
88 // STORE MERKLE PATH MATCHS ==============================================================
89 // assert the merkle path returned by the store is the same as the one in the tree
90 let result = store
91 .get_path(mtree.root(), NodeIndex::new(mtree.depth(), 0))
92 .unwrap();
93 assert_eq!(
94 LEAVES4[0], result.value,
95 "Value for merkle path at index 0 must match leaf value"
96 );
97 assert_eq!(
98 mtree.get_path(NodeIndex::new(mtree.depth(), 0)),
99 Ok(result.path),
100 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
101 );
102
103 let result = store
104 .get_path(mtree.root(), NodeIndex::new(mtree.depth(), 1))
105 .unwrap();
106 assert_eq!(
107 LEAVES4[1], result.value,
108 "Value for merkle path at index 0 must match leaf value"
109 );
110 assert_eq!(
111 mtree.get_path(NodeIndex::new(mtree.depth(), 1)),
112 Ok(result.path),
113 "merkle path for index 1 must be the same for the MerkleTree and MerkleStore"
114 );
115
116 let result = store
117 .get_path(mtree.root(), NodeIndex::new(mtree.depth(), 2))
118 .unwrap();
119 assert_eq!(
120 LEAVES4[2], result.value,
121 "Value for merkle path at index 0 must match leaf value"
122 );
123 assert_eq!(
124 mtree.get_path(NodeIndex::new(mtree.depth(), 2)),
125 Ok(result.path),
126 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
127 );
128
129 let result = store
130 .get_path(mtree.root(), NodeIndex::new(mtree.depth(), 3))
131 .unwrap();
132 assert_eq!(
133 LEAVES4[3], result.value,
134 "Value for merkle path at index 0 must match leaf value"
135 );
136 assert_eq!(
137 mtree.get_path(NodeIndex::new(mtree.depth(), 3)),
138 Ok(result.path),
139 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
140 );
141
142 Ok(())
143}
144
145#[test]
146fn test_empty_roots() {
147 let store = MerkleStore::default();
148 let mut root = RpoDigest::new(EMPTY);
149
150 for depth in 0..255 {
151 root = Rpo256::merge(&[root; 2]);
152 assert!(
153 store.get_node(root.into(), NodeIndex::new(0, 0)).is_ok(),
154 "The root of the empty tree of depth {depth} must be registered"
155 );
156 }
157}
158
159#[test]
160fn test_leaf_paths_for_empty_trees() -> Result<(), MerkleError> {
161 let store = MerkleStore::default();
162
163 // Starts at 1 because leafs are not included in the store.
164 // Ends at 64 because it is not possible to represent an index of a depth greater than 64,
165 // because a u64 is used to index the leaf.
166 for depth in 1..64 {
167 let smt = SimpleSmt::new(depth)?;
168
169 let index = NodeIndex::new(depth, 0);
170 let store_path = store.get_path(smt.root(), index)?;
171 let smt_path = smt.get_path(index)?;
172 assert_eq!(
173 store_path.value, EMPTY,
174 "the leaf of an empty tree is always ZERO"
175 );
176 assert_eq!(
177 store_path.path, smt_path,
178 "the returned merkle path does not match the computed values"
179 );
180 assert_eq!(
181 store_path.path.compute_root(depth.into(), EMPTY),
182 smt.root(),
183 "computed root from the path must match the empty tree root"
184 );
185 }
186
187 Ok(())
188}
189
190#[test]
191fn test_get_invalid_node() {
192 let mut store = MerkleStore::default();
193 let mtree = MerkleTree::new(LEAVES4.to_vec()).expect("creating a merkle tree must work");
194 store
195 .add_merkle_tree(LEAVES4.to_vec())
196 .expect("adding a merkle tree to the store must work");
197 let _ = store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 3));
198}
199
200#[test]
201fn test_add_sparse_merkle_tree_one_level() -> Result<(), MerkleError> {
202 let mut store = MerkleStore::default();
203 let keys2: [u64; 2] = [0, 1];
204 let leaves2: [Word; 2] = [int_to_node(1), int_to_node(2)];
205 store.add_sparse_merkle_tree(keys2.into_iter().zip(leaves2.into_iter()))?;
206 let smt = SimpleSmt::new(1)
207 .unwrap()
208 .with_leaves(keys2.into_iter().zip(leaves2.into_iter()))
209 .unwrap();
210
211 let idx = NodeIndex::new(1, 0);
212 assert_eq!(smt.get_node(&idx).unwrap(), leaves2[0]);
213 assert_eq!(
214 store.get_node(smt.root(), idx).unwrap(),
215 smt.get_node(&idx).unwrap()
216 );
217
218 let idx = NodeIndex::new(1, 1);
219 assert_eq!(smt.get_node(&idx).unwrap(), leaves2[1]);
220 assert_eq!(
221 store.get_node(smt.root(), idx).unwrap(),
222 smt.get_node(&idx).unwrap()
223 );
224
225 Ok(())
226}
227
228#[test]
229fn test_sparse_merkle_tree() -> Result<(), MerkleError> {
230 let mut store = MerkleStore::default();
231 store.add_sparse_merkle_tree(KEYS4.into_iter().zip(LEAVES4.into_iter()))?;
232
233 let smt = SimpleSmt::new(SimpleSmt::MAX_DEPTH)
234 .unwrap()
235 .with_leaves(KEYS4.into_iter().zip(LEAVES4.into_iter()))
236 .unwrap();
237
238 // STORE LEAVES ARE CORRECT ==============================================================
239 // checks the leaves in the store corresponds to the expected values
240 assert_eq!(
241 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 0)),
242 Ok(LEAVES4[0]),
243 "node 0 must be in the tree"
244 );
245 assert_eq!(
246 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 1)),
247 Ok(LEAVES4[1]),
248 "node 1 must be in the tree"
249 );
250 assert_eq!(
251 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 2)),
252 Ok(LEAVES4[2]),
253 "node 2 must be in the tree"
254 );
255 assert_eq!(
256 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 3)),
257 Ok(LEAVES4[3]),
258 "node 3 must be in the tree"
259 );
260 assert_eq!(
261 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 4)),
262 Ok(EMPTY),
263 "unmodified node 4 must be ZERO"
264 );
265
266 // STORE LEAVES MATCH TREE ===============================================================
267 // sanity check the values returned by the store and the tree
268 assert_eq!(
269 smt.get_node(&NodeIndex::new(smt.depth(), 0)),
270 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 0)),
271 "node 0 must be the same for both SparseMerkleTree and MerkleStore"
272 );
273 assert_eq!(
274 smt.get_node(&NodeIndex::new(smt.depth(), 1)),
275 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 1)),
276 "node 1 must be the same for both SparseMerkleTree and MerkleStore"
277 );
278 assert_eq!(
279 smt.get_node(&NodeIndex::new(smt.depth(), 2)),
280 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 2)),
281 "node 2 must be the same for both SparseMerkleTree and MerkleStore"
282 );
283 assert_eq!(
284 smt.get_node(&NodeIndex::new(smt.depth(), 3)),
285 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 3)),
286 "node 3 must be the same for both SparseMerkleTree and MerkleStore"
287 );
288 assert_eq!(
289 smt.get_node(&NodeIndex::new(smt.depth(), 4)),
290 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 4)),
291 "node 4 must be the same for both SparseMerkleTree and MerkleStore"
292 );
293
294 // STORE MERKLE PATH MATCHS ==============================================================
295 // assert the merkle path returned by the store is the same as the one in the tree
296 let result = store
297 .get_path(smt.root(), NodeIndex::new(smt.depth(), 0))
298 .unwrap();
299 assert_eq!(
300 LEAVES4[0], result.value,
301 "Value for merkle path at index 0 must match leaf value"
302 );
303 assert_eq!(
304 smt.get_path(NodeIndex::new(smt.depth(), 0)),
305 Ok(result.path),
306 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
307 );
308
309 let result = store
310 .get_path(smt.root(), NodeIndex::new(smt.depth(), 1))
311 .unwrap();
312 assert_eq!(
313 LEAVES4[1], result.value,
314 "Value for merkle path at index 1 must match leaf value"
315 );
316 assert_eq!(
317 smt.get_path(NodeIndex::new(smt.depth(), 1)),
318 Ok(result.path),
319 "merkle path for index 1 must be the same for the MerkleTree and MerkleStore"
320 );
321
322 let result = store
323 .get_path(smt.root(), NodeIndex::new(smt.depth(), 2))
324 .unwrap();
325 assert_eq!(
326 LEAVES4[2], result.value,
327 "Value for merkle path at index 2 must match leaf value"
328 );
329 assert_eq!(
330 smt.get_path(NodeIndex::new(smt.depth(), 2)),
331 Ok(result.path),
332 "merkle path for index 2 must be the same for the MerkleTree and MerkleStore"
333 );
334
335 let result = store
336 .get_path(smt.root(), NodeIndex::new(smt.depth(), 3))
337 .unwrap();
338 assert_eq!(
339 LEAVES4[3], result.value,
340 "Value for merkle path at index 3 must match leaf value"
341 );
342 assert_eq!(
343 smt.get_path(NodeIndex::new(smt.depth(), 3)),
344 Ok(result.path),
345 "merkle path for index 3 must be the same for the MerkleTree and MerkleStore"
346 );
347
348 let result = store
349 .get_path(smt.root(), NodeIndex::new(smt.depth(), 4))
350 .unwrap();
351 assert_eq!(
352 EMPTY, result.value,
353 "Value for merkle path at index 4 must match leaf value"
354 );
355 assert_eq!(
356 smt.get_path(NodeIndex::new(smt.depth(), 4)),
357 Ok(result.path),
358 "merkle path for index 4 must be the same for the MerkleTree and MerkleStore"
359 );
360
361 Ok(())
362}
363
364#[test]
365fn test_add_merkle_paths() -> Result<(), MerkleError> {
366 let mtree = MerkleTree::new(LEAVES4.to_vec())?;
367
368 let i0 = 0;
369 let p0 = mtree.get_path(NodeIndex::new(2, i0)).unwrap();
370
371 let i1 = 1;
372 let p1 = mtree.get_path(NodeIndex::new(2, i1)).unwrap();
373
374 let i2 = 2;
375 let p2 = mtree.get_path(NodeIndex::new(2, i2)).unwrap();
376
377 let i3 = 3;
378 let p3 = mtree.get_path(NodeIndex::new(2, i3)).unwrap();
379
380 let paths = [
381 (i0, LEAVES4[i0 as usize], p0),
382 (i1, LEAVES4[i1 as usize], p1),
383 (i2, LEAVES4[i2 as usize], p2),
384 (i3, LEAVES4[i3 as usize], p3),
385 ];
386
387 let mut store = MerkleStore::default();
388 store
389 .add_merkle_paths(paths.clone())
390 .expect("the valid paths must work");
391
392 let depth = 2;
393 let set = MerklePathSet::new(depth).with_paths(paths).unwrap();
394
395 // STORE LEAVES ARE CORRECT ==============================================================
396 // checks the leaves in the store corresponds to the expected values
397 assert_eq!(
398 store.get_node(set.root(), NodeIndex::new(set.depth(), 0)),
399 Ok(LEAVES4[0]),
400 "node 0 must be in the set"
401 );
402 assert_eq!(
403 store.get_node(set.root(), NodeIndex::new(set.depth(), 1)),
404 Ok(LEAVES4[1]),
405 "node 1 must be in the set"
406 );
407 assert_eq!(
408 store.get_node(set.root(), NodeIndex::new(set.depth(), 2)),
409 Ok(LEAVES4[2]),
410 "node 2 must be in the set"
411 );
412 assert_eq!(
413 store.get_node(set.root(), NodeIndex::new(set.depth(), 3)),
414 Ok(LEAVES4[3]),
415 "node 3 must be in the set"
416 );
417
418 // STORE LEAVES MATCH SET ================================================================
419 // sanity check the values returned by the store and the set
420 assert_eq!(
421 set.get_node(NodeIndex::new(set.depth(), 0)),
422 store.get_node(set.root(), NodeIndex::new(set.depth(), 0)),
423 "node 0 must be the same for both SparseMerkleTree and MerkleStore"
424 );
425 assert_eq!(
426 set.get_node(NodeIndex::new(set.depth(), 1)),
427 store.get_node(set.root(), NodeIndex::new(set.depth(), 1)),
428 "node 1 must be the same for both SparseMerkleTree and MerkleStore"
429 );
430 assert_eq!(
431 set.get_node(NodeIndex::new(set.depth(), 2)),
432 store.get_node(set.root(), NodeIndex::new(set.depth(), 2)),
433 "node 2 must be the same for both SparseMerkleTree and MerkleStore"
434 );
435 assert_eq!(
436 set.get_node(NodeIndex::new(set.depth(), 3)),
437 store.get_node(set.root(), NodeIndex::new(set.depth(), 3)),
438 "node 3 must be the same for both SparseMerkleTree and MerkleStore"
439 );
440
441 // STORE MERKLE PATH MATCHS ==============================================================
442 // assert the merkle path returned by the store is the same as the one in the set
443 let result = store
444 .get_path(set.root(), NodeIndex::new(set.depth(), 0))
445 .unwrap();
446 assert_eq!(
447 LEAVES4[0], result.value,
448 "Value for merkle path at index 0 must match leaf value"
449 );
450 assert_eq!(
451 set.get_path(NodeIndex::new(set.depth(), 0)),
452 Ok(result.path),
453 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
454 );
455
456 let result = store
457 .get_path(set.root(), NodeIndex::new(set.depth(), 1))
458 .unwrap();
459 assert_eq!(
460 LEAVES4[1], result.value,
461 "Value for merkle path at index 0 must match leaf value"
462 );
463 assert_eq!(
464 set.get_path(NodeIndex::new(set.depth(), 1)),
465 Ok(result.path),
466 "merkle path for index 1 must be the same for the MerkleTree and MerkleStore"
467 );
468
469 let result = store
470 .get_path(set.root(), NodeIndex::new(set.depth(), 2))
471 .unwrap();
472 assert_eq!(
473 LEAVES4[2], result.value,
474 "Value for merkle path at index 0 must match leaf value"
475 );
476 assert_eq!(
477 set.get_path(NodeIndex::new(set.depth(), 2)),
478 Ok(result.path),
479 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
480 );
481
482 let result = store
483 .get_path(set.root(), NodeIndex::new(set.depth(), 3))
484 .unwrap();
485 assert_eq!(
486 LEAVES4[3], result.value,
487 "Value for merkle path at index 0 must match leaf value"
488 );
489 assert_eq!(
490 set.get_path(NodeIndex::new(set.depth(), 3)),
491 Ok(result.path),
492 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
493 );
494
495 Ok(())
496}
497
498#[test]
499fn wont_open_to_different_depth_root() {
500 let empty = EmptySubtreeRoots::empty_hashes(64);
501 let a = [Felt::new(1); 4];
502 let b = [Felt::new(2); 4];
503
504 // Compute the root for a different depth. We cherry-pick this specific depth to prevent a
505 // regression to a bug in the past that allowed the user to fetch a node at a depth lower than
506 // the inserted path of a Merkle tree.
507 let mut root = Rpo256::merge(&[a.into(), b.into()]);
508 for depth in (1..=63).rev() {
509 root = Rpo256::merge(&[root, empty[depth]]);
510 }
511 let root = Word::from(root);
512
513 // For this example, the depth of the Merkle tree is 1, as we have only two leaves. Here we
514 // attempt to fetch a node on the maximum depth, and it should fail because the root shouldn't
515 // exist for the set.
516 let store = MerkleStore::default().with_merkle_tree([a, b]).unwrap();
517 let index = NodeIndex::root();
518 let err = store.get_node(root, index).err().unwrap();
519 assert_eq!(err, MerkleError::RootNotInStore(root));
520}
521
522#[test]
523fn store_path_opens_from_leaf() {
524 let a = [Felt::new(1); 4];
525 let b = [Felt::new(2); 4];
526 let c = [Felt::new(3); 4];
527 let d = [Felt::new(4); 4];
528 let e = [Felt::new(5); 4];
529 let f = [Felt::new(6); 4];
530 let g = [Felt::new(7); 4];
531 let h = [Felt::new(8); 4];
532
533 let i = Rpo256::merge(&[a.into(), b.into()]);
534 let j = Rpo256::merge(&[c.into(), d.into()]);
535 let k = Rpo256::merge(&[e.into(), f.into()]);
536 let l = Rpo256::merge(&[g.into(), h.into()]);
537
538 let m = Rpo256::merge(&[i.into(), j.into()]);
539 let n = Rpo256::merge(&[k.into(), l.into()]);
540
541 let root = Rpo256::merge(&[m.into(), n.into()]);
542
543 let store = MerkleStore::default()
544 .with_merkle_tree([a, b, c, d, e, f, g, h])
545 .unwrap();
546 let path = store
547 .get_path(root.into(), NodeIndex::new(3, 1))
548 .unwrap()
549 .path;
550
551 let expected = MerklePath::new([a.into(), j.into(), n.into()].to_vec());
552 assert_eq!(path, expected);
553}
554
555#[test]
556fn test_set_node() -> Result<(), MerkleError> {
557 let mtree = MerkleTree::new(LEAVES4.to_vec())?;
558 let mut store = MerkleStore::default().with_merkle_tree(LEAVES4)?;
559 let value = int_to_node(42);
560 let index = NodeIndex::new(mtree.depth(), 0);
561 let new_root = store.set_node(mtree.root(), index, value)?.root;
562 assert_eq!(
563 store.get_node(new_root, index),
564 Ok(value),
565 "Value must have changed"
566 );
567
568 Ok(())
569}
570
571#[test]
572fn test_constructors() -> Result<(), MerkleError> {
573 let store = MerkleStore::new().with_merkle_tree(LEAVES4)?;
574 let mtree = MerkleTree::new(LEAVES4.to_vec())?;
575
576 let depth = mtree.depth();
577 let leaves = 2u64.pow(depth.into());
578 for index in 0..leaves {
579 let index = NodeIndex::new(depth, index);
580 let value_path = store.get_path(mtree.root(), index)?;
581 assert_eq!(mtree.get_path(index)?, value_path.path);
582 }
583
584 let store = MerkleStore::default()
585 .with_sparse_merkle_tree(KEYS4.into_iter().zip(LEAVES4.into_iter()))?;
586 let smt = SimpleSmt::new(SimpleSmt::MAX_DEPTH)
587 .unwrap()
588 .with_leaves(KEYS4.into_iter().zip(LEAVES4.into_iter()))
589 .unwrap();
590 let depth = smt.depth();
591
592 for key in KEYS4 {
593 let index = NodeIndex::new(depth, key);
594 let value_path = store.get_path(smt.root(), index)?;
595 assert_eq!(smt.get_path(index)?, value_path.path);
596 }
597
598 let d = 2;
599 let paths = [
600 (0, LEAVES4[0], mtree.get_path(NodeIndex::new(d, 0)).unwrap()),
601 (1, LEAVES4[1], mtree.get_path(NodeIndex::new(d, 1)).unwrap()),
602 (2, LEAVES4[2], mtree.get_path(NodeIndex::new(d, 2)).unwrap()),
603 (3, LEAVES4[3], mtree.get_path(NodeIndex::new(d, 3)).unwrap()),
604 ];
605
606 let store1 = MerkleStore::default().with_merkle_paths(paths.clone())?;
607 let store2 = MerkleStore::default()
608 .with_merkle_path(0, LEAVES4[0], mtree.get_path(NodeIndex::new(d, 0))?)?
609 .with_merkle_path(1, LEAVES4[1], mtree.get_path(NodeIndex::new(d, 1))?)?
610 .with_merkle_path(2, LEAVES4[2], mtree.get_path(NodeIndex::new(d, 2))?)?
611 .with_merkle_path(3, LEAVES4[3], mtree.get_path(NodeIndex::new(d, 3))?)?;
612 let set = MerklePathSet::new(d).with_paths(paths).unwrap();
613
614 for key in [0, 1, 2, 3] {
615 let index = NodeIndex::new(d, key);
616 let value_path1 = store1.get_path(set.root(), index)?;
617 let value_path2 = store2.get_path(set.root(), index)?;
618 assert_eq!(value_path1, value_path2);
619
620 let index = NodeIndex::new(d, key);
621 assert_eq!(set.get_path(index)?, value_path1.path);
622 }
623
624 Ok(())
625}