Contact Discovery
Algorithm: What a Lookup Proof Binds
14 min read
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.
1. What arrives, and what has to be true of it
Discovery turns a phone number into an opaque lattice identifier — phone_id on the wire, stored
re-keyed as the presence_id of article 05 — and that identifier into a directory entry: the
peer's X-Wing discovery key and the inbox to reach them at. Article 05 established that the
entry must be authenticated — unlinkability is not 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. Article 14 built that log; this one 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, with a FRI-STARK proving in-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:
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: a rotation appends version+1 rather than
overwriting, so the tree is strictly append-only. Third, three namespaces share the one tree,
disjoint by label length — 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. Two of
the errors below bite in only one of those. Fourth, each hourly epoch emits a tree head signed
hybrid (Ed25519 and ML-DSA-65, both required) and chained by prev_sth_hash, while
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.
2. Four bindings
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 are
[key_commitment ‖ label ‖ phone_id ‖ version] — three 16-limb KoalaBear digests and one field
element, 49 in all — and 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 folds smt.leaf up to the signed
root, and the resulting presence bit 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.
3. The field nothing compared
VersionEntry carries the committed value twice. There is smt.leaf, which is 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 gate the client actually calls to bind a served key is
kt_verify_resolve_opens (backend/pixie-zk/src/kt.rs), and 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, kt_gossip sees the same sth_hash everyone else sees, and an
auditor replaying every append-only transition from genesis 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 — and 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 (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 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 — a group invitation whose signature is verified against the committer's leaf resolved from the tree carried inside that same invitation 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?"
4. Answering a different question
Check 4 closes the value binding. Two reasoning errors survive it, and both take the same form: the verifier answers honestly — 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 — label_id_and_version splits those bytes, the trailing four big-endian as the version
and the rest hashed into the directory id — and refuse when the two disagree.
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 — never forking, never lying, handing a
different honest generation to each cohort it wants to bucket, which is the exact equivocation
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, so v and v + p are the same public value and derive the
same label — a u32 equality check passes 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 at an absurd version while serving an old key set. Real versions are
small counters; anything that can alias is rejected outright.
5. Inclusion is not latest
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, demand a non-inclusion proof for v+1 under the same signed root. Under one
root v+1 either exists or it does not, so two clients that both check this cannot be shown
different latest generations without being shown different roots — and two roots for one epoch is
a fork, which is exactly what the STH chain and the gossip are built to catch. That is
kt_verify_absent, and 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 — 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.
6. Freshness: authenticity is not currency
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 section 5 without breaking a check in it, because
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
(article 14 §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 skew tolerance. 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,
because 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 — throwing 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 (a hostile contact can claim any epoch, so
nothing here trusts the peer), require the gossiped sth_hash to match, and only then advance
the local anchor. No new alarm machinery is needed, which is the nice part — 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,
and refusing on unavailability here means refusing to mint admission tokens, which means no
messages can be sent at all. So staleness returns "I could not check", loudly logged, while 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.
7. Two parameters, without which none of it means anything
Every mechanism above assumes two quantities are what they claim to be, and both were wrong here at some point, which is a reasonable prior 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 in about 2³¹ Poseidon2 evaluations from a single published
pair: minutes, embarrassingly parallel. Whoever recovers it can compute the label for any number
and turn the directory into a membership oracle — 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
Merkle-commitment salts and the HidingFriPcs random codewords. Both took their randomness from
SmallRng::seed_from_u64(1), under a comment noting that a real CSPRNG was wanted in production,
on the path that actually proves. Deterministic salts are publicly derivable, so the
statistical-ZK masking hid nothing — and the witness that masking exists to hide is k_dir
itself. Both now come from the OS CSPRNG, and the fact that it took two passes is the instructive
part: the first fix moved the salts and left the codewords, which are the ones HidingFriPcs
actually masks the trace with. 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.
8. The residual
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 lagging an
epoch — 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 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.
"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 — 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.
References
- M. Chase, A. Deshpande, E. Ghosh, H. Malvai, "SEEMless: Secure End-to-End Encrypted Messaging with less trust," CCS 2019 — the append-only authenticated dictionary this replaces with a post-quantum construction.
- B. Laurie, "Certificate Transparency," CACM 2014, and RFC 9162 — where "inclusion is not latest", signed tree heads, gossip, and split-view detection were worked out at scale.
- Wikipedia: Merkle tree, Key transparency, Pseudorandom function family.
Back to The Transparency Log, which builds the structure these checks read, or across to The Admission Token, whose key set is namespace K.