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