miden-crypto/src/merkle/partial_mt/tests.rs
src/merkle/partial_mt/tests.rsRaw
1use super::{
2 super::{digests_to_words, int_to_node, MerkleStore, MerkleTree, NodeIndex, PartialMerkleTree},
3 RpoDigest, ValuePath, Vec,
4};
5
6// TEST DATA
7// ================================================================================================
8
9const NODE10: NodeIndex = NodeIndex::new_unchecked(1, 0);
10const NODE11: NodeIndex = NodeIndex::new_unchecked(1, 1);
11
12const NODE20: NodeIndex = NodeIndex::new_unchecked(2, 0);
13const NODE22: NodeIndex = NodeIndex::new_unchecked(2, 2);
14const NODE23: NodeIndex = NodeIndex::new_unchecked(2, 3);
15
16const NODE30: NodeIndex = NodeIndex::new_unchecked(3, 0);
17const NODE31: NodeIndex = NodeIndex::new_unchecked(3, 1);
18const NODE32: NodeIndex = NodeIndex::new_unchecked(3, 2);
19const NODE33: NodeIndex = NodeIndex::new_unchecked(3, 3);
20
21const VALUES8: [RpoDigest; 8] = [
22 int_to_node(30),
23 int_to_node(31),
24 int_to_node(32),
25 int_to_node(33),
26 int_to_node(34),
27 int_to_node(35),
28 int_to_node(36),
29 int_to_node(37),
30];
31
32// TESTS
33// ================================================================================================
34
35// For the Partial Merkle Tree tests we will use parts of the Merkle Tree which full form is
36// illustrated below:
37//
38// __________ root __________
39// / \
40// ____ 10 ____ ____ 11 ____
41// / \ / \
42// 20 21 22 23
43// / \ / \ / \ / \
44// (30) (31) (32) (33) (34) (35) (36) (37)
45//
46// Where node number is a concatenation of its depth and index. For example, node with
47// NodeIndex(3, 5) will be labeled as `35`. Leaves of the tree are shown as nodes with parenthesis
48// (33).
49
50/// Checks that root returned by `root()` function is equal to the expected one.
51#[test]
52fn get_root() {
53 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
54 let expected_root = mt.root();
55
56 let ms = MerkleStore::from(&mt);
57 let path33 = ms.get_path(expected_root, NODE33).unwrap();
58
59 let pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
60
61 assert_eq!(pmt.root(), expected_root);
62}
63
64/// This test checks correctness of the `add_path()` and `get_path()` functions. First it creates a
65/// PMT using `add_path()` by adding Merkle Paths from node 33 and node 22 to the empty PMT. Then
66/// it checks that paths returned by `get_path()` function are equal to the expected ones.
67#[test]
68fn add_and_get_paths() {
69 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
70 let expected_root = mt.root();
71
72 let ms = MerkleStore::from(&mt);
73
74 let expected_path33 = ms.get_path(expected_root, NODE33).unwrap();
75 let expected_path22 = ms.get_path(expected_root, NODE22).unwrap();
76
77 let mut pmt = PartialMerkleTree::new();
78 pmt.add_path(3, expected_path33.value, expected_path33.path.clone()).unwrap();
79 pmt.add_path(2, expected_path22.value, expected_path22.path.clone()).unwrap();
80
81 let path33 = pmt.get_path(NODE33).unwrap();
82 let path22 = pmt.get_path(NODE22).unwrap();
83 let actual_root = pmt.root();
84
85 assert_eq!(expected_path33.path, path33);
86 assert_eq!(expected_path22.path, path22);
87 assert_eq!(expected_root, actual_root);
88}
89
90/// Checks that function `get_node` used on nodes 10 and 32 returns expected values.
91#[test]
92fn get_node() {
93 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
94 let expected_root = mt.root();
95
96 let ms = MerkleStore::from(&mt);
97
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!(ms.get_node(expected_root, NODE32).unwrap(), pmt.get_node(NODE32).unwrap());
103 assert_eq!(ms.get_node(expected_root, NODE10).unwrap(), pmt.get_node(NODE10).unwrap());
104}
105
106/// Updates leaves of the PMT using `update_leaf()` function and checks that new root of the tree
107/// is equal to the expected one.
108#[test]
109fn update_leaf() {
110 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
111 let root = mt.root();
112
113 let mut ms = MerkleStore::from(&mt);
114 let path33 = ms.get_path(root, NODE33).unwrap();
115
116 let mut pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
117
118 let new_value32 = int_to_node(132);
119 let expected_root = ms.set_node(root, NODE32, new_value32).unwrap().root;
120
121 pmt.update_leaf(NODE32, new_value32).unwrap();
122 let actual_root = pmt.root();
123
124 assert_eq!(expected_root, actual_root);
125
126 let new_value20 = int_to_node(120);
127 let expected_root = ms.set_node(expected_root, NODE20, new_value20).unwrap().root;
128
129 pmt.update_leaf(NODE20, new_value20).unwrap();
130 let actual_root = pmt.root();
131
132 assert_eq!(expected_root, actual_root);
133}
134
135/// Checks that paths of the PMT returned by `paths()` function are equal to the expected ones.
136#[test]
137fn get_paths() {
138 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
139 let expected_root = mt.root();
140
141 let ms = MerkleStore::from(&mt);
142
143 let path33 = ms.get_path(expected_root, NODE33).unwrap();
144 let path22 = ms.get_path(expected_root, NODE22).unwrap();
145
146 let mut pmt = PartialMerkleTree::new();
147 pmt.add_path(3, path33.value, path33.path).unwrap();
148 pmt.add_path(2, path22.value, path22.path).unwrap();
149 // After PMT creation with path33 (33; 32, 20, 11) and path22 (22; 23, 10) we will have this
150 // tree:
151 //
152 // ______root______
153 // / \
154 // ___10___ ___11___
155 // / \ / \
156 // (20) 21 (22) (23)
157 // / \
158 // (32) (33)
159 //
160 // Which have leaf nodes 20, 22, 23, 32 and 33. Hence overall we will have 5 paths -- one path
161 // for each leaf.
162
163 let leaves = vec![NODE20, NODE22, NODE23, NODE32, NODE33];
164 let expected_paths: Vec<(NodeIndex, ValuePath)> = leaves
165 .iter()
166 .map(|&leaf| {
167 (
168 leaf,
169 ValuePath {
170 value: mt.get_node(leaf).unwrap(),
171 path: mt.get_path(leaf).unwrap(),
172 },
173 )
174 })
175 .collect();
176
177 let actual_paths = pmt.paths();
178
179 assert_eq!(expected_paths, actual_paths);
180}
181
182// Checks correctness of leaves determination when using the `leaves()` function.
183#[test]
184fn leaves() {
185 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
186 let expected_root = mt.root();
187
188 let ms = MerkleStore::from(&mt);
189
190 let path33 = ms.get_path(expected_root, NODE33).unwrap();
191 let path22 = ms.get_path(expected_root, NODE22).unwrap();
192
193 let mut pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
194 // After PMT creation with path33 (33; 32, 20, 11) we will have this tree:
195 //
196 // ______root______
197 // / \
198 // ___10___ (11)
199 // / \
200 // (20) 21
201 // / \
202 // (32) (33)
203 //
204 // Which have leaf nodes 11, 20, 32 and 33.
205
206 let value11 = mt.get_node(NODE11).unwrap();
207 let value20 = mt.get_node(NODE20).unwrap();
208 let value32 = mt.get_node(NODE32).unwrap();
209 let value33 = mt.get_node(NODE33).unwrap();
210
211 let leaves = vec![(NODE11, value11), (NODE20, value20), (NODE32, value32), (NODE33, value33)];
212
213 let expected_leaves = leaves.iter().copied();
214 assert!(expected_leaves.eq(pmt.leaves()));
215
216 pmt.add_path(2, path22.value, path22.path).unwrap();
217 // After adding the path22 (22; 23, 10) to the existing PMT we will have this tree:
218 //
219 // ______root______
220 // / \
221 // ___10___ ___11___
222 // / \ / \
223 // (20) 21 (22) (23)
224 // / \
225 // (32) (33)
226 //
227 // Which have leaf nodes 20, 22, 23, 32 and 33.
228
229 let value20 = mt.get_node(NODE20).unwrap();
230 let value22 = mt.get_node(NODE22).unwrap();
231 let value23 = mt.get_node(NODE23).unwrap();
232 let value32 = mt.get_node(NODE32).unwrap();
233 let value33 = mt.get_node(NODE33).unwrap();
234
235 let leaves = vec![
236 (NODE20, value20),
237 (NODE22, value22),
238 (NODE23, value23),
239 (NODE32, value32),
240 (NODE33, value33),
241 ];
242
243 let expected_leaves = leaves.iter().copied();
244 assert!(expected_leaves.eq(pmt.leaves()));
245}
246
247/// Checks that addition of the path with different root will cause an error.
248#[test]
249fn err_add_path() {
250 let path33 = vec![int_to_node(1), int_to_node(2), int_to_node(3)].into();
251 let path22 = vec![int_to_node(4), int_to_node(5)].into();
252
253 let mut pmt = PartialMerkleTree::new();
254 pmt.add_path(3, int_to_node(6), path33).unwrap();
255
256 assert!(pmt.add_path(2, int_to_node(7), path22).is_err());
257}
258
259/// Checks that the request of the node which is not in the PMT will cause an error.
260#[test]
261fn err_get_node() {
262 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
263 let expected_root = mt.root();
264
265 let ms = MerkleStore::from(&mt);
266
267 let path33 = ms.get_path(expected_root, NODE33).unwrap();
268
269 let pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
270
271 assert!(pmt.get_node(NODE22).is_err());
272 assert!(pmt.get_node(NODE23).is_err());
273 assert!(pmt.get_node(NODE30).is_err());
274 assert!(pmt.get_node(NODE31).is_err());
275}
276
277/// Checks that the request of the path from the leaf which is not in the PMT will cause an error.
278#[test]
279fn err_get_path() {
280 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
281 let expected_root = mt.root();
282
283 let ms = MerkleStore::from(&mt);
284
285 let path33 = ms.get_path(expected_root, NODE33).unwrap();
286
287 let pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
288
289 assert!(pmt.get_path(NODE22).is_err());
290 assert!(pmt.get_path(NODE23).is_err());
291 assert!(pmt.get_path(NODE30).is_err());
292 assert!(pmt.get_path(NODE31).is_err());
293}
294
295#[test]
296fn err_update_leaf() {
297 let mt = MerkleTree::new(digests_to_words(&VALUES8)).unwrap();
298 let expected_root = mt.root();
299
300 let ms = MerkleStore::from(&mt);
301
302 let path33 = ms.get_path(expected_root, NODE33).unwrap();
303
304 let mut pmt = PartialMerkleTree::with_paths([(3, path33.value, path33.path)]).unwrap();
305
306 assert!(pmt.update_leaf(NODE22, int_to_node(22)).is_err());
307 assert!(pmt.update_leaf(NODE23, int_to_node(23)).is_err());
308 assert!(pmt.update_leaf(NODE30, int_to_node(30)).is_err());
309 assert!(pmt.update_leaf(NODE31, int_to_node(31)).is_err());
310}