search

arkworks-rs / curves

Implementations of popular elliptic curves
https://www.arkworks.rs
Apache License 2.0
303 stars 103 forks source link

GLV implementation for BLS12_377, BLS12_381 and BN254 #158

Closed mmagician closed 1 year ago

mmagician commented 1 year ago

Description

Updates #147 by @simonmasson to use the slightly improved trait interface from https://github.com/arkworks-rs/algebra/pull/644.

Update: Benchmarks show that there is a significant improvement for BLS12-377, BLS12-381 (40%, 37% respectively), moderate improvement for BN254 (10%) and a small improvement for Bandersnatch at 2%. The rest perform worse with GLV enabled by default. For the last group I've left the implementation of the GLV trait in, but haven't enabled it by default. PR title reflects the defaults only.

closes: #147

Before we can merge this PR, please make sure that all the following items have been checked off. If any of the checklist items are not applicable, please leave them but write a little note why.

mmagician commented 1 year ago

@Pratyush I'm thinking to just pull out the Bandersnatch changes into a separate PR, as I don't know why a new parameter set is used. Maybe later @simonmasson can add more details on this change, but I think we should move forward with the rest for now, WDYT?

mmagician commented 1 year ago

@asanso maybe you can shed some light on the new parameters as we discussed today?

Pratyush commented 1 year ago

@mmagician Handling Bandersnatch in a different PR seems reasonable!

mmagician commented 1 year ago

The failing tests for curves with GLV enabled should be fixed when https://github.com/arkworks-rs/curves/pull/171 is merged. As explained there, overriding mul_projective with the new GLV implementation forces the scalars passed to be at most MODULUS (in particular, at most N limbs), and otherwise panics upon conversion from more than N limbs. This is a breaking change, and maybe we should think about a way to either 1) impose the same behaviour for non-GLV implementations 2) change the trait signature to directly receive a Scalar 3) distinguish the two cases here and handle appropriately.