BLS Signatures: Aggregating Thousands of Signatures Into One

The problem: n signatures over one block

Consensus protocols and certificate systems constantly face the same bottleneck: many parties sign the same message, and someone must store and re-verify all of those signatures. A block finalized by 500,000 validators, a threshold certificate signed by a committee, a multisig wallet — naively each needs its own signature stored and its own verification.

With ECDSA or Ed25519, 500,000 signatures means ~32 MB of data and 500,000 independent verification operations per block. Batch verification helps constant-factor but does not shrink the data. BLS attacks the problem at its root with two properties classical schemes lack:

• Aggregation: combine many signatures into one that is the size of a single signature.
• Public aggregatability: no signer interaction and no secret keys are needed to aggregate — a passive third party can do it after the fact.

The verifier of an aggregate over the same message pays only two pairings plus a cheap sum of public keys, independent of how many signers there were. This is why BLS became the backbone of proof-of-stake consensus.

How it works: hash-to-curve, sign, aggregate, pair

BLS lives in a bilinear-pairing setting: two groups G1, G2 of prime order r with generators g1, g2, and a pairing map e: G1 x G2 -> GT that is bilinear: e(a·P, b·Q) = e(P, Q)^(ab). There is also a hash-to-curve function H mapping arbitrary bytes onto a curve point.

KeyGen:   sk = random scalar in [1, r-1]
          pk = sk · g2                 (a point in G2)

Sign(sk, m):
          sigma = sk · H(m)            (H(m) in G1; scalar-mult)

Verify(pk, m, sigma):
          accept iff  e(sigma, g2) == e(H(m), pk)

Aggregate(sigma_1..sigma_n):
          sigma_agg = sigma_1 + sigma_2 + ... + sigma_n   (point add)

AggregateVerify (same message m):
          apk = pk_1 + ... + pk_n
          accept iff  e(sigma_agg, g2) == e(H(m), apk)

The verification identity holds by bilinearity: e(sk·H(m), g2) = e(H(m), g2)^sk = e(H(m), sk·g2) = e(H(m), pk). Aggregation is just point addition, and because pairing is bilinear the sum of signatures pairs correctly against the sum of public keys — one equation covers the whole group.

Complexity and a worked step-trace

Let n be the number of signers, over a common message m. Key operations:

• Sign: one hash-to-curve + one scalar multiplication — O(1) per signer.
• Aggregate signatures: (n-1) elliptic-curve point additions — O(n) cheap ops, output stays constant size (one point).
• Verify same-message aggregate: sum the n public keys (O(n) adds) then exactly 2 pairings — pairing cost is independent of n.
• Verify distinct-message aggregate: n+1 pairings — one per distinct message plus one for the signature.

Worked trace, n=3, same message m. Signers have sk=2,3,5 (toy scalars). Each computes sigma_i = sk_i·H(m):

sigma_1 = 2·H(m)
sigma_2 = 3·H(m)
sigma_3 = 5·H(m)
sigma_agg = sigma_1+sigma_2+sigma_3 = (2+3+5)·H(m) = 10·H(m)
apk = pk_1+pk_2+pk_3 = (2+3+5)·g2 = 10·g2
check: e(10·H(m), g2) == e(H(m), 10·g2)
       both equal e(H(m),g2)^10  ->  ACCEPT

Storage collapses from 3 points to 1; verification is 2 pairings, not 3. At Ethereum scale, ~500k points become one 96-byte point.

Where it's used in real systems

BLS on the BLS12-381 curve (a pairing-friendly curve giving ~128-bit security, designed by Sean Bowe for Zcash) is now infrastructure:

• Ethereum consensus (proof-of-stake): every validator's attestation and block signature is BLS. Attestations for the same target are aggregated so the beacon chain stores one signature plus a bitfield of who signed, instead of hundreds of thousands of signatures.
• Chia: uses BLS for all transaction signatures, exploiting aggregation to shrink the blockchain.
• Dfinity / Internet Computer and drand: BLS threshold signatures produce publicly verifiable randomness beacons.
• Algorand, Skale, and many L2/bridge designs use BLS multisignatures for committees.

The IETF standardized the scheme in draft-irtf-cfrg-bls-signature, defining two ciphersuites: min-pubkey-size (signatures in G2, 96 B; keys in G1) and min-signature-size (signatures in G1, 48 B; keys in G2). Ethereum uses min-pubkey-size, so its aggregated signature is 96 bytes.

Comparison to alternatives and the tradeoff

Against ECDSA/Ed25519, BLS trades speed and simplicity for aggregation. The costs:

• Slow verification per single signature: a pairing is far more expensive than an ECDSA verify. BLS wins only in the many-signers regime; for a single signature it is slower.
• New, heavier assumptions: security rests on the co-CDH problem in pairing groups (proven in the random-oracle model), a stronger and younger assumption than plain ECDLP.
• No native standard hardware: secp256k1/Ed25519 enjoy ubiquitous library and HSM support; pairings do not.

Versus Schnorr multisignatures (MuSig2): Schnorr also yields one 64-byte signature, but requires interactive signing rounds among the parties. BLS aggregation is non-interactive — signers never talk to each other, and a third party aggregates later. That non-interactivity is decisive for large, asynchronous validator sets where coordinating signing rounds among 500k nodes is infeasible.

Pitfalls, failure modes, and significance

BLS aggregation has one famous foot-gun: the rogue-key attack. If a verifier accepts apk = sum(pk_i), an attacker can choose pk_evil = pk_target·(-1) + x·g2 so the honest key cancels, letting the attacker forge an aggregate that appears to include a victim who never signed. Defenses:

• Proof of Possession (PoP): each key holder signs their own public key; verifiers reject keys without a valid PoP. This is what Ethereum uses — validators submit a PoP at registration.
• Message augmentation: each signer signs H(pk_i, m) (no coefficients), so no attacker-chosen key can cancel an honest one.
• MuSig-style key aggregation: apply per-key coefficients derived from H(pk_i, {pk_j}) to the public keys during aggregation, so a rogue key cannot cancel an honest signer's contribution.

Other pitfalls: signatures and keys must be checked for correct subgroup membership (small-subgroup attacks otherwise); hash-to-curve must be the standardized constant-time map; and distinct-message aggregate verification is n+1 pairings, so it does not give the O(1) win — only same-message aggregation does. Despite these sharp edges, BLS's non-interactive aggregation is what made million-validator proof-of-stake practical, making it one of the most consequential applied-crypto results of the 2000s.

BLS vs. mainstream signature schemes: size, aggregation, and verification cost

Scheme	Signature size	Native aggregation?	Verify cost (n sigs, same msg)
BLS (BLS12-381)	48 B (min-sig) / 96 B	Yes — non-interactive, 1 point	2 pairings + (n-1) point adds
ECDSA (secp256k1)	64-72 B	No	n independent verifies
Ed25519 (EdDSA)	64 B	No (batch verify only)	n verifies, ~2x batch speedup
Schnorr / MuSig	64 B	Interactive multisig only	1 verify (needs signing rounds)
RSA-2048	256 B	No	n verifies (fast per-verify)