BLS12-381 G1 Subgroup checks are slow

Running the G1 subgroup checks is very slow for the BLS12-381 curve. The G1 subgroup checks are only slightly slower. Between G1 and G2 subgroup checks should be a large difference imo

Expected Behavior

G1 subgroup checks should be significantly faster than g2 subgroup checks

Actual Behavior

BenchmarkG1-24 31113 37117 ns/op 368 B/op 6 allocs/op
BenchmarkG2-24 30657 39935 ns/op 184 B/op 3 allocs/op

Possible Fix

Implement a different algo for the g1 subgroup checks

Steps to Reproduce

func BenchmarkG1(b *testing.B) {
 g1 := new(bls12381.G1Affine)
 for i := 0; i < b.N; i++ {
  g1.IsInSubGroup()
 }
}

func BenchmarkG2(b *testing.B) {
 g2 := new(bls12381.G2Affine)
 for i := 0; i < b.N; i++ {
  g2.IsInSubGroup()
 }
}

Context

This issue makes it kinda impossible for us to use gnark in go-ethereum

Your Environment

v0.12.1

Hi @MariusVanDerWijden, g1.IsInSubGroup() cost is dominated by 2 scalar multiplications with a 64-bit scalar while g2.IsInSubGroup() cost is dominated by a single scalar multiplication with the same 64-bit scalar. Both tests have an endomorphism evaluation (G2 endomorphism is slightly costlier as it has 5 more field multiplications). So all in all maybe it's not surprising that G1 and G2 tests costs are almost the same but I will run a profiler to confirm. In terms of the algorithms we implement https://eprint.iacr.org/2022/352.pdf.

Note that we can optimize a bit more the tests by "specializing" the scalar multiplication by the (fixed) 64-bit scalar using an addition chain.

I also ran the same benchmark for kilic's library which implements https://eprint.iacr.org/2019/814.pdf
and is about 4 times faster BenchmarkKilic-24 337947 5299 ns/op 8056 B/op 49 allocs/op
I saw that you are referencing this algo in your paper as well, so probably not a big improvement here?

edit: Ah I saw that this paper seems to use some unproven point to speed up the subgroup check

Maybe it would also be possible to implement the algorithm used by blst: https://github.com/supranational/blst/blob/0d46eefa45fc1e57aceb42bba0e84eab3a7a9725/src/e1.c#L101
which seems to implement x^3+b == y^2

I also ran the same benchmark for kilic's library which implements https://eprint.iacr.org/2019/814.pdf and is about 4 times faster BenchmarkKilic-24 337947 5299 ns/op 8056 B/op 49 allocs/op I saw that you are referencing this algo in your paper as well, so probably not a big improvement here?

edit: Ah I saw that this paper seems to use some unproven point to speed up the subgroup check

This paper has some unproven results and is anyway sub-optimal compared to https://eprint.iacr.org/2021/1130.pdf, https://eprint.iacr.org/2022/348.pdf and https://eprint.iacr.org/2022/352.pdf.

Maybe it would also be possible to implement the algorithm used by blst: https://github.com/supranational/blst/blob/0d46eefa45fc1e57aceb42bba0e84eab3a7a9725/src/e1.c#L101 which seems to implement x^3+b == y^2

This test is to check that the point is on the curve but not necessarily on the sub-group. It is also implemented in gnark-crypto

gnark-crypto/ecc/bls12-381/g1.go

Line 404 in 2e4aaaa

func (p *G1Jac) IsOnCurve() bool {

and in Kilic's https://github.com/kilic/bls12-381/blob/ca162e8a70f456f4cf733097edfd60d0e9deca2c/g2.go#L292. Note that gnark-crypto calls IsOnCurve inside IsInSubGroup

gnark-crypto/ecc/bls12-381/g1.go

Line 432 in 2e4aaaa

return res.IsOnCurve() && res.Z.IsZero()

can we close this? :)