Implement GLV for the Bandersnatch curve

[mmagician]

Summary

We removed the parameters for Bandersnatch from arkworks-rs/curves#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

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[CPerezz]

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

Edit: Nevermind. arkworks-rs/curves#102 Already resolves this.

[mmagician]

@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]

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]

^ 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]

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]

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

[CPerezz]

^ 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 😅

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