BLS12-381 G1 Subgroup checks are slow

[MariusVanDerWijden]

BLS12-381 G1 Subgroup checks are slow

[yelhousni]

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.

[yelhousni]

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.

[MariusVanDerWijden]

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

[MariusVanDerWijden]

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

[yelhousni]

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.

[yelhousni]

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()

[gbotrel]

can we close this? :)