BLS Aggregation and the Rogue-Key Attack It Invites

A BLS signature is one group element. Signing multiplies a hash of the message, mapped into a curve, by the private key. Verification checks a pairing equation. The scheme produces among the shortest public-key signatures in common use: on the BLS12-381 curve a point in the 48-byte group compresses to 48 bytes and a point in the 96-byte group to 96, and the scheme is arranged so that one group holds the public keys and the other holds the signatures. Validation is a single pairing check rather than the two scalar multiplications that Ed25519 needs.

The reason to use it is not the size of one signature. It is that signatures over the same message combine by addition in the group, so a thousand signatures become one signature of the same size, verified with the same single pairing equation against the sum of the public keys. That property is what makes it the basis of consensus protocols where hundreds of validators must attest to the same block without hundreds of signatures on the wire.

The combination is also where the scheme’s main pitfall lives.

The pairing equation

Let $G_1$ and $G_2$ be groups of prime order $p$ with a bilinear map $e : G_1 \times G_2 \to G_T$ satisfying $e(aP, bQ) = e(P, Q)^{ab}$. Fix generators $g_1 \in G_1$ and $g_2 \in G_2$, and publish the hash-to-curve function $H$ that maps a message to a point of $G_2$, as specified in RFC 9380 for the relevant suite.

The private key is a scalar $x \in \mathbb{Z}_p$, and the public key is $X = x g_1 \in G_1$. The signature on message $m$ is $\sigma = x H(m) \in G_2$. Verification checks

$$e(X, H(m)) = e(g_1, \sigma)$$

Both sides are elements of $G_T$, and the check holds because $e(x g_1, H(m)) = e(g_1, H(m))^x = e(g_1, x H(m))$. The verifier needs only the public key, the message, and the signature.

The aggregation property follows from linearity. If signers $i$ produce $\sigma_i = x_i H(m)$ on the same message, the sum $\sigma = \sum_i \sigma_i$ equals $(\sum_i x_i) H(m)$, and verification against the aggregate public key $\sum_i X_i$ succeeds. The aggregate key and aggregate signature are the same size as a single one, so a set of $n$ signatures compresses to one element plus the set of public keys, or to one element alone if the verifier already knows the key set.

Aggregation over different messages

For distinct messages, the aggregate is $\sigma = \sum_i \sigma_i$ where $\sigma_i$ signs $m_i$, and verification requires a product of pairings:

$$e(g_1, \sigma) = \prod_i e(X_i, H(m_i))$$

The right-hand side is a multi-pairing and can be computed more cheaply than $n$ separate verifications because the final exponentiation is shared: the Miller loops run $n$ times but the expensive exponentiation runs once. The saving is real but sublinear; the cost of the product grows with $n$ even though the number of pairing checks does not.

This “different messages” mode has a structural weakness that the same-message mode does not. The verifier must be convinced that the aggregate signature really is the sum of the claimed individual signatures over the claimed messages. An adversary who is one of the signers can choose their own contribution after seeing the others, and the aggregate over a set of messages can be made to verify for a different set of messages. The fix is to require each signer to commit to their message before seeing the others’, or to bind the set into the hash. Protocols that aggregate across messages generally do the latter, by including the full set of (public key, message) pairs in a domain separator that each signer hashes.

The rogue-key attack on multisignatures

The tempting multisignature construction is the simplest one: the group’s public key is the sum of the members’ public keys, and the group’s signature is the sum of their signatures. The attack requires one malicious member and works as follows.

The honest members publish their public keys $X_1, \dots, X_{n-1}$ first. The attacker, joining last, picks an arbitrary private key $x’$ and sets their published key to

$$X_n = x’ g_1 - \sum_{i=1}^{n-1} X_i$$

The aggregate key is then $\sum_i X_i = x’ g_1$, which the attacker controls entirely. Any signature the attacker can make under $x’$ verifies as a group signature, including signatures on messages the honest members never saw. The attacker has not learned their keys; the framing is more direct than that, because the group key itself is now the attacker’s key.

# Pseudocode for the rogue-key computation. q is the group order, G the
# generator, and the group law is written additively.
x_rogue = <scalar the attacker picks uniformly from 1..q-1>
pseudo_key = x_rogue * G - (hs[0] + hs[1] + ... + hs[k - 1])
# pseudo_key is published as the attacker's key. The sum of all k published
# keys is then x_rogue * G, which the attacker alone can sign under.

The attack requires nothing but the ability to publish a public key after seeing the others, which is the normal situation in a permissionless setting. It is not a break of the BLS scheme; every signature involved is valid under its own key. It is a break of the reduction from the multisignature scheme to the underlying signature scheme, because the security proof needs the adversary’s key to be an honest output of key generation, and the attacker’s key depends on the honest keys.

Proofs of possession

The standard defence is to require each member to prove knowledge of their private key at registration. A proof of possession is a BLS signature by the member on their own public key, or a Schnorr proof of knowledge of the discrete logarithm; the verifier checks that the signature verifies under the key being registered. An attacker who publishes a key they do not know the discrete logarithm of cannot produce the proof, because the discrete logarithm of $x’ g_1 - \sum X_i$ is unknown.

The cost is one extra verification per key at registration, paid once, plus the requirement that every verifier of the multisignature trusts that the registration check happened. If the proof of possession is checked at key generation but not re-checked when the key is used, the check is only as good as the key database’s integrity.

A proof of possession does not fully restore the plain aggregate scheme in all settings. It defeats the specific attack above, and it is sufficient for the simple sum construction in a static group, but the security analysis of aggregate signatures has needed refinement whenever the adversary’s key choice is richer than a single published point. Boldyreva’s treatment of multisignatures and aggregate signatures from gap-Diffie-Hellman groups sets out the models in which the sum construction is and is not sound. The repair for the cases that fail is to hash the set of all public keys into the message, so that a key chosen to cancel the others changes the hash for every signer and invalidates the cancellation.

Binding the signer set

The general principle is that an aggregate must be verified against a description of who signed what. Concretely, the message that each signer signs becomes

$$m_i’ = \mathrm{encode}(\mathrm{keyset}, i, m)$$

where $\mathrm{keyset}$ is the sorted list of participating public keys and $i$ is the signer’s position or identity. With this binding, the attacker’s cancellation trick fails, because changing their own key changes $\mathrm{keyset}$ and therefore changes every $m_i’$ and every honest signer’s signature.

The protocol cost is that the keyset must be known before signing starts, which turns the aggregation into a two-round process or requires the set to be fixed in advance by an external mechanism. Consensus protocols solve this by having a known validator set per epoch, so the keyset is fixed and the binding is free. Ad-hoc aggregation among participants who discover each other dynamically has to either run the commitment round or fall back to per-signature verification.

For the same-message case that consensus uses, there is a cheaper alternative. If the message already names the epoch and the block, and the validator set is authenticated by the protocol’s own state, then a rogue key cannot be inserted, because the key set is determined by the protocol, not by the signers’ announcements. The attack needs the attacker to influence the set, and a fixed set removes that influence.

Verification cost and the pairing trap

Verifying an aggregate is one multi-pairing over $n+1$ pairs plus a single final exponentiation. The Miller loop is the dominant cost and scales linearly in the number of pairs, so an aggregate of $n$ signatures does not verify in constant time; it verifies in time proportional to $n$ but with a much smaller constant than $n$ independent verifications, because the final exponentiation is shared and the operations are batched.

There is a subtler cost in the choice of groups. The scheme requires a bilinear map, which means a curve with an embedding degree small enough for the target group to be manageable. Curves used for this are larger than plain signature curves for the same security level, so a BLS signature is 48 or 96 bytes where an Ed25519 signature is 64, and the public keys are correspondingly larger. The hash-to-curve step is also more expensive than hashing to a scalar, because it must produce a point with the right subgroup membership and, for the standard suites, with a distribution indistinguishable from uniform.

Group membership checks are as important here as they are in Ed25519. A signature or public key that is not in the prime-order subgroup can satisfy the pairing equation in ways that reveal the key or that allow a signature to be reused across subgroups. Implementations must validate that points are on the curve and in the correct subgroup before using them, and the cost of the subgroup check, a scalar multiplication by $p$, is significant relative to a single verification.

Where aggregation pays

The scheme pays when many signers sign the same thing: block attestations, threshold signature shares combined into one signature, and cryptographic accumulators. It does not pay when signers sign different things and the verifier needs to know each signature individually, because the aggregate hides which signature belongs to whom unless the verifier recomputes the product, and any per-signer accountability requires separate material.

The distinction between a MAC and a signature is unaffected, as the verification split sets out: an aggregate is still publicly verifiable, and every participant still holds a private key that only they know. What aggregation changes is the size of the evidence, not its nature, and the rogue-key attacks are the price of compressing evidence that was produced by independently chosen keys. The mitigation is always the same in form: make the signer’s key and identity part of what is signed, so that a signature cannot be lifted from one context into another.