To appear · IACR TCHES 2027

Pairing Proofs and Polynomial Ring Toolkit

Abstract

Elliptic curve pairings are fundamental to modern zero-knowledge proof systems, including Groth16, PLONK, and KZG polynomial commitments. In resource-constrained execution environments (Ethereum VM, BitVM, blockchain smart contracts), where computation is metered by gas fees, and in arithmetized computation systems (R1CS, Plonkish, Cairo AIR), where each computational step imposes significant prover overhead, the cost of pairing computation remains a practical bottleneck. We present a public-coin interactive proof system that consolidates the Miller loop iterations and final exponentiation into a single polynomial relation. The relation can then be verified as polynomial identities, greatly reducing the pairing costs. We present a full implementation in gnark (the industry-standard framework for arithmetized circuit development) as a reusable polynomial ring toolkit in the emulated package. Benchmarked on a 3-pairing product check (the pairing workload of a Groth16 verification), our gnark implementation achieves over 32% reduction in constraints, over 50% reduction in committed elements, and reductions in both compile-time and solver memory for both BN254 and BLS12-381 curves. This enables practical pairing verification in recursive proof systems and resource-constrained environments.

Method

One polynomial identity per Miller loop step

F(x)² · L₁(x) L₂(x) L₃(x) = Q(x) · P₁₂(x) + R(x)

Earlier work checks every 𝔽_p¹² multiplication as its own identity and commits each remainder. This work checks a whole loop step at once, then batches every step and the final exponentiation into one check at a random point. Soundness error stays below 2⁻²⁴⁴ for BN254.

F is the loop accumulator, L₁ to L₃ the line functions of three pairs, and P₁₂ = x¹² − 18x⁶ + 82 the BN254 extension modulus. Builds on El Housni, Feltroidprime, and Novakovic and Eagen's On Proving Pairings.

Constraints per loop step, three pairs

𝔽_p¹² arithmetic (El Housni)

132

One identity per multiplication, 48 commitments

One identity per step, 12 commitments

Paper, Table 1, zero bit.

Results

A third off the pairing, in gnark and on Starknet

Table 7: 3-pairing product check in gnark, baseline against this work. Apple M3 Pro.
Metric	BN254	BLS12-381
R1CS
Constraints	−35.7%	−32.5%
Committed 𝔽_q elements	−52.8%	−54.5%
Compile time	−40.5%	−38.3%
Solve time	−39.4%	−33.7%
PLONK (SCS)
Constraints	−35.0%	−33.2%
Compile time	−43.6%	−36.9%
Solve time	−41.9%	−38.0%

Table 6: Garaga on Starknet, 3-pairing check with final exponentiation, in production.
Metric	BN254	BLS12-381
CairoVM steps	−37.1%	−32.7%
Committed elements	−50.7%	−41.6%
MULMOD	−33.9%	−31.5%
ADDMOD	−30.2%	−25.4%

Fewer committed elements means less to hash and less hint calldata per verification.

Table 7 in full

Metric	BN254 gnark	BN254 this work	BLS12-381 gnark	BLS12-381 this work
SCS (PLONK)
Constraints	1,592,440	1,035,550	1,784,247	1,191,105
Committed 𝔽_q elements	571,125	269,616	660,160	300,104
Compile time	615.04 ms	347.13 ms	650.02 ms	410.48 ms
Compile memory	1.33 GB	0.82 GB	1.48 GB	0.97 GB
Solve time	167.57 ms	97.30 ms	180.05 ms	111.60 ms
Solve memory	348.73 MB	181.24 MB	362.14 MB	284.30 MB
R1CS
Constraints	491,447	316,167	545,510	368,434
Committed 𝔽_q elements	571,125	269,616	660,160	300,104
Compile time	617.63 ms	367.25 ms	686.95 ms	424.01 ms
Compile memory	1.60 GB	0.98 GB	1.74 GB	1.13 GB
Solve time	175.42 ms	106.36 ms	182.72 ms	121.15 ms
Solve memory	173.26 MB	112.72 MB	231.77 MB	118.61 MB

Paper to library

Bigger numbers, same ratio

The paper measured a bare 3-pairing check on a gnark fork. Two gnark advisories published since then, GHSA-3mvx-pp85-pm65 and GHSA-fwf3-jmp7-gmrj, added range checks to every emulated multiplication. Both columns grew, and the saving held.

The paper's fork stays frozen to reproduce its tables. polyring builds on the fixed gnark.

R1CS constraints, BN254

Paper, 3-pairing check

−35.7%

Same circuit, patched gnark*

−38.6%

Full Groth16 verifier

−38.0%

gnarkpolyring

* Preliminary: measured, benchmark not yet in the tree.

The toolkit

Not just pairings

The protocol ships as a toolkit for any emulated field and any monic modulus. Register a ring, submit products, and the checker proves them all with two commitments when Define returns. The paper names lattice schemes such as ML-KEM and ML-DSA as a next application.

std/polyring

prc := polyring.NewPolyRingChecker[emulated.BN254Fp](api) // before any other emulated field
modPoly := prc.MakePoly(82, 0, 0, 0, 0, 0, -18, 0, 0, 0, 0, 0, 1)
ring := prc.NewPolyRingCheck(modPoly, nil)
res, _ := prc.MulPolyRings(ring, A, B, C) // (A·B·C) mod modPoly, checked when Define returns
acc := prc.NewPolyRingAccumulator(ring, targetDeg)
acc.Mul(A).Mul(B).Sqr() // enqueue (A·B)², nothing multiplied yet
rem := acc.Eval()        // one deferred check for the whole chain

Acknowledgements

Youssef El Housni and Ivo Kubjas (Linea, Consensys) for discussions and encouragement, Feltroidprime for discussions on his technique, and StarkWare and the Starknet Foundation for supporting an earlier version of the technique.