Faster pairings #101
Description
Introduction
As discussed with @yi-sun during EthCC, here is my internal Taiko note on pairing acceleration.
cc @ggkitsas who has been looking into this, @Brechtpd.
cc @yelhousni who had the original idea of using RS03 for circuits (in Gnark) and @nikkolasg who was looking into this very recently.
Extra review note, the current final exponentiation in Axiom is using
- On the final exponentiation for calculating pairings on ordinary elliptic curves
Scott, Benger, Charlemagne, Perez, Kachisa, 2008
https://eprint.iacr.org/2008/490.pdf
in https://github.com/axiom-crypto/halo2-lib/blob/a74c594/halo2-ecc/src/bn254/final_exp.rs#L303-L370
But there are 2 faster developments:
- Memory-saving computation of the pairing final exponentiation on BN curves
Sylvain Duquesne and Loubna Ghammam, 2015
https://eprint.iacr.org/2015/192 - Faster hashing to G2
Laura Fuentes-Castañeda, Edward Knapp,
Francisco Jose Rodríguez-Henríquez, 2011
https://link.springer.com/content/pdf/10.1007%2F978-3-642-28496-0_25.pdf
Circuit - Fast Pairings
Pairing (ECPAIRING - EIP197) is likely the slowest operation in the EVM.
However if we want to allow L3s to work on Taiko, it needs to be fast enough.
This document gives an overview of the state-of-the-art to significantly reduce pairings constraint requirement.
2 optimizations are available to significantly reduce pairings cost.
Current EIP197 PR from Scroll (pending merge as of july 2023):
Scroll forks Halo2-ecc from Axiom for the “PairingChip”
https://github.com/axiom-crypto/halo2-lib/tree/community-edition/halo2-ecc
I. Multi-pairings
note: a version of multi-pairings has been implemented in Axiom’s codebase #65
Overview
Pairings are computed in 2 expensive main steps:
- Miller Loop
- Final exponentiation
Their cost is similar, if pairings cost is 100, each costs 50.
However, for n pairings, we can accumulate n Miller Loop and do a single final exponentiation, reducing the asymptotic cost by 2x. It is worth it even with only 2 pairings, as needed for BLS signatures or KZG commitments or 3 pairings as needed for Groth16.
Implementation
There are 2 ways to implement multi-pairings, they are detailed in
Savings
In this PR, gas cost has been reduced from 1.4M gas to 872k gas
II. Compressed pairings
Overview
Pairings are done on a subgroup of the Fp12 extension field (k=12 is the embedding degree of BN and BLS12 curves) of order r that is cyclotomic.
In particular they respect the cyclotomic polynomial equation ϕ₁₂(x) = x⁴-x²+1
This allows compressed representations for cheaper arithmetic, in particular squaring.
Some representations do not allow multiplication (only squaring) and some representations do not allow decompression.
Implementation
Pairings in circuit can be accelerated using number theoretic properties of cyclotomic fields (https://en.wikipedia.org/wiki/Cyclotomic_field)
In particular the final exponentiation can be done in a compressed representation using either:
- Torus-based compression (1/2 in Gnark, 1/3 as a research direction proposed by Karabina)
- Trace-of-Frobenius compression (XTR) (1/3 in Miracl)
- Lucas compression (1/2 in Miracl)
Operations
Operations using a compressed representation can save 1/3, 1/2 or 2/3 of space and also a significant amount field operations, hence constraints.
For regular computation on a CPU, compression is problematic due to either the absence of decompression or decompression requiring a field inversion, a very expensive operations (80x to 120x more expensive than field multiplication).
In constraint system however, it’s free as we can provide the inverse as a witness and the cost becomes the same as proving a multiplication.
Presentations:
- Pairings in R1CS: https://yelhousni.github.io/zksummit7.pdf
- https://www.youtube.com/watch?v=F351X6EDn9g
- https://hackmd.io/@yelhousni/emulated-pairing
Implementation
See also all “emulated pairing” PRs like:
- Perf: emulated pairing BN254 Consensys/gnark#714
- Perf: optimise BN254 emulated final exponentiation Consensys/gnark#594
- Perf: emulated BN254 pairing Consensys/gnark#566
- feat: BN254 pairing Consensys/gnark#411
- std/pairing: hinted division in extension fields Consensys/gnark#299
Other impl in regular arithmetic (not a constraint system)
- XTR:
https://github.com/miracl/core/blob/45f58f8/c/fp12.c#L683-L728
https://github.com/miracl/core/blob/45f58f8/c/fp4.c#L389-L612 - Karabina’s compressed squarings (cannot be used for mul though, BN254 might not have enough consecutive squarings to make this useful):
https://github.com/mratsim/constantine/blob/d69c7bf/constantine/math/pairings/cyclotomic_subgroups.nim#L436-L788
Research papers:
Gnark implements “T2” arithmetic (Torus with 1/2 compression) according to
- Torus-based Cryptography
Rubin and Silverberg, 2003
https://link.springer.com/content/pdf/10.1007/978-3-540-45146-4_21.pdf
https://www.iacr.org/archive/crypto2003/27290348/27290348.pdf
https://eprint.iacr.org/2003/039
A paper with a nice high-level overview of compression techniques is Karabina’s:
- Squaring in cyclotomic subgroups
Koray Karabina, 2010
https://eprint.iacr.org/2010/542.pdf
TODOs (research)
Evaluate
- Compression in Finite Fields and Torus-Based Cryptography
Rubin & Silverberg, 2008
https://dl.acm.org/doi/abs/10.1137/060676155 - A Comparison of CEILIDH and XTR
R. Granger, D. Page, and M. Sta, 2004
https://sci-hub.se/10.1007/978-3-540-24847-7_17 - Effective compression maps for torus-based cryptography
Montanari, 2016
https://dl.acm.org/doi/10.1007/s10623-014-0031-9