HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

Algorithm: The Transparency Log

13 min read

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 — and each of them discharges that obligation 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.

1. The leak that authentication does not close

Article 05 §5 closes directory poisoning: you cannot publish an entry for a presence_id 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, gets an X-Wing public key the operator generated, and 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 and no amount of better cryptography in the lookup fixes it. The lookup answers honestly; 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.

2. What a log changes

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. Every binding the directory will ever serve is first inserted into one structure; that structure is periodically hashed down to a single 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.

3. What is actually in a row

The dictionary is a sparse Merkle tree over Poseidon2 (KoalaBear field), and 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 of the identifier under a symmetric directory key the server holds:

label = directory_label(k_dir, phone_id, version)          // Poseidon2, KoalaBear

Symmetric is a deliberate divergence. Key-transparency systems conventionally label with a VRF, whose public key lets anyone check the label was computed correctly — but public-key means a structure Shor's algorithm 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, and it is why the production system is a from-scratch aZKS 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 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 (Plonky3) whose public values are (key_commitment, label, phone_id, version) and whose statement is "this label is the PRF of this id at this version, under the key committed by key_commitment". That commitment —

key_commitment = Poseidon2("KCMT" ‖ k_dir ‖ r)

— 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 cannot equivocate on the key any more than it can on 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, hashed into the leaf. A client that 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 for any number — precisely the harvest attack the symmetric PRF was chosen to prevent. It is KDIR_LEN = 8 KoalaBear limbs, roughly 248 bits, and for a while it was one limb, about 31 bits, recoverable from a single (phone_id, label) pair — which 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.

4. One tree, three namespaces

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 against a key list the log does not hold.

The one-byte prefixes exist to make the byte-strings length-disjoint, so a proof minted for one namespace can never be replayed as an answer in another. All three resolve through the same verifier, so that is 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 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.

5. The head, the chain, and the heartbeat

Epochs are cut on a 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 — Ed25519 and ML-DSA-65, 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 a cut (KT_EPOCH_DEBOUNCE_SECS, two seconds). 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, and under a frozen root every check a client makes passes honestly, because at that epoch the stale answer really was the latest one. A quiet log and a log freezing one client's view are 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 — which 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 fleet) plus 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.

6. Why the directory serves only what the log can already prove

Here is a failure mode that exists because the client fails closed — a gate creating 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 returns 404 for — and 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 folded view that publish_epoch writes as it drains each namespace-D entry into the tree, in the same transaction as the signed head; /v1/discovery/lookup reads that 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 meaning — the latest published intent — and still answers "what is my own current inbox".

7. Detection needs someone to look

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 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 reproduces exactly that leaf, which 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 1:1 send in ten carries kt_gossip { epoch, sth_hash } — the sender's trusted head, ridden inside the encrypted payload. Inside is not incidental: gossip is a cross-user check, and putting it in the envelope would hand the relay precisely the who-talks-to-whom edge the entire Relay series exists to withhold. It is best-effort and never gates delivery.

The recipient compares (ingestGossip). Same epoch, different hash: two heads exist for one epoch — a fork — and it alarms. Older epoch: nothing, 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 KT-root keys pinned in the app, and requires the gossiped hash to match the one it was handed — a mismatch is two heads for one epoch, so it alarms — before advancing its anchor. That 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.

8. Three things a log structurally cannot do

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 with more fields on it than the signed root commits to, and a field the verifier does not compare is a field the server may choose freely — with the STARK still verifying, the label still binding, the path still folding to the real root, and 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.

9. The residual

A log makes equivocation 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), but the client verifies only the immediate prev_sth_hash link between consecutive heads, so 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.

References

  • B. Laurie, "Certificate Transparency," ACM Queue 2014, and RFC 6962 — the append-only-log-plus-gossip design this is an instance of.
  • M. Chase, A. Deshpande, E. Ghosh, H. Malvai, "SEEMless: Secure End-to-End Encrypted Messaging with Less Trust," CCS 2019 — the auditable key directory (aZKS) model, VRF labels included.
  • M. Melara et al., "CONIKS: Bringing Key Transparency to End Users," USENIX Security 2015 — where the self-monitoring obligation and the gossip-for-non-equivocation argument come from.
  • Guarding the Directory — the poisoning defense this article extends past the operator.
  • The Admission Token §5 — namespace K in use, and why "committed" needs version binding and v+1 absent to mean "current".
  • Known-Answer Testing — the complementary check: a log proves what a server committed to, a hidden known-answer test proves it actually used it.

Next, the anatomy of a single lookup proof and the four checks it has to survive: What a Lookup Proof Binds.