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
489 // For this example, the depth of the Merkle tree is 1, as we have only two leaves. Here we
490 // attempt to fetch a node on the maximum depth, and it should fail because the root shouldn't
491 // exist for the set.
492 let mtree = MerkleTree::new(vec![a, b]).unwrap();
493 let store = MerkleStore::from(&mtree);
494 let index = NodeIndex::root();
495 let err = store.get_node(root, index).err().unwrap();
496 assert_eq!(err, MerkleError::RootNotInStore(root));
497}
498
499#[test]
500fn store_path_opens_from_leaf() {
501 let a = [Felt::new(1); 4];
502 let b = [Felt::new(2); 4];
503 let c = [Felt::new(3); 4];
504 let d = [Felt::new(4); 4];
505 let e = [Felt::new(5); 4];
506 let f = [Felt::new(6); 4];
507 let g = [Felt::new(7); 4];
508 let h = [Felt::new(8); 4];
509
510 let i = Rpo256::merge(&[a.into(), b.into()]);
511 let j = Rpo256::merge(&[c.into(), d.into()]);
512 let k = Rpo256::merge(&[e.into(), f.into()]);
513 let l = Rpo256::merge(&[g.into(), h.into()]);
514
515 let m = Rpo256::merge(&[i, j]);
516 let n = Rpo256::merge(&[k, l]);
517
518 let root = Rpo256::merge(&[m, n]);
519
520 let mtree = MerkleTree::new(vec![a, b, c, d, e, f, g, h]).unwrap();
521 let store = MerkleStore::from(&mtree);
522 let path = store.get_path(root, NodeIndex::make(3, 1)).unwrap().path;
523
524 let expected = MerklePath::new([a.into(), j, n].to_vec());
525 assert_eq!(path, expected);
526}
527
528#[test]
529fn test_set_node() -> Result<(), MerkleError> {
530 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
531 let mut store = MerkleStore::from(&mtree);
532 let value = int_to_node(42);
533 let index = NodeIndex::make(mtree.depth(), 0);
534 let new_root = store.set_node(mtree.root(), index, value)?.root;
535 assert_eq!(store.get_node(new_root, index), Ok(value), "Value must have changed");
536
537 Ok(())
538}
539
540#[test]
541fn test_constructors() -> Result<(), MerkleError> {
542 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
543 let store = MerkleStore::from(&mtree);
544
545 let depth = mtree.depth();
546 let leaves = 2u64.pow(depth.into());
547 for index in 0..leaves {
548 let index = NodeIndex::make(depth, index);
549 let value_path = store.get_path(mtree.root(), index)?;
550 assert_eq!(mtree.get_path(index)?, value_path.path);
551 }
552
553 let depth = 32;
554 let smt = SimpleSmt::with_leaves(
555 depth,
556 KEYS4.into_iter().zip(digests_to_words(&VALUES4).into_iter()),
557 )
558 .unwrap();
559 let store = MerkleStore::from(&smt);
560 let depth = smt.depth();
561
562 for key in KEYS4 {
563 let index = NodeIndex::make(depth, key);
564 let value_path = store.get_path(smt.root(), index)?;
565 assert_eq!(smt.get_path(index)?, value_path.path);
566 }
567
568 let d = 2;
569 let paths = [
570 (0, VALUES4[0], mtree.get_path(NodeIndex::make(d, 0)).unwrap()),
571 (1, VALUES4[1], mtree.get_path(NodeIndex::make(d, 1)).unwrap()),
572 (2, VALUES4[2], mtree.get_path(NodeIndex::make(d, 2)).unwrap()),
573 (3, VALUES4[3], mtree.get_path(NodeIndex::make(d, 3)).unwrap()),
574 ];
575
576 let mut store1 = MerkleStore::default();
577 store1.add_merkle_paths(paths.clone())?;
578
579 let mut store2 = MerkleStore::default();
580 store2.add_merkle_path(0, VALUES4[0], mtree.get_path(NodeIndex::make(d, 0))?)?;
581 store2.add_merkle_path(1, VALUES4[1], mtree.get_path(NodeIndex::make(d, 1))?)?;
582 store2.add_merkle_path(2, VALUES4[2], mtree.get_path(NodeIndex::make(d, 2))?)?;
583 store2.add_merkle_path(3, VALUES4[3], mtree.get_path(NodeIndex::make(d, 3))?)?;
584 let set = MerklePathSet::new(d).with_paths(paths).unwrap();
585
586 for key in [0, 1, 2, 3] {
587 let index = NodeIndex::make(d, key);
588 let value_path1 = store1.get_path(set.root(), index)?;
589 let value_path2 = store2.get_path(set.root(), index)?;
590 assert_eq!(value_path1, value_path2);
591
592 let index = NodeIndex::make(d, key);
593 assert_eq!(set.get_path(index)?, value_path1.path);
594 }
595
596 Ok(())
597}
598
599#[test]
600fn node_path_should_be_truncated_by_midtier_insert() {
601 let key = 0b11010010_11001100_11001100_11001100_11001100_11001100_11001100_11001100_u64;
602
603 let mut store = MerkleStore::new();
604 let root: RpoDigest = EmptySubtreeRoots::empty_hashes(64)[0];
605
606 // insert first node - works as expected
607 let depth = 64;
608 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
609 let index = NodeIndex::new(depth, key).unwrap();
610 let root = store.set_node(root, index, node).unwrap().root;
611 let result = store.get_node(root, index).unwrap();
612 let path = store.get_path(root, index).unwrap().path;
613 assert_eq!(node, result);
614 assert_eq!(path.depth(), depth);
615 assert!(path.verify(index.value(), result, &root));
616
617 // flip the first bit of the key and insert the second node on a different depth
618 let key = key ^ (1 << 63);
619 let key = key >> 8;
620 let depth = 56;
621 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
622 let index = NodeIndex::new(depth, key).unwrap();
623 let root = store.set_node(root, index, node).unwrap().root;
624 let result = store.get_node(root, index).unwrap();
625 let path = store.get_path(root, index).unwrap().path;
626 assert_eq!(node, result);
627 assert_eq!(path.depth(), depth);
628 assert!(path.verify(index.value(), result, &root));
629
630 // attempt to fetch a path of the second node to depth 64
631 // should fail because the previously inserted node will remove its sub-tree from the set
632 let key = key << 8;
633 let index = NodeIndex::new(64, key).unwrap();
634 assert!(store.get_node(root, index).is_err());
635}
636
637#[test]
638fn get_leaf_depth_works_depth_64() {
639 let mut store = MerkleStore::new();
640 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(64)[0];
641 let key = u64::MAX;
642
643 // this will create a rainbow tree and test all opening to depth 64
644 for d in 0..64 {
645 let k = key & (u64::MAX >> d);
646 let node = RpoDigest::from([Felt::new(k); WORD_SIZE]);
647 let index = NodeIndex::new(64, k).unwrap();
648
649 // assert the leaf doesn't exist before the insert. the returned depth should always
650 // increment with the paths count of the set, as they are insersecting one another up to
651 // the first bits of the used key.
652 assert_eq!(d, store.get_leaf_depth(root, 64, k).unwrap());
653
654 // insert and assert the correct depth
655 root = store.set_node(root, index, node).unwrap().root;
656 assert_eq!(64, store.get_leaf_depth(root, 64, k).unwrap());
657 }
658}
659
660#[test]
661fn get_leaf_depth_works_with_incremental_depth() {
662 let mut store = MerkleStore::new();
663 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(64)[0];
664
665 // insert some path to the left of the root and assert it
666 let key = 0b01001011_10110110_00001101_01110100_00111011_10101101_00000100_01000001_u64;
667 assert_eq!(0, store.get_leaf_depth(root, 64, key).unwrap());
668 let depth = 64;
669 let index = NodeIndex::new(depth, key).unwrap();
670 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
671 root = store.set_node(root, index, node).unwrap().root;
672 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
673
674 // flip the key to the right of the root and insert some content on depth 16
675 let key = 0b11001011_10110110_00000000_00000000_00000000_00000000_00000000_00000000_u64;
676 assert_eq!(1, store.get_leaf_depth(root, 64, key).unwrap());
677 let depth = 16;
678 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
679 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
680 root = store.set_node(root, index, node).unwrap().root;
681 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
682
683 // attempt the sibling of the previous leaf
684 let key = 0b11001011_10110111_00000000_00000000_00000000_00000000_00000000_00000000_u64;
685 assert_eq!(16, store.get_leaf_depth(root, 64, key).unwrap());
686 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
687 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
688 root = store.set_node(root, index, node).unwrap().root;
689 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
690
691 // move down to the next depth and assert correct behavior
692 let key = 0b11001011_10110100_00000000_00000000_00000000_00000000_00000000_00000000_u64;
693 assert_eq!(15, store.get_leaf_depth(root, 64, key).unwrap());
694 let depth = 17;
695 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
696 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
697 root = store.set_node(root, index, node).unwrap().root;
698 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
699}
700
701#[test]
702fn get_leaf_depth_works_with_depth_8() {
703 let mut store = MerkleStore::new();
704 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(8)[0];
705
706 // insert some random, 8 depth keys. `a` diverges from the first bit
707 let a = 0b01101001_u64;
708 let b = 0b10011001_u64;
709 let c = 0b10010110_u64;
710 let d = 0b11110110_u64;
711
712 for k in [a, b, c, d] {
713 let index = NodeIndex::new(8, k).unwrap();
714 let node = RpoDigest::from([Felt::new(k); WORD_SIZE]);
715 root = store.set_node(root, index, node).unwrap().root;
716 }
717
718 // assert all leaves returns the inserted depth
719 for k in [a, b, c, d] {
720 assert_eq!(8, store.get_leaf_depth(root, 8, k).unwrap());
721 }
722
723 // flip last bit of a and expect it to return the the same depth, but for an empty node
724 assert_eq!(8, store.get_leaf_depth(root, 8, 0b01101000_u64).unwrap());
725
726 // flip fourth bit of a and expect an empty node on depth 4
727 assert_eq!(4, store.get_leaf_depth(root, 8, 0b01111001_u64).unwrap());
728
729 // flip third bit of a and expect an empty node on depth 3
730 assert_eq!(3, store.get_leaf_depth(root, 8, 0b01001001_u64).unwrap());
731
732 // flip second bit of a and expect an empty node on depth 2
733 assert_eq!(2, store.get_leaf_depth(root, 8, 0b00101001_u64).unwrap());
734
735 // flip fourth bit of c and expect an empty node on depth 4
736 assert_eq!(4, store.get_leaf_depth(root, 8, 0b10000110_u64).unwrap());
737
738 // flip second bit of d and expect an empty node on depth 3 as depth 2 conflicts with b and c
739 assert_eq!(3, store.get_leaf_depth(root, 8, 0b10110110_u64).unwrap());
740
741 // duplicate the tree on `a` and assert the depth is short-circuited by such sub-tree
742 let index = NodeIndex::new(8, a).unwrap();
743 root = store.set_node(root, index, root).unwrap().root;
744 assert_eq!(Err(MerkleError::DepthTooBig(9)), store.get_leaf_depth(root, 8, a));
745}
746
747// SUBSET EXTRACTION
748// ================================================================================================
749
750#[test]
751fn mstore_subset() {
752 // add a Merkle tree of depth 3 to the store
753 let mtree = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
754 let mut store = MerkleStore::default();
755 let empty_store_num_nodes = store.nodes.len();
756 store.extend(mtree.inner_nodes());
757
758 // build 3 subtrees contained within the above Merkle tree; note that subtree2 is a subset
759 // of subtree1
760 let subtree1 = MerkleTree::new(digests_to_words(&VALUES8[..4])).unwrap();
761 let subtree2 = MerkleTree::new(digests_to_words(&VALUES8[2..4])).unwrap();
762 let subtree3 = MerkleTree::new(digests_to_words(&VALUES8[6..])).unwrap();
763
764 // --- extract all 3 subtrees ---------------------------------------------
765
766 let substore = store.subset([subtree1.root(), subtree2.root(), subtree3.root()].iter());
767
768 // number of nodes should increase by 4: 3 nodes form subtree1 and 1 node from subtree3
769 assert_eq!(substore.nodes.len(), empty_store_num_nodes + 4);
770
771 // make sure paths that all subtrees are in the store
772 check_mstore_subtree(&substore, &subtree1);
773 check_mstore_subtree(&substore, &subtree2);
774 check_mstore_subtree(&substore, &subtree3);
775
776 // --- extract subtrees 1 and 3 -------------------------------------------
777 // this should give the same result as above as subtree2 is nested withing subtree1
778
779 let substore = store.subset([subtree1.root(), subtree3.root()].iter());
780
781 // number of nodes should increase by 4: 3 nodes form subtree1 and 1 node from subtree3
782 assert_eq!(substore.nodes.len(), empty_store_num_nodes + 4);
783
784 // make sure paths that all subtrees are in the store
785 check_mstore_subtree(&substore, &subtree1);
786 check_mstore_subtree(&substore, &subtree2);
787 check_mstore_subtree(&substore, &subtree3);
788}
789
790fn check_mstore_subtree(store: &MerkleStore, subtree: &MerkleTree) {
791 for (i, value) in subtree.leaves() {
792 let index = NodeIndex::new(subtree.depth(), i).unwrap();
793 let path1 = store.get_path(subtree.root(), index).unwrap();
794 assert_eq!(*path1.value, *value);
795
796 let path2 = subtree.get_path(index).unwrap();
797 assert_eq!(path1.path, path2);
798 }
799}
800
801// SERIALIZATION
802// ================================================================================================
803
804#[cfg(feature = "std")]
805#[test]
806fn test_serialization() -> Result<(), Box<dyn Error>> {
807 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
808 let store = MerkleStore::from(&mtree);
809 let decoded = MerkleStore::read_from_bytes(&store.to_bytes()).expect("deserialization failed");
810 assert_eq!(store, decoded);
811 Ok(())
812}