Comments (7)
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.
from gnark-crypto.
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.
from gnark-crypto.
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
from gnark-crypto.
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
from gnark-crypto.
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.
from gnark-crypto.
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
IsOnCurve
inside IsInSubGroup
gnark-crypto/ecc/bls12-381/g1.go
Line 432 in 2e4aaaa
from gnark-crypto.
can we close this? :)
from gnark-crypto.
Related Issues (20)
- bug: invalid marshalling found by fuzzer HOT 2
- iop.Polynomial.Evaluate should work in Lagrange/Lagrange shifted form
- refactor: make applying domain separation optional in Fiat-Shamir Transcript HOT 1
- bug: When dynamic linking, R15 may be clobbered by a global variable access HOT 7
- bug: possibly incorrect `DST_prime` in `ExpandMsgXmd` HOT 6
- Parametrizable mimc endianness HOT 4
- Docu: Merkle tree documentation outdated or hashing of nodes in is incorrect
- Add SetElement to fptower.E2 HOT 2
- feat: MIMC security considerations HOT 2
- Optimize Legendre symbol
- Generator of Fr*
- feat: Implement Poseidon hash
- 📦 `github.com/consensys/gnark-crypto/ecc` HOT 1
- bug: MiMC Write() violates hash.Hash expectations. HOT 5
- feat: add MustSetRandom methods
- Question: is it possible to generate secp256k1 ecdsa Private Key from a secret string? HOT 3
- Question: compatibility between crypto/sha256 and gnark/sha2 HOT 1
- bug: Incorrect ScalarMultiplication in bandersnatch HOT 2
- bug: fft
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from gnark-crypto.