War on CARs

Hello and welcome to data service diaries! Expect atproto deep cuts and niche database tricks. General announcements will stay over at Microcosm updates!

Disclosure: this is a hit(-by-a-CAR) piece, by me, the author of an alternative atproto repo export format called STAR-lite.

Authenticated Transfer. Any time you grab some data in atproto, that "AT" prefix guarantees the data's authenticity. You don't need to extend your trust boundary to subscribe to someone else' relay or pull a whole repo archive from Hubble -- those services can't tamper with atproto data without you noticing.

At least, as long as you do all the checks. Unfortunately, there seems to be a sort of last-mile complacency around checking the contents of CARs (one could call it a... close-to-home effect?):

I did a wide (non-comprehensive) survey of atproto projects, and found that the Atmosphere frequently fails to verify CAR blocks.

I think these results are driven by a CAR-specific hazard that has been under-appreciated, and which undermines authenticity in the protocol.

Authenticating atproto data

Every account in the Atmosphere has a key-value data store and a stable identifier ("DID") that resolves to a public signing key. A Merkle Search Tree bridges signatures to data, verifiable in five easy steps:

1. 💪 Resolve the DID to its public key!
2. 💪Verify the signature with that key!
3. 👀 Follow the CID link -> root of Merkle Search Tree!
4. 👀 Traverse MST to enumerate keys and links-to-values!
5. 👀 Look up values by CID link!

💁‍♀️ CIDs are Content IDentifiers, a hash of the data they identify, and part of the atproto data model. Any change in key-value data "bubbles up" and changes the MST root CID, which the signed commit covers.

Implementations tend to get steps 1 and 2 right (💪). You have to get them at least mostly right, or else things don't work. This is a nice property!

In steps 3, 4, and 5 (👀), CARs work against this property. Things mostly work if you do it wrong, while looking deceptively—even obviously!—right.

The body of a CAR file is a sequence of [len, CID, bytes],

| ---------------- CAR body ---------------- |
[ len | CID | bytes ] [ len | CID | bytes ] …

where CID is supposed to(!) be the CID of bytes, and bytes is a serialized block. The CAR-format CID is the same CID as the atproto data model CID.

CARs index blocks by the exact links we need to look them up by! This should be a nice thing! And yet...

CAR reader libraries don't verify block CIDs

CAR libraries give you a stream of (CID, bytes) pairs.

CAR libraries do not check* that the CID actually matches the bytes they are giving you.

Your CAR library will happily give you wrong (CID, bytes) pairs from a malicious / buggy / tampered-with archive!

I'm being repetitive, but this was really shocking to me when I found out!

Why don't CAR libraries verify CIDs?

Because CIDs come from the IPLD multihash / multiformats / multicodec / multi-whatever universe, with 653 codecs registered at time of writing, meant to grow over time. Should a CAR library support all CID types? Some subset? (which subset? who picks?)

Almost all CAR libraries don't try to answer this, and using them safely requires manually checking each block. Most libraries don't warn about this in their docs. Most atproto projects don't have the check.

*Positive exceptions:

🐸 ipld/go-car has a registry / hash-lookup system, and does verify contents. Golang projects like Bluesky's back-end and Streamplace benefit from this.

🐸 carbox (python) and elixir-dasl (elixir) are made-for-atproto CAR libraries, and explicitly expect atproto CIDs.

💁‍♀️ CIDs in the atproto data model are always sha256

👹 ~All other notable libraries surveyed pass unverified contents.

Can this be fixed?

Yeah of course, switch everything to STAR-lite! I'm mostly joking.

The root of the problem is the inclusion of CIDs in the archive at all. They are redundant by definition, since the contents are right there! And you have to recompute the CID from the contents anyway, to check if the CID is right! Having it can only help implementations do the wrong thing.

Dropping block CIDs, forcing them to be computed from the content, would get that nice property:

You have to get it least mostly right, or else things don't work.

You can't have that with CARs.

💁‍♀️ I think this is a form of Parse, don't validate.

Can this be mitigated?

Yeah probably!

Maybe we can make insecure atproto projects happen less frequent / less likely:

1. Call out this hazard in the IETF spec (issue opened), so that at least spec-following implementations are more likely to get it right.
2. Periodically audit ecosystem repo libraries: fixes here are high-leverage, benefiting downstream apps.
3. Encourage more CAR libraries to add block verification directly, or warn about the hazard in their docs if they don't. (eg @ipld/car and iroh-car both already have open issues)

I think those efforts could help in a limited way. But the CAR format is so simple that people (and agents!) do often (and will continue to) hand-roll parsers directly into their projects, with an evidently high risk of failing to verify contents.

🦐 this is the end, the article is over

Appendix 1: CARs in atproto spaces

The current atproto permissioned data draft specifies repository serialization in CAR format. For the purpose of this post, that's probably fine: The authenticity risk doesn't apply, because space data has no authenticity check at all! That's the trade for deniable (and non-rebroadcastable) data.

I still think CARs are a bad fit for spaces though, and I hope to make the case for using a STAR-lite spaces variant (or any safer streamable key-value-set alternative format!) anyway. Maybe if DASL adopts it, this could even be a realistic possibility.

Or maybe we start a bottom-up shift in the ecosystem, like with public-data STAR-lite archives. There are already multiple STAR-lite producers on the network, at least half a dozen consumers, and third-party implementations in languages I don't even know. Better formats win? :)

Appendix 2: Detailed survey results

Bluesky's stuff:

🍋 Typescript libraries: sometimes. Its CAR reader defaults to always verifying, but its firehose consumer explicitly turns that off. It seems to think that MST structural consistency (from inductive proof transform?) is sufficient, but I'm pretty sure it's not. (MST aside, record contents wouldn't be covered by that. i didn't trace this all the way to POC).

🐊 PDS: verifies, inherited from typescript library

🍋 Indigo: sometimes. Everything that uses go-car inherits its checks. The reader at repo/carutil/reader.go appears to have regressed, no longer recomputing block hashes.

🥬 Tap: verifies, inherited from go-car. LoadCommitFromCAR might bypass the check for Commit Object lookup. I think that can only lead to confusing bugs, not authenticity weakness.

🌲 Relay: verifies, inherited from go-car.

🥦 Jetstream v2: verifies, inherited from go-car.

💄 Jetstream v1: does not verify in its firehose consumer, so commit contents are likely not covered by the signature check.

CAR libraries:

atproto repo libraries

atproto apps

I hope I got everything right in the survey. It was kind of a lot to pull together. Corrections welcome.