miden-crypto/src/merkle/smt/full/tests.rs
src/merkle/smt/full/tests.rsRaw
1use super::*;
2use crate::{
3 merkle::{EmptySubtreeRoots, MerkleStore},
4 ONE, WORD_SIZE,
5};
6
7/// This test checks that inserting twice at the same key functions as expected. The test covers
8/// only the case where the key is alone in its leaf
9#[test]
10fn test_smt_insert_at_same_key() {
11 let mut smt = Smt::default();
12 let mut store: MerkleStore = MerkleStore::default();
13
14 assert_eq!(smt.root(), *EmptySubtreeRoots::entry(SMT_DEPTH, 0));
15
16 let key_1: RpoDigest = {
17 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
18
19 RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)])
20 };
21 let key_1_index: NodeIndex = LeafIndex::<SMT_DEPTH>::from(key_1).into();
22
23 let value_1 = [ONE; WORD_SIZE];
24 let value_2 = [ONE + ONE; WORD_SIZE];
25
26 // Insert value 1 and ensure root is as expected
27 {
28 let leaf_node = build_single_leaf_node(key_1, value_1);
29 let tree_root = store.set_node(smt.root(), key_1_index, leaf_node).unwrap().root;
30
31 let old_value_1 = smt.insert(key_1, value_1);
32 assert_eq!(old_value_1, EMPTY_WORD);
33
34 assert_eq!(smt.root(), tree_root);
35 }
36
37 // Insert value 2 and ensure root is as expected
38 {
39 let leaf_node = build_single_leaf_node(key_1, value_2);
40 let tree_root = store.set_node(smt.root(), key_1_index, leaf_node).unwrap().root;
41
42 let old_value_2 = smt.insert(key_1, value_2);
43 assert_eq!(old_value_2, value_1);
44
45 assert_eq!(smt.root(), tree_root);
46 }
47}
48
49/// This test checks that inserting twice at the same key functions as expected. The test covers
50/// only the case where the leaf type is `SmtLeaf::Multiple`
51#[test]
52fn test_smt_insert_at_same_key_2() {
53 // The most significant u64 used for both keys (to ensure they map to the same leaf)
54 let key_msb: u64 = 42;
55
56 let key_already_present: RpoDigest =
57 RpoDigest::from([2_u64.into(), 2_u64.into(), 2_u64.into(), Felt::new(key_msb)]);
58 let key_already_present_index: NodeIndex =
59 LeafIndex::<SMT_DEPTH>::from(key_already_present).into();
60 let value_already_present = [ONE + ONE + ONE; WORD_SIZE];
61
62 let mut smt =
63 Smt::with_entries(core::iter::once((key_already_present, value_already_present))).unwrap();
64 let mut store: MerkleStore = {
65 let mut store = MerkleStore::default();
66
67 let leaf_node = build_single_leaf_node(key_already_present, value_already_present);
68 store
69 .set_node(*EmptySubtreeRoots::entry(SMT_DEPTH, 0), key_already_present_index, leaf_node)
70 .unwrap();
71 store
72 };
73
74 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, Felt::new(key_msb)]);
75 let key_1_index: NodeIndex = LeafIndex::<SMT_DEPTH>::from(key_1).into();
76
77 assert_eq!(key_1_index, key_already_present_index);
78
79 let value_1 = [ONE; WORD_SIZE];
80 let value_2 = [ONE + ONE; WORD_SIZE];
81
82 // Insert value 1 and ensure root is as expected
83 {
84 // Note: key_1 comes first because it is smaller
85 let leaf_node = build_multiple_leaf_node(&[
86 (key_1, value_1),
87 (key_already_present, value_already_present),
88 ]);
89 let tree_root = store.set_node(smt.root(), key_1_index, leaf_node).unwrap().root;
90
91 let old_value_1 = smt.insert(key_1, value_1);
92 assert_eq!(old_value_1, EMPTY_WORD);
93
94 assert_eq!(smt.root(), tree_root);
95 }
96
97 // Insert value 2 and ensure root is as expected
98 {
99 let leaf_node = build_multiple_leaf_node(&[
100 (key_1, value_2),
101 (key_already_present, value_already_present),
102 ]);
103 let tree_root = store.set_node(smt.root(), key_1_index, leaf_node).unwrap().root;
104
105 let old_value_2 = smt.insert(key_1, value_2);
106 assert_eq!(old_value_2, value_1);
107
108 assert_eq!(smt.root(), tree_root);
109 }
110}
111
112/// This test ensures that the root of the tree is as expected when we add 3 items at 3 different
113/// keys. This also tests that the merkle paths produced are as expected.
114#[test]
115fn test_smt_insert_multiple_values() {
116 let mut smt = Smt::default();
117 let mut store: MerkleStore = MerkleStore::default();
118
119 assert_eq!(smt.root(), *EmptySubtreeRoots::entry(SMT_DEPTH, 0));
120
121 let key_1: RpoDigest = {
122 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
123
124 RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)])
125 };
126
127 let key_2: RpoDigest = {
128 let raw = 0b_11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111_u64;
129
130 RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)])
131 };
132
133 let key_3: RpoDigest = {
134 let raw = 0b_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000_u64;
135
136 RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)])
137 };
138
139 let value_1 = [ONE; WORD_SIZE];
140 let value_2 = [ONE + ONE; WORD_SIZE];
141 let value_3 = [ONE + ONE + ONE; WORD_SIZE];
142
143 let key_values = [(key_1, value_1), (key_2, value_2), (key_3, value_3)];
144
145 for (key, value) in key_values {
146 let key_index: NodeIndex = LeafIndex::<SMT_DEPTH>::from(key).into();
147
148 let leaf_node = build_single_leaf_node(key, value);
149 let tree_root = store.set_node(smt.root(), key_index, leaf_node).unwrap().root;
150
151 let old_value = smt.insert(key, value);
152 assert_eq!(old_value, EMPTY_WORD);
153
154 assert_eq!(smt.root(), tree_root);
155
156 let expected_path = store.get_path(tree_root, key_index).unwrap();
157 assert_eq!(smt.open(&key).0, expected_path.path);
158 }
159}
160
161/// This tests that inserting the empty value does indeed remove the key-value contained at the
162/// leaf. We insert & remove 3 values at the same leaf to ensure that all cases are covered (empty,
163/// single, multiple).
164#[test]
165fn test_smt_removal() {
166 let mut smt = Smt::default();
167
168 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
169
170 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
171 let key_2: RpoDigest =
172 RpoDigest::from([2_u64.into(), 2_u64.into(), 2_u64.into(), Felt::new(raw)]);
173 let key_3: RpoDigest =
174 RpoDigest::from([3_u64.into(), 3_u64.into(), 3_u64.into(), Felt::new(raw)]);
175
176 let value_1 = [ONE; WORD_SIZE];
177 let value_2 = [2_u64.into(); WORD_SIZE];
178 let value_3: [Felt; 4] = [3_u64.into(); WORD_SIZE];
179
180 // insert key-value 1
181 {
182 let old_value_1 = smt.insert(key_1, value_1);
183 assert_eq!(old_value_1, EMPTY_WORD);
184
185 assert_eq!(smt.get_leaf(&key_1), SmtLeaf::Single((key_1, value_1)));
186 }
187
188 // insert key-value 2
189 {
190 let old_value_2 = smt.insert(key_2, value_2);
191 assert_eq!(old_value_2, EMPTY_WORD);
192
193 assert_eq!(
194 smt.get_leaf(&key_2),
195 SmtLeaf::Multiple(vec![(key_1, value_1), (key_2, value_2)])
196 );
197 }
198
199 // insert key-value 3
200 {
201 let old_value_3 = smt.insert(key_3, value_3);
202 assert_eq!(old_value_3, EMPTY_WORD);
203
204 assert_eq!(
205 smt.get_leaf(&key_3),
206 SmtLeaf::Multiple(vec![(key_1, value_1), (key_2, value_2), (key_3, value_3)])
207 );
208 }
209
210 // remove key 3
211 {
212 let old_value_3 = smt.insert(key_3, EMPTY_WORD);
213 assert_eq!(old_value_3, value_3);
214
215 assert_eq!(
216 smt.get_leaf(&key_3),
217 SmtLeaf::Multiple(vec![(key_1, value_1), (key_2, value_2)])
218 );
219 }
220
221 // remove key 2
222 {
223 let old_value_2 = smt.insert(key_2, EMPTY_WORD);
224 assert_eq!(old_value_2, value_2);
225
226 assert_eq!(smt.get_leaf(&key_2), SmtLeaf::Single((key_1, value_1)));
227 }
228
229 // remove key 1
230 {
231 let old_value_1 = smt.insert(key_1, EMPTY_WORD);
232 assert_eq!(old_value_1, value_1);
233
234 assert_eq!(smt.get_leaf(&key_1), SmtLeaf::Empty);
235 }
236}
237
238/// Tests that 2 key-value pairs stored in the same leaf have the same path
239#[test]
240fn test_smt_path_to_keys_in_same_leaf_are_equal() {
241 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
242
243 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
244 let key_2: RpoDigest =
245 RpoDigest::from([2_u64.into(), 2_u64.into(), 2_u64.into(), Felt::new(raw)]);
246
247 let value_1 = [ONE; WORD_SIZE];
248 let value_2 = [2_u64.into(); WORD_SIZE];
249
250 let smt = Smt::with_entries([(key_1, value_1), (key_2, value_2)]).unwrap();
251
252 assert_eq!(smt.open(&key_1), smt.open(&key_2));
253}
254
255/// Tests that an empty leaf hashes to the empty word
256#[test]
257fn test_empty_leaf_hash() {
258 let smt = Smt::default();
259
260 let leaf = smt.get_leaf(&RpoDigest::default());
261 assert_eq!(leaf.hash(), EMPTY_WORD.into());
262}
263
264/// Tests that `get_value()` works as expected
265#[test]
266fn test_smt_get_value() {
267 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, ONE]);
268 let key_2: RpoDigest =
269 RpoDigest::from([2_u64.into(), 2_u64.into(), 2_u64.into(), 2_u64.into()]);
270
271 let value_1 = [ONE; WORD_SIZE];
272 let value_2 = [2_u64.into(); WORD_SIZE];
273
274 let smt = Smt::with_entries([(key_1, value_1), (key_2, value_2)]).unwrap();
275
276 let returned_value_1 = smt.get_value(&key_1);
277 let returned_value_2 = smt.get_value(&key_2);
278
279 assert_eq!(value_1, returned_value_1);
280 assert_eq!(value_2, returned_value_2);
281
282 // Check that a key with no inserted value returns the empty word
283 let key_no_value =
284 RpoDigest::from([42_u64.into(), 42_u64.into(), 42_u64.into(), 42_u64.into()]);
285
286 assert_eq!(EMPTY_WORD, smt.get_value(&key_no_value));
287}
288
289/// Tests that `entries()` works as expected
290#[test]
291fn test_smt_entries() {
292 let key_1: RpoDigest = RpoDigest::from([ONE, ONE, ONE, ONE]);
293 let key_2: RpoDigest =
294 RpoDigest::from([2_u64.into(), 2_u64.into(), 2_u64.into(), 2_u64.into()]);
295
296 let value_1 = [ONE; WORD_SIZE];
297 let value_2 = [2_u64.into(); WORD_SIZE];
298
299 let smt = Smt::with_entries([(key_1, value_1), (key_2, value_2)]).unwrap();
300
301 let mut entries = smt.entries();
302
303 // Note: for simplicity, we assume the order `(k1,v1), (k2,v2)`. If a new implementation
304 // switches the order, it is OK to modify the order here as well.
305 assert_eq!(&(key_1, value_1), entries.next().unwrap());
306 assert_eq!(&(key_2, value_2), entries.next().unwrap());
307 assert!(entries.next().is_none());
308}
309// HELPERS
310// --------------------------------------------------------------------------------------------
311
312fn build_single_leaf_node(key: RpoDigest, value: Word) -> RpoDigest {
313 SmtLeaf::Single((key, value)).hash()
314}
315
316fn build_multiple_leaf_node(kv_pairs: &[(RpoDigest, Word)]) -> RpoDigest {
317 let elements: Vec<Felt> = kv_pairs
318 .iter()
319 .flat_map(|(key, value)| {
320 let key_elements = key.into_iter();
321 let value_elements = (*value).into_iter();
322
323 key_elements.chain(value_elements)
324 })
325 .collect();
326
327 Rpo256::hash_elements(&elements)
328}