HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Relay

The Relay

12 min read

You type "on my way," hit send, and a second later it is on your friend's phone. In between sits a server. How much does that server have to know — about you, about your friend, about the fact that the two of you are talking at all — for the message to arrive? The answer we fought for is: almost nothing.

This is the story of the piece of the system that carries messages: the relay. It is the entry point to a series, and each hard sub-problem gets its own deep dive that this article links out to as we go. If you have taken a data structures course and remember what a "hash," a "public key," and a "server" are, you have enough to follow along. We will meet the specialized cryptography exactly when we need it and never before.

1. The problem

Two phones almost never want to talk at the same instant. Yours is awake; your friend's is in a pocket, screen dark, the app suspended by iOS to save battery. So every messenger puts a server in the middle: you hand it a message, it holds or forwards the message, and when your friend's phone is reachable the message lands. That middle server is the relay, and it is the most privacy-sensitive machine in the whole system — not because of what is in the messages, but because of what surrounds them.

Here is the uncomfortable fact. You can encrypt message content end to end so the relay sees only ciphertext — that part is table stakes, and we do it — and the relay can still betray you completely. Because even with perfect content encryption, the naive relay learns who is talking to whom, how often, at what times, and in what pattern. That is a social graph, and a social graph is often more damaging than the words. "We don't have your messages" is a sentence a surveillance-friendly service can say with a straight face while handing over everything that actually matters.

So let us be precise about what we want. When Alice sends a message through the relay to Bob, the relay must not learn:

  1. The content. Obvious, and the easy part.
  2. Who sent it. Not Alice's account, not her public key, not her phone.
  3. That two conversations belong to the same person. Even watching for months, the relay must not be able to cluster Alice's chats together into "this is one user."
  4. What kind of message it is, or exactly when. A voice call, a typing receipt, a reaction, a background sync — these should look alike, and the timestamp should be fuzzy.
  5. That it ever held the message at all. No durable server mailbox to subpoena, dump, or breach.

And two things the relay still must do, which is what makes this hard rather than trivial:

  • Reach an offline phone. If Bob is asleep, someone has to wake his phone — and the only doorbell iOS gives us rings through Apple's servers.
  • Stop abuse. A relay that accepts anonymous messages from anyone is a spam cannon. We have to rate-limit a sender we have deliberately made invisible — a genuine paradox we will have to resolve.

Plus one clause that reshaped every decision, exactly as it did in our Contact Discovery work: it has to hold forever. A recording of who-talked-to-whom does not expire, and neither does a signature that proves you said something. An adversary can record the encrypted traffic today and wait — for a quantum computer, or just for a subpoena — and try to break it in fifteen years. So every wrapping primitive must resist quantum attack, and, as we will see, every authenticator must be deniable.

The strawman, and why it fails

The obvious design is a mailbox: the relay keeps a table, one row per undelivered message, (recipient, sender, timestamp, ciphertext), and Bob's phone downloads its rows when it wakes. Encrypt the ciphertext column and you might feel done.

You are not close to done. That table is the social graph, in a database, sorted and indexed for convenient querying, retained until delivery and often long after. A breach dumps it. A subpoena compels it. An honest-but-curious operator mines it. The columns you did not encrypt — who, to whom, when, how big, how often — are precisely the metadata that de-anonymizes people, and no amount of content encryption touches them. Signal's own research and a decade of "metadata is the message" reporting say the same thing: the envelope leaks more than the letter.

Everything in this series is a reaction to one of those leaks. The rest of this article is the map.

2. The shape of the solution: an onion

The design principle is blunt: the relay should be a dumb pipe that learns as close to nothing as the laws of networking allow. We get there by wrapping the message in layers, peeling off one thing the relay is not allowed to know at a time, until what is left on the outside is the bare minimum needed to move bytes to the right phone.

A useful mental model is a paranoid postal system:

  • The letter is sealed in a box only Bob can open — content encryption.
  • The return address is replaced by a numbered cloakroom ticket that proves the sender checked in, without naming them — sealed sender.
  • The ticket is different for every correspondent, so the post office can't tell that the person mailing Bob is the same person mailing Carol — unlinkability.
  • The only stamp the post office reads is a coarse "urgent / not urgent," never the kind of letter — header encryption.
  • The post office keeps no record of anything it hands over — ephemeral delivery.
  • You collect your mail without telling the clerk which box is yours — oblivious pull.
  • The "you have mail" doorbell rings through a doorman who cannot read the tag or link it to you — push without a social graph.
  • And you paid for postage with an untraceable, single-use token, so the post office can enforce "one letter per stamp" without knowing who bought the stamp — anonymous admission.
  • Finally, nothing about the letter can later be used to prove in court that you wrote it — deniability.

Each of those is a sub-problem, and each turned into its own piece of engineering:

What the relay must not learn Why it's hard Deep dive
The message content — (the baseline everything else assumes) The End-to-End Layer
Who sent it the relay must still route and authorize the message Sealed Sender
That two chats are the same person a stable pseudonym silently clusters a sender's whole life Sender Unlinkability
The message kind and precise time the relay must read something to know how to wake a phone The Envelope
That it held the message at all a durable mailbox is a metadata honeypot Ephemeral Delivery
Which conversation you are reading the act of pulling your mail leaks which box you checked Oblivious Pull
The graph, when it wakes your phone the only wake channel runs through Apple Waking a Sleeping Phone
…while still blocking floods we made the sender invisible, so who do we throttle? Anonymous Admission
…forever, and un-provably a signature is a portable, permanent confession Deniability

The rest of the series is the machinery underneath. But two constraints cut across all of it, so they come first.

3. The two constraints that cut across everything

Post-quantum. A social graph is exactly the kind of long-lived secret that "harvest now, decrypt later" is designed to steal: record the traffic today, break the wrapping in 2035, reconstruct fifteen years of who-knew-whom retroactively. So — as a hard rule, the same one the discovery path follows — the relay's cryptography avoids anything a quantum computer breaks. Key agreement is PQXDH (Signal's key exchange with a lattice lock added); the group and push seals use X-Wing (a hybrid of the lattice KEM ML-KEM-768 and classical X25519); identity signatures are hybrid Ed25519 + ML-DSA-65; the admission token is a lattice VOPRF. Where we still lean on a classical primitive, we say so out loud and explain why the residual is acceptable.

Deniability. This one is specific to a messenger and easy to miss. A digital signature is not just authentication — it is transferable proof. If Alice signs each message with her long-term key, then anyone who later gets the transcript (a breach, a seized phone, a hostile recipient) holds a mathematical certificate that Alice, and only Alice, wrote those words, and can prove it to a third party who wasn't there. Face-to- face conversation has never worked that way — you can always deny what you said — and we want the digital version to keep that property. Worse, this is a harvest-now-judge- later threat: a signature recorded today stays a valid proof forever, even against a future quantum "judge." So the relay's authenticators are deliberately not signatures where they don't have to be. They are deniable MACs — authenticators the recipient could have produced themselves — which convince Bob the message is real while proving nothing to anyone else. That is Deniability, and it is why several places you would expect a signature have a shared-key MAC instead.

4. Walking the onion

A quick tour of the layers, each linking to its full treatment.

Content, and the layer we build on. Underneath everything, the message body is encrypted with libsignal — PQXDH to set up a session, the Double Ratchet to give every message its own key, and SPQR, a post-quantum ratchet, so that even the steady-state stream resists a future quantum computer. This is the one part we consume rather than invent (it is Signal's, and excellent), but we add a fail-closed guard that refuses to send or accept a steady-state frame that isn't actually carrying the post-quantum ratchet. See The End-to-End Layer.

Who sent it. The relay has to check that a message comes from a real, non-banned user before it spends resources delivering it — but it must do that without learning the user's identity. The trick is sealed sender: the sender's identity and their signed certificate ride inside the encrypted payload, and the relay sees only an opaque 16-byte ticket, the cert_id. See Sealed Sender.

Linking chats. A ticket that stays the same across all of Alice's conversations is still a pseudonym: the relay can cluster "everything ticket #7 ever sent" into one person's social life. So Alice mints a different certificate per conversation, and the relay loses the thread between her chats. See Sender Unlinkability.

Kind and timing. The relay cannot be completely blind: to decide whether to ring a phone like an incoming call or nudge it silently in the background, it must read how urgent a message is. We give it the absolute minimum — a coarse WakeClass with six values — while the precise message type (one of twenty-seven kinds: reaction, post, huddle turn, sync, …) stays sealed inside. Crucially, the recipient re-derives the class from the sealed type and rejects a mismatch, so a lying relay can only degrade a notification (which is detectable), never learn the kind. See The Envelope.

Holding it. There is no mailbox. The relay is pure publish/subscribe: a message with no live subscriber is dropped on the floor. Durability lives entirely in the sender's outbox, and a message is cleared only when Bob's phone acknowledges it. See Ephemeral Delivery.

Reading it back. When Bob reconnects and pulls whatever he missed, naive polling would tell the relay which conversation had new mail. A short windowed pool served by Private Information Retrieval — the same lattice construction from the discovery path — lets him fetch his messages without the relay learning which he asked for. See Oblivious Pull.

Waking him. If Bob is offline, we have to ring his doorbell, and iOS only offers one doorbell: Apple Push. Whoever presents Bob's push token to Apple, together with the directory that maps push tokens to accounts, can join Bob's phone-linked identity to his message traffic. We split that path into a blind registry and a "decrypt one wake and forget" sender, seal each wake to an attested key, and are honest that Apple itself remains a floor we disclose rather than pretend away. See Waking a Sleeping Phone.

Paying for it. Now the paradox: we hid the sender so thoroughly that we cannot throttle them by identity. The resolution is to move the rate limit upstream — a budgeted, authenticated mint hands out single-use admission tokens — and give the relay a token it cannot link back to the mint, so it can only count spends, never identify a spender. (That unlinkability is computational and post-quantum, not unconditional; article 08 is precise about the difference and why the trade was taken.) See Anonymous Admission.

5. The shape we converged on

Put together, one message travels a single, uniform path — and, as with the discovery work, we deliberately collapsed early alternatives into one way of doing things, because a security system with four code paths has four times the attack surface:

  1. Seal. The client encrypts the body (libsignal), tucks its per-conversation certificate and a deniable MAC inside the seal, and wraps the result in an outer envelope carrying only { recipient routing key, coarse WakeClass, fuzzy timestamp, cert ticket, one admission token }.
  2. Admit. The relay checks the token was minted for this class, hasn't been spent, and the certificate isn't revoked — learning only "some real, non-banned user paid one token to send some class of frame to this recipient."
  3. Publish. It publishes the sealed bytes to the recipient's subject. If a device is live, the bytes arrive; the relay stores nothing.
  4. Or wake, then pull. If no device is live, the relay asks the push path to ring the phone by WakeClass. The woken app reconnects and pulls — obliviously — and the sender's outbox re-ships into that window.
  5. Ack. When Bob's phone acknowledges the message, the sender's outbox finally lets it go.

At no step does the relay hold a mailbox, see an identity, link two conversations, learn a message kind, or produce anything that could later prove who said what. What it does learn — a recipient routing key, a coarse class, a fuzzy time, a per-conversation pseudonym, and a spent anonymous token — is the residue we could not remove without breaking delivery, and each article that follows is honest about exactly that residue.

References & further reading