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