BLS Signature Scheme Cheatsheet
Command Palette
Search for a command to run...
Comments
Join the discussionNo comments yet. Be the first to comment.
Search for a command to run...
No comments yet. Be the first to comment.
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
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)$$
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
Pick a random secret key \(x \in \mathbb{Z}_r\).
Derive the public key:
$$Y = g^x \in G$$
Let the hash function $H$ map messages into the group \(G_1\):
$$sig = H(m)^x$$
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.
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.
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.
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$$
To verify an aggregated signature, check:
$$e(g, Sig) \equiv \prod_{i=1}^{n} e(Y_i, H(m_i))$$
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.
