bls12-381 extern on Substrate

[sorpaas]

One of the issues faced by Shasper is that bls12-381 verification can be slow. While on Shasper this can also be fixed by using native execution strategy, if the algorithm is commonly used, we may want to make that as an extern.

An issue is that different places have different definitions of what is the "signature" and what is the "public key". I've seen places which use G1 as "signature", while in other places G2 is used as "signature". So we may want to expose the raw extern directly operate on G1 and G2.

[burdges]

I'd envision some substrate-zexe-algebra crate that re-impls the traits from zexe's algebra-core on the types from zexe's algebra.

Anything fast enough should receive a direct impl, but some slow operations require host calls:

• scalar multiplication,
• multi-scalar multiplication,
• batch inversion,
• point preparation on G2,
• multi-milter loop, and
• final exponentiation.

There are never single miller loops because you almost never want just one pairing.

We'd then invoke pairing based crypto inside the runtime using zexe's higher level libraries directly, but with types from substrate-zexe-algebra, not zexe's algebra.

We'll eventually want some fancy pairing aggregation tooling using TIPP that starts the pairing computations in another thread when the block starts running.

We've a lot to do here..

[burdges]

As for the original Shasper issue, we should switch grandpa to BLS eventually, but yeah it's pretty slow, so maybe a Ed25519 signature outside and a BLS signature inside, and we slash anyone who signs an invalid BLS signature.

I've a partial BLS library that does bitfields and some optimized verifiers at https://github.com/w3f/bls but we'll eventually want some fancier TIPP based verifiers, but no idea how long that'll take so..