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