Paper 2024/640

On Proving Pairings

Andrija Novakovic, Geometry Research
Liam Eagen, Alpen Labs, Zeta Function Technologies

In this paper we explore efficient ways to prove correctness of elliptic curve pairing relations. Pairing-based cryptographic protocols such as the Groth16 and Plonk SNARKs and the BLS signature scheme are used extensively in public blockchains such as Ethereum due in large part to their small size. However the relatively high cost of pairing computation remains a practical problem for many use cases such as verification ``in circuit" inside a SNARK. This naturally arises in recursive SNARK composition and SNARKs of BLS based consensus protocols. To improve pairing verification, we first show that the final exponentiation step of pairing verification can be replaced with a more efficient ``residue check," which can be incorporated into the Miller loop. Then, we show how to reduce the cost of the Miller loop by pre-computing all the necessary lines, and how this is especially efficient when the second pairing argument is fixed in advance. This is the case for BLS signatures with a fixed public key, as well as for KZG based SNARKs like Plonk and two of the three Groth16 pairings. Finally, we show how to improve of the protocol of [gar] by combining quotients, which allows us to more efficiently prove higher degree relations. These techniques also carry over naturally to pairing verification, for example on-chain verification or as part of the BitVM(2) protocol for Bitcoin smart contracts. We instantiate algorithms and show results for the BN254 curve.

Available format(s)
Cryptographic protocols
Publication info
elliptic curvespairingszero knowledge proofsSNARKs
Contact author(s)
andrija @ geometry dev
liameagen @ protonmail com
2024-04-29: approved
2024-04-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andrija Novakovic and Liam Eagen},
      title = {On Proving Pairings},
      howpublished = {Cryptology ePrint Archive, Paper 2024/640},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.