Cryptid Protocol: Major Spec Rewrite: What's Changing and Why

Announcements and Roadmap
1

Okay, so….. I did a major oopsie and we’re gonna have to do a significant rewrite of the Cryptid spec as a result of that. I’m writing this post to explain what the problem is and what we’re doing to solve it.

The Problem

One of the fundamental principles of Cryptid is that we treat servers as adversaries. The whole protocol was designed around the idea that servers are just dumb pipes and they know close to nothing about the users connecting to them.

But there was a fundamental contradiction baked into the spec: we were using JWT’s for authentication. (Thanks to @randomscientist for pointing this out to me)

Every authenticated action (sending a message, rotating an address, etc) required a JWT tied to your device. That meant that every time you did anything, the server knew exactly who you were and that you were active. It didn’t matter how carefully we minimized the metadata footprint everywhere else. The authentication layer essentially gave everything up and pointed straight at your device identity. A server operator could trivially reconstruct a detailed picture of when you’re online, who you talk to, and how often you message — exactly the kind of thing we don’t want our servers to know.

This was an architectural mistake that arose from my inexperience with the privacy engineering required here and I reached for a familiar tool without fully thinking about the implications for our threat model. I’m sorry about that, but the good news is that it’s fixable!

What’s Changing

1. Authentication: JWTs → PrivacyPass

We’re replacing JWT-based authentication with PrivacyPass, a cryptographic token protocol that gives us unlinkable authentication. A server can now issue tokens to you and later verify that those tokens are legitimate without being able to link the redemption back to the original issuance.

In practice, this does mean that the server knows that a legitimate device registered and got tokens at some point, but when the tokens are spent to actually do anything, the server can’t tell which device is performing the action. Your activity cannot be linked to your identity.

This also does mean that the progressive trust rate limiting system is going to go away entirely because the server has no way of knowing who anyone is anymore. PrivacyPass token issuance becomes the rate limit now. We’ll need to tune the issuance policy carefully to get a good balance, but honestly, that’s something we can only really figure out once we start building and see how it behaves in practice.

2. Message Format: Double-Encrypted Envelopes

For messages, we’re moving to a double-envelope design:

  • CryptidEnvelope (outer): This is all the server ever sees. It literally only contains the recipient’s delivery address and a ciphertext that was encrypted directly to the recipient device’s public key, so the server can’t read anything.
  • InnerEnvelope (inner): This is what the recipient sees once they decrypt the outer layer. It contains additional routing context, metadata, and the actual MLS ciphertext.

The server’s job is now reduced to: “look at the address, send it an opaque blob, and forget about it”. It learns nothing about the content, nothing about the sender, and nothing about what kind of message it is.

3. Delivery Addresses: Mailbox Keypairs

The current address system has a problem when you replace JWTs with PrivacyPass: while the addresses are pseudonymous and rotatable, proving that an address belongs to you still ties back to your device identity in ways that a server can observe.

We’re replacing this with a Mailbox Keypair system. Each device generates a dedicated Mailbox keypair. Individual delivery addresses are then derived from that keypair (one keypair per address). This gives devices a way to cryptographically prove to a server that they own a mailbox and are entitled to its messages without the server learning which device that is, or being able to link addresses together.

What’s NOT Changing

A lot of the spec actually remains intact, because the problems were concentrated in the authentication and envelope layers, not the core protocol design:

  • MLS remains our E2EE foundation. Nothing changes here.
  • Two-layer identity (device identity + user identity) stays as-is.
  • InfoPackages and the contact exchange model are unchanged.
  • Federation protocol architecture is the same, though it will be updated to reflect the new envelope format.
  • Moderation architecture stays the same.
  • VDF for device announcements stays.

Timeline and What Happens to Existing Implementations

The rewrite will be reflected in the spec incrementally, but the authentication and envelope changes are breaking. I’ll be posting updates here as sections are revised. The first areas to land will be the new authentication model and the envelope format, since those are the foundation everything else rests on.

Thank you for bearing with me through this. Building a privacy protocol correctly is genuinely hard and I’d rather be honest about mistakes and fix them rather than just give it the ol’ landlord special.

The design coming out of this rewrite is going to be significantly stronger and actually deliver on the promises that the current spec makes.

1 Like
MLS Commit Ordering and Group Self-Healing
2

Alrighty! The first chunk of spec updates are now live on main!

Here’s what’s been updated:

  1. Wire Format Documentation
    • Documented the whole double-encrypted envelope design
    • CryptidEnvelope (outer) – what servers see
    • InnerEnvelope (inner) – what clients see after decryption
  2. Message Types:
    • CryptidMessages – Application-level messages (text, reactions, edits, files, etc)
    • SystemOperations – MLS commits, group extension updates, address rotations, etc
    • ContactRequests – Initial contact establishment and DM group bootstrapping
  3. Intro Pages:
    • Updated foundational principles to include unlinkable authentication and double-encrypted envelopes
    • Added PrivacyPass and Mailbox Keypairs to key terminology
    • Updated the “What the Server Knows” section to reflect the new model
    • Status page now reflects v0.10 and Breaking Rewrite status

What’s still left to do:

  • Mailbox Keypairs documentation (delivery address system rework)
  • PrivacyPass authentication details
  • Federation protocol updates for the new envelope format

The next areas to land will most likely be the Mailbox Keypairs system and documentation about how PrivacyPass fits into all this. I’ll post updates as these sections are revised/added.

As always, feedback welcome!

3

Okay! Second chunk of spec updates just landed on main! Everything from the last post’s TODO has landed, plus a fair bit more. Status page is now v0.11!

Here’s what’s been updated:

  • Mailbox Keypairs
    • Per-group addresses derived from a master seed. Servers no longer assign addresses at all.
    • Challenge-response ownership proof, two-phase rotation with an overlap window.
    • Multi-homing now explicitly means primary + failover.
  • PrivacyPass
    • Token type 0x0001 (VOPRF over P-384), redeemable only at the issuing server.
    • Rate limiting moved from send time to issuance, using token buckets.
    • Progressive trust now sizes your token budget rather than capping messages/hour.
  • Blind KeyPackage Distribution
    • KeyPackages live under derived handles and are encrypted at rest, so servers no longer index them by device_id.
  • Federation
    • Servers relay opaque envelopes now: group_id and sender_signature are gone from the payload.
    • Server-to-server auth is per-server signatures; PrivacyPass tokens never cross the federation boundary.
  • Files and Media
    • Device-to-device transfer has been replaced with an encrypted blob store.
    • The sender no longer has to be online for anyone to receive a file.
    • Report-based takedown, since hosts now store content they cannot read.
  • Wire Format
    • Canonical serialization pinned to TLS presentation language (tls_codec), same as MLS.
    • ContactRequest is now signed and replay-protected.
    • All IDs are 32-byte Blake3, and GroupId no longer has two different widths.

What’s still left to do:

  • The entire API reference. Everything under /api is void until it is rewritten.
  • Most notably, there are no endpoints defined for sending messages, receiving them, or getting tokens.
  • An error model. Right now a client can’t tell “back off” from “re-issue”.

The next thing I’m gonna tackle is the API rewrite. The plan is to define abstract operations with per-transport bindings underneath rather than baking HTTP into everything, which should leave room for gRPC/QUIC/Meshtastic down the line. (I WILL MAKE THE CRYPTID OVER ICMP MEME REAL)

As always, feedback welcome! :smiling_face:

4

Aaaand the third chunk of spec updates just landed on main! The API rewrite from the last post is done, plus a bunch of stuff I didn’t expect to be doing. Status page now reflects v0.12!

Here’s what’s been updated!

  • The API Reference
    • The entire /api tree has been rewritten. 14 pages, nothing carried over.
    • Operations are defined abstractly - input, output, auth, errors - with HTTP as one binding underneath rather than baked into everything.
    • All the endpoints that didn’t exist now do: submitting and retrieving envelopes, token issuance, mailbox registration, blob upload/fetch/delete, KeyPackage handles.
  • Error Model
    • Every code carries a retry class, so a client can finally tell “back off” from “re-issue” from “an operator blocked you and nothing will help”.
    • Codes also carry failover eligibility, which makes the multi-homing rules actually executable instead of prose a client has to interpret.
  • Things I got wrong in 0.11:
    • Writing the API against the model exposed a lot of these
    • InfoPackages were being encrypted by the server, with a key the server generated. It could read your identity, every device, and every contact address. Now the client encrypts and the server stores bytes it can’t read.
    • KeyPackage fetch was metered, but tokens only redeem at the server that issued them and KeyPackages live on the target’s server. So it was unimplementable across servers. It’s unmetered now with the derived handle acting as the capability.
    • Token scoping is gone. Tokens are fungible now. Scoping bought nothing (there was only ever one bucket) and cost something real: challenge_digest is visible at redemption, so scoping split the anonymity set.
    • Announcement was returning finished tokens, which would have handed the server the exact values it later verifies. Issuance is properly blinded now.
  • Group Size
    • Fan-out means one message costs one token per recipient device, so groups are practically capped around 200-250 users. Past that you’re rationing tokens.
    • Large low-traffic groups are fine - receiving is free, so a 4,000-person announcement channel works just fine today as long as the sender can cover a token per participant device for each announcement. The real problem is conversation at these scales.
    • To allow community-scale groups to exist, we’re going to reserve the cryptid_community_ext_v1 server feature handle and treat that use case as deliberately outside the base protocol because at that scale, we need server coordination to keep things working and that’s going to cost a little privacy. More on that below.
  • Moderation
    • Device reports to servers are gone. They left the only per-device record in the whole design, and they asked operators to judge conduct they fundamentally cannot see.
    • Blob reports are staying - a server actually hosts those, so it has both the evidence and the liability. (This does not mean that the servers can decipher the blobs, only that they can verify their existence)
    • Groups got a ban list as an MLS extension, and client-side blocking got fleshed out properly (by user, by device, by content, plus burning your contact mailbox).
  • Message size dropped from 10MB to 256KB, since bulk data has exactly one path now and there’s no reason a message needs to be that big.
  • Build gates, I finally made it so that broken internal links will fail the build.
  • Now that the API rewrite is done, the API tree is finally back in the sidebar once again instead of existing but being unreachable.

What’s still left to do:

  • A pass to cut pseudocode back. There’s about 100 different function definitions across the reference tree and six pages that are more code than content, which is hard to read and where basically every contradiction I found this round was hiding.
  • Implementation. That’s the real gate on the freeze now.

The next thing I’m going to throw myself at is a server implementation. I feel like the spec is complete enough that the remaining questions can only be answered by running code - particularly the token bucket numbers, which are based on math I did in my head rather than anything measured.

Two things I’d genuinely appreciate input on:

  • The Group Ceiling. 200-250 users is where the current token budgets land. Raising them ~3x would make 250 comfortable rather than merely possible, and I’m not sure what the right number is without real traffic.
  • Community Groups. The design I’m leaning towards is a replicated shared mailbox: one envelope many people read, replicated across servers so nobody’s stuck depending on one host. It costs you group membership visibility at server granularity (concretely: a server hosting a community mailbox sees how many distinct addresses read it and when. It does not see any device_id - every member proves ownership with the same derived key, so members are indistinguishable to the server except by source address and timing). To me that trade-off feels fine for a public community but it’s not something I’d recommend for a group chat, which is why it’s going to be opt-in and explicitly part of a server feature extension rather than part of the base protocol - but I’d like to hear from you if that reasoning holds up.

As always, feedback welcome! :smiling_face: