BLS Signatures

BLS(Boneh-Lynn-Shacham) signatures was invented by Dan Boneh, Ben Lynn, and _Hovav Shacham), and their paper was published in 2001.

Note: we can’t use any elliptic curve for BLS (in particular, standard Bitcoin curve secp256k1 doesn’t work for BLS). In BLS, we have to use very special curves from “pairing-friendly” family.

BLS also has all those nice features which Schnorr Signatures brings: Signature Aggregation, Key Aggregation, etc. But unfortunately, BLS has an obvious drawback which prevent it from widely adopted: computation efficiency! BLS signature verification is order of magnitude harder than ECDSA.

Unlike BLS, Schnorr signatures are very efficient — they can be validated all together and this process is factor of 3 more efficient than ECDSA, this is a big win factor for Schnorr signatures, at least for now.

[update at 4th Aug. 2018]:

An interesting BLS Signature Lib in C++, has just been started for a few days!

Here I paste some bench test result of this BLS signature lib:

$ make bench
./blsbench -d yes

Sigining
Total: 1000 runs in 2237 ms
Avg: 2.237 ms

Verification
Total: 1000 runs in 7820 ms
Avg: 7.82 ms

Batch verification
Total: 1000 runs in 2026 ms
Avg: 2.026 ms

Batch verification with cached verifications
Total: 1000 runs in 386 ms
Avg: 0.386 ms

Generate aggregate signature, same message
Total: 1000 runs in 2415 ms
Avg: 2.415 ms

Generate aggregate pk, same message
Total: 1000 runs in 428 ms
Avg: 0.428 ms

Verify agg signature, same message
Total: 1000 runs in 8 ms
Avg: 0.008 ms

Generate aggregate signature, distinct messages
Total: 1000 runs in 245 ms
Avg: 0.245 ms

Verify aggregate signature, distinct messages
Total: 1000 runs in 2070 ms
Avg: 2.07 ms

Generate degenerate aggSig tree
Total: 30 runs in 748 ms
Avg: 24.9333 ms

Verify degenerate aggSig tree
Total: 30 runs in 21 ms
Avg: 0.7 ms

As seen above, the single signature and verification spent 10~50 times compared to ECDSA and Schnorr Signature. The reference bench test of latter is here