perf: optimize precomputation in fixed-argument pairings

[yelhousni]

Description

This PR pptimizes doubleAndAddStep in fixed-argument pairing by computing 2P+Q with a single field inversion instead of two. Based on https://eprint.iacr.org/2003/257, this uses Montgomery's batch inversion to compute both slopes λ1 and λ2 together: 1/A = U/(A·U) and 1/U = A/(A·U) with a single inversion of A·U where A = x1 - x2 and U = B² - (2x1 + x2)·A².

This speeds up the hints computation in gnark.

Changes:

• Updated doubleAndAddStep in bn254, bls12-381, bls12-377, bw6-761
• Added BenchmarkPrecomputeLines to pairing test template

Type of change

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

How has this been tested?

MillerLoop and MillerLoopFixedQ output the same result.

How has this been benchmarked?

Benchmarking PrecomputeLines on a AWS c7a.8xlarge:

BN254:      BenchmarkPrecomputeLines-32     149943        118355        -21.07%
BLS12-377:  BenchmarkPrecomputeLines-32     226428        216831        -4.24%
BLS12-381:  BenchmarkPrecomputeLines-32     218752        210380        -3.83%
BW6-761:    BenchmarkPrecomputeLines-32     3304770       3287600       -0.52%

Checklist:

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

---

Note

Optimizes fixed-argument pairing precomputation by computing 2P+Q with a single inversion via the Eisenträger–Lauter–Montgomery formula and Montgomery batch inversion.

• Rewrites doubleAndAddStep in bn254, bls12-381, bls12-377, bw6-761 to use batch-inversion for λ1/λ2 (one field inversion instead of two)
• Adds reference doubleAndAddStepRef and property-based equivalence tests to verify optimized vs. reference outputs
• Introduces BenchmarkPrecomputeLines across pairing tests and updates the test template to generate the new test/benchmark

No API changes; behavior is validated to match previous outputs while improving precompute performance.

^{Written by Cursor Bugbot for commit b7ee69d. This will update automatically on new commits. Configure here.}

[Copilot]

Pull request overview

This PR optimizes the doubleAndAddStep function in fixed-argument pairing by using Montgomery's batch inversion technique to compute two slopes with a single field inversion instead of two. The optimization is based on the Eisenträger-Lauter-Montgomery formula from https://eprint.iacr.org/2003/257 and achieves performance improvements ranging from 0.52% to 21.07% depending on the curve.

Changes:

• Optimized doubleAndAddStep in four curves (bn254, bls12-381, bls12-377, bw6-761) to use batch inversion
• Added BenchmarkPrecomputeLines to the pairing test template and all curve implementations

Reviewed changes

Copilot reviewed 12 out of 12 changed files in this pull request and generated no comments.

Show a summary per file

File	Description
internal/generator/pairing/template/tests/pairing.go.tmpl	Added benchmark template for PrecomputeLines function
ecc/bn254/pairing.go	Optimized doubleAndAddStep using Montgomery batch inversion (21.07% improvement)
ecc/bn254/pairing_test.go	Added PrecomputeLines benchmark (generated from template)
ecc/bls12-381/pairing.go	Optimized doubleAndAddStep using Montgomery batch inversion (3.83% improvement)
ecc/bls12-381/pairing_test.go	Added PrecomputeLines benchmark (generated from template)
ecc/bls12-377/pairing.go	Optimized doubleAndAddStep using Montgomery batch inversion (4.24% improvement)
ecc/bls12-377/pairing_test.go	Added PrecomputeLines benchmark (generated from template)
ecc/bw6-761/pairing.go	Optimized doubleAndAddStep using Montgomery batch inversion (0.52% improvement)
ecc/bw6-761/pairing_test.go	Added PrecomputeLines benchmark (generated from template)
ecc/bw6-633/pairing_test.go	Added PrecomputeLines benchmark for consistency (no optimization - uses separate double/add steps)
ecc/bls24-317/pairing_test.go	Added PrecomputeLines benchmark for consistency (no optimization - uses separate double/add steps)
ecc/bls24-315/pairing_test.go	Added PrecomputeLines benchmark for consistency (no optimization - uses separate double/add steps)

[ivokub]

Looks good to me! I also added compatibility test to ensure the new implementation is equivalent to the old one. See if it makes sense to you. Good to merge!

[yelhousni]

Looks good to me! I also added compatibility test to ensure the new implementation is equivalent to the old one. See if it makes sense to you. Good to merge!

Yeah that makes sense. Good to merge.