Skip to main content

publet_core/
cid.rs

1//! Content identifiers (R2, Section 4.2).
2//!
3//! R2 requires every object to be named by the hash of its canonical
4//! serialization, and retrieved bytes to be verified against the name they
5//! were asked for. [`Cid::of`] does the naming; [`Cid::verifies`] and
6//! `Object::verify` do the checking, and nothing downstream accepts bytes
7//! that have not been through one of them.
8//!
9//! A CID names an object by the hash of its canonical serialization:
10//!
11//! ```text
12//! pub:<hash-algorithm-id>:<base32-lower-no-pad(digest)>
13//! ```
14//!
15//! The algorithm identifier travels in-band so that a future migration is a
16//! new identifier rather than a flag day (Section 15).
17//!
18//! # Examples
19//!
20//! ```
21//! use publet_core::{cbor, Cid, HashAlg};
22//!
23//! let bytes = cbor::encode(&cbor::Value::Text("hello".into()));
24//! let cid = Cid::of(&bytes, HashAlg::Sha2_256);
25//! assert!(cid.to_string().starts_with("pub:sha2-256:"));
26//! assert!(cid.verifies(&bytes));
27//! ```
28
29use std::fmt;
30use std::str::FromStr;
31
32use sha2::{Digest as _, Sha256};
33use thiserror::Error;
34
35/// A hash algorithm usable for content identifiers.
36///
37/// `sha2-256` is required by Section 4.2. Further algorithms are added as
38/// variants rather than as a trait object, because the set is small, closed
39/// at any given protocol version, and exhaustively matched.
40#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
41#[non_exhaustive]
42pub enum HashAlg {
43    /// SHA-256, required by Section 4.2.
44    Sha2_256,
45}
46
47impl HashAlg {
48    /// The in-band identifier used in a CID.
49    ///
50    /// # Example
51    ///
52    /// ```
53    /// use publet_core::HashAlg;
54    ///
55    /// assert_eq!(HashAlg::Sha2_256.id(), "sha2-256");
56    /// ```
57    #[must_use]
58    pub fn id(self) -> &'static str {
59        match self {
60            Self::Sha2_256 => "sha2-256",
61        }
62    }
63
64    /// Resolve an in-band identifier.
65    ///
66    /// # Example
67    ///
68    /// ```
69    /// use publet_core::HashAlg;
70    ///
71    /// assert_eq!(HashAlg::from_id("sha2-256"), Some(HashAlg::Sha2_256));
72    /// // An algorithm this implementation does not know.
73    /// assert_eq!(HashAlg::from_id("md5"), None);
74    /// ```
75    #[must_use]
76    pub fn from_id(id: &str) -> Option<Self> {
77        match id {
78            "sha2-256" => Some(Self::Sha2_256),
79            _ => None,
80        }
81    }
82
83    /// Hash `bytes` with this algorithm.
84    ///
85    /// # Example
86    ///
87    /// ```
88    /// use publet_core::HashAlg;
89    ///
90    /// // SHA-256 of the empty string.
91    /// let digest = HashAlg::Sha2_256.digest(b"");
92    /// assert_eq!(digest.len(), 32);
93    /// assert_eq!(digest[..4], [0xe3, 0xb0, 0xc4, 0x42]);
94    /// ```
95    #[must_use]
96    pub fn digest(self, bytes: &[u8]) -> Vec<u8> {
97        match self {
98            Self::Sha2_256 => Sha256::digest(bytes).to_vec(),
99        }
100    }
101}
102
103/// A content identifier.
104#[derive(Debug, Clone, PartialEq, Eq, Hash)]
105pub struct Cid {
106    alg: HashAlg,
107    digest: Vec<u8>,
108}
109
110impl Cid {
111    /// Compute the identifier of `bytes` under `alg`.
112    ///
113    /// `bytes` must already be canonical; this does not check that, because
114    /// callers holding a decoded object have checked it already and callers
115    /// holding raw input should use [`crate::cbor::decode`] first.
116    ///
117    /// # Example
118    ///
119    /// ```
120    /// use publet_core::{Cid, HashAlg};
121    ///
122    /// let cid = Cid::of(b"", HashAlg::Sha2_256);
123    /// assert_eq!(
124    ///     cid.to_string(),
125    ///     "pub:sha2-256:4oymiquy7qobjgx36tejs35zeqt24qpemsnzgtfeswmrw6csxbkq",
126    /// );
127    /// // The same bytes always have the same identifier.
128    /// assert_eq!(Cid::of(b"", HashAlg::Sha2_256), cid);
129    /// ```
130    #[must_use]
131    pub fn of(bytes: &[u8], alg: HashAlg) -> Self {
132        Self {
133            alg,
134            digest: alg.digest(bytes),
135        }
136    }
137
138    /// Construct from a digest computed elsewhere.
139    ///
140    /// Merkle roots are digests rather than hashes of any single byte
141    /// string, so they cannot be produced by [`Cid::of`]. Returns `None`
142    /// when the digest length does not match the algorithm.
143    ///
144    /// # Example
145    ///
146    /// ```
147    /// use publet_core::{Cid, HashAlg};
148    ///
149    /// let digest = HashAlg::Sha2_256.digest(b"");
150    /// let cid = Cid::from_digest(HashAlg::Sha2_256, &digest).unwrap();
151    /// assert_eq!(cid, Cid::of(b"", HashAlg::Sha2_256));
152    ///
153    /// // A digest of the wrong length for the algorithm is refused.
154    /// assert_eq!(Cid::from_digest(HashAlg::Sha2_256, &digest[..31]), None);
155    /// ```
156    #[must_use]
157    pub fn from_digest(alg: HashAlg, digest: &[u8]) -> Option<Self> {
158        if digest.len() != alg.digest(&[]).len() {
159            return None;
160        }
161        Some(Self {
162            alg,
163            digest: digest.to_vec(),
164        })
165    }
166
167    /// The algorithm this identifier uses.
168    ///
169    /// # Example
170    ///
171    /// ```
172    /// use publet_core::{Cid, HashAlg};
173    ///
174    /// let cid: Cid = "pub:sha2-256:4oymiquy7qobjgx36tejs35zeqt24qpemsnzgtfeswmrw6csxbkq".parse()?;
175    /// assert_eq!(cid.alg(), HashAlg::Sha2_256);
176    /// # Ok::<(), publet_core::CidError>(())
177    /// ```
178    #[must_use]
179    pub fn alg(&self) -> HashAlg {
180        self.alg
181    }
182
183    /// The raw digest.
184    ///
185    /// # Example
186    ///
187    /// ```
188    /// use publet_core::{Cid, HashAlg};
189    ///
190    /// let cid = Cid::of(b"", HashAlg::Sha2_256);
191    /// assert_eq!(cid.digest(), HashAlg::Sha2_256.digest(b"").as_slice());
192    /// ```
193    #[must_use]
194    pub fn digest(&self) -> &[u8] {
195        &self.digest
196    }
197
198    /// Whether `bytes` hash to this identifier.
199    ///
200    /// Section 4.2 requires a recipient to verify retrieved bytes against
201    /// the identifier they asked for before parsing them.
202    ///
203    /// # Example
204    ///
205    /// ```
206    /// use publet_core::{Cid, HashAlg};
207    ///
208    /// let cid = Cid::of(b"the bytes asked for", HashAlg::Sha2_256);
209    /// assert!(cid.verifies(b"the bytes asked for"));
210    /// // Bytes a peer substituted do not match the identifier asked for.
211    /// assert!(!cid.verifies(b"other bytes"));
212    /// ```
213    #[must_use]
214    pub fn verifies(&self, bytes: &[u8]) -> bool {
215        self.alg.digest(bytes) == self.digest
216    }
217}
218
219impl fmt::Display for Cid {
220    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
221        write!(f, "pub:{}:{}", self.alg.id(), base32_lower(&self.digest))
222    }
223}
224
225/// Reasons a string is not a well-formed CID.
226#[derive(Debug, Error, PartialEq, Eq, Clone)]
227#[non_exhaustive]
228pub enum CidError {
229    /// The `pub:` scheme prefix was absent.
230    #[error("not a CID: expected a `pub:` prefix")]
231    MissingScheme,
232    /// The three-part structure was not present.
233    #[error("not a CID: expected pub:<algorithm>:<digest>")]
234    Malformed,
235    /// The algorithm identifier is not implemented.
236    #[error("unknown hash algorithm: {0}")]
237    UnknownAlgorithm(String),
238    /// The digest was not lower-case unpadded base32.
239    #[error("invalid digest encoding: {0}")]
240    InvalidDigest(&'static str),
241    /// The digest length did not match the algorithm.
242    #[error("digest length {got} does not match {alg} (expected {expected})")]
243    WrongDigestLength {
244        /// The algorithm named in the identifier.
245        alg: &'static str,
246        /// Expected digest length in bytes.
247        expected: usize,
248        /// Length actually decoded.
249        got: usize,
250    },
251}
252
253impl FromStr for Cid {
254    type Err = CidError;
255
256    fn from_str(s: &str) -> Result<Self, Self::Err> {
257        let rest = s.strip_prefix("pub:").ok_or(CidError::MissingScheme)?;
258        let (alg_id, digest_text) = rest.split_once(':').ok_or(CidError::Malformed)?;
259        if alg_id.is_empty() || digest_text.is_empty() {
260            return Err(CidError::Malformed);
261        }
262        let alg = HashAlg::from_id(alg_id)
263            .ok_or_else(|| CidError::UnknownAlgorithm(alg_id.to_owned()))?;
264        let digest = base32_lower_decode(digest_text)?;
265        let expected = alg.digest(&[]).len();
266        if digest.len() != expected {
267            return Err(CidError::WrongDigestLength {
268                alg: alg.id(),
269                expected,
270                got: digest.len(),
271            });
272        }
273        Ok(Self { alg, digest })
274    }
275}
276
277const ALPHABET: &[u8; 32] = b"abcdefghijklmnopqrstuvwxyz234567";
278
279/// RFC 4648 base32, lower case, no padding.
280///
281/// Every index below is masked to five bits and the alphabet has exactly 32
282/// entries, so the lookups cannot be out of range. A fallback character
283/// would silently corrupt a digest, which is worse than an annotated index.
284#[allow(clippy::indexing_slicing)]
285fn base32_lower(data: &[u8]) -> String {
286    let mut out = String::with_capacity(data.len().div_ceil(5) * 8);
287    let mut acc: u32 = 0;
288    let mut bits = 0u32;
289    for &byte in data {
290        acc = (acc << 8) | u32::from(byte);
291        bits += 8;
292        while bits >= 5 {
293            bits -= 5;
294            let index = ((acc >> bits) & 0x1f) as usize;
295            out.push(char::from(ALPHABET[index]));
296        }
297    }
298    if bits > 0 {
299        let index = ((acc << (5 - bits)) & 0x1f) as usize;
300        out.push(char::from(ALPHABET[index]));
301    }
302    out
303}
304
305fn base32_lower_decode(text: &str) -> Result<Vec<u8>, CidError> {
306    let mut out = Vec::with_capacity(text.len().div_ceil(8) * 5);
307    let mut acc: u32 = 0;
308    let mut bits = 0u32;
309    for ch in text.chars() {
310        let value = match ch {
311            'a'..='z' => u32::from(ch as u8 - b'a'),
312            '2'..='7' => u32::from(ch as u8 - b'2') + 26,
313            'A'..='Z' => {
314                return Err(CidError::InvalidDigest("digests are lower case"));
315            }
316            '=' => return Err(CidError::InvalidDigest("digests are unpadded")),
317            _ => return Err(CidError::InvalidDigest("not a base32 character")),
318        };
319        acc = (acc << 5) | value;
320        bits += 5;
321        if bits >= 8 {
322            bits -= 8;
323            // Masking to 8 bits makes the narrowing exact.
324            #[allow(clippy::cast_possible_truncation)]
325            out.push(((acc >> bits) & 0xff) as u8);
326        }
327    }
328    // The bits left after the last whole byte are padding, and RFC 4648
329    // encoders write them as zero. Accepting others would give one digest
330    // many spellings, and an identifier more than one text form.
331    if acc & ((1 << bits) - 1) != 0 {
332        return Err(CidError::InvalidDigest(
333            "non-zero bits after the digest; an identifier has one text form",
334        ));
335    }
336    Ok(out)
337}
338
339#[cfg(test)]
340mod tests {
341    use super::*;
342
343    // covers: Cid, Cid::of
344    #[test]
345    fn round_trips_through_text() {
346        let cid = Cid::of(b"hello world", HashAlg::Sha2_256);
347        let text = cid.to_string();
348        assert_eq!(text.parse::<Cid>().unwrap(), cid);
349    }
350
351    #[test]
352    fn base32_matches_rfc4648_vectors_lowercased_unpadded() {
353        // RFC 4648 section 10, with padding removed and lower-cased.
354        assert_eq!(base32_lower(b"f"), "my");
355        assert_eq!(base32_lower(b"fo"), "mzxq");
356        assert_eq!(base32_lower(b"foo"), "mzxw6");
357        assert_eq!(base32_lower(b"foob"), "mzxw6yq");
358        assert_eq!(base32_lower(b"fooba"), "mzxw6ytb");
359        assert_eq!(base32_lower(b"foobar"), "mzxw6ytboi");
360    }
361
362    // covers: Cid
363    #[test]
364    fn rejects_malformed_identifiers() {
365        assert_eq!("nope".parse::<Cid>(), Err(CidError::MissingScheme));
366        assert_eq!("pub:sha2-256".parse::<Cid>(), Err(CidError::Malformed));
367        assert!(matches!(
368            "pub:md5:aaaa".parse::<Cid>(),
369            Err(CidError::UnknownAlgorithm(_))
370        ));
371        assert!(matches!(
372            "pub:sha2-256:MZXW6".parse::<Cid>(),
373            Err(CidError::InvalidDigest(_))
374        ));
375        assert!(matches!(
376            "pub:sha2-256:mzxw6".parse::<Cid>(),
377            Err(CidError::WrongDigestLength { .. })
378        ));
379    }
380
381    // covers: Cid::of, Cid::verifies
382    #[test]
383    fn verifies_only_the_bytes_it_names() {
384        let cid = Cid::of(b"a", HashAlg::Sha2_256);
385        assert!(cid.verifies(b"a"));
386        assert!(!cid.verifies(b"b"));
387    }
388}