HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

Algorithm: OLE Packed

8 min read

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. 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.

1. The waste

The proof ring has elements of degree D = 64: each ring element is a polynomial with 64 coefficient slots. The naive way to encode the proof witness — the ~16,000 integers making up s, R, and the carries — puts one integer per ring element, as a "constant polynomial" (v, 0, 0, …, 0).

Read that again: every ring element carries a single meaningful number and 63 zeros. We are paying for 64 slots and using 1. The commitment A·w, the response z, the Fiat–Shamir hashing — all of it scales with the number of ring elements, so 63/64 of the prover's work is spent shuffling zeros around. The witness is nz ≈ 16,384 ring elements when it could be about 256.

The obvious question: why not pack 64 real integers into each ring element's 64 slots, turning 16,384 near-empty polynomials into ~256 full ones — a 64× smaller witness? 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.

2. Why packing fights the relations

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 over all i + j = k of products aᵢ·bⱼ (with the negacyclic sign flips from article 01). So if you pack two vectors a and b into two ring elements and multiply, you do not get a ring element holding the 64 products aᵢ·bᵢ; you get a scrambled convolution mixing everything together.

This is a real problem, because the OLE relation we must prove is full of things that look like "multiply these two vectors slot-by-slot and sum" — inner products and coefficient-wise checks. A packed representation gives us convolutions where we wanted dot products. Packing saves 64× space only if we can still express the relations we need through convolution, not despite it.

Two operations rescue us, and they are the technical heart of the packed prover.

3. Reading one number out of a convolution: the constant term

Here is the first trick, and it is genuinely elegant. Suppose you pack vector a into a ring element, and you pack the reverse of vector b (call it σ(b), b read backwards with the ring's sign convention). Multiply them. Look at just the constant term (the degree-0 coefficient) of the product. Because of how convolution lines up indices, the constant term of a · σ(b) is exactly

ct( a · σ(b) )  =  Σᵢ aᵢ · bᵢ  =  ⟨a, b⟩.

The full product is still a scrambled 64-slot polynomial, but one specific slot of it — the constant term — holds the honest dot product we wanted. The convolution did all the cross-terms; we simply read the one slot where the indices align. So a dot product over the integers can be computed inside the packed ring by a single ring multiply and a "take the constant term" projection. This identity (a staple of the LaBRADOR line of work) is what lets us keep proving inner-product-shaped relations after packing.

The evaluation relation from article 06 is a pile of such inner products (each output coefficient is ⟨M[i], s⟩ plus mask and carry terms). Packing turns each into a "constant-term-of-a-product" statement, and the proof certifies those.

4. Aggregating many constraints without unpacking

Reading one dot product per multiply is progress, but the OLE has thousands of coefficient constraints (E0 and E1, one per output coefficient). Proving each separately would give back the size we saved. The second trick is random aggregation: instead of proving constraint₁ AND constraint₂ AND … individually, the prover proves a single random linear combination of them, Σₖ ψₖ · constraintₖ = 0, where the ψₖ are challenge scalars. If any individual constraint were false, the random combination is nonzero with overwhelming probability (this is the Schwartz–Zippel principle again — a random linear check catches any single failure). So thousands of constraints collapse into a constant number of aggregated checks.

There is a genuine subtlety the implementation had to get exactly right: the "constant term" projection from §3 is only ℤ_q-linear, so the aggregation challenges ψ must be scalars, not full ring elements, and a single round of scalar aggregation only gives soundness ≈ 1/q per prime. To reach the 2⁻¹²⁸ security target we run the aggregation for K = 2 rounds (q⁻² ≈ 2⁻¹⁸⁹, comfortably below 2⁻¹²⁸). The prover reveals the K aggregated ring values and proves them consistent with the committed witness. This "dot-product-over-ℤ" prover — sound aggregation of constant-term inner products — is the piece that made packing work end to end, and it took importing the exact aggregation lemma from the LaBRADOR paper rather than improvising.

A trap worth flagging, because it is the kind of bug that silently corrupts a proof: the aggregated values ψ · target involve products of numbers each near 2⁹⁴ (the proof modulus), whose product overflows a 128-bit integer. The consistency check has to be computed in the ring (per-prime, via CRT from article 10), never as a naive 128-bit multiply. Get that wrong and honest proofs fail — a completeness bug hiding inside a performance optimization.

5. What packing bought, honestly

The measured effect, at production parameters: packing shrank the witness from nz = 16,384 ring elements to about 256 — 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.

  • The commitment step (committing to the witness with the SIS matrix) scales with witness size, so packing shrinks it dramatically — the mask commitment dropped by ~40× in isolation.
  • But other costs scale with the number of constraints (M), not the witness, and those do not shrink: the aggregation still has to touch all M coefficient constraints to build the combined check. This O(M) floor is fundamental — the proof is about an M-coefficient ciphertext, so something must read all M values.

Net, packing turned a prover that took a couple of seconds into one several times faster, which — combined with folding for size (article 12) — is what put the whole verifiable resolve under a second on a phone. Packing is the throughput lever (fast to produce the proof); folding is the size lever (small to send it). They are independent and they compose.

We spent real effort chasing that O(M) floor before accepting it. Two of the biggest wins were almost embarrassingly mundane: the Fiat–Shamir hashing was absorbing all M · terms derived constraint coefficients (fixed by hashing a compact digest of the statement instead), and a prover-side sanity check was recomputing the whole relation on every call (fixed by gating it behind debug builds). Neither was a cryptographic insight; both were "stop doing O(M) work you don't need to." The lesson: once the asymptotics are right, the remaining speed is ordinary profiling, and it matters just as much.

6. Roads considered

Why not pack even more aggressively, or use a different transform? The 64 slots are the ring degree D from article 10, and that degree was fixed by the soundness requirement (invertible challenge differences). We cannot enlarge it just to pack more without revisiting the whole splitting/invertibility analysis. Packing to exactly D is the most we get "for free."

Why not a fancier packed multiplication (full NTT)? Same answer as article 10: the fastest packed multiply wants a fully-split ring, which breaks exact extraction. 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? We did also parallelize (the commitment and aggregation run across CPU cores), and that helps latency. But 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. Parallelism and packing compose, and we used both, but packing was the structural win.

7. Summary

  • The naive proof wastes 63 of every 64 ring-element slots (one integer per polynomial), making the witness ~16,384 elements when it could be ~256.
  • Packing 64 integers per ring element gives a 64× smaller witness — the biggest single prover speedup — but ring multiplication convolves packed data instead of multiplying it slot-wise, which fights the relations.
  • Two tricks rescue it: reading a dot product from the constant term of a · σ(b), and random scalar aggregation (2 rounds for 2⁻¹²⁸ soundness) to collapse thousands of constraints into a constant number of checks — the "dot-product-over-ℤ" prover.
  • The real speedup is several-fold, not 64×, because aggregation still has an O(M) floor (the proof must read the whole M-coefficient ciphertext); the rest of the gains were ordinary profiling (compact Fiat–Shamir digest, debug-gated sanity checks).
  • Packing is the throughput lever and composes with folding (the size lever) to reach sub-second, small proofs.

References

  • W. Beullens, G. Seiler, "LaBRADOR: Compact Proofs for R1CS from Module-SIS," CRYPTO 2023 — the constant-term / dot-product-over-ℤ aggregation this packing is built on.
  • J. Schwartz, "Fast Probabilistic Algorithms for Verification of Polynomial Identities," JACM 1980; R. Zippel, 1979 — the random-linear-combination soundness principle.
  • The "packed / batched" encoding line in lattice and MPC proofs generally (SIMD-style plaintext packing, as in BGV/BFV ciphertext packing) — the same "use all the slots" idea.
  • Wikipedia: Convolution, Schwartz–Zippel lemma, Dot product.

Next: Algorithm: Succinct Proofs by Folding.