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}