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