miden-crypto/src/merkle/partial_mt/tests.rs
src/merkle/partial_mt/tests.rsRaw
1use super::{
2 super::{
3 digests_to_words, int_to_node, BTreeMap, DefaultMerkleStore as MerkleStore, MerkleTree,
4 NodeIndex, PartialMerkleTree,
5 },
6 Deserializable, InnerNodeInfo, RpoDigest, Serializable, ValuePath, Vec,
7};
8
9// TEST DATA
10// ================================================================================================
11
12const NODE10: NodeIndex = NodeIndex::new_unchecked(1, 0);
13const NODE11: NodeIndex = NodeIndex::new_unchecked(1, 1);
14
15const NODE20: NodeIndex = NodeIndex::new_unchecked(2, 0);
16const NODE21: NodeIndex = NodeIndex::new_unchecked(2, 1);
17const NODE22: NodeIndex = NodeIndex::new_unchecked(2, 2);
18const NODE23: NodeIndex = NodeIndex::new_unchecked(2, 3);
19
20const NODE30: NodeIndex = NodeIndex::new_unchecked(3, 0);
21const NODE31: NodeIndex = NodeIndex::new_unchecked(3, 1);
22const NODE32: NodeIndex = NodeIndex::new_unchecked(3, 2);
23const NODE33: NodeIndex = NodeIndex::new_unchecked(3, 3);
24
25const VALUES8: [RpoDigest; 8] = [
26 int_to_node(30),
27 int_to_node(31),
28 int_to_node(32),
29 int_to_node(33),
30 int_to_node(34),
31 int_to_node(35),
32 int_to_node(36),
33 int_to_node(37),
34];
35
36// TESTS
37// ================================================================================================
38
39// For the Partial Merkle Tree tests we will use parts of the Merkle Tree which full form is
40// illustrated below:
41//
42// __________ root __________
43// / \
44// ____ 10 ____ ____ 11 ____
45// / \ / \
46// 20 21 22 23
47// / \ / \ / \ / \
48// (30) (31) (32) (33) (34) (35) (36) (37)
49//
50// Where node number is a concatenation of its depth and index. For example, node with
51// NodeIndex(3, 5) will be labeled as `35`. Leaves of the tree are shown as nodes with parenthesis
52// (33).
53
54/// Checks that creation of the PMT with `with_leaves()` constructor is working correctly.
55#[test]
56fn with_leaves() {
57 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
58 let expected_root = mt.root();
59
60 let leaf_nodes_vec = vec![
61 (NODE20, mt.get_node(NODE20).unwrap()),
62 (NODE32, mt.get_node(NODE32).unwrap()),
63 (NODE33, mt.get_node(NODE33).unwrap()),
64 (NODE22, mt.get_node(NODE22).unwrap()),
65 (NODE23, mt.get_node(NODE23).unwrap()),
66 ];
67
68 let leaf_nodes: BTreeMap<NodeIndex, RpoDigest> = leaf_nodes_vec.into_iter().collect();
69
70 let pmt = PartialMerkleTree::with_leaves(leaf_nodes).unwrap();
71
72 assert_eq!(expected_root, pmt.root())
73}
74
75/// Checks that `with_leaves()` function returns an error when using incomplete set of nodes.
76#[test]
77fn err_with_leaves() {
78 // NODE22 is missing
79 let leaf_nodes_vec = vec![
80 (NODE20, int_to_node(20)),
81 (NODE32, int_to_node(32)),
82 (NODE33, int_to_node(33)),
83 (NODE23, int_to_node(23)),
84 ];
85
86 let leaf_nodes: BTreeMap<NodeIndex, RpoDigest> = leaf_nodes_vec.into_iter().collect();
87
88 assert!(PartialMerkleTree::with_leaves(leaf_nodes).is_err());
89}
90
91/// Checks that root returned by `root()` function is equal to the expected one.
92#[test]
93fn get_root() {
94 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
95 let expected_root = mt.root();
96
97 let ms = MerkleStore::from(&mt);
98 let path33 = ms.get_path(expected_root, NODE33).unwrap();
99
100 let pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
101
102 assert_eq!(expected_root, pmt.root());
103}
104
105/// This test checks correctness of the `add_path()` and `get_path()` functions. First it creates a
106/// PMT using `add_path()` by adding Merkle Paths from node 33 and node 22 to the empty PMT. Then
107/// it checks that paths returned by `get_path()` function are equal to the expected ones.
108#[test]
109fn add_and_get_paths() {
110 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
111 let expected_root = mt.root();
112
113 let ms = MerkleStore::from(&mt);
114
115 let expected_path33 = ms.get_path(expected_root, NODE33).unwrap();
116 let expected_path22 = ms.get_path(expected_root, NODE22).unwrap();
117
118 let mut pmt = PartialMerkleTree::new();
119 pmt.add_path(3, expected_path33.value, expected_path33.path.clone()).unwrap();
120 pmt.add_path(2, expected_path22.value, expected_path22.path.clone()).unwrap();
121
122 let path33 = pmt.get_path(NODE33).unwrap();
123 let path22 = pmt.get_path(NODE22).unwrap();
124 let actual_root = pmt.root();
125
126 assert_eq!(expected_path33.path, path33);
127 assert_eq!(expected_path22.path, path22);
128 assert_eq!(expected_root, actual_root);
129}
130
131/// Checks that function `get_node` used on nodes 10 and 32 returns expected values.
132#[test]
133fn get_node() {
134 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
135 let expected_root = mt.root();
136
137 let ms = MerkleStore::from(&mt);
138
139 let path33 = ms.get_path(expected_root, NODE33).unwrap();
140
141 let pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
142
143 assert_eq!(ms.get_node(expected_root, NODE32).unwrap(), pmt.get_node(NODE32).unwrap());
144 assert_eq!(ms.get_node(expected_root, NODE10).unwrap(), pmt.get_node(NODE10).unwrap());
145}
146
147/// Updates leaves of the PMT using `update_leaf()` function and checks that new root of the tree
148/// is equal to the expected one.
149#[test]
150fn update_leaf() {
151 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
152 let root = mt.root();
153
154 let mut ms = MerkleStore::from(&mt);
155 let path33 = ms.get_path(root, NODE33).unwrap();
156
157 let mut pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
158
159 let new_value32 = int_to_node(132);
160 let expected_root = ms.set_node(root, NODE32, new_value32).unwrap().root;
161
162 pmt.update_leaf(2, *new_value32).unwrap();
163 let actual_root = pmt.root();
164
165 assert_eq!(expected_root, actual_root);
166
167 let new_value20 = int_to_node(120);
168 let expected_root = ms.set_node(expected_root, NODE20, new_value20).unwrap().root;
169
170 pmt.update_leaf(0, *new_value20).unwrap();
171 let actual_root = pmt.root();
172
173 assert_eq!(expected_root, actual_root);
174
175 let new_value11 = int_to_node(111);
176 let expected_root = ms.set_node(expected_root, NODE11, new_value11).unwrap().root;
177
178 pmt.update_leaf(6, *new_value11).unwrap();
179 let actual_root = pmt.root();
180
181 assert_eq!(expected_root, actual_root);
182}
183
184/// Checks that paths of the PMT returned by `paths()` function are equal to the expected ones.
185#[test]
186fn get_paths() {
187 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
188 let expected_root = mt.root();
189
190 let ms = MerkleStore::from(&mt);
191
192 let path33 = ms.get_path(expected_root, NODE33).unwrap();
193 let path22 = ms.get_path(expected_root, NODE22).unwrap();
194
195 let mut pmt = PartialMerkleTree::new();
196 pmt.add_path(3, path33.value, path33.path).unwrap();
197 pmt.add_path(2, path22.value, path22.path).unwrap();
198 // After PMT creation with path33 (33; 32, 20, 11) and path22 (22; 23, 10) we will have this
199 // tree:
200 //
201 // ______root______
202 // / \
203 // ___10___ ___11___
204 // / \ / \
205 // (20) 21 (22) (23)
206 // / \
207 // (32) (33)
208 //
209 // Which have leaf nodes 20, 22, 23, 32 and 33. Hence overall we will have 5 paths -- one path
210 // for each leaf.
211
212 let leaves = [NODE20, NODE22, NODE23, NODE32, NODE33];
213 let expected_paths: Vec<(NodeIndex, ValuePath)> = leaves
214 .iter()
215 .map(|&leaf| {
216 (
217 leaf,
218 ValuePath {
219 value: mt.get_node(leaf).unwrap(),
220 path: mt.get_path(leaf).unwrap(),
221 },
222 )
223 })
224 .collect();
225
226 let actual_paths = pmt.to_paths();
227
228 assert_eq!(expected_paths, actual_paths);
229}
230
231// Checks correctness of leaves determination when using the `leaves()` function.
232#[test]
233fn leaves() {
234 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
235 let expected_root = mt.root();
236
237 let ms = MerkleStore::from(&mt);
238
239 let path33 = ms.get_path(expected_root, NODE33).unwrap();
240 let path22 = ms.get_path(expected_root, NODE22).unwrap();
241
242 let mut pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
243 // After PMT creation with path33 (33; 32, 20, 11) we will have this tree:
244 //
245 // ______root______
246 // / \
247 // ___10___ (11)
248 // / \
249 // (20) 21
250 // / \
251 // (32) (33)
252 //
253 // Which have leaf nodes 11, 20, 32 and 33.
254
255 let value11 = mt.get_node(NODE11).unwrap();
256 let value20 = mt.get_node(NODE20).unwrap();
257 let value32 = mt.get_node(NODE32).unwrap();
258 let value33 = mt.get_node(NODE33).unwrap();
259
260 let leaves = [(NODE11, value11), (NODE20, value20), (NODE32, value32), (NODE33, value33)];
261
262 let expected_leaves = leaves.iter().copied();
263 assert!(expected_leaves.eq(pmt.leaves()));
264
265 pmt.add_path(2, path22.value, path22.path).unwrap();
266 // After adding the path22 (22; 23, 10) to the existing PMT we will have this tree:
267 //
268 // ______root______
269 // / \
270 // ___10___ ___11___
271 // / \ / \
272 // (20) 21 (22) (23)
273 // / \
274 // (32) (33)
275 //
276 // Which have leaf nodes 20, 22, 23, 32 and 33.
277
278 let value20 = mt.get_node(NODE20).unwrap();
279 let value22 = mt.get_node(NODE22).unwrap();
280 let value23 = mt.get_node(NODE23).unwrap();
281 let value32 = mt.get_node(NODE32).unwrap();
282 let value33 = mt.get_node(NODE33).unwrap();
283
284 let leaves = vec![
285 (NODE20, value20),
286 (NODE22, value22),
287 (NODE23, value23),
288 (NODE32, value32),
289 (NODE33, value33),
290 ];
291
292 let expected_leaves = leaves.iter().copied();
293 assert!(expected_leaves.eq(pmt.leaves()));
294}
295
296/// Checks that nodes of the PMT returned by `inner_nodes()` function are equal to the expected ones.
297#[test]
298fn test_inner_node_iterator() {
299 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
300 let expected_root = mt.root();
301
302 let ms = MerkleStore::from(&mt);
303
304 let path33 = ms.get_path(expected_root, NODE33).unwrap();
305 let path22 = ms.get_path(expected_root, NODE22).unwrap();
306
307 let mut pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
308
309 // get actual inner nodes
310 let actual: Vec<InnerNodeInfo> = pmt.inner_nodes().collect();
311
312 let expected_n00 = mt.root();
313 let expected_n10 = mt.get_node(NODE10).unwrap();
314 let expected_n11 = mt.get_node(NODE11).unwrap();
315 let expected_n20 = mt.get_node(NODE20).unwrap();
316 let expected_n21 = mt.get_node(NODE21).unwrap();
317 let expected_n32 = mt.get_node(NODE32).unwrap();
318 let expected_n33 = mt.get_node(NODE33).unwrap();
319
320 // create vector of the expected inner nodes
321 let mut expected = vec![
322 InnerNodeInfo {
323 value: expected_n00,
324 left: expected_n10,
325 right: expected_n11,
326 },
327 InnerNodeInfo {
328 value: expected_n10,
329 left: expected_n20,
330 right: expected_n21,
331 },
332 InnerNodeInfo {
333 value: expected_n21,
334 left: expected_n32,
335 right: expected_n33,
336 },
337 ];
338
339 assert_eq!(actual, expected);
340
341 // add another path to the Partial Merkle Tree
342 pmt.add_path(2, path22.value, path22.path).unwrap();
343
344 // get new actual inner nodes
345 let actual: Vec<InnerNodeInfo> = pmt.inner_nodes().collect();
346
347 let expected_n22 = mt.get_node(NODE22).unwrap();
348 let expected_n23 = mt.get_node(NODE23).unwrap();
349
350 let info_11 = InnerNodeInfo {
351 value: expected_n11,
352 left: expected_n22,
353 right: expected_n23,
354 };
355
356 // add new inner node to the existing vertor
357 expected.insert(2, info_11);
358
359 assert_eq!(actual, expected);
360}
361
362/// Checks that serialization and deserialization implementations for the PMT are working
363/// correctly.
364#[test]
365fn serialization() {
366 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
367 let expected_root = mt.root();
368
369 let ms = MerkleStore::from(&mt);
370
371 let path33 = ms.get_path(expected_root, NODE33).unwrap();
372 let path22 = ms.get_path(expected_root, NODE22).unwrap();
373
374 let pmt = PartialMerkleTree::with_paths([
375 (3, path33.value, path33.path),
376 (2, path22.value, path22.path),
377 ])
378 .unwrap();
379
380 let serialized_pmt = pmt.to_bytes();
381 let deserialized_pmt = PartialMerkleTree::read_from_bytes(&serialized_pmt).unwrap();
382
383 assert_eq!(deserialized_pmt, pmt);
384}
385
386/// Checks that deserialization fails with incorrect data.
387#[test]
388fn err_deserialization() {
389 let mut tree_bytes: Vec<u8> = vec![5];
390 tree_bytes.append(&mut NODE20.to_bytes());
391 tree_bytes.append(&mut int_to_node(20).to_bytes());
392
393 tree_bytes.append(&mut NODE21.to_bytes());
394 tree_bytes.append(&mut int_to_node(21).to_bytes());
395
396 // node with depth 1 could have index 0 or 1, but it has 2
397 tree_bytes.append(&mut vec![1, 2]);
398 tree_bytes.append(&mut int_to_node(11).to_bytes());
399
400 assert!(PartialMerkleTree::read_from_bytes(&tree_bytes).is_err());
401}
402
403/// Checks that addition of the path with different root will cause an error.
404#[test]
405fn err_add_path() {
406 let path33 = vec![int_to_node(1), int_to_node(2), int_to_node(3)].into();
407 let path22 = vec![int_to_node(4), int_to_node(5)].into();
408
409 let mut pmt = PartialMerkleTree::new();
410 pmt.add_path(3, int_to_node(6), path33).unwrap();
411
412 assert!(pmt.add_path(2, int_to_node(7), path22).is_err());
413}
414
415/// Checks that the request of the node which is not in the PMT will cause an error.
416#[test]
417fn err_get_node() {
418 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
419 let expected_root = mt.root();
420
421 let ms = MerkleStore::from(&mt);
422
423 let path33 = ms.get_path(expected_root, NODE33).unwrap();
424
425 let pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
426
427 assert!(pmt.get_node(NODE22).is_err());
428 assert!(pmt.get_node(NODE23).is_err());
429 assert!(pmt.get_node(NODE30).is_err());
430 assert!(pmt.get_node(NODE31).is_err());
431}
432
433/// Checks that the request of the path from the leaf which is not in the PMT will cause an error.
434#[test]
435fn err_get_path() {
436 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
437 let expected_root = mt.root();
438
439 let ms = MerkleStore::from(&mt);
440
441 let path33 = ms.get_path(expected_root, NODE33).unwrap();
442
443 let pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
444
445 assert!(pmt.get_path(NODE22).is_err());
446 assert!(pmt.get_path(NODE23).is_err());
447 assert!(pmt.get_path(NODE30).is_err());
448 assert!(pmt.get_path(NODE31).is_err());
449}
450
451#[test]
452fn err_update_leaf() {
453 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
454 let expected_root = mt.root();
455
456 let ms = MerkleStore::from(&mt);
457
458 let path33 = ms.get_path(expected_root, NODE33).unwrap();
459
460 let mut pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
461
462 assert!(pmt.update_leaf(8, *int_to_node(38)).is_err());
463}