Introduction

The Boneh–Lynn–Shacham (BLS) signature scheme is an exciting piece of cryptography. It uses pairings on elliptic curves to create short, aggregatable signatures with strong security guarantees. This scheme got popular with usage in Ethereum Beacon Chain, but it has some other exciting use cases, such as VRF.

This post demonstrates the BLS formulas and constructs (non-scientific) proofs to show why they work.

Readers should be familiar with:

• Elliptic curve groups and scalar multiplication

• Finite fields and modular arithmetic

• Basic cryptographic notation

A primer

Pairings

Some elliptic curves have a surprising structure:

$$e: \ \ E(F_p) \times E(F_p) \rightarrow F_{P^a}$$

Two points on the curve can be mapped onto a finite field extension.

A bilinear pairing is an operation on two group elements that satisfies:

$$\begin{align} e(g^r, H(m)^x) &= e(g, H(m))^{rx} && \text{(bilinearity)} \\ &= e(g, H(m))^{xr} && \text{(commutativity)} \\ &= e(g^x, H(m)^r) && \text{(bilinearity)} \end{align}$$

Notes:

• We could have used any other group element instead of $H(m)$, but in the BLS scheme the tuple $(g, H(m))$ naturally appears.

• \(g^x\) denotes scalar multiplication, not exponentiation, since elliptic curve groups use additive or scalar multiplication notation.

• Bilinearity also extends to products:

$$e(a, \prod_{i=1}^{n} b_i) = \prod_{i=1}^{n} e(a, b_i)$$

BLS Signature Scheme

EC Groups

The algorithm may use two elliptic curve groups (often denoted \(G_1\) and \(G_2\), though it can also operate on one:

• $G$: base group

• $g$: generator (base point)

• $q$: order of the group

Key Generation

Pick a random secret key \(x \in \mathbb{Z}_r\).

Derive the public key:

$$Y = g^x \in G$$

Sign

Let the hash function $H$ map messages into the group \(G_1\):

$$sig = H(m)^x$$

Verify

To verify the correctness of a BLS signature, check that:

$$e(g, sig) \equiv e(Y, H(m))$$

If both sides are equal, the signature is valid.

Proof

Expand $sig$ and $Y$:

$$e(g, H(m)^x) \equiv e(g^x, H(m))$$

Apply bilinearity to transform the right term:

$$e(g, H(m))^x \equiv e(g, H(m))^x$$

Since both terms coincide exactly, the equation holds.

Aggregation

One of the exciting properties of BLS signatures is their aggregation support. A single check can verify the validity of numerous signatures. This exact property is used in the Beacon Chain.

Sign

Let each signer \(i \in \{1, \ldots, n\}\) generate their own keypair \((x_i, Y_i)\):

$$sig_i = H(m_i)^{x_i}$$

Aggregate all partial signatures:

$$Sig = \prod_{i=1}^{n} sig_i$$

Verify

To verify an aggregated signature, check:

$$e(g, Sig) \equiv \prod_{i=1}^{n} e(Y_i, H(m_i))$$

Proof

Expand $Sig$ using its definition:

$$e(g, Sig) = e\left(g, \prod_{i=1}^{n} H(m_i)^{x_i}\right)$$

Apply bilinearity step by step to separate the product inside the pairing:

$$e(g, \prod_{i=1}^{n} H(m_i)^{x_i}) = \prod_{i=1}^{n} e(g, H(m_i)^{x_i})$$

Next, expand each term by bilinearity again:

$$\prod_{i=1}^{n} e(g, H(m_i)^{x_i}) = \prod_{i=1}^{n} e(g^{x_i}, H(m_i))$$

Substitute the public keys \(Y_i = g^{x_i}\):

$$\prod_{i=1}^{n} e(g^{x_i}, H(m_i)) = \prod_{i=1}^{n} e(Y_i, H(m_i))$$

Thus:

$$e(g, Sig) = \prod_{i=1}^{n} e(Y_i, H(m_i))$$

We have reached equality from both directions, confirming the validity of the aggregation proof.