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