Skip to content

BLS Signature Aggregation

Table of contents

Open 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 EE that is of order qq and has a generator GG.

We’ll also use a hash function HH as well as an Elliptic Curve Pairing ee

e:E1×E2Fe: E_1 \times E_2 \rightarrow \mathbb{F}

where ee is the pairing that maps two Elliptic Curve points E1E_1 and E2E_2 to an element in a finite field F\mathbb{F}.

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

e(P+Q,R)=e(P,R)e(Q,R)e(aP,bQ)=e(P,Q)ab\begin{aligned} e(P + Q, R) &= e(P, R)e(Q, R) \\ e(aP, bQ) &= e(P, Q)^{ab} \end{aligned}

where PP, QQ and RR are Elliptic Curve points and aZa \in \mathbb{Z}, bZb \in \mathbb{Z}.

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

  1. Generate a private key by sampling a random value from Zq\mathbb{Z}_q:
xi$Zqx_i \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q
  1. Derive the public key from the private key xix_i by multiplying it with the generator GG:
Xi=xiGX_i = x_iG
  1. Generate the signature by multiplying the private key with a hash of the message mim_i, the result of which can be interpreted as a point on the Elliptic Curve:
σi=xiH(mi)\sigma_i = x_iH(m_i)

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

σ=σ1,...,σn\sigma = \sigma_1, ..., \sigma_n

To verify this aggregated signature we can check the following:

e[H(m1),X1]×...×e[H(mn),Xn]=?e(σ,G)e[H(m_1), X_1] \times ... \times e[H(m_n), X_n] \overset{?}{=} e(\sigma, G)

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:

e[H(m1),X1]×...×e[H(mn),Xn]=?e(σ,G)=e(σ1+...+σn,G)=e[x1H(m1)+...+xnH(mn),G]=e[x1H(m1),G]×...×e[xnH(mn),G]=e[H(m1),G]x1×...×e[H(mn),G]xn=e[H(m1),x1G]×...×e[H(mn),xnG]=e[H(m1),X1]×...×e[H(mn),Xn]\begin{aligned} e[H(m_1), X_1] \times ... \times e[H(m_n), X_n] &\overset{?}{=} e(\sigma, G) \\ &= e(\sigma_1 + ... + \sigma_n, G) \\ &= e[x_1H(m_1) + ... + x_nH(m_n), G] \\ &= e[x_1H(m_1), G] \times ... \times e[x_nH(m_n), G] \\ &= e[H(m_1), G]^{x_1} \times ... \times e[H(m_n), G]^{x_n} \\ &= e[H(m_1), x_1G] \times ... \times e[H(m_n), x_nG] \\ &= e[H(m_1), X_1] \times ... \times e[H(m_n), X_n] \end{aligned}

Resources