Packing made the proof fast to produce. It did not make it small to send: the honest response still contains the whole witness (the secret data the proof is about), and at our scale that is megabytes. This final article is the size lever: a recursive "fold" that halves the proof again and again. It compresses a transcript that grows in step with the witness down to one that grows only with its logarithm, taking the shipped proof from ~6 MB to about 52 KB.
Prerequisites: The NIZK (the commit–challenge–respond skeleton and its soundness), and ideally OLE Packed. The idea rhymes with the classical inner-product argument, so it helps to have met Bulletproofs (the elliptic-curve proof system that made this kind of compression famous), but we build it up from scratch.
Recall the Sigma protocol from The NIZK, the three-move
commit–challenge–respond exchange. Its last move is the response: the prover sends
z = y + c·w, its secret witness w scaled by the challenge c and masked by the
one-time randomness y.
The problem is that z is the same length as the witness w. Even after packing shrinks the witness, z for the full relation is a long vector of ring elements (the 64-slot polynomials all of this arithmetic lives in), and writing it out is the bulk of the proof's bytes.
At production parameters the flat Sigma response over the scalar encoding is around 6 megabytes, dominated entirely by shipping z. (Packing alone brings the unfolded proof to roughly 113 KB. Folding takes it the rest of the way, and the two levers compose rather than overlap.)
So here is the question. Can the prover convince the verifier that it knows a valid z satisfying the public check, without sending all of z?
The answer is yes. The technique is one of the prettiest ideas in modern proof systems: the inner-product argument, realized here in the lattice setting.
The check the verifier wants to run has the shape of an inner product. That is the familiar dot
product ⟨a, z⟩ = a₁z₁ + a₂z₂ + … (multiply matching entries, add everything up), only over
vectors of ring elements rather than plain numbers.
Something like ⟨a, z⟩ = t, where a is a public vector built from the challenge
and the constraints, and t is a public target. The prover wants to show it knows a z making
that hold, cheaply.
Here is the recursive trick. Split both vectors in half (a left piece and a right piece) into
z = (z_L, z_R) and a = (a_L, a_R). The inner product then decomposes:
⟨a, z⟩ = ⟨a_L, z_L⟩ + ⟨a_R, z_R⟩
The prover sends two small cross-term values, the verifier sends one random challenge x, and both parties fold the halves together:
z′ = z_R + x·z_L and a′ = a_L + x·a_R
The new vectors are half the length. And here is the magic. There is a new target t′, which
the verifier computes from the cross-terms, the challenge and the old target. The folded claim
⟨a′, z′⟩ = t′ holds if and only if the original one did, except with negligible
cheating probability.
So one round has reduced a length-n inner-product claim to a length-n/2 one, at the cost of two small values.
Then repeat. Each round halves the length and adds two small messages. After log₂ n rounds (the number of times you can halve n before reaching one), the vector is a single element, which the prover simply sends.
Total proof size: O(log n) small messages (a count that grows with the logarithm of n, not with n itself) instead of one length-n vector. A megabyte-scale z becomes a few kilobytes of fold messages. That is the entire size win, and it is why the final proof is 52 KB rather than 6 MB.
The classical version of this is the Bulletproofs inner-product argument, from Bootle et al. and Bünz et al. It shrinks range proofs (proofs that a hidden number lies inside a stated interval) from linear to logarithmic in exactly this way.
Our contribution is not the idea. It is making the idea work over a lattice commitment, with all the extra care that setting demands.
Two things make lattice folding harder than the elliptic-curve original, and both trace back to themes from The Proof Ring and The NIZK.
No dividing by the challenge.
The classical inner-product argument folds with x on one side and its reciprocal x⁻¹ on the
other. But our proof ring deliberately avoids assuming challenges can be divided by (that they
are invertible) in the fast case. That was the
whole invertibility discussion in The Proof Ring.
So we use an inverse-free fold, the variant that combines the halves using only x and never
x⁻¹. That is the z′ = z_R + x·z_L above, with no reciprocal anywhere.
It is a known but non-default variant, chosen precisely so the fold's soundness rests on the same partial-split ring that keeps extraction exact. The proof system and the ring were co-designed; you cannot pick the ring for one and the fold for the other.
Norms must stay bounded.
Here is the subtle killer. Soundness in the lattice world is not just "the equation holds." It is "the equation holds and the witness is short" (made of small numbers), and that shortness is what binds to SIS, the Short Integer Solution problem the commitment's security rests on (The NIZK).
But folding grows the numbers. z′ = z_R + x·z_L has larger entries than z_L or z_R
did, because of the multiplication by x, and over log n rounds that growth compounds.
If the final folded witness is no longer short, the SIS reduction (the argument tying any cheat to that hard lattice problem) collapses, and the proof proves nothing. So every fold has to be paired with a norm check (a check on the witness's size as a vector) certifying the folded witness stayed within bounds.
That is the tension that makes lattice folding intricate. Challenges must be large enough to give soundness per round, and small enough that repeated folding does not blow the norm past the SIS threshold.
Getting both at once is why the LaBRADOR-style recursion (LaBRADOR being the lattice proof framework this system follows) is a multi-week research artifact rather than a weekend port of Bulletproofs.
The norm check has its own miniature version of the same problem. How do you prove a long hidden vector z is short without sending z? Sending it to check its norm would un-compress everything we just compressed.
The tool is a random projection, and it leans on a classic result. The Johnson–Lindenstrauss lemma says that projecting a high-dimensional vector onto a handful of random directions approximately preserves its length.
So the prover reveals a few random ±1-combinations of z's entries (each entry randomly added or subtracted into one running total) as a tiny sketch, and the verifier checks the sketch is small.
Why that is convincing: if the true z were large, its random projections would be large with
high probability. On average the sketch's squared length equals the vector's:
E[‖projection‖²] = ‖z‖², where E is the expected value and ‖z‖ is the length of z. So a
small sketch is real evidence of a small z.
The sketch is a constant number of values regardless of how long z is, so the norm proof stays succinct too. And the projection rows are derived from the Fiat–Shamir transcript (the running hash of everything said in the proof so far), so the prover cannot grind them against its own z: it cannot keep retrying until it finds projections that flatter a too-long witness.
One design choice recorded here is worth surfacing.
An early version used a looser, deterministic infinity-norm bound: the size of the single largest entry. We tightened it to the Johnson–Lindenstrauss ℓ₂ concentration bound: the Euclidean length ‖z‖ of the whole vector, which is what the projection actually tracks.
The loose version was safe, but it forced larger parameters everywhere downstream. Tighter norm accounting is free bytes and free speed.
The catch is margin. You have to keep enough statistical slack that an honest proof never spuriously fails, and that margin is completeness: the thing you must never optimize away. It is exactly what makes tightening a norm bound delicate rather than trivial.
Folding shrinks the response. There is a parallel cost on the commitment side.
The prover committed to its witness with t = A·w, and the verifier has to be convinced the
folded claims are consistent with that commitment. Done naively, checking it reintroduces a cost
that grows linearly with the witness.
The shipped answer is simpler than it looks. The commitment is a fixed κ ring elements (a small constant count) regardless of witness length, so the commitment side is constant rather than linear, and it was never the term that needed shrinking.
Between logarithmic fold messages and a constant-size commitment, no part of the proof is linear in the witness. That is the definition of a succinct proof.
(Greyhound (The NIZK) is built in-tree as an alternative front-end;
its opening proof grows only with the square root of the witness length N, via a
√N × √N tiling. It is not on the shipped path, and the constant-size commitment is why it has
not needed to be.)
An honest note on how this interacted with packing.
Once we packed the witness down to about 200 ring elements (OLE Packed), it was already small. The elaborate square-root machinery on the verifier side was solving a problem we had mostly eliminated: a flat opening of 200 elements is cheap.
That observation let us collapse several parallel proof formats into one. The packed-and-folded proof was simultaneously the smallest and the fastest, so the separate sublinear-verifier design became redundant.
We kept the fold, since it is what gives the 52 KB, and let the rest go. Convergence to a single proof, one more time, because the best option dominated the others outright.
Putting the levers together, the campaign reads like a ladder:
presence_id at the end of it.Fifty-two kilobytes is not a vanity metric. It is the difference between a proof you can attach to every contact lookup on a mobile network and one you cannot. The entire multi-article descent (the ring, the packing, the folding) exists to turn "post-quantum verifiable OPRF" (an OPRF is a keyed hash the server computes for you without ever seeing your input) from a theoretical possibility into 52 KB that fits in a phone's pocket.
This closes the descent. Back up to The NIZK, or all the way up to Contact Discovery.