miden-crypto/src/merkle/tiered_smt/tests.rs
src/merkle/tiered_smt/tests.rsRaw
1use super::{
2 super::{super::ONE, Felt, MerkleStore, WORD_SIZE, ZERO},
3 EmptySubtreeRoots, InnerNodeInfo, NodeIndex, Rpo256, RpoDigest, TieredSmt, Vec, Word,
4};
5
6// INSERTION TESTS
7// ================================================================================================
8
9#[test]
10fn tsmt_insert_one() {
11 let mut smt = TieredSmt::default();
12 let mut store = MerkleStore::default();
13
14 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
15 let key = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
16 let value = [ONE; WORD_SIZE];
17
18 // since the tree is empty, the first node will be inserted at depth 16 and the index will be
19 // 16 most significant bits of the key
20 let index = NodeIndex::make(16, raw >> 48);
21 let leaf_node = build_leaf_node(key, value, 16);
22 let tree_root = store.set_node(smt.root(), index, leaf_node).unwrap().root;
23
24 smt.insert(key, value);
25
26 assert_eq!(smt.root(), tree_root);
27
28 // make sure the value was inserted, and the node is at the expected index
29 assert_eq!(smt.get_value(key), value);
30 assert_eq!(smt.get_node(index).unwrap(), leaf_node);
31
32 // make sure the paths we get from the store and the tree match
33 let expected_path = store.get_path(tree_root, index).unwrap();
34 assert_eq!(smt.get_path(index).unwrap(), expected_path.path);
35
36 // make sure inner nodes match
37 let expected_nodes = get_non_empty_nodes(&store);
38 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
39 assert_eq!(actual_nodes.len(), expected_nodes.len());
40 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
41
42 // make sure leaves are returned correctly
43 let mut leaves = smt.upper_leaves();
44 assert_eq!(leaves.next(), Some((leaf_node, key, value)));
45 assert_eq!(leaves.next(), None);
46}
47
48#[test]
49fn tsmt_insert_two_16() {
50 let mut smt = TieredSmt::default();
51 let mut store = MerkleStore::default();
52
53 // --- insert the first value ---------------------------------------------
54 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
55 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
56 let val_a = [ONE; WORD_SIZE];
57 smt.insert(key_a, val_a);
58
59 // --- insert the second value --------------------------------------------
60 // the key for this value has the same 16-bit prefix as the key for the first value,
61 // thus, on insertions, both values should be pushed to depth 32 tier
62 let raw_b = 0b_10101010_10101010_10011111_11111111_10010110_10010011_11100000_00000000_u64;
63 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
64 let val_b = [Felt::new(2); WORD_SIZE];
65 smt.insert(key_b, val_b);
66
67 // --- build Merkle store with equivalent data ----------------------------
68 let mut tree_root = get_init_root();
69 let index_a = NodeIndex::make(32, raw_a >> 32);
70 let leaf_node_a = build_leaf_node(key_a, val_a, 32);
71 tree_root = store.set_node(tree_root, index_a, leaf_node_a).unwrap().root;
72
73 let index_b = NodeIndex::make(32, raw_b >> 32);
74 let leaf_node_b = build_leaf_node(key_b, val_b, 32);
75 tree_root = store.set_node(tree_root, index_b, leaf_node_b).unwrap().root;
76
77 // --- verify that data is consistent between store and tree --------------
78
79 assert_eq!(smt.root(), tree_root);
80
81 assert_eq!(smt.get_value(key_a), val_a);
82 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
83 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
84 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
85
86 assert_eq!(smt.get_value(key_b), val_b);
87 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
88 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
89 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
90
91 // make sure inner nodes match - the store contains more entries because it keeps track of
92 // all prior state - so, we don't check that the number of inner nodes is the same in both
93 let expected_nodes = get_non_empty_nodes(&store);
94 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
95 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
96
97 // make sure leaves are returned correctly
98 let mut leaves = smt.upper_leaves();
99 assert_eq!(leaves.next(), Some((leaf_node_a, key_a, val_a)));
100 assert_eq!(leaves.next(), Some((leaf_node_b, key_b, val_b)));
101 assert_eq!(leaves.next(), None);
102}
103
104#[test]
105fn tsmt_insert_two_32() {
106 let mut smt = TieredSmt::default();
107 let mut store = MerkleStore::default();
108
109 // --- insert the first value ---------------------------------------------
110 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
111 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
112 let val_a = [ONE; WORD_SIZE];
113 smt.insert(key_a, val_a);
114
115 // --- insert the second value --------------------------------------------
116 // the key for this value has the same 32-bit prefix as the key for the first value,
117 // thus, on insertions, both values should be pushed to depth 48 tier
118 let raw_b = 0b_10101010_10101010_00011111_11111111_00010110_10010011_11100000_00000000_u64;
119 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
120 let val_b = [Felt::new(2); WORD_SIZE];
121 smt.insert(key_b, val_b);
122
123 // --- build Merkle store with equivalent data ----------------------------
124 let mut tree_root = get_init_root();
125 let index_a = NodeIndex::make(48, raw_a >> 16);
126 let leaf_node_a = build_leaf_node(key_a, val_a, 48);
127 tree_root = store.set_node(tree_root, index_a, leaf_node_a).unwrap().root;
128
129 let index_b = NodeIndex::make(48, raw_b >> 16);
130 let leaf_node_b = build_leaf_node(key_b, val_b, 48);
131 tree_root = store.set_node(tree_root, index_b, leaf_node_b).unwrap().root;
132
133 // --- verify that data is consistent between store and tree --------------
134
135 assert_eq!(smt.root(), tree_root);
136
137 assert_eq!(smt.get_value(key_a), val_a);
138 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
139 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
140 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
141
142 assert_eq!(smt.get_value(key_b), val_b);
143 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
144 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
145 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
146
147 // make sure inner nodes match - the store contains more entries because it keeps track of
148 // all prior state - so, we don't check that the number of inner nodes is the same in both
149 let expected_nodes = get_non_empty_nodes(&store);
150 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
151 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
152}
153
154#[test]
155fn tsmt_insert_three() {
156 let mut smt = TieredSmt::default();
157 let mut store = MerkleStore::default();
158
159 // --- insert the first value ---------------------------------------------
160 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
161 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
162 let val_a = [ONE; WORD_SIZE];
163 smt.insert(key_a, val_a);
164
165 // --- insert the second value --------------------------------------------
166 // the key for this value has the same 16-bit prefix as the key for the first value,
167 // thus, on insertions, both values should be pushed to depth 32 tier
168 let raw_b = 0b_10101010_10101010_10011111_11111111_10010110_10010011_11100000_00000000_u64;
169 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
170 let val_b = [Felt::new(2); WORD_SIZE];
171 smt.insert(key_b, val_b);
172
173 // --- insert the third value ---------------------------------------------
174 // the key for this value has the same 16-bit prefix as the keys for the first two,
175 // values; thus, on insertions, it will be inserted into depth 32 tier, but will not
176 // affect locations of the other two values
177 let raw_c = 0b_10101010_10101010_11011111_11111111_10010110_10010011_11100000_00000000_u64;
178 let key_c = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_c)]);
179 let val_c = [Felt::new(3); WORD_SIZE];
180 smt.insert(key_c, val_c);
181
182 // --- build Merkle store with equivalent data ----------------------------
183 let mut tree_root = get_init_root();
184 let index_a = NodeIndex::make(32, raw_a >> 32);
185 let leaf_node_a = build_leaf_node(key_a, val_a, 32);
186 tree_root = store.set_node(tree_root, index_a, leaf_node_a).unwrap().root;
187
188 let index_b = NodeIndex::make(32, raw_b >> 32);
189 let leaf_node_b = build_leaf_node(key_b, val_b, 32);
190 tree_root = store.set_node(tree_root, index_b, leaf_node_b).unwrap().root;
191
192 let index_c = NodeIndex::make(32, raw_c >> 32);
193 let leaf_node_c = build_leaf_node(key_c, val_c, 32);
194 tree_root = store.set_node(tree_root, index_c, leaf_node_c).unwrap().root;
195
196 // --- verify that data is consistent between store and tree --------------
197
198 assert_eq!(smt.root(), tree_root);
199
200 assert_eq!(smt.get_value(key_a), val_a);
201 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
202 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
203 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
204
205 assert_eq!(smt.get_value(key_b), val_b);
206 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
207 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
208 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
209
210 assert_eq!(smt.get_value(key_c), val_c);
211 assert_eq!(smt.get_node(index_c).unwrap(), leaf_node_c);
212 let expected_path = store.get_path(tree_root, index_c).unwrap().path;
213 assert_eq!(smt.get_path(index_c).unwrap(), expected_path);
214
215 // make sure inner nodes match - the store contains more entries because it keeps track of
216 // all prior state - so, we don't check that the number of inner nodes is the same in both
217 let expected_nodes = get_non_empty_nodes(&store);
218 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
219 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
220}
221
222// UPDATE TESTS
223// ================================================================================================
224
225#[test]
226fn tsmt_update() {
227 let mut smt = TieredSmt::default();
228 let mut store = MerkleStore::default();
229
230 // --- insert a value into the tree ---------------------------------------
231 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
232 let key = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
233 let value_a = [ONE; WORD_SIZE];
234 smt.insert(key, value_a);
235
236 // --- update the value ---------------------------------------------------
237 let value_b = [Felt::new(2); WORD_SIZE];
238 smt.insert(key, value_b);
239
240 // --- verify consistency -------------------------------------------------
241 let mut tree_root = get_init_root();
242 let index = NodeIndex::make(16, raw >> 48);
243 let leaf_node = build_leaf_node(key, value_b, 16);
244 tree_root = store.set_node(tree_root, index, leaf_node).unwrap().root;
245
246 assert_eq!(smt.root(), tree_root);
247
248 assert_eq!(smt.get_value(key), value_b);
249 assert_eq!(smt.get_node(index).unwrap(), leaf_node);
250 let expected_path = store.get_path(tree_root, index).unwrap().path;
251 assert_eq!(smt.get_path(index).unwrap(), expected_path);
252
253 // make sure inner nodes match - the store contains more entries because it keeps track of
254 // all prior state - so, we don't check that the number of inner nodes is the same in both
255 let expected_nodes = get_non_empty_nodes(&store);
256 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
257 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
258}
259
260// DELETION TESTS
261// ================================================================================================
262
263#[test]
264fn tsmt_delete_16() {
265 let mut smt = TieredSmt::default();
266
267 // --- insert a value into the tree ---------------------------------------
268 let smt0 = smt.clone();
269 let raw_a = 0b_01010101_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
270 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
271 let value_a = [ONE, ONE, ONE, ONE];
272 smt.insert(key_a, value_a);
273
274 // --- insert another value into the tree ---------------------------------
275 let smt1 = smt.clone();
276 let raw_b = 0b_01011111_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
277 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
278 let value_b = [ONE, ONE, ONE, ZERO];
279 smt.insert(key_b, value_b);
280
281 // --- delete the last inserted value -------------------------------------
282 assert_eq!(smt.insert(key_b, [ZERO; 4]), value_b);
283 assert_eq!(smt, smt1);
284
285 // --- delete the first inserted value ------------------------------------
286 assert_eq!(smt.insert(key_a, [ZERO; 4]), value_a);
287 assert_eq!(smt, smt0);
288}
289
290#[test]
291fn tsmt_delete_32() {
292 let mut smt = TieredSmt::default();
293
294 // --- insert a value into the tree ---------------------------------------
295 let smt0 = smt.clone();
296 let raw_a = 0b_01010101_01101100_01111111_11111111_10010110_10010011_11100000_00000000_u64;
297 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
298 let value_a = [ONE, ONE, ONE, ONE];
299 smt.insert(key_a, value_a);
300
301 // --- insert another with the same 16-bit prefix into the tree -----------
302 let smt1 = smt.clone();
303 let raw_b = 0b_01010101_01101100_00111111_11111111_10010110_10010011_11100000_00000000_u64;
304 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
305 let value_b = [ONE, ONE, ONE, ZERO];
306 smt.insert(key_b, value_b);
307
308 // --- insert the 3rd value with the same 16-bit prefix into the tree -----
309 let smt2 = smt.clone();
310 let raw_c = 0b_01010101_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
311 let key_c = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_c)]);
312 let value_c = [ONE, ONE, ZERO, ZERO];
313 smt.insert(key_c, value_c);
314
315 // --- delete the last inserted value -------------------------------------
316 assert_eq!(smt.insert(key_c, [ZERO; 4]), value_c);
317 assert_eq!(smt, smt2);
318
319 // --- delete the last inserted value -------------------------------------
320 assert_eq!(smt.insert(key_b, [ZERO; 4]), value_b);
321 assert_eq!(smt, smt1);
322
323 // --- delete the first inserted value ------------------------------------
324 assert_eq!(smt.insert(key_a, [ZERO; 4]), value_a);
325 assert_eq!(smt, smt0);
326}
327
328#[test]
329fn tsmt_delete_48_same_32_bit_prefix() {
330 let mut smt = TieredSmt::default();
331
332 // test the case when all values share the same 32-bit prefix
333
334 // --- insert a value into the tree ---------------------------------------
335 let smt0 = smt.clone();
336 let raw_a = 0b_01010101_01010101_11111111_11111111_10010110_10010011_11100000_00000000_u64;
337 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
338 let value_a = [ONE, ONE, ONE, ONE];
339 smt.insert(key_a, value_a);
340
341 // --- insert another with the same 32-bit prefix into the tree -----------
342 let smt1 = smt.clone();
343 let raw_b = 0b_01010101_01010101_11111111_11111111_11010110_10010011_11100000_00000000_u64;
344 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
345 let value_b = [ONE, ONE, ONE, ZERO];
346 smt.insert(key_b, value_b);
347
348 // --- insert the 3rd value with the same 32-bit prefix into the tree -----
349 let smt2 = smt.clone();
350 let raw_c = 0b_01010101_01010101_11111111_11111111_11110110_10010011_11100000_00000000_u64;
351 let key_c = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_c)]);
352 let value_c = [ONE, ONE, ZERO, ZERO];
353 smt.insert(key_c, value_c);
354
355 // --- delete the last inserted value -------------------------------------
356 assert_eq!(smt.insert(key_c, [ZERO; 4]), value_c);
357 assert_eq!(smt, smt2);
358
359 // --- delete the last inserted value -------------------------------------
360 assert_eq!(smt.insert(key_b, [ZERO; 4]), value_b);
361 assert_eq!(smt, smt1);
362
363 // --- delete the first inserted value ------------------------------------
364 assert_eq!(smt.insert(key_a, [ZERO; 4]), value_a);
365 assert_eq!(smt, smt0);
366}
367
368#[test]
369fn tsmt_delete_48_mixed_prefix() {
370 let mut smt = TieredSmt::default();
371
372 // test the case when some values share a 32-bit prefix and others share a 16-bit prefix
373
374 // --- insert a value into the tree ---------------------------------------
375 let smt0 = smt.clone();
376 let raw_a = 0b_01010101_01010101_11111111_11111111_10010110_10010011_11100000_00000000_u64;
377 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
378 let value_a = [ONE, ONE, ONE, ONE];
379 smt.insert(key_a, value_a);
380
381 // --- insert another with the same 16-bit prefix into the tree -----------
382 let smt1 = smt.clone();
383 let raw_b = 0b_01010101_01010101_01111111_11111111_10010110_10010011_11100000_00000000_u64;
384 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
385 let value_b = [ONE, ONE, ONE, ZERO];
386 smt.insert(key_b, value_b);
387
388 // --- insert a value with the same 32-bit prefix as the first value -----
389 let smt2 = smt.clone();
390 let raw_c = 0b_01010101_01010101_11111111_11111111_11010110_10010011_11100000_00000000_u64;
391 let key_c = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_c)]);
392 let value_c = [ONE, ONE, ZERO, ZERO];
393 smt.insert(key_c, value_c);
394
395 // --- insert another value with the same 32-bit prefix as the first value
396 let smt3 = smt.clone();
397 let raw_d = 0b_01010101_01010101_11111111_11111111_11110110_10010011_11100000_00000000_u64;
398 let key_d = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_d)]);
399 let value_d = [ONE, ZERO, ZERO, ZERO];
400 smt.insert(key_d, value_d);
401
402 // --- delete the inserted values one-by-one ------------------------------
403 assert_eq!(smt.insert(key_d, [ZERO; 4]), value_d);
404 assert_eq!(smt, smt3);
405
406 assert_eq!(smt.insert(key_c, [ZERO; 4]), value_c);
407 assert_eq!(smt, smt2);
408
409 assert_eq!(smt.insert(key_b, [ZERO; 4]), value_b);
410 assert_eq!(smt, smt1);
411
412 assert_eq!(smt.insert(key_a, [ZERO; 4]), value_a);
413 assert_eq!(smt, smt0);
414}
415
416#[test]
417fn tsmt_delete_64() {
418 let mut smt = TieredSmt::default();
419
420 // test the case when all values share the same 48-bit prefix
421
422 // --- insert a value into the tree ---------------------------------------
423 let smt0 = smt.clone();
424 let raw_a = 0b_01010101_01010101_11111111_11111111_10110101_10101010_11111100_00000000_u64;
425 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
426 let value_a = [ONE, ONE, ONE, ONE];
427 smt.insert(key_a, value_a);
428
429 // --- insert a value with the same 48-bit prefix into the tree -----------
430 let smt1 = smt.clone();
431 let raw_b = 0b_01010101_01010101_11111111_11111111_10110101_10101010_10111100_00000000_u64;
432 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
433 let value_b = [ONE, ONE, ONE, ZERO];
434 smt.insert(key_b, value_b);
435
436 // --- insert a value with the same 32-bit prefix into the tree -----------
437 let smt2 = smt.clone();
438 let raw_c = 0b_01010101_01010101_11111111_11111111_11111101_10101010_10111100_00000000_u64;
439 let key_c = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_c)]);
440 let value_c = [ONE, ONE, ZERO, ZERO];
441 smt.insert(key_c, value_c);
442
443 let smt3 = smt.clone();
444 let raw_d = 0b_01010101_01010101_11111111_11111111_10110101_10101010_11111100_00000000_u64;
445 let key_d = RpoDigest::from([ZERO, ZERO, ONE, Felt::new(raw_d)]);
446 let value_d = [ONE, ZERO, ZERO, ZERO];
447 smt.insert(key_d, value_d);
448
449 // --- delete the last inserted value -------------------------------------
450 assert_eq!(smt.insert(key_d, [ZERO; 4]), value_d);
451 assert_eq!(smt, smt3);
452
453 assert_eq!(smt.insert(key_c, [ZERO; 4]), value_c);
454 assert_eq!(smt, smt2);
455
456 assert_eq!(smt.insert(key_b, [ZERO; 4]), value_b);
457 assert_eq!(smt, smt1);
458
459 assert_eq!(smt.insert(key_a, [ZERO; 4]), value_a);
460 assert_eq!(smt, smt0);
461}
462
463// BOTTOM TIER TESTS
464// ================================================================================================
465
466#[test]
467fn tsmt_bottom_tier() {
468 let mut smt = TieredSmt::default();
469 let mut store = MerkleStore::default();
470
471 // common prefix for the keys
472 let prefix = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
473
474 // --- insert the first value ---------------------------------------------
475 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(prefix)]);
476 let val_a = [ONE; WORD_SIZE];
477 smt.insert(key_a, val_a);
478
479 // --- insert the second value --------------------------------------------
480 // this key has the same 64-bit prefix and thus both values should end up in the same
481 // node at depth 64
482 let key_b = RpoDigest::from([ZERO, ONE, ONE, Felt::new(prefix)]);
483 let val_b = [Felt::new(2); WORD_SIZE];
484 smt.insert(key_b, val_b);
485
486 // --- build Merkle store with equivalent data ----------------------------
487 let index = NodeIndex::make(64, prefix);
488 // to build bottom leaf we sort by key starting with the least significant element, thus
489 // key_b is smaller than key_a.
490 let leaf_node = build_bottom_leaf_node(&[key_b, key_a], &[val_b, val_a]);
491 let mut tree_root = get_init_root();
492 tree_root = store.set_node(tree_root, index, leaf_node).unwrap().root;
493
494 // --- verify that data is consistent between store and tree --------------
495
496 assert_eq!(smt.root(), tree_root);
497
498 assert_eq!(smt.get_value(key_a), val_a);
499 assert_eq!(smt.get_value(key_b), val_b);
500
501 assert_eq!(smt.get_node(index).unwrap(), leaf_node);
502 let expected_path = store.get_path(tree_root, index).unwrap().path;
503 assert_eq!(smt.get_path(index).unwrap(), expected_path);
504
505 // make sure inner nodes match - the store contains more entries because it keeps track of
506 // all prior state - so, we don't check that the number of inner nodes is the same in both
507 let expected_nodes = get_non_empty_nodes(&store);
508 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
509 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
510
511 // make sure leaves are returned correctly
512 let mut leaves = smt.bottom_leaves();
513 assert_eq!(leaves.next(), Some((leaf_node, vec![(key_b, val_b), (key_a, val_a)])));
514 assert_eq!(leaves.next(), None);
515}
516
517#[test]
518fn tsmt_bottom_tier_two() {
519 let mut smt = TieredSmt::default();
520 let mut store = MerkleStore::default();
521
522 // --- insert the first value ---------------------------------------------
523 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
524 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
525 let val_a = [ONE; WORD_SIZE];
526 smt.insert(key_a, val_a);
527
528 // --- insert the second value --------------------------------------------
529 // the key for this value has the same 48-bit prefix as the key for the first value,
530 // thus, on insertions, both should end up in different nodes at depth 64
531 let raw_b = 0b_10101010_10101010_00011111_11111111_10010110_10010011_01100000_00000000_u64;
532 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
533 let val_b = [Felt::new(2); WORD_SIZE];
534 smt.insert(key_b, val_b);
535
536 // --- build Merkle store with equivalent data ----------------------------
537 let mut tree_root = get_init_root();
538 let index_a = NodeIndex::make(64, raw_a);
539 let leaf_node_a = build_bottom_leaf_node(&[key_a], &[val_a]);
540 tree_root = store.set_node(tree_root, index_a, leaf_node_a).unwrap().root;
541
542 let index_b = NodeIndex::make(64, raw_b);
543 let leaf_node_b = build_bottom_leaf_node(&[key_b], &[val_b]);
544 tree_root = store.set_node(tree_root, index_b, leaf_node_b).unwrap().root;
545
546 // --- verify that data is consistent between store and tree --------------
547
548 assert_eq!(smt.root(), tree_root);
549
550 assert_eq!(smt.get_value(key_a), val_a);
551 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
552 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
553 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
554
555 assert_eq!(smt.get_value(key_b), val_b);
556 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
557 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
558 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
559
560 // make sure inner nodes match - the store contains more entries because it keeps track of
561 // all prior state - so, we don't check that the number of inner nodes is the same in both
562 let expected_nodes = get_non_empty_nodes(&store);
563 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
564 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
565
566 // make sure leaves are returned correctly
567 let mut leaves = smt.bottom_leaves();
568 assert_eq!(leaves.next(), Some((leaf_node_b, vec![(key_b, val_b)])));
569 assert_eq!(leaves.next(), Some((leaf_node_a, vec![(key_a, val_a)])));
570 assert_eq!(leaves.next(), None);
571}
572
573// ERROR TESTS
574// ================================================================================================
575
576#[test]
577fn tsmt_node_not_available() {
578 let mut smt = TieredSmt::default();
579
580 let raw = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
581 let key = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
582 let value = [ONE; WORD_SIZE];
583
584 // build an index which is just below the inserted leaf node
585 let index = NodeIndex::make(17, raw >> 47);
586
587 // since we haven't inserted the node yet, we should be able to get node and path to this index
588 assert!(smt.get_node(index).is_ok());
589 assert!(smt.get_path(index).is_ok());
590
591 smt.insert(key, value);
592
593 // but once the node is inserted, everything under it should be unavailable
594 assert!(smt.get_node(index).is_err());
595 assert!(smt.get_path(index).is_err());
596
597 let index = NodeIndex::make(32, raw >> 32);
598 assert!(smt.get_node(index).is_err());
599 assert!(smt.get_path(index).is_err());
600
601 let index = NodeIndex::make(34, raw >> 30);
602 assert!(smt.get_node(index).is_err());
603 assert!(smt.get_path(index).is_err());
604
605 let index = NodeIndex::make(50, raw >> 14);
606 assert!(smt.get_node(index).is_err());
607 assert!(smt.get_path(index).is_err());
608
609 let index = NodeIndex::make(64, raw);
610 assert!(smt.get_node(index).is_err());
611 assert!(smt.get_path(index).is_err());
612}
613
614// HELPER FUNCTIONS
615// ================================================================================================
616
617fn get_init_root() -> RpoDigest {
618 EmptySubtreeRoots::empty_hashes(64)[0]
619}
620
621fn build_leaf_node(key: RpoDigest, value: Word, depth: u8) -> RpoDigest {
622 Rpo256::merge_in_domain(&[key, value.into()], depth.into())
623}
624
625fn build_bottom_leaf_node(keys: &[RpoDigest], values: &[Word]) -> RpoDigest {
626 assert_eq!(keys.len(), values.len());
627
628 let mut elements = Vec::with_capacity(keys.len());
629 for (key, val) in keys.iter().zip(values.iter()) {
630 elements.extend_from_slice(key.as_elements());
631 elements.extend_from_slice(val.as_slice());
632 }
633
634 Rpo256::hash_elements(&elements)
635}
636
637fn get_non_empty_nodes(store: &MerkleStore) -> Vec<InnerNodeInfo> {
638 store
639 .inner_nodes()
640 .filter(|node| !is_empty_subtree(&node.value))
641 .collect::<Vec<_>>()
642}
643
644fn is_empty_subtree(node: &RpoDigest) -> bool {
645 EmptySubtreeRoots::empty_hashes(255).contains(node)
646}