ic_certification/hash_tree/
mod.rs

1//! cf <https://internetcomputer.org/docs/current/references/ic-interface-spec/#certification-encoding>
2
3use hex::FromHexError;
4use sha2::Digest;
5use std::{
6    borrow::{Borrow, Cow},
7    fmt,
8};
9
10/// Sha256 Digest: 32 bytes
11pub type Hash = [u8; 32];
12
13#[derive(Clone, Hash, Ord, PartialOrd, Eq, PartialEq)]
14/// For labeled [HashTreeNode]
15pub struct Label<Storage: AsRef<[u8]>>(Storage);
16
17impl<Storage: AsRef<[u8]>> Label<Storage> {
18    /// Create a label from bytes.
19    pub fn from_bytes<'a>(v: &'a [u8]) -> Self
20    where
21        &'a [u8]: Into<Storage>,
22    {
23        Self(v.into())
24    }
25
26    /// Convert labels
27    pub fn from_label<StorageB: AsRef<[u8]> + Into<Storage>>(s: Label<StorageB>) -> Self {
28        Self(s.0.into())
29    }
30
31    /// Returns this label as bytes.
32    pub fn as_bytes(&self) -> &[u8] {
33        self.0.as_ref()
34    }
35
36    /// The length of the output of [`Self::write_hex`]
37    #[cfg(feature = "serde")]
38    fn hex_len(&self) -> usize {
39        self.as_bytes().len() * 2
40    }
41
42    /// Write out the hex
43    fn write_hex(&self, f: &mut impl fmt::Write) -> fmt::Result {
44        self.as_bytes()
45            .iter()
46            .try_for_each(|b| write!(f, "{:02X}", b))
47    }
48}
49
50impl<Storage: AsRef<[u8]>> From<Storage> for Label<Storage> {
51    fn from(s: Storage) -> Self {
52        Self(s)
53    }
54}
55
56impl<const N: usize> From<[u8; N]> for Label<Vec<u8>> {
57    fn from(s: [u8; N]) -> Self {
58        Self(s.into())
59    }
60}
61impl<'a, const N: usize> From<&'a [u8; N]> for Label<Vec<u8>> {
62    fn from(s: &'a [u8; N]) -> Self {
63        Self(s.as_slice().into())
64    }
65}
66impl<'a> From<&'a [u8]> for Label<Vec<u8>> {
67    fn from(s: &'a [u8]) -> Self {
68        Self(s.into())
69    }
70}
71impl<'a> From<&'a str> for Label<Vec<u8>> {
72    fn from(s: &'a str) -> Self {
73        Self(s.as_bytes().into())
74    }
75}
76impl From<String> for Label<Vec<u8>> {
77    fn from(s: String) -> Self {
78        Self(s.into())
79    }
80}
81
82impl<'a, const N: usize> From<&'a [u8; N]> for Label<&'a [u8]> {
83    fn from(s: &'a [u8; N]) -> Self {
84        Self(s.as_slice())
85    }
86}
87impl<'a> From<&'a str> for Label<&'a [u8]> {
88    fn from(s: &'a str) -> Self {
89        Self(s.as_bytes())
90    }
91}
92
93impl<'a, const N: usize> From<&'a [u8; N]> for Label<Cow<'a, [u8]>> {
94    fn from(s: &'a [u8; N]) -> Self {
95        Self(s.as_slice().into())
96    }
97}
98impl<'a> From<&'a [u8]> for Label<Cow<'a, [u8]>> {
99    fn from(s: &'a [u8]) -> Self {
100        Self(s.into())
101    }
102}
103impl<'a> From<&'a str> for Label<Cow<'a, [u8]>> {
104    fn from(s: &'a str) -> Self {
105        Self(s.as_bytes().into())
106    }
107}
108
109impl<Storage: AsRef<[u8]>> fmt::Display for Label<Storage> {
110    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
111        use fmt::Write;
112
113        // Try to print it as an UTF-8 string. If an error happens, print the bytes
114        // as hexadecimal.
115        match std::str::from_utf8(self.as_bytes()) {
116            Ok(s) if s.chars().all(|c| c.is_ascii_graphic()) => {
117                f.write_char('"')?;
118                f.write_str(s)?;
119                f.write_char('"')
120            }
121            _ => {
122                write!(f, "0x")?;
123                fmt::Debug::fmt(self, f)
124            }
125        }
126    }
127}
128
129impl<Storage: AsRef<[u8]>> fmt::Debug for Label<Storage> {
130    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
131        self.write_hex(f)
132    }
133}
134
135impl<Storage: AsRef<[u8]>> AsRef<[u8]> for Label<Storage> {
136    fn as_ref(&self) -> &[u8] {
137        self.0.as_ref()
138    }
139}
140
141/// A result of looking up for a certificate.
142#[derive(Clone, PartialEq, Eq, Debug)]
143pub enum LookupResult<'tree> {
144    /// The value is guaranteed to be absent in the original state tree.
145    Absent,
146
147    /// This partial view does not include information about this path, and the original
148    /// tree may or may note include this value.
149    Unknown,
150
151    /// The value was found at the referenced node.
152    Found(&'tree [u8]),
153
154    /// The path does not make sense for this certificate.
155    Error,
156}
157
158/// A result of looking up for a subtree.
159#[derive(Clone, PartialEq, Eq, Debug)]
160pub enum SubtreeLookupResult<Storage: AsRef<[u8]>> {
161    /// The subtree at the provided path is guaranteed to be absent in the original state tree.
162    Absent,
163
164    /// This partial view does not include information about this path, and the original
165    /// tree may or may note include a subtree at this path.
166    Unknown,
167
168    /// The subtree was found at the provided path.
169    Found(HashTree<Storage>),
170}
171
172/// A HashTree representing a full tree.
173#[derive(Clone, PartialEq, Eq)]
174pub struct HashTree<Storage: AsRef<[u8]>> {
175    pub(crate) root: HashTreeNode<Storage>,
176}
177
178impl<Storage: AsRef<[u8]>> fmt::Debug for HashTree<Storage> {
179    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
180        f.debug_struct("HashTree")
181            .field("root", &self.root)
182            .finish()
183    }
184}
185
186#[allow(dead_code)]
187impl<Storage: AsRef<[u8]>> HashTree<Storage> {
188    /// Recomputes root hash of the full tree that this hash tree was constructed from.
189    #[inline]
190    pub fn digest(&self) -> Hash {
191        self.root.digest()
192    }
193
194    /// Given a (verified) tree, the client can fetch the value at a given path, which is a
195    /// sequence of labels (blobs).
196    pub fn lookup_path<P>(&self, path: P) -> LookupResult<'_>
197    where
198        P: IntoIterator,
199        P::Item: AsRef<[u8]>,
200    {
201        self.root.lookup_path(&mut path.into_iter())
202    }
203}
204
205impl<Storage: Clone + AsRef<[u8]>> HashTree<Storage> {
206    /// Given a (verified) tree, the client can fetch the subtree at a given path, which is a
207    /// sequence of labels (blobs).
208    pub fn lookup_subtree<'p, P, I>(&self, path: P) -> SubtreeLookupResult<Storage>
209    where
210        P: IntoIterator<Item = &'p I>,
211        I: ?Sized + AsRef<[u8]> + 'p,
212    {
213        self.root
214            .lookup_subtree(&mut path.into_iter().map(|v| v.borrow()))
215    }
216
217    /// List all paths in the [HashTree]
218    pub fn list_paths(&self) -> Vec<Vec<Label<Storage>>> {
219        self.root.list_paths(&vec![])
220    }
221}
222
223impl<Storage: AsRef<[u8]>> AsRef<HashTreeNode<Storage>> for HashTree<Storage> {
224    fn as_ref(&self) -> &HashTreeNode<Storage> {
225        &self.root
226    }
227}
228
229impl<Storage: AsRef<[u8]>> From<HashTree<Storage>> for HashTreeNode<Storage> {
230    fn from(tree: HashTree<Storage>) -> HashTreeNode<Storage> {
231        tree.root
232    }
233}
234
235/// Create an empty hash tree.
236#[inline]
237pub fn empty<Storage: AsRef<[u8]>>() -> HashTree<Storage> {
238    HashTree {
239        root: HashTreeNode::Empty(),
240    }
241}
242
243/// Create a forked tree from two trees or node.
244#[inline]
245pub fn fork<Storage: AsRef<[u8]>>(
246    left: HashTree<Storage>,
247    right: HashTree<Storage>,
248) -> HashTree<Storage> {
249    HashTree {
250        root: HashTreeNode::Fork(Box::new((left.root, right.root))),
251    }
252}
253
254/// Create a labeled hash tree.
255#[inline]
256pub fn label<Storage: AsRef<[u8]>, L: Into<Label<Storage>>, N: Into<HashTree<Storage>>>(
257    label: L,
258    node: N,
259) -> HashTree<Storage> {
260    HashTree {
261        root: HashTreeNode::Labeled(label.into(), Box::new(node.into().root)),
262    }
263}
264
265/// Create a leaf in the tree.
266#[inline]
267pub fn leaf<Storage: AsRef<[u8]>, L: Into<Storage>>(leaf: L) -> HashTree<Storage> {
268    HashTree {
269        root: HashTreeNode::Leaf(leaf.into()),
270    }
271}
272
273/// Create a pruned tree node.
274#[inline]
275pub fn pruned<Storage: AsRef<[u8]>, C: Into<Hash>>(content: C) -> HashTree<Storage> {
276    HashTree {
277        root: HashTreeNode::Pruned(content.into()),
278    }
279}
280
281/// Create a pruned tree node, from a hex representation of the data. Useful for
282/// testing or hard coded values.
283#[inline]
284pub fn pruned_from_hex<Storage: AsRef<[u8]>, C: AsRef<str>>(
285    content: C,
286) -> Result<HashTree<Storage>, FromHexError> {
287    let mut decode: Hash = [0; 32];
288    hex::decode_to_slice(content.as_ref(), &mut decode)?;
289
290    Ok(pruned(decode))
291}
292
293/// Private type for label lookup result.
294#[derive(Debug)]
295enum LookupLabelResult<'node, Storage: AsRef<[u8]>> {
296    /// The label is not part of this node's tree.
297    Absent,
298
299    /// Same as absent, but some leaves were pruned and so it's impossible to know.
300    Unknown,
301
302    /// The label was not found, but could still be to the left.
303    Less,
304
305    /// The label was not found, but could still be to the right.
306    Greater,
307
308    /// The label was found. Contains a reference to the [HashTreeNode].
309    Found(&'node HashTreeNode<Storage>),
310}
311
312/// A Node in the HashTree.
313#[derive(Clone, PartialEq, Eq)]
314pub enum HashTreeNode<Storage: AsRef<[u8]>> {
315    Empty(),
316    Fork(Box<(Self, Self)>),
317    Labeled(Label<Storage>, Box<Self>),
318    Leaf(Storage),
319    Pruned(Hash),
320}
321
322impl<Storage: AsRef<[u8]>> fmt::Debug for HashTreeNode<Storage> {
323    // Shows a nicer view to debug than the default debugger.
324    // Example:
325    //
326    // ```
327    // HashTree {
328    //     root: Fork(
329    //         Fork(
330    //             Label("a", Fork(
331    //                 Pruned(1b4feff9bef8131788b0c9dc6dbad6e81e524249c879e9f10f71ce3749f5a638),
332    //                 Label("y", Leaf("world")),
333    //             )),
334    //             Label("b", Pruned(7b32ac0c6ba8ce35ac82c255fc7906f7fc130dab2a090f80fe12f9c2cae83ba6)),
335    //         ),
336    //         Fork(
337    //             Pruned(ec8324b8a1f1ac16bd2e806edba78006479c9877fed4eb464a25485465af601d),
338    //             Label("d", Leaf("morning")),
339    //         ),
340    //     ),
341    // }
342    // ```
343    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
344        fn readable_print(v: &[u8]) -> String {
345            // If it's UTF-8 and all the characters are graphic ASCII, then show as a string.
346            // If it's short, show hex.
347            // Otherwise, show length.
348            match std::str::from_utf8(v) {
349                Ok(s) if s.chars().all(|c| c.is_ascii_graphic()) => s.to_string(),
350                _ if v.len() <= 32 => {
351                    format!("0x{}", hex::encode(v))
352                }
353                _ => {
354                    format!("{} bytes", v.len())
355                }
356            }
357        }
358
359        match self {
360            HashTreeNode::Empty() => f.write_str("Empty"),
361            HashTreeNode::Fork(nodes) => f
362                .debug_tuple("Fork")
363                .field(&nodes.0)
364                .field(&nodes.1)
365                .finish(),
366            HashTreeNode::Leaf(v) => {
367                f.write_str("Leaf(")?;
368                f.write_str(&readable_print(v.as_ref()))?;
369                f.write_str(")")
370            }
371            HashTreeNode::Labeled(l, node) => f
372                .debug_tuple("Label")
373                .field(&readable_print(l.as_bytes()))
374                .field(&node)
375                .finish(),
376            HashTreeNode::Pruned(digest) => write!(f, "Pruned({})", hex::encode(digest.as_ref())),
377        }
378    }
379}
380
381impl<Storage: AsRef<[u8]>> HashTreeNode<Storage> {
382    /// Update a hasher with the domain separator (byte(|s|) . s).
383    #[inline]
384    fn domain_sep(&self, hasher: &mut sha2::Sha256) {
385        let domain_sep = match self {
386            HashTreeNode::Empty() => "ic-hashtree-empty",
387            HashTreeNode::Fork(_) => "ic-hashtree-fork",
388            HashTreeNode::Labeled(_, _) => "ic-hashtree-labeled",
389            HashTreeNode::Leaf(_) => "ic-hashtree-leaf",
390            HashTreeNode::Pruned(_) => return,
391        };
392        hasher.update([domain_sep.len() as u8]);
393        hasher.update(domain_sep.as_bytes());
394    }
395
396    /// Calculate the digest of this node only.
397    #[inline]
398    pub fn digest(&self) -> Hash {
399        let mut hasher = sha2::Sha256::new();
400        self.domain_sep(&mut hasher);
401
402        match self {
403            HashTreeNode::Empty() => {}
404            HashTreeNode::Fork(nodes) => {
405                hasher.update(nodes.0.digest());
406                hasher.update(nodes.1.digest());
407            }
408            HashTreeNode::Labeled(label, node) => {
409                hasher.update(label.as_bytes());
410                hasher.update(node.digest());
411            }
412            HashTreeNode::Leaf(bytes) => {
413                hasher.update(bytes.as_ref());
414            }
415            HashTreeNode::Pruned(digest) => {
416                return *digest;
417            }
418        }
419
420        hasher.finalize().into()
421    }
422
423    /// Lookup a single label, returning a reference to the labeled [HashTreeNode] node if found.
424    ///
425    /// This assumes a sorted hash tree, which is what the spec says the system should
426    /// return. It will stop when it finds a label that's greater than the one being looked
427    /// for.
428    ///
429    /// This function is implemented with flattening in mind, ie. flattening the forks
430    /// is not necessary.
431    fn lookup_label(&self, label: &[u8]) -> LookupLabelResult<Storage> {
432        match self {
433            // If this node is a labeled node, check for the name.
434            HashTreeNode::Labeled(l, node) => match label.cmp(l.as_bytes()) {
435                std::cmp::Ordering::Greater => LookupLabelResult::Greater,
436                std::cmp::Ordering::Equal => LookupLabelResult::Found(node.as_ref()),
437                // If this node has a smaller label than the one we're looking for, shortcut
438                // out of this search (sorted tree), we looked too far.
439                std::cmp::Ordering::Less => LookupLabelResult::Less,
440            },
441            HashTreeNode::Fork(nodes) => {
442                let left_label = nodes.0.lookup_label(label);
443                match left_label {
444                    // On greater or unknown, look on the right side of the fork.
445                    LookupLabelResult::Greater => {
446                        let right_label = nodes.1.lookup_label(label);
447                        match right_label {
448                            LookupLabelResult::Less => LookupLabelResult::Absent,
449                            result => result,
450                        }
451                    }
452                    LookupLabelResult::Unknown => {
453                        let right_label = nodes.1.lookup_label(label);
454                        match right_label {
455                            LookupLabelResult::Less => LookupLabelResult::Unknown,
456                            result => result,
457                        }
458                    }
459                    result => result,
460                }
461            }
462            HashTreeNode::Pruned(_) => LookupLabelResult::Unknown,
463            // Any other type of node and we need to look for more forks.
464            _ => LookupLabelResult::Absent,
465        }
466    }
467
468    /// Lookup the path for the current node only. If the node does not contain the label,
469    /// this will return [None], signifying that whatever process is recursively walking the
470    /// tree should continue with siblings of this node (if possible). If it returns
471    /// [Some] value, then it found an actual result and this may be propagated to the
472    /// original process doing the lookup.
473    ///
474    /// This assumes a sorted hash tree, which is what the spec says the system should return.
475    /// It will stop when it finds a label that's greater than the one being looked for.
476    fn lookup_path(&self, path: &mut dyn Iterator<Item = impl AsRef<[u8]>>) -> LookupResult<'_> {
477        use HashTreeNode::*;
478        use LookupLabelResult as LLR;
479        use LookupResult::*;
480
481        match (
482            path.next()
483                .map(|segment| self.lookup_label(segment.as_ref())),
484            self,
485        ) {
486            (Some(LLR::Found(node)), _) => node.lookup_path(path),
487            (None, Leaf(v)) => Found(v.as_ref()),
488
489            (None, Empty()) => Absent,
490            (None, Pruned(_)) => Unknown,
491            (None, Labeled(_, _) | Fork(_)) => Error,
492
493            (Some(LLR::Unknown), _) => Unknown,
494            (Some(LLR::Absent | LLR::Greater | LLR::Less), _) => Absent,
495        }
496    }
497}
498
499impl<Storage: Clone + AsRef<[u8]>> HashTreeNode<Storage> {
500    /// Lookup a subtree at the provided path.
501    /// If the tree definitely does not contain the label, this will return [SubtreeLookupResult::Absent].
502    /// If the tree has pruned sections that might contain the path, this will return [SubtreeLookupResult::Unknown].
503    /// If the provided path is found, this will return [SubtreeLookupResult::Found] with the node that was found at that path.
504    ///
505    /// This assumes a sorted hash tree, which is what the spec says the system should return.
506    /// It will stop when it finds a label that's greater than the one being looked for.
507    fn lookup_subtree(
508        &self,
509        path: &mut dyn Iterator<Item = impl AsRef<[u8]>>,
510    ) -> SubtreeLookupResult<Storage> {
511        use LookupLabelResult as LLR;
512        use SubtreeLookupResult::*;
513
514        match path
515            .next()
516            .map(|segment| self.lookup_label(segment.as_ref()))
517        {
518            Some(LLR::Found(node)) => node.lookup_subtree(path),
519            Some(LLR::Unknown) => Unknown,
520            Some(LLR::Absent | LLR::Greater | LLR::Less) => Absent,
521            None => Found(HashTree {
522                root: self.to_owned(),
523            }),
524        }
525    }
526
527    fn list_paths(&self, path: &Vec<Label<Storage>>) -> Vec<Vec<Label<Storage>>> {
528        match self {
529            HashTreeNode::Empty() => vec![],
530            HashTreeNode::Fork(nodes) => {
531                [nodes.0.list_paths(path), nodes.1.list_paths(path)].concat()
532            }
533            HashTreeNode::Leaf(_) => vec![path.clone()],
534            HashTreeNode::Labeled(l, node) => {
535                let mut path = path.clone();
536                path.push(l.clone());
537                node.list_paths(&path)
538            }
539            HashTreeNode::Pruned(_) => vec![],
540        }
541    }
542}
543#[cfg(feature = "serde")]
544mod serde_impl {
545    use std::{borrow::Cow, fmt, marker::PhantomData};
546
547    use crate::serde_impl::{CowStorage, SliceStorage, Storage, VecStorage};
548
549    use super::{HashTree, HashTreeNode, Label};
550
551    use serde::{
552        de::{self, SeqAccess, Visitor},
553        ser::SerializeSeq,
554        Deserialize, Deserializer, Serialize, Serializer,
555    };
556    use serde_bytes::Bytes;
557
558    impl<Storage: AsRef<[u8]>> Serialize for Label<Storage> {
559        fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
560            if serializer.is_human_readable() {
561                let mut s = String::with_capacity(self.hex_len());
562                self.write_hex(&mut s).unwrap();
563                s.serialize(serializer)
564            } else {
565                serializer.serialize_bytes(self.0.as_ref())
566            }
567        }
568    }
569    impl<'de, Storage: AsRef<[u8]>> Deserialize<'de> for Label<Storage>
570    where
571        Storage: serde_bytes::Deserialize<'de>,
572    {
573        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
574        where
575            D: Deserializer<'de>,
576        {
577            serde_bytes::deserialize(deserializer).map(Self)
578        }
579    }
580
581    impl<Storage: AsRef<[u8]>> Serialize for HashTreeNode<Storage> {
582        // Serialize a `MixedHashTree` per the CDDL of the public spec.
583        // See https://docs.dfinity.systems/public/certificates.cddl
584        fn serialize<S>(
585            &self,
586            serializer: S,
587        ) -> Result<<S as Serializer>::Ok, <S as Serializer>::Error>
588        where
589            S: Serializer,
590        {
591            match self {
592                HashTreeNode::Empty() => {
593                    let mut seq = serializer.serialize_seq(Some(1))?;
594                    seq.serialize_element(&0u8)?;
595                    seq.end()
596                }
597                HashTreeNode::Fork(tree) => {
598                    let mut seq = serializer.serialize_seq(Some(3))?;
599                    seq.serialize_element(&1u8)?;
600                    seq.serialize_element(&tree.0)?;
601                    seq.serialize_element(&tree.1)?;
602                    seq.end()
603                }
604                HashTreeNode::Labeled(label, tree) => {
605                    let mut seq = serializer.serialize_seq(Some(3))?;
606                    seq.serialize_element(&2u8)?;
607                    seq.serialize_element(Bytes::new(label.as_bytes()))?;
608                    seq.serialize_element(&tree)?;
609                    seq.end()
610                }
611                HashTreeNode::Leaf(leaf_bytes) => {
612                    let mut seq = serializer.serialize_seq(Some(2))?;
613                    seq.serialize_element(&3u8)?;
614                    seq.serialize_element(Bytes::new(leaf_bytes.as_ref()))?;
615                    seq.end()
616                }
617                HashTreeNode::Pruned(digest) => {
618                    let mut seq = serializer.serialize_seq(Some(2))?;
619                    seq.serialize_element(&4u8)?;
620                    seq.serialize_element(Bytes::new(digest))?;
621                    seq.end()
622                }
623            }
624        }
625    }
626
627    struct HashTreeNodeVisitor<S>(PhantomData<S>);
628
629    impl<'de, S: Storage> Visitor<'de> for HashTreeNodeVisitor<S>
630    where
631        HashTreeNode<S::Value<'de>>: Deserialize<'de>,
632    {
633        type Value = HashTreeNode<S::Value<'de>>;
634
635        fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
636            formatter.write_str(
637                "HashTree encoded as a sequence of the form \
638                 hash-tree ::= [0] | [1 hash-tree hash-tree] | [2 bytes hash-tree] | [3 bytes] | [4 hash]",
639            )
640        }
641
642        fn visit_seq<V>(self, mut seq: V) -> Result<Self::Value, V::Error>
643        where
644            V: SeqAccess<'de>,
645        {
646            let tag: u8 = seq
647                .next_element()?
648                .ok_or_else(|| de::Error::invalid_length(0, &self))?;
649
650            match tag {
651                0 => {
652                    if let Some(de::IgnoredAny) = seq.next_element()? {
653                        return Err(de::Error::invalid_length(2, &self));
654                    }
655
656                    Ok(HashTreeNode::Empty())
657                }
658                1 => {
659                    let left = seq
660                        .next_element()?
661                        .ok_or_else(|| de::Error::invalid_length(1, &self))?;
662                    let right = seq
663                        .next_element()?
664                        .ok_or_else(|| de::Error::invalid_length(2, &self))?;
665
666                    if let Some(de::IgnoredAny) = seq.next_element()? {
667                        return Err(de::Error::invalid_length(4, &self));
668                    }
669
670                    Ok(HashTreeNode::Fork(Box::new((left, right))))
671                }
672                2 => {
673                    let label = seq
674                        .next_element()?
675                        .ok_or_else(|| de::Error::invalid_length(1, &self))?;
676                    let subtree = seq
677                        .next_element()?
678                        .ok_or_else(|| de::Error::invalid_length(2, &self))?;
679
680                    if let Some(de::IgnoredAny) = seq.next_element()? {
681                        return Err(de::Error::invalid_length(4, &self));
682                    }
683
684                    Ok(HashTreeNode::Labeled(
685                        Label(S::convert(label)),
686                        Box::new(subtree),
687                    ))
688                }
689                3 => {
690                    let bytes = seq
691                        .next_element()?
692                        .ok_or_else(|| de::Error::invalid_length(1, &self))?;
693
694                    if let Some(de::IgnoredAny) = seq.next_element()? {
695                        return Err(de::Error::invalid_length(3, &self));
696                    }
697
698                    Ok(HashTreeNode::Leaf(S::convert(bytes)))
699                }
700                4 => {
701                    let digest_bytes: &serde_bytes::Bytes = seq
702                        .next_element()?
703                        .ok_or_else(|| de::Error::invalid_length(1, &self))?;
704
705                    if let Some(de::IgnoredAny) = seq.next_element()? {
706                        return Err(de::Error::invalid_length(3, &self));
707                    }
708
709                    let digest =
710                        std::convert::TryFrom::try_from(digest_bytes.as_ref()).map_err(|_| {
711                            de::Error::invalid_length(digest_bytes.len(), &"Expected digest blob")
712                        })?;
713
714                    Ok(HashTreeNode::Pruned(digest))
715                }
716                _ => Err(de::Error::custom(format!(
717                    "Unknown tag: {}, expected the tag to be one of {{0, 1, 2, 3, 4}}",
718                    tag
719                ))),
720            }
721        }
722    }
723
724    impl<'de> Deserialize<'de> for HashTreeNode<Vec<u8>> {
725        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
726        where
727            D: Deserializer<'de>,
728        {
729            deserializer.deserialize_seq(HashTreeNodeVisitor::<VecStorage>(PhantomData))
730        }
731    }
732
733    impl<'de> Deserialize<'de> for HashTreeNode<&'de [u8]> {
734        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
735        where
736            D: Deserializer<'de>,
737        {
738            deserializer.deserialize_seq(HashTreeNodeVisitor::<SliceStorage>(PhantomData))
739        }
740    }
741
742    impl<'de> Deserialize<'de> for HashTreeNode<Cow<'de, [u8]>> {
743        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
744        where
745            D: Deserializer<'de>,
746        {
747            deserializer.deserialize_seq(HashTreeNodeVisitor::<CowStorage>(PhantomData))
748        }
749    }
750
751    impl<Storage: AsRef<[u8]>> serde::Serialize for HashTree<Storage> {
752        fn serialize<S>(
753            &self,
754            serializer: S,
755        ) -> Result<<S as serde::Serializer>::Ok, <S as serde::Serializer>::Error>
756        where
757            S: serde::Serializer,
758        {
759            self.root.serialize(serializer)
760        }
761    }
762
763    impl<'de, Storage: AsRef<[u8]>> serde::Deserialize<'de> for HashTree<Storage>
764    where
765        HashTreeNode<Storage>: Deserialize<'de>,
766    {
767        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
768        where
769            D: serde::Deserializer<'de>,
770        {
771            Ok(HashTree {
772                root: HashTreeNode::deserialize(deserializer)?,
773            })
774        }
775    }
776}
777
778/// Identifiably hashes a fork in the branch. Used for hashing [HashTreeNode::Fork].
779pub fn fork_hash(l: &Hash, r: &Hash) -> Hash {
780    let mut h = domain_sep("ic-hashtree-fork");
781    h.update(&l[..]);
782    h.update(&r[..]);
783    h.finalize().into()
784}
785
786/// Identifiably hashes a leaf node's data. Used for hashing [HashTreeNode::Leaf].
787pub fn leaf_hash(data: &[u8]) -> Hash {
788    let mut h = domain_sep("ic-hashtree-leaf");
789    h.update(data);
790    h.finalize().into()
791}
792
793/// Identifiably hashes a label for this branch. Used for hashing [HashTreeNode::Labeled].
794pub fn labeled_hash(label: &[u8], content_hash: &Hash) -> Hash {
795    let mut h = domain_sep("ic-hashtree-labeled");
796    h.update(label);
797    h.update(&content_hash[..]);
798    h.finalize().into()
799}
800
801fn domain_sep(s: &str) -> sha2::Sha256 {
802    let buf: [u8; 1] = [s.len() as u8];
803    let mut h = sha2::Sha256::new();
804    h.update(&buf[..]);
805    h.update(s.as_bytes());
806    h
807}
808
809#[cfg(test)]
810mod tests;
ic_certification/hash_tree/mod.rs

ic_certification/hash_tree/
mod.rs
