-
Notifications
You must be signed in to change notification settings - Fork 138
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Optimization: implement RCB15 group addition for BN curves #15
Comments
@davidnevadoc (and possibly others) will do some checks to the paper and discuss whether to go for an implementation as this requires to change the macros that implement everything for the curves. |
Sounds good. My demo has shows that both the group law can be integrated to both arkworks and halo2. I see two way to move forward
Option 1 could serve as a temp patch until 2 is ready |
no arkworks also used 16 mul version |
I think @kilic has already started to implement the Field encoding required for this. So we should be able to adopt it soon. |
very nice! |
I went for approach number 2 and switched to homogeneous coordinates. Are you aware of any downsides of using these instead of jacobian coordinates? @zhenfeizhang |
I am not aware of any downside other than that the doubling is slightly more costly IIRC |
The current group law uses 16 field multiplications.
https://github.com/privacy-scaling-explorations/halo2curves/blob/main/src/derive/curve.rs#L810
We may use the method from https://eprint.iacr.org/2015/1060 which requires only 12 field multiplications.
I have a demo implementation of this algorithm here:
https://github.com/zhenfeizhang/rcb15-group-law
This should improve the proving speed by 25% or so.
(I noticed that both Halo2 and Arkworks didn't use this 8 years old method. Did I missed anything here?)
The text was updated successfully, but these errors were encountered: