miden-crypto/src/merkle/tiered_smt/tests.rs
src/merkle/tiered_smt/tests.rsRaw
1use super::{
2 super::{
3 super::{ONE, ZERO},
4 Felt, MerkleStore, WORD_SIZE,
5 },
6 get_remaining_path, EmptySubtreeRoots, NodeIndex, Rpo256, RpoDigest, TieredSmt, Vec, Word,
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().into(), index, leaf_node.into()).unwrap().root;
23
24 smt.insert(key, value);
25
26 assert_eq!(smt.root(), tree_root.into());
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
37#[test]
38fn tsmt_insert_two_16() {
39 let mut smt = TieredSmt::default();
40 let mut store = MerkleStore::default();
41
42 // --- insert the first value ---------------------------------------------
43 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
44 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
45 let val_a = [ONE; WORD_SIZE];
46 smt.insert(key_a, val_a);
47
48 // --- insert the second value --------------------------------------------
49 // the key for this value has the same 16-bit prefix as the key for the first value,
50 // thus, on insertions, both values should be pushed to depth 32 tier
51 let raw_b = 0b_10101010_10101010_10011111_11111111_10010110_10010011_11100000_00000000_u64;
52 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
53 let val_b = [Felt::new(2); WORD_SIZE];
54 smt.insert(key_b, val_b);
55
56 // --- build Merkle store with equivalent data ----------------------------
57 let mut tree_root = get_init_root();
58 let index_a = NodeIndex::make(32, raw_a >> 32);
59 let leaf_node_a = build_leaf_node(key_a, val_a, 32);
60 tree_root = store.set_node(tree_root, index_a, leaf_node_a.into()).unwrap().root;
61
62 let index_b = NodeIndex::make(32, raw_b >> 32);
63 let leaf_node_b = build_leaf_node(key_b, val_b, 32);
64 tree_root = store.set_node(tree_root, index_b, leaf_node_b.into()).unwrap().root;
65
66 // --- verify that data is consistent between store and tree --------------
67
68 assert_eq!(smt.root(), tree_root.into());
69
70 assert_eq!(smt.get_value(key_a), val_a);
71 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
72 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
73 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
74
75 assert_eq!(smt.get_value(key_b), val_b);
76 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
77 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
78 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
79}
80
81#[test]
82fn tsmt_insert_two_32() {
83 let mut smt = TieredSmt::default();
84 let mut store = MerkleStore::default();
85
86 // --- insert the first value ---------------------------------------------
87 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
88 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
89 let val_a = [ONE; WORD_SIZE];
90 smt.insert(key_a, val_a);
91
92 // --- insert the second value --------------------------------------------
93 // the key for this value has the same 32-bit prefix as the key for the first value,
94 // thus, on insertions, both values should be pushed to depth 48 tier
95 let raw_b = 0b_10101010_10101010_00011111_11111111_00010110_10010011_11100000_00000000_u64;
96 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
97 let val_b = [Felt::new(2); WORD_SIZE];
98 smt.insert(key_b, val_b);
99
100 // --- build Merkle store with equivalent data ----------------------------
101 let mut tree_root = get_init_root();
102 let index_a = NodeIndex::make(48, raw_a >> 16);
103 let leaf_node_a = build_leaf_node(key_a, val_a, 48);
104 tree_root = store.set_node(tree_root, index_a, leaf_node_a.into()).unwrap().root;
105
106 let index_b = NodeIndex::make(48, raw_b >> 16);
107 let leaf_node_b = build_leaf_node(key_b, val_b, 48);
108 tree_root = store.set_node(tree_root, index_b, leaf_node_b.into()).unwrap().root;
109
110 // --- verify that data is consistent between store and tree --------------
111
112 assert_eq!(smt.root(), tree_root.into());
113
114 assert_eq!(smt.get_value(key_a), val_a);
115 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
116 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
117 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
118
119 assert_eq!(smt.get_value(key_b), val_b);
120 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
121 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
122 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
123}
124
125#[test]
126fn tsmt_insert_three() {
127 let mut smt = TieredSmt::default();
128 let mut store = MerkleStore::default();
129
130 // --- insert the first value ---------------------------------------------
131 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
132 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
133 let val_a = [ONE; WORD_SIZE];
134 smt.insert(key_a, val_a);
135
136 // --- insert the second value --------------------------------------------
137 // the key for this value has the same 16-bit prefix as the key for the first value,
138 // thus, on insertions, both values should be pushed to depth 32 tier
139 let raw_b = 0b_10101010_10101010_10011111_11111111_10010110_10010011_11100000_00000000_u64;
140 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
141 let val_b = [Felt::new(2); WORD_SIZE];
142 smt.insert(key_b, val_b);
143
144 // --- insert the third value ---------------------------------------------
145 // the key for this value has the same 16-bit prefix as the keys for the first two,
146 // values; thus, on insertions, it will be inserted into depth 32 tier, but will not
147 // affect locations of the other two values
148 let raw_c = 0b_10101010_10101010_11011111_11111111_10010110_10010011_11100000_00000000_u64;
149 let key_c = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_c)]);
150 let val_c = [Felt::new(3); WORD_SIZE];
151 smt.insert(key_c, val_c);
152
153 // --- build Merkle store with equivalent data ----------------------------
154 let mut tree_root = get_init_root();
155 let index_a = NodeIndex::make(32, raw_a >> 32);
156 let leaf_node_a = build_leaf_node(key_a, val_a, 32);
157 tree_root = store.set_node(tree_root, index_a, leaf_node_a.into()).unwrap().root;
158
159 let index_b = NodeIndex::make(32, raw_b >> 32);
160 let leaf_node_b = build_leaf_node(key_b, val_b, 32);
161 tree_root = store.set_node(tree_root, index_b, leaf_node_b.into()).unwrap().root;
162
163 let index_c = NodeIndex::make(32, raw_c >> 32);
164 let leaf_node_c = build_leaf_node(key_c, val_c, 32);
165 tree_root = store.set_node(tree_root, index_c, leaf_node_c.into()).unwrap().root;
166
167 // --- verify that data is consistent between store and tree --------------
168
169 assert_eq!(smt.root(), tree_root.into());
170
171 assert_eq!(smt.get_value(key_a), val_a);
172 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
173 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
174 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
175
176 assert_eq!(smt.get_value(key_b), val_b);
177 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
178 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
179 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
180
181 assert_eq!(smt.get_value(key_c), val_c);
182 assert_eq!(smt.get_node(index_c).unwrap(), leaf_node_c);
183 let expected_path = store.get_path(tree_root, index_c).unwrap().path;
184 assert_eq!(smt.get_path(index_c).unwrap(), expected_path);
185}
186
187#[test]
188fn tsmt_update() {
189 let mut smt = TieredSmt::default();
190 let mut store = MerkleStore::default();
191
192 // --- insert a value into the tree ---------------------------------------
193 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
194 let key = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
195 let value_a = [ONE; WORD_SIZE];
196 smt.insert(key, value_a);
197
198 // --- update the value ---------------------------------------------------
199 let value_b = [Felt::new(2); WORD_SIZE];
200 smt.insert(key, value_b);
201
202 // --- verify consistency -------------------------------------------------
203 let mut tree_root = get_init_root();
204 let index = NodeIndex::make(16, raw >> 48);
205 let leaf_node = build_leaf_node(key, value_b, 16);
206 tree_root = store.set_node(tree_root, index, leaf_node.into()).unwrap().root;
207
208 assert_eq!(smt.root(), tree_root.into());
209
210 assert_eq!(smt.get_value(key), value_b);
211 assert_eq!(smt.get_node(index).unwrap(), leaf_node);
212 let expected_path = store.get_path(tree_root, index).unwrap().path;
213 assert_eq!(smt.get_path(index).unwrap(), expected_path);
214}
215
216// BOTTOM TIER TESTS
217// ================================================================================================
218
219#[test]
220fn tsmt_bottom_tier() {
221 let mut smt = TieredSmt::default();
222 let mut store = MerkleStore::default();
223
224 // common prefix for the keys
225 let prefix = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
226
227 // --- insert the first value ---------------------------------------------
228 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(prefix)]);
229 let val_a = [ONE; WORD_SIZE];
230 smt.insert(key_a, val_a);
231
232 // --- insert the second value --------------------------------------------
233 // this key has the same 64-bit prefix and thus both values should end up in the same
234 // node at depth 64
235 let key_b = RpoDigest::from([ZERO, ONE, ONE, Felt::new(prefix)]);
236 let val_b = [Felt::new(2); WORD_SIZE];
237 smt.insert(key_b, val_b);
238
239 // --- build Merkle store with equivalent data ----------------------------
240 let index = NodeIndex::make(64, prefix);
241 // to build bottom leaf we sort by key starting with the least significant element, thus
242 // key_b is smaller than key_a.
243 let leaf_node = build_bottom_leaf_node(&[key_b, key_a], &[val_b, val_a]);
244 let mut tree_root = get_init_root();
245 tree_root = store.set_node(tree_root, index, leaf_node.into()).unwrap().root;
246
247 // --- verify that data is consistent between store and tree --------------
248
249 assert_eq!(smt.root(), tree_root.into());
250
251 assert_eq!(smt.get_value(key_a), val_a);
252 assert_eq!(smt.get_value(key_b), val_b);
253
254 assert_eq!(smt.get_node(index).unwrap(), leaf_node);
255 let expected_path = store.get_path(tree_root, index).unwrap().path;
256 assert_eq!(smt.get_path(index).unwrap(), expected_path);
257}
258
259#[test]
260fn tsmt_bottom_tier_two() {
261 let mut smt = TieredSmt::default();
262 let mut store = MerkleStore::default();
263
264 // --- insert the first value ---------------------------------------------
265 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
266 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
267 let val_a = [ONE; WORD_SIZE];
268 smt.insert(key_a, val_a);
269
270 // --- insert the second value --------------------------------------------
271 // the key for this value has the same 48-bit prefix as the key for the first value,
272 // thus, on insertions, both should end up in different nodes at depth 64
273 let raw_b = 0b_10101010_10101010_00011111_11111111_10010110_10010011_01100000_00000000_u64;
274 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
275 let val_b = [Felt::new(2); WORD_SIZE];
276 smt.insert(key_b, val_b);
277
278 // --- build Merkle store with equivalent data ----------------------------
279 let mut tree_root = get_init_root();
280 let index_a = NodeIndex::make(64, raw_a);
281 let leaf_node_a = build_bottom_leaf_node(&[key_a], &[val_a]);
282 tree_root = store.set_node(tree_root, index_a, leaf_node_a.into()).unwrap().root;
283
284 let index_b = NodeIndex::make(64, raw_b);
285 let leaf_node_b = build_bottom_leaf_node(&[key_b], &[val_b]);
286 tree_root = store.set_node(tree_root, index_b, leaf_node_b.into()).unwrap().root;
287
288 // --- verify that data is consistent between store and tree --------------
289
290 assert_eq!(smt.root(), tree_root.into());
291
292 assert_eq!(smt.get_value(key_a), val_a);
293 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
294 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
295 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
296
297 assert_eq!(smt.get_value(key_b), val_b);
298 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
299 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
300 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
301}
302
303// ERROR TESTS
304// ================================================================================================
305
306#[test]
307fn tsmt_node_not_available() {
308 let mut smt = TieredSmt::default();
309
310 let raw = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
311 let key = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
312 let value = [ONE; WORD_SIZE];
313
314 // build an index which is just below the inserted leaf node
315 let index = NodeIndex::make(17, raw >> 47);
316
317 // since we haven't inserted the node yet, we should be able to get node and path to this index
318 assert!(smt.get_node(index).is_ok());
319 assert!(smt.get_path(index).is_ok());
320
321 smt.insert(key, value);
322
323 // but once the node is inserted, everything under it should be unavailable
324 assert!(smt.get_node(index).is_err());
325 assert!(smt.get_path(index).is_err());
326
327 let index = NodeIndex::make(32, raw >> 32);
328 assert!(smt.get_node(index).is_err());
329 assert!(smt.get_path(index).is_err());
330
331 let index = NodeIndex::make(34, raw >> 30);
332 assert!(smt.get_node(index).is_err());
333 assert!(smt.get_path(index).is_err());
334
335 let index = NodeIndex::make(50, raw >> 14);
336 assert!(smt.get_node(index).is_err());
337 assert!(smt.get_path(index).is_err());
338
339 let index = NodeIndex::make(64, raw);
340 assert!(smt.get_node(index).is_err());
341 assert!(smt.get_path(index).is_err());
342}
343
344// HELPER FUNCTIONS
345// ================================================================================================
346
347fn get_init_root() -> Word {
348 EmptySubtreeRoots::empty_hashes(64)[0].into()
349}
350
351fn build_leaf_node(key: RpoDigest, value: Word, depth: u8) -> RpoDigest {
352 let remaining_path = get_remaining_path(key, depth as u32);
353 Rpo256::merge_in_domain(&[remaining_path, value.into()], depth.into())
354}
355
356fn build_bottom_leaf_node(keys: &[RpoDigest], values: &[Word]) -> RpoDigest {
357 assert_eq!(keys.len(), values.len());
358
359 let mut elements = Vec::with_capacity(keys.len());
360 for (key, val) in keys.iter().zip(values.iter()) {
361 let mut key = Word::from(key);
362 key[3] = ZERO;
363 elements.extend_from_slice(&key);
364 elements.extend_from_slice(val);
365 }
366
367 Rpo256::hash_elements(&elements)
368}