HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

Algorithm: Succinct Proofs by Folding

9 min read

Packing made the proof fast to produce. It did not make it small to send — the honest response still contains the whole witness, and at our scale that is megabytes. This final article is the size lever: a recursive "fold" that halves the proof again and again, compressing a linear-size transcript down to a logarithmic one, and 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, but we build it up from scratch.

1. Where the size goes

Recall the Sigma-protocol response from article 09: the prover sends z = y + c·w. 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, and writing it out is the bulk of the proof's bytes. At production parameters the flat proof is around 6 megabytes — dominated entirely by shipping z.

So the question is: 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, and the technique is one of the prettiest ideas in modern proof systems — the inner-product argument, realized here in the lattice setting.

2. Folding, from the intuition

The check the verifier wants to run has the shape of an inner product: 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 prove it knows a z making this hold, cheaply.

Here is the recursive trick. Split both vectors in half: z = (z_L, z_R) and a = (a_L, a_R). The inner product decomposes as ⟨a, z⟩ = ⟨a_L, z_L⟩ + ⟨a_R, z_R⟩. Now the prover sends just 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,        a'  =  a_L + x · a_R.

The new vectors z' and a' are half the length, and — this is the magic — there is a new target t' (computable by the verifier from the cross-terms, the challenge, and the old target) such that ⟨a', z'⟩ = t' holds if and only if the original ⟨a, z⟩ = t held, except with negligible cheating probability. So one round of interaction has reduced a length-n inner-product claim to a length-n/2 one, at the cost of sending two small values.

Repeat. Each round halves the length and adds two small messages. After log₂ n rounds the vector is a single element, which the prover just sends. Total proof size: O(log n) small messages 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 (Bootle et al. / Bünz et al.), which shrinks range proofs from linear to logarithmic in exactly this way. Our contribution is not the idea; it is making it work over a lattice commitment with all the extra care the lattice setting demands.

3. The lattice complication: keep it inverse-free and short

Two things make lattice folding harder than the elliptic-curve original, and both trace back to themes from earlier articles.

No dividing by the challenge. The classical inner-product argument folds with x on one side and x⁻¹ on the other. But in our proof ring, we deliberately avoided assuming challenges are invertible in the fast case (that was the whole invertibility discussion in article 10). So we use an inverse-free fold — the variant that combines the halves using only x, never x⁻¹ (z' = z_R + x·z_L, no reciprocal anywhere). This 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" (that shortness is what binds to SIS, article 09). But folding grows the size of the numbers: z' = z_R + x·z_L has larger entries than z_L, z_R because of the x· term, and after log n rounds the growth compounds. If the final folded witness is no longer short, the SIS reduction collapses and the proof proves nothing. So every fold has to be paired with a norm check that certifies the folded witness stayed within bounds. This is the tension that makes lattice folding intricate: challenges must be large enough to give soundness per round, but small enough that repeated folding doesn't blow up the norm past the SIS threshold. Getting both at once is why the LaBRADOR-style recursion is a multi-week research artifact rather than a weekend port of Bulletproofs.

4. Proving "the witness is short" without sending it

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 (which would defeat the whole point)? Sending z 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 — a tiny "sketch" — and the verifier checks that the sketch is small. If the true z were large, its random projections would be large with high probability (a second-moment argument: E[‖projection‖²] = ‖z‖²), so a small sketch is convincing 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. The projection rows are derived from the Fiat–Shamir transcript so the prover cannot grind them against its z.

There is a design choice recorded here worth surfacing: an early version used a looser, deterministic "infinity-norm" bound; we tightened it to the Johnson–Lindenstrauss ℓ₂ concentration bound because the loose version, while safe, forced larger parameters everywhere downstream. Tighter norm accounting is free bytes and free speed, as long as you keep enough statistical margin that an honest proof never spuriously fails. That margin — completeness — is the thing you must never optimize away, and it is exactly what makes tightening a norm bound delicate rather than trivial.

5. The commitment side: square-root openings

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 that the folded claims are consistent with that commitment. Done naively, checking the commitment reintroduces linear cost.

This is where Greyhound (article 09) earns its place: it is a polynomial commitment whose opening proof is only about √N in the witness length, using a clever √N × √N tiling of the committed data. So the commitment side contributes a square-root term, not a linear one. Between logarithmic fold messages and a square-root commitment opening, no part of the proof is linear in the witness anymore — which is the definition of a succinct proof.

An honest note on how this interacted with packing. Once we packed the witness down to ~200 ring elements (article 11), the witness was already small, so the elaborate square-root/sublinear machinery on the verifier side was solving a problem we'd mostly eliminated — a flat opening of 200 elements is cheap. This is the observation that 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 (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.

6. The number that mattered

Putting the levers together, the campaign reads like a ladder:

  • The flat proof (Sigma response written out) at production scale: ~6 MB.
  • Add succinct folding (this article): the response compresses from linear to logarithmic → down to about 52 KB.
  • Add packing (article 11): the prover gets several times faster (witness 64× smaller), and the verify becomes cheap because the packed witness is tiny.
  • Result, validated on an actual phone: the server produces the proof in a couple of seconds, the client verifies in well under a second, the whole verifiable contact resolve completes sub-second on the device, and the correct presence_id comes out.

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" from a theoretical possibility into 52 KB that fits in a phone's pocket.

7. Summary

  • The Sigma response z is as long as the witness, so the flat proof is ~6 MB — dominated by shipping z.
  • The inner-product fold recursively halves an inner-product claim, sending two small values per round, compressing z from linear to O(log n) — the ~6 MB → ~52 KB win.
  • The lattice setting forces two departures from the classical version: an inverse-free fold (no dividing by the challenge, matching the partial-split ring) and a norm check every round (folding grows entries; soundness needs them to stay short for the SIS binding).
  • Proving "the witness is short" without sending it uses a Johnson–Lindenstrauss random projection — a constant-size sketch whose length tracks the true norm.
  • The commitment side stays sublinear via Greyhound's √N openings; combined with packing, no part of the proof is linear anymore.
  • The payoff is measured, not theoretical: 52 KB, sub-second verify on a phone, which is what makes the verifiable OPRF shippable.

References

  • J. Bootle, A. Cerulli, P. Chaidos, J. Groth, C. Petit, "Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting," EUROCRYPT 2016 — the inner-product argument.
  • B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, G. Maxwell, "Bulletproofs: Short Proofs for Confidential Transactions and More," IEEE S&P 2018 — the classical logarithmic fold.
  • W. Beullens, G. Seiler, "LaBRADOR: Compact Proofs for R1CS from Module-SIS," CRYPTO 2023 — the lattice recursion, inverse-free fold, and norm control we implement.
  • N. Nguyen, G. Seiler, "Greyhound: Fast Polynomial Commitments from Lattices," CRYPTO 2024 — the √N commitment opening.
  • W. Johnson, J. Lindenstrauss, "Extensions of Lipschitz mappings into a Hilbert space," 1984 — the random-projection norm sketch.
  • Wikipedia: Bulletproofs, Johnson–Lindenstrauss lemma, Inner product.

This closes the descent. Back up to The NIZK, or all the way up to Contact Discovery.