MSM Optimizations - Githubissues

lambdaclass / lambdaworks

lambdaworks offers implementations for both SNARKs and STARKs provers, along with the flexibility to leverage their individual components for constructing customized SNARKs.

https://lambdaclass.github.io/lambdaworks/

Apache License 2.0

617 stars 136 forks source link

MSM Optimizations #730

Open MauroToscano opened 10 months ago

MauroToscano commented 10 months ago

There are a series of optimizations that can be applied to MSM that are not leveraged right now. The following can be implemented and benched, with the fastest setted to be used as the default one:

[ ] Constantine tricks for high core machines, see their #277, code, and docs. Also the following gist. This related halo2 issue can also be helpful
[ ] Faster Batch forgery Identification algorithm. Implementation of Gnark

rahulghangas commented 8 months ago

@MauroToscano we would like to contribute some optimization to MSM implementation based on SOA (@Strohy will be working on this). Is it okay we open up a couple of PRs?