07d-bls-signatures.ipynb

Kernel: SageMath 10.5

Notebook 07d: BLS Signatures

Module 07. Bilinear Pairings

---

Motivating Question. ECDSA (Module 06) produces a signature $(r, s)$, two scalars, each the size of the group order. Can we do better? BLS signatures produce a single curve point as the signature, cutting the size in half. Even more remarkably, multiple BLS signatures can be aggregated into a single signature that verifies all at once. This is why Ethereum 2.0 uses BLS, thousands of validator signatures compress into one. How does bilinearity make this possible?

---

Prerequisites. You should be comfortable with:

• Bilinear maps: $e(aP, bQ) = e(P, Q)^{ab}$ (Notebook 07a)

• Pairing-friendly curves and embedding degree (07c)

• Digital signatures: sign/verify paradigm (Module 06, ECDSA)

Learning objectives. By the end of this notebook you will be able to:

1. Implement BLS key generation, signing, and verification from scratch.

2. Understand why the verification equation works (using bilinearity).

3. Aggregate multiple signatures and verify the aggregate.

4. Identify the rogue key attack and understand proof-of-possession as a defense.

1. BLS Signature Scheme Overview

Bridge from Module 06. In ECDSA, verification requires computing $u_1 G + u_2 Q$ and checking an x-coordinate. BLS verification is simpler: a single pairing equation. The trade-off: BLS needs a pairing-friendly curve (more expensive arithmetic), but the signature is shorter and aggregation is trivial.

Setup: A pairing-friendly curve with groups $G_1, G_2, G_T$ of prime order $n$, generators $g_1 \in G_1$ and $g_2 \in G_2$, and pairing $e: G_1 \times G_2 \to G_T$.

Hash-to-curve: A function $H: \{0,1\}^* \to G_1$ that maps messages to curve points.

Algorithm	Operation	Result
KeyGen	Pick random $sk \in \mathbb{Z}/n\mathbb{Z}$, compute $pk = sk \cdot g_2$	$(sk, pk)$
Sign	Compute $\sigma = sk \cdot H(m)$	$\sigma \in G_1$
Verify	Check $e(\sigma, g_2) = e(H(m), pk)$	True/False

# Set up a pairing-friendly curve (supersingular for teaching)
p = 467  # prime, p ≡ 3 mod 4
E = EllipticCurve(GF(p), [1, 0])  # y^2 = x^3 + x, supersingular
card = E.cardinality()
print(f"Curve: y² = x³ + x over F_{p}")
print(f"|E| = {card} = {factor(card)}")

# Use a prime-order subgroup
n = 13  # prime factor of 468
k = 2   # embedding degree

# Extension field for G2 and GT
F2 = GF(p^k, 'a')
E_ext = E.change_ring(F2)

# Find generators for G1 and G2
cofactor = card // n
while True:
    g1 = cofactor * E.random_point()
    if g1 != E(0) and n * g1 == E(0):
        break

g1_ext = E_ext(g1)

cofactor_ext = E_ext.cardinality() // n
while True:
    g2 = cofactor_ext * E_ext.random_point()
    if g2 != E_ext(0) and n * g2 == E_ext(0):
        if g2.weil_pairing(g1_ext, n) != 1:
            break

print(f"\nG1 generator: g1 = {g1}")
print(f"G2 generator: g2 = {g2}")
print(f"Subgroup order: n = {n}")
print(f"Embedding degree: k = {k}")
print(f"Pairing: e(g1, g2) = {g1_ext.weil_pairing(g2, n)}")

def hash_to_curve(message, E, n, cofactor):
    """
    Simple hash-to-curve: hash message to an integer, multiply a random
    base point by cofactor to land in the n-torsion subgroup.
    (Simplified, real hash-to-curve is more complex.)
    """
    h = hash(message) % (10^6)
    # Use the hash to deterministically find a point
    for x_try in range(h, h + 1000):
        x = GF(p)(x_try)
        y_sq = x^3 + x  # for y^2 = x^3 + x
        if y_sq.is_square():
            y = y_sq.sqrt()
            P = E(x, y)
            Q = cofactor * P
            if Q != E(0):
                return Q
    # Fallback
    return cofactor * E.random_point()

# Test hash-to-curve
H_msg = hash_to_curve("Hello BLS", E, n, cofactor)
print(f"H('Hello BLS') = {H_msg}")
print(f"Order: {H_msg.order()} (should divide {n})")

2. Key Generation

# BLS Key Generation
sk = randint(1, n - 1)  # private key: random scalar
pk = sk * g2            # public key: point in G2

print(f"Private key: sk = {sk}")
print(f"Public key:  pk = sk · g2 = {pk}")
print(f"pk in G2? Order = {pk.order()}")

3. Signing

To sign message $m$:

1. Hash the message to a curve point: $h = H(m) \in G_1$.

2. Multiply by the secret key: $\sigma = sk \cdot h$.

That's it! The signature is a single point in $G_1$.

def bls_sign(message, sk, E, n, cofactor):
    """Sign a message using BLS."""
    h = hash_to_curve(message, E, n, cofactor)
    sigma = sk * h
    return sigma

# Sign a message
msg = "Attest to block #42"
sigma = bls_sign(msg, sk, E, n, cofactor)

print(f"Message: '{msg}'")
print(f"H(m) = {hash_to_curve(msg, E, n, cofactor)}")
print(f"Signature: σ = sk · H(m) = {sigma}")
print(f"\nSignature is a SINGLE point in G1 (much shorter than ECDSA's (r,s) pair!)")

4. Verification

To verify signature $\sigma$ on message $m$ with public key $pk$, check:

$$e(\sigma, g_2) = e(H(m), pk)$$

Why does this work? If $\sigma = sk \cdot H(m)$ and $pk = sk \cdot g_2$:

$$e(\sigma, g_2) = e(sk \cdot H(m), g_2) = e(H(m), g_2)^{sk}$$$$e(H(m), pk) = e(H(m), sk \cdot g_2) = e(H(m), g_2)^{sk}$$

Both sides equal $e(H(m), g_2)^{sk}$. Bilinearity does all the work!

def bls_verify(message, sigma, pk, g2, E, n, cofactor):
    """Verify a BLS signature using the pairing check."""
    h = hash_to_curve(message, E, n, cofactor)
    h_ext = E_ext(h)
    sigma_ext = E_ext(sigma)
    
    # Check: e(sigma, g2) == e(H(m), pk)
    lhs = sigma_ext.weil_pairing(g2, n)
    rhs = h_ext.weil_pairing(pk, n)
    return lhs == rhs

# Verify the signature
valid = bls_verify(msg, sigma, pk, g2, E, n, cofactor)
print(f"Message: '{msg}'")
print(f"Signature valid? {valid}")

# Show the pairing values
h = hash_to_curve(msg, E, n, cofactor)
h_ext = E_ext(h)
sigma_ext = E_ext(sigma)
lhs = sigma_ext.weil_pairing(g2, n)
rhs = h_ext.weil_pairing(pk, n)
print(f"\ne(σ, g2)   = {lhs}")
print(f"e(H(m), pk) = {rhs}")
print(f"Equal? {lhs == rhs}")

# Test: wrong message should fail
valid_wrong = bls_verify("Wrong message", sigma, pk, g2, E, n, cofactor)
print(f"Wrong message:    valid = {valid_wrong}")

# Test: wrong key should fail
sk_wrong = randint(1, n - 1)
pk_wrong = sk_wrong * g2
valid_wrong_key = bls_verify(msg, sigma, pk_wrong, g2, E, n, cofactor)
print(f"Wrong public key: valid = {valid_wrong_key}")

# Test: forged signature should fail
sigma_forged = E.random_point()
sigma_forged = cofactor * sigma_forged
if sigma_forged != E(0):
    valid_forged = bls_verify(msg, sigma_forged, pk, g2, E, n, cofactor)
    print(f"Forged signature: valid = {valid_forged}")

Checkpoint 1. BLS verification requires computing two pairings and comparing them. In practice, this is optimized to a single "pairing product" check: $e(\sigma, g_2) \cdot e(-H(m), pk) = 1_{G_T}$. Pairing computation is more expensive than scalar multiplication, but the simplicity of the scheme makes up for it.

5. Comparison: BLS vs ECDSA

Feature	ECDSA	BLS
Signature size	2 scalars (64 bytes at 256-bit)	1 curve point (48 bytes compressed)
Verification	1 scalar mul + 1 multi-scalar mul	2 pairings
Nonce required?	Yes (catastrophic if reused!)	No (deterministic)
Aggregation	Not possible	Yes, key advantage
Curve type	Any EC group	Pairing-friendly only
Speed (sign)	Fast	Slightly slower (hash-to-curve)
Speed (verify)	Fast	Slower (pairings expensive)

6. Signature Aggregation

The killer feature of BLS: aggregation. Given $n$ signatures from $n$ different signers on $n$ different messages, we can combine them into a single signature that can be verified with a single (multi-)pairing check.

Aggregation: $\sigma_{\text{agg}} = \sigma_1 + \sigma_2 + \cdots + \sigma_n$

Verification: Check $e(\sigma_{\text{agg}}, g_2) = \prod_{i=1}^{n} e(H(m_i), pk_i)$

Why? By bilinearity: $$e(\sigma_{\text{agg}}, g_2) = e(\sum_i \sigma_i, g_2) = \prod_i e(\sigma_i, g_2) = \prod_i e(H(m_i), pk_i)$$

# Signature aggregation demo with 3 signers

# Generate 3 key pairs
signers = []
for i in range(3):
    sk_i = randint(1, n - 1)
    pk_i = sk_i * g2
    signers.append((sk_i, pk_i))
    print(f"Signer {i+1}: sk = {sk_i}, pk = {pk_i}")

# Each signer signs a different message
messages = ["Block 100 is valid", "Block 101 is valid", "Block 102 is valid"]
signatures = []

print(f"\nIndividual signatures:")
for i, (sk_i, pk_i) in enumerate(signers):
    sigma_i = bls_sign(messages[i], sk_i, E, n, cofactor)
    signatures.append(sigma_i)
    print(f"  σ_{i+1} = sign('{messages[i]}') = {sigma_i}")

# Aggregate!
sigma_agg = sum(signatures[1:], signatures[0])
print(f"\nAggregate signature: σ_agg = σ_1 + σ_2 + σ_3 = {sigma_agg}")
print(f"Size: 1 curve point (instead of 3!)")

# Verify the aggregate signature
sigma_agg_ext = E_ext(sigma_agg)
lhs_agg = sigma_agg_ext.weil_pairing(g2, n)

# RHS: product of e(H(m_i), pk_i)
rhs_agg = F2(1)
for i, (_, pk_i) in enumerate(signers):
    h_i = hash_to_curve(messages[i], E, n, cofactor)
    h_i_ext = E_ext(h_i)
    rhs_agg *= h_i_ext.weil_pairing(pk_i, n)

print(f"Aggregate verification:")
print(f"  e(σ_agg, g2)           = {lhs_agg}")
print(f"  Π e(H(m_i), pk_i)      = {rhs_agg}")
print(f"  Equal? {lhs_agg == rhs_agg}")
print(f"\nOne aggregate check replaces {len(signers)} individual checks!")

Checkpoint 2. Aggregation saves space and verification time:

• Space: $n$ signatures compress to 1 point (48 bytes for BLS12-381, regardless of $n$).

• Verification: Instead of $2n$ pairings, we need $n + 1$ pairings (one per message + one for the aggregate). For same-message aggregation, it's just 2 pairings total.

In Ethereum 2.0, thousands of validator signatures on the same block attestation are aggregated into one.

7. Same-Message Aggregation

When all signers sign the same message (common in consensus protocols), aggregation is even simpler:

$$e(\sigma_{\text{agg}}, g_2) = e(H(m), \sum_i pk_i)$$

Only 2 pairings regardless of how many signers!

# Same-message aggregation (like Ethereum 2.0 attestations)
same_msg = "Block 200 is valid"

# All signers sign the same message
sigs_same = []
for i, (sk_i, pk_i) in enumerate(signers):
    sig_i = bls_sign(same_msg, sk_i, E, n, cofactor)
    sigs_same.append(sig_i)

# Aggregate signatures
sigma_same_agg = sum(sigs_same[1:], sigs_same[0])

# Aggregate public keys
pk_agg = sum([pk for _, pk in signers[1:]], signers[0][1])

# Verify with just 2 pairings
h_same = hash_to_curve(same_msg, E, n, cofactor)
h_same_ext = E_ext(h_same)
sigma_same_ext = E_ext(sigma_same_agg)

lhs_same = sigma_same_ext.weil_pairing(g2, n)
rhs_same = h_same_ext.weil_pairing(pk_agg, n)

print(f"Same-message aggregation ({len(signers)} signers):")
print(f"  Message: '{same_msg}'")
print(f"  σ_agg = {sigma_same_agg}")
print(f"  pk_agg = {pk_agg}")
print(f"\n  e(σ_agg, g2)      = {lhs_same}")
print(f"  e(H(m), pk_agg)   = {rhs_same}")
print(f"  Valid? {lhs_same == rhs_same}")
print(f"\n  Only 2 pairings needed, regardless of number of signers!")

8. The Rogue Key Attack

There's a subtle vulnerability in naive same-message aggregation. An attacker Mallory can choose her "public key" as:

$$pk_M = sk_M \cdot g_2 - \sum_{i \neq M} pk_i$$

Then the aggregated public key becomes just $sk_M \cdot g_2$, and Mallory can forge an aggregate signature for any message without the other signers' participation!

Defense: Proof of Possession (PoP). Each signer must prove they know the secret key corresponding to their public key by signing the public key itself: $\text{PoP} = sk \cdot H_{\text{pop}}(pk)$.

# Demonstrate the rogue key attack
print("=== Rogue Key Attack ===")

# Alice has a legitimate key pair
sk_alice = randint(1, n - 1)
pk_alice = sk_alice * g2
print(f"Alice: pk = {pk_alice}")

# Mallory creates a ROGUE public key
sk_mal = randint(1, n - 1)
pk_mal_rogue = sk_mal * g2 - pk_alice  # The rogue key!
print(f"Mallory (rogue): pk = {pk_mal_rogue}")

# Aggregated public key = pk_alice + pk_mal_rogue = sk_mal * g2
pk_agg_rogue = pk_alice + pk_mal_rogue
print(f"Aggregated pk = {pk_agg_rogue}")
print(f"sk_mal * g2   = {sk_mal * g2}")
print(f"Equal? {pk_agg_rogue == sk_mal * g2}")

# Mallory can now forge an aggregate signature alone!
forged_msg = "Send all funds to Mallory"
h_forged = hash_to_curve(forged_msg, E, n, cofactor)
sigma_forged = sk_mal * h_forged  # Mallory signs alone

# Verify as aggregate of Alice + Mallory
sigma_f_ext = E_ext(sigma_forged)
h_f_ext = E_ext(h_forged)
lhs_f = sigma_f_ext.weil_pairing(g2, n)
rhs_f = h_f_ext.weil_pairing(pk_agg_rogue, n)

print(f"\nForged aggregate signature on '{forged_msg}':")
print(f"  Verifies? {lhs_f == rhs_f}")
print(f"\n⚠ Mallory forged a signature 'from Alice and Mallory' without Alice's key!")

Checkpoint 3. The rogue key attack is prevented by requiring each signer to provide a proof of possession (PoP), a BLS signature on their own public key using a separate hash function. This proves they know the secret key and can't construct a rogue key that cancels others. Ethereum 2.0 validators must submit a PoP when registering.

Misconception alert. "BLS aggregation is always safe." No, naive aggregation is vulnerable to the rogue key attack. You need either (a) proof of possession for same-message aggregation, or (b) distinct-message aggregation (where each signer uses a unique message), or (c) the "message augmentation" scheme where each message is prepended with the signer's public key.

9. Exercises

Exercise 1 (Worked): BLS Round Trip

Problem. Generate a BLS key pair. Sign the message "Consensus reached". Verify the signature. Then change one character in the message and show verification fails.

Solution:

# Exercise 1: Worked solution
sk_ex = randint(1, n - 1)
pk_ex = sk_ex * g2

msg_ex = "Consensus reached"
sigma_ex = bls_sign(msg_ex, sk_ex, E, n, cofactor)

valid_ex = bls_verify(msg_ex, sigma_ex, pk_ex, g2, E, n, cofactor)
print(f"Message: '{msg_ex}'")
print(f"Signature: {sigma_ex}")
print(f"Valid? {valid_ex}")

# Change one character
msg_mod = "Consensus Reached"  # capital R
valid_mod = bls_verify(msg_mod, sigma_ex, pk_ex, g2, E, n, cofactor)
print(f"\nModified: '{msg_mod}'")
print(f"Valid? {valid_mod}")

Exercise 2 (Guided): Five-Signer Aggregation

Problem. Create 5 signers, each signing the same message "Block 500 is valid". Aggregate all 5 signatures and verify the aggregate with just 2 pairings.

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# TODO 1: Generate 5 key pairs
# signers_ex2 = []
# for i in range(5):
#     sk_i = randint(1, n - 1)
#     pk_i = sk_i * g2
#     signers_ex2.append((sk_i, pk_i))

# TODO 2: Sign the same message
# msg_ex2 = "Block 500 is valid"
# sigs_ex2 = [bls_sign(msg_ex2, sk, E, n, cofactor) for sk, _ in signers_ex2]

# TODO 3: Aggregate signatures and public keys
# sigma_agg_ex2 = ???
# pk_agg_ex2 = ???

# TODO 4: Verify with 2 pairings
# h_ex2 = hash_to_curve(msg_ex2, E, n, cofactor)
# lhs = ???
# rhs = ???
# print(f"Aggregate valid? {lhs == rhs}")

Exercise 3 (Independent): Rogue Key Defense

Problem.

1. Implement a proof_of_possession(sk, pk) function that returns $sk \cdot H_{\text{pop}}(pk)$ (use a different hash-to-curve for PoP).

2. Implement verify_pop(pk, pop) that checks $e(\text{pop}, g_2) = e(H_{\text{pop}}(pk), pk)$.

3. Show that a legitimate signer can produce a valid PoP, but Mallory's rogue key cannot (because Mallory doesn't know the discrete log of her rogue key).

4. Modify the aggregation scheme to require a valid PoP from each signer before accepting their public key.

# Exercise 3: write your solution here

Summary

Concept	Key Fact
BLS KeyGen	$sk \in \mathbb{Z}/n\mathbb{Z}$, $pk = sk \cdot g_2 \in G_2$
BLS Sign	$\sigma = sk \cdot H(m) \in G_1$, one point, no nonce needed
BLS Verify	$e(\sigma, g_2) = e(H(m), pk)$, one pairing equation
Aggregation	$\sigma_{\text{agg}} = \sum \sigma_i$; verify with product of pairings
Same-message	Only 2 pairings: $e(\sigma_{\text{agg}}, g_2) = e(H(m), \sum pk_i)$
Rogue key attack	Attacker crafts $pk$ to cancel others; prevented by proof of possession

BLS signatures are the most elegant pairing-based protocol: short, deterministic, and aggregatable. In the final notebook, we'll see how pairings enable something even more surprising: identity-based encryption.

---

Next: 07e: Identity-Based Encryption