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