BLS signatures and aggregation

[ghost]

Hopefully we can identify a suitable existing implementation, otherwise implement independently.

Any implementation should take into account the issues described here

https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407

NuBLS is a pure rust implementation, but of course the dependencies are an issue. blstrs - another option, dependency issues and also depends on unsafe code/C library

https://www.cc.gatech.edu/~aboldyre/papers/bold.pdf

[ghost]

It is worth noting that BLS signatures are needed for distributed key signing, but potentially not for DKG participant signatures (another signature scheme could be used).

[simonmasson]

About the multi-verification

There is now a "multi" version of the verification of aggregated BLS signatures. Namely, for n signatures, it computes n+1 pairings insteaf of 2*n. In [eprint 2018.483], there is two constructions that we consider for the moment:

• An aggregated signature (section 3)
• A threshold signature (section 4) that computes more hashes into G2. I don't know which one is our use-case (the threshold concerns only the DKG?).

The improvement of the "multi-verification" is not significant in the threshold case, due to the lot (n²) of hashes to G2 needed in the frag_keys. Using the aggregated signatures, the multi verification leads to a significant gain: n+1 miller loop instead of 2*n). See benches/bls.rs for details, together with the README.md file, of the branch simonmasson/bls-pairing-equation, commit 04ebd120e6ff98624f7a643be819fe6ce41e94db.

[ghost]

Unfortunately BLS signatures are not directly compatible with the PVSS/PVDKG, so we'll have to put this on ice until we have a need for it.