miden-crypto/src/merkle/simple_smt/tests.rs
src/merkle/simple_smt/tests.rsRaw
1use super::{
2 super::{InnerNodeInfo, MerkleError, MerkleTree, RpoDigest, SimpleSmt, EMPTY_WORD},
3 NodeIndex, Rpo256, Vec,
4};
5use crate::{
6 merkle::{digests_to_words, int_to_leaf, int_to_node, EmptySubtreeRoots},
7 Word,
8};
9
10// TEST DATA
11// ================================================================================================
12
13const KEYS4: [u64; 4] = [0, 1, 2, 3];
14const KEYS8: [u64; 8] = [0, 1, 2, 3, 4, 5, 6, 7];
15
16const VALUES4: [RpoDigest; 4] = [int_to_node(1), int_to_node(2), int_to_node(3), int_to_node(4)];
17
18const VALUES8: [RpoDigest; 8] = [
19 int_to_node(1),
20 int_to_node(2),
21 int_to_node(3),
22 int_to_node(4),
23 int_to_node(5),
24 int_to_node(6),
25 int_to_node(7),
26 int_to_node(8),
27];
28
29const ZERO_VALUES8: [Word; 8] = [int_to_leaf(0); 8];
30
31// TESTS
32// ================================================================================================
33
34#[test]
35fn build_empty_tree() {
36 // tree of depth 3
37 let smt = SimpleSmt::new(3).unwrap();
38 let mt = MerkleTree::new(ZERO_VALUES8.to_vec()).unwrap();
39 assert_eq!(mt.root(), smt.root());
40}
41
42#[test]
43fn build_sparse_tree() {
44 let mut smt = SimpleSmt::new(3).unwrap();
45 let mut values = ZERO_VALUES8.to_vec();
46
47 // insert single value
48 let key = 6;
49 let new_node = int_to_leaf(7);
50 values[key as usize] = new_node;
51 let old_value = smt.update_leaf(key, new_node).expect("Failed to update leaf");
52 let mt2 = MerkleTree::new(values.clone()).unwrap();
53 assert_eq!(mt2.root(), smt.root());
54 assert_eq!(
55 mt2.get_path(NodeIndex::make(3, 6)).unwrap(),
56 smt.get_path(NodeIndex::make(3, 6)).unwrap()
57 );
58 assert_eq!(old_value, EMPTY_WORD);
59
60 // insert second value at distinct leaf branch
61 let key = 2;
62 let new_node = int_to_leaf(3);
63 values[key as usize] = new_node;
64 let old_value = smt.update_leaf(key, new_node).expect("Failed to update leaf");
65 let mt3 = MerkleTree::new(values).unwrap();
66 assert_eq!(mt3.root(), smt.root());
67 assert_eq!(
68 mt3.get_path(NodeIndex::make(3, 2)).unwrap(),
69 smt.get_path(NodeIndex::make(3, 2)).unwrap()
70 );
71 assert_eq!(old_value, EMPTY_WORD);
72}
73
74/// Tests that [`SimpleSmt::with_contiguous_leaves`] works as expected
75#[test]
76fn build_contiguous_tree() {
77 let tree_with_leaves = SimpleSmt::with_leaves(
78 2,
79 [0, 1, 2, 3].into_iter().zip(digests_to_words(&VALUES4).into_iter()),
80 )
81 .unwrap();
82
83 let tree_with_contiguous_leaves =
84 SimpleSmt::with_contiguous_leaves(2, digests_to_words(&VALUES4).into_iter()).unwrap();
85
86 assert_eq!(tree_with_leaves, tree_with_contiguous_leaves);
87}
88
89#[test]
90fn test_depth2_tree() {
91 let tree =
92 SimpleSmt::with_leaves(2, KEYS4.into_iter().zip(digests_to_words(&VALUES4).into_iter()))
93 .unwrap();
94
95 // check internal structure
96 let (root, node2, node3) = compute_internal_nodes();
97 assert_eq!(root, tree.root());
98 assert_eq!(node2, tree.get_node(NodeIndex::make(1, 0)).unwrap());
99 assert_eq!(node3, tree.get_node(NodeIndex::make(1, 1)).unwrap());
100
101 // check get_node()
102 assert_eq!(VALUES4[0], tree.get_node(NodeIndex::make(2, 0)).unwrap());
103 assert_eq!(VALUES4[1], tree.get_node(NodeIndex::make(2, 1)).unwrap());
104 assert_eq!(VALUES4[2], tree.get_node(NodeIndex::make(2, 2)).unwrap());
105 assert_eq!(VALUES4[3], tree.get_node(NodeIndex::make(2, 3)).unwrap());
106
107 // check get_path(): depth 2
108 assert_eq!(vec![VALUES4[1], node3], *tree.get_path(NodeIndex::make(2, 0)).unwrap());
109 assert_eq!(vec![VALUES4[0], node3], *tree.get_path(NodeIndex::make(2, 1)).unwrap());
110 assert_eq!(vec![VALUES4[3], node2], *tree.get_path(NodeIndex::make(2, 2)).unwrap());
111 assert_eq!(vec![VALUES4[2], node2], *tree.get_path(NodeIndex::make(2, 3)).unwrap());
112
113 // check get_path(): depth 1
114 assert_eq!(vec![node3], *tree.get_path(NodeIndex::make(1, 0)).unwrap());
115 assert_eq!(vec![node2], *tree.get_path(NodeIndex::make(1, 1)).unwrap());
116}
117
118#[test]
119fn test_inner_node_iterator() -> Result<(), MerkleError> {
120 let tree =
121 SimpleSmt::with_leaves(2, KEYS4.into_iter().zip(digests_to_words(&VALUES4).into_iter()))
122 .unwrap();
123
124 // check depth 2
125 assert_eq!(VALUES4[0], tree.get_node(NodeIndex::make(2, 0)).unwrap());
126 assert_eq!(VALUES4[1], tree.get_node(NodeIndex::make(2, 1)).unwrap());
127 assert_eq!(VALUES4[2], tree.get_node(NodeIndex::make(2, 2)).unwrap());
128 assert_eq!(VALUES4[3], tree.get_node(NodeIndex::make(2, 3)).unwrap());
129
130 // get parent nodes
131 let root = tree.root();
132 let l1n0 = tree.get_node(NodeIndex::make(1, 0))?;
133 let l1n1 = tree.get_node(NodeIndex::make(1, 1))?;
134 let l2n0 = tree.get_node(NodeIndex::make(2, 0))?;
135 let l2n1 = tree.get_node(NodeIndex::make(2, 1))?;
136 let l2n2 = tree.get_node(NodeIndex::make(2, 2))?;
137 let l2n3 = tree.get_node(NodeIndex::make(2, 3))?;
138
139 let nodes: Vec<InnerNodeInfo> = tree.inner_nodes().collect();
140 let expected = vec![
141 InnerNodeInfo { value: root, left: l1n0, right: l1n1 },
142 InnerNodeInfo { value: l1n0, left: l2n0, right: l2n1 },
143 InnerNodeInfo { value: l1n1, left: l2n2, right: l2n3 },
144 ];
145 assert_eq!(nodes, expected);
146
147 Ok(())
148}
149
150#[test]
151fn update_leaf() {
152 let mut tree =
153 SimpleSmt::with_leaves(3, KEYS8.into_iter().zip(digests_to_words(&VALUES8).into_iter()))
154 .unwrap();
155
156 // update one value
157 let key = 3;
158 let new_node = int_to_leaf(9);
159 let mut expected_values = digests_to_words(&VALUES8);
160 expected_values[key] = new_node;
161 let expected_tree = MerkleTree::new(expected_values.clone()).unwrap();
162
163 let old_leaf = tree.update_leaf(key as u64, new_node).unwrap();
164 assert_eq!(expected_tree.root(), tree.root);
165 assert_eq!(old_leaf, *VALUES8[key]);
166
167 // update another value
168 let key = 6;
169 let new_node = int_to_leaf(10);
170 expected_values[key] = new_node;
171 let expected_tree = MerkleTree::new(expected_values.clone()).unwrap();
172
173 let old_leaf = tree.update_leaf(key as u64, new_node).unwrap();
174 assert_eq!(expected_tree.root(), tree.root);
175 assert_eq!(old_leaf, *VALUES8[key]);
176}
177
178#[test]
179fn small_tree_opening_is_consistent() {
180 // ____k____
181 // / \
182 // _i_ _j_
183 // / \ / \
184 // e f g h
185 // / \ / \ / \ / \
186 // a b 0 0 c 0 0 d
187
188 let z = EMPTY_WORD;
189
190 let a = Word::from(Rpo256::merge(&[z.into(); 2]));
191 let b = Word::from(Rpo256::merge(&[a.into(); 2]));
192 let c = Word::from(Rpo256::merge(&[b.into(); 2]));
193 let d = Word::from(Rpo256::merge(&[c.into(); 2]));
194
195 let e = Rpo256::merge(&[a.into(), b.into()]);
196 let f = Rpo256::merge(&[z.into(), z.into()]);
197 let g = Rpo256::merge(&[c.into(), z.into()]);
198 let h = Rpo256::merge(&[z.into(), d.into()]);
199
200 let i = Rpo256::merge(&[e, f]);
201 let j = Rpo256::merge(&[g, h]);
202
203 let k = Rpo256::merge(&[i, j]);
204
205 let depth = 3;
206 let entries = vec![(0, a), (1, b), (4, c), (7, d)];
207 let tree = SimpleSmt::with_leaves(depth, entries).unwrap();
208
209 assert_eq!(tree.root(), k);
210
211 let cases: Vec<(u8, u64, Vec<RpoDigest>)> = vec![
212 (3, 0, vec![b.into(), f, j]),
213 (3, 1, vec![a.into(), f, j]),
214 (3, 4, vec![z.into(), h, i]),
215 (3, 7, vec![z.into(), g, i]),
216 (2, 0, vec![f, j]),
217 (2, 1, vec![e, j]),
218 (2, 2, vec![h, i]),
219 (2, 3, vec![g, i]),
220 (1, 0, vec![j]),
221 (1, 1, vec![i]),
222 ];
223
224 for (depth, key, path) in cases {
225 let opening = tree.get_path(NodeIndex::make(depth, key)).unwrap();
226
227 assert_eq!(path, *opening);
228 }
229}
230
231#[test]
232fn test_simplesmt_fail_on_duplicates() {
233 let values = [
234 // same key, same value
235 (int_to_leaf(1), int_to_leaf(1)),
236 // same key, different values
237 (int_to_leaf(1), int_to_leaf(2)),
238 // same key, set to zero
239 (EMPTY_WORD, int_to_leaf(1)),
240 // same key, re-set to zero
241 (int_to_leaf(1), EMPTY_WORD),
242 // same key, set to zero twice
243 (EMPTY_WORD, EMPTY_WORD),
244 ];
245
246 for (first, second) in values.iter() {
247 // consecutive
248 let entries = [(1, *first), (1, *second)];
249 let smt = SimpleSmt::with_leaves(64, entries);
250 assert_eq!(smt.unwrap_err(), MerkleError::DuplicateValuesForIndex(1));
251
252 // not consecutive
253 let entries = [(1, *first), (5, int_to_leaf(5)), (1, *second)];
254 let smt = SimpleSmt::with_leaves(64, entries);
255 assert_eq!(smt.unwrap_err(), MerkleError::DuplicateValuesForIndex(1));
256 }
257}
258
259#[test]
260fn with_no_duplicates_empty_node() {
261 let entries = [(1_u64, int_to_leaf(0)), (5, int_to_leaf(2))];
262 let smt = SimpleSmt::with_leaves(64, entries);
263 assert!(smt.is_ok());
264}
265
266#[test]
267fn test_simplesmt_update_nonexisting_leaf_with_zero() {
268 // TESTING WITH EMPTY WORD
269 // --------------------------------------------------------------------------------------------
270
271 // Depth 1 has 2 leaf. Position is 0-indexed, position 2 doesn't exist.
272 let mut smt = SimpleSmt::new(1).unwrap();
273 let result = smt.update_leaf(2, EMPTY_WORD);
274 assert!(!smt.leaves.contains_key(&2));
275 assert!(result.is_err());
276
277 // Depth 2 has 4 leaves. Position is 0-indexed, position 4 doesn't exist.
278 let mut smt = SimpleSmt::new(2).unwrap();
279 let result = smt.update_leaf(4, EMPTY_WORD);
280 assert!(!smt.leaves.contains_key(&4));
281 assert!(result.is_err());
282
283 // Depth 3 has 8 leaves. Position is 0-indexed, position 8 doesn't exist.
284 let mut smt = SimpleSmt::new(3).unwrap();
285 let result = smt.update_leaf(8, EMPTY_WORD);
286 assert!(!smt.leaves.contains_key(&8));
287 assert!(result.is_err());
288
289 // TESTING WITH A VALUE
290 // --------------------------------------------------------------------------------------------
291 let value = int_to_node(1);
292
293 // Depth 1 has 2 leaves. Position is 0-indexed, position 1 doesn't exist.
294 let mut smt = SimpleSmt::new(1).unwrap();
295 let result = smt.update_leaf(2, *value);
296 assert!(!smt.leaves.contains_key(&2));
297 assert!(result.is_err());
298
299 // Depth 2 has 4 leaves. Position is 0-indexed, position 2 doesn't exist.
300 let mut smt = SimpleSmt::new(2).unwrap();
301 let result = smt.update_leaf(4, *value);
302 assert!(!smt.leaves.contains_key(&4));
303 assert!(result.is_err());
304
305 // Depth 3 has 8 leaves. Position is 0-indexed, position 4 doesn't exist.
306 let mut smt = SimpleSmt::new(3).unwrap();
307 let result = smt.update_leaf(8, *value);
308 assert!(!smt.leaves.contains_key(&8));
309 assert!(result.is_err());
310}
311
312#[test]
313fn test_simplesmt_with_leaves_nonexisting_leaf() {
314 // TESTING WITH EMPTY WORD
315 // --------------------------------------------------------------------------------------------
316
317 // Depth 1 has 2 leaf. Position is 0-indexed, position 2 doesn't exist.
318 let leaves = [(2, EMPTY_WORD)];
319 let result = SimpleSmt::with_leaves(1, leaves);
320 assert!(result.is_err());
321
322 // Depth 2 has 4 leaves. Position is 0-indexed, position 4 doesn't exist.
323 let leaves = [(4, EMPTY_WORD)];
324 let result = SimpleSmt::with_leaves(2, leaves);
325 assert!(result.is_err());
326
327 // Depth 3 has 8 leaves. Position is 0-indexed, position 8 doesn't exist.
328 let leaves = [(8, EMPTY_WORD)];
329 let result = SimpleSmt::with_leaves(3, leaves);
330 assert!(result.is_err());
331
332 // TESTING WITH A VALUE
333 // --------------------------------------------------------------------------------------------
334 let value = int_to_node(1);
335
336 // Depth 1 has 2 leaves. Position is 0-indexed, position 2 doesn't exist.
337 let leaves = [(2, *value)];
338 let result = SimpleSmt::with_leaves(1, leaves);
339 assert!(result.is_err());
340
341 // Depth 2 has 4 leaves. Position is 0-indexed, position 4 doesn't exist.
342 let leaves = [(4, *value)];
343 let result = SimpleSmt::with_leaves(2, leaves);
344 assert!(result.is_err());
345
346 // Depth 3 has 8 leaves. Position is 0-indexed, position 8 doesn't exist.
347 let leaves = [(8, *value)];
348 let result = SimpleSmt::with_leaves(3, leaves);
349 assert!(result.is_err());
350}
351
352#[test]
353fn test_simplesmt_set_subtree() {
354 // Final Tree:
355 //
356 // ____k____
357 // / \
358 // _i_ _j_
359 // / \ / \
360 // e f g h
361 // / \ / \ / \ / \
362 // a b 0 0 c 0 0 d
363
364 let z = EMPTY_WORD;
365
366 let a = Word::from(Rpo256::merge(&[z.into(); 2]));
367 let b = Word::from(Rpo256::merge(&[a.into(); 2]));
368 let c = Word::from(Rpo256::merge(&[b.into(); 2]));
369 let d = Word::from(Rpo256::merge(&[c.into(); 2]));
370
371 let e = Rpo256::merge(&[a.into(), b.into()]);
372 let f = Rpo256::merge(&[z.into(), z.into()]);
373 let g = Rpo256::merge(&[c.into(), z.into()]);
374 let h = Rpo256::merge(&[z.into(), d.into()]);
375
376 let i = Rpo256::merge(&[e, f]);
377 let j = Rpo256::merge(&[g, h]);
378
379 let k = Rpo256::merge(&[i, j]);
380
381 // subtree:
382 // g
383 // / \
384 // c 0
385 let subtree = {
386 let depth = 1;
387 let entries = vec![(0, c)];
388 SimpleSmt::with_leaves(depth, entries).unwrap()
389 };
390
391 // insert subtree
392 let tree = {
393 let depth = 3;
394 let entries = vec![(0, a), (1, b), (7, d)];
395 let mut tree = SimpleSmt::with_leaves(depth, entries).unwrap();
396
397 tree.set_subtree(2, subtree).unwrap();
398
399 tree
400 };
401
402 assert_eq!(tree.root(), k);
403 assert_eq!(tree.get_leaf(4).unwrap(), c);
404 assert_eq!(tree.get_branch_node(&NodeIndex::new_unchecked(2, 2)).parent(), g);
405}
406
407/// Ensures that an invalid input node index into `set_subtree()` incurs no mutation of the tree
408#[test]
409fn test_simplesmt_set_subtree_unchanged_for_wrong_index() {
410 // Final Tree:
411 //
412 // ____k____
413 // / \
414 // _i_ _j_
415 // / \ / \
416 // e f g h
417 // / \ / \ / \ / \
418 // a b 0 0 c 0 0 d
419
420 let z = EMPTY_WORD;
421
422 let a = Word::from(Rpo256::merge(&[z.into(); 2]));
423 let b = Word::from(Rpo256::merge(&[a.into(); 2]));
424 let c = Word::from(Rpo256::merge(&[b.into(); 2]));
425 let d = Word::from(Rpo256::merge(&[c.into(); 2]));
426
427 // subtree:
428 // g
429 // / \
430 // c 0
431 let subtree = {
432 let depth = 1;
433 let entries = vec![(0, c)];
434 SimpleSmt::with_leaves(depth, entries).unwrap()
435 };
436
437 let mut tree = {
438 let depth = 3;
439 let entries = vec![(0, a), (1, b), (7, d)];
440 SimpleSmt::with_leaves(depth, entries).unwrap()
441 };
442 let tree_root_before_insertion = tree.root();
443
444 // insert subtree
445 assert!(tree.set_subtree(500, subtree).is_err());
446
447 assert_eq!(tree.root(), tree_root_before_insertion);
448}
449
450/// We insert an empty subtree that has the same depth as the original tree
451#[test]
452fn test_simplesmt_set_subtree_entire_tree() {
453 // Initial Tree:
454 //
455 // ____k____
456 // / \
457 // _i_ _j_
458 // / \ / \
459 // e f g h
460 // / \ / \ / \ / \
461 // a b 0 0 c 0 0 d
462
463 let z = EMPTY_WORD;
464
465 let a = Word::from(Rpo256::merge(&[z.into(); 2]));
466 let b = Word::from(Rpo256::merge(&[a.into(); 2]));
467 let c = Word::from(Rpo256::merge(&[b.into(); 2]));
468 let d = Word::from(Rpo256::merge(&[c.into(); 2]));
469
470 let depth = 3;
471
472 // subtree: E3
473 let subtree = { SimpleSmt::with_leaves(depth, Vec::new()).unwrap() };
474 assert_eq!(subtree.root(), *EmptySubtreeRoots::entry(depth, 0));
475
476 // insert subtree
477 let mut tree = {
478 let entries = vec![(0, a), (1, b), (4, c), (7, d)];
479 SimpleSmt::with_leaves(depth, entries).unwrap()
480 };
481
482 tree.set_subtree(0, subtree).unwrap();
483
484 assert_eq!(tree.root(), *EmptySubtreeRoots::entry(depth, 0));
485}
486
487// HELPER FUNCTIONS
488// --------------------------------------------------------------------------------------------
489
490fn compute_internal_nodes() -> (RpoDigest, RpoDigest, RpoDigest) {
491 let node2 = Rpo256::merge(&[VALUES4[0], VALUES4[1]]);
492 let node3 = Rpo256::merge(&[VALUES4[2], VALUES4[3]]);
493 let root = Rpo256::merge(&[node2, node3]);
494
495 (root, node2, node3)
496}