Faster pairings

[mratsim]

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

Impl: https://github.com/mratsim/constantine/blob/47b4f48/constantine/math/pairings/pairings_bn.nim#L112-L162

---

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):

• ECC Circuit: EcAdd, EcMul, EcPairing scroll-tech/zkevm-circuits#559

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

https://github.com/mratsim/constantine/blob/47b4f48dfb08c9ab9188c5308d4185156b8cb0bd/constantine/math/pairings/multi_pairings.md

Savings

In this PR, gas cost has been reduced from 1.4M gas to 872k gas

metacraft-labs/DendrETH@6b3c652#diff-f9d3c1274a560fb7a19b949feb0601823fa0d96eb8fb7d7f8603ad00b97230d7

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

• Perf: emulated BN254 pairing Consensys/gnark#566

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

[jonathanpwang]

Thanks for this!

Just a comment: for the hard part of final exponentiation we do use Karabina's cyclotomic squaring: https://github.com/axiom-crypto/halo2-lib/blob/a74c5944a0d495d899b51971491e8600bca604bb/halo2-ecc/src/bn254/final_exp.rs#L104C103-L104C139
It's been a while but when I last looked from his paper it seemed like that was the best compression optimization on the hard part.

But I haven't looked at the other new developments you referenced, so I'm sure there's more cool optimizations to be added.

[mratsim]

Just a comment: for the hard part of final exponentiation we do use Karabina's cyclotomic squaring

Ah interesting, I missed this.

The torus-based compression can do both squaring and multiplication while Karabina can only do squaring so the acceleration depends on the ration of squaring vs multiplication and BN254 is meh regarding hamming weight as the ATE parameter is:

# u = 0x44e992b44a6909f1
# Ate BN |6u+2|
# hex: 0x19d797039be763ba8
# bin: 0x11001110101111001011100000011100110111110011101100011101110101000

For further improvement on Karabina, it's also possible to augment Karabina with batch cyclotomic decompression, see:

• declaration https://github.com/mratsim/constantine/blob/47b4f48/constantine/math/pairings/cyclotomic_subgroups.nim#L744C6-L788
• usage for BLS12-381 https://github.com/mratsim/constantine/blob/47b4f48/constantine/math/constants/bls12_381_pairings.nim#L84-L93

but even with batch decompression, the decompression still scales per fp12 multiplication.

[unbalancedparentheses]

This is amazing. We will use many ideas from here in lambdaworks. Thanks for creating it