BLS Signatures Part 1 — Overview

Bitcoin and ethereum both use elliptic-curve cryptography for generating keys and signing transactions. The algorithm they both use is called Elliptic Curve Digital Signature Algorithm (ECDSA), which represents a secure way of signing a message (a transaction for example) using Elliptic Curve Cryptography (ECC).

When work started on eth 2.0 (transition to POS and sharding), all of a sudden simple ECDSA signatures just didn’t cut it anymore as the number of signatures to verify was too big and would take too long on the average machine (See Justin Drake’s post). Eth2.0 latest spec definies 64 committees for every block and each committee can have as many as 2048 validators, with each epoch consisting of 32 blocks.
Under normal ECDSA that means 131,072 (64*2048) signatures for every block (12 sec), and 4,194,304 for every epoch (32 blocks).
If every node in the network will need to verify each signature it becomes infeasible to build a scalable, sharded, blockchain.
As a solution to the above, signature aggregation was considered. Technically it will mean that many signatures could be verified in a batch, significantly shortening the time and resources required. Specifically BLS signatures were considered. The aggregated signature size will be 96 bytes.

This is a two-part blog on BLS signatures, a Digital Signature Algorithm (DSA) being adopted by more and more blockchains for it’s interesting properties.

• Part One will go over the properties of BLS signatures with some technical explanations.
• Part Two will dive deep into how pairings work, which is the crucial theory to understand how BLS is even possible.
• Wonderful sources of information I’ve used are Craig Costello’s Pairing for Beginners and Steve Diaz’s paper

A prerequisite for this article is a good knowledge of how elliptic-curve cryptography works. (A great intro is Craig Costello’s chapter 2)

BLS Signatures — overview

BLS stands for Boneh-Lynn-Shacham, it’s a signature scheme that is based on bi-linear pairings.
A pairing, defined as e(,), is a bilinear map of 2 groups G1 and G2 in some other group, GT. e(,) takese as arguments points in G1 and G2.

Pairings that verifies a signature looks like this: e(g1, sig) = e(pk, H(m))
(in expanded form: e(g1, sk*H(m)) = e(sk*g1, H(m)) = e(g1, sk*H(m))
H(m) is hashing a message to a point on an elliptic curve.
BLS consists of:

• KeyGen — choose a random α. Given generator g1, pk=α*g1
• Sign — σ = α*H(m) ∈ G2 (in the case of eth2.0)
• Verify(pk,m, σ) — if e(g1, σ) = e(pk, H(m)) return true.

https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html

BLS has been around for a few years, slowly finding its way into the blockchain industry. Projects like dfinity, Celo, chia and now eth2.0 leverage BLS for various purposes.

As a side note, Dan Boneh has been very active in the blockchain space in recent years, publishing papers and advising in projects like dfinity and of-course ethereum. It is great to see the academy’s influence on the industry and vice-versa.

Properties

BLS signatures have some really exciting properties that make it special and interesting for many applications.

Deterministic

Many signature algorithms dictate some randomness to be included in every signature to prevent attacks exploiting multiple signatures to recover the secret key.
A famous case was Sony’s Playstation attack where user keys were recovered because Sony did not use a uniform (non bias) random generator for their signatures.

Having a random parameter in a DSA means that a signature on the same message by the same key will result in different signature bytes, though both of those signatures could be easily verified.
Non-deterministic signatures are, of-course, secure but make it harder to implement some applications like signature aggregation and multi-signature schemes (note that both on bitcoin and ethereum multi signature is done on the blockchain protocol level, not the signature implementation level).

BLS is a deterministic signature scheme, meaning that signing the same message with the same key will result in the same signature bytes. This opens up a lot of possibilities as signatures can now be added up in various ways, making aggregation, multisignature, Distributed Key Generation (DKG) and other applications almost feel “native” to the signing algorithm.

Aggregatable

BLS has an out-of-the-box ability to aggregate signatures into a fixed size output of 96 bytes and the aggregated public key is sized to 48 bytes.

σ ⇐ σ1 + … + σ2
signature aggregation is done by simply adding signature EC points (note that it requires the message to be the same for all signatures.

Once aggregated, given that the message signed is the same across, verifying can now become as easy as verifying a single signature:

e(g_1, σ) = e(pk, H(m))

Easy Multisig support

Having the above properties in mind, we can imagine a simple and easy recipe for a BLS multisig support. M-of-N.

Let’s start with the setup phase where a group of participants want to set up a common secret but without having to trust a 3rd party.
We can do a DKG round based on Rosario-Jarecki-Krawczyk-Rabin paper. In a nutshell a group of participants each generates a random polynomial (the free coefficient is the secret) of m -1 degree and shares to the other participants, including some commitment to share verification data. Anyone of the participants can issue a dispute if he thinks he got a wrong share.

Once all participants received N shares they each reconstruct their own group secret. From that point on, to sign a message as a group, we follow Shamir’s secret sharing algorithm. Because BLS signatures are deterministic it becomes feasible to implement such a protocol.

Part 1 — Summary

• BLS is a great adoption of cutting edge cryptography to solve specific issues, scale in the case of eth 2.0.
• The way it works is more complicated than ECDSA but offers some interesting properties and possibilities.
• Behind the scene, what makes BLS possible is a concept called bi-linear pairings. To better understand how pairings work (and thus how BLS works), we will need to cover some basic concepts.
• Part 2 will cover some of the key concepts behind pairings and BLS signatures.
• Part 2 is fairly technical and complex, proceed with caution :)