david wong

Hey! I'm David, a security engineer at the Blockchain team of Facebook, previously a security consultant for the Cryptography Services of NCC Group. I'm also the author of the Real World Cryptography book. This is my blog about cryptography and security and other related topics that I find interesting.

What is the BLS signature scheme? posted February 2019

BLS

BLS is a digital signature scheme being standardized.

Its basis is quite similar to other signature schemes, it has a key generation with a generator $P2$:

BLS keygen

The signature is a bit weird though, you pretend the hashed message is the generator (using a hash_to_G1 function you hash the message into a point on a curve) and you do what you usually do in a key generation: you make it a public key with your private key

BLS sign

Verification is even weirder, you use a bilinear pairing to verify that indeed, pairing([secret_key]hashed_msg, P2) = pairing([secret_key]P2, hashed_msg).

BLS verify

This weird signing/verifying process allows for pretty cool stuff. You can compress (aggregate) signatures of the same msg in a single signature!

To do that, simply add all the signatures together! Easy peasy right?

BLS aggregate-1

Can you verify such a compressed signature? Yes you can.

Simply compress the public key, the same way you compressed the signature. And verify the sig_compressed with the public_key_compressed. Elegant :)

BLS aggregate-1 verify

But what if the different signatures are on different messages? Well, just add them together as well.

BLS aggregate-n

The process to verify that is a bit more complicated. This time you multiply a bunch of pairing([secret_key]P2, hashed_msg) together, and you verify that it is equal to another pairing made out of the compressed signature. Pairings are magical!

BLS aggregate-n verify


Leave a comment