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