Skip to main content

scionic_merkletree/
hash.rs

1//! A hash, and the root that a tree is known by.
2
3use crate::encoding::{base32_lower, base32_lower_decode, hex_lower, hex_lower_decode, sha256};
4use crate::{Error, Result};
5use std::fmt;
6use std::str::FromStr;
7
8/// A SHA-256 hash: of a chunk's bytes, or of the bytes that describe a file,
9/// a folder or a tree.
10#[derive(Clone, Copy, Eq, Hash, Ord, PartialEq, PartialOrd)]
11pub struct Hash([u8; 32]);
12
13impl Hash {
14    /// What an empty list has in place of a hash.
15    pub const ZERO: Self = Self([0; 32]);
16
17    pub const fn from_bytes(bytes: [u8; 32]) -> Self {
18        Self(bytes)
19    }
20
21    pub const fn as_bytes(&self) -> &[u8; 32] {
22        &self.0
23    }
24
25    /// The SHA-256 of `bytes`.
26    pub fn of(bytes: &[u8]) -> Self {
27        Self(sha256(bytes))
28    }
29
30    /// Reads a hash from exactly 32 bytes.
31    pub fn from_slice(bytes: &[u8]) -> Result<Self> {
32        <[u8; 32]>::try_from(bytes)
33            .map(Self)
34            .map_err(|_| Error::InvalidData {
35                detail: "a hash is not 32 bytes".to_owned(),
36            })
37    }
38
39    /// The hash as 64 lowercase hex digits.
40    pub fn to_hex(&self) -> String {
41        hex_lower(&self.0)
42    }
43
44    /// Reads 64 lowercase hex digits.
45    pub fn from_hex(text: &str) -> Result<Self> {
46        let mut bytes = [0_u8; 32];
47        hex_lower_decode(text, &mut bytes)?;
48        Ok(Self(bytes))
49    }
50}
51
52impl fmt::Display for Hash {
53    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
54        f.write_str(&self.to_hex())
55    }
56}
57
58impl fmt::Debug for Hash {
59    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
60        write!(f, "Hash({})", self.to_hex())
61    }
62}
63
64impl From<[u8; 32]> for Hash {
65    fn from(bytes: [u8; 32]) -> Self {
66        Self(bytes)
67    }
68}
69
70/// What a root's text form starts with, before the hash: CID version 1, raw
71/// content, SHA-256, 32 bytes.
72const ROOT_PREFIX: [u8; 4] = [0x01, 0x55, 0x12, 0x20];
73
74/// The root of a tree: the hash of its record. It is what a tree is known by.
75///
76/// Written out, a root is a CID that begins `bafkrei`.
77#[derive(Clone, Copy, Eq, Hash, Ord, PartialEq, PartialOrd)]
78pub struct Root(Hash);
79
80impl Root {
81    pub const fn from_hash(hash: Hash) -> Self {
82        Self(hash)
83    }
84
85    pub const fn as_hash(&self) -> &Hash {
86        &self.0
87    }
88
89    /// The root of the tree whose record is `record`.
90    pub fn of_record(record: &[u8]) -> Self {
91        Self(Hash::of(record))
92    }
93
94    /// The root as text.
95    pub fn to_text(&self) -> String {
96        let mut bytes = [0_u8; 36];
97        bytes[..4].copy_from_slice(&ROOT_PREFIX);
98        bytes[4..].copy_from_slice(self.0.as_bytes());
99        let mut text = String::with_capacity(59);
100        text.push('b');
101        text.push_str(&base32_lower(&bytes));
102        text
103    }
104
105    /// Reads a root from its text. Only the one way of writing a root is
106    /// read: any other spelling of the same bytes is refused.
107    pub fn parse(text: &str) -> Result<Self> {
108        let invalid = || Error::InvalidRoot {
109            value: text.chars().take(80).collect(),
110        };
111        let body = text.strip_prefix('b').ok_or_else(invalid)?;
112        let bytes = base32_lower_decode(body).map_err(|_| invalid())?;
113        if bytes.len() != 36 || bytes[..4] != ROOT_PREFIX {
114            return Err(invalid());
115        }
116        let root = Self(Hash::from_slice(&bytes[4..])?);
117        if root.to_text() != text {
118            return Err(invalid());
119        }
120        Ok(root)
121    }
122}
123
124impl fmt::Display for Root {
125    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
126        f.write_str(&self.to_text())
127    }
128}
129
130impl fmt::Debug for Root {
131    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
132        write!(f, "Root({})", self.to_text())
133    }
134}
135
136impl FromStr for Root {
137    type Err = Error;
138
139    fn from_str(text: &str) -> Result<Self> {
140        Self::parse(text)
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147
148    #[test]
149    fn a_hash_is_the_sha_256_of_the_bytes() {
150        assert_eq!(
151            Hash::of(b"abc").to_hex(),
152            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"
153        );
154        assert_eq!(
155            Hash::of(b"").to_hex(),
156            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
157        );
158    }
159
160    #[test]
161    fn a_hash_reads_back_from_its_hex() {
162        let hash = Hash::of(b"abc");
163        assert_eq!(Hash::from_hex(&hash.to_hex()).unwrap(), hash);
164        assert_eq!(format!("{hash}"), hash.to_hex());
165        assert!(Hash::from_hex(&hash.to_hex().to_uppercase()).is_err());
166        assert!(Hash::from_hex(&hash.to_hex()[..63]).is_err());
167        assert!(Hash::from_slice(&[0; 31]).is_err());
168    }
169
170    #[test]
171    fn a_root_is_written_as_a_cid_that_begins_bafkrei() {
172        let root = Root::of_record(b"abc");
173        let text = root.to_text();
174        assert_eq!(text.len(), 59);
175        assert!(text.starts_with("bafkrei"), "{text}");
176        // The CID of the raw bytes "abc", as other tools write it.
177        assert_eq!(
178            text,
179            "bafkreif2pall7dybz7vecqka3zo24irdwabwdi4wc55jznaq75q7eaavvu"
180        );
181        assert_eq!(Root::parse(&text).unwrap(), root);
182        assert_eq!(text.parse::<Root>().unwrap(), root);
183    }
184
185    #[test]
186    fn only_the_one_spelling_of_a_root_is_read() {
187        let text = Root::of_record(b"abc").to_text();
188        let old_layout = text.replacen("bafkrei", "bafirei", 1);
189        let mut longer = text.clone();
190        longer.push('a');
191        for other in [
192            text.to_uppercase(),
193            text[1..].to_owned(),
194            text[..58].to_owned(),
195            longer,
196            old_layout,
197            format!("{text}="),
198            String::new(),
199        ] {
200            assert!(Root::parse(&other).is_err(), "{other:?}");
201        }
202        // The last letter carries two bits that must be zero.
203        let mut bytes = text.into_bytes();
204        let last = bytes.len() - 1;
205        bytes[last] = if bytes[last] == b'b' { b'c' } else { b'b' };
206        let changed = String::from_utf8(bytes).unwrap();
207        assert!(Root::parse(&changed).is_err(), "{changed:?}");
208    }
209}