Several articles across these series reach a point where they need a fact to be the same fact for everybody: the discovery key served for a phone number, the roster of devices on an account, the list of live token-issuing keys. Each of them settles the matter with the same four words: "committed to the transparency log." None of them says what the log is. This article is the debt being paid.
Prerequisites: Guarding the Directory, whose last defense (authenticated publication) is exactly where this one picks up.
Guarding the Directory, §5 closes directory poisoning: you cannot publish an
entry for a presence_id (the anonymous identifier the discovery system derives from a
phone number) unless you hold a phone-ownership certificate for it. That stops a
stranger claiming your slot. Read it again and notice who is not covered.
The certificate is checked by the directory server. The directory is served by the directory server. Nothing in that arrangement constrains the directory server.
It can accept your honest, certificate-backed publication, store it, serve it faithfully to nine hundred people. And serve one substituted key to the tenth.
That tenth person's client resolves your number and gets back an X-Wing public key the operator generated. (X-Wing is the hybrid key exchange a first message is sealed to, encrypted so only the key's holder can open it. It runs a lattice-based scheme and an elliptic-curve one together, and it is taken apart in The Attested Push Seal.) The client seals its first handshake to the operator instead of to you.
Every signature checks out. The victim sees a normal contact appearing normally.
This is the shape worth staring at, because it is not a cryptographic break. No amount of better cryptography in the lookup fixes it: the lookup answers honestly, but it answers a question whose answer the server chooses.
The attack is targeted, silent and deniable: the row can be swapped back afterwards. Its one weakness is that it requires the operator to say different things to different people, and that is the seam a transparency log is built to open.
A transparency log does not make the operator honest. It makes the operator consistent, by removing the ability to answer per-victim.
The mechanism is an append-only authenticated dictionary: a lookup table that can only be added to, never edited, and whose every answer can be checked against a single public fingerprint. Every binding the directory will ever serve (a binding is one association: this identifier, this key) is first inserted into one structure. That structure is periodically hashed (run through a one-way fingerprint function) down to a single value called the root. The root is signed and published, and every lookup comes back with a proof folding the answer you were given up to that published root.
Two properties follow. The operator cannot serve a binding that is not in the tree, because it cannot produce the proof. And it cannot serve you a different tree, because the root is a single public value other people are also watching.
Substituting one victim's key therefore stops being a database edit and becomes a commitment to a second, incompatible history: a fork. Forks are loud. That is the whole trade: the operator's cheapest attack goes from invisible to detectable.
The dictionary is a sparse Merkle tree, the structure of §2 made concrete. Rows sit at
the leaves; each pair of leaves is hashed together, each pair of results is hashed again, and so
on until one value, the root, remains. "Sparse" means a slot waits for every label that could
ever exist, and empty slots cost nothing. The hash is Poseidon2 over the KoalaBear field (a
field is arithmetic done modulo a fixed prime), chosen because it is cheap to prove things about
inside a zero-knowledge proof: a proof that convinces you a statement is true while revealing
nothing else. A row is a (label, value) pair. Both halves are less obvious
than they look.
The label is not the phone number. A published, world-readable directory keyed by
presence_id would undo the entire premise of the series: the tree is a durable artifact, so
anything recoverable from it is recoverable forever, including by a future adversary with a
quantum computer and a decade of patience. So the label is a keyed pseudorandom function (PRF)
of the identifier (a hash whose output looks random to anyone who lacks the key) under a
symmetric directory key the server holds, symmetric meaning one secret key and no public
half:
label = directory_label(k_dir, phone_id, version) // Poseidon2, KoalaBear
A note on the two names, because both appear across this series and they denote the same
32 bytes. presence_id is what the earlier articles call the value the oblivious PRF (a keyed
hash the server helps compute without ever seeing your input) produces
on the device; phone_id is what the directory's own API and this article's formulas call the
field carrying it. There is no re-keying step between them: the client computes the value and
sends it as-is, so the identifier the directory stores is the identifier the client derived.
Symmetric is a deliberate divergence.
Key-transparency systems conventionally label with a VRF, a verifiable random function: a keyed hash that comes with a public key, so anyone can check the label was computed correctly. But a public key is a structure Shor's algorithm (the quantum algorithm that breaks today's public-key mathematics) eventually eats. Harvest the tree today, invert the labels in 2040.
A symmetric PRF has no public key to break, so a harvested tree stays opaque. The implementation calls this everlasting label privacy. It is why the production system is a from-scratch aZKS (an append-only zero-knowledge set, a directory you can prove things about without it revealing who is in it) rather than an off-the-shelf VRF-labeled one.
Which immediately creates a problem. If the label key is secret and symmetric, nobody outside the server can check that a label really is the PRF of the identifier you asked about.
The operator could derive your victim's label under a different key and hand you a perfectly valid inclusion proof (the chain of hashes showing a row really sits in the tree) for a row that has nothing to do with the number you queried.
So label correctness is proved in zero knowledge. Every lookup carries a FRI-STARK (built with the Plonky3 library): a proof of the kind The NIZK sets up, a short certificate that a computation was done correctly, but built out of hashing alone, so it carries no public key of its own for a quantum computer to break.
Its public values (the inputs and outputs the proof states openly, as opposed to the secrets it
hides) are (key_commitment, label, phone_id, version), and its statement is: this
label is the PRF of this id at this version, under the key committed by key_commitment. A
commitment is a hash that locks a value in without revealing it. This one:
key_commitment = Poseidon2("KCMT" ‖ k_dir ‖ r)
It is a 64-byte constant pinned in the app binary (SocialBackendConfig.ktKeyCommitment).
Every proof must verify under it. So there is exactly one directory key, the same for everyone,
and the server can no more tell different users different stories about the key than it can
about the root.
The value is a commitment, not the plaintext. For a discovery row the committed plaintext is
"pixie:kt-D-leaf:v1" ‖ discovery_xwing_pubkey ‖ discovery_inbox ‖ version (the ‖ symbol
means the byte-strings are joined end to end), hashed into the
leaf. A client that already holds a candidate binding re-commits it and compares; a client that
holds nothing learns nothing.
A footnote on secrets that are only nominally secret.
All of this rests on k_dir staying secret. Recover it and the published tree becomes a
membership oracle (a way to test, number by number, who is in the directory), which is
precisely the harvest attack the symmetric PRF was chosen to
prevent.
The key is KDIR_LEN = 8 KoalaBear limbs (a limb is one field element, a chunk of roughly 31
bits), so about 248 bits in all. For a while it was one limb, about 31
bits, recoverable by brute force from a single (phone_id, label) pair. And such a pair is
exactly what a lookup proof
hands out.
That defect, and a companion one in the prover's randomness, are taken up in What a Lookup Proof Binds §7. Neither changed a single verification result, which is why neither was visible from outside.
There is one tree, one root, one signed head, and three different mechanisms committing to it. They are kept from colliding by the crudest possible means: label length.
| ns | label input | bytes | what the row commits |
|---|---|---|---|
| D | phone_id ‖ u32(version) |
36 | a contact's X-Wing discovery key and inbox |
| I | "I" ‖ account_kt_handle ‖ u32(version) |
37 | an account's signing keys and its device-chain head |
| K | "K" ‖ u32(version) |
5 | a digest of credential-svc's live OPRF key set |
D is what the discovery resolve gate reads before a first handshake is sealed to a stranger's
key. I backs identity-key transparency and the clone detection in §7. K is read by the
admission token mint, which refuses to issue tokens
against a key list the log does not hold. (An OPRF, an oblivious PRF, is a keyed hash the
server computes for you without ever seeing your input, the same primitive behind
presence_id in §3.)
The one-byte prefixes exist to make the byte-strings length-disjoint: labels from different namespaces can never have the same length, so a proof minted for one namespace can never be replayed as an answer in another. All three resolve through the same verifier, which makes that a real requirement rather than a tidiness one.
Sharing a tree has a payoff: one root means one thing to keep fresh, one thing to gossip about, and one place a fork shows up. Three separate logs would be three independent opportunities to equivocate.
Entries are immutable. Rotating your discovery key (retiring it in favor of a fresh one) does not overwrite version 3; it appends version 4. Old versions stay, which is what makes a complete, gap-free history provable, and what makes "here is a key that was inserted for your number in April" a checkable statement.
An epoch is one tick of the log's publishing clock, and epochs are cut on that clock:
KT_EPOCH_SECS, hourly by default. Each cut folds the pending queue
into the tree and emits a signed tree head: epoch number, root, tree size, timestamp, and a
prev_sth_hash linking it to the previous head. The signature is hybrid in the sense
Guarding the Directory §5 sets out: Ed25519, a classical
elliptic-curve signature, and ML-DSA-65, a post-quantum lattice one,
both required, verified against keys pinned in the app.
The chain matters as much as the signature. A signed root proves the log said it;
prev_sth_hash proves where in the sequence it said it. A client keeps its last trusted head
and refuses one whose epoch has gone backwards: the rollback defense.
An hour is a long time to wait to become reachable, so a publish also nudges the log into
cutting an epoch early (KT_EPOCH_DEBOUNCE_SECS, two seconds after the publish).
The rule pointing the other way is subtler. A tick with nothing pending would naturally be a no-op, but a log that stops emitting is a problem, because a validly-signed root from last month is still validly signed.
The rollback guard catches an epoch that moves backwards. It does nothing about one that simply stops. Under a frozen root every check a client makes passes honestly, because at that epoch the stale answer really was the latest one. From one client's chair, a log that has gone quiet for everyone and a log freezing that client's view alone produce the same observation.
So an idle tick cuts an epoch anyway once the newest head is older than KT_HEARTBEAT_SECS, an
hour. An empty cut is a legitimate append-only no-op: nothing staged, root unchanged, every
existing proof still verifying. That is what makes the heartbeat cheap enough to be
unconditional, and what makes silence itself a signal.
The client half of the property is a bound on the head's age: maxSTHAge, three hours against an
hourly beat, so one missed tick does not flip the whole fleet into refusal. The other half is the
gossip loop in §7, which pulls
a frozen client forward onto an epoch its own server is then visibly behind.
What a Lookup Proof Binds §6 takes that apart.
Staleness is reported as unavailable, never as evidence. An honestly-down log looks identical from the client's side, and treating it as compromise would take the whole network down with it.
Here is a failure mode that exists because the client fails closed: that is, it refuses to proceed whenever it cannot verify. A safety gate can create its own outage.
A publish writes three things: the servable directory row, the advertised version counter, and a pending tree entry. The first two are visible to every resolver immediately. The third is not provable until an epoch is cut.
In the window between, the directory hands out a binding at version N that /v1/kt/lookup
answers with a 404 (not found). The fail-closed resolve gate reads "the directory served me a
binding the log has
never heard of" as exactly what it is built to read it as: substitution evidence. It refuses to
send the handshake.
That window used to be up to a full hour, and it opened on every publish, so an established contact went dark whenever the peer relaunched.
The fix is to make the directory strictly behind the log rather than ahead of it. Migration 0023
adds discovery_published, a view of what has already been folded into the tree, which
publish_epoch writes as it drains each
namespace-D entry, in the same database transaction as the signed head, so a row lands
there at the exact moment it becomes provable, never before.
/v1/discovery/lookup reads that view instead of the raw publish table, so a resolver is only
ever handed a binding already committed at a signed root. The raw table keeps its own meaning
(the latest published intent) and still answers "what is my own current inbox".
Everything so far makes substitution detectable. Detection is a verb with a subject, and a log with no readers is a filing cabinet. Two loops supply the subject.
Self-monitoring. Each device periodically walks the version history of its own row and
requires every published version to open to a binding it authored (selfMonitor). A
commitment "opens" when you show the value inside it and the hash checks out. A version that
opens to something else (or will not verify at all) is a key someone inserted for your number,
and it raises a hard alarm.
Note what this does that no proof can. The log guarantees consistency, but only you know which value is correct, so the correctness check has to be run by the party who knows.
Namespace I runs the same loop with a stricter notion of mine (selfMonitorIdentity): a
published version counts as self-authored only if a device-signed entry in your own synced device
chain (the signed, append-only list of devices on your account) reproduces exactly that leaf.
That is what turns the loop into clone detection: a version
the directory inserted cannot satisfy it without one of your device keys.
Cross-user gossip. Self-monitoring catches an insertion in your row. It says nothing about
whether you and your contacts are looking at the same tree at all. So roughly one direct 1:1
send in ten
carries kt_gossip { epoch, sth_hash }: the sender's trusted head, riding inside the
encrypted payload. Inside is not incidental. Gossip is a cross-user check, and putting it on the
outer envelope (the part of a message the relay server can read) would hand the relay
precisely the who-talks-to-whom edge the entire
Relay series exists to withhold. Gossip is best-effort and never
gates delivery.
The recipient compares (ingestGossip), and there are three branches.
Same epoch, different hash. Two heads exist for one epoch. That is a fork, and it alarms.
Older epoch. Nothing happens; an old head is evidence of nothing.
Newer epoch. It does not take the peer's word, since a hostile contact could claim any epoch. It fetches that epoch's head from the server, requires the hybrid signature to verify under the key-transparency (KT) root keys pinned in the app, and requires the gossiped hash to match the one it was handed. A mismatch is again two heads for one epoch, so it alarms. Only then does it advance its anchor.
That last branch is what closes the freeze from §5, and it needed no new alarm machinery. Adopting a newer head converts "your view is frozen" into "your server is serving something older than what you trust", which is the rollback the client already refuses.
Worth stating plainly, because "it's in the transparency log" gets used as though it settles more than it does.
It cannot tell you a value is correct. It tells you everyone was shown the same one. If a wrong key is published, the log publishes it faithfully, proves it to everyone identically, and reports no anomaly. Consistency is not correctness, and the gap between them is filled by the self-monitor in §7: a human-authored assertion of "that isn't mine", not a proof.
It cannot act on its own. The log produces evidence. Evidence that nobody reads changes nothing, and an attacker who is confident the monitoring is not running faces the pre-log threat model exactly. Every guarantee here is really a guarantee about the monitoring loop, with the log as its instrument.
It binds only what the verifier actually checks. This is the sharpest one. A proof bundle is a wire structure (the actual bytes sent over the network), and it carries more fields than the signed root commits to. A field the verifier does not compare is a field the server may choose freely. The STARK still verifies, the label still binds, the path still folds to the real root, and there is no tree write for a monitor or a gossip to see. The system shipped in exactly that state, and What a Lookup Proof Binds is the anatomy of the four bindings a proof carries, including the one that was not being checked.
A log makes equivocation (serving different answers to different people) detectable, not impossible. Nothing here prevents the server from signing a second root and serving it to one person; it only guarantees that doing so leaves an artifact which cannot be un-signed. The substitution still happens. The victim's first handshake still goes to the wrong key. What changes is that the operator must now hope nobody compares notes.
Which makes the guarantee only as good as the comparing, and the comparing is thinner than the structure suggests.
Gossip rides a fraction of 1:1 messages between people who already talk to each other. So a victim who is newly onboarded, or isolated, or communicating only with the very account the operator controls, may hold a forked head for a long time with no honest peer to contradict it.
And "append-only" is, on the client, mostly an assumption. identity-svc will serve an append-only
proof between two epochs (/v1/kt/consistency), evidence that the later tree extends the
earlier one without edits, but the client verifies only the immediate
prev_sth_hash link between consecutive heads. A device that was offline across several epochs
accepts the newest signed root without checking that the epochs it skipped only ever added.
Verifying that range is auditor work, and there is no auditor. No independent monitor runs, and no public witness network exists to gossip roots outside the app's own message traffic.
That is the honest shape of it. The tree is the instrument; the guarantee is a property of who picks it up. Nothing in the cryptography here makes anyone look.
Next, the anatomy of a single lookup proof and the four checks it has to survive: What a Lookup Proof Binds.