HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Relay

Sender Unlinkability: The Pseudonym Problem

6 min read

Hiding your name is not the same as hiding that it's you. A relay that never learns "Alice" can still learn "the same unnamed person who messaged Bob at 9, Carol at 10, and a support line at 2am" — and that shape is often enough to put a name back on.

Sealed sender removed the sender's identity from the envelope and left one thing behind: a 16-byte cert_id the relay needs for revocation and abuse control. This article is about the surprisingly sharp leak that one small field creates, and the shipped fix.

1. Linkability, and why a pseudonym is dangerous

Cryptographers distinguish anonymity (the system doesn't know who you are) from unlinkability (the system can't tell that two of your actions were done by the same someone). They are different, and the second is easy to lose while thinking you have the first.

The cert_id is stable for the life of a certificate — roughly a day. So even though the relay never learns "Alice," it can group every message carrying ticket #7 into one bucket and study the bucket: how many conversations it touches, at what hours, in what bursts, in reply to what. That bucket is a pseudonym, and pseudonyms de-anonymize through pattern. This is the entire field of traffic analysis: intelligence agencies have reconstructed identities and relationships from nothing but who-contacted-whom-and-when for a century. "It's just an unlabeled graph" has never been much comfort, because graphs get labels from the outside — one known contact, one predictable routine — and the whole shape lights up.

So a stable per-user ticket, even an anonymous one, is a real leak. We want the relay to lose the thread between a person's conversations.

2. Why we can't just delete the ticket

The tempting answer is to drop cert_id from the envelope entirely. We cannot — not without moving the jobs it does somewhere else first — because the relay uses it for two things that genuinely have to happen at the moment a message arrives:

  • Revocation. If a certificate is compromised or its owner is banned mid-day, the relay has to stop honoring it now, before its daily expiry. It does that by checking the incoming cert_id against a short revocation list. No identifier, no revocation.
  • Abuse metering. An anonymous per-certificate counter (fed to a separate anomaly detector) is how the system notices "one ticket is behaving like a spam cannon" without attaching that behavior to a person.

Both are legitimate, both need some stable handle, and neither is allowed to be the user's identity. The tension is real: the same field that enables anonymous revocation is the field that enables pseudonymous clustering.

3. The shipped fix: a different ticket per conversation

The resolution is to keep a stable ticket, but make it stable only within a single conversation rather than across a user's whole life. Instead of one certificate per user per day, Alice mints one certificate per conversation — a distinct cert_id for her chat with Bob, another for her chat with Carol.

The trick that makes this cheap and private is where the certificates are keyed: each is derived from the local channel key of that specific conversation — a secret Alice and her partner already share and that is never transmitted to anyone. Alice caches these per-conversation certificates locally. When she messages Bob she presents the Bob-ticket; when she messages Carol she presents the Carol-ticket.

Now walk it from the relay's side. It still sees a stable ticket inside a single conversation — but it already knew those messages belonged together, because a conversation shares a routing subject anyway. What it has lost is the ability to tie the Bob-ticket and the Carol-ticket to each other. Alice's separate conversations are now separate unlabeled shapes with no line drawn between them. The pseudonym that used to span her whole social life now stops at the edge of each chat.

The analogy is using a different alias at every venue. A doorman at one club can still recognize "the guy in seat 4 all night," but no one can cross-reference the clubs to discover it's the same person making the rounds — because the name on each wristband is different and unlinkable.

4. What it costs

Not much, which is why this is the shipped choice rather than a someday-plan:

  • One extra certificate per active conversation, each renewed at half its (~1-day) life. The count is bounded by how many people you are actively talking to, not your whole address book.
  • Each mint is a hybrid Ed25519 + ML-DSA-65 signature at credential-svc — cheap, and only for pairs with live traffic.

That is the entire price for erasing cross-conversation linkage at the relay.

5. The honest residuals

We name what this does not fix:

  • Within one conversation, the relay still sees a conversation's messages grouped — but it saw that already (they share a routing subject), so per-pair certificates reveal nothing new inside a chat. This is not a regression; it is the pre-existing floor.

  • The number of distinct tickets a device presents ≈ its number of active conversations. That count is itself a coarse signal — roughly "how socially busy is this device" — even though it links to no identity and no specific partner. It is a much fainter shape than a full cross-conversation graph, but it is not zero.

  • credential-svc sees the mint volume. The service that issues certificates knows how many were minted, though its ledger keys on a hashed user handle, never the raw account, and it never sees the content or recipients of anything. Mint volume is a weak, aggregate signal held by a different party than the relay.

  • The admission token carries a cleartext key_id. This is the one field on the list that is not per-conversation, so it is the one that could re-stitch the pseudonyms above into a single identity — and it would survive cert rotation, which is what makes it worth naming separately. Its harmlessness is not a property of the cryptography but of three deliberate checks on the key set: a hidden known-answer canary, a published live-key list, and a transparency-log commitment with a proof that the committed generation is the current one (The Admission Token §5). Those checks are load-bearing here, not just at the mint.

None of these reconstruct a cross-conversation social graph, which is the leak we set out to close. But honesty is the house style, so they are on the record.

6. The endgame we didn't ship (yet)

There is a cleaner design, and it is worth stating because it is the recommended next step. True Signal-style sealed sender removes cert_id from the envelope entirely. In that world the relay does no per-message identity check at all: revocation moves entirely to credential-svc (a banned account simply cannot mint fresh admission tokens, so its messages stop being admitted rather than being recognized-and-rejected), and all relay-side abuse control rides on the single-use admission token, which is already anonymous and unlinkable by construction.

We did not ship that yet because it is a change to both the envelope format and the admission path — the riskier surgery — whereas per-conversation certificates deliver the property that actually matters (no cross-conversation linkage) as a localized, low-risk change that touches neither. It is the classic engineering call: ship the 90% that removes the real leak now, keep the elegant 100% as a planned migration. When the envelope format next changes, dropping the ticket is the plan.

References & further reading