New architecture for template generator

[ggutoski]

Why?

It is now much easier to automatically compute constants required for code generation from within gurvy instead of manually copy-pasting from sage. (Also, I did some house cleaning. There's still lots more cleaning needed though.)

The flagship example is the methods MulByNonResiduexPowery found in frobenius.go for each curve. Another example is the inverse of 2 modulo p used in curves with a field tower of the form used by BLS12-381, BW6-761. There are several other constants whose computation could also be automated in this way.

In the future, it will be easier to add new constants or new curves to gurvy. Perhaps one could even use this new architecture to reduce reliance on sage to make tests, though I suspect the complete elimination of sage from the process is not yet worth the effort.

Overview

Prior to this PR, all code (goff, tower, curve groups, pairing) for each curve was generated from a single executable invoked from the root directory via go generate ./internal/.... This single executable prevented the use of code generated earlier in the process to generate subsequent code. For example, it was not possible to use code from goff or the field tower to generate code for the pairing. Thus, it was impossible, for example, to automate the computation of constants used in Frobenius computations. Instead, these constants must be computed manually in sage and copy-pasted into gurvy's Go codebase.

By contrast, the new architecture splits code generation into four worker executables: one for each of goff, tower, curve groups, pairing. These four workers are managed by another master executable, so the original user-facing terminal command is the same: all code is generated with a single command:

go generate ./internal/...

Each worker is invoked under-the-hood via go run, which automatically compiles the executable from source before executing. Some of that source is generated by previous workers, so newly generated code is instantly compiled into the next worker's executable.

The new architecture

• The master executable is located at /internal/generators/main.go. It contains all the info required to generate all the curves.
• Instead of passing all this info to the four worker executables via terminal arguments, the master executable generates code in the curve package.
• The four worker packages are primefields, tower, gpoint, and pairing. Each imports from curve---that's how they get their arguments.
• A minimalist package has at least two files:

   ├── generator.go
   └── main
       └── main.go
  

  Template execution occurs in generator.go. The master executable invokes main/main.go via go run. main.go is typically just a wrapper that imports curve (as a way to get curve info) and invokes generator.go.
  • The primefields worker has this simple structure. All the work is done by goff, so no more code is needed here.
• All workers other than primefields provide their own templates instead of invoking goff. For these workers, template code appears in a templates/ directory.
• Some workers have code generated for them by other workers. Such code, if present, appears at the worker's root directory in generated-code.go.
  • These workers provide a template for themselves. This template is usually nothing more than an import statement, so it is included in generator.go. See for example: https://github.com/ConsenSys/gurvy/blob/17fb8608bf278e67ad264849ef11ed3a3d260f0b/internal/generators/tower/generator.go#L103
  • Worker code generation is invoked from the master executable in main.go. Example: https://github.com/ConsenSys/gurvy/blob/17fb8608bf278e67ad264849ef11ed3a3d260f0b/internal/generators/main.go#L130
• Some workers might have complicated generation code. In order to keep generate.go simple, this extra generation code is typically split into other source files at the worker's root. (Example: computation of Frobenius constants in pairing/constants.go.)

[ggutoski]

By the way, this PR also contains some new code for BW6-761 pairing: Frobenius and final exponentiation.

TODO for BW6-761

• mulAssign for lineEval to finish off the pairing
• tests

[ggutoski]

We now have a working pairing for BW6-761. Ready to merge.

Several optimizations remain TODO. For example:

• Miller loop is currently the "naive" method with 190-bit loop length instead of 127. Reference sage code for the "naive" Miller loop. Need to get fully optimized Miller loop with 127-bit loop length. Reference sage code for optimized Miller loop.
• Need to hard-code the non-residue constants like we do for other curves. Currently we do an expensive conversion from string inside the Miller loop. See for example: https://github.com/ConsenSys/gurvy/blob/c023044951d4589aef9a877b9d60af447314b090/bw6_761/pairing.go#L414

Clean-up TODO:

• Work for clean up: MulByV, etc #7 has begun with BW6-761. The methods MulByVMinusThree, MulByVminusTwo, MulByVminusFive introduced for BW6-761 appear in pairing.go. Need to do the same for other curves and modify the template generator accordingly.
• The template for pairing.go is a mess. Most of the code here is curve-specific. Most or all of this code should be removed from the template generator.