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