Skip to main content

hyprstream_pds/
car.rs

1//! CAR (Content Addressable aRchive) proof production and verification.
2//!
3//! A CAR file bundles a set of `(CID → block bytes)` pairs with a set of root
4//! CIDs, so a recipient can store and re-verify the blocks offline. atproto's
5//! `getRepo` / `getRecord` endpoints return CAR files; this module produces
6//! minimal CAR **proofs** — just enough blocks to verify one record against the
7//! signed commit.
8//!
9//! # CARv1 wire format (IPLD)
10//!
11//! ```text
12//! CARv1 := header-section block-section*
13//!   header-section := varint(len) ++ CBOR({ "version": 1, "roots": [CID,...] })
14//!   block-section  := varint(len) ++ CID ++ raw-block-bytes
15//! ```
16//! `len` is a unsigned-varint byte count of the *rest* of the section.
17//!
18//! # `verify_record_proof`
19//!
20//! [`verify_record_proof`] is the D5 untrusted-host check: given a (purported)
21//! signed commit, the account's `#atproto` P-256 verifying key, an MST inclusion
22//! path, and the record bytes, confirm (1) the commit signature, (2) the MST
23//! path leads from the commit's `data` root to the record's entry, and
24//! (3) the record's CID matches the entry's value.
25
26use anyhow::{anyhow, bail, ensure, Result};
27use p256::ecdsa::VerifyingKey;
28
29use crate::atproto_cbor::AtprotoRecord;
30use crate::cid::{read_uvarint, write_uvarint, Cid};
31use crate::commit::Commit;
32use crate::dag_cbor::DagCbor;
33use crate::mst::{NodeData, Proof};
34use crate::record::ModelRecord;
35
36/// Build a CARv1 byte blob containing the given root CIDs and `(cid → bytes)` blocks.
37///
38/// Like [`build_car_v1`] but returns each length-framed section as its own
39/// `Vec<u8>` — the header section first, then one entry per block — so the
40/// caller can stream them incrementally over HTTP without materializing the
41/// entire CAR into a single contiguous buffer.
42///
43/// Each returned `Vec<u8>` is a complete framed CAR section
44/// (`varint(len) ++ body`), safe to flush independently.
45pub fn build_car_v1_sections(roots: &[Cid], blocks: &[(Cid, Vec<u8>)]) -> Vec<Vec<u8>> {
46    let mut sections = Vec::with_capacity(1 + blocks.len());
47    let header_value = DagCbor::str_map([
48        ("version", DagCbor::Unsigned(1)),
49        (
50            "roots",
51            DagCbor::List(roots.iter().copied().map(DagCbor::Link).collect()),
52        ),
53    ]);
54    let header_bytes = header_value.encode();
55    sections.push(frame_section(&header_bytes));
56    for (cid, bytes) in blocks {
57        let mut section = Vec::with_capacity(cid.as_bytes().len() + bytes.len());
58        section.extend_from_slice(cid.as_bytes());
59        section.extend_from_slice(bytes);
60        sections.push(frame_section(&section));
61    }
62    sections
63}
64
65/// Build just the CARv1 header section (varint-framed CBOR `{version, roots}`).
66/// Useful for lazy/streaming CAR producers that emit the header first, then
67/// block sections one at a time.
68pub fn car_header_bytes(roots: &[Cid]) -> Vec<u8> {
69    let header_value = DagCbor::str_map([
70        ("version", DagCbor::Unsigned(1)),
71        (
72            "roots",
73            DagCbor::List(roots.iter().copied().map(DagCbor::Link).collect()),
74        ),
75    ]);
76    frame_section(&header_value.encode())
77}
78
79/// Build one length-framed CARv1 block section (`varint(len) ++ CID ++ raw`).
80/// Used by lazy/streaming CAR producers that encode blocks on demand.
81pub fn car_block_bytes(cid: Cid, raw: &[u8]) -> Vec<u8> {
82    let mut section = Vec::with_capacity(cid.as_bytes().len() + raw.len());
83    section.extend_from_slice(cid.as_bytes());
84    section.extend_from_slice(raw);
85    frame_section(&section)
86}
87
88fn frame_section(body: &[u8]) -> Vec<u8> {
89    let mut out = Vec::with_capacity(10 + body.len());
90    write_uvarint(body.len() as u64, &mut out);
91    out.extend_from_slice(body);
92    out
93}
94
95/// `blocks` need not be sorted; duplicates are harmless. The header's `roots`
96/// is taken verbatim from `roots`.
97pub fn build_car_v1(roots: &[Cid], blocks: &[(Cid, Vec<u8>)]) -> Vec<u8> {
98    let mut out = Vec::new();
99    // Header section: CBOR { "version": 1, "roots": [Link, ...] }
100    let header_value = DagCbor::str_map([
101        ("version", DagCbor::Unsigned(1)),
102        (
103            "roots",
104            DagCbor::List(roots.iter().copied().map(DagCbor::Link).collect()),
105        ),
106    ]);
107    let header_bytes = header_value.encode();
108    write_section(&mut out, &header_bytes);
109    // Block sections: varint(len) ++ CID ++ bytes
110    for (cid, bytes) in blocks {
111        let mut section = Vec::with_capacity(cid.as_bytes().len() + bytes.len());
112        section.extend_from_slice(cid.as_bytes());
113        section.extend_from_slice(bytes);
114        write_section(&mut out, &section);
115    }
116    out
117}
118
119/// Build a public AT Protocol CAR proof without changing the native CAR
120/// builder. Every block CID and byte payload is derived from the public
121/// canonical codec, including the CAR header.
122pub fn build_public_record_proof_car(
123    commit: &Commit,
124    path: &Proof,
125    node_blocks: &[(Cid, NodeData)],
126    record: &AtprotoRecord,
127) -> Result<Vec<u8>> {
128    commit.ensure_atproto_signature()?;
129    // Bind the supplied proof to both the signed commit root and this exact
130    // record before emitting any blocks. This rejects empty proofs and proofs
131    // copied from a different commit or record.
132    path.verify_atproto(&commit.data, &record.cid())?;
133    ensure_proof_record_key(path, record)?;
134
135    let commit_cid = commit.cid_atproto()?;
136    let mut blocks = vec![(commit_cid, commit.to_atproto_dag_cbor()?)];
137    let path_cids: std::collections::BTreeSet<Cid> = path
138        .path
139        .iter()
140        .map(|step| match step {
141            crate::mst::ProofStep::FoundAt(d, _)
142            | crate::mst::ProofStep::ThroughEntry(d, _)
143            | crate::mst::ProofStep::LeftSubtree(d) => d.cid_atproto(),
144        })
145        .collect::<Result<_>>()?;
146    let mut supplied_path_cids = std::collections::BTreeSet::new();
147    for (cid, data) in node_blocks {
148        ensure!(
149            data.cid_atproto()? == *cid,
150            "public MST block is labeled with a CID that does not match its bytes"
151        );
152        if path_cids.contains(cid) {
153            ensure!(
154                supplied_path_cids.insert(*cid),
155                "duplicate public MST block for proof path"
156            );
157            blocks.push((*cid, data.encode_atproto()?));
158        }
159    }
160    ensure!(
161        supplied_path_cids.len() == path_cids.len(),
162        "public proof CAR is missing an MST path block"
163    );
164    blocks.push((record.cid(), record.bytes().to_vec()));
165    build_car_v1_atproto(&[commit_cid], &blocks)
166}
167
168fn ensure_proof_record_key(path: &Proof, record: &AtprotoRecord) -> Result<()> {
169    let (data, index) = match path.path.last() {
170        Some(crate::mst::ProofStep::FoundAt(data, index)) => (data, *index),
171        _ => bail!("public MST proof has no terminal record entry"),
172    };
173    let mut key = Vec::new();
174    for entry in data.e.iter().take(index + 1) {
175        ensure!(
176            entry.p <= key.len(),
177            "public MST proof has an invalid key prefix length"
178        );
179        key.truncate(entry.p);
180        key.extend_from_slice(&entry.k);
181    }
182    let key = String::from_utf8(key).map_err(|_| anyhow!("public MST proof key is not UTF-8"))?;
183    ensure!(
184        key == format!("{}/{}", record.collection(), record.rkey().as_str()),
185        "public MST proof key does not match the supplied record"
186    );
187    Ok(())
188}
189
190/// Public AT Protocol CARv1 builder. The native builder remains unchanged.
191pub fn build_car_v1_atproto(roots: &[Cid], blocks: &[(Cid, Vec<u8>)]) -> Result<Vec<u8>> {
192    let header_value = DagCbor::str_map([
193        ("version", DagCbor::Unsigned(1)),
194        (
195            "roots",
196            DagCbor::List(roots.iter().copied().map(DagCbor::Link).collect()),
197        ),
198    ]);
199    let header_bytes = crate::atproto_cbor::encode(&header_value)?;
200    let mut out = Vec::new();
201    write_section(&mut out, &header_bytes);
202    for (cid, bytes) in blocks {
203        let mut section = Vec::with_capacity(cid.as_bytes().len() + bytes.len());
204        section.extend_from_slice(cid.as_bytes());
205        section.extend_from_slice(bytes);
206        write_section(&mut out, &section);
207    }
208    Ok(out)
209}
210
211fn write_section(out: &mut Vec<u8>, body: &[u8]) {
212    write_uvarint(body.len() as u64, out);
213    out.extend_from_slice(body);
214}
215
216/// Parse a CARv1 blob into `(roots, blocks)`. Used by tests / offline verifiers
217/// that read a fetched CAR.
218pub fn parse_car_v1(input: &[u8]) -> Result<(Vec<Cid>, Vec<(Cid, Vec<u8>)>)> {
219    let mut cursor = 0usize;
220    // Header section.
221    let (header_body, after_header) = read_section(input, cursor)?;
222    cursor = after_header;
223    let header_val = DagCbor::decode(header_body)?;
224    let version = header_val
225        .get("version")
226        .ok_or_else(|| anyhow!("CAR header missing 'version'"))?
227        .as_unsigned()?;
228    ensure!(
229        version == 1,
230        "only CARv1 is supported (got version {version})"
231    );
232    let roots_val = header_val
233        .get("roots")
234        .ok_or_else(|| anyhow!("CAR header missing 'roots'"))?
235        .as_list()?;
236    let mut roots = Vec::with_capacity(roots_val.len());
237    for r in roots_val {
238        roots.push(*r.as_link()?);
239    }
240    // Block sections.
241    let mut blocks = Vec::new();
242    while cursor < input.len() {
243        let (body, after) = read_section(input, cursor)?;
244        cursor = after;
245        // body = CID ++ raw-bytes. Parse the CID prefix.
246        let (cid, consumed) = parse_cid_prefix(body)?;
247        let raw = body[consumed..].to_vec();
248        blocks.push((cid, raw));
249    }
250    Ok((roots, blocks))
251}
252
253/// Parse a CAR whose header uses public AT canonical DAG-CBOR. Block framing is
254/// identical to [`parse_car_v1`]; callers decide how to decode each block.
255pub fn parse_car_v1_atproto(input: &[u8]) -> Result<(Vec<Cid>, Vec<(Cid, Vec<u8>)>)> {
256    let (header_body, mut cursor) = read_section(input, 0)?;
257    let header_val = crate::atproto_cbor::decode(header_body)?;
258    let version = header_val
259        .get("version")
260        .ok_or_else(|| anyhow!("CAR header missing 'version'"))?
261        .as_unsigned()?;
262    ensure!(
263        version == 1,
264        "only CARv1 is supported (got version {version})"
265    );
266    let roots_val = header_val
267        .get("roots")
268        .ok_or_else(|| anyhow!("CAR header missing 'roots'"))?
269        .as_list()?;
270    let roots = roots_val
271        .iter()
272        .map(|r| r.as_link())
273        .collect::<Result<Vec<_>>>()?
274        .into_iter()
275        .copied()
276        .collect();
277    let mut blocks = Vec::new();
278    while cursor < input.len() {
279        let (body, after) = read_section(input, cursor)?;
280        cursor = after;
281        let (cid, consumed) = parse_cid_prefix(body)?;
282        blocks.push((cid, body[consumed..].to_vec()));
283    }
284    Ok((roots, blocks))
285}
286
287/// Read one length-prefixed CAR section. Returns `(body, new_cursor)`.
288fn read_section(input: &[u8], cursor: usize) -> Result<(&[u8], usize)> {
289    let (len, rest) =
290        read_uvarint(&input[cursor..]).ok_or_else(|| anyhow!("truncated CAR varint"))?;
291    let prefix_len = input.len() - cursor - rest.len();
292    let body_start = cursor + prefix_len;
293    let body_end = body_start
294        .checked_add(len as usize)
295        .ok_or_else(|| anyhow!("CAR section length overflow"))?;
296    ensure!(body_end <= input.len(), "truncated CAR section body");
297    Ok((&input[body_start..body_end], body_end))
298}
299
300/// Parse a CID at the start of `body`, returning `(Cid, bytes_consumed)`.
301fn parse_cid_prefix(body: &[u8]) -> Result<(Cid, usize)> {
302    // CIDv1: 0x01 ++ codec-varint ++ multihash. Multihash = code-varint ++ len-varint ++ bytes.
303    // CIDv0: 0x12 ++ 0x20 ++ 32 bytes (base58 in string form; here a raw prefix).
304    if body.is_empty() {
305        bail!("empty CID prefix");
306    }
307    if body[0] == 0x01 {
308        // CIDv1 — walk the varints to find the total length.
309        let mut i = 1usize;
310        let (_codec, rest) = read_uvarint(&body[i..]).ok_or_else(|| anyhow!("truncated codec"))?;
311        i += (body.len() - i) - rest.len();
312        let (_code, rest) = read_uvarint(&body[i..]).ok_or_else(|| anyhow!("truncated mh code"))?;
313        i += (body.len() - i) - rest.len();
314        let (len, rest) = read_uvarint(&body[i..]).ok_or_else(|| anyhow!("truncated mh len"))?;
315        i += (body.len() - i) - rest.len();
316        let digest_len = usize::try_from(len).map_err(|_| anyhow!("CID digest length overflow"))?;
317        let end = i
318            .checked_add(digest_len)
319            .ok_or_else(|| anyhow!("CID digest length overflow"))?;
320        ensure!(end <= body.len(), "truncated CID digest");
321        i = end;
322        let cid = Cid::from_bytes(&body[..i])?;
323        Ok((cid, i))
324    } else if body[0] == 0x12 {
325        // CIDv0 (sha2-256, 32 bytes): 34 bytes total.
326        ensure!(body.len() >= 34, "truncated CIDv0");
327        let cid = Cid::from_bytes(&body[..34])?;
328        Ok((cid, 34))
329    } else {
330        bail!("unsupported CID prefix byte 0x{:02x}", body[0]);
331    }
332}
333
334/// Build a CAR proof for a single record: the commit block + all MST nodes on
335/// the path + the record block, rooted at the commit's CID.
336///
337/// `record_bytes` is the DAG-CBOR of the [`ModelRecord`] (i.e. `record.to_dag_cbor()`).
338pub fn build_record_proof_car(
339    commit: &Commit,
340    path: &Proof,
341    node_blocks: &[(Cid, NodeData)],
342    record: &ModelRecord,
343) -> Vec<u8> {
344    let mut blocks: Vec<(Cid, Vec<u8>)> = Vec::new();
345    // Commit block first.
346    let commit_cid = commit.cid();
347    let commit_bytes = commit.to_dag_cbor();
348    blocks.push((commit_cid, commit_bytes));
349    // All MST node blocks referenced by the proof (caller passes the full tree's
350    // blocks; we filter to those on the path for a minimal proof, but including
351    // the whole tree is also valid — verifiers just won't use the extras).
352    let path_cids: std::collections::BTreeSet<Cid> = path
353        .path
354        .iter()
355        .map(|step| match step {
356            crate::mst::ProofStep::FoundAt(d, _)
357            | crate::mst::ProofStep::ThroughEntry(d, _)
358            | crate::mst::ProofStep::LeftSubtree(d) => d.cid(),
359        })
360        .collect();
361    for (cid, data) in node_blocks {
362        if path_cids.contains(cid) {
363            blocks.push((*cid, data.encode()));
364        }
365    }
366    // Record block.
367    let record_cid = record.cid();
368    let record_bytes = record.to_dag_cbor();
369    blocks.push((record_cid, record_bytes));
370    build_car_v1(&[commit_cid], &blocks)
371}
372
373/// `verifyRecordProof(commit, signingKey, path, record)` — offline D5 verification.
374///
375/// Checks, in order:
376/// 1. **Commit signature**: `commit` is signed by `signing_key` (the account's
377///    published `#atproto` P-256 verifying key).
378/// 2. **MST path**: `path` is a valid inclusion proof from the commit's `data`
379///    (MST root) down to an entry whose value is the record's CID.
380/// 3. **Record CID**: the `record`'s computed CID equals the entry value the
381///    path addresses.
382///
383/// If all three pass, the host's claim ("this account's repo contains this
384/// record at this MST root, signed by this DID") is trustworthy without needing
385/// to trust the host.
386pub fn verify_record_proof(
387    commit: &Commit,
388    signing_key: &VerifyingKey,
389    path: &Proof,
390    record: &ModelRecord,
391) -> Result<()> {
392    // (1) Commit signature.
393    commit
394        .verify(signing_key)
395        .map_err(|e| anyhow!("commit signature: {e}"))?;
396    // (2) + (3) MST path + record CID.
397    let record_cid = record.cid();
398    path.verify(&commit.data, &record_cid)
399        .map_err(|e| anyhow!("MST proof: {e}"))?;
400    Ok(())
401}
402
403#[cfg(test)]
404mod tests {
405    #![allow(
406        clippy::unwrap_used,
407        clippy::expect_used,
408        clippy::indexing_slicing,
409        clippy::panic
410    )]
411    use super::*;
412    use crate::commit::{Commit, UnsignedCommit};
413    use crate::mst::Node;
414    use crate::record::{self, ModelRecord};
415    use crate::tid::Tid;
416    use p256::ecdsa::{SigningKey, VerifyingKey};
417    use std::collections::BTreeMap;
418
419    fn fixture() -> (
420        VerifyingKey,
421        Commit,
422        Node,
423        Tid,
424        ModelRecord,
425        Vec<(Cid, NodeData)>,
426    ) {
427        let signing_key = SigningKey::random(&mut rand::rngs::OsRng);
428        let verifying_key = VerifyingKey::from(&signing_key);
429
430        let mut recs = BTreeMap::new();
431        let mut records_by_tid: std::collections::BTreeMap<Tid, ModelRecord> = BTreeMap::new();
432        for i in 0..6 {
433            let tid = Tid::from_micros(1_700_000_000_000_000 + i * 1000, i as u16);
434            let rec = ModelRecord::new(
435                "at://did:web:alice.example.com",
436                format!("bafyreiexampleoid{i:020}"),
437                "2026-06-23T12:34:56.789Z",
438            )
439            .expect("record");
440            recs.insert(tid, rec.cid());
441            records_by_tid.insert(tid, rec);
442        }
443        let tree = Node::from_records(record::COLLECTION_NSID, &recs);
444        let root = tree.root_cid();
445        let (_root_data, node_blocks) = tree.to_node_data_with_blocks();
446
447        let unsigned = UnsignedCommit::new("did:web:alice.example.com", root, Tid::now(), None);
448        let commit = Commit::sign(&unsigned, &signing_key);
449
450        let target_tid = recs.keys().nth(2).copied().expect("key");
451        let target_record = records_by_tid.get(&target_tid).cloned().expect("record");
452        (
453            verifying_key,
454            commit,
455            tree,
456            target_tid,
457            target_record,
458            node_blocks,
459        )
460    }
461
462    #[test]
463    fn verify_record_proof_round_trip() {
464        let (vk, commit, tree, tid, record, _node_blocks) = fixture();
465        let proof = tree.proof(record::COLLECTION_NSID, &tid).expect("proof");
466        verify_record_proof(&commit, &vk, &proof, &record).expect("proof verifies");
467    }
468
469    #[test]
470    fn verify_record_proof_car_round_trip() {
471        let (vk, commit, tree, tid, record, node_blocks) = fixture();
472        let proof = tree.proof(record::COLLECTION_NSID, &tid).expect("proof");
473        let car = build_record_proof_car(&commit, &proof, &node_blocks, &record);
474        // The CAR must parse back, contain the commit + record blocks.
475        let (roots, blocks) = parse_car_v1(&car).expect("parse CAR");
476        assert_eq!(roots, vec![commit.cid()]);
477        let block_cids: std::collections::BTreeSet<Cid> = blocks.iter().map(|(c, _)| *c).collect();
478        assert!(
479            block_cids.contains(&commit.cid()),
480            "CAR must contain commit block"
481        );
482        assert!(
483            block_cids.contains(&record.cid()),
484            "CAR must contain record block"
485        );
486
487        // And the proof still verifies independently.
488        verify_record_proof(&commit, &vk, &proof, &record).expect("proof verifies");
489    }
490
491    #[test]
492    fn verify_record_proof_detects_wrong_record() {
493        let (vk, commit, tree, tid, _record, _node_blocks) = fixture();
494        let proof = tree.proof(record::COLLECTION_NSID, &tid).expect("proof");
495        // Substitute a different record (wrong CID for the path's terminal entry).
496        let wrong = ModelRecord::new(
497            "at://did:web:alice.example.com",
498            "bafyreiexampleoidDIFFERENT000",
499            "2026-06-23T12:34:56.789Z",
500        )
501        .expect("record");
502        assert!(
503            verify_record_proof(&commit, &vk, &proof, &wrong).is_err(),
504            "must reject a record whose CID isn't addressed by the path"
505        );
506    }
507
508    #[test]
509    fn verify_record_proof_detects_bad_signature() {
510        let (_vk, commit, tree, tid, record, _node_blocks) = fixture();
511        let proof = tree.proof(record::COLLECTION_NSID, &tid).expect("proof");
512        // A different verifying key — commit won't verify.
513        let other = VerifyingKey::from(&SigningKey::random(&mut rand::rngs::OsRng));
514        assert!(
515            verify_record_proof(&commit, &other, &proof, &record).is_err(),
516            "must reject a commit signed by a different key"
517        );
518    }
519
520    #[test]
521    fn verify_record_proof_detects_tampered_commit_data() {
522        let (vk, mut commit, tree, tid, record, _node_blocks) = fixture();
523        let proof = tree.proof(record::COLLECTION_NSID, &tid).expect("proof");
524        // Point the commit at a different MST root — signature verification will
525        // fail because the sig no longer covers the tampered data.
526        commit.data = Cid::from_dag_cbor(b"different root");
527        assert!(
528            verify_record_proof(&commit, &vk, &proof, &record).is_err(),
529            "must reject a commit whose data was tampered with"
530        );
531    }
532
533    #[test]
534    fn car_build_parse_round_trip() {
535        let cid_a = Cid::from_dag_cbor(b"a");
536        let cid_b = Cid::from_dag_cbor(b"b");
537        let blocks = vec![(cid_a, b"block-a".to_vec()), (cid_b, b"block-b".to_vec())];
538        let car = build_car_v1(&[cid_a], &blocks);
539        let (roots, parsed) = parse_car_v1(&car).expect("parse");
540        assert_eq!(roots, vec![cid_a]);
541        assert_eq!(parsed, blocks);
542    }
543
544    #[test]
545    fn empty_car_round_trip() {
546        // Zero blocks, one root — header only.
547        let root = Cid::from_dag_cbor(b"root");
548        let car = build_car_v1(&[root], &[]);
549        let (roots, blocks) = parse_car_v1(&car).expect("parse");
550        assert_eq!(roots, vec![root]);
551        assert!(blocks.is_empty());
552    }
553
554    #[test]
555    fn atproto_parser_rejects_truncated_cid_without_panicking() {
556        // A CIDv1 multihash advertises a 32-byte digest but the CAR section
557        // ends immediately after the length varint.
558        let malformed = hex::decode("11a265726f6f7473806776657273696f6e010401711220")
559            .expect("fixture is valid hex");
560        assert!(parse_car_v1_atproto(&malformed).is_err());
561
562        // The fixed-width CIDv0 form must receive the same bounds check.
563        assert!(parse_cid_prefix(&[0x12, 0x20]).is_err());
564    }
565}