Perf: KZG with fixed-argument pairing in affine coordinates #466

yelhousni · 2023-11-03T16:19:56Z

Description

This PR refactors KZG to use fixed-argument pairings. This requires to change the SRS verifying key to store the precomputed lines instead of the points G2 and [a]G2.

TODO:

~~I need to implement an ate variant Miller loop for BW6-633 to implement this feature.~~ Done in 07b87ae.

Type of change

Please delete options that are not relevant.

New feature (non-breaking change which adds functionality)
Breaking change (fix or feature that would cause existing functionality to not work as expected)

How has this been tested?

Same tests for KZG work here as well + testing that Pair results with fixed and variable arguments match.

How has this been benchmarked?

Some benchmarks on a AWS z1d.large machine:

goos: linux
goarch: amd64
pkg: github.com/consensys/gnark-crypto/ecc/*/kzg
cpu: Intel(R) Xeon(R) Platinum 8151 CPU @ 3.40GHz

BN254

benchmark                          old ns/op      new ns/op      delta
BenchmarkSRSGen/real_SRS-2         3101757295     3085342398     -0.53%
BenchmarkSRSGen/quick_SRS-2        952900         1523358        +59.87%
BenchmarkKZGCommit/real_SRS-2      122914358      121965943      -0.77%
BenchmarkKZGCommit/quick_SRS-2     114308031      113640429      -0.58%
BenchmarkDivideByXMinusA-2         103447328      102627372      -0.79%
BenchmarkKZGOpen-2                 124670902      124335198      -0.27%
BenchmarkKZGVerify-2               658898         537151         -18.48%
BenchmarkKZGBatchOpen10-2          136281734      136385577      +0.08%
BenchmarkKZGBatchVerify10-2        1043165        922205         -11.60%
BenchmarkToLagrangeG1-2            5548069025     4977902867     -10.28%

BW6-761

benchmark                          old ns/op       new ns/op       delta
BenchmarkSRSGen/real_SRS-2         26341215560     26358001933     +0.06%
BenchmarkSRSGen/quick_SRS-2        3537481         10778989        +204.71%
BenchmarkKZGCommit/real_SRS-2      1186236493      1189108978      +0.24%
BenchmarkKZGCommit/quick_SRS-2     1099211577      1102560337      +0.30%
BenchmarkDivideByXMinusA-2         167096682       167218972       +0.07%
BenchmarkKZGOpen-2                 1186146836      1195299942      +0.77%
BenchmarkKZGVerify-2               3779093         3044281         -19.44%
BenchmarkKZGBatchOpen10-2          1200625617      1202907566      +0.19%
BenchmarkKZGBatchVerify10-2        6456328         5730700         -11.24%
BenchmarkToLagrangeG1-2            44017779311     44044702422     +0.06%

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

github-actions · 2023-11-03T16:20:44Z

📦 github.com/consensys/gnark-crypto/ecc/bls24-315/fr/fri
❌ TestFRI 0s

+ verifying wrong opening should fail: OK, passed 10 tests.
+ verifying correct opening should succeed: OK, passed 10 tests.
+ The claimed value of a polynomial should match P(x): OK, passed 10 tests.
+ Derive queries position: points should belong the correct fiber: OK,
   passed 10 tests.

📦 github.com/consensys/gnark-crypto/ecc/bls24-315/internal/fptower
❌ TestE12Ops 0s

❌ TestE24Ops 0s

+ [BLS24-315] sub & add should leave an element invariant: OK, passed 100
   tests.
+ [BLS24-315] mul & inverse should leave an element invariant: OK, passed
   100 tests.
+ [BLS24-315] inverse twice should leave an element invariant: OK, passed
   100 tests.
+ [BLS24-315] square and mul should output the same result: OK, passed 100
   tests.
+ [BLS24-315] a + pi(a), a-pi(a) should be real: OK, passed 100 tests.
+ [BLS24-315] Torus-based Compress/decompress E24 elements in the
   cyclotomic subgroup: OK, passed 100 tests.
+ [BLS24-315] Torus-based batch Compress/decompress E24 elements in the
   cyclotomic subgroup: OK, passed 100 tests.
+ [BLS24-315] pi**24=id: OK, passed 100 tests.
+ [BLS24-315] (pi**2)**12=id: OK, passed 100 tests.
+ [BLS24-315] (pi**4)**6=id: OK, passed 100 tests.
+ [BLS24-315] cyclotomic square (Granger-Scott) and square should be the
   same in the cyclotomic subgroup: OK, passed 100 tests.
+ [BLS24-315] compressed cyclotomic square (Karabina) and square should be
   the same in the cyclotomic subgroup: OK, passed 100 tests.
+ [BLS24-315] batch decompress and individual decompress (Karabina) should
   be the same: OK, passed 100 tests.
+ [BLS24-315] Exp and CyclotomicExp results must be the same in the
   cyclotomic subgroup: OK, passed 100 tests.
+ [BLS24-315] Frobenius of x in E24 should be equal to x^q: OK, passed 100
   tests.
+ [BLS24-315] FrobeniusSquare of x in E24 should be equal to x^(q^2): OK,
   passed 100 tests.

📦 github.com/consensys/gnark-crypto/ecc/bls24-317
❌ TestCrossMultiExpG2 0s

❌ TestEncodeToG1 0s

❌ TestEncoder 0s

❌ TestG1AffineCofactorCleaning 0s

❌ TestG1AffineConversions 0s

❌ TestG1AffineEndomorphism 0s

❌ TestG1AffineInvalidBitMask 0s

❌ TestG1AffineIsOnCurve 0s

❌ TestG1AffineOps 0s

❌ TestG1AffineSerialization 0s

❌ TestG1SqrtRatio 0s

❌ TestG2AffineCofactorCleaning 0s

❌ TestG2AffineConversions 0s

❌ TestG2AffineEndomorphism 0s

❌ TestG2AffineInvalidBitMask 0s

❌ TestG2AffineIsOnCurve 0s

❌ TestG2AffineOps 0s

❌ TestG2AffineSerialization 0s

❌ TestHashToG1 0s

❌ TestIsCompressed 0s

❌ TestMapToCurve1 0s

❌ TestMapToG1 0s

📦 github.com/consensys/gnark-crypto/ecc/bls24-317/fr/fft
❌ TestBitReverse 0s

📦 github.com/consensys/gnark-crypto/ecc/bls24-317/fr/fri
❌ TestFRI 0s

📦 github.com/consensys/gnark-crypto/ecc/bls24-317/internal/fptower
❌ TestE24Ops 0s

+ [BLS24-317] sub & add should leave an element invariant: OK, passed 100
   tests.
+ [BLS24-317] mul & inverse should leave an element invariant: OK, passed
   100 tests.
+ [BLS24-317] inverse twice should leave an element invariant: OK, passed
   100 tests.
+ [BLS24-317] square and mul should output the same result: OK, passed 100
   tests.
+ [BLS24-317] a + pi(a), a-pi(a) should be real: OK, passed 100 tests.
+ [BLS24-315] Torus-based Compress/decompress E24 elements in the
   cyclotomic subgroup: OK, passed 100 tests.
+ [BLS24-315] Torus-based batch Compress/decompress E24 elements in the
   cyclotomic subgroup: OK, passed 100 tests.

github-actions · 2023-11-03T21:23:32Z

📦 github.com/consensys/gnark-crypto/ecc/bls24-317/fr/fri
❌ TestFRI 0s

+ verifying wrong opening should fail: OK, passed 10 tests.
+ verifying correct opening should succeed: OK, passed 10 tests.
+ The claimed value of a polynomial should match P(x): OK, passed 10 tests.
+ Derive queries position: points should belong the correct fiber: OK,
   passed 10 tests.

📦 github.com/consensys/gnark-crypto/ecc/bls24-317/internal/fptower
❌ TestE24Ops 0s

+ [BLS24-317] sub & add should leave an element invariant: OK, passed 100
   tests.
+ [BLS24-317] mul & inverse should leave an element invariant: OK, passed
   100 tests.
+ [BLS24-317] inverse twice should leave an element invariant: OK, passed
   100 tests.
+ [BLS24-317] square and mul should output the same result: OK, passed 100
   tests.
+ [BLS24-317] a + pi(a), a-pi(a) should be real: OK, passed 100 tests.
+ [BLS24-315] Torus-based Compress/decompress E24 elements in the
   cyclotomic subgroup: OK, passed 100 tests.
+ [BLS24-315] Torus-based batch Compress/decompress E24 elements in the
   cyclotomic subgroup: OK, passed 100 tests.
+ [BLS24-317] pi**24=id: OK, passed 100 tests.
+ [BLS24-317] (pi**2)**12=id: OK, passed 100 tests.
+ [BLS24-317] (pi**4)**6=id: OK, passed 100 tests.
+ [BLS24-317] cyclotomic square (Granger-Scott) and square should be the
   same in the cyclotomic subgroup: OK, passed 100 tests.
+ [BLS24-317] compressed cyclotomic square (Karabina) and square should be
   the same in the cyclotomic subgroup: OK, passed 100 tests.
+ [BLS24-315] Exp and CyclotomicExp results must be the same in the
   cyclotomic subgroup: OK, passed 100 tests.
+ [BLS24-317] Frobenius of x in E24 should be equal to x^q: OK, passed 100
   tests.
+ [BLS24-317] FrobeniusSquare of x in E24 should be equal to x^(q^2): OK,
   passed 100 tests.

📦 github.com/consensys/gnark-crypto/ecc/bn254/fr/fft
❌ TestBitReverse 0s

📦 github.com/consensys/gnark-crypto/ecc/bn254/fr/fri
❌ TestFRI 0s

+ verifying wrong opening should fail: OK, passed 10 tests.

📦 github.com/consensys/gnark-crypto/ecc/bw6-633 [github.com/consensys/gnark-crypto/ecc/bw6-633.test]

ecc/bw6-633/pairing_test.go:185:14: undefined: MillerLoopFixedQ
ecc/bw6-633/pairing_test.go:187:15: undefined: LoopCounter
ecc/bw6-633/pairing_test.go:187:32: undefined: LineEvaluationAff
ecc/bw6-633/pairing_test.go:188:6: undefined: PrecomputeLines
ecc/bw6-633/pairing_test.go:189:6: undefined: PrecomputeLines

📦 github.com/consensys/gnark-crypto/ecc/bw6-633/ecdsa
❌ TestECDSA 0s

📦 github.com/consensys/gnark-crypto/ecc/bw6-633/fp
❌ TestElementAdd 0s

❌ TestElementBatchInvert 0s

❌ TestElementBitLen 0s

❌ TestElementButterflies 0s

❌ TestElementBytes 0s

❌ TestElementDiv 0s

❌ TestElementDouble 0s

❌ TestElementEqual 0s

❌ TestElementExp 0s

❌ TestElementFixedExp 0s

❌ TestElementFromMont 0s

❌ TestElementHalve 0s

❌ TestElementInverse 0s

❌ TestElementInverseExp 0s

❌ TestElementIsUint64 0s

❌ TestElementLegendre 0s

❌ TestElementLexicographicallyLargest 0s

❌ TestElementMul 0s

❌ TestElementMulByConstants 0s

❌ TestElementNeg 0s

❌ TestElementNegativeExp 0s

❌ TestElementReduce 0s

❌ TestElementSelect 0s

❌ TestElementSetInt64 0s

+ reduce should output a result smaller than modulus: OK, passed 20 tests.
+ Select: must select correctly: OK, passed 20 tests.
+ butterfly0 == a -b; a +b: OK, passed 20 tests.
+ Assembly implementation must be consistent with generic one: OK, passed
   20 tests.
+ x.fromMont().toMont() == x: OK, passed 20 tests.
+ Select: having the receiver as operand should output the same result:
   OK, passed 20 tests.

❌ TestElementSetInterface 0s

❌ TestElementSqrt 0s

❌ TestElementSquare 0s

❌ TestElementSub 0s

github-actions · 2023-11-06T19:09:04Z

📦 github.com/consensys/gnark-crypto/ecc/bw6-633
🛑 build failed

📦 github.com/consensys/gnark-crypto/ecc/bw6-633 [github.com/consensys/gnark-crypto/ecc/bw6-633.test]

ecc/bw6-633/pairing_test.go:185:14: undefined: MillerLoopFixedQ
ecc/bw6-633/pairing_test.go:187:15: undefined: LoopCounter
ecc/bw6-633/pairing_test.go:187:32: undefined: LineEvaluationAff
ecc/bw6-633/pairing_test.go:188:6: undefined: PrecomputeLines
ecc/bw6-633/pairing_test.go:189:6: undefined: PrecomputeLines

📦 github.com/consensys/gnark-crypto/ecc/bw6-633/fr/permutation
🛑 build failed

📦 github.com/consensys/gnark-crypto/ecc/bw6-633/fr/plookup
🛑 build failed

📦 github.com/consensys/gnark-crypto/ecc/bw6-633/kzg
🛑 build failed

ecc/bw6-633/kzg/kzg.go:52:26: undefined: bw6633.LoopCounter
ecc/bw6-633/kzg/kzg.go:52:50: undefined: bw6633.LineEvaluationAff
ecc/bw6-633/kzg/kzg.go:121:28: undefined: bw6633.PrecomputeLines
ecc/bw6-633/kzg/kzg.go:122:28: undefined: bw6633.PrecomputeLines
ecc/bw6-633/kzg/kzg.go:128:27: undefined: bw6633.PrecomputeLines
ecc/bw6-633/kzg/kzg.go:129:27: undefined: bw6633.PrecomputeLines
ecc/bw6-633/kzg/kzg.go:241:23: undefined: bw6633.PairingCheckFixedQ
ecc/bw6-633/kzg/kzg.go:243:20: undefined: bw6633.LoopCounter
ecc/bw6-633/kzg/kzg.go:243:44: undefined: bw6633.LineEvaluationAff
ecc/bw6-633/kzg/kzg.go:500:23: undefined: bw6633.PairingCheckFixedQ
ecc/bw6-633/kzg/kzg.go:500:23: too many errors

ecc/bls12-377/pairing.go

ivokub

Looks good. Maybe can simplify a few methods in comments?

ecc/bls12-377/internal/fptower/e12_pairing.go

ecc/bls12-377/kzg/kzg.go

yelhousni added 19 commits October 25, 2023 19:18

refactor: remove G1 from KZG verifiying key

a620985

perf(bw6): precomuting lines in pairing

132e06b

refactor(bw6): simplify PrecomputeLines

809ca82

perf(bw6): precomuting lines in pairing in affine

9c64699

perf(bw6): use precomputed affine lines in kzg

ecccc50

perf(bw6-756): precomuting lines in pairing in affine + kzg

065b135

perf(bn254): precomuting lines in pairing in affine

8c017da

perf(bn254): use precomputed affine lines in kzg

9259e02

perf(bls12-377): precomuting lines in pairing in affine

e8d9e09

perf(bls12-377): use precomputed affine lines in kzg

b596dbe

perf(bls24-315): precomuting lines in pairing in affine

a22be87

perf(bls24-315): use precomputed affine lines in kzg

749cbdf

perf(bls12-381): precomuting lines in pairing in affine

f883b34

perf(bls12-378): precomuting lines in pairing in affine

7e180a6

perf(bls24-317): precomuting lines in pairing in affine

39726b0

perf(bls12-381): use precomputed affine lines in kzg

46ba6a5

perf(bls12-378): use precomputed affine lines in kzg

66f0ffc

perf(bls24-317): use precomputed affine lines in kzg

73755d8

refactor: generify and consolidate new kzg and fixed-arg pairing

4a2b903

yelhousni added new feature perf labels Nov 3, 2023

yelhousni added this to the v0.10.0 milestone Nov 3, 2023

yelhousni self-assigned this Nov 3, 2023

yelhousni marked this pull request as draft November 3, 2023 21:10

fix: kzg template for bn254

ced3c7b

refactor(bw6-633): use revisited Ate pairing instead of Tate

a646db6

perf(bw6-633): precomuting lines in pairing in affine

07b87ae

fix(kzg): bw6-633 vk marshal

689cd26

yelhousni marked this pull request as ready for review November 6, 2023 21:44

yelhousni requested review from ThomasPiellard and ivokub November 6, 2023 21:44

refactor: consolidate fixed-argument pairing across curves

5e633e8

yelhousni mentioned this pull request Nov 7, 2023

Refactor(BW6): use revisited Ate pairing instead of Tate #465

Merged

13 tasks

yelhousni added 3 commits November 7, 2023 13:13

docs: skipping inf points in PairFixedQ is implicit

bf5af37

docs: fix misspelled comment

47d3c08

perf: specialize mul by affine lines

ea69954

yelhousni changed the title ~~Perf: KZG with fixed-argument pairing~~ Perf: KZG with fixed-argument pairing in affine coordinates Nov 9, 2023

yelhousni mentioned this pull request Nov 11, 2023

Perf: KZG verify gadget Consensys/gnark#874

Merged

20 tasks

ThomasPiellard approved these changes Nov 15, 2023

View reviewed changes

ecc/bls12-377/pairing.go Outdated Show resolved Hide resolved

ecc/bls12-377/pairing.go Show resolved Hide resolved

ivokub approved these changes Nov 15, 2023

View reviewed changes

ecc/bls12-377/internal/fptower/e12_pairing.go Show resolved Hide resolved

ecc/bls12-377/internal/fptower/e12_pairing.go Show resolved Hide resolved

ecc/bls12-377/kzg/kzg.go Show resolved Hide resolved

ecc/bls12-377/kzg/kzg.go Outdated Show resolved Hide resolved

yelhousni added 2 commits November 15, 2023 16:25

perf: batchInvert 1/P.Y in fixed-arg pairing

683b7b0

refactor: apply code review suggestions

3abc810

yelhousni merged commit 0d49504 into master Nov 15, 2023
7 checks passed

yelhousni deleted the kzg/srs branch November 15, 2023 22:13

yelhousni mentioned this pull request Nov 16, 2023

Refactor: re-introduce points in KZG verification key #469

Merged

9 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Perf: KZG with fixed-argument pairing in affine coordinates #466

Perf: KZG with fixed-argument pairing in affine coordinates #466

yelhousni commented Nov 3, 2023 •

edited

Loading

github-actions bot commented Nov 3, 2023

github-actions bot commented Nov 3, 2023

github-actions bot commented Nov 6, 2023

ivokub left a comment

Perf: KZG with fixed-argument pairing in affine coordinates #466

Perf: KZG with fixed-argument pairing in affine coordinates #466

Conversation

yelhousni commented Nov 3, 2023 • edited Loading

Description

Type of change

How has this been tested?

How has this been benchmarked?

Checklist:

github-actions bot commented Nov 3, 2023

github-actions bot commented Nov 3, 2023

github-actions bot commented Nov 6, 2023

ivokub left a comment

Choose a reason for hiding this comment

yelhousni commented Nov 3, 2023 •

edited

Loading