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