A directory lookup comes back with a key and a proof. This article is about what that proof actually asserts (four separate bindings you can hold in your head at once) and about the period in this codebase when it asserted three of them impeccably and did not bind the one field it was asked about.
Prerequisites: The Transparency Log, which builds the structure this article verifies against. Guarding the Directory supplies the threat model.
Discovery turns a phone number into an opaque, lattice-derived identifier: the presence_id of
Guarding the Directory, computed on the device by the oblivious
PRF (a keyed hash the server helps compute without ever seeing your number) and sent as-is, so
the value the directory stores is the value the client derived.
It then turns that identifier into a directory entry: the peer's X-Wing discovery key, and the inbox to reach them at. (X-Wing is a hybrid key exchange running a lattice scheme and a classical elliptic-curve one together, so sealing a message to it, encrypting it so only the key's holder can open it, forces an attacker to break both.)
Guarding the Directory established that the entry must be authenticated: unlinkability (the server not learning who is looking up whom) is not the same thing as authorization. But authentication by the server serving it is worth exactly what that server's honesty is worth, which here is nothing.
So the binding goes into the transparency log, and the client refuses any key the log cannot prove. The Transparency Log built that log. This article is about the verifier at the other end of it.
Four things from there are load-bearing. First, an entry's address is not a plain hash of the id but a symmetric keyed PRF: a pseudorandom function, a hash whose output looks random to anyone without the key, symmetric in that there is no public half. A FRI-STARK (a short zero-knowledge proof, cheap to check and leaking nothing about the key itself) proves, step by step inside its own circuit, that a served label really is that PRF of the id you asked about, under a directory key the app has pinned by commitment, a hash that locks the key in without revealing it:
label = directory_label(k_dir, phone_id, version)
= Poseidon2("LABL" ‖ k_dir ‖ phone_id ‖ version) over KoalaBear
key_commitment = Poseidon2("KCMT" ‖ k_dir ‖ r) pinned in the app
Second, entries are immutable and versioned: rotating a key (retiring it for a fresh one)
appends version+1 rather than
overwriting, so the tree is strictly append-only.
Third, three namespaces share the one tree, kept disjoint by label length (the ‖ symbol means
byte-strings joined end to end): D, discovery
keys, phone_id ‖ u32(version), 36 bytes; I, the identity and device roster,
"I" ‖ handle ‖ version, 37; and K, the OPRF key set behind
the admission token, "K" ‖ u32(version), 5. (An
OPRF, an oblivious pseudorandom function, is a keyed hash the server computes for you without
ever seeing your input.) Two of
the errors below bite in only one of those namespaces.
Fourth, each hourly epoch (one tick of the log's publishing clock) emits a tree head:
the root, the single hash summarizing the whole tree at that moment, plus metadata. The head is
signed hybrid
(a classical Ed25519 signature and a post-quantum ML-DSA-65 one,
both required) and chained by prev_sth_hash, each head naming the one before it (STH is
short for signed tree head). Meanwhile kt_gossip {epoch, sth_hash} rides
inside sealed messages between users, so "is this the root everyone else sees?" gets asked
without the relay learning who asked whom.
The verifier is verify_version_entry in backend/pixie-zk/src/azks.rs. It takes the pinned
key_commitment, a signed root, the phone_id and version you asked about, the entry, and
whether you expect presence or absence. It runs four checks, best read as four independent
English sentences.
1. The label is honestly derived. The STARK verifies. Something of the form
label = PRF(k_dir, id, version) was computed under some key committed as key_commitment.
2. It is derived from your question. The STARK's public values (the inputs and outputs
the proof states openly) are
[key_commitment ‖ label ‖ phone_id ‖ version]: three digests of 16 limbs each plus one lone
field element, 49 values in all. (A limb is one element of the KoalaBear field: arithmetic done
modulo a fixed prime.) The verifier compares every one of them against what the caller pinned
and asked for. Check 1 without check 2 proves a correct computation on unknown inputs, which is
worth nothing.
3. That leaf is in this tree. The sparse Merkle path (the handful of sibling hashes that
let you recompute the tree's single root hash starting from one leaf) folds smt.leaf up to
the signed root, and the
resulting presence bit (present or absent) matches what the caller expected. This is the only check
that touches the root, and therefore the only one that connects the entry to anything the server
signed.
4. The value you are about to use is that leaf. e.value == e.smt.leaf.
Read the first three again and notice what none of them touches. Check 1 is about a computation. Check 2 is about the inputs to that computation. Check 3 is about a label's position in a tree. Not one of them says anything about the contents of the entry. And the contents are the whole reason anyone ran a lookup.
VersionEntry carries the committed value twice. There is smt.leaf, the copy the
Merkle path folds, and hence the only copy the signed root ever commits to. And there is value,
a plain field on the same wire struct, the bytes as they actually travel over the network. The
gate the client actually calls to bind a served key is
kt_verify_resolve_opens (backend/pixie-zk/src/kt.rs). What it does is re-commit the bytes
it was served and compare them against proof.entry.value:
proof.entry.value == value_commit(expected_value)
Check 4 did not exist until recently. Nothing compared the two copies. And so a genuine proof
(produced by the honest prover, for the honest binding) with that one field rewritten would
open to anything at all. The STARK still verifies, because it was never told about value. The
label still binds to the queried phone_id and version, for the same reason. And the Merkle
path still folds smt.leaf to the real signed root, because smt is untouched.
Sit with the consequences.
There is no tree write and no second root. The epoch chain is intact, the hybrid signature is
genuine, and kt_gossip sees the same sth_hash everyone else sees. An auditor replaying every
append-only transition from genesis (the log's very first epoch) finds nothing, because
nothing was appended.
The attack lives entirely in the gap between the value the log commits to and the value the client reads. Every other mechanism in the system is busy watching the log.
The blast radius is everything the log is for. A substituted discovery key in namespace D, which is a person-in-the-middle on first contact. A rewritten identity or device-roster tuple in I. And a tailored OPRF key set in K: precisely the per-user tagging key (one chosen to mark a single user's tokens as theirs) that the transparency check in the admission token exists to make impossible.
The general shape is worth naming, because it recurs: a structure that carries the same fact twice, where one copy is authenticated and the other is the one the code reads.
It appears elsewhere in this system. Consider a group invitation that carries its own copy of the tree, and whose signature is verified against the committer's leaf resolved from that carried copy. It has the identical defect: proving integrity while proving nothing about authorization.
When a verifier's inputs include something that was supposed to be derived from its own output, the question is not "does this verify?" but "verify against what?"
Check 4 closes the value binding. Two reasoning errors survive it, and both take the same form: the verifier honestly answers a question nobody asked.
The first is version. ResolveProof carries a version field, which
verify_version_entry faithfully binds into the STARK's public values. But that field is
server-chosen: the bundle is internally consistent for whatever version the server decided to
prove. So kt_verify_resolve must compare it against the version in the label the caller actually
queried, and refuse when the two disagree. (label_id_and_version does the splitting: the
trailing four bytes, read big-endian, most significant byte first, are the version, and the
rest is hashed into the directory id.)
Namespace K is the sharp case, for a structural reason. Its label is "K" ‖ u32(version), so the
id-part is a single constant byte and every generation of the key set lives at the same
directory id, separated only by version.
Without the equality check, a server answers "show me generation 7" with a flawless proof for generation 3. It never forks and never lies. It just hands a different honest generation to each cohort (each group of users) it wants to sort into buckets, which is the exact equivocation (different answers for different people) namespace K exists to prevent.
The same move rolls a namespace-D binding back to a key the peer has since rotated away from.
A second version bug lives in the field arithmetic.
The STARK binds the version as Val::new(version) over KoalaBear, a small prime field: every
quantity in the proof is taken modulo a fixed prime p, the way a 12-hour clock face takes
hours modulo 12. On that clock, 1 and 13 land on the same mark; in the field, v and v + p
are the same public
value and derive the same label. So a u32 equality check can pass while the proof
attests a different generation. Hence if version >= KOALABEAR_ORDER { return false }.
K bites here too. Its leaf plaintext carries no version of its own, so nothing downstream would notice, and a server could park a device's monotonic floor (the highest-version-yet-verified marker of §5) at an absurd version while serving an old key set.
Real versions are small counters. Anything big enough to alias (to collide with a smaller
version modulo p) is rejected outright.
The second surviving error is subtler: being in an append-only log proves a generation existed, never that it is current.
Exploiting that requires publishing nothing dishonest. An operator publishes several entirely
legitimate generations (each correctly labelled, committed, folded into the root) and serves
generation 5 to one cohort and generation 6 to another. Every client verifies. No root forks.
kt_gossip compares sth_hash values across users and finds them identical, because they are
identical. The log is behaving perfectly; it was just never asked the right question.
The fix is to ask a question whose answer cannot differ between cohorts. Alongside the inclusion
proof for v (the Merkle path showing v is in the tree) demand a non-inclusion proof
for v+1 under the same signed root: a proof that the slot for v+1 is still empty.
Under one root, v+1 either exists or it does not. So two clients that both run this check
cannot be shown different latest generations without being shown different roots; two roots
for one epoch is a fork, which is exactly what the chain of signed tree heads and the gossip are
built to catch.
That is kt_verify_absent. Mechanically, verify_absent is verify_version_entry with the
presence bit inverted: same STARK, same label binding, same root, same value check.
On the client, KeyTransparencyService.verifyKeySet demands both before it will let a token mint
proceed, and it is the only path that does. The discovery gate takes a cheaper route, and §8 is
where that bill comes due.
One piece of state carries the property across time. "v is latest" now says nothing about a
later session. So the highest version a device has actually verified is persisted as a monotonic
floor, a number that only ever rises (discoveryFloor, one per phone_id, and a single
global keySetFloor), and a lower
version offered afterwards is evidence, not an outage. The proof for the superseded version is
perfectly genuine, which is exactly why inclusion alone can never catch it.
The floor is monotone in the version, though, and that leaves a gap it cannot close by itself: an old key republished at a higher version clears the floor comfortably.
Nothing stops that at the client, because the publish endpoint takes no session: no login state accompanies the request. The year-long phone-ownership certificate is the only authorization, so a captured publish body stays replayable for as long as the certificate lives.
The server side closes it. The directory records every binding a number has retired and refuses to accept one back, so a replayed body is rejected before it can ever be proved.
Client-side monotonicity and server-side history are two halves of one property, and neither is sufficient alone.
One property survives everything above, and it is the one most likely to be missing from a verifier that otherwise looks complete: 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.
A server that freezes a single client's view (serving the same genuine head forever while
everyone else advances) defeats §5 without breaking a single check in it. Under a frozen root
the "v+1 is absent" proof is satisfied honestly: at that epoch, v really was the newest
thing in the tree.
Every signature verifies, every binding holds, and the client is simply living in the past.
Three things close it, and they interlock:
The log must tick even when idle (The Transparency Log, §5). Otherwise a quiet directory and a frozen view are the same observation, and no client-side checking separates them.
So a tick with nothing pending cuts an epoch anyway once the newest signed head is an hour old
(KT_HEARTBEAT_SECS). An empty cut is a legitimate append-only no-op (nothing inserted, root
unchanged, every existing proof still verifying), which is what makes the heartbeat cheap enough
to be unconditional.
Silence becomes a signal because an honest log never falls silent.
The client must bound the head's age. trustedLatestSTH rejects a head older than
maxSTHAge (three hours, against an hourly heartbeat), and one dated in the future beyond a
five-minute tolerance for clock skew, the normal drift between machines' clocks. The timestamp
is covered by the STH signature, so it cannot be
back-dated without the pinned root key. Note where the check sits: before the chain
comparison. The same-epoch branch returns early, so a freshness check placed after it would be
skipped for precisely the client being held at a fixed epoch.
A peer's newer epoch is adopted, not ignored. ingestGossip used to require the gossiped
epoch to equal the trusted one, discarding anything ahead, which threw away the only message that
could have revealed a freeze.
Now an epoch ahead of ours triggers adoptPeerEpoch: fetch that epoch's signed head, verify it
under the pinned root, require the gossiped sth_hash to match, and only then advance the local
anchor. A hostile contact can claim any epoch, so nothing in that sequence trusts the peer.
The nice part is that no new alarm machinery was needed. A server that keeps serving the older
head from here now trips the existing rollback guard and comes back compromised. Adoption
converts a freeze into the one failure the client already refuses.
And a discipline running through all of it: stale is treated as unavailable, never as evidence.
A genuinely down log produces a stale head indistinguishable from a targeted freeze. Refusing on unavailability here would mean refusing to mint admission tokens, which means no messages can be sent at all.
So staleness returns "I could not check", loudly logged. The accusing verdicts stay reserved for
the unambiguous: compromised for a failed root signature, an epoch that moved backwards, or two
roots for one epoch; blocked and mismatch for a served value that is not what the log commits.
The age bound does not buy refusal. It buys that a stale root can no longer come back
verified.
Every mechanism above assumes two quantities are what they claim to be. Both were wrong here at some point, which is a fair baseline guess for how often they are wrong elsewhere.
The width of k_dir. The directory key is KDIR_LEN = 8 KoalaBear limbs, roughly 248 bits.
It was one limb (about 31 bits) because a helper took hash_bytes(..)[0] and discarded the
rest.
The lookup endpoint hands out (phone_id, label) pairs by construction; that is what a proof
is. So the key was recoverable from a single published pair in about 2³¹ Poseidon2 evaluations,
roughly two billion hashes. That is minutes of work, and embarrassingly parallel: every guess is
independent, so the search splits cleanly across as many machines as you have.
Whoever recovers it can compute the label for any number and turn the directory into a membership oracle: a way to test, number by number, who is in it. That is the exact harvest attack the symmetric PRF was chosen to prevent. A post-quantum construction with a 31-bit key is not one.
The prover's randomness. build_config in stark.rs wires two independent hiding inputs:
the random values mixed into a proof so the proof itself reveals nothing about the secret it was
computed from. They are the Merkle-commitment salts (a salt is a one-off random value stirred
into a hash) and the HidingFriPcs random codewords.
Both took their randomness from SmallRng::seed_from_u64(1) (a generator seeded with the
constant 1, so it produces the same "random" numbers on every run) under a comment noting that
a real
CSPRNG, a cryptographically secure random number generator, was wanted in production. This was
on the path that actually proves.
Deterministic salts are publicly derivable (anyone can rerun the seeded generator), so the
masking hid nothing. And the witness the
masking exists to hide, the proof's secret input, is k_dir itself. Both sources now come from
the OS CSPRNG.
The instructive part is that it took two passes. The first fix moved the salts and left the
codewords, and the codewords are what HidingFriPcs actually uses to mask the trace, the
step-by-step record of the computation being proved. A config with two
randomness sources will happily look fixed after you have corrected one of them.
The two k_dir defects reach one outcome by different routes: the width hands the key to anyone
with a laptop, the determinism to anyone who can recompute the masking that was supposed to hide
it. Neither is a thing tests catch, because everything still verifies: correct proofs of the
correct statement, with the secret leaking out the side.
Three boundaries, in the order they matter.
Unavailability is a state the server controls, and the paths do not treat it alike.
Staleness, an unreachable log, a namespace-K version "not yet resolvable", a replica (a secondary copy of the server's database) lagging an epoch behind: a client cannot tell any of them from an honest outage, so all of them degrade rather than accuse.
Where degrading costs only latency, the code defers. The discovery resolve gate holds the hello
(the first handshake message) back and retries, because sending it would seal our envelope key
and our certificate's
userIDHash to a binding nobody vouched for.
Where refusing would break the product, it degrades the other way. The token mint proceeds unverified, since no tokens means no messages at all, and an identity or device-roster pin is adopted unverified.
So an operator who wants those two checks skipped need not forge anything: only be unavailable, persistently. What we get back is that the escape has to be persistent and loudly logged, rather than momentary and silent.
One path refuses outright rather than degrading, and the asymmetry is deliberate. A sign-in approval request seals to your own account's discovery record, and the reply it invites carries the account signing seed. An unproven binding there does not cost latency. It hands over the account. So that call fails closed on an unavailable log, accepting the outage as the cheaper outcome.
"Inclusion is not latest" is closed for the key set and not for a contact's key. The
v+1-absent demand of §5 runs on namespace K.
A discovery resolve verifies whichever version the server advertised, with only the
per-phone_id floor between it and an older generation. So on a first resolve, before any floor
exists, a genuine, correctly-proved, superseded binding verifies.
That is a key the peer has already rotated away from, and the ordinary reason to rotate is that the old one is no longer trustworthy. The peer's own self-monitor will not flag it either, because they really did author that version.
The floor closes the repeat. Nothing closes the first.
A freeze shorter than the head-age bound is invisible. The bound is a threshold, not a continuous measurement.
With an hourly heartbeat and a three-hour ceiling, a server can hold a client at a stale-but-fresh-enough head for the better part of three hours and nothing fires.
Adopting a gossiped newer epoch shortens that in practice, but only if a peer happens to send you a sealed message inside the window, which is traffic-dependent and therefore not a guarantee.
Tightening the bound narrows the gap. Nothing closes it, because "the head has not advanced yet" and "the head is not being allowed to advance" are the same observation until enough time passes to tell them apart.
Back to The Transparency Log, which builds the structure these checks read, or across to The Admission Token, whose key set is namespace K.