Faster Post-Quantum zkSNARK Provers Using the LCH Polynomial Basis
:12
Abstract
An important class of plausibly post-quantum zkSNARKs uses univariate-polynomial interactive oracle proofs (IOPs) over binary extension fields $\mathbb{F}_{2^k}$, relying on the Fast Reed--Solomon (RS) Interactive Oracle Proof of Proximity (FRI) for low-degree testing. Their provers fold RS codewords in FRI and perform polynomial arithmetic, notably division and multiplication by subspace vanishing polynomials. Constraint polynomials and RS codewords are in evaluation form, but existing implementations perform this arithmetic in the monomial basis, requiring inverse additive fast Fourier transforms (FFTs) for coefficient recovery and forward FFTs for evaluation. On a general basis, Gao--Mateer and Lin--Chung--Han (LCH) additive FFTs incur $O(n(\log n)^2)$ field additions and $O(n\log n)$ field multiplications for basis conversion per $n$-point transform, and Lagrange-based FRI folding performs a field inversion per coset. We carry out this arithmetic directly in the LCH polynomial basis for arbitrary $\mathbb{F}_2$-bases. We introduce a divide-and-conquer algorithm for division by subspace vanishing polynomials directly in the LCH basis. For $n$ input coefficients, it requires $O(n)$ field operations, and on a Cantor basis it requires no field multiplications. We also show that the multiples of vanishing polynomials used for zero-knowledge blinding can be sampled directly through their LCH coefficients. Together, these remove the basis-conversion stage of the LCH additive FFT, leaving only its butterfly. We further express the FRI fold in the LCH basis: on each coset, it is an LCH inverse butterfly followed by an evaluation at the verifier challenge, and for higher-arity folds, the challenge of each stage is the value of a normalized subspace vanishing polynomial at the verifier challenge. Given constants that depend only on the domain, this yields a fold without field inversions whose folding loop performs $n(1-1/\kappa)$ field multiplications for a length-$n$ codeword and arity $\kappa$; for every input word, it outputs the same next codeword as the classical fold. We integrate these algorithms into the Aurora prover without changing the proof or the verifier. At $2^{19}$ constraints over $\mathbb{F}_{2^{256}}$, when all configurations use our FRI fold, the LCH-basis arithmetic speeds up the prover by $2.80\times$ over \texttt{libiop} on a general basis and by $1.24\times$ over a Cantor-basis prover that uses the LCH additive FFT. Against these baselines with their Lagrange-based FRI fold, the speedups are $3.63\times$ and $2.05\times$.