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#[test]
7fn tsmt_insert_one() {
8 let mut smt = TieredSmt::default();
9 let mut store = MerkleStore::default();
10
11 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
12 let key = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
13 let value = [ONE; WORD_SIZE];
14
15 // since the tree is empty, the first node will be inserted at depth 16 and the index will be
16 // 16 most significant bits of the key
17 let index = NodeIndex::make(16, raw >> 48);
18 let leaf_node = build_leaf_node(key, value, 16);
19 let tree_root = store.set_node(smt.root(), index, leaf_node).unwrap().root;
20
21 smt.insert(key, value);
22
23 assert_eq!(smt.root(), tree_root);
24
25 // make sure the value was inserted, and the node is at the expected index
26 assert_eq!(smt.get_value(key), value);
27 assert_eq!(smt.get_node(index).unwrap(), leaf_node);
28
29 // make sure the paths we get from the store and the tree match
30 let expected_path = store.get_path(tree_root, index).unwrap();
31 assert_eq!(smt.get_path(index).unwrap(), expected_path.path);
32
33 // make sure inner nodes match
34 let expected_nodes = get_non_empty_nodes(&store);
35 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
36 assert_eq!(actual_nodes.len(), expected_nodes.len());
37 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
38
39 // make sure leaves are returned correctly
40 let mut leaves = smt.upper_leaves();
41 assert_eq!(leaves.next(), Some((leaf_node, key, value)));
42 assert_eq!(leaves.next(), None);
43}
44
45#[test]
46fn tsmt_insert_two_16() {
47 let mut smt = TieredSmt::default();
48 let mut store = MerkleStore::default();
49
50 // --- insert the first value ---------------------------------------------
51 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
52 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
53 let val_a = [ONE; WORD_SIZE];
54 smt.insert(key_a, val_a);
55
56 // --- insert the second value --------------------------------------------
57 // the key for this value has the same 16-bit prefix as the key for the first value,
58 // thus, on insertions, both values should be pushed to depth 32 tier
59 let raw_b = 0b_10101010_10101010_10011111_11111111_10010110_10010011_11100000_00000000_u64;
60 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
61 let val_b = [Felt::new(2); WORD_SIZE];
62 smt.insert(key_b, val_b);
63
64 // --- build Merkle store with equivalent data ----------------------------
65 let mut tree_root = get_init_root();
66 let index_a = NodeIndex::make(32, raw_a >> 32);
67 let leaf_node_a = build_leaf_node(key_a, val_a, 32);
68 tree_root = store.set_node(tree_root, index_a, leaf_node_a).unwrap().root;
69
70 let index_b = NodeIndex::make(32, raw_b >> 32);
71 let leaf_node_b = build_leaf_node(key_b, val_b, 32);
72 tree_root = store.set_node(tree_root, index_b, leaf_node_b).unwrap().root;
73
74 // --- verify that data is consistent between store and tree --------------
75
76 assert_eq!(smt.root(), tree_root);
77
78 assert_eq!(smt.get_value(key_a), val_a);
79 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
80 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
81 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
82
83 assert_eq!(smt.get_value(key_b), val_b);
84 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
85 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
86 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
87
88 // make sure inner nodes match - the store contains more entries because it keeps track of
89 // all prior state - so, we don't check that the number of inner nodes is the same in both
90 let expected_nodes = get_non_empty_nodes(&store);
91 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
92 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
93
94 // make sure leaves are returned correctly
95 let mut leaves = smt.upper_leaves();
96 assert_eq!(leaves.next(), Some((leaf_node_a, key_a, val_a)));
97 assert_eq!(leaves.next(), Some((leaf_node_b, key_b, val_b)));
98 assert_eq!(leaves.next(), None);
99}
100
101#[test]
102fn tsmt_insert_two_32() {
103 let mut smt = TieredSmt::default();
104 let mut store = MerkleStore::default();
105
106 // --- insert the first value ---------------------------------------------
107 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
108 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
109 let val_a = [ONE; WORD_SIZE];
110 smt.insert(key_a, val_a);
111
112 // --- insert the second value --------------------------------------------
113 // the key for this value has the same 32-bit prefix as the key for the first value,
114 // thus, on insertions, both values should be pushed to depth 48 tier
115 let raw_b = 0b_10101010_10101010_00011111_11111111_00010110_10010011_11100000_00000000_u64;
116 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
117 let val_b = [Felt::new(2); WORD_SIZE];
118 smt.insert(key_b, val_b);
119
120 // --- build Merkle store with equivalent data ----------------------------
121 let mut tree_root = get_init_root();
122 let index_a = NodeIndex::make(48, raw_a >> 16);
123 let leaf_node_a = build_leaf_node(key_a, val_a, 48);
124 tree_root = store.set_node(tree_root, index_a, leaf_node_a).unwrap().root;
125
126 let index_b = NodeIndex::make(48, raw_b >> 16);
127 let leaf_node_b = build_leaf_node(key_b, val_b, 48);
128 tree_root = store.set_node(tree_root, index_b, leaf_node_b).unwrap().root;
129
130 // --- verify that data is consistent between store and tree --------------
131
132 assert_eq!(smt.root(), tree_root);
133
134 assert_eq!(smt.get_value(key_a), val_a);
135 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
136 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
137 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
138
139 assert_eq!(smt.get_value(key_b), val_b);
140 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
141 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
142 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
143
144 // make sure inner nodes match - the store contains more entries because it keeps track of
145 // all prior state - so, we don't check that the number of inner nodes is the same in both
146 let expected_nodes = get_non_empty_nodes(&store);
147 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
148 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
149}
150
151#[test]
152fn tsmt_insert_three() {
153 let mut smt = TieredSmt::default();
154 let mut store = MerkleStore::default();
155
156 // --- insert the first value ---------------------------------------------
157 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
158 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
159 let val_a = [ONE; WORD_SIZE];
160 smt.insert(key_a, val_a);
161
162 // --- insert the second value --------------------------------------------
163 // the key for this value has the same 16-bit prefix as the key for the first value,
164 // thus, on insertions, both values should be pushed to depth 32 tier
165 let raw_b = 0b_10101010_10101010_10011111_11111111_10010110_10010011_11100000_00000000_u64;
166 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
167 let val_b = [Felt::new(2); WORD_SIZE];
168 smt.insert(key_b, val_b);
169
170 // --- insert the third value ---------------------------------------------
171 // the key for this value has the same 16-bit prefix as the keys for the first two,
172 // values; thus, on insertions, it will be inserted into depth 32 tier, but will not
173 // affect locations of the other two values
174 let raw_c = 0b_10101010_10101010_11011111_11111111_10010110_10010011_11100000_00000000_u64;
175 let key_c = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_c)]);
176 let val_c = [Felt::new(3); WORD_SIZE];
177 smt.insert(key_c, val_c);
178
179 // --- build Merkle store with equivalent data ----------------------------
180 let mut tree_root = get_init_root();
181 let index_a = NodeIndex::make(32, raw_a >> 32);
182 let leaf_node_a = build_leaf_node(key_a, val_a, 32);
183 tree_root = store.set_node(tree_root, index_a, leaf_node_a).unwrap().root;
184
185 let index_b = NodeIndex::make(32, raw_b >> 32);
186 let leaf_node_b = build_leaf_node(key_b, val_b, 32);
187 tree_root = store.set_node(tree_root, index_b, leaf_node_b).unwrap().root;
188
189 let index_c = NodeIndex::make(32, raw_c >> 32);
190 let leaf_node_c = build_leaf_node(key_c, val_c, 32);
191 tree_root = store.set_node(tree_root, index_c, leaf_node_c).unwrap().root;
192
193 // --- verify that data is consistent between store and tree --------------
194
195 assert_eq!(smt.root(), tree_root);
196
197 assert_eq!(smt.get_value(key_a), val_a);
198 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
199 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
200 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
201
202 assert_eq!(smt.get_value(key_b), val_b);
203 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
204 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
205 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
206
207 assert_eq!(smt.get_value(key_c), val_c);
208 assert_eq!(smt.get_node(index_c).unwrap(), leaf_node_c);
209 let expected_path = store.get_path(tree_root, index_c).unwrap().path;
210 assert_eq!(smt.get_path(index_c).unwrap(), expected_path);
211
212 // make sure inner nodes match - the store contains more entries because it keeps track of
213 // all prior state - so, we don't check that the number of inner nodes is the same in both
214 let expected_nodes = get_non_empty_nodes(&store);
215 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
216 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
217}
218
219#[test]
220fn tsmt_update() {
221 let mut smt = TieredSmt::default();
222 let mut store = MerkleStore::default();
223
224 // --- insert a value into the tree ---------------------------------------
225 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
226 let key = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
227 let value_a = [ONE; WORD_SIZE];
228 smt.insert(key, value_a);
229
230 // --- update the value ---------------------------------------------------
231 let value_b = [Felt::new(2); WORD_SIZE];
232 smt.insert(key, value_b);
233
234 // --- verify consistency -------------------------------------------------
235 let mut tree_root = get_init_root();
236 let index = NodeIndex::make(16, raw >> 48);
237 let leaf_node = build_leaf_node(key, value_b, 16);
238 tree_root = store.set_node(tree_root, index, leaf_node).unwrap().root;
239
240 assert_eq!(smt.root(), tree_root);
241
242 assert_eq!(smt.get_value(key), value_b);
243 assert_eq!(smt.get_node(index).unwrap(), leaf_node);
244 let expected_path = store.get_path(tree_root, index).unwrap().path;
245 assert_eq!(smt.get_path(index).unwrap(), expected_path);
246
247 // make sure inner nodes match - the store contains more entries because it keeps track of
248 // all prior state - so, we don't check that the number of inner nodes is the same in both
249 let expected_nodes = get_non_empty_nodes(&store);
250 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
251 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
252}
253
254// BOTTOM TIER TESTS
255// ================================================================================================
256
257#[test]
258fn tsmt_bottom_tier() {
259 let mut smt = TieredSmt::default();
260 let mut store = MerkleStore::default();
261
262 // common prefix for the keys
263 let prefix = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
264
265 // --- insert the first value ---------------------------------------------
266 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(prefix)]);
267 let val_a = [ONE; WORD_SIZE];
268 smt.insert(key_a, val_a);
269
270 // --- insert the second value --------------------------------------------
271 // this key has the same 64-bit prefix and thus both values should end up in the same
272 // node at depth 64
273 let key_b = RpoDigest::from([ZERO, ONE, ONE, Felt::new(prefix)]);
274 let val_b = [Felt::new(2); WORD_SIZE];
275 smt.insert(key_b, val_b);
276
277 // --- build Merkle store with equivalent data ----------------------------
278 let index = NodeIndex::make(64, prefix);
279 // to build bottom leaf we sort by key starting with the least significant element, thus
280 // key_b is smaller than key_a.
281 let leaf_node = build_bottom_leaf_node(&[key_b, key_a], &[val_b, val_a]);
282 let mut tree_root = get_init_root();
283 tree_root = store.set_node(tree_root, index, leaf_node).unwrap().root;
284
285 // --- verify that data is consistent between store and tree --------------
286
287 assert_eq!(smt.root(), tree_root);
288
289 assert_eq!(smt.get_value(key_a), val_a);
290 assert_eq!(smt.get_value(key_b), val_b);
291
292 assert_eq!(smt.get_node(index).unwrap(), leaf_node);
293 let expected_path = store.get_path(tree_root, index).unwrap().path;
294 assert_eq!(smt.get_path(index).unwrap(), expected_path);
295
296 // make sure inner nodes match - the store contains more entries because it keeps track of
297 // all prior state - so, we don't check that the number of inner nodes is the same in both
298 let expected_nodes = get_non_empty_nodes(&store);
299 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
300 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
301
302 // make sure leaves are returned correctly
303 let mut leaves = smt.bottom_leaves();
304 assert_eq!(leaves.next(), Some((leaf_node, vec![(key_b, val_b), (key_a, val_a)])));
305 assert_eq!(leaves.next(), None);
306}
307
308#[test]
309fn tsmt_bottom_tier_two() {
310 let mut smt = TieredSmt::default();
311 let mut store = MerkleStore::default();
312
313 // --- insert the first value ---------------------------------------------
314 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
315 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
316 let val_a = [ONE; WORD_SIZE];
317 smt.insert(key_a, val_a);
318
319 // --- insert the second value --------------------------------------------
320 // the key for this value has the same 48-bit prefix as the key for the first value,
321 // thus, on insertions, both should end up in different nodes at depth 64
322 let raw_b = 0b_10101010_10101010_00011111_11111111_10010110_10010011_01100000_00000000_u64;
323 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
324 let val_b = [Felt::new(2); WORD_SIZE];
325 smt.insert(key_b, val_b);
326
327 // --- build Merkle store with equivalent data ----------------------------
328 let mut tree_root = get_init_root();
329 let index_a = NodeIndex::make(64, raw_a);
330 let leaf_node_a = build_bottom_leaf_node(&[key_a], &[val_a]);
331 tree_root = store.set_node(tree_root, index_a, leaf_node_a).unwrap().root;
332
333 let index_b = NodeIndex::make(64, raw_b);
334 let leaf_node_b = build_bottom_leaf_node(&[key_b], &[val_b]);
335 tree_root = store.set_node(tree_root, index_b, leaf_node_b).unwrap().root;
336
337 // --- verify that data is consistent between store and tree --------------
338
339 assert_eq!(smt.root(), tree_root);
340
341 assert_eq!(smt.get_value(key_a), val_a);
342 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
343 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
344 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
345
346 assert_eq!(smt.get_value(key_b), val_b);
347 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
348 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
349 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
350
351 // make sure inner nodes match - the store contains more entries because it keeps track of
352 // all prior state - so, we don't check that the number of inner nodes is the same in both
353 let expected_nodes = get_non_empty_nodes(&store);
354 let actual_nodes = smt.inner_nodes().collect::<Vec<_>>();
355 actual_nodes.iter().for_each(|node| assert!(expected_nodes.contains(node)));
356
357 // make sure leaves are returned correctly
358 let mut leaves = smt.bottom_leaves();
359 assert_eq!(leaves.next(), Some((leaf_node_b, vec![(key_b, val_b)])));
360 assert_eq!(leaves.next(), Some((leaf_node_a, vec![(key_a, val_a)])));
361 assert_eq!(leaves.next(), None);
362}
363
364// ERROR TESTS
365// ================================================================================================
366
367#[test]
368fn tsmt_node_not_available() {
369 let mut smt = TieredSmt::default();
370
371 let raw = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
372 let key = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
373 let value = [ONE; WORD_SIZE];
374
375 // build an index which is just below the inserted leaf node
376 let index = NodeIndex::make(17, raw >> 47);
377
378 // since we haven't inserted the node yet, we should be able to get node and path to this index
379 assert!(smt.get_node(index).is_ok());
380 assert!(smt.get_path(index).is_ok());
381
382 smt.insert(key, value);
383
384 // but once the node is inserted, everything under it should be unavailable
385 assert!(smt.get_node(index).is_err());
386 assert!(smt.get_path(index).is_err());
387
388 let index = NodeIndex::make(32, raw >> 32);
389 assert!(smt.get_node(index).is_err());
390 assert!(smt.get_path(index).is_err());
391
392 let index = NodeIndex::make(34, raw >> 30);
393 assert!(smt.get_node(index).is_err());
394 assert!(smt.get_path(index).is_err());
395
396 let index = NodeIndex::make(50, raw >> 14);
397 assert!(smt.get_node(index).is_err());
398 assert!(smt.get_path(index).is_err());
399
400 let index = NodeIndex::make(64, raw);
401 assert!(smt.get_node(index).is_err());
402 assert!(smt.get_path(index).is_err());
403}
404
405// HELPER FUNCTIONS
406// ================================================================================================
407
408fn get_init_root() -> RpoDigest {
409 EmptySubtreeRoots::empty_hashes(64)[0]
410}
411
412fn build_leaf_node(key: RpoDigest, value: Word, depth: u8) -> RpoDigest {
413 Rpo256::merge_in_domain(&[key, value.into()], depth.into())
414}
415
416fn build_bottom_leaf_node(keys: &[RpoDigest], values: &[Word]) -> RpoDigest {
417 assert_eq!(keys.len(), values.len());
418
419 let mut elements = Vec::with_capacity(keys.len());
420 for (key, val) in keys.iter().zip(values.iter()) {
421 elements.extend_from_slice(key.as_elements());
422 elements.extend_from_slice(val.as_slice());
423 }
424
425 Rpo256::hash_elements(&elements)
426}
427
428fn get_non_empty_nodes(store: &MerkleStore) -> Vec<InnerNodeInfo> {
429 store
430 .inner_nodes()
431 .filter(|node| !is_empty_subtree(&node.value))
432 .collect::<Vec<_>>()
433}
434
435fn is_empty_subtree(node: &RpoDigest) -> bool {
436 EmptySubtreeRoots::empty_hashes(255).contains(node)
437}