1use crate::{parse_cbor, CborError, CborHashTree, CborResult, CborValue};
2use ic_certification::{
3 hash_tree::{empty, fork, label, leaf, pruned, Hash, Label},
4 HashTree,
5};
6
7pub trait HashTreeToCbor {
8 fn from_cbor(cbor: &[u8]) -> CborResult<HashTree>;
9}
10
11impl HashTreeToCbor for HashTree {
12 fn from_cbor(cbor: &[u8]) -> CborResult<HashTree> {
13 let parsed_cbor = parse_cbor(cbor).map_err(|e| CborError::MalformedCbor(e.to_string()))?;
14
15 parsed_cbor_to_tree(&parsed_cbor)
16 }
17}
18
19pub fn parsed_cbor_to_tree(parsed_cbor: &CborValue) -> CborResult<HashTree> {
20 if let CborValue::Array(mut cbor_tags) = parsed_cbor.to_owned() {
21 cbor_tags.reverse();
22
23 if let Some(CborValue::HashTree(hash_tree_tag)) = cbor_tags.pop() {
24 match hash_tree_tag {
25 CborHashTree::Empty => Ok(empty()),
26
27 CborHashTree::Leaf => {
28 if let Some(CborValue::ByteString(data)) = cbor_tags.pop() {
29 Ok(leaf(data))
30 } else {
31 Err(CborError::MalformedHashTree(String::from(
32 "Missing ByteString for Leaf node",
33 )))
34 }
35 }
36
37 CborHashTree::Pruned => {
38 if let Some(CborValue::ByteString(data)) = cbor_tags.pop() {
39 let digest: Hash = TryFrom::<&[u8]>::try_from(data.as_ref())
40 .map_err(CborError::IncorrectPrunedDataLength)?;
41
42 Ok(pruned(digest))
43 } else {
44 Err(CborError::MalformedHashTree(String::from(
45 "Missing ByteString for Pruned node",
46 )))
47 }
48 }
49
50 CborHashTree::Labelled => {
51 if let (Some(CborValue::ByteString(data)), Some(child_tag)) =
52 (cbor_tags.pop(), cbor_tags.pop())
53 {
54 let node_label = Label::from(data);
55 let child_node = parsed_cbor_to_tree(&child_tag)?;
56
57 Ok(label(node_label, child_node))
58 } else {
59 Err(CborError::MalformedHashTree(String::from(
60 "Missing ByteString or child node for Labelled node",
61 )))
62 }
63 }
64
65 CborHashTree::Fork => {
66 if let (Some(left_tag), Some(right_tag)) = (cbor_tags.pop(), cbor_tags.pop()) {
67 let left = parsed_cbor_to_tree(&left_tag)?;
68 let right = parsed_cbor_to_tree(&right_tag)?;
69
70 Ok(fork(left, right))
71 } else {
72 Err(CborError::MalformedHashTree(String::from(
73 "Missing child nodes for Fork node",
74 )))
75 }
76 }
77 }
78 } else {
79 Err(CborError::MalformedHashTree(String::from(
80 "Expected Hash Tree cbor tag",
81 )))
82 }
83 } else {
84 Err(CborError::MalformedHashTree(String::from(
85 "Expected Array cbor tag",
86 )))
87 }
88}
89
90#[cfg(test)]
91mod tests {
92 use super::*;
93 use ic_certification::hash_tree::{
94 empty, fork, label, leaf, pruned, pruned_from_hex, Label, LookupResult,
95 };
96 use ic_response_verification_test_utils::{cbor_encode, hex_encode};
97
98 fn lookup_path<P: AsRef<[&'static str]>>(tree: &HashTree, path: P) -> LookupResult<'_> {
99 let path: Vec<Label<Vec<u8>>> = path
100 .as_ref()
101 .iter()
102 .map(|l| l.as_bytes().to_vec().into())
103 .collect();
104
105 tree.lookup_path(path)
106 }
107
108 #[test]
109 fn works_with_simple_tree() {
110 let original_tree: HashTree = fork(
111 label("label 1", empty()),
112 fork(
113 pruned(*b"\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"),
114 leaf(vec![1u8, 2, 3, 4, 5, 6]),
115 ),
116 );
117 let tree_cbor = cbor_encode(&original_tree);
118
119 let tree = HashTree::from_cbor(&tree_cbor).expect("Failed to deserialize tree");
120
121 assert_eq!(
122 hex_encode(&tree.digest()),
123 "69cf325d0f20505b261821a7e77ff72fb9a8753a7964f0b587553bfb44e72532"
124 );
125 }
126
127 #[test]
128 fn spec_example() {
129 let original_tree: HashTree = fork(
131 fork(
132 label(
133 "a",
134 fork(
135 fork(label("x", leaf(b"hello".to_vec())), empty()),
136 label("y", leaf(b"world".to_vec())),
137 ),
138 ),
139 label("b", leaf(b"good".to_vec())),
140 ),
141 fork(label("c", empty()), label("d", leaf(b"morning".to_vec()))),
142 );
143 let tree_cbor = cbor_encode(&original_tree);
144 let tree = HashTree::from_cbor(&tree_cbor).expect("Failed to deserialize tree");
145
146 assert_eq!(
147 hex_encode(&tree.digest()),
148 "eb5c5b2195e62d996b84c9bcc8259d19a83786a2f59e0878cec84c811f669aa0"
149 );
150 }
151
152 #[test]
153 fn spec_example_pruned() {
154 let original_tree: HashTree = fork(
156 fork(
157 label(
158 "a",
159 fork(
160 pruned_from_hex(
161 "1b4feff9bef8131788b0c9dc6dbad6e81e524249c879e9f10f71ce3749f5a638",
162 )
163 .unwrap(),
164 label("y", leaf(b"world".to_vec())),
165 ),
166 ),
167 label(
168 "b",
169 pruned_from_hex(
170 "7b32ac0c6ba8ce35ac82c255fc7906f7fc130dab2a090f80fe12f9c2cae83ba6",
171 )
172 .unwrap(),
173 ),
174 ),
175 fork(
176 pruned_from_hex("ec8324b8a1f1ac16bd2e806edba78006479c9877fed4eb464a25485465af601d")
177 .unwrap(),
178 label("d", leaf(b"morning".to_vec())),
179 ),
180 );
181 let tree_cbor = cbor_encode(&original_tree);
182 let tree = HashTree::from_cbor(&tree_cbor).expect("Failed to deserialize tree");
183
184 assert_eq!(
185 hex_encode(&tree.digest()),
186 "eb5c5b2195e62d996b84c9bcc8259d19a83786a2f59e0878cec84c811f669aa0"
187 );
188
189 assert_eq!(lookup_path(&tree, ["a", "a"]), LookupResult::Unknown);
190 assert_eq!(
191 lookup_path(&tree, ["a", "y"]),
192 LookupResult::Found(b"world")
193 );
194 assert_eq!(lookup_path(&tree, ["aa"]), LookupResult::Absent);
195 assert_eq!(lookup_path(&tree, ["ax"]), LookupResult::Absent);
196 assert_eq!(lookup_path(&tree, ["b"]), LookupResult::Unknown);
197 assert_eq!(lookup_path(&tree, ["bb"]), LookupResult::Unknown);
198 assert_eq!(lookup_path(&tree, ["d"]), LookupResult::Found(b"morning"));
199 assert_eq!(lookup_path(&tree, ["e"]), LookupResult::Absent);
200 }
201
202 #[test]
203 fn can_lookup_paths_1() {
204 let original_tree: HashTree = fork(
205 label("label 1", empty()),
206 fork(
207 pruned([1; 32]),
208 fork(
209 label("label 3", leaf(vec![1, 2, 3, 4, 5, 6])),
210 label("label 5", empty()),
211 ),
212 ),
213 );
214 let tree_cbor = cbor_encode(&original_tree);
215 let tree = HashTree::from_cbor(&tree_cbor).expect("Failed to deserialize tree");
216
217 assert_eq!(
218 tree.lookup_path(&["label 0".as_bytes().to_vec()]),
219 LookupResult::Absent
220 );
221 assert_eq!(
222 tree.lookup_path(&["label 1".as_bytes().to_vec()]),
223 LookupResult::Absent
224 );
225 assert_eq!(
226 tree.lookup_path(&["label 2".as_bytes().to_vec()]),
227 LookupResult::Unknown
228 );
229 assert_eq!(
230 tree.lookup_path(&["label 3".as_bytes().to_vec()]),
231 LookupResult::Found(&[1, 2, 3, 4, 5, 6])
232 );
233 assert_eq!(
234 tree.lookup_path(&["label 4".as_bytes().to_vec()]),
235 LookupResult::Absent
236 );
237 assert_eq!(
238 tree.lookup_path(&["label 5".as_bytes().to_vec()]),
239 LookupResult::Absent
240 );
241 assert_eq!(
242 tree.lookup_path(&["label 6".as_bytes().to_vec()]),
243 LookupResult::Absent
244 );
245 }
246
247 #[test]
248 fn can_lookup_paths_2() {
249 let original_tree: HashTree = fork(
250 label("label 1", empty()),
251 fork(
252 fork(
253 label("label 3", leaf(vec![1, 2, 3, 4, 5, 6])),
254 label("label 5", empty()),
255 ),
256 pruned([1; 32]),
257 ),
258 );
259 let tree_cbor = cbor_encode(&original_tree);
260 let tree = HashTree::from_cbor(&tree_cbor).expect("Failed to deserialize tree");
261
262 assert_eq!(
263 tree.lookup_path(&["label 0".as_bytes().to_vec()]),
264 LookupResult::Absent
265 );
266 assert_eq!(
267 tree.lookup_path(&["label 1".as_bytes().to_vec()]),
268 LookupResult::Absent
269 );
270 assert_eq!(
271 tree.lookup_path(&["label 2".as_bytes().to_vec()]),
272 LookupResult::Absent
273 );
274 assert_eq!(
275 tree.lookup_path(&["label 3".as_bytes().to_vec()]),
276 LookupResult::Found(&[1, 2, 3, 4, 5, 6])
277 );
278 assert_eq!(
279 tree.lookup_path(&["label 4".as_bytes().to_vec()]),
280 LookupResult::Absent
281 );
282 assert_eq!(
283 tree.lookup_path(&["label 5".as_bytes().to_vec()]),
284 LookupResult::Absent
285 );
286 assert_eq!(
287 tree.lookup_path(&["label 6".as_bytes().to_vec()]),
288 LookupResult::Unknown
289 );
290 }
291
292 #[test]
293 fn can_lookup_paths_3() {
294 let original_tree: HashTree = fork(
295 pruned([0; 32]),
296 fork(
297 pruned([1; 32]),
298 fork(
299 label("label 3", leaf(vec![1, 2, 3, 4, 5, 6])),
300 label("label 5", empty()),
301 ),
302 ),
303 );
304 let tree_cbor = cbor_encode(&original_tree);
305 let tree = HashTree::from_cbor(&tree_cbor).expect("Failed to deserialize tree");
306
307 assert_eq!(
308 tree.lookup_path(&["label 2".as_bytes().to_vec()]),
309 LookupResult::Unknown
310 );
311 assert_eq!(
312 tree.lookup_path(&["label 3".as_bytes().to_vec()]),
313 LookupResult::Found(&[1, 2, 3, 4, 5, 6])
314 );
315 assert_eq!(
316 tree.lookup_path(&["label 4".as_bytes().to_vec()]),
317 LookupResult::Absent
318 );
319 assert_eq!(
320 tree.lookup_path(&["label 5".as_bytes().to_vec()]),
321 LookupResult::Absent
322 );
323 assert_eq!(
324 tree.lookup_path(&["label 6".as_bytes().to_vec()]),
325 LookupResult::Absent
326 );
327 }
328
329 #[test]
330 fn can_lookup_paths_4() {
331 let original_tree: HashTree = fork(
332 pruned([0; 32]),
333 fork(
334 fork(
335 label("label 3", leaf(vec![1, 2, 3, 4, 5, 6])),
336 label("label 5", empty()),
337 ),
338 pruned([1; 32]),
339 ),
340 );
341 let tree_cbor = cbor_encode(&original_tree);
342 let tree = HashTree::from_cbor(&tree_cbor).expect("Failed to deserialize tree");
343
344 assert_eq!(
345 tree.lookup_path(&["label 2".as_bytes().to_vec()]),
346 LookupResult::Unknown
347 );
348 assert_eq!(
349 tree.lookup_path(&["label 3".as_bytes().to_vec()]),
350 LookupResult::Found(&[1, 2, 3, 4, 5, 6])
351 );
352 assert_eq!(
353 tree.lookup_path(&["label 4".as_bytes().to_vec()]),
354 LookupResult::Absent
355 );
356 assert_eq!(
357 tree.lookup_path(&["label 5".as_bytes().to_vec()]),
358 LookupResult::Absent
359 );
360 assert_eq!(
361 tree.lookup_path(&["label 6".as_bytes().to_vec()]),
362 LookupResult::Unknown
363 );
364 }
365
366 #[test]
367 fn can_lookup_paths_5() {
368 let original_tree: HashTree = fork(
369 fork(
370 pruned([1; 32]),
371 fork(
372 label("label 3", leaf(vec![1, 2, 3, 4, 5, 6])),
373 label("label 5", empty()),
374 ),
375 ),
376 label("label 7", empty()),
377 );
378 let tree_cbor = cbor_encode(&original_tree);
379 let tree = HashTree::from_cbor(&tree_cbor).expect("Failed to deserialize tree");
380
381 assert_eq!(
382 tree.lookup_path(&["label 2".as_bytes().to_vec()]),
383 LookupResult::Unknown
384 );
385 assert_eq!(
386 tree.lookup_path(&["label 3".as_bytes().to_vec()]),
387 LookupResult::Found(&[1, 2, 3, 4, 5, 6])
388 );
389 assert_eq!(
390 tree.lookup_path(&["label 4".as_bytes().to_vec()]),
391 LookupResult::Absent
392 );
393 assert_eq!(
394 tree.lookup_path(&["label 5".as_bytes().to_vec()]),
395 LookupResult::Absent
396 );
397 assert_eq!(
398 tree.lookup_path(&["label 6".as_bytes().to_vec()]),
399 LookupResult::Absent
400 );
401 assert_eq!(
402 tree.lookup_path(&["label 7".as_bytes().to_vec()]),
403 LookupResult::Absent
404 );
405 assert_eq!(
406 tree.lookup_path(&["label 8".as_bytes().to_vec()]),
407 LookupResult::Absent
408 );
409 }
410
411 #[test]
412 fn can_lookup_paths_6() {
413 let original_tree: HashTree = fork(
414 fork(
415 fork(
416 label("label 3", leaf(vec![1, 2, 3, 4, 5, 6])),
417 label("label 5", empty()),
418 ),
419 pruned([1; 32]),
420 ),
421 label("label 7", empty()),
422 );
423 let tree_cbor = cbor_encode(&original_tree);
424 let tree = HashTree::from_cbor(&tree_cbor).expect("Failed to deserialize tree");
425
426 assert_eq!(
427 tree.lookup_path(&["label 2".as_bytes().to_vec()]),
428 LookupResult::Absent
429 );
430 assert_eq!(
431 tree.lookup_path(&["label 3".as_bytes().to_vec()]),
432 LookupResult::Found(&[1, 2, 3, 4, 5, 6])
433 );
434 assert_eq!(
435 tree.lookup_path(&["label 4".as_bytes().to_vec()]),
436 LookupResult::Absent
437 );
438 assert_eq!(
439 tree.lookup_path(&["label 5".as_bytes().to_vec()]),
440 LookupResult::Absent
441 );
442 assert_eq!(
443 tree.lookup_path(&["label 6".as_bytes().to_vec()]),
444 LookupResult::Unknown
445 );
446 assert_eq!(
447 tree.lookup_path(&["label 7".as_bytes().to_vec()]),
448 LookupResult::Absent
449 );
450 assert_eq!(
451 tree.lookup_path(&["label 8".as_bytes().to_vec()]),
452 LookupResult::Absent
453 );
454 }
455
456 #[test]
457 fn can_lookup_paths_7() {
458 let original_tree: HashTree = fork(
459 fork(
460 pruned([1; 32]),
461 fork(
462 label("label 3", leaf(vec![1, 2, 3, 4, 5, 6])),
463 label("label 5", empty()),
464 ),
465 ),
466 pruned([0; 32]),
467 );
468 let tree_cbor = cbor_encode(&original_tree);
469 let tree = HashTree::from_cbor(&tree_cbor).expect("Failed to deserialize tree");
470
471 assert_eq!(
472 tree.lookup_path(&["label 2".as_bytes().to_vec()]),
473 LookupResult::Unknown
474 );
475 assert_eq!(
476 tree.lookup_path(&["label 3".as_bytes().to_vec()]),
477 LookupResult::Found(&[1, 2, 3, 4, 5, 6])
478 );
479 assert_eq!(
480 tree.lookup_path(&["label 4".as_bytes().to_vec()]),
481 LookupResult::Absent
482 );
483 assert_eq!(
484 tree.lookup_path(&["label 5".as_bytes().to_vec()]),
485 LookupResult::Absent
486 );
487 assert_eq!(
488 tree.lookup_path(&["label 6".as_bytes().to_vec()]),
489 LookupResult::Unknown
490 );
491 }
492
493 #[test]
494 fn can_lookup_paths_8() {
495 let original_tree: HashTree = fork(
496 fork(
497 fork(
498 label("label 3", leaf(vec![1, 2, 3, 4, 5, 6])),
499 label("label 5", empty()),
500 ),
501 pruned([1; 32]),
502 ),
503 pruned([0; 32]),
504 );
505 let tree_cbor = cbor_encode(&original_tree);
506 let tree = HashTree::from_cbor(&tree_cbor).expect("Failed to deserialize tree");
507
508 assert_eq!(
509 tree.lookup_path(&["label 2".as_bytes().to_vec()]),
510 LookupResult::Absent
511 );
512 assert_eq!(
513 tree.lookup_path(&["label 3".as_bytes().to_vec()]),
514 LookupResult::Found(&[1, 2, 3, 4, 5, 6])
515 );
516 assert_eq!(
517 tree.lookup_path(&["label 4".as_bytes().to_vec()]),
518 LookupResult::Absent
519 );
520 assert_eq!(
521 tree.lookup_path(&["label 5".as_bytes().to_vec()]),
522 LookupResult::Absent
523 );
524 assert_eq!(
525 tree.lookup_path(&["label 6".as_bytes().to_vec()]),
526 LookupResult::Unknown
527 );
528 }
529}