search

arkworks-rs / algebra

Libraries for finite field, elliptic curve, and polynomial arithmetic
https://arkworks.rs
Apache License 2.0
648 stars 253 forks source link

Implement GLV for the Bandersnatch curve #718

Open mmagician opened 1 year ago

mmagician commented 1 year ago

Summary

We removed the parameters for Bandersnatch from https://github.com/arkworks-rs/curves/pull/158 due to subsequent changes in the Bandersnatch parameters (although producing isomorphic curves). First, let's implement the new curve parameters and then see about enabling GLV for it.

For Admin Use

CPerezz commented 11 months ago

Happy to take this! Wanted to add the Banderwagon construction too used for Ethereum Verkle trees.

Edit: Nevermind. https://github.com/arkworks-rs/curves/pull/102 Already resolves this.

mmagician commented 10 months ago

@CPerezz Actually this is still open - the PR you mention was using the old GLV interface which has since changed.

I believe this should be a simple change, given that the code was already in an older PR to curves, but I temporarily removed it as it wasn't clear why the curve parameters were different. As pointed out in this comment, the new parameters produce an isomorphic curve yet they yield optimized computation. This issue amounts to confirming the isomorphism, changing the curve parameters to the new ones, and finally implementing GLVConfig as per the linked commit above.

weikengchen commented 9 months ago

I am in the process of adding GLV for secp256k1 and would take this one, and ideally streamline the process, with addition script that helps people in the future to generate the parameters.

weikengchen commented 9 months ago

^ I will do the GLV for the simple curves (a=0) today. For those with more than one parameters, anyone with a good reference? For Ed curve, do we just implement the one for the ed config, or more?

CPerezz commented 9 months ago

Hey @weikengchen this script from Gnark might help.

We used it to generate all the endo params in halo2curves. See: https://github.com/privacy-scaling-explorations/halo2curves/blob/9fff22c5f72cc54fac1ef3a844e1072b08cfecdf/src/grumpkin/curve.rs#L59

weikengchen commented 9 months ago

^ do you happen to have one for more complicated cases like Bandersnatch? I.e., twisted edwards curves. They have endo, but very different.

CPerezz commented 9 months ago

^ do you happen to have one for more complicated cases like Bandersnatch? I.e., twisted edwards curves. They have endo, but very different.

Sadly no.. At least I',m not aware of it. We don't have any TwEd curves in halo2curves hence we've never looked at it. It would complicate quite a lot the crate TBH :sweat_smile:

cc: @yelhousni maybe you've derived the script and I missed it?