BLS Signatures

By Ulrik Strid

‍

BLS is a scheme for making digital signature using pairing friendly elliptic curves. Digital signatures are used to protect authenticity of messages but doesn't hide the content. BLS signatures save space across many signed messages and is a crucial optimization for a block chain.

‍

What is a digital signature

‍

In the physical world, to prove a message is from a specific author we add a signature on a paper. When we then move to the digital world and want to sign a document, a naive way of doing this is to add a picture of the signature into the document. This has obvious drawbacks - anyone can forge a signature and we can't prove that the message has not been changed.

What makes digital signatures effective is that they takes both the unique identity of the author and the contents of the document being signed into account. Should one of them change, the signature will change too.

One of the first schemes for digital signatures was RSA. RSA suffers from a drawback in that it needs large keys, the current recommended smallest key size is now 2048 bytes. Cryptography has come a long way since then and now we have elliptic curves and schemes to use them for signing. Elliptic curve cryptography can have much smaller keys (32 bytes for BLS).

During communication between two parties without a shared secret, the sender of a message will have a private key which is secret. They use this key to sign a hash of the message they want to send to prove that they are the sender. When the other party receives this message they can use the public key, which is not secret, to verify the authenticity.

‍

Why are we interested in this?

‍

We, at Marigold, are implementing Optimistic Rollups for the Tezos blockchain. Rollups are essentially a way to run instructions outside of the chain and then commit the proof back with signatures to the chain. This allows us to increase the throughput - ideally we can fit more than 30,000 rollup transactions in a block, corresponding to about 500 transactions/second. However, each transaction also requires a signature authorizing it from the sender. Signatures are quite large (96 bytes); thus, naively including each signature in each transaction would detract from the potential of rollups. But there are several cryptographic tricks we can do to save space while maintaining integrity, and BLS signatures are one of them.

Calculation for the a bove claim: We have 512kB of available space in a block. One rollup transaction takes about 15B. 512kB/15B = 34 133,3333 transactions/block. But there will be some fluctuation.

‍

What is BLS?

‍

BLS (Boneh - Lynn - Shacham) signature scheme is digital signing scheme whose most well-known usage is for aggregation of multiple signatures, thereby saving space. BLS uses a "pairing friendly curve" - we won't go into the details here, but these curves have the properties we need.

Slightly confusing is that there is a paring friendly curve named BLS12-381 which is not the same thing, but they work very well together.

The standard operations when working with digital signatures are signing and verification.

When using elliptic curves to make digital signatures, the signature is a point on the curve. It works by using a special algorithm to convert from the hashed message to a point on the curve and then multiplying that with the point of the secret key.

To verify the signature we convert the public key to a point and pair it with the point created with the message. We then create another pair from the signature and a special point P. Then to validate the signature we check if these pairs are equal.

The two additional operations that BLS brings are aggregation and verification of aggregate signatures.

To aggregate the signatures, BLS uses the fact that signatures are points and we can just add them together with addition to get a new number that is then our new signature.

To verify aggregate signatures we create a pair for each message and public key and then we multiply the pairs together to form an aggregate pair. We then compare it to the pair of the aggregate signature and the special point P.

‍

Security considerations

‍

The details are beyond the scope of this post, but it is possible for an attacker to construct a special public key that can be used to forge an aggregate signature. There are several schemes to protect against this attack, each with different tradeoffs.

The three main schemes are basic, message augmentation, and proof of possession. These schemes are all implemented ontop of the core that we described in the last section.

• The basic scheme checks that all the signed messages are different.
• Message augmentation works by concatenating the public key and the message and using that as the signed message.
• Proof of possession adds a step to validate that the public key via a extra proof of possession. When there are many signers for the same message this scheme can be very fast because of possible optimizations.

There are other security considerations to take into account as well - side channel attacks, insufficient entropy/randomness, or using libraries that omit parts of the BLS RFC or implement it incorrectly.

‍

In conclusion

‍

We hope that this post helped you understand BLS signatures on a high level, and how we at Marigold plan to implement it for Rollups on the Tezos blockchain.

If you want to learn more you can reach out to us at Marigold or read the RFC.

If you'd like to see more such posts, follow us on Twitter

‍