didbot_data/

cid.rs

//! Content identifiers, decoded rather than glanced at.
//!
//! `didbot_schema::format::cid` already checks CID *strings*, and it
//! deliberately does not decode: a client can write any CID into a record and
//! this server dereferences none of them, so the lenient alphabet-and-length
//! rule atproto specifies is the right check at that boundary. This type is
//! for the other direction. To encode a link into DAG-CBOR you need the CID's
//! bytes, and to know that two links are the same link you need to compare
//! them; neither is answerable from the string.
//!
//! What atproto permits is a narrow slice of what a CID can be, and all of it
//! is enforced here, because a value this crate cannot re-encode byte for byte
//! is a value it must not accept:
//!
//! * version 1. CIDv0 is a valid IPFS identifier, is base58 with no multibase
//!   prefix at all, and is not permitted in atproto.
//! * the multibase is base32, lowercase, unpadded — the `b` prefix. Another
//!   multibase would decode to the same bytes and print back differently.
//! * the multihash is sha-256, 32 bytes.
//! * the codec is DAG-CBOR or raw. Everything atproto links to is one or the
//!   other: a record or a blob.

use std::fmt::Write as _;

use sha2::{Digest, Sha256};

use crate::encoding::{base32_decode, base32_encode, DecodeError};

/// The multicodec for DAG-CBOR, which is what a link to a record carries.
pub const DAG_CBOR: u64 = 0x71;

/// The multicodec for raw bytes, which is what a link to a blob carries.
pub const RAW: u64 = 0x55;

/// The multihash code for sha-256.
const SHA2_256: u64 = 0x12;

/// How long a sha-256 digest is.
const DIGEST_LENGTH: u64 = 32;

/// The multibase prefix for lowercase unpadded base32.
const BASE32_PREFIX: char = 'b';

/// Why a string or a byte sequence is not a CID this crate can use.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum CidError {
    /// Empty, so there is not even a multibase prefix.
    #[error("a cid cannot be empty")]
    Empty,
    /// A multibase other than lowercase base32.
    #[error("multibase {0:?} is not the lowercase base32 atproto requires")]
    Multibase(char),
    /// The base32 body did not decode.
    #[error("cid is not valid base32: {0}")]
    NotBase32(#[from] DecodeError),
    /// A varint that ran off the end of the input, or one too long to be a
    /// `u64`.
    #[error("truncated or oversized varint in cid")]
    BadVarint,
    /// A CID version other than 1, which includes every CIDv0.
    #[error("cid version {0} is not supported; atproto requires version 1")]
    Version(u64),
    /// A codec other than DAG-CBOR or raw.
    #[error("cid codec {0:#x} is neither dag-cbor nor raw")]
    Codec(u64),
    /// A multihash that is not a 32-byte sha-256.
    #[error("cid multihash {code:#x}/{length} is not a 32-byte sha-256")]
    Multihash {
        /// The multihash function code that was found.
        code: u64,
        /// The digest length that was found.
        length: u64,
    },
    /// Bytes after the digest, or fewer than the digest claimed.
    #[error("cid digest is {found} bytes, not the {expected} its multihash declares")]
    DigestLength {
        /// How many bytes actually followed the multihash header.
        found: usize,
        /// How many the header said there would be.
        expected: usize,
    },
}

/// A content identifier, held as the bytes it hashes and prints from.
///
/// The binary form is the canonical one and the string is derived from it, not
/// the other way around: a CID that came in as a string and goes out as one
/// goes out identical, because there is only one string for these bytes.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Cid {
    /// Version, codec and multihash, concatenated — the multibase payload.
    bytes: Vec<u8>,
    /// The codec, parsed out so a caller can ask without re-reading varints.
    codec: u64,
}

impl Cid {
    /// The CID of a DAG-CBOR block: sha-256 over exactly these bytes.
    ///
    /// This is the whole reason the encoder has to be canonical. The identity
    /// of a record is the hash of its encoding, so two encoders that disagree
    /// about map order or integer width give the same record two identities,
    /// and every other implementation would be right to say ours is the wrong
    /// one.
    pub fn of_dag_cbor(block: &[u8]) -> Self {
        Self::of_block(DAG_CBOR, block)
    }

    /// The CID of a raw block, which is what a blob is referenced by.
    pub fn of_raw(block: &[u8]) -> Self {
        Self::of_block(RAW, block)
    }

    /// Builds a CID over `block` under `codec`.
    fn of_block(codec: u64, block: &[u8]) -> Self {
        let digest = Sha256::digest(block);
        let mut bytes = Vec::with_capacity(4 + digest.len());
        write_varint(&mut bytes, 1);
        write_varint(&mut bytes, codec);
        write_varint(&mut bytes, SHA2_256);
        write_varint(&mut bytes, DIGEST_LENGTH);
        bytes.extend_from_slice(&digest);
        Self { bytes, codec }
    }

    /// Parses the string form: `b` followed by lowercase base32.
    ///
    /// ```
    /// use didbot_data::Cid;
    /// let cid = Cid::parse("bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a").unwrap();
    /// assert_eq!(cid.to_string(), "bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a");
    /// assert!(Cid::parse("QmbWqxBEKC3P8tqsKc98xmWNzrzDtRLMiMPL8wBuTGsMnR").is_err());
    /// ```
    pub fn parse(text: &str) -> Result<Self, CidError> {
        let mut chars = text.chars();
        let prefix = chars.next().ok_or(CidError::Empty)?;
        if prefix != BASE32_PREFIX {
            return Err(CidError::Multibase(prefix));
        }
        Self::from_bytes(&base32_decode(chars.as_str())?)
    }

    /// Parses the binary form, which is what a DAG-CBOR link tag carries.
    pub fn from_bytes(bytes: &[u8]) -> Result<Self, CidError> {
        let mut rest = bytes;
        let version = read_varint(&mut rest)?;
        if version != 1 {
            return Err(CidError::Version(version));
        }
        let codec = read_varint(&mut rest)?;
        if codec != DAG_CBOR && codec != RAW {
            return Err(CidError::Codec(codec));
        }
        let code = read_varint(&mut rest)?;
        let length = read_varint(&mut rest)?;
        if code != SHA2_256 || length != DIGEST_LENGTH {
            return Err(CidError::Multihash { code, length });
        }
        if rest.len() as u64 != length {
            return Err(CidError::DigestLength {
                found: rest.len(),
                expected: length as usize,
            });
        }
        Ok(Self {
            bytes: bytes.to_vec(),
            codec,
        })
    }

    /// Reads a CID off the front of a byte stream, leaving the rest.
    ///
    /// A CID is self-delimiting — the multihash declares its own digest
    /// length — which is what lets a CAR file put one immediately before a
    /// block with no length prefix between them. [`Cid::from_bytes`] is the
    /// whole-slice form and refuses a trailing byte; this one is the streaming
    /// form and hands the trailing bytes back.
    ///
    /// ```
    /// use didbot_data::Cid;
    ///
    /// let cid = Cid::of_raw(b"a block");
    /// let mut framed = cid.as_bytes().to_vec();
    /// framed.extend_from_slice(b"a block");
    /// let mut rest = framed.as_slice();
    /// assert_eq!(Cid::read(&mut rest).unwrap(), cid);
    /// assert_eq!(rest, b"a block");
    /// ```
    pub fn read(input: &mut &[u8]) -> Result<Self, CidError> {
        let whole = *input;
        let mut rest: &[u8] = whole;
        let version = read_varint(&mut rest)?;
        if version != 1 {
            return Err(CidError::Version(version));
        }
        let codec = read_varint(&mut rest)?;
        if codec != DAG_CBOR && codec != RAW {
            return Err(CidError::Codec(codec));
        }
        let code = read_varint(&mut rest)?;
        let length = read_varint(&mut rest)?;
        if code != SHA2_256 || length != DIGEST_LENGTH {
            return Err(CidError::Multihash { code, length });
        }
        let digest = usize::try_from(length).unwrap_or(usize::MAX);
        if rest.len() < digest {
            return Err(CidError::DigestLength {
                found: rest.len(),
                expected: digest,
            });
        }
        let taken = whole.len() - rest.len() + digest;
        *input = &whole[taken..];
        Ok(Self {
            bytes: whole[..taken].to_vec(),
            codec,
        })
    }

    /// The CID these bytes have under `codec`, which is how a reader checks
    /// that a block is the one it was handed under a name.
    ///
    /// The codec comes from the name being checked rather than from the
    /// caller's expectation: a block is either the bytes its CID says it is
    /// or it is not, and which codec that CID declares is part of the claim.
    #[must_use]
    pub fn of_block_under(codec: u64, block: &[u8]) -> Self {
        Self::of_block(codec, block)
    }

    /// The binary form: version, codec and multihash, with no multibase
    /// prefix.
    pub fn as_bytes(&self) -> &[u8] {
        &self.bytes
    }

    /// Which of the two permitted codecs this CID names.
    pub fn codec(&self) -> u64 {
        self.codec
    }
}

/// A raw-block CID computed over bytes that arrive a chunk at a time.
///
/// [`Cid::of_raw`] needs the whole block in hand, which is the one thing a
/// blob upload must never have: a personal data server that buffers a body
/// before it hashes it is holding the whole file in memory to learn its name
/// (a known defect in jacquard's `uploadBlob`). This is the same
/// hash, fed incrementally, so the bytes can go to their destination as they
/// arrive and the name falls out at the end.
///
/// It counts as it hashes, because the size is the other half of a blob
/// reference and a caller that tracked it separately could disagree with the
/// bytes that were actually hashed.
///
/// ```
/// use didbot_data::{Cid, RawHasher};
/// let mut hasher = RawHasher::new();
/// hasher.update(b"quernstone");
/// hasher.update(b"-farthingale");
/// let (cid, size) = hasher.finish();
/// assert_eq!(cid, Cid::of_raw(b"quernstone-farthingale"));
/// assert_eq!(size, 22);
/// ```
#[derive(Debug, Clone, Default)]
pub struct RawHasher {
    digest: Sha256,
    size: u64,
}

impl RawHasher {
    /// A hasher over nothing yet.
    pub fn new() -> Self {
        Self::default()
    }

    /// Folds in the next chunk.
    pub fn update(&mut self, chunk: &[u8]) {
        self.digest.update(chunk);
        self.size = self.size.saturating_add(chunk.len() as u64);
    }

    /// How many bytes have been folded in so far.
    ///
    /// Readable mid-stream so a caller enforcing a size limit can stop at the
    /// byte that breaks it rather than after the body has been written out.
    pub fn size(&self) -> u64 {
        self.size
    }

    /// The CID of everything folded in, and how much that was.
    pub fn finish(self) -> (Cid, u64) {
        let digest = self.digest.finalize();
        let mut bytes = Vec::with_capacity(4 + digest.len());
        write_varint(&mut bytes, 1);
        write_varint(&mut bytes, RAW);
        write_varint(&mut bytes, SHA2_256);
        write_varint(&mut bytes, DIGEST_LENGTH);
        bytes.extend_from_slice(&digest);
        (Cid { bytes, codec: RAW }, self.size)
    }
}

impl std::fmt::Display for Cid {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_char(BASE32_PREFIX)?;
        f.write_str(&base32_encode(&self.bytes))
    }
}

/// Appends an unsigned LEB128 varint, the multiformats encoding.
fn write_varint(out: &mut Vec<u8>, mut value: u64) {
    while value >= 0x80 {
        out.push((value as u8) | 0x80);
        value >>= 7;
    }
    out.push(value as u8);
}

/// Reads an unsigned LEB128 varint, advancing `input` past it.
///
/// Nine continuation bytes is already more than a `u64` holds, so the length
/// cap is what stops a hostile string from being read forever.
///
/// The encoding must also be minimal, which multiformats requires of an
/// unsigned varint and which is not a tidiness here. A [`Cid`] keeps the bytes
/// it was read from and prints from them, so a version written `81 00` rather
/// than `01` is a second byte sequence, a second string and a second `Cid`
/// that compares unequal — for one block, with one digest. The rule is that
/// the last group of a multi-byte varint has to carry something, so a
/// terminating zero group after a continuation byte is refused.
fn read_varint(input: &mut &[u8]) -> Result<u64, CidError> {
    let mut value: u64 = 0;
    for index in 0..10 {
        let byte = *input.first().ok_or(CidError::BadVarint)?;
        *input = &input[1..];
        let payload = u64::from(byte & 0x7f);
        value |= payload
            .checked_shl(index * 7)
            .filter(|shifted| shifted >> (index * 7) == payload)
            .ok_or(CidError::BadVarint)?;
        if byte & 0x80 == 0 {
            if index > 0 && payload == 0 {
                return Err(CidError::BadVarint);
            }
            return Ok(value);
        }
    }
    Err(CidError::BadVarint)
}

#[cfg(test)]
mod tests {
    use super::*;

    /// The `$link` in the upstream data-model fixtures.
    const FIXTURE: &str = "bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a";

    #[test]
    fn a_parsed_cid_prints_back_identically() {
        assert_eq!(Cid::parse(FIXTURE).unwrap().to_string(), FIXTURE);
    }

    #[test]
    fn the_binary_form_opens_with_version_and_codec() {
        let cid = Cid::parse(FIXTURE).unwrap();
        assert_eq!(&cid.as_bytes()[..4], &[0x01, 0x71, 0x12, 0x20]);
        assert_eq!(cid.codec(), DAG_CBOR);
    }

    #[test]
    fn a_raw_blob_reference_parses_and_keeps_its_codec() {
        let cid =
            Cid::parse("bafkreiccldh766hwcnuxnf2wh6jgzepf2nlu2lvcllt63eww5p6chi4ity").unwrap();
        assert_eq!(cid.codec(), RAW);
    }

    #[test]
    fn hashing_a_block_agrees_with_the_string_form() {
        // The empty DAG-CBOR map, `a0`, has a CID every implementation agrees
        // on; it is the identity of an empty record.
        assert_eq!(
            Cid::of_dag_cbor(&[0xa0]).to_string(),
            "bafyreigbtj4x7ip5legnfznufuopl4sg4knzc2cof6duas4b3q2fy6swua"
        );
    }

    #[test]
    fn a_cid_v0_is_refused_before_anything_is_decoded() {
        assert_eq!(
            Cid::parse("QmbWqxBEKC3P8tqsKc98xmWNzrzDtRLMiMPL8wBuTGsMnR"),
            Err(CidError::Multibase('Q'))
        );
    }

    #[test]
    fn the_bogus_cid_from_the_vectors_is_refused() {
        assert!(Cid::parse(".").is_err());
    }

    #[test]
    fn a_truncated_digest_is_refused() {
        let mut bytes = Cid::parse(FIXTURE).unwrap().as_bytes().to_vec();
        bytes.pop();
        assert_eq!(
            Cid::from_bytes(&bytes),
            Err(CidError::DigestLength {
                found: 31,
                expected: 32
            })
        );
    }

    #[test]
    fn an_unsupported_codec_is_refused() {
        // 0x70 is dag-pb, which is what a CIDv0 would have been.
        let cid = Cid::of_dag_cbor(&[0xa0]);
        let mut bytes = cid.as_bytes().to_vec();
        bytes[1] = 0x70;
        assert_eq!(Cid::from_bytes(&bytes), Err(CidError::Codec(0x70)));
    }

    #[test]
    fn varints_round_trip_across_the_whole_range() {
        for value in [0u64, 1, 0x7f, 0x80, 0x3fff, 0x4000, u64::MAX] {
            let mut bytes = Vec::new();
            write_varint(&mut bytes, value);
            let mut input = bytes.as_slice();
            assert_eq!(read_varint(&mut input), Ok(value));
            assert!(input.is_empty());
        }
    }

    /// A varint written wider than it needs gives one block two names.
    ///
    /// Asserted as the round trip rather than as an error kind: a `Cid` keeps
    /// the bytes it read and prints from them, so anything `from_bytes`
    /// accepts must serialise back to what it was handed. The named error
    /// comes after, so a regression fails on the property and not on the
    /// spelling of the refusal.
    #[test]
    fn a_padded_varint_would_be_a_second_name_for_one_block() {
        let canonical = Cid::of_dag_cbor(&[0xa0]);
        // Version 1 written `81 00`; codec, multihash and digest unchanged.
        let mut padded = vec![0x81, 0x00];
        padded.extend_from_slice(&canonical.as_bytes()[1..]);
        if let Ok(read) = Cid::from_bytes(&padded) {
            assert_eq!(
                read.to_string(),
                canonical.to_string(),
                "{read} is a second name for the block {canonical} names"
            );
        }
        assert_eq!(Cid::from_bytes(&padded), Err(CidError::BadVarint));

        // The same padding in the codec, which a reader checks by value and
        // is least likely to check the width of.
        let mut padded_codec = vec![0x01, 0xf1, 0x00];
        padded_codec.extend_from_slice(&canonical.as_bytes()[2..]);
        assert_eq!(Cid::from_bytes(&padded_codec), Err(CidError::BadVarint));

        // The canonical spelling still reads, so the rule refuses a form
        // rather than the field.
        assert_eq!(Cid::from_bytes(canonical.as_bytes()), Ok(canonical));
    }

    /// The same refusal reaches a link inside a block, which is where a
    /// padded CID would actually arrive: a peer's record or tree node.
    #[test]
    fn a_link_carrying_a_padded_cid_is_not_a_link() {
        let canonical = Cid::of_dag_cbor(&[0xa0]);
        let mut padded = vec![0x81, 0x00];
        padded.extend_from_slice(&canonical.as_bytes()[1..]);
        // Tag 42 over a byte string of the identity prefix and those bytes.
        let mut block = vec![0xd8, 0x2a, 0x58, (padded.len() + 1) as u8, 0x00];
        block.extend_from_slice(&padded);
        assert!(
            crate::dag_cbor::decode(&block).is_err(),
            "a block linking through a padded cid decoded"
        );
    }

    #[test]
    fn a_varint_with_no_end_is_refused_rather_than_read_forever() {
        let mut input: &[u8] = &[0x80; 12];
        assert_eq!(read_varint(&mut input), Err(CidError::BadVarint));
    }
}