Bilinear Pairings and BLS Signatures: Compressing Ten Thousand Signatures into One

This article has three layers:

1. The intuition: what a pairing can do, and why signature aggregation matters
2. Real-world use: the Ethereum consensus layer, zk-SNARKs, Filecoin, threshold signatures
3. The mathematics: bilinearity, BLS signatures and aggregation, rogue-key attacks and a toy worked example

Layer 1: The Intuition

1.1 What's missing on an elliptic curve

In an elliptic curve group, we can add points and multiply them by integers: given $aP$ and $bP$, we can compute $aP + bP = (a+b)P$. But we can't "multiply" two points to get $abP$, or Diffie–Hellman would be insecure.

A pairing offers a compromise: it can't compute $abP$ directly, but it can test "does $a \cdot b$ equal $c$", even if you see only $aP$, $bQ$ and $cP$ and don't know $a, b, c$. It is like a balance scale: you don't know the weight of each block, but you can see whether the two sides balance.

1.2 Why signature aggregation matters

Imagine a committee of 10,000 members, each of whom must sign the same block.

• Ordinary signatures (ECDSA, Schnorr): 10,000 signatures must be stored and verified.
• BLS signatures: the 10,000 signatures simply add up into one 96-byte signature, and verification adds up the 10,000 public keys too and performs one check.

For a blockchain, where storage and verification time are both extremely expensive, this difference is decisive.

Layer 2: Real-World Use

The cost: pairing operations are relatively slow (one pairing costs from a few to a dozen or so times an elliptic curve scalar multiplication), and they require specially constructed "pairing-friendly curves".

Layer 3: The Mathematics

3.1 The definition of a bilinear pairing

Let $G_1, G_2, G_T$ all be groups of prime order $r$, with $G_1, G_2$ written additively and $G_T$ multiplicatively. A map $e: G_1 \times G_2 \to G_T$ is called a bilinear pairing if:

1. Bilinear: $e(P_1 + P_2, Q) = e(P_1, Q)\,e(P_2, Q)$ and $e(P, Q_1 + Q_2) = e(P, Q_1)\,e(P, Q_2)$. It follows that $e(aP, bQ) = e(P, Q)^{ab}$.
2. Non-degenerate: $e(P, Q) \ne 1$ (for generators).
3. Efficiently computable (Miller's algorithm).

In abstract algebra terms: fixing one side, it is a group homomorphism in the other.

Real pairings (the Weil pairing, the Tate pairing and its optimized ate variant) are defined on the $r$-torsion points of an elliptic curve, and $G_T$ is a subgroup of the finite field extension $\mathbb{F}_{p^k}^\times$, where $k$ is called the embedding degree. BLS12-381 has $k = 12$.

3.2 BLS signatures

Let $P$ be a generator of $G_1$, and $H$ a hash function mapping messages into $G_2$ ("hash-to-curve").

• Private key: $x$; public key: $\mathrm{pk} = xP$
• Signature: $\sigma = x \cdot H(m)$
• Verification: $e(P, \sigma) \stackrel{?}{=} e(\mathrm{pk}, H(m))$

Correctness takes one line:

$$e(P, xH(m)) = e(P, H(m))^x = e(xP, H(m)).$$

BLS signatures are also deterministic (no random number needed), naturally avoiding the nonce-reuse accidents of ECDSA.

3.3 Aggregation

When $n$ people sign the same message $m$, add the signatures and the public keys separately:

$$\sigma = \sum_i \sigma_i,\qquad \mathrm{pk} = \sum_i \mathrm{pk}_i.$$

By bilinearity,

$$e(P, \sigma) = \prod_i e(P, x_i H(m)) = e\Big(\sum_i x_i P,\ H(m)\Big) = e(\mathrm{pk}, H(m)).$$

One pairing equation verifies everyone. Different messages can also be aggregated, but verification then takes $n+1$ pairings.

3.4 A worked example (a toy pairing)

Real pairings can't be computed by hand, so here is an insecure toy model that shows the algebraic structure:

3.5 Rogue-key attacks

Aggregation has a trap. After seeing Alice's public key $\mathrm{pk}_A$, Mallory deliberately announces her "public key" as

$$\mathrm{pk}_M = yP - \mathrm{pk}_A.$$

The aggregate public key is then $\mathrm{pk}_A + \mathrm{pk}_M = yP$. Mallory knows $y$, and can single-handedly forge a signature "jointly from Alice and Mallory".

Countermeasures:

• Proof of possession: registering a public key requires signing a specific message with the matching private key, proving you know it. Ethereum validators submit this when depositing.
• Or multiply each public key by a coefficient hashed from all the public keys (similar to how MuSig handles Schnorr).

Summary