Design an end-to-end encrypted messaging backend

End-to-end encryption (E2EE) means only the communicating devices hold the keys; the server relays ciphertext it cannot decrypt. This changes the backend's job: it becomes a key directory, a store-and-forward queue and a push notifier, and its security goal shifts to not learning metadata and not being able to impersonate users.

Functional requirements

1. Users send 1:1 and group messages and media; recipients get them when they come online.
2. Each user may have several devices (phone plus desktop), all receiving all messages.
3. The server cannot read content and cannot silently substitute keys.
4. Users can report abuse and block senders.

Non-functional requirements

1. 100 M daily active users, 50 messages sent each per day.
2. Delivery < 500 ms p99 when the recipient is online.
3. Offline messages held up to 30 days, deleted on acknowledgement.
4. Store and log the minimum metadata needed to operate.

Back of the envelope

messages sent           100 M x 50                  = 5 B / day ≈ 57,900 / s, ~175k / s peak (x3)
device fan-out          1.5 devices per user        -> 7.5 B deliveries / day
envelope size           ~1 kB ciphertext (media goes to a blob store, key travels in the message)
relay bandwidth         175k x 1.5 x 1 kB           ≈ 260 MB/s at peak
persistent connections  30 M concurrent, 100k per gateway node -> 300 nodes (+ headroom)

prekey storage (classical)
  150 M devices x 100 one-time prekeys x 32 B      = 480 GB
prekey storage (post-quantum, ML-KEM-1024 public key 1,568 B)
  150 M devices x 10 one-time PQ prekeys x 1,568 B ≈ 2.35 TB   <- why PQ prekey counts are kept small

X3DH and PQXDH: starting a session with someone offline

Alice wants to message Bob, who is offline. Bob has uploaded a prekey bundle in advance: his long-term identity key (IK), a signed prekey (SPK, rotated every week or so, signed by IK), and a batch of one-time prekeys (OPK). Alice fetches the bundle, verifies the SPK signature, generates an ephemeral key (EK), and computes several Diffie-Hellman (DH) values:

DH1 = DH(IK_A, SPK_B)      mutual authentication (Alice's identity)
DH2 = DH(EK_A, IK_B)       mutual authentication (Bob's identity)
DH3 = DH(EK_A, SPK_B)      forward secrecy
DH4 = DH(EK_A, OPK_B)      only if a one-time prekey was available: replay protection, better forward secrecy
SK  = KDF(DH1 || DH2 || DH3 || DH4)                      X3DH

PQXDH adds a post-quantum KEM (ML-KEM / Kyber) prekey PQPK_B, signed by IK_B:
(CT, SS) = KEM.Encaps(PQPK_B)       Alice sends CT in her first message
SK  = KDF(DH1 || DH2 || DH3 [|| DH4] || SS)              PQXDH: harvest-now-decrypt-later resistant

Server stores:  IK_B (public), SPK_B + signature, OPK_B[], PQPK_B + signature, PQ one-time keys
Server never sees: any private key, EK_A private, SK, message keys

Double ratchet: why the server does not care, mostly

After setup, each message uses a fresh key from a symmetric ratchet (a KDF chain), giving forward secrecy: stealing today's keys does not decrypt yesterday's messages. Each time the conversation changes direction, a new DH exchange advances a DH ratchet, giving post-compromise security: after a key theft, the session heals once a fresh DH happens. For the backend this means: messages carry a ratchet header (sender's current DH public key, message number), clients keep a bounded cache of skipped message keys for out-of-order delivery (for example at most 1,000), and the server must deliver in order per device where it can, but never needs keys.

Key distribution service

PUT  /v1/keys                       # device uploads, authenticated as account+device
     { identityKey, signedPreKey: { id, pub, sig }, pqLastResort: { id, pub, sig },
       oneTimePreKeys: [{ id, pub } x 100], pqOneTimePreKeys: [{ id, pub, sig } x 10] }
GET  /v1/keys/{account}/{deviceId}   # returns ONE bundle; atomically removes the OPK it hands out
     -> { identityKey, signedPreKey, oneTimePreKey?, pqPreKey }   # pqPreKey: one-time if left, else last-resort
GET  /v1/keys/count                  # device checks stock; refills when < 10 remain
PUT  /v1/messages/{account}          # per-device ciphertexts, see multi-device
     { messages: [{ deviceId, registrationId, type, body }] }

• Atomic consumption: each one-time prekey must be handed out once. Use a per-device queue with an atomic pop (a conditional delete in the database), so two concurrent senders never get the same OPK.
• Exhaustion: if a device's OPKs run out (offline for a long time, or someone draining them), the server returns the bundle without an OPK; the session still works on DH1 to DH3, with weaker replay protection for the first message. Rate limit bundle fetches per requester to stop deliberate draining.
• The server is not trusted with keys, only with storing public ones honestly. That is exactly what key transparency checks.

Multi-device

Each device has its own prekeys and its own sessions. To send, Alice's client fetches Bob's device list, and encrypts the message separately for each of Bob's devices and each of Alice's own other devices (so her desktop sees what her phone sent). The server checks the submitted device set against the current list and rejects with 409 stale devices if it is out of date, so the client refreshes and retries. To stop the server silently adding a device of its own, the device list is signed by the account's identity key (or a primary device) and covered by key transparency, and users are notified when a device is added.

Groups

Metadata minimisation

• Sealed sender: the envelope's sender identity is encrypted to the recipient, so the server sees only the destination. The recipient's client verifies a short-lived sender certificate inside, issued by the server, so it knows the sender is a real account. To limit spam, sealed-sender delivery requires a delivery token derived from the recipient's profile key, which only contacts have.
• No stored social graph: contact discovery through hashed lookups inside a secure enclave or with private set intersection, not by uploading address books in the clear; group membership stored encrypted, with zero-knowledge credentials proving membership.
• Logs: no IP-to-account logs beyond what abuse prevention needs, short retention, and drop delivery receipts from server logs.
• What still leaks: the recipient, timing, size (pad ciphertexts to buckets), IP at connection time, and the fact that you use the service.

Key transparency

A malicious or compelled server could hand Alice a fake identity key for Bob and sit in the middle. Safety numbers (a fingerprint users compare in person or by QR code) catch this but few people check. Key transparency publishes every account-to-key mapping in an append-only, verifiable log (a Merkle tree, as in WhatsApp's Auditable Key Directory); clients check that the key they received is the one in the log and that their own entry has not been changed, and independent auditors check the log is append-only.

Abuse reporting when the server cannot read

• User reports: the reporting user's client, which has the plaintext, forwards the reported messages (and recent context) to the trust and safety team. The reporter is choosing to share what they received, which does not break E2EE for anyone else.
• Message franking: the sender's client includes a cryptographic commitment to the message that the server records (without learning content). On report, the commitment proves the reported plaintext really was sent by that sender, so reports cannot be forged.
• Metadata-based signals: account age, message rate, fan-out to non-contacts, number of blocks and reports. These catch spam without content.
• Client-side scanning (matching content against hashes on the device before encryption) is the contested option: it re-introduces a content inspection point and a list nobody can audit. Name the trade-off rather than pick it silently.

Failure modes

Trade-offs to state