BLS Signatures: Short Signatures with Aggregation

BLS Signatures: Short Signatures with Aggregation

BLS (Boneh-Lynn-Shacham) signatures are a pairing-based cryptographic signature scheme that enables short signatures and unique aggregation properties. Unlike ECDSA or RSA, BLS signatures can be aggregated: multiple signatures from different signers on different messages can be combined into a single compact signature. This aggregation property is invaluable for blockchains (combining thousands of validator signatures into one), consensus protocols, and verifiable computation where storage and verification bandwidth are limited.

To understand BLS signatures properly, it helps to be familiar with elliptic curve pairings, elliptic curve cryptography, and public key cryptography.

┌─────────────────────────────────────────────────────────────────────────┐
│                          BLS Signatures                                   │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│   Key Generation:  sk ← random,  pk = g2^sk                              │
│                                                                          │
│   Sign:  σ = H(m)^sk  (σ ∈ G1, 48 bytes)                                │
│                                                                          │
│   Verify:  e(σ, g2) == e(H(m), pk)  using pairing bilinearity           │
│                                                                          │
│   ┌─────────────────────────────────────────────────────────────────┐   │
│   │                    Signature Aggregation                         │   │
│   │                                                                  │   │
│   │  σ_agg = σ1 × σ2 × ... × σn   (single 48-byte signature)        │   │
│   │  pk_agg = pk1 × pk2 × ... × pkn (aggregated public key)         │   │
│   │                                                                  │   │
│   │  Verify aggregated: e(σ_agg, g2) == ∏ e(H(m_i), pk_i)           │   │
│   └─────────────────────────────────────────────────────────────────┘   │
│                                                                          │
│   Key Properties:                                                        │
│   • Short signatures (48 bytes with BLS12-381)                         │
│   • Deterministic (no randomness needed)                               │
│   • Aggregatable (N signatures → 1 signature)                          │
│   • Batch verification (verify many signatures)                        │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

What Are BLS Signatures?

BLS signatures are a digital signature scheme invented by Boneh, Lynn, and Shacham in 2001. They are based on elliptic curve pairings (bilinear maps). The signature is a single elliptic curve point, typically 48 bytes when using the BLS12-381 curve. BLS signatures are deterministic (same message + same key = same signature). Their most powerful feature is aggregation: any number of signatures can be combined into a single signature, and any number of public keys can be combined into a single aggregated public key.

• Deterministic: No randomness required during signing (unlike ECDSA which needs per-signature nonce). Eliminates risks from bad random number generators.
• Succinct: Signature size is constant (48 bytes for BLS12-381) regardless of message size or number of signers.
• Aggregatable: Multiple signatures from independent signers can be combined into one signature. Verification of aggregated signature uses all messages and aggregated public key.
• Batchable: Many signatures can be verified together with fewer pairing operations (2 pairings vs N pairings).
• Threshold Capable: Threshold BLS signatures allow any t-of-n signers to produce valid aggregated signature.

Why BLS Signatures Matter

BLS signatures solve critical problems in blockchain and distributed systems where many signatures must be stored and verified.

• Ethereum 2.0 Consensus: Each epoch, ~16000 validators sign attestations. With ECDSA, this would be 64 bytes × 16000 = 1MB per epoch (every 6.4 minutes). With BLS aggregation, 16000 signatures aggregate to 1 signature (48 bytes). Verification cost reduces from 16000 ECDSA verifications to 1 pairing (plus aggregation precomputation).
• Blockchain Scalability: Reduce on-chain signature storage (important for rollups). Compress many signatures from different users into one (for state updates). Lower gas costs for verifying many signatures.
• Distributed Systems: Byzantine Fault Tolerance (BFT) protocols can use aggregated signatures. Each round's commit messages aggregate to single signature. Reduces message size and storage overhead.
• Verifiable Computation (zk-Rollups): Aggregated signatures for validator sets. Proof of validator participation.
• Threshold Signatures: t-of-n signers can produce aggregated signature (without revealing individual shares). Ideal for wallet recovery, DAOs, and validator sets.

Aspect                  BLS                         ECDSA (secp256k1)
─────────────────────────────────────────────────────────────────────────────
Signature Size          48 bytes (BLS12-381)        64 bytes (DER) / 32+32
Aggregation             Yes (N → 1)                 No
Batch Verification      O(1) pairings               O(N) operations
Deterministic           Yes (no randomness)         No (requires per-signature nonce)
Key Generation          Fast                        Fast
Threshold Support       Native (aggregation)        Complex (Feldman, Pedersen)
Blockchain Use          Ethereum 2.0                Bitcoin, Ethereum 1.0
Implementation           More complex (pairings)    Standard (secp256k1)

How BLS Signatures Work

Setup:
  • G1, G2, GT: groups of prime order r with pairing e: G1 × G2 → GT
  • g1: generator of G1 (48 bytes)
  • g2: generator of G2 (96 bytes)
  • H: hash function to G1 (hash-to-curve)

Key Generation:
  sk ← random number in [0, r-1]   (32 bytes)
  pk = g2^sk                         (96 bytes)

Signing:
  σ = H(m)^sk                        (48 bytes)

Verification:
  Check: e(σ, g2) == e(H(m), pk)

Why this works (bilinearity):
  e(σ, g2) = e(H(m)^sk, g2) = e(H(m), g2)^sk
  e(H(m), pk) = e(H(m), g2^sk) = e(H(m), g2)^sk
  Both equal → valid signature

Signature Aggregation

Aggregation is the most powerful feature of BLS signatures. Multiple signatures from different signers on different messages can be combined into a single signature.

Individual signatures:
  σ1 = H(m1)^sk1
  σ2 = H(m2)^sk2
  σ3 = H(m3)^sk3
  ... (N signatures)

Aggregated signature:
  σ_agg = σ1 × σ2 × σ3 × ... × σN    (single 48-byte point)

Aggregated public key:
  pk_agg = pk1 × pk2 × pk3 × ... × pkN   (single 96-byte point)

Aggregated verification:
  e(σ_agg, g2) == e(H(m1), pk1) × e(H(m2), pk2) × ... × e(H(mN), pkN)

But this still requires N pairings! Optimization batch verification does better.

Batch Verification Optimization

Batch verification uses random weights to reduce many pairings to only 2 pairings (plus exponentiations). This is crucial for large validator sets.

Standard verification:  N pairings
Batch verification:      2 pairings + N exponentiations

Algorithm:
  1. Choose random weights r_i ∈ [0, 2^64)
  2. Compute σ_agg = ∏ σ_i^{r_i}
  3. Compute left_side = e(σ_agg, g2)
  4. Compute right_side = ∏ e(H(m_i), pk_i)^{r_i}
  5. Check left_side == right_side

Security:
  • Probability of false positive is negligible (~2^-64)
  • No false negatives (all signatures valid → batch passes)
  • Verifier can retry with different weights if needed

Ethereum 2.0 uses this to verify 16384 validator attestations per epoch (≈6.4 min)

Number of   ECDSA Verify   BLS Verify   BLS Batch Verify
Signatures   (secp256k1)    (BLS)        (aggr + batch)
─────────────────────────────────────────────────────────────────────────────
1            1 mult         1 pairing    1 pairing
10           10 mult        10 pairings  2 pairings + 10 exp
100          100 mult       100 pairings 2 pairings + 100 exp
1000         1000 mult      1000 pairings 2 pairings + 1000 exp
16384        16384 mult     16384 pairings 2 pairings + 16384 exp

Exponentiations are much cheaper than pairings (~2 orders of magnitude)
Batch verification is a massive win for large batches

Hash-to-Curve

BLS signatures require hashing messages to elliptic curve points (G1). This is not a simple mapping (maps arbitrary bytes to point). IETF RFC 9380 standardizes secure hash-to-curve.

• Simplified SWU (Shallue-Woestijne-Ulas): Constant-time, non-constant time if not careful. Uses rejection sampling (deterministic). Hashing to G1 for BLS12-381.
• Expander Functions: Use SHA-256 or SHA-384 to generate pseudo-random bytes. Domain separation prevents cross-protocol attacks.
• Why not simple map: Simple (x, y) from hash would not be uniformly distributed. Map might leak discrete logarithm information.

H(m) = hash_to_curve("BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_" || m)

Components:
  "BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_"  ← domain separation tag
  m                                            ← message

Purpose:
  • Prevents cross-protocol attacks
  • Same message hashed to different curves
  • Standardized across implementations

Important: All BLS implementations must use same domain separation tag

BLS Applications

Ethereum 2.0 Consensus

Beacon chain uses BLS12-381 signatures for validator attestations, block proposals, and slashing proofs. Validators have BLS public keys (96 bytes). Attestation signatures aggregated per committee (10-16 validators). Block signatures aggregated across all attesting validators (~16,000 per epoch). Use-case: signature aggregation reduces data per epoch from 1MB to 48 bytes.

Filecoin Proof-of-Spacetime (PoSt)

Filecoin uses BLS signatures for aggregation of GPU-generated proofs. Reduces on-chain verification cost.

Zcash (Aggregate Signatures)

Sapling upgrade uses BLS for transaction binding signatures (batch verification). Performance optimization.

Diem (Libra) Blockchain

Used BLS signatures for validator consensus (HotStuff BFT). Aggregated signatures reduced commit messages.

Beacon chain epoch (6.4 minutes, 16384 validators):

Without BLS aggregation:
  Signatures: 16384 × 64 bytes = 1 MB per epoch (2.25 GB per day)

With BLS aggregation:
  Aggregated signature: 48 bytes per attestation type
  Total per epoch: ~few hundred bytes

Savings: >99.9% storage and bandwidth reduction

Implementation:
  Validators submit signatures via gossip
  Block proposer aggregates signatures before including in block
  Consensus layer verifies with batch verification

Threshold BLS Signatures

Threshold BLS allows any t-of-n signers to produce a valid aggregated signature (without revealing individual private keys). Used in distributed key generation (DKG) and validator recovery.

• Distributed Key Generation (DKG): n participants generate key shares without central dealer. Public key is aggregate (anyone can compute). Private shares held by each participant.
• Threshold Signing: t participants sign partial signatures (σ_i = H(m)^(sk_i)). Signature aggregation: combine t partial signatures into σ (Lagrange interpolation on exponents). No need for all n signers.
• Applications: Validator recovery (t-of-n recovery key). DAO governance (multi-signature wallet). Secure oracles (threshold signing).

Aspect                  Threshold BLS            Multisig (Ethereum)
─────────────────────────────────────────────────────────────────────────────
On-chain cost           One signature (aggregated) N signatures
Signature size          48 bytes                 N × 64 bytes
Key management          Distributed              All keys on-chain
Trust assumption        Cryptographic security   Smart contract code
Setup complexity        DKG ceremony             Simple contract deployment
Gas cost (3-of-5)       ~50k gas                ~150k gas (per signature, more for checks)

BLS Signatures Anti-Patterns

• Using Unvalidated Points: Signature may be invalid (not in subgroup G1) leading to small subgroup attacks. Always validate signature point is in the correct subgroup. Precompute G1 order and verify multiplication.
• Incorrect Hash-to-Curve Implementation: Not using standardized hash-to-curve creates mismatched signatures. Missing domain separation causes cross-protocol attacks. Use RFC 9380 implementation (constant-time and deterministic).
• No Public Key Validation: Public key must be in G2 subgroup (for BLS12-381). Validate with subgroup check (multiplication by cofactor).
• Using Non-Deterministic Hashing: Randomness in hash-to-curve breaks determinism and can cause security holes. Use deterministic mapping (SSWU).
• Aggregating Unverified Signatures: Malicious signature can invalidate whole aggregated signature. Verify each signature before aggregation or use rogue public key attack defense: proof of possession (PoP).

Problem:
  Attacker can choose malicious public key: pk' = pk_agg_inv × pk
  Aggregate signature becomes invalid for some signer.

Solution 1: Proof of Possession (PoP)
  Each signer provides PoP = sign(sk, "pop")
  Verifier checks PoP before aggregating

Solution 2: Enhanced Aggregation
  σ_agg = ∏ σ_i
  Verification: e(σ_agg, g2) == ∏ e(H(m_i), pk_i)

But without PoP, attacker can publish pk_agg = g^sk × pk_malicious
  σ_agg = σ1 × σ_malicious (invalid)

Standard Ethereum 2.0 approach:
  Validators must register PoP when depositing
  PoP verified at deposit time

BLS Signatures Best Practices

• Use BLS12-381 Curve: Industry standard for pairing-based signatures (128-bit security). Used in Ethereum 2.0, Filecoin, and many blockchains. Supports aggregation and efficient batch verification.
• Use Standardized Hash-to-Curve (RFC 9380): "BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_" for BLS12-381. Include domain separation tag in hash. Ensure deterministic mapping.
• Validate All Points: Verify signature point is in G1 (subgroup). Verify public key point is in G2 (subgroup). Check for point at infinity (invalid).
• Use Proof of Possession for Aggregation: Require PoP when registering public keys. Prevents rogue public key attacks. PoP = sign(sk, "BLS_POP_BLS12381G1_XMD:SHA-256_SSWU_RO_").
• Batch Verification with Random Weights: Use good randomness source (cryptographic RNG) for weights. Avoid fixed weights (could be gamed). Use 64-bit random integers.
• Use Audited Libraries: Herumi BLS (MCL), arkworks (Rust), milagro_bls, noble-bls12-381 (TypeScript). Avoid self-implementation of pairings.

✓ Use BLS12-381 curve
✓ Use hash-to-curve from RFC 9380
✓ Include domain separation tag
✓ Validate signature (G1 subgroup)
✓ Validate public key (G2 subgroup)
✓ Use proof-of-possession (PoP) for aggregation
✓ Use batch verification with random weights
✓ Use audited pairing library

Popular BLS Libraries

Frequently Asked Questions

1. Are BLS signatures better than ECDSA?
   For aggregation and batch verification, yes. For single signatures, BLS verification is slower (pairing). ECDSA has faster single verification. Choose BLS when you need many signatures (consensus, validators). Choose ECDSA for single wallets, single transactions.
2. What is the difference between BLS and Schnorr?
   Schnorr signatures aggregate linearly (sum signatures). BLS aggregates via multiplication (uses pairings). Schnorr aggregation requires interactive aggregation (signers coordinate). BLS aggregation is non-interactive (independent signers). BLS signatures are shorter (48 vs 64 bytes). Schnorr requires less complex cryptography (no pairings).
3. Are BLS signatures quantum-safe?
   No. BLS relies on discrete logarithm hardness (broken by Shor's algorithm). Quantum computers break BLS signatures. For long-term security, consider hash-based signatures (SPHINCS+) or post-quantum schemes.
4. What is proof of possession (PoP)?
   PoP is a signature by a key owner proving they control the private key. Prevents rogue key attacks during aggregation. PoP = sign(sk, "domain_separation_tag || public_key"). Verifier checks PoP before accepting public key into aggregation set.
5. Can BLS signatures be made deterministic?
   Yes. BLS signatures are naturally deterministic: same message + same key = same signature. Unlike ECDSA (needs per-signature randomness), BLS uses hash-to-curve (deterministic mapping). Eliminates RNG failures (nonce reuse).
6. What should I learn next after BLS signatures?
   After mastering BLS signatures, explore elliptic curve pairings, threshold BLS signatures, and distributed key generation (DKG).