bellpepper-bls12381 implementation

[wwared]

This PR adds a bellpepper-bls12381 crate that includes gadgets for a circuit performing pairings and other basic BLS12-381 operations. The implementation is heavily inspired (i.e. copied) from gnark's std/algebra/emulated/ package. This makes use of torus transformations for more efficient exponentiation in $E_{12}$.

Currently, there are still (non-trivial) low-hanging optimizations in the base operations used by the pairing (implemented by bellpepper-emulated). Currently, one pairing takes roughly 28M constraints, but the majority of the constraints are for bit reductions and right shifts, so it should (hopefully) be possible to bring this number down to <10M constraints (or lower) if we improve the reduction strategy used by bellpepper-emulated.[^1]

This crate uses a minimal fork of bls12_381 that exposes some private elements of the crate. CI is rejecting the PR because of the git dependency to a non-lurk-lab repository, so the fork could be transferred to the lurk-lab org.

Because of the high constraint count, I've commented out two tests that take a long time to run.

Future improvements that would come in future PRs:

• Performance improvements to the reduce flow on bellpepper-emulated operations.
• Support for "hash to curve" operations for full end-to-end signature verification.
• Miscellaneous curve operations that could be useful (like is_on_curve for G1/G2).
• Reducing code duplication (e.g. the g1.rs and g2.rs files are very similar) and enabling the gadget to be more generic (e.g. use differently-sized limbs depending on the specific underlying native field size).
• Reduce the exported pub elements (right now basically everything is pub for convenience).

[^1]: Currently, bellpepper-emulated's implementation of reduce ends up calling assert_is_equal which does a bit decomposition of the values in the assert_limb_equality_slow path, and it ends up exploding the number of constraints. gnark instead commits to some polynomials and does a more optimized multiplication hint (which is not feasible in pure R1CS). circom-pairing has some different strategies for performing multiplications and prime reductions, which may be better than the assert_is_equal slow path as well (here and here). The strategy used by bp-ed25519 should be similar to circom-pairing's and is also a possible inspiration to draw from.

[wwared]

1. to override the cargo-deny checks, you can edit the last few lines of the deny.toml, (I'll approve when this is done)

Done in a03fdc74cf3749ea7c5c0c3cec37c67cb5e1f6f3

2. we should open an issue to fix this unsightly git dependency (irrespective of how)

Opened #21

3. instead of forking the repo, have you looked at whether the sought-after types are accessible in https://github.com/filecoin-project/blstrs ?

I looked at it briefly before but not too deeply, IIRC it doesn't export things like Fp2, Fp6 or Fp12 types. The blst crate exports more things and it might be a suitable replacement (if we ignore needing to write a rust unsafe wrapper around things), but it has a few omissions like no add/sub for Fp6/Fp12 types (I'm not sure what the best way to work around those would be).

EDIT: To be clear, blstrs seems to have all the same types and operations we use from bls12_381 implemented in nice rust wrapper types, but the FpX types are private to the crate so the issue ends up being the same as the one I had with bls12_381