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#[test]
641fn get_leaf_depth_works_depth_64() {
642 let mut store = MerkleStore::new();
643 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(64)[0];
644 let key = u64::MAX;
645
646 // this will create a rainbow tree and test all opening to depth 64
647 for d in 0..64 {
648 let k = key & (u64::MAX >> d);
649 let node = RpoDigest::from([Felt::new(k); WORD_SIZE]);
650 let index = NodeIndex::new(64, k).unwrap();
651
652 // assert the leaf doesn't exist before the insert. the returned depth should always
653 // increment with the paths count of the set, as they are insersecting one another up to
654 // the first bits of the used key.
655 assert_eq!(d, store.get_leaf_depth(root, 64, k).unwrap());
656
657 // insert and assert the correct depth
658 root = store.set_node(root, index, node).unwrap().root;
659 assert_eq!(64, store.get_leaf_depth(root, 64, k).unwrap());
660 }
661}
662
663#[test]
664fn get_leaf_depth_works_with_incremental_depth() {
665 let mut store = MerkleStore::new();
666 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(64)[0];
667
668 // insert some path to the left of the root and assert it
669 let key = 0b01001011_10110110_00001101_01110100_00111011_10101101_00000100_01000001_u64;
670 assert_eq!(0, store.get_leaf_depth(root, 64, key).unwrap());
671 let depth = 64;
672 let index = NodeIndex::new(depth, key).unwrap();
673 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
674 root = store.set_node(root, index, node).unwrap().root;
675 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
676
677 // flip the key to the right of the root and insert some content on depth 16
678 let key = 0b11001011_10110110_00000000_00000000_00000000_00000000_00000000_00000000_u64;
679 assert_eq!(1, store.get_leaf_depth(root, 64, key).unwrap());
680 let depth = 16;
681 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
682 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
683 root = store.set_node(root, index, node).unwrap().root;
684 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
685
686 // attempt the sibling of the previous leaf
687 let key = 0b11001011_10110111_00000000_00000000_00000000_00000000_00000000_00000000_u64;
688 assert_eq!(16, store.get_leaf_depth(root, 64, key).unwrap());
689 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
690 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
691 root = store.set_node(root, index, node).unwrap().root;
692 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
693
694 // move down to the next depth and assert correct behavior
695 let key = 0b11001011_10110100_00000000_00000000_00000000_00000000_00000000_00000000_u64;
696 assert_eq!(15, store.get_leaf_depth(root, 64, key).unwrap());
697 let depth = 17;
698 let index = NodeIndex::new(depth, key >> (64 - depth)).unwrap();
699 let node = RpoDigest::from([Felt::new(key); WORD_SIZE]);
700 root = store.set_node(root, index, node).unwrap().root;
701 assert_eq!(depth, store.get_leaf_depth(root, 64, key).unwrap());
702}
703
704#[test]
705fn get_leaf_depth_works_with_depth_8() {
706 let mut store = MerkleStore::new();
707 let mut root: RpoDigest = EmptySubtreeRoots::empty_hashes(8)[0];
708
709 // insert some random, 8 depth keys. `a` diverges from the first bit
710 let a = 0b01101001_u64;
711 let b = 0b10011001_u64;
712 let c = 0b10010110_u64;
713 let d = 0b11110110_u64;
714
715 for k in [a, b, c, d] {
716 let index = NodeIndex::new(8, k).unwrap();
717 let node = RpoDigest::from([Felt::new(k); WORD_SIZE]);
718 root = store.set_node(root, index, node).unwrap().root;
719 }
720
721 // assert all leaves returns the inserted depth
722 for k in [a, b, c, d] {
723 assert_eq!(8, store.get_leaf_depth(root, 8, k).unwrap());
724 }
725
726 // flip last bit of a and expect it to return the the same depth, but for an empty node
727 assert_eq!(8, store.get_leaf_depth(root, 8, 0b01101000_u64).unwrap());
728
729 // flip fourth bit of a and expect an empty node on depth 4
730 assert_eq!(4, store.get_leaf_depth(root, 8, 0b01111001_u64).unwrap());
731
732 // flip third bit of a and expect an empty node on depth 3
733 assert_eq!(3, store.get_leaf_depth(root, 8, 0b01001001_u64).unwrap());
734
735 // flip second bit of a and expect an empty node on depth 2
736 assert_eq!(2, store.get_leaf_depth(root, 8, 0b00101001_u64).unwrap());
737
738 // flip fourth bit of c and expect an empty node on depth 4
739 assert_eq!(4, store.get_leaf_depth(root, 8, 0b10000110_u64).unwrap());
740
741 // flip second bit of d and expect an empty node on depth 3 as depth 2 conflicts with b and c
742 assert_eq!(3, store.get_leaf_depth(root, 8, 0b10110110_u64).unwrap());
743
744 // duplicate the tree on `a` and assert the depth is short-circuited by such sub-tree
745 let index = NodeIndex::new(8, a).unwrap();
746 root = store.set_node(root, index, root).unwrap().root;
747 assert_eq!(Err(MerkleError::DepthTooBig(9)), store.get_leaf_depth(root, 8, a));
748}
749
750// SUBSET EXTRACTION
751// ================================================================================================
752
753#[test]
754fn mstore_subset() {
755 // add a Merkle tree of depth 3 to the store
756 let mtree = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
757 let mut store = MerkleStore::default();
758 let empty_store_num_nodes = store.nodes.len();
759 store.extend(mtree.inner_nodes());
760
761 // build 3 subtrees contained within the above Merkle tree; note that subtree2 is a subset
762 // of subtree1
763 let subtree1 = MerkleTree::new(digests_to_words(&VALUES8[..4])).unwrap();
764 let subtree2 = MerkleTree::new(digests_to_words(&VALUES8[2..4])).unwrap();
765 let subtree3 = MerkleTree::new(digests_to_words(&VALUES8[6..])).unwrap();
766
767 // --- extract all 3 subtrees ---------------------------------------------
768
769 let substore = store.subset([subtree1.root(), subtree2.root(), subtree3.root()].iter());
770
771 // number of nodes should increase by 4: 3 nodes form subtree1 and 1 node from subtree3
772 assert_eq!(substore.nodes.len(), empty_store_num_nodes + 4);
773
774 // make sure paths that all subtrees are in the store
775 check_mstore_subtree(&substore, &subtree1);
776 check_mstore_subtree(&substore, &subtree2);
777 check_mstore_subtree(&substore, &subtree3);
778
779 // --- extract subtrees 1 and 3 -------------------------------------------
780 // this should give the same result as above as subtree2 is nested withing subtree1
781
782 let substore = store.subset([subtree1.root(), subtree3.root()].iter());
783
784 // number of nodes should increase by 4: 3 nodes form subtree1 and 1 node from subtree3
785 assert_eq!(substore.nodes.len(), empty_store_num_nodes + 4);
786
787 // make sure paths that all subtrees are in the store
788 check_mstore_subtree(&substore, &subtree1);
789 check_mstore_subtree(&substore, &subtree2);
790 check_mstore_subtree(&substore, &subtree3);
791}
792
793fn check_mstore_subtree(store: &MerkleStore, subtree: &MerkleTree) {
794 for (i, value) in subtree.leaves() {
795 let index = NodeIndex::new(subtree.depth(), i).unwrap();
796 let path1 = store.get_path(subtree.root(), index).unwrap();
797 assert_eq!(*path1.value, *value);
798
799 let path2 = subtree.get_path(index).unwrap();
800 assert_eq!(path1.path, path2);
801 }
802}
803
804// SERIALIZATION
805// ================================================================================================
806
807#[cfg(feature = "std")]
808#[test]
809fn test_serialization() -> Result<(), Box<dyn Error>> {
810 let mtree = MerkleTree::new(digests_to_words(&VALUES4))?;
811 let store = MerkleStore::from(&mtree);
812 let decoded = MerkleStore::read_from_bytes(&store.to_bytes()).expect("deserialization failed");
813 assert_eq!(store, decoded);
814 Ok(())
815}
816
817// MERKLE RECORDER
818// ================================================================================================
819#[test]
820fn test_recorder() {
821 // instantiate recorder from MerkleTree and SimpleSmt
822 let mtree = MerkleTree::new(digests_to_words(&VALUES4)).unwrap();
823 let smtree = SimpleSmt::with_leaves(
824 64,
825 KEYS8.into_iter().zip(VALUES8.into_iter().map(|x| x.into()).rev()),
826 )
827 .unwrap();
828
829 let mut recorder: RecordingMerkleStore =
830 mtree.inner_nodes().chain(smtree.inner_nodes()).collect();
831
832 // get nodes from both trees and make sure they are correct
833 let index_0 = NodeIndex::new(mtree.depth(), 0).unwrap();
834 let node = recorder.get_node(mtree.root(), index_0).unwrap();
835 assert_eq!(node, mtree.get_node(index_0).unwrap());
836
837 let index_1 = NodeIndex::new(smtree.depth(), 1).unwrap();
838 let node = recorder.get_node(smtree.root(), index_1).unwrap();
839 assert_eq!(node, smtree.get_node(index_1).unwrap());
840
841 // insert a value and assert that when we request it next time it is accurate
842 let new_value = [ZERO, ZERO, ONE, ONE].into();
843 let index_2 = NodeIndex::new(smtree.depth(), 2).unwrap();
844 let root = recorder.set_node(smtree.root(), index_2, new_value).unwrap().root;
845 assert_eq!(recorder.get_node(root, index_2).unwrap(), new_value);
846
847 // construct the proof
848 let rec_map = recorder.into_inner();
849 let (_, proof) = rec_map.finalize();
850 let merkle_store: MerkleStore = proof.into();
851
852 // make sure the proof contains all nodes from both trees
853 let node = merkle_store.get_node(mtree.root(), index_0).unwrap();
854 assert_eq!(node, mtree.get_node(index_0).unwrap());
855
856 let node = merkle_store.get_node(smtree.root(), index_1).unwrap();
857 assert_eq!(node, smtree.get_node(index_1).unwrap());
858
859 let node = merkle_store.get_node(smtree.root(), index_2).unwrap();
860 assert_eq!(node, smtree.get_leaf(index_2.value()).unwrap().into());
861
862 // assert that is doesnt contain nodes that were not recorded
863 let not_recorded_index = NodeIndex::new(smtree.depth(), 4).unwrap();
864 assert!(merkle_store.get_node(smtree.root(), not_recorded_index).is_err());
865 assert!(smtree.get_node(not_recorded_index).is_ok());
866}