The single biggest speedup in the whole proof system came not from a cleverer algorithm but from a cleverer representation. The naive proof stores one number per polynomial, wasting 63 of every 64 coefficient slots. Packing 64 numbers into each polynomial shrinks the secret being proven about by 64×, and that ripples into a several-fold faster prover (the code that produces the proof). This article is how, and why it is harder than it sounds.
Prerequisites: The NIZK (the proof skeleton) and The Proof Ring (the exact-integer discipline). Familiarity with the convolution relation from OLE from Ring-LWE helps.
The proof ring (the polynomial number system the whole proof computes in) has elements of degree D = 64. So each ring element is a polynomial with 64 coefficient slots: 64 positions, each holding one number.
The witness is the secret data the proof makes its claims about: here, roughly thirteen thousand integers making up the secret s, the randomness R, and the carries. The naive encoding puts one integer per ring element, as a constant polynomial (v, 0, 0, …, 0): one real number in the first slot, zeros in the rest.
Read that again. Every ring element carries a single meaningful number and 63 zeros. We are paying for 64 slots and using one.
That waste is not confined to storage. The commitment A·w, the response z, the
Fiat–Shamir hashing (the hash trick that lets the prover generate its own challenges instead of
talking to a live verifier): every step of the commit–challenge–respond skeleton from
The NIZK scales with the number of ring elements. So 63 of every 64
units of the prover's work go into shuffling zeros.
Concretely, the witness runs to roughly thirteen thousand scalar variables (plain single numbers) when it could be a couple of hundred packed ring elements.
The obvious question follows: why not pack 64 real integers into each element's 64 slots? That turns thousands of near-empty polynomials into a couple of hundred full ones (a 64× smaller witness), and everything the prover does scales with witness size, so this should be the dominant lever.
It is. The catch is that packing changes what ring multiplication does to your data, and the proof's relations are built out of multiplications.
When your 64 numbers are the coefficients of one polynomial, ordinary polynomial multiplication does not multiply them slot by slot. It convolves them. Output slot k is a sum of the products ai·bj over every pair of positions with i + j = k (every slot mixes with every other), complete with the negacyclic sign flips from Lattice Foundations, the minus signs picked up by terms that wrap around past the end of the polynomial.
So pack two vectors a and b into two ring elements and multiply, and you do not get an element holding the 64 matching products ai·bi. You get a scrambled convolution with everything mixed together.
This is a real problem. The OLE (oblivious linear evaluation, the encrypted multiply-and-add this whole proof is about) gives us a relation full of things that look like "multiply these two vectors slot by slot and sum": inner products (dot products) and coefficient-wise checks.
A packed representation gives us convolutions where we wanted dot products. Packing saves 64× only if we can still express the relations we need through convolution, rather than despite it.
Two operations rescue us, and they are the technical heart of the packed prover.
Here is the first trick, and it is genuinely elegant.
Pack vector a into a ring element. Pack the reverse of vector b into another: call it σ(b), meaning b read backwards with the ring's sign convention. Multiply the two, and look at just the constant term of the product: the degree-0 coefficient, slot zero.
Because of how convolution lines up indices, that one coefficient is exactly the dot product (written ⟨a, b⟩, with ct(·) meaning "take the constant term"):
ct(a·σ(b)) = a₀·b₀ + a₁·b₁ + … = ⟨a, b⟩
The full product is still a scrambled 64-slot polynomial. But one specific slot of it holds the honest answer. The convolution did all the cross-terms, and we simply read the slot where the indices align.
So a dot product over the integers can be computed inside the packed ring by a single ring multiply plus a take-the-constant-term projection. That identity (a staple of the LaBRADOR line of work, the lattice-proof framework our proof follows) is what lets us keep proving inner-product-shaped relations after packing.
The evaluation relation from OLE from Ring-LWE is a pile of
exactly such inner products: each output coefficient is ⟨M_i, s⟩ plus mask and
carry terms. Packing turns every one of them into a constant-term-of-a-product statement, and the
proof certifies those.
Reading one dot product per multiply is progress, but the OLE has thousands of coefficient
constraints. These are the E0 and E1 identities, one per output coefficient: the two
exact-integer relations pinning the reply ciphertext's two halves c0 and c1. Proving each
separately would hand back the size we just saved.
The second trick is random aggregation. Instead of proving constraint 1 and constraint 2 and so on individually, the prover proves a single random linear combination of them, one weighted sum over all of them:
Σ_k ψ_k·constraint_k = 0
where the weights ψk are challenge scalars: random numbers fixed only after the prover has committed, so nothing can be tailored to them.
If any individual constraint were false, that combination is nonzero with overwhelming probability. This is the Schwartz–Zippel principle again: a random linear check catches any single failure. Thousands of constraints collapse into a constant number of aggregated ones.
There is a genuine subtlety the implementation had to get exactly right.
The constant-term projection from §3 is only ℤq-linear: linear over plain numbers modulo q. It survives addition and scaling by plain numbers, but not multiplication by a whole polynomial. So the aggregation challenges ψ have to be scalars, not full ring elements.
That constraint has a cost: a single round of scalar aggregation lets a cheat slip through with
probability about 1/q per prime. To reach the 2−128 security target we run the aggregation for
K = 2 rounds, which lands at q⁻² ≈ 2⁻¹⁸⁹, comfortably clear. The prover then reveals
the K aggregated ring values and proves them consistent with the committed witness.
This dot-product-over-the-integers prover, with sound aggregation of constant-term inner products, is the piece that made packing work end to end. Getting it right meant importing the exact aggregation lemma from the LaBRADOR paper rather than improvising one.
One trap is worth flagging, because it is the kind of bug that silently corrupts a proof.
The aggregated values ψ·target involve products of numbers each near 294, the
proof modulus. Multiply two numbers that size and the result overflows a 128-bit integer.
So the consistency check has to be computed in the ring, prime by prime via the CRT (the Chinese Remainder Theorem decomposition from The Proof Ring, which works modulo several small primes instead of one huge number), never as a naive 128-bit multiply. Get that wrong and honest proofs fail: a completeness bug (completeness being the promise that honest proofs always pass) hiding inside a performance optimization.
The measured effect, at production parameters: packing shrank the witness from roughly thirteen thousand scalar variables to about two hundred ring elements: the promised ~64×. But the prover speedup is not 64×, and it is worth being honest about why, because it illustrates where the real costs live.
That O(M) floor (a cost proportional to M, no matter what) is fundamental. The proof is about an M-coefficient ciphertext, so something has to read all M values.
Net, packing turned a prover that took a couple of seconds into one several times faster. Combined with folding for size (Succinct Proofs by Folding), that is what put the whole verifiable resolve under a second on a phone.
The two levers are independent and they compose. Packing is the throughput lever: fast to produce the proof. Folding is the size lever: small to send it.
We spent real effort chasing that O(M) floor before accepting it, and two of the biggest wins were almost embarrassingly mundane.
The Fiat–Shamir hashing was absorbing every one of the M derived constraint coefficients; we fixed it by hashing a compact digest of the statement instead. And a prover-side sanity check was recomputing the whole relation on every call; we gated it behind debug builds.
Neither was a cryptographic insight. Both were "stop doing O(M) work you do not need to." Once the asymptotics are right, the remaining speed is ordinary profiling. And it matters just as much.
Why not pack even more aggressively, or use a different transform?
The 64 slots are the ring degree D from The Proof Ring, and that degree was fixed by a soundness requirement: differences of challenges must be invertible, so that a cheating prover can always be pinned down.
We cannot enlarge it just to pack more without revisiting the whole splitting and invertibility analysis. Packing to exactly D is the most we get for free.
Why not a fancier packed multiplication?
The candidate is a full NTT, the Fourier-style transform that turns polynomial multiplication into cheap slot-by-slot multiplication.
Same answer as The Proof Ring: the fastest packed multiply wants a fully-split ring, and that breaks exact extraction: the step of the soundness argument that pulls a valid witness out of any prover who manages to convince the verifier. We kept the honest partial-split multiply. Packing lives within the ring the soundness analysis already blessed.
Why not abandon packing and just make the prover parallel? Threading divides the same work across cores; packing removes work by not storing zeros. Removing work beats dividing work: a smaller witness is faster on one core and on many. (An earlier tiled prover did run its commitment across cores; packing replaced that path outright, which is the point: the structural win made the parallel one unnecessary.)
a·σ(b), and random scalar aggregation, run for two rounds to reach 2−128 soundness,
which collapses thousands of
constraints into a constant number of checks. Together they form the "dot-product-over-ℤ"
prover (ℤ being the integers).