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