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