1use 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
36pub 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(§ion));
61 }
62 sections
63}
64
65pub 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
79pub 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(§ion)
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
95pub fn build_car_v1(roots: &[Cid], blocks: &[(Cid, Vec<u8>)]) -> Vec<u8> {
98 let mut out = Vec::new();
99 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 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, §ion);
115 }
116 out
117}
118
119pub 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 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
190pub 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, §ion);
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
216pub fn parse_car_v1(input: &[u8]) -> Result<(Vec<Cid>, Vec<(Cid, Vec<u8>)>)> {
219 let mut cursor = 0usize;
220 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 let mut blocks = Vec::new();
242 while cursor < input.len() {
243 let (body, after) = read_section(input, cursor)?;
244 cursor = after;
245 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
253pub 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
287fn 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
300fn parse_cid_prefix(body: &[u8]) -> Result<(Cid, usize)> {
302 if body.is_empty() {
305 bail!("empty CID prefix");
306 }
307 if body[0] == 0x01 {
308 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 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
334pub 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 let commit_cid = commit.cid();
347 let commit_bytes = commit.to_dag_cbor();
348 blocks.push((commit_cid, commit_bytes));
349 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 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
373pub fn verify_record_proof(
387 commit: &Commit,
388 signing_key: &VerifyingKey,
389 path: &Proof,
390 record: &ModelRecord,
391) -> Result<()> {
392 commit
394 .verify(signing_key)
395 .map_err(|e| anyhow!("commit signature: {e}"))?;
396 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 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 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 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 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 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 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 let malformed = hex::decode("11a265726f6f7473806776657273696f6e010401711220")
559 .expect("fixture is valid hex");
560 assert!(parse_car_v1_atproto(&malformed).is_err());
561
562 assert!(parse_cid_prefix(&[0x12, 0x20]).is_err());
564 }
565}