Comments (1)
The cost of bucket-list MSM is roughly: b/c*(n+2^c)
additions where n
is the number of points, b
the bitsize of scalars and c
the chosen window bitsize. For large instances, this is dominated by the n
additions that correspond to summing the buckets contents. In gnark-crypto
, this is a mixed addition of affine points and Jacobian extended points (XYZZ), which costs 10 field multiplications per addition (10 M
), assuming a square costs the same as a multiplication (1S=1M
).
Note: The only shapes-coordinates with faster mixed addition are Jacobi quartics XXYZZ/XXYZZR (9M
), Edwards projective/inverted (9M
), twisted Edwards extended (8M
) and twisted Edwards extended with a=-1
(7M
). To convert a short Weierstrass to a twisted Edwards or a Jacobi quartic, we need a point of order 2 to map to a Montgomery curve which has then a bijection with these shapes. However, only BLS12-377, BLS24-315 and BW6-761 satisfy this condition (on G1). Moreover, we need to implement the new arithmetic on these shapes.
The idea behind this issue is to compare mixed addition in Jacobian extended to a batched affine addition. Assuming 1S=1M
, the cost of an affine addition is 3M+1I
(I
is a field inverse). For a single addition, this is not worth it as usually 1I > 7M = 10M-3M
but this might be different for a batch addition that leverages Montgomery's batch inversion trick. One can accumulate L
points in affine and batch add them which costs 3L*M+L*I= 6L*M + 1I
(with Montgomery's trick costing L*I = 3L*M + 1I
). Assuming I = C*M
, this is worth it if we accumulate a number of points L > C/4
.
e.g. for BLS12-381, currently in gnark-crypto
, C=143
over Fp
and C=43
over Fp2
. This means that one can expect MSM speedups on G1 when L > 36
and on G2 when L > 11
. Note that, the inverse cost can be reduced with Pornin's algorithm for example.
from gnark-crypto.
Related Issues (20)
- How to call mimc to input a string and output the mimc hashed result? HOT 1
- feat: define and implement field hasher implement for snark-friendly hash functions HOT 1
- Optimize BW6 final exponentiation
- What's the rationale for methods returning pointers in the ecc packages? HOT 3
- 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
- BLS12-381 G1 Subgroup checks are slow HOT 7
- 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
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.