This signature scheme is beautiful and simple, but it also has several very nice features, especially for Bitcoin.

Signature aggregation

Now let’s combine all signatures in the block! Imagine we have a block with 1000 transactions and every transaction contains a signature Si, a public key Pi and a message that is signed mi. Why to store all the signatures if we can combine them? After all, we only care if all signatures in the block are valid. Aggregated signature will be just a sum of all signatures in the block:

S = S1+S2+…+S1000

To verify the block we need to check that the following equality holds:

e(G, S) = e(P1, H(m1))⋅e(P2, H(m2))⋅…⋅e(P1000, H(m1000))

If you look carefully you will see that it’s indeed true:

e(G, S) = e(G, S1+S2+…+S1000) = e(G, S1)⋅e(G, S2)⋅…⋅e(G, S1000) = e(G, pk1×H(m1))⋅…⋅e(G, pk1000×H(m1000)) = e(pk1×G, H(m1))⋅…⋅e(pk1000×G, H(m1000)) = e(P1, H(m1))⋅e(P2, H(m2))⋅…⋅e(P1000, H(m1000))

We still need to know all the public keys and calculate 1001 pairing functions, but at least all the signatures in the block take only 33 bytes. Signature aggregation can be done by a miner and save a lot of space in the block.

Key aggregation and n-of-n multisignature

If we are using multisignature addresses, we are signing the same transaction with different keys. In this case we can do key aggregation like in Schnorr, where we combine all signatures and all keys to a single pair of a key and a signature. Let’s take a common 3-of-3 multisig scheme (it can be done similarly for any number of signers).

A simple way to combine them is to add all the signatures and all the keys together. The result will be a signature S=S1+S2+S3 and a key P=P1+P2+P3. It’s easy to see that the same verification equation still works:

e(G, S) = e(P, H(m))

e(G, S) = e(G, S1+S2+S3) = e(G, (pk1+pk2+pk3)×H(m)) = e((pk1+pk2+pk3)×G, H(m)) = e(P1+P2+P3, H(m)) = e(P, H(m))

Just like in Schnorr we need to protect ourselves from the rogue key attack. We can do it either by asking every co-signer to prove that they have private keys for their public keys (by signing their public keys), or we can add some nonlinearity to the scheme and make rogue key attack impossible. Instead of just summing up all the keys and signatures we multiply them by a certain number and then add:

S = a1×S1+a2×S2+a3×S3

P = a1×P1+a2×P2+a3×P3

Here coefficients of the signatures and keys are calculated deterministically from the public key of the signer and all other public keys:

ai = hash(Pi, {P1,P2,P3})

For example it can be just a concatenation of the signer’s public key and the whole set of public keys used for signing: ai = hash(Pi||P1||P2||P3).

The same verification equation still works. There will be additional coefficients ai in the proof, but the logic remains.

Nice thing about this scheme is that you don’t need several communication rounds between devices. You just need to know who are other signers, and you are all set. This is much simpler than 3-round multisig scheme for Schnorr signatures. It also doesn’t rely on any randomness, it is a completely deterministic signature algorithm.

Subgroup multisignature scheme (m-of-n multisig)

Often we don’t want to use n-of-n multisig scheme, we prefer to use m-of-n, say, 2-of-3. We don’t want to lose all our money just because we’ve lost one of our keys. It would be nice to use key aggregation in this scenario. With Schnorr signatures we were able to do so by using merkle tree of public keys. It is not the most efficient way, but it kinda works. Unfortunately, as soon as you go to high m and n values, merkle tree size blows up exponentially.

With BLS signature scheme there is another method. It’s not that simple though. We will need a normal hash function that outputs a number — hash(x), and a hash to the curve — H(x). We will also need a “setup” phase when we decide to use multisig, but after this we don’t need to communicate anymore — we only need signatures to sign any amount of transactions.

Again I will use a simple example where we want to construct 2-of-3 multisig scheme with keys stored on 3 different devices, but it can be extended to any values of m and n.

Setup phase

Each of our devices has a signer’s number i = 1,2,3 that represent its place in a set, a private key pki and a corresponding public key Pi = pki×G. We calculate an aggregated public key exactly the same way as before:

P = a1×P1+a2×P2+a3×P3, ai = hash(Pi, {P1,P2,P3})

Now every device needs to sign that number i is a member of our aggregated public key (for every i), aggregate these signatures and save the result on corresponding device:

MKi = (a1⋅pk1)×H(P, i)+(a2⋅pk2)×H(P, i)+(a3⋅pk3)×H(P, i)

This signature we will call a “membership key” and we will use it later on for signing. Each membership key is a valid n-of-n signature of the message H(P,i), it means that:

e(G, MKi)=e(P, H(P,i))

Remember this equation, we will need it later. It will be used to prove that we are valid participants of the multisignature scheme.

Signing

Now let’s say we want to sign a transaction only with keys pk1 and pk3. We generate two signatures S1 and S3:

S1 = pk1×H(P, m)+MK1, S3=pk3×H(P, m)+MK3

and add them up to obtain single signature and key:

(S’, P’) = (S1+S3, P1+P3)

I write P’ and S’ here to emphasise that this key and signature are signed only by a subset of signers and it not the same as P that is an aggregated key for all signers. To verify this 2-of-3 signature we need to check that:

e(G, S’) = e(P’, H(P, m))⋅e(P, H(P, 1)+H(P, 3))

We remember that membership keys MK1 and MK3 are valid signatures for messages H(P, 1) and H(P, 3) signed by aggregated key P, so:

e(G, S’) = e(G, S1+S3)=e(G, pk1×H(P, m)+pk3×H(P, m)+MK1+MK3) =e(G, pk1×H(P, m)+pk3×H(P, m))⋅e(G, MK1+MK3)=e(pk1×G+pk3×G, H(P, m))⋅e(P, H(P, 1)+H(P, 3))=e(P’, H(P, m))⋅e(P, H(P, 1)+H(P, 3))

That’s it. A bit more complicated than n-of-n, but still understandable.

Possible implementation

To implement this multisignature scheme we will need to send money to an address corresponding to an aggregated public key P and say that we need at least two signatures. In Bitcoin scripting language locking script could look like this:

OP_2 <P> OP_CHECK_BLS_MULTISIG

Here OP_2 tells that we require two keys to sign the message. We don’t say anywhere that there are 3 signers in total, so one can’t say if it is 2-of-3 or 2-of-100 multisig address. We also don’t reveal this information later.

To spend this output we need to provide a key P’, signature S’ and indexes of participating signers — in our case numbers 1 and 3. Unlocking script could look like this:

OP_1 OP_3 <P’> <S’>

Combining these scripts gives us all necessary information. From OP_1 and OP_3 we know that we need to calculate hashes H(P, 1) and H(P, 3), and then we have everything we need to verify the transaction.

This means that for any m and n we need only:

• one aggregated public key P in the locking script
• one aggregated public key of participating signers P’
• one aggregated signature S’
• m numbers with signer’s indexes.

It is very compact and beautiful!

There is only one thing that I don’t like here… Normally we use addresses only once — we use key derivation like BIP32 to generate new private keys and addresses. But for every new set of private keys we also need a set of new membership keys. One way to do it without running through setup phase every time is to generate a bunch of keys, like 1000 of them and get corresponding membership keys. After all, they are just 32-byte long. Then we will need to run the setup phase again only when all 1000 addresses are used.

Drawbacks

As it was pointed out in the comments here and on twitter, I skipped one important part and made you think that BLS signatures are perfect. They are not. And thanks a lot for bringing this up!

Pairing is hard. I completely skipped that part and we considered that our magic function e(P, Q) is efficient and secure. It is not exactly true.

Paring is not so efficient

BLS signature verification is order of magnitude harder than ECDSA. Signature aggregation for the whole block with 1000 transactions still requires to compute 1000 pairing, so verifying one tiny signature in a block may take longer than verifying 1000 separate ECDSA signatures. The only benefit we achieve here is that we can fit more transactions in the block as aggregated signature takes only ~32 bytes.

Unlike BLS, Schnorr signatures are very efficient — they can be validated all together and this process is factor of 3 more efficient than ECDSA. The question then arises: what is more important for us?

Security proof is harder

Pairing functions are complicated, and it can become our foe if we are not careful enough. On the one hand we want pairing to be efficient to verify signatures faster, on the other hand we don’t want to reveal any information about our secret key. These two requirements fight each other and we need to be extremely careful with our choice of pairing-friendly curves.

There is actually an attack on elliptic curve crypto systems, called MOV attack (named after Menezes, Okamoto, and Vanstone), that allows to reduce security of the system by using our magic pairing function. So we really need to be careful here.

Conclusion

BLS signatures are amazing — we can combine all signatures in a block to a single signature, we can use key aggregation and m-of-n multisig scheme without additional communication rounds, we don’t need to rely on random number generators and the scheme itself looks very nice and simple. There is still room for improvement, standardising and optimising everything will take some time. But I hope at some point this signature algorithm will become good enough to be included in the Bitcoin protocol and we will be able to use all these nice features with smaller and more aggregatable signatures.

I am very excited to see the first author Dan Boneh working on cryptocurrencies. He is a great cryptographer and his coursera crypto course is outstanding. I also recommend his crypto book even though it’s not finished yet. I am sure we will see many interesting schemes and protocol improvements from him and his team in the near future.