miden-crypto/src/merkle/store/tests.rs
src/merkle/store/tests.rsRaw
1use super::{
2 DefaultMerkleStore as MerkleStore, EmptySubtreeRoots, MerkleError, MerklePath, NodeIndex,
3 PartialMerkleTree, RecordingMerkleStore, RpoDigest,
4};
5use crate::{
6 hash::rpo::Rpo256,
7 merkle::{digests_to_words, int_to_leaf, int_to_node, 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 pmt = PartialMerkleTree::with_paths(paths).unwrap();
382
383 // STORE LEAVES ARE CORRECT ==============================================================
384 // checks the leaves in the store corresponds to the expected values
385 assert_eq!(
386 store.get_node(pmt.root(), NodeIndex::make(pmt.max_depth(), 0)),
387 Ok(VALUES4[0]),
388 "node 0 must be in the pmt"
389 );
390 assert_eq!(
391 store.get_node(pmt.root(), NodeIndex::make(pmt.max_depth(), 1)),
392 Ok(VALUES4[1]),
393 "node 1 must be in the pmt"
394 );
395 assert_eq!(
396 store.get_node(pmt.root(), NodeIndex::make(pmt.max_depth(), 2)),
397 Ok(VALUES4[2]),
398 "node 2 must be in the pmt"
399 );
400 assert_eq!(
401 store.get_node(pmt.root(), NodeIndex::make(pmt.max_depth(), 3)),
402 Ok(VALUES4[3]),
403 "node 3 must be in the pmt"
404 );
405
406 // STORE LEAVES MATCH PMT ================================================================
407 // sanity check the values returned by the store and the pmt
408 assert_eq!(
409 pmt.get_node(NodeIndex::make(pmt.max_depth(), 0)),
410 store.get_node(pmt.root(), NodeIndex::make(pmt.max_depth(), 0)),
411 "node 0 must be the same for both PartialMerkleTree and MerkleStore"
412 );
413 assert_eq!(
414 pmt.get_node(NodeIndex::make(pmt.max_depth(), 1)),
415 store.get_node(pmt.root(), NodeIndex::make(pmt.max_depth(), 1)),
416 "node 1 must be the same for both PartialMerkleTree and MerkleStore"
417 );
418 assert_eq!(
419 pmt.get_node(NodeIndex::make(pmt.max_depth(), 2)),
420 store.get_node(pmt.root(), NodeIndex::make(pmt.max_depth(), 2)),
421 "node 2 must be the same for both PartialMerkleTree and MerkleStore"
422 );
423 assert_eq!(
424 pmt.get_node(NodeIndex::make(pmt.max_depth(), 3)),
425 store.get_node(pmt.root(), NodeIndex::make(pmt.max_depth(), 3)),
426 "node 3 must be the same for both PartialMerkleTree and MerkleStore"
427 );
428
429 // STORE MERKLE PATH MATCHS ==============================================================
430 // assert the merkle path returned by the store is the same as the one in the pmt
431 let result = store.get_path(pmt.root(), NodeIndex::make(pmt.max_depth(), 0)).unwrap();
432 assert_eq!(
433 VALUES4[0], result.value,
434 "Value for merkle path at index 0 must match leaf value"
435 );
436 assert_eq!(
437 pmt.get_path(NodeIndex::make(pmt.max_depth(), 0)),
438 Ok(result.path),
439 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
440 );
441
442 let result = store.get_path(pmt.root(), NodeIndex::make(pmt.max_depth(), 1)).unwrap();
443 assert_eq!(
444 VALUES4[1], result.value,
445 "Value for merkle path at index 0 must match leaf value"
446 );
447 assert_eq!(
448 pmt.get_path(NodeIndex::make(pmt.max_depth(), 1)),
449 Ok(result.path),
450 "merkle path for index 1 must be the same for the MerkleTree and MerkleStore"
451 );
452
453 let result = store.get_path(pmt.root(), NodeIndex::make(pmt.max_depth(), 2)).unwrap();
454 assert_eq!(
455 VALUES4[2], result.value,
456 "Value for merkle path at index 0 must match leaf value"
457 );
458 assert_eq!(
459 pmt.get_path(NodeIndex::make(pmt.max_depth(), 2)),
460 Ok(result.path),
461 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
462 );
463
464 let result = store.get_path(pmt.root(), NodeIndex::make(pmt.max_depth(), 3)).unwrap();
465 assert_eq!(
466 VALUES4[3], result.value,
467 "Value for merkle path at index 0 must match leaf value"
468 );
469 assert_eq!(
470 pmt.get_path(NodeIndex::make(pmt.max_depth(), 3)),
471 Ok(result.path),
472 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
473 );
474
475 Ok(())
476}
477
478#[test]
479fn wont_open_to_different_depth_root() {
480 let empty = EmptySubtreeRoots::empty_hashes(64);
481 let a = [Felt::new(1); 4];
482 let b = [Felt::new(2); 4];
483
484 // Compute the root for a different depth. We cherry-pick this specific depth to prevent a
485 // regression to a bug in the past that allowed the user to fetch a node at a depth lower than
486 // the inserted path of a Merkle tree.
487 let mut root = Rpo256::merge(&[a.into(), b.into()]);
488 for depth in (1..=63).rev() {
489 root = Rpo256::merge(&[root, empty[depth]]);
490 }
491
492 // For this example, the depth of the Merkle tree is 1, as we have only two leaves. Here we
493 // attempt to fetch a node on the maximum depth, and it should fail because the root shouldn't
494 // exist for the set.
495 let mtree = MerkleTree::new(vec![a, b]).unwrap();
496 let store = MerkleStore::from(&mtree);
497 let index = NodeIndex::root();
498 let err = store.get_node(root, index).err().unwrap();
499 assert_eq!(err, MerkleError::RootNotInStore(root));
500}
501
502#[test]
503fn store_path_opens_from_leaf() {
504 let a = [Felt::new(1); 4];
505 let b = [Felt::new(2); 4];
506 let c = [Felt::new(3); 4];
507 let d = [Felt::new(4); 4];
508 let e = [Felt::new(5); 4];
509 let f = [Felt::new(6); 4];
510 let g = [Felt::new(7); 4];
511 let h = [Felt::new(8); 4];
512
513 let i = Rpo256::merge(&[a.into(), b.into()]);
514 let j = Rpo256::merge(&[c.into(), d.into()]);
515 let k = Rpo256::merge(&[e.into(), f.into()]);
516 let l = Rpo256::merge(&[g.into(), h.into()]);
517
518 let m = Rpo256::merge(&[i, j]);
519 let n = Rpo256::merge(&[k, l]);
520
521 let root = Rpo256::merge(&[m, n]);
522
523 let mtree = MerkleTree::new(vec![a, b, c, d, e, f, g, h]).unwrap();
524 let store = MerkleStore::from(&mtree);
525 let path = store.get_path(root, NodeIndex::make(3, 1)).unwrap().path;
526
527 let expected = MerklePath::new([a.into(), j, n].to_vec());
528 assert_eq!(path, expected);
529}
530
531#[test]
532fn test_set_node() -> Result<(), MerkleError> {
533 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
534 let mut store = MerkleStore::from(&mtree);
535 let value = int_to_node(42);
536 let index = NodeIndex::make(mtree.depth(), 0);
537 let new_root = store.set_node(mtree.root(), index, value)?.root;
538 assert_eq!(store.get_node(new_root, index), Ok(value), "Value must have changed");
539
540 Ok(())
541}
542
543#[test]
544fn test_constructors() -> Result<(), MerkleError> {
545 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
546 let store = MerkleStore::from(&mtree);
547
548 let depth = mtree.depth();
549 let leaves = 2u64.pow(depth.into());
550 for index in 0..leaves {
551 let index = NodeIndex::make(depth, index);
552 let value_path = store.get_path(mtree.root(), index)?;
553 assert_eq!(mtree.get_path(index)?, value_path.path);
554 }
555
556 let depth = 32;
557 let smt = SimpleSmt::with_leaves(
558 depth,
559 KEYS4.into_iter().zip(digests_to_words(&VALUES4).into_iter()),
560 )
561 .unwrap();
562 let store = MerkleStore::from(&smt);
563 let depth = smt.depth();
564
565 for key in KEYS4 {
566 let index = NodeIndex::make(depth, key);
567 let value_path = store.get_path(smt.root(), index)?;
568 assert_eq!(smt.get_path(index)?, value_path.path);
569 }
570
571 let d = 2;
572 let paths = [
573 (0, VALUES4[0], mtree.get_path(NodeIndex::make(d, 0)).unwrap()),
574 (1, VALUES4[1], mtree.get_path(NodeIndex::make(d, 1)).unwrap()),
575 (2, VALUES4[2], mtree.get_path(NodeIndex::make(d, 2)).unwrap()),
576 (3, VALUES4[3], mtree.get_path(NodeIndex::make(d, 3)).unwrap()),
577 ];
578
579 let mut store1 = MerkleStore::default();
580 store1.add_merkle_paths(paths.clone())?;
581
582 let mut store2 = MerkleStore::default();
583 store2.add_merkle_path(0, VALUES4[0], mtree.get_path(NodeIndex::make(d, 0))?)?;
584 store2.add_merkle_path(1, VALUES4[1], mtree.get_path(NodeIndex::make(d, 1))?)?;
585 store2.add_merkle_path(2, VALUES4[2], mtree.get_path(NodeIndex::make(d, 2))?)?;
586 store2.add_merkle_path(3, VALUES4[3], mtree.get_path(NodeIndex::make(d, 3))?)?;
587 let pmt = PartialMerkleTree::with_paths(paths).unwrap();
588
589 for key in [0, 1, 2, 3] {
590 let index = NodeIndex::make(d, key);
591 let value_path1 = store1.get_path(pmt.root(), index)?;
592 let value_path2 = store2.get_path(pmt.root(), index)?;
593 assert_eq!(value_path1, value_path2);
594
595 let index = NodeIndex::make(d, key);
596 assert_eq!(pmt.get_path(index)?, value_path1.path);
597 }
598
599 Ok(())
600}
601
602#[test]
603fn node_path_should_be_truncated_by_midtier_insert() {
604 let key = 0b11010010_11001100_11001100_11001100_11001100_11001100_11001100_11001100_u64;
605
606 let mut store = MerkleStore::new();
607 let root: RpoDigest = EmptySubtreeRoots::empty_hashes(64)[0];
608
609 // insert first node - works as expected
610 let depth = 64;
611 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
612 let index = NodeIndex::new(depth, key).unwrap();
613 let root = store.set_node(root, index, node).unwrap().root;
614 let result = store.get_node(root, index).unwrap();
615 let path = store.get_path(root, index).unwrap().path;
616 assert_eq!(node, result);
617 assert_eq!(path.depth(), depth);
618 assert!(path.verify(index.value(), result, &root));
619
620 // flip the first bit of the key and insert the second node on a different depth
621 let key = key ^ (1 << 63);
622 let key = key >> 8;
623 let depth = 56;
624 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
625 let index = NodeIndex::new(depth, key).unwrap();
626 let root = store.set_node(root, index, node).unwrap().root;
627 let result = store.get_node(root, index).unwrap();
628 let path = store.get_path(root, index).unwrap().path;
629 assert_eq!(node, result);
630 assert_eq!(path.depth(), depth);
631 assert!(path.verify(index.value(), result, &root));
632
633 // attempt to fetch a path of the second node to depth 64
634 // should fail because the previously inserted node will remove its sub-tree from the set
635 let key = key << 8;
636 let index = NodeIndex::new(64, key).unwrap();
637 assert!(store.get_node(root, index).is_err());
638}
639
640// LEAF TRAVERSAL
641// ================================================================================================
642
643#[test]
644fn get_leaf_depth_works_depth_64() {
645 let mut store = MerkleStore::new();
646 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(64)[0];
647 let key = u64::MAX;
648
649 // this will create a rainbow tree and test all opening to depth 64
650 for d in 0..64 {
651 let k = key & (u64::MAX >> d);
652 let node = RpoDigest::from([Felt::new(k); WORD_SIZE]);
653 let index = NodeIndex::new(64, k).unwrap();
654
655 // assert the leaf doesn't exist before the insert. the returned depth should always
656 // increment with the paths count of the set, as they are insersecting one another up to
657 // the first bits of the used key.
658 assert_eq!(d, store.get_leaf_depth(root, 64, k).unwrap());
659
660 // insert and assert the correct depth
661 root = store.set_node(root, index, node).unwrap().root;
662 assert_eq!(64, store.get_leaf_depth(root, 64, k).unwrap());
663 }
664}
665
666#[test]
667fn get_leaf_depth_works_with_incremental_depth() {
668 let mut store = MerkleStore::new();
669 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(64)[0];
670
671 // insert some path to the left of the root and assert it
672 let key = 0b01001011_10110110_00001101_01110100_00111011_10101101_00000100_01000001_u64;
673 assert_eq!(0, store.get_leaf_depth(root, 64, key).unwrap());
674 let depth = 64;
675 let index = NodeIndex::new(depth, key).unwrap();
676 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
677 root = store.set_node(root, index, node).unwrap().root;
678 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
679
680 // flip the key to the right of the root and insert some content on depth 16
681 let key = 0b11001011_10110110_00000000_00000000_00000000_00000000_00000000_00000000_u64;
682 assert_eq!(1, store.get_leaf_depth(root, 64, key).unwrap());
683 let depth = 16;
684 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
685 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
686 root = store.set_node(root, index, node).unwrap().root;
687 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
688
689 // attempt the sibling of the previous leaf
690 let key = 0b11001011_10110111_00000000_00000000_00000000_00000000_00000000_00000000_u64;
691 assert_eq!(16, store.get_leaf_depth(root, 64, key).unwrap());
692 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
693 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
694 root = store.set_node(root, index, node).unwrap().root;
695 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
696
697 // move down to the next depth and assert correct behavior
698 let key = 0b11001011_10110100_00000000_00000000_00000000_00000000_00000000_00000000_u64;
699 assert_eq!(15, store.get_leaf_depth(root, 64, key).unwrap());
700 let depth = 17;
701 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
702 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
703 root = store.set_node(root, index, node).unwrap().root;
704 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
705}
706
707#[test]
708fn get_leaf_depth_works_with_depth_8() {
709 let mut store = MerkleStore::new();
710 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(8)[0];
711
712 // insert some random, 8 depth keys. `a` diverges from the first bit
713 let a = 0b01101001_u64;
714 let b = 0b10011001_u64;
715 let c = 0b10010110_u64;
716 let d = 0b11110110_u64;
717
718 for k in [a, b, c, d] {
719 let index = NodeIndex::new(8, k).unwrap();
720 let node = RpoDigest::from([Felt::new(k); WORD_SIZE]);
721 root = store.set_node(root, index, node).unwrap().root;
722 }
723
724 // assert all leaves returns the inserted depth
725 for k in [a, b, c, d] {
726 assert_eq!(8, store.get_leaf_depth(root, 8, k).unwrap());
727 }
728
729 // flip last bit of a and expect it to return the the same depth, but for an empty node
730 assert_eq!(8, store.get_leaf_depth(root, 8, 0b01101000_u64).unwrap());
731
732 // flip fourth bit of a and expect an empty node on depth 4
733 assert_eq!(4, store.get_leaf_depth(root, 8, 0b01111001_u64).unwrap());
734
735 // flip third bit of a and expect an empty node on depth 3
736 assert_eq!(3, store.get_leaf_depth(root, 8, 0b01001001_u64).unwrap());
737
738 // flip second bit of a and expect an empty node on depth 2
739 assert_eq!(2, store.get_leaf_depth(root, 8, 0b00101001_u64).unwrap());
740
741 // flip fourth bit of c and expect an empty node on depth 4
742 assert_eq!(4, store.get_leaf_depth(root, 8, 0b10000110_u64).unwrap());
743
744 // flip second bit of d and expect an empty node on depth 3 as depth 2 conflicts with b and c
745 assert_eq!(3, store.get_leaf_depth(root, 8, 0b10110110_u64).unwrap());
746
747 // duplicate the tree on `a` and assert the depth is short-circuited by such sub-tree
748 let index = NodeIndex::new(8, a).unwrap();
749 root = store.set_node(root, index, root).unwrap().root;
750 assert_eq!(Err(MerkleError::DepthTooBig(9)), store.get_leaf_depth(root, 8, a));
751}
752
753#[test]
754fn find_lone_leaf() {
755 let mut store = MerkleStore::new();
756 let empty = EmptySubtreeRoots::empty_hashes(64);
757 let mut root: RpoDigest = empty[0];
758
759 // insert a single leaf into the store at depth 64
760 let key_a = 0b01010101_10101010_00001111_01110100_00111011_10101101_00000100_01000001_u64;
761 let idx_a = NodeIndex::make(64, key_a);
762 let val_a = RpoDigest::from([ONE, ONE, ONE, ONE]);
763 root = store.set_node(root, idx_a, val_a).unwrap().root;
764
765 // for every ancestor of A, A should be a long leaf
766 for depth in 1..64 {
767 let parent_index = NodeIndex::make(depth, key_a >> (64 - depth));
768 let parent = store.get_node(root, parent_index).unwrap();
769
770 let res = store.find_lone_leaf(parent, parent_index, 64).unwrap();
771 assert_eq!(res, Some((idx_a, val_a)));
772 }
773
774 // insert another leaf into the store such that it has the same 8 bit prefix as A
775 let key_b = 0b01010101_01111010_00001111_01110100_00111011_10101101_00000100_01000001_u64;
776 let idx_b = NodeIndex::make(64, key_b);
777 let val_b = RpoDigest::from([ONE, ONE, ONE, ZERO]);
778 root = store.set_node(root, idx_b, val_b).unwrap().root;
779
780 // for any node which is common between A and B, find_lone_leaf() should return None as the
781 // node has two descendants
782 for depth in 1..9 {
783 let parent_index = NodeIndex::make(depth, key_a >> (64 - depth));
784 let parent = store.get_node(root, parent_index).unwrap();
785
786 let res = store.find_lone_leaf(parent, parent_index, 64).unwrap();
787 assert_eq!(res, None);
788 }
789
790 // for other ancestors of A and B, A and B should be lone leaves respectively
791 for depth in 9..64 {
792 let parent_index = NodeIndex::make(depth, key_a >> (64 - depth));
793 let parent = store.get_node(root, parent_index).unwrap();
794
795 let res = store.find_lone_leaf(parent, parent_index, 64).unwrap();
796 assert_eq!(res, Some((idx_a, val_a)));
797 }
798
799 for depth in 9..64 {
800 let parent_index = NodeIndex::make(depth, key_b >> (64 - depth));
801 let parent = store.get_node(root, parent_index).unwrap();
802
803 let res = store.find_lone_leaf(parent, parent_index, 64).unwrap();
804 assert_eq!(res, Some((idx_b, val_b)));
805 }
806
807 // for any other node, find_lone_leaf() should return None as they have no leaf nodes
808 let parent_index = NodeIndex::make(16, 0b01010101_11111111);
809 let parent = store.get_node(root, parent_index).unwrap();
810 let res = store.find_lone_leaf(parent, parent_index, 64).unwrap();
811 assert_eq!(res, None);
812}
813
814// SUBSET EXTRACTION
815// ================================================================================================
816
817#[test]
818fn mstore_subset() {
819 // add a Merkle tree of depth 3 to the store
820 let mtree = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
821 let mut store = MerkleStore::default();
822 let empty_store_num_nodes = store.nodes.len();
823 store.extend(mtree.inner_nodes());
824
825 // build 3 subtrees contained within the above Merkle tree; note that subtree2 is a subset
826 // of subtree1
827 let subtree1 = MerkleTree::new(digests_to_words(&VALUES8[..4])).unwrap();
828 let subtree2 = MerkleTree::new(digests_to_words(&VALUES8[2..4])).unwrap();
829 let subtree3 = MerkleTree::new(digests_to_words(&VALUES8[6..])).unwrap();
830
831 // --- extract all 3 subtrees ---------------------------------------------
832
833 let substore = store.subset([subtree1.root(), subtree2.root(), subtree3.root()].iter());
834
835 // number of nodes should increase by 4: 3 nodes form subtree1 and 1 node from subtree3
836 assert_eq!(substore.nodes.len(), empty_store_num_nodes + 4);
837
838 // make sure paths that all subtrees are in the store
839 check_mstore_subtree(&substore, &subtree1);
840 check_mstore_subtree(&substore, &subtree2);
841 check_mstore_subtree(&substore, &subtree3);
842
843 // --- extract subtrees 1 and 3 -------------------------------------------
844 // this should give the same result as above as subtree2 is nested withing subtree1
845
846 let substore = store.subset([subtree1.root(), subtree3.root()].iter());
847
848 // number of nodes should increase by 4: 3 nodes form subtree1 and 1 node from subtree3
849 assert_eq!(substore.nodes.len(), empty_store_num_nodes + 4);
850
851 // make sure paths that all subtrees are in the store
852 check_mstore_subtree(&substore, &subtree1);
853 check_mstore_subtree(&substore, &subtree2);
854 check_mstore_subtree(&substore, &subtree3);
855}
856
857fn check_mstore_subtree(store: &MerkleStore, subtree: &MerkleTree) {
858 for (i, value) in subtree.leaves() {
859 let index = NodeIndex::new(subtree.depth(), i).unwrap();
860 let path1 = store.get_path(subtree.root(), index).unwrap();
861 assert_eq!(*path1.value, *value);
862
863 let path2 = subtree.get_path(index).unwrap();
864 assert_eq!(path1.path, path2);
865 }
866}
867
868// SERIALIZATION
869// ================================================================================================
870
871#[cfg(feature = "std")]
872#[test]
873fn test_serialization() -> Result<(), Box<dyn Error>> {
874 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
875 let store = MerkleStore::from(&mtree);
876 let decoded = MerkleStore::read_from_bytes(&store.to_bytes()).expect("deserialization failed");
877 assert_eq!(store, decoded);
878 Ok(())
879}
880
881// MERKLE RECORDER
882// ================================================================================================
883#[test]
884fn test_recorder() {
885 // instantiate recorder from MerkleTree and SimpleSmt
886 let mtree = MerkleTree::new(digests_to_words(&VALUES4)).unwrap();
887 let smtree = SimpleSmt::with_leaves(
888 64,
889 KEYS8.into_iter().zip(VALUES8.into_iter().map(|x| x.into()).rev()),
890 )
891 .unwrap();
892
893 let mut recorder: RecordingMerkleStore =
894 mtree.inner_nodes().chain(smtree.inner_nodes()).collect();
895
896 // get nodes from both trees and make sure they are correct
897 let index_0 = NodeIndex::new(mtree.depth(), 0).unwrap();
898 let node = recorder.get_node(mtree.root(), index_0).unwrap();
899 assert_eq!(node, mtree.get_node(index_0).unwrap());
900
901 let index_1 = NodeIndex::new(smtree.depth(), 1).unwrap();
902 let node = recorder.get_node(smtree.root(), index_1).unwrap();
903 assert_eq!(node, smtree.get_node(index_1).unwrap());
904
905 // insert a value and assert that when we request it next time it is accurate
906 let new_value = [ZERO, ZERO, ONE, ONE].into();
907 let index_2 = NodeIndex::new(smtree.depth(), 2).unwrap();
908 let root = recorder.set_node(smtree.root(), index_2, new_value).unwrap().root;
909 assert_eq!(recorder.get_node(root, index_2).unwrap(), new_value);
910
911 // construct the proof
912 let rec_map = recorder.into_inner();
913 let (_, proof) = rec_map.finalize();
914 let merkle_store: MerkleStore = proof.into();
915
916 // make sure the proof contains all nodes from both trees
917 let node = merkle_store.get_node(mtree.root(), index_0).unwrap();
918 assert_eq!(node, mtree.get_node(index_0).unwrap());
919
920 let node = merkle_store.get_node(smtree.root(), index_1).unwrap();
921 assert_eq!(node, smtree.get_node(index_1).unwrap());
922
923 let node = merkle_store.get_node(smtree.root(), index_2).unwrap();
924 assert_eq!(node, smtree.get_leaf(index_2.value()).unwrap().into());
925
926 // assert that is doesnt contain nodes that were not recorded
927 let not_recorded_index = NodeIndex::new(smtree.depth(), 4).unwrap();
928 assert!(merkle_store.get_node(smtree.root(), not_recorded_index).is_err());
929 assert!(smtree.get_node(not_recorded_index).is_ok());
930}