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