BLS Signature Aggregation

Table of contents

What it is

Sometimes multiple signatures have to be validated at once which would usually be carried out by validating one signature after the other.

Doing this can be slow and resource intensive as the same mathematical operations have to be carried out multiple times.

BLS Signature Aggregation allows for multiple signatures to be validated in one, single batch.

The result of such validation is binary, meaning that either the validation succeeds of all signatures in the batch are valid or it’s rejected if at least one signature is invalid (even if the others are still valid).

How it works

As a prerequisite, it’s useful to have a solid understanding of Elliptic Curve Pairings and BLS Signatures before continuing.

In this example we’ll be working with an Elliptic Curve $E$ that is of order $q$ and has a generator $G$. All calculations are done $\bmod\ q$ if not stated otherwise.

We’ll also use a hash function $H$ as well as an Elliptic Curve Pairing $e$

where $e$ is the pairing that maps two Elliptic Curve points $E_1$ and $E_2$ to an element in a finite field $\mathbb{F}$.

Recall that an Elliptic Curve Pairing has the following bilinear mappings:

where $P$, $Q$ and $R$ are Elliptic Curve points and $a \in \mathbb{Z}$, $b \in \mathbb{Z}$.

We assume that we want to aggregate and validate $n$ BLS Signatures. Therefore the following steps will be done $n$ times (once per signature):

1. Generate a private key by sampling a random value from $\mathbb{Z}_q$:

2. Derive the public key from the private key $x_i$ by multiplying it with the generator $G$:

3. Generate the signature by multiplying the private key with a hash of the message $m_i$, the result of which can be interpreted as a point on the Elliptic Curve:

Once we did the above steps $n$ times to generate all the signatures for each individual message we can aggregate them:

To verify this aggregated signature we can check the following:

Note that compared to the regular BLS Signature verification algorithm, we’re multiplying the Elliptic Curve Pairings of the individual signatures, yet still check the result of that operation against the pairing of the aggregated signature and the generator (which is the same pairing that’s also checked against in regular BLS Signature verifications).

Why it works

Using the aforementioned bilinear mappings for Elliptic Curve Pairings we can expand the right hand side of the signature verification check to see that the equality is indeed present:

Resources

• Wikipedia - BLS Digital Signature
• Remco Bloemen - BLS Signatures
• Paul Miller - BLS Signature for Busy People
• Stepan - BLS signatures: better than Schnorr
• Ben Edgington - BLS12-381 For The Rest Of Us
• David Wong - What is the BLS signature scheme?
• Nguyen Thoi Minh Quan - Intuitive Advanced Cryptography