Skip to content
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

Misc optimizations for group gadgets #125

Open
DanieleDiBenedetto opened this issue Sep 15, 2021 · 0 comments
Open

Misc optimizations for group gadgets #125

DanieleDiBenedetto opened this issue Sep 15, 2021 · 0 comments
Labels
documentation Improvements or additions to documentation enhancement New feature or request nice to have Possible new feature to introduce optimization Performance improvement for the current codebase

Comments

@DanieleDiBenedetto
Copy link
Collaborator

DanieleDiBenedetto commented Sep 15, 2021

  • In mul_bits_fixed_base we can optimize performances by applying the batch inversion to the whole table and not only to the table obtained by packing 2 bits at a time;
  • Modify mul_bits and mul_bits_fixed_base functions to transparently handle exceptional cases if arithmetic is incomplete (shift + conditional selection of the result);
  • Optimize AllocGadget:
    1. For curves with Weierstrass A=0 and small B since most of our curves are of this form;
    2. Remove on curve checks for alloc_input, there is no real need for it;
    3. Regarding alloc checked, many curves have a cofactor which is either or large small compared to the prime order r. Let's take a more accurate measure instead of the Hamming weight to pick out the most efficient test.
  • Add better documentation related to handling of exceptional cases for curves with incomplete arithmetic
  • Replace incomplete arithmetic where it's not safe to use (roughly, replace calls to add_incomplete_safe() with calls to add_complete() (partially addressed in Complete add for AffineGagdet + fix serialization to field elements #172 )
  • As stated in Refactor Ginger-Lib #144 (comment), we should drop the distinction between exponentiation functions (.*fixed_base.*) that computes the power of the bases(s) inside or accepting already the precomputed powers of the base(s) as input parameter. I would suggest to keep the latters, as we can always precompute the powers of the base(s), save them somewhere, and pass references to them to the circuit whenever needed. We should address also the functions left todo!() in the implementers of GroupGadget trait.
  • Change interfaces (where not done already) to accept Iterator<bool> instead of Vec<bool>
@DanieleDiBenedetto DanieleDiBenedetto added documentation Improvements or additions to documentation optimization Performance improvement for the current codebase labels Sep 15, 2021
@DanieleDiBenedetto DanieleDiBenedetto added enhancement New feature or request nice to have Possible new feature to introduce labels Mar 21, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
documentation Improvements or additions to documentation enhancement New feature or request nice to have Possible new feature to introduce optimization Performance improvement for the current codebase
Projects
None yet
Development

No branches or pull requests

1 participant