Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Faster pairings #101

Open
mratsim opened this issue Aug 2, 2023 · 3 comments
Open

Faster pairings #101

mratsim opened this issue Aug 2, 2023 · 3 comments
Labels
enhancement New feature or request

Comments

@mratsim
Copy link

mratsim commented Aug 2, 2023

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

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:

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

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.

image

Presentations:

Implementation

See also all “emulated pairing” PRs like:

Other impl in regular arithmetic (not a constraint system)

Research papers:

Gnark implements “T2” arithmetic (Torus with 1/2 compression) according to

A paper with a nice high-level overview of compression techniques is Karabina’s:

image

TODOs (research)

Evaluate

@jonathanpwang
Copy link
Contributor

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
Copy link
Author

mratsim commented Aug 3, 2023

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:

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

@unbalancedparentheses
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

4 participants
@unbalancedparentheses @mratsim @jonathanpwang and others