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