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