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,
6};
7
8#[cfg(std)]
9use std::error::Error;
10
11const KEYS4: [u64; 4] = [0, 1, 2, 3];
12const LEAVES4: [Word; 4] = [
13 int_to_node(1),
14 int_to_node(2),
15 int_to_node(3),
16 int_to_node(4),
17];
18
19#[test]
20fn test_root_not_in_store() -> Result<(), MerkleError> {
21 let mtree = MerkleTree::new(LEAVES4.to_vec())?;
22 let store = MerkleStore::default().with_merkle_tree(LEAVES4)?;
23 assert_eq!(
24 store.get_node(LEAVES4[0], NodeIndex::new(mtree.depth(), 0)),
25 Err(MerkleError::RootNotInStore(LEAVES4[0])),
26 "Leaf 0 is not a root"
27 );
28 assert_eq!(
29 store.get_path(LEAVES4[0], NodeIndex::new(mtree.depth(), 0)),
30 Err(MerkleError::RootNotInStore(LEAVES4[0])),
31 "Leaf 0 is not a root"
32 );
33
34 Ok(())
35}
36
37#[test]
38fn test_merkle_tree() -> Result<(), MerkleError> {
39 let mut store = MerkleStore::default();
40
41 let mtree = MerkleTree::new(LEAVES4.to_vec())?;
42 store.add_merkle_tree(LEAVES4.to_vec())?;
43
44 // STORE LEAVES ARE CORRECT ==============================================================
45 // checks the leaves in the store corresponds to the expected values
46 assert_eq!(
47 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 0)),
48 Ok(LEAVES4[0]),
49 "node 0 must be in the tree"
50 );
51 assert_eq!(
52 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 1)),
53 Ok(LEAVES4[1]),
54 "node 1 must be in the tree"
55 );
56 assert_eq!(
57 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 2)),
58 Ok(LEAVES4[2]),
59 "node 2 must be in the tree"
60 );
61 assert_eq!(
62 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 3)),
63 Ok(LEAVES4[3]),
64 "node 3 must be in the tree"
65 );
66
67 // STORE LEAVES MATCH TREE ===============================================================
68 // sanity check the values returned by the store and the tree
69 assert_eq!(
70 mtree.get_node(NodeIndex::new(mtree.depth(), 0)),
71 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 0)),
72 "node 0 must be the same for both MerkleTree and MerkleStore"
73 );
74 assert_eq!(
75 mtree.get_node(NodeIndex::new(mtree.depth(), 1)),
76 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 1)),
77 "node 1 must be the same for both MerkleTree and MerkleStore"
78 );
79 assert_eq!(
80 mtree.get_node(NodeIndex::new(mtree.depth(), 2)),
81 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 2)),
82 "node 2 must be the same for both MerkleTree and MerkleStore"
83 );
84 assert_eq!(
85 mtree.get_node(NodeIndex::new(mtree.depth(), 3)),
86 store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 3)),
87 "node 3 must be the same for both MerkleTree and MerkleStore"
88 );
89
90 // STORE MERKLE PATH MATCHS ==============================================================
91 // assert the merkle path returned by the store is the same as the one in the tree
92 let result = store
93 .get_path(mtree.root(), NodeIndex::new(mtree.depth(), 0))
94 .unwrap();
95 assert_eq!(
96 LEAVES4[0], result.value,
97 "Value for merkle path at index 0 must match leaf value"
98 );
99 assert_eq!(
100 mtree.get_path(NodeIndex::new(mtree.depth(), 0)),
101 Ok(result.path),
102 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
103 );
104
105 let result = store
106 .get_path(mtree.root(), NodeIndex::new(mtree.depth(), 1))
107 .unwrap();
108 assert_eq!(
109 LEAVES4[1], result.value,
110 "Value for merkle path at index 0 must match leaf value"
111 );
112 assert_eq!(
113 mtree.get_path(NodeIndex::new(mtree.depth(), 1)),
114 Ok(result.path),
115 "merkle path for index 1 must be the same for the MerkleTree and MerkleStore"
116 );
117
118 let result = store
119 .get_path(mtree.root(), NodeIndex::new(mtree.depth(), 2))
120 .unwrap();
121 assert_eq!(
122 LEAVES4[2], result.value,
123 "Value for merkle path at index 0 must match leaf value"
124 );
125 assert_eq!(
126 mtree.get_path(NodeIndex::new(mtree.depth(), 2)),
127 Ok(result.path),
128 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
129 );
130
131 let result = store
132 .get_path(mtree.root(), NodeIndex::new(mtree.depth(), 3))
133 .unwrap();
134 assert_eq!(
135 LEAVES4[3], result.value,
136 "Value for merkle path at index 0 must match leaf value"
137 );
138 assert_eq!(
139 mtree.get_path(NodeIndex::new(mtree.depth(), 3)),
140 Ok(result.path),
141 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
142 );
143
144 Ok(())
145}
146
147#[test]
148fn test_get_invalid_node() {
149 let mut store = MerkleStore::default();
150 let mtree = MerkleTree::new(LEAVES4.to_vec()).expect("creating a merkle tree must work");
151 store
152 .add_merkle_tree(LEAVES4.to_vec())
153 .expect("adding a merkle tree to the store must work");
154 let _ = store.get_node(mtree.root(), NodeIndex::new(mtree.depth(), 3));
155}
156
157#[test]
158fn test_add_sparse_merkle_tree_one_level() -> Result<(), MerkleError> {
159 let mut store = MerkleStore::default();
160 let keys2: [u64; 2] = [0, 1];
161 let leaves2: [Word; 2] = [int_to_node(1), int_to_node(2)];
162 store.add_sparse_merkle_tree(keys2.into_iter().zip(leaves2.into_iter()))?;
163 let smt = SimpleSmt::new(1)
164 .unwrap()
165 .with_leaves(keys2.into_iter().zip(leaves2.into_iter()))
166 .unwrap();
167
168 let idx = NodeIndex::new(1, 0);
169 assert_eq!(smt.get_node(&idx).unwrap(), leaves2[0]);
170 assert_eq!(
171 store.get_node(smt.root(), idx).unwrap(),
172 smt.get_node(&idx).unwrap()
173 );
174
175 let idx = NodeIndex::new(1, 1);
176 assert_eq!(smt.get_node(&idx).unwrap(), leaves2[1]);
177 assert_eq!(
178 store.get_node(smt.root(), idx).unwrap(),
179 smt.get_node(&idx).unwrap()
180 );
181
182 Ok(())
183}
184
185#[test]
186fn test_sparse_merkle_tree() -> Result<(), MerkleError> {
187 let mut store = MerkleStore::default();
188 store.add_sparse_merkle_tree(KEYS4.into_iter().zip(LEAVES4.into_iter()))?;
189
190 let smt = SimpleSmt::new(SimpleSmt::MAX_DEPTH)
191 .unwrap()
192 .with_leaves(KEYS4.into_iter().zip(LEAVES4.into_iter()))
193 .unwrap();
194
195 // STORE LEAVES ARE CORRECT ==============================================================
196 // checks the leaves in the store corresponds to the expected values
197 assert_eq!(
198 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 0)),
199 Ok(LEAVES4[0]),
200 "node 0 must be in the tree"
201 );
202 assert_eq!(
203 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 1)),
204 Ok(LEAVES4[1]),
205 "node 1 must be in the tree"
206 );
207 assert_eq!(
208 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 2)),
209 Ok(LEAVES4[2]),
210 "node 2 must be in the tree"
211 );
212 assert_eq!(
213 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 3)),
214 Ok(LEAVES4[3]),
215 "node 3 must be in the tree"
216 );
217
218 // STORE LEAVES MATCH TREE ===============================================================
219 // sanity check the values returned by the store and the tree
220 assert_eq!(
221 smt.get_node(&NodeIndex::new(smt.depth(), 0)),
222 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 0)),
223 "node 0 must be the same for both SparseMerkleTree and MerkleStore"
224 );
225 assert_eq!(
226 smt.get_node(&NodeIndex::new(smt.depth(), 1)),
227 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 1)),
228 "node 1 must be the same for both SparseMerkleTree and MerkleStore"
229 );
230 assert_eq!(
231 smt.get_node(&NodeIndex::new(smt.depth(), 2)),
232 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 2)),
233 "node 2 must be the same for both SparseMerkleTree and MerkleStore"
234 );
235 assert_eq!(
236 smt.get_node(&NodeIndex::new(smt.depth(), 3)),
237 store.get_node(smt.root(), NodeIndex::new(smt.depth(), 3)),
238 "node 3 must be the same for both SparseMerkleTree and MerkleStore"
239 );
240
241 // STORE MERKLE PATH MATCHS ==============================================================
242 // assert the merkle path returned by the store is the same as the one in the tree
243 let result = store
244 .get_path(smt.root(), NodeIndex::new(smt.depth(), 0))
245 .unwrap();
246 assert_eq!(
247 LEAVES4[0], result.value,
248 "Value for merkle path at index 0 must match leaf value"
249 );
250 assert_eq!(
251 smt.get_path(NodeIndex::new(smt.depth(), 0)),
252 Ok(result.path),
253 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
254 );
255
256 let result = store
257 .get_path(smt.root(), NodeIndex::new(smt.depth(), 1))
258 .unwrap();
259 assert_eq!(
260 LEAVES4[1], result.value,
261 "Value for merkle path at index 0 must match leaf value"
262 );
263 assert_eq!(
264 smt.get_path(NodeIndex::new(smt.depth(), 1)),
265 Ok(result.path),
266 "merkle path for index 1 must be the same for the MerkleTree and MerkleStore"
267 );
268
269 let result = store
270 .get_path(smt.root(), NodeIndex::new(smt.depth(), 2))
271 .unwrap();
272 assert_eq!(
273 LEAVES4[2], result.value,
274 "Value for merkle path at index 0 must match leaf value"
275 );
276 assert_eq!(
277 smt.get_path(NodeIndex::new(smt.depth(), 2)),
278 Ok(result.path),
279 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
280 );
281
282 let result = store
283 .get_path(smt.root(), NodeIndex::new(smt.depth(), 3))
284 .unwrap();
285 assert_eq!(
286 LEAVES4[3], result.value,
287 "Value for merkle path at index 0 must match leaf value"
288 );
289 assert_eq!(
290 smt.get_path(NodeIndex::new(smt.depth(), 3)),
291 Ok(result.path),
292 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
293 );
294
295 Ok(())
296}
297
298#[test]
299fn test_add_merkle_paths() -> Result<(), MerkleError> {
300 let mtree = MerkleTree::new(LEAVES4.to_vec())?;
301
302 let i0 = 0;
303 let p0 = mtree.get_path(NodeIndex::new(2, i0)).unwrap();
304
305 let i1 = 1;
306 let p1 = mtree.get_path(NodeIndex::new(2, i1)).unwrap();
307
308 let i2 = 2;
309 let p2 = mtree.get_path(NodeIndex::new(2, i2)).unwrap();
310
311 let i3 = 3;
312 let p3 = mtree.get_path(NodeIndex::new(2, i3)).unwrap();
313
314 let paths = [
315 (i0, LEAVES4[i0 as usize], p0),
316 (i1, LEAVES4[i1 as usize], p1),
317 (i2, LEAVES4[i2 as usize], p2),
318 (i3, LEAVES4[i3 as usize], p3),
319 ];
320
321 let mut store = MerkleStore::default();
322 store
323 .add_merkle_paths(paths.clone())
324 .expect("the valid paths must work");
325
326 let depth = 2;
327 let set = MerklePathSet::new(depth).with_paths(paths).unwrap();
328
329 // STORE LEAVES ARE CORRECT ==============================================================
330 // checks the leaves in the store corresponds to the expected values
331 assert_eq!(
332 store.get_node(set.root(), NodeIndex::new(set.depth(), 0)),
333 Ok(LEAVES4[0]),
334 "node 0 must be in the set"
335 );
336 assert_eq!(
337 store.get_node(set.root(), NodeIndex::new(set.depth(), 1)),
338 Ok(LEAVES4[1]),
339 "node 1 must be in the set"
340 );
341 assert_eq!(
342 store.get_node(set.root(), NodeIndex::new(set.depth(), 2)),
343 Ok(LEAVES4[2]),
344 "node 2 must be in the set"
345 );
346 assert_eq!(
347 store.get_node(set.root(), NodeIndex::new(set.depth(), 3)),
348 Ok(LEAVES4[3]),
349 "node 3 must be in the set"
350 );
351
352 // STORE LEAVES MATCH SET ================================================================
353 // sanity check the values returned by the store and the set
354 assert_eq!(
355 set.get_node(NodeIndex::new(set.depth(), 0)),
356 store.get_node(set.root(), NodeIndex::new(set.depth(), 0)),
357 "node 0 must be the same for both SparseMerkleTree and MerkleStore"
358 );
359 assert_eq!(
360 set.get_node(NodeIndex::new(set.depth(), 1)),
361 store.get_node(set.root(), NodeIndex::new(set.depth(), 1)),
362 "node 1 must be the same for both SparseMerkleTree and MerkleStore"
363 );
364 assert_eq!(
365 set.get_node(NodeIndex::new(set.depth(), 2)),
366 store.get_node(set.root(), NodeIndex::new(set.depth(), 2)),
367 "node 2 must be the same for both SparseMerkleTree and MerkleStore"
368 );
369 assert_eq!(
370 set.get_node(NodeIndex::new(set.depth(), 3)),
371 store.get_node(set.root(), NodeIndex::new(set.depth(), 3)),
372 "node 3 must be the same for both SparseMerkleTree and MerkleStore"
373 );
374
375 // STORE MERKLE PATH MATCHS ==============================================================
376 // assert the merkle path returned by the store is the same as the one in the set
377 let result = store
378 .get_path(set.root(), NodeIndex::new(set.depth(), 0))
379 .unwrap();
380 assert_eq!(
381 LEAVES4[0], result.value,
382 "Value for merkle path at index 0 must match leaf value"
383 );
384 assert_eq!(
385 set.get_path(NodeIndex::new(set.depth(), 0)),
386 Ok(result.path),
387 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
388 );
389
390 let result = store
391 .get_path(set.root(), NodeIndex::new(set.depth(), 1))
392 .unwrap();
393 assert_eq!(
394 LEAVES4[1], result.value,
395 "Value for merkle path at index 0 must match leaf value"
396 );
397 assert_eq!(
398 set.get_path(NodeIndex::new(set.depth(), 1)),
399 Ok(result.path),
400 "merkle path for index 1 must be the same for the MerkleTree and MerkleStore"
401 );
402
403 let result = store
404 .get_path(set.root(), NodeIndex::new(set.depth(), 2))
405 .unwrap();
406 assert_eq!(
407 LEAVES4[2], result.value,
408 "Value for merkle path at index 0 must match leaf value"
409 );
410 assert_eq!(
411 set.get_path(NodeIndex::new(set.depth(), 2)),
412 Ok(result.path),
413 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
414 );
415
416 let result = store
417 .get_path(set.root(), NodeIndex::new(set.depth(), 3))
418 .unwrap();
419 assert_eq!(
420 LEAVES4[3], result.value,
421 "Value for merkle path at index 0 must match leaf value"
422 );
423 assert_eq!(
424 set.get_path(NodeIndex::new(set.depth(), 3)),
425 Ok(result.path),
426 "merkle path for index 0 must be the same for the MerkleTree and MerkleStore"
427 );
428
429 Ok(())
430}
431
432#[test]
433fn wont_open_to_different_depth_root() {
434 let empty = EmptySubtreeRoots::empty_hashes(64);
435 let a = [Felt::new(1); 4];
436 let b = [Felt::new(2); 4];
437
438 // Compute the root for a different depth. We cherry-pick this specific depth to prevent a
439 // regression to a bug in the past that allowed the user to fetch a node at a depth lower than
440 // the inserted path of a Merkle tree.
441 let mut root = Rpo256::merge(&[a.into(), b.into()]);
442 for depth in (1..=63).rev() {
443 root = Rpo256::merge(&[root, empty[depth]]);
444 }
445 let root = Word::from(root);
446
447 // For this example, the depth of the Merkle tree is 1, as we have only two leaves. Here we
448 // attempt to fetch a node on the maximum depth, and it should fail because the root shouldn't
449 // exist for the set.
450 let store = MerkleStore::default().with_merkle_tree([a, b]).unwrap();
451 let index = NodeIndex::root();
452 let err = store.get_node(root, index).err().unwrap();
453 assert_eq!(err, MerkleError::RootNotInStore(root));
454}
455
456#[test]
457fn store_path_opens_from_leaf() {
458 let a = [Felt::new(1); 4];
459 let b = [Felt::new(2); 4];
460 let c = [Felt::new(3); 4];
461 let d = [Felt::new(4); 4];
462 let e = [Felt::new(5); 4];
463 let f = [Felt::new(6); 4];
464 let g = [Felt::new(7); 4];
465 let h = [Felt::new(8); 4];
466
467 let i = Rpo256::merge(&[a.into(), b.into()]);
468 let j = Rpo256::merge(&[c.into(), d.into()]);
469 let k = Rpo256::merge(&[e.into(), f.into()]);
470 let l = Rpo256::merge(&[g.into(), h.into()]);
471
472 let m = Rpo256::merge(&[i.into(), j.into()]);
473 let n = Rpo256::merge(&[k.into(), l.into()]);
474
475 let root = Rpo256::merge(&[m.into(), n.into()]);
476
477 let store = MerkleStore::default()
478 .with_merkle_tree([a, b, c, d, e, f, g, h])
479 .unwrap();
480 let path = store
481 .get_path(root.into(), NodeIndex::new(3, 1))
482 .unwrap()
483 .path;
484
485 let expected = MerklePath::new([a.into(), j.into(), n.into()].to_vec());
486 assert_eq!(path, expected);
487}
488
489#[test]
490fn test_set_node() -> Result<(), MerkleError> {
491 let mtree = MerkleTree::new(LEAVES4.to_vec())?;
492 let mut store = MerkleStore::default().with_merkle_tree(LEAVES4)?;
493 let value = int_to_node(42);
494 let index = NodeIndex::new(mtree.depth(), 0);
495 let new_root = store.set_node(mtree.root(), index, value)?.root;
496 assert_eq!(
497 store.get_node(new_root, index),
498 Ok(value),
499 "Value must have changed"
500 );
501
502 Ok(())
503}
504
505#[test]
506fn test_constructors() -> Result<(), MerkleError> {
507 let store = MerkleStore::new().with_merkle_tree(LEAVES4)?;
508 let mtree = MerkleTree::new(LEAVES4.to_vec())?;
509
510 let depth = mtree.depth();
511 let leaves = 2u64.pow(depth.into());
512 for index in 0..leaves {
513 let index = NodeIndex::new(depth, index);
514 let value_path = store.get_path(mtree.root(), index)?;
515 assert_eq!(mtree.get_path(index)?, value_path.path);
516 }
517
518 let store = MerkleStore::default()
519 .with_sparse_merkle_tree(KEYS4.into_iter().zip(LEAVES4.into_iter()))?;
520 let smt = SimpleSmt::new(SimpleSmt::MAX_DEPTH)
521 .unwrap()
522 .with_leaves(KEYS4.into_iter().zip(LEAVES4.into_iter()))
523 .unwrap();
524 let depth = smt.depth();
525
526 for key in KEYS4 {
527 let index = NodeIndex::new(depth, key);
528 let value_path = store.get_path(smt.root(), index)?;
529 assert_eq!(smt.get_path(index)?, value_path.path);
530 }
531
532 let d = 2;
533 let paths = [
534 (0, LEAVES4[0], mtree.get_path(NodeIndex::new(d, 0)).unwrap()),
535 (1, LEAVES4[1], mtree.get_path(NodeIndex::new(d, 1)).unwrap()),
536 (2, LEAVES4[2], mtree.get_path(NodeIndex::new(d, 2)).unwrap()),
537 (3, LEAVES4[3], mtree.get_path(NodeIndex::new(d, 3)).unwrap()),
538 ];
539
540 let store1 = MerkleStore::default().with_merkle_paths(paths.clone())?;
541 let store2 = MerkleStore::default()
542 .with_merkle_path(0, LEAVES4[0], mtree.get_path(NodeIndex::new(d, 0))?)?
543 .with_merkle_path(1, LEAVES4[1], mtree.get_path(NodeIndex::new(d, 1))?)?
544 .with_merkle_path(2, LEAVES4[2], mtree.get_path(NodeIndex::new(d, 2))?)?
545 .with_merkle_path(3, LEAVES4[3], mtree.get_path(NodeIndex::new(d, 3))?)?;
546 let set = MerklePathSet::new(d).with_paths(paths).unwrap();
547
548 for key in [0, 1, 2, 3] {
549 let index = NodeIndex::new(d, key);
550 let value_path1 = store1.get_path(set.root(), index)?;
551 let value_path2 = store2.get_path(set.root(), index)?;
552 assert_eq!(value_path1, value_path2);
553
554 let index = NodeIndex::new(d, key);
555 assert_eq!(set.get_path(index)?, value_path1.path);
556 }
557
558 Ok(())
559}
560
561#[cfg(std)]
562#[test]
563fn test_serialization() -> Result<(), Box<dyn Error>> {
564 let original = MerkleStore::new().with_merkle_tree(LEAVES4)?;
565 let decoded = MerkleStore::read_from_bytes(&original.to_bytes())?;
566 assert_eq!(original, decoded);
567 Ok(())
568}