The mathematics of the Veil: anonymous sender delivery

Encrypting content is the easy half. The harder problem is metadata: the fact that Alice sent a message to Bob at a particular time is itself information — often more valuable than the message, and almost never protected. The recipient needs to be told "this message is for you." The network needs to know where to deliver it. Nobody needs to know who wrote it — and if the envelope is designed correctly, nobody does.

That is the job of the Veil, Enchant's anonymous sender delivery system, and it is the most intricate piece of mathematics in the LibEnchant library. This post derives both versions of the Veil exactly as they run: the original V1 construction and the newer V2, which trades V1's per-message DH for a single-writer envelope that can address many recipients at once. Both share one property — the server that routes a Veil message never learns the sender's identity, and cannot link two messages from the same sender. The sender's identity is recoverable only by the recipient, who must hold the corresponding private key.

Why the envelope must be anonymous

A conventional Enchant message travels as an envelope addressed by device ID. The server sees: this device sent a sealed packet to that device. Over a week, that single observation produces a social graph — call graph, timing correlation, frequency, sleep schedule — drawn entirely from routing headers that never needed to exist.

The Veil inverts the addressing model. The sender does not reveal themselves in the envelope at all. Instead, the envelope contains enough per-recipient secret material that exactly one intended recipient can unlock it — and the server cannot tell which slot belongs to whom, cannot decrypt the sender field, and cannot tell two envelopes came from the same keyboard.

Veil V1: per-message anonymous delivery

What it is. The original construction. A message is encrypted under keys derived from a fresh ephemeral DH between the sender's ephemeral key and each recipient's identity key, with the sender's own identity encrypted and sealed inside the envelope.

How the keys are built. The sender generates a fresh ephemeral X25519 key pair per message. For each recipient, the sender computes one X25519 agreement — sender ephemeral private × recipient identity public — and feeds it through HKDF. The salt is where the anonymity lives: it is the literal byte string "UnidentifiedDelivery" (13 bytes, the library constant SALT_PREFIX) concatenated with the two public keys in an order that depends on direction, so sender and recipient compute the same value while the server sees only random bytes:

$$\mathrm{eph_salt} = \begin{cases} \text{UnidentifiedDelivery"} \parallel \mathit{pub}_{\mathrm{their}} \parallel \mathit{pub}_{\mathrm{our}} & \text{sending} \\ \text{UnidentifiedDelivery"} \parallel \mathit{pub}$$

$$(\mathrm{chain_key} \parallel \mathrm{cipher_key} \parallel \mathrm{mac_key}) = \mathrm{HKDF\text{-}SHA256}(\mathrm{X25519}(sk_{\mathrm{eph}},\ \mathit{pk}_{\mathrm{recipient}}),\ \mathrm{salt}=\mathrm{eph_salt},\ \mathrm{info}=\varnothing,\ L=96)$$

That yields 96 bytes: a chain key (32), a cipher key (32), and a MAC key (32) — VeilEphemeralKeys in the source. The message itself is sealed with the cipher key:

$$\text{wire message} = \underbrace{\mathit{nonce}}$${24\ \mathrm{B}} \parallel \underbrace{C}{\mathrm{XChaCha20\text{-}Poly1305}} \parallel \underbrace{\mathrm{HMAC\text{-}SHA256}(mac_key,\ \mathit{nonce} \parallel C \parallel mac_key)}{32\ \mathrm{B}}wire message=24 Bnonce​​∥XChaCha20-Poly1305C​​∥32 BHMAC-SHA256(mackey, nonce∥C∥mac_key)​​

The sender's identity is encrypted too. The recipient must be able to see who wrote the message; the server must not. So the sender's identity public key (32 bytes) is encrypted with a second key set — VeilStaticKeys, derived from a separate DH between the sender's identity key and the recipient's identity key, salted with the chain key and the ciphertext:

$$(\mathrm{cipher_key}' \parallel \mathrm{mac_key}') = \mathrm{HKDF\text{-}SHA256}(\mathrm{X25519}(IK$$

The encrypted sender key is itself MAC'd (HMAC-SHA256, 32 bytes) so a tampered envelope is rejected before decryption. The recipient decrypts the message under the ephemeral keys, then decrypts the sender field under the static keys — recovering the sender's identity. The server sees neither. The sender field never exists in plaintext on the wire; it exists only inside the envelope, under two layers of encryption, and is recoverable only by the holder of the recipient's private key.

   Sender (one per message)          Server                     Recipient
   ───────────────────────          ──────                     ─────────
   eph keypair (fresh)              sees: version,             holds IK private key
        │                                eph_pub,
        ├── DH(eph, IK_recipient) ──►    encrypted_static      DH(eph, IK_recipient)
        │                                encrypted_message         = same secret
   HKDF → chain‖cipher‖mac         (no sender, no link         HKDF → same keys
        │                               between envelopes)         │
   encrypt message, encrypt                                      decrypt sender
   sender key, both MAC'd                                        and message

What V1 achieves — and its cost. The server cannot identify the sender, cannot link two messages from the same sender (every message has a fresh ephemeral), and cannot decrypt the sender field. But each message pays one X25519 DH and one 96-byte HKDF per recipient. For a message addressed to a large group, the sender's work grows linearly — and the recipient must try every slot to find theirs. Fine for a chat between two people. Wrong tool for a group of 500. Hence V2.

Veil V2: one secret, many recipients

What it is. The redesign. Instead of deriving per-recipient keys from per-recipient DH, V2 starts with a single random "sender secret" $m$ (32 bytes), derives the message key and the sender's ephemeral keypair from it — and then wraps $m$ for every recipient with a DH-XOR construction. The result: one envelope, arbitrarily many recipients, one encryption of the message, and no per-recipient symmetric keys.

Step 1 — derive the message key and ephemeral keypair. Both come from the single random value $m$, through domain-separated HKDF calls with the fixed salt $0^{32}$:

$$e = \mathrm{HKDF}(m,\ \mathrm{salt}=0^{32},\ \mathrm{info}=\text{``Veil Sender v2: r (2023-08)"},\ L=32) \qquad \text{→ ephemeral keypair}$$

$$K = \mathrm{HKDF}(m,\ \mathrm{salt}=0^{32},\ \mathrm{info}=\text{``Veil Sender v2: K"},\ L=32) \qquad \text{→ message key}$$

The message is encrypted once, under $K$, with XChaCha20-Poly1305. Every recipient ends up recovering the same $K$.

Step 2 — wrap $m$ for each recipient. For each recipient, the sender computes an X25519 agreement (their ephemeral private × the recipient's identity public), feeds it through HKDF with a "DH-wrapping" label, and XORs the result with $m$:

$$c_i = \mathrm{HKDF}(\mathrm{X25519}(sk_{\mathrm{eph}},\ \mathit{pk}_i),\ \mathrm{salt}=0^{32},\ \mathrm{info}=\text{``Veil Sender v2: DH"},\ L=32) \oplus m$$

The recipient — who holds the other half of that X25519 agreement — computes the same HKDF output and XORs again:

$$m = c_i \oplus \mathrm{HKDF}(\mathrm{X25519}(sk_i,\ \mathit{pk}_{\mathrm{eph}}),\ \mathrm{salt}=0^{32},\ \mathrm{info}=\text{``Veil Sender v2: DH"},\ L=32)$$

XOR with itself: $c_i \oplus h_i \oplus h_i = m$. The message key $K$ is re-derived from $m$ via the fixed label, so every recipient who can recover $m$ can decrypt the message. This is the key architectural shift from V1: the wrap is cheap (one DH + one HKDF per recipient) and the encryption is shared (one ciphertext for everyone).

Step 3 — authenticate each slot. A wrapped secret is useless if anyone can inject a forged slot — a fake recipient entry that, when opened, decrypts to garbage that still "validates." So each slot carries a 16-byte authentication tag, derived from the same agreement plus the exact slot contents, with a "sender-proving" label:

$$at_i = \mathrm{HKDF}(\mathrm{X25519}(sk_{\mathrm{eph}},\ \mathit{pk}_i),\ \mathrm{salt}=0^{32},\ \mathrm{info}=\text{``Veil Sender v2: DH-sender"},\ L=16)[0 \ldots 16)$$

The tag binds the slot to the sender's ephemeral key and the recipient's identity — a recipient can verify that the slot was written by the holder of the corresponding ephemeral private key, and the tag depends on $c_i$, so it cannot be spliced from another envelope.

The wire format. Everything is fixed-width, parseable without decryption:

┌────────────────────────────── Veil V2 envelope ──────────────────────────────┐
│ version(1) │ count(4, BE)                                                   │
│ ┌──────────────────────────── per recipient ────────────────────────────┐   │
│ │ device_id(4) │ recipient_pub(32) │ c_i(32) │ at_i(16)                │   │
│ └───────────────────────────────────────────────────────────────────────┘   │
│ ... (count slots)                                                            │
│ ephemeral_pub(32) │ nonce(24) │ ciphertext                                   │
└──────────────────────────────────────────────────────────────────────────────┘

The server sees: a version byte, a count, a list of opaque 84-byte slots (each containing a device ID and three random-looking values), an ephemeral public key, a nonce, and a ciphertext. It does not see the sender. It cannot test a slot against a suspect's key — every slot is under a fresh DH. It cannot correlate envelopes from the same sender — each envelope uses a fresh $m$ and a fresh ephemeral. And the per-recipient tags, verified on the receiving device, reject forgeries before decryption is ever attempted.

Inside the payload: USMC and the sender certificate

What rides inside the envelope is the unidentified sender message container (USMC): a structured payload carrying the message type, the sender's certificate, the contents, a content hint, and — for group messages — the group ID. The contents themselves are encrypted with the session keys established by the X3DH/Triple Envelope handshake; the Veil's job is to get the envelope to the right device without revealing the sender.

The sender certificate is the mechanism by which the recipient authenticates the sender, even though the server never saw it: it carries the sender's UUID, E.164 number, device ID, expiration, and identity key, all signed by a server certificate — which is itself signed by Enchant's trust root (Ed25519). The certificate is sealed inside the Veil envelope; only the recipient who can open the envelope can read it. The server cannot revoke it, alter it, or learn from it.

What the Veil provably gives — and the honest boundary

The boundary is equally explicit: the Veil hides who sent, not that something was sent. The server still sees the delivery event — it is the delivery network, after all — and the size of the envelope, and the recipient device IDs. An adversary who records all traffic can still see "an envelope of 4.2 KB was delivered to device 7" — what they cannot see is which of the world's senders produced it. That is the difference between metadata being a public ledger and metadata being a needle without a haystack, and it is the difference the Veil's mathematics — two rounds of per-recipient DH in V1, one wrap in V2 — enforces byte for byte in LibEnchant (enchant_veil_encrypt_v1 / enchant_veil_encrypt_v2 and their decrypt counterparts).