BLS curve

Hi all!

Together with my colleagues, we are implementing a pallet for distributed key generation (DKG) and a randomness beacon pallet using keys generated by the DKG. We are supported by a Web3 grant.

For that, we need to use some prime order elliptic curve group. In the grant proposal, we mentioned that a BLS group will be used, however, only later we realized that substrate does not yet support BLS signatures (or any other pairing-friendly crypto). In fact, we also learned that BLS was used in substrate before but was discarded due to performance issues (mostly with respect to the runtime). We also saw some comments in the code and in the docs stating that BLS support is planned for the future. For this reason, we would like to bring to your attention that a new, fast BLS library was developed: blst. It has rust bindings and may be compiled to wasm.

The question would be then: whether it is time for BLS to come back to substrate?

Regarding our project, the DKG pallet can be still implemented and makes sense also for non-pairing curves, like ed25519. However, using such an instantiation of DKG as a base for the randomness beacon, the performance of the beacon is much worse when pairing friendly curves are used, more specifically:

• pairing curves: O(1) group elements per block, O(1) verification time
• non-pairing curves: O(t) group elements per block, O(t^2) verification time (in the runtime). Here t is the “threshold” parameter, should be of the order of the number of participants in the randomness beacon protocol, so of the order of ~100.

This comparison hopefully gives a clear argument, for why we think BLS is useful :)