gnark-crypto icon indicating copy to clipboard operation
gnark-crypto copied to clipboard

perf(bn254): optimize affine pairing with doubleAndAdd

Open yelhousni opened this issue 8 months ago • 0 comments

Description

In affine pairing (MillerLoopFixedQ), use doubleAndAdd to compute 2P+Q as of P+Q+P. This optimizes the one-time line precomputation for KZG in gnark-crypto, but most importantly matches gnark in-circuit implementation. This is now important since after https://github.com/Consensys/gnark/pull/1143 we need to have the exact same lines so that the witness residue is the same.

Type of change

Please delete options that are not relevant.

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

How has this been tested?

pairing tests pass.

How has this been benchmarked?

In gnark-crypto, only the lines precompuation should be affected (faster) but it's just a one-time computation.

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 Jun 05 '24 00:06 yelhousni