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

Auto-generate hard-coded non-residue constants for the field tower #8

Closed
ggutoski opened this issue Jun 19, 2020 · 0 comments
Closed
Assignees
Labels
cleanup Suggestion to clean up the code

Comments

@ggutoski
Copy link
Contributor

In all curves, the 2- and 6-degree field extensions have methods MulByNonResidue, MulByNonResidueInv. Sometimes the most efficient way to implement these methods is to call Mul with a hard-coded constant. Example: the inverse of 2: https://github.com/ConsenSys/gurvy/blob/5cb7d9881b3e10bc77e7a9836189e2c9d14874e4/bls381/e6.go#L530
These constants should be computed automatically by the template generator. Right now we only compute the inverse of 2, as in here: https://github.com/ConsenSys/gurvy/blob/5cb7d9881b3e10bc77e7a9836189e2c9d14874e4/internal/generators/tower/generator.go#L96
Similar constants are not automatically computed. Instead they are simply hard-coded in the template generator. Example: this constant for BLS377: https://github.com/ConsenSys/gurvy/blob/5cb7d9881b3e10bc77e7a9836189e2c9d14874e4/bls377/e6.go#L509
is simply hard-coded in the template here: https://github.com/ConsenSys/gurvy/blob/5cb7d9881b3e10bc77e7a9836189e2c9d14874e4/internal/generators/tower/templates/fp2/inline.go#L37
That's bad, of course. All these constants should be computed automatically.

An egregious example

Our current "hello world" implementation of the BW6-761 pairing initializes the inverse of 4 via string conversion inside the Miller loop! https://github.com/ConsenSys/gurvy/blob/5cb7d9881b3e10bc77e7a9836189e2c9d14874e4/bw761/pairing.go#L418
That must be slowing down the Miller loop. Thus, a proper solution for this issue should yield a noticeable performance improvement for the BW6-761 Miller loop.

What to do

As mentioned above, our only auto-generated constant in this family is the inverse of 2. But that template code is a PoC and does not immediately generalize. A more intelligent design is needed in the template generator.

Most (all?) of these hard-coded constants appear only in the MulByV, etc methods in #7 . Presumably, design work for this issue will directly affect #7, too.

@ggutoski ggutoski added the cleanup Suggestion to clean up the code label Jun 19, 2020
@ggutoski ggutoski self-assigned this Jun 19, 2020
harveyyue pushed a commit to harveyyue/gnark-crypto that referenced this issue May 14, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
cleanup Suggestion to clean up the code
Projects
None yet
Development

No branches or pull requests

1 participant