paritytech
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). Heretis 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 :)
We're asking pairing based stuff to run in pure wasm right now. In fact, pairings could run native on a substrate fork, which works fine for polkadot collators, but polkadot validators shall only support wasm based pairings when parachains launch.
We think https://github.com/arkworks-rs/algebra/issues/730 represents the first step towards pairings on substrate, which sounds easy enough. Yet, there are several linked issues, like stability and validation function run times, so..
Ideally, we might force most cryptography, if not all computationally intensive tasks, into using semi-audited wasm modules, which themselves then performed the required native arkworks calls. We'd expect non-threshold BLS signatures over large signer sets might be validated using what amounts to a SNARK, but threshold BLS gets considerable simpler of course. We'd provide SNARK verifiers for things like groth16 and some plonks too. All this requires extensive work however, so maybe we'd simply expose arkworks over the near term and/or make parachains that access it slashable for bad block runtimes.
Anyways, arkworks built to wasm remains the current advice. :)
p.s. As I understand it, C code would not be considered for merge into substrate, but again forks can do what they like, and collators can run on forks.
