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 mut nodes: Vec<InnerNodeInfo> = tree.inner_nodes().collect();
145 let mut expected = [
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 nodes.sort();
151 expected.sort();
152
153 assert_eq!(nodes, expected);
154
155 Ok(())
156}
157
158#[test]
159fn test_insert() {
160 const DEPTH: u8 = 3;
161 let mut tree =
162 SimpleSmt::<DEPTH>::with_leaves(KEYS8.into_iter().zip(digests_to_words(&VALUES8))).unwrap();
163 assert_eq!(tree.num_leaves(), 8);
164
165 // update one value
166 let key = 3;
167 let new_node = int_to_leaf(9);
168 let mut expected_values = digests_to_words(&VALUES8);
169 expected_values[key] = new_node;
170 let expected_tree = MerkleTree::new(expected_values.clone()).unwrap();
171
172 let old_leaf = tree.insert(LeafIndex::<DEPTH>::new(key as u64).unwrap(), new_node);
173 assert_eq!(expected_tree.root(), tree.root);
174 assert_eq!(old_leaf, *VALUES8[key]);
175 assert_eq!(tree.num_leaves(), 8);
176
177 // update another value
178 let key = 6;
179 let new_node = int_to_leaf(10);
180 expected_values[key] = new_node;
181 let expected_tree = MerkleTree::new(expected_values.clone()).unwrap();
182
183 let old_leaf = tree.insert(LeafIndex::<DEPTH>::new(key as u64).unwrap(), new_node);
184 assert_eq!(expected_tree.root(), tree.root);
185 assert_eq!(old_leaf, *VALUES8[key]);
186 assert_eq!(tree.num_leaves(), 8);
187
188 // set a leaf to empty value
189 let key = 5;
190 let new_node = EMPTY_WORD;
191 expected_values[key] = new_node;
192 let expected_tree = MerkleTree::new(expected_values.clone()).unwrap();
193
194 let old_leaf = tree.insert(LeafIndex::<DEPTH>::new(key as u64).unwrap(), new_node);
195 assert_eq!(expected_tree.root(), tree.root);
196 assert_eq!(old_leaf, *VALUES8[key]);
197 assert_eq!(tree.num_leaves(), 7);
198}
199
200#[test]
201fn small_tree_opening_is_consistent() {
202 // ____k____
203 // / \
204 // _i_ _j_
205 // / \ / \
206 // e f g h
207 // / \ / \ / \ / \
208 // a b 0 0 c 0 0 d
209
210 let z = EMPTY_WORD;
211
212 let a = Word::from(Rpo256::merge(&[z.into(); 2]));
213 let b = Word::from(Rpo256::merge(&[a.into(); 2]));
214 let c = Word::from(Rpo256::merge(&[b.into(); 2]));
215 let d = Word::from(Rpo256::merge(&[c.into(); 2]));
216
217 let e = Rpo256::merge(&[a.into(), b.into()]);
218 let f = Rpo256::merge(&[z.into(), z.into()]);
219 let g = Rpo256::merge(&[c.into(), z.into()]);
220 let h = Rpo256::merge(&[z.into(), d.into()]);
221
222 let i = Rpo256::merge(&[e, f]);
223 let j = Rpo256::merge(&[g, h]);
224
225 let k = Rpo256::merge(&[i, j]);
226
227 let entries = vec![(0, a), (1, b), (4, c), (7, d)];
228 let tree = SimpleSmt::<3>::with_leaves(entries).unwrap();
229
230 assert_eq!(tree.root(), k);
231
232 let cases: Vec<(u64, Vec<RpoDigest>)> = vec![
233 (0, vec![b.into(), f, j]),
234 (1, vec![a.into(), f, j]),
235 (4, vec![z.into(), h, i]),
236 (7, vec![z.into(), g, i]),
237 ];
238
239 for (key, path) in cases {
240 let opening = tree.open(&LeafIndex::<3>::new(key).unwrap());
241
242 assert_eq!(path, *opening.path);
243 }
244}
245
246#[test]
247fn test_simplesmt_fail_on_duplicates() {
248 let values = [
249 // same key, same value
250 (int_to_leaf(1), int_to_leaf(1)),
251 // same key, different values
252 (int_to_leaf(1), int_to_leaf(2)),
253 // same key, set to zero
254 (EMPTY_WORD, int_to_leaf(1)),
255 // same key, re-set to zero
256 (int_to_leaf(1), EMPTY_WORD),
257 // same key, set to zero twice
258 (EMPTY_WORD, EMPTY_WORD),
259 ];
260
261 for (first, second) in values.iter() {
262 // consecutive
263 let entries = [(1, *first), (1, *second)];
264 let smt = SimpleSmt::<64>::with_leaves(entries);
265 assert_matches!(smt.unwrap_err(), MerkleError::DuplicateValuesForIndex(1));
266
267 // not consecutive
268 let entries = [(1, *first), (5, int_to_leaf(5)), (1, *second)];
269 let smt = SimpleSmt::<64>::with_leaves(entries);
270 assert_matches!(smt.unwrap_err(), MerkleError::DuplicateValuesForIndex(1));
271 }
272}
273
274#[test]
275fn with_no_duplicates_empty_node() {
276 let entries = [(1_u64, int_to_leaf(0)), (5, int_to_leaf(2))];
277 let smt = SimpleSmt::<64>::with_leaves(entries);
278 assert!(smt.is_ok());
279}
280
281#[test]
282fn test_simplesmt_with_leaves_nonexisting_leaf() {
283 // TESTING WITH EMPTY WORD
284 // --------------------------------------------------------------------------------------------
285
286 // Depth 1 has 2 leaf. Position is 0-indexed, position 2 doesn't exist.
287 let leaves = [(2, EMPTY_WORD)];
288 let result = SimpleSmt::<1>::with_leaves(leaves);
289 assert!(result.is_err());
290
291 // Depth 2 has 4 leaves. Position is 0-indexed, position 4 doesn't exist.
292 let leaves = [(4, EMPTY_WORD)];
293 let result = SimpleSmt::<2>::with_leaves(leaves);
294 assert!(result.is_err());
295
296 // Depth 3 has 8 leaves. Position is 0-indexed, position 8 doesn't exist.
297 let leaves = [(8, EMPTY_WORD)];
298 let result = SimpleSmt::<3>::with_leaves(leaves);
299 assert!(result.is_err());
300
301 // TESTING WITH A VALUE
302 // --------------------------------------------------------------------------------------------
303 let value = int_to_node(1);
304
305 // Depth 1 has 2 leaves. Position is 0-indexed, position 2 doesn't exist.
306 let leaves = [(2, *value)];
307 let result = SimpleSmt::<1>::with_leaves(leaves);
308 assert!(result.is_err());
309
310 // Depth 2 has 4 leaves. Position is 0-indexed, position 4 doesn't exist.
311 let leaves = [(4, *value)];
312 let result = SimpleSmt::<2>::with_leaves(leaves);
313 assert!(result.is_err());
314
315 // Depth 3 has 8 leaves. Position is 0-indexed, position 8 doesn't exist.
316 let leaves = [(8, *value)];
317 let result = SimpleSmt::<3>::with_leaves(leaves);
318 assert!(result.is_err());
319}
320
321#[test]
322fn test_simplesmt_set_subtree() {
323 // Final Tree:
324 //
325 // ____k____
326 // / \
327 // _i_ _j_
328 // / \ / \
329 // e f g h
330 // / \ / \ / \ / \
331 // a b 0 0 c 0 0 d
332
333 let z = EMPTY_WORD;
334
335 let a = Word::from(Rpo256::merge(&[z.into(); 2]));
336 let b = Word::from(Rpo256::merge(&[a.into(); 2]));
337 let c = Word::from(Rpo256::merge(&[b.into(); 2]));
338 let d = Word::from(Rpo256::merge(&[c.into(); 2]));
339
340 let e = Rpo256::merge(&[a.into(), b.into()]);
341 let f = Rpo256::merge(&[z.into(), z.into()]);
342 let g = Rpo256::merge(&[c.into(), z.into()]);
343 let h = Rpo256::merge(&[z.into(), d.into()]);
344
345 let i = Rpo256::merge(&[e, f]);
346 let j = Rpo256::merge(&[g, h]);
347
348 let k = Rpo256::merge(&[i, j]);
349
350 // subtree:
351 // g
352 // / \
353 // c 0
354 let subtree = {
355 let entries = vec![(0, c)];
356 SimpleSmt::<1>::with_leaves(entries).unwrap()
357 };
358
359 // insert subtree
360 const TREE_DEPTH: u8 = 3;
361 let tree = {
362 let entries = vec![(0, a), (1, b), (7, d)];
363 let mut tree = SimpleSmt::<TREE_DEPTH>::with_leaves(entries).unwrap();
364
365 tree.set_subtree(2, subtree).unwrap();
366
367 tree
368 };
369
370 assert_eq!(tree.root(), k);
371 assert_eq!(tree.get_leaf(&LeafIndex::<TREE_DEPTH>::new(4).unwrap()), c);
372 assert_eq!(tree.get_inner_node(NodeIndex::new_unchecked(2, 2)).hash(), g);
373}
374
375/// Ensures that an invalid input node index into `set_subtree()` incurs no mutation of the tree
376#[test]
377fn test_simplesmt_set_subtree_unchanged_for_wrong_index() {
378 // Final Tree:
379 //
380 // ____k____
381 // / \
382 // _i_ _j_
383 // / \ / \
384 // e f g h
385 // / \ / \ / \ / \
386 // a b 0 0 c 0 0 d
387
388 let z = EMPTY_WORD;
389
390 let a = Word::from(Rpo256::merge(&[z.into(); 2]));
391 let b = Word::from(Rpo256::merge(&[a.into(); 2]));
392 let c = Word::from(Rpo256::merge(&[b.into(); 2]));
393 let d = Word::from(Rpo256::merge(&[c.into(); 2]));
394
395 // subtree:
396 // g
397 // / \
398 // c 0
399 let subtree = {
400 let entries = vec![(0, c)];
401 SimpleSmt::<1>::with_leaves(entries).unwrap()
402 };
403
404 let mut tree = {
405 let entries = vec![(0, a), (1, b), (7, d)];
406 SimpleSmt::<3>::with_leaves(entries).unwrap()
407 };
408 let tree_root_before_insertion = tree.root();
409
410 // insert subtree
411 assert!(tree.set_subtree(500, subtree).is_err());
412
413 assert_eq!(tree.root(), tree_root_before_insertion);
414}
415
416/// We insert an empty subtree that has the same depth as the original tree
417#[test]
418fn test_simplesmt_set_subtree_entire_tree() {
419 // Initial Tree:
420 //
421 // ____k____
422 // / \
423 // _i_ _j_
424 // / \ / \
425 // e f g h
426 // / \ / \ / \ / \
427 // a b 0 0 c 0 0 d
428
429 let z = EMPTY_WORD;
430
431 let a = Word::from(Rpo256::merge(&[z.into(); 2]));
432 let b = Word::from(Rpo256::merge(&[a.into(); 2]));
433 let c = Word::from(Rpo256::merge(&[b.into(); 2]));
434 let d = Word::from(Rpo256::merge(&[c.into(); 2]));
435
436 // subtree: E3
437 const DEPTH: u8 = 3;
438 let subtree = { SimpleSmt::<DEPTH>::with_leaves(Vec::new()).unwrap() };
439 assert_eq!(subtree.root(), *EmptySubtreeRoots::entry(DEPTH, 0));
440
441 // insert subtree
442 let mut tree = {
443 let entries = vec![(0, a), (1, b), (4, c), (7, d)];
444 SimpleSmt::<3>::with_leaves(entries).unwrap()
445 };
446
447 tree.set_subtree(0, subtree).unwrap();
448
449 assert_eq!(tree.root(), *EmptySubtreeRoots::entry(DEPTH, 0));
450}
451
452/// Tests that `EMPTY_ROOT` constant generated in the `SimpleSmt` equals to the root of the empty
453/// tree of depth 64
454#[test]
455fn test_simplesmt_check_empty_root_constant() {
456 // get the root of the empty tree of depth 64
457 let empty_root_64_depth = EmptySubtreeRoots::empty_hashes(64)[0];
458 assert_eq!(empty_root_64_depth, SimpleSmt::<64>::EMPTY_ROOT);
459
460 // get the root of the empty tree of depth 32
461 let empty_root_32_depth = EmptySubtreeRoots::empty_hashes(32)[0];
462 assert_eq!(empty_root_32_depth, SimpleSmt::<32>::EMPTY_ROOT);
463
464 // get the root of the empty tree of depth 0
465 let empty_root_1_depth = EmptySubtreeRoots::empty_hashes(1)[0];
466 assert_eq!(empty_root_1_depth, SimpleSmt::<1>::EMPTY_ROOT);
467}
468
469// HELPER FUNCTIONS
470// --------------------------------------------------------------------------------------------
471
472fn compute_internal_nodes() -> (RpoDigest, RpoDigest, RpoDigest) {
473 let node2 = Rpo256::merge(&[VALUES4[0], VALUES4[1]]);
474 let node3 = Rpo256::merge(&[VALUES4[2], VALUES4[3]]);
475 let root = Rpo256::merge(&[node2, node3]);
476
477 (root, node2, node3)
478}