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