miden-crypto/src/merkle/simple_smt/tests.rs
src/merkle/simple_smt/tests.rsRaw
1use super::{
2 super::{InnerNodeInfo, MerkleError, MerkleTree, RpoDigest, SimpleSmt, EMPTY_WORD},
3 NodeIndex, Rpo256, Vec,
4};
5use crate::{
6 merkle::{digests_to_words, int_to_leaf, int_to_node},
7 Word,
8};
9
10// TEST DATA
11// ================================================================================================
12
13const KEYS4: [u64; 4] = [0, 1, 2, 3];
14const KEYS8: [u64; 8] = [0, 1, 2, 3, 4, 5, 6, 7];
15
16const VALUES4: [RpoDigest; 4] = [int_to_node(1), int_to_node(2), int_to_node(3), int_to_node(4)];
17
18const VALUES8: [RpoDigest; 8] = [
19 int_to_node(1),
20 int_to_node(2),
21 int_to_node(3),
22 int_to_node(4),
23 int_to_node(5),
24 int_to_node(6),
25 int_to_node(7),
26 int_to_node(8),
27];
28
29const ZERO_VALUES8: [Word; 8] = [int_to_leaf(0); 8];
30
31// TESTS
32// ================================================================================================
33
34#[test]
35fn build_empty_tree() {
36 // tree of depth 3
37 let smt = SimpleSmt::new(3).unwrap();
38 let mt = MerkleTree::new(ZERO_VALUES8.to_vec()).unwrap();
39 assert_eq!(mt.root(), smt.root());
40}
41
42#[test]
43fn build_sparse_tree() {
44 let mut smt = SimpleSmt::new(3).unwrap();
45 let mut values = ZERO_VALUES8.to_vec();
46
47 // insert single value
48 let key = 6;
49 let new_node = int_to_leaf(7);
50 values[key as usize] = new_node;
51 let old_value = smt.update_leaf(key, new_node).expect("Failed to update leaf");
52 let mt2 = MerkleTree::new(values.clone()).unwrap();
53 assert_eq!(mt2.root(), smt.root());
54 assert_eq!(
55 mt2.get_path(NodeIndex::make(3, 6)).unwrap(),
56 smt.get_path(NodeIndex::make(3, 6)).unwrap()
57 );
58 assert_eq!(old_value, EMPTY_WORD);
59
60 // insert second value at distinct leaf branch
61 let key = 2;
62 let new_node = int_to_leaf(3);
63 values[key as usize] = new_node;
64 let old_value = smt.update_leaf(key, new_node).expect("Failed to update leaf");
65 let mt3 = MerkleTree::new(values).unwrap();
66 assert_eq!(mt3.root(), smt.root());
67 assert_eq!(
68 mt3.get_path(NodeIndex::make(3, 2)).unwrap(),
69 smt.get_path(NodeIndex::make(3, 2)).unwrap()
70 );
71 assert_eq!(old_value, EMPTY_WORD);
72}
73
74#[test]
75fn test_depth2_tree() {
76 let tree =
77 SimpleSmt::with_leaves(2, KEYS4.into_iter().zip(digests_to_words(&VALUES4).into_iter()))
78 .unwrap();
79
80 // check internal structure
81 let (root, node2, node3) = compute_internal_nodes();
82 assert_eq!(root, tree.root());
83 assert_eq!(node2, tree.get_node(NodeIndex::make(1, 0)).unwrap());
84 assert_eq!(node3, tree.get_node(NodeIndex::make(1, 1)).unwrap());
85
86 // check get_node()
87 assert_eq!(VALUES4[0], tree.get_node(NodeIndex::make(2, 0)).unwrap());
88 assert_eq!(VALUES4[1], tree.get_node(NodeIndex::make(2, 1)).unwrap());
89 assert_eq!(VALUES4[2], tree.get_node(NodeIndex::make(2, 2)).unwrap());
90 assert_eq!(VALUES4[3], tree.get_node(NodeIndex::make(2, 3)).unwrap());
91
92 // check get_path(): depth 2
93 assert_eq!(vec![VALUES4[1], node3], *tree.get_path(NodeIndex::make(2, 0)).unwrap());
94 assert_eq!(vec![VALUES4[0], node3], *tree.get_path(NodeIndex::make(2, 1)).unwrap());
95 assert_eq!(vec![VALUES4[3], node2], *tree.get_path(NodeIndex::make(2, 2)).unwrap());
96 assert_eq!(vec![VALUES4[2], node2], *tree.get_path(NodeIndex::make(2, 3)).unwrap());
97
98 // check get_path(): depth 1
99 assert_eq!(vec![node3], *tree.get_path(NodeIndex::make(1, 0)).unwrap());
100 assert_eq!(vec![node2], *tree.get_path(NodeIndex::make(1, 1)).unwrap());
101}
102
103#[test]
104fn test_inner_node_iterator() -> Result<(), MerkleError> {
105 let tree =
106 SimpleSmt::with_leaves(2, KEYS4.into_iter().zip(digests_to_words(&VALUES4).into_iter()))
107 .unwrap();
108
109 // check depth 2
110 assert_eq!(VALUES4[0], tree.get_node(NodeIndex::make(2, 0)).unwrap());
111 assert_eq!(VALUES4[1], tree.get_node(NodeIndex::make(2, 1)).unwrap());
112 assert_eq!(VALUES4[2], tree.get_node(NodeIndex::make(2, 2)).unwrap());
113 assert_eq!(VALUES4[3], tree.get_node(NodeIndex::make(2, 3)).unwrap());
114
115 // get parent nodes
116 let root = tree.root();
117 let l1n0 = tree.get_node(NodeIndex::make(1, 0))?;
118 let l1n1 = tree.get_node(NodeIndex::make(1, 1))?;
119 let l2n0 = tree.get_node(NodeIndex::make(2, 0))?;
120 let l2n1 = tree.get_node(NodeIndex::make(2, 1))?;
121 let l2n2 = tree.get_node(NodeIndex::make(2, 2))?;
122 let l2n3 = tree.get_node(NodeIndex::make(2, 3))?;
123
124 let nodes: Vec<InnerNodeInfo> = tree.inner_nodes().collect();
125 let expected = vec![
126 InnerNodeInfo { value: root, left: l1n0, right: l1n1 },
127 InnerNodeInfo { value: l1n0, left: l2n0, right: l2n1 },
128 InnerNodeInfo { value: l1n1, left: l2n2, right: l2n3 },
129 ];
130 assert_eq!(nodes, expected);
131
132 Ok(())
133}
134
135#[test]
136fn update_leaf() {
137 let mut tree =
138 SimpleSmt::with_leaves(3, KEYS8.into_iter().zip(digests_to_words(&VALUES8).into_iter()))
139 .unwrap();
140
141 // update one value
142 let key = 3;
143 let new_node = int_to_leaf(9);
144 let mut expected_values = digests_to_words(&VALUES8);
145 expected_values[key] = new_node;
146 let expected_tree = MerkleTree::new(expected_values.clone()).unwrap();
147
148 let old_leaf = tree.update_leaf(key as u64, new_node).unwrap();
149 assert_eq!(expected_tree.root(), tree.root);
150 assert_eq!(old_leaf, *VALUES8[key]);
151
152 // update another value
153 let key = 6;
154 let new_node = int_to_leaf(10);
155 expected_values[key] = new_node;
156 let expected_tree = MerkleTree::new(expected_values.clone()).unwrap();
157
158 let old_leaf = tree.update_leaf(key as u64, new_node).unwrap();
159 assert_eq!(expected_tree.root(), tree.root);
160 assert_eq!(old_leaf, *VALUES8[key]);
161}
162
163#[test]
164fn small_tree_opening_is_consistent() {
165 // ____k____
166 // / \
167 // _i_ _j_
168 // / \ / \
169 // e f g h
170 // / \ / \ / \ / \
171 // a b 0 0 c 0 0 d
172
173 let z = EMPTY_WORD;
174
175 let a = Word::from(Rpo256::merge(&[z.into(); 2]));
176 let b = Word::from(Rpo256::merge(&[a.into(); 2]));
177 let c = Word::from(Rpo256::merge(&[b.into(); 2]));
178 let d = Word::from(Rpo256::merge(&[c.into(); 2]));
179
180 let e = Rpo256::merge(&[a.into(), b.into()]);
181 let f = Rpo256::merge(&[z.into(), z.into()]);
182 let g = Rpo256::merge(&[c.into(), z.into()]);
183 let h = Rpo256::merge(&[z.into(), d.into()]);
184
185 let i = Rpo256::merge(&[e, f]);
186 let j = Rpo256::merge(&[g, h]);
187
188 let k = Rpo256::merge(&[i, j]);
189
190 let depth = 3;
191 let entries = vec![(0, a), (1, b), (4, c), (7, d)];
192 let tree = SimpleSmt::with_leaves(depth, entries).unwrap();
193
194 assert_eq!(tree.root(), k);
195
196 let cases: Vec<(u8, u64, Vec<RpoDigest>)> = vec![
197 (3, 0, vec![b.into(), f, j]),
198 (3, 1, vec![a.into(), f, j]),
199 (3, 4, vec![z.into(), h, i]),
200 (3, 7, vec![z.into(), g, i]),
201 (2, 0, vec![f, j]),
202 (2, 1, vec![e, j]),
203 (2, 2, vec![h, i]),
204 (2, 3, vec![g, i]),
205 (1, 0, vec![j]),
206 (1, 1, vec![i]),
207 ];
208
209 for (depth, key, path) in cases {
210 let opening = tree.get_path(NodeIndex::make(depth, key)).unwrap();
211
212 assert_eq!(path, *opening);
213 }
214}
215
216#[test]
217fn fail_on_duplicates() {
218 let entries = [(1_u64, int_to_leaf(1)), (5, int_to_leaf(2)), (1_u64, int_to_leaf(3))];
219 let smt = SimpleSmt::with_leaves(64, entries);
220 assert!(smt.is_err());
221
222 let entries = [(1_u64, int_to_leaf(0)), (5, int_to_leaf(2)), (1_u64, int_to_leaf(0))];
223 let smt = SimpleSmt::with_leaves(64, entries);
224 assert!(smt.is_err());
225
226 let entries = [(1_u64, int_to_leaf(0)), (5, int_to_leaf(2)), (1_u64, int_to_leaf(1))];
227 let smt = SimpleSmt::with_leaves(64, entries);
228 assert!(smt.is_err());
229
230 let entries = [(1_u64, int_to_leaf(1)), (5, int_to_leaf(2)), (1_u64, int_to_leaf(0))];
231 let smt = SimpleSmt::with_leaves(64, entries);
232 assert!(smt.is_err());
233}
234
235#[test]
236fn with_no_duplicates_empty_node() {
237 let entries = [(1_u64, int_to_leaf(0)), (5, int_to_leaf(2))];
238 let smt = SimpleSmt::with_leaves(64, entries);
239 assert!(smt.is_ok());
240}
241
242#[test]
243fn test_simplesmt_update_nonexisting_leaf_with_zero() {
244 // TESTING WITH EMPTY WORD
245 // --------------------------------------------------------------------------------------------
246
247 // Depth 1 has 2 leaf. Position is 0-indexed, position 2 doesn't exist.
248 let mut smt = SimpleSmt::new(1).unwrap();
249 let result = smt.update_leaf(2, EMPTY_WORD);
250 assert!(!smt.leaves.contains_key(&2));
251 assert!(result.is_err());
252
253 // Depth 2 has 4 leaves. Position is 0-indexed, position 4 doesn't exist.
254 let mut smt = SimpleSmt::new(2).unwrap();
255 let result = smt.update_leaf(4, EMPTY_WORD);
256 assert!(!smt.leaves.contains_key(&4));
257 assert!(result.is_err());
258
259 // Depth 3 has 8 leaves. Position is 0-indexed, position 8 doesn't exist.
260 let mut smt = SimpleSmt::new(3).unwrap();
261 let result = smt.update_leaf(8, EMPTY_WORD);
262 assert!(!smt.leaves.contains_key(&8));
263 assert!(result.is_err());
264
265 // TESTING WITH A VALUE
266 // --------------------------------------------------------------------------------------------
267 let value = int_to_node(1);
268
269 // Depth 1 has 2 leaves. Position is 0-indexed, position 1 doesn't exist.
270 let mut smt = SimpleSmt::new(1).unwrap();
271 let result = smt.update_leaf(2, *value);
272 assert!(!smt.leaves.contains_key(&2));
273 assert!(result.is_err());
274
275 // Depth 2 has 4 leaves. Position is 0-indexed, position 2 doesn't exist.
276 let mut smt = SimpleSmt::new(2).unwrap();
277 let result = smt.update_leaf(4, *value);
278 assert!(!smt.leaves.contains_key(&4));
279 assert!(result.is_err());
280
281 // Depth 3 has 8 leaves. Position is 0-indexed, position 4 doesn't exist.
282 let mut smt = SimpleSmt::new(3).unwrap();
283 let result = smt.update_leaf(8, *value);
284 assert!(!smt.leaves.contains_key(&8));
285 assert!(result.is_err());
286}
287
288#[test]
289fn test_simplesmt_with_leaves_nonexisting_leaf() {
290 // TESTING WITH EMPTY WORD
291 // --------------------------------------------------------------------------------------------
292
293 // Depth 1 has 2 leaf. Position is 0-indexed, position 2 doesn't exist.
294 let leaves = [(2, EMPTY_WORD)];
295 let result = SimpleSmt::with_leaves(1, leaves);
296 assert!(result.is_err());
297
298 // Depth 2 has 4 leaves. Position is 0-indexed, position 4 doesn't exist.
299 let leaves = [(4, EMPTY_WORD)];
300 let result = SimpleSmt::with_leaves(2, leaves);
301 assert!(result.is_err());
302
303 // Depth 3 has 8 leaves. Position is 0-indexed, position 8 doesn't exist.
304 let leaves = [(8, EMPTY_WORD)];
305 let result = SimpleSmt::with_leaves(3, leaves);
306 assert!(result.is_err());
307
308 // TESTING WITH A VALUE
309 // --------------------------------------------------------------------------------------------
310 let value = int_to_node(1);
311
312 // Depth 1 has 2 leaves. Position is 0-indexed, position 2 doesn't exist.
313 let leaves = [(2, *value)];
314 let result = SimpleSmt::with_leaves(1, leaves);
315 assert!(result.is_err());
316
317 // Depth 2 has 4 leaves. Position is 0-indexed, position 4 doesn't exist.
318 let leaves = [(4, *value)];
319 let result = SimpleSmt::with_leaves(2, leaves);
320 assert!(result.is_err());
321
322 // Depth 3 has 8 leaves. Position is 0-indexed, position 8 doesn't exist.
323 let leaves = [(8, *value)];
324 let result = SimpleSmt::with_leaves(3, leaves);
325 assert!(result.is_err());
326}
327
328// HELPER FUNCTIONS
329// --------------------------------------------------------------------------------------------
330
331fn compute_internal_nodes() -> (RpoDigest, RpoDigest, RpoDigest) {
332 let node2 = Rpo256::merge(&[VALUES4[0], VALUES4[1]]);
333 let node3 = Rpo256::merge(&[VALUES4[2], VALUES4[3]]);
334 let root = Rpo256::merge(&[node2, node3]);
335
336 (root, node2, node3)
337}