gnark icon indicating copy to clipboard operation
gnark copied to clipboard

perf: optimize `DoublePairingCheck` i.e. e(a,b)e(c,d) == 1

Open yelhousni opened this issue 6 months ago • 1 comments

Description

This PR needs https://github.com/Consensys/gnark-crypto/pull/524 to be merged first.

We define the DoublePairingCheck method which asserts that e(a,b)e(c,d) == 1. We merge the squares in final exp equivalence check for witnessResidue^λ with the Miller loop computation. This PR optimizes KZG and Pedersen commitments.

Type of change

  • [x] New feature (non-breaking change which adds functionality)

How has this been tested?

Added tests for the new method in addition to existing tests for PairingCheck.

How has this been benchmarked?

The PR saves for a double-pairing check:

  • 316,593 scs for BN254
  • 714,146 scs for BLS12-381
  • 3,877 scs for BLS12-377

Checklist:

  • [x] I have performed a self-review of my code
  • [x] I have commented my code, particularly in hard-to-understand areas
  • [x] I have made corresponding changes to the documentation
  • [x] I have added tests that prove my fix is effective or that my feature works
  • [x] I did not modify files generated from templates
  • [x] golangci-lint does not output errors locally
  • [x] New and existing unit tests pass locally with my changes
  • [x] Any dependent changes have been merged and published in downstream modules

yelhousni avatar Jul 30 '24 01:07 yelhousni