ginger-lib icon indicating copy to clipboard operation
ginger-lib copied to clipboard

Misc optimizations for group gadgets

Open 95DDB opened this issue 4 years ago • 0 comments

  • 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 #172 )
  • As stated in https://github.com/HorizenOfficial/ginger-lib/pull/144#discussion_r826247385, 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>

95DDB avatar Sep 15 '21 14:09 95DDB