It's commonly accepted wisdom to “never roll your own crypto,” it's always better to use well-established, trusted implementations and protocols. Even when using well-known cryptographic primitives for their apparently intended purpose, it is surprisingly easy to introduce subtle errors and unintended edge cases.

In this blog post, we will explore one such case appearing in production blockchain infrastructure. We focus specifically on a case where ambiguity on message binding in BLS signatures and their aggregation may lead to different behavior than protocol designers often intend. Through the following discussion, we will demonstrate how to think about the composition of cryptographic primitives into higher-level protocols.

BLS Signatures offer a simple and efficient way to construct a scheme in which multiple parties all cryptographically agree on some fact. Given a secret key and a message hashed appropriately to a curve point , a BLS signature is obtained as . The public key related to is , with the group generator. Signature verification requires a special bilinear mapping called a pairing (denoted by ), from which it follows that: . For simplicity, we use generic group notation and do not distinguish between the source groups and of the pairing, which are determined by the choice of the pairing-friendly elliptic curve. Given a signature of a message , and the public key of the purported signer , verifying the signature is simply checking the validity of the following equation: . We can see this equality must hold by expanding out the definitions; we have , so . Using the aforementioned property of the bilinear map we can now “move" , giving: .  In other words, a signature that satisfies this equation could only be generated by the party who knows the secret behind the public key. A set of signatures can be aggregated by group addition as . The set of corresponding public keys is also aggregated in the same way as . Happily, aggregate verification over the same message works in exactly the same way as a single signature, i.e. , requiring only two pairing operations.

It is important to understand the original use case for which BLS signature aggregation was conceived, namely “Aggregate signatures are useful for reducing the size of certificate chains (by aggregating all signatures in the chain) and for reducing message size” [1]. Comparing this goal to that of other schemes where multiple signatures are involved brings up a clear contrast when it comes to signature verification. For instance, Batch Verification serves the purpose of ascertaining whether all signatures in a batch are valid (without necessarily verifying all of them individually). On the other hand, Screening offers weaker guarantees: it only checks whether the holder of a secret key authenticated the message, but can’t discern whether individual signatures will verify correctly when checked separately.

Despite this distinction, Batch Verification and Aggregation are often confused. This confusion was first pointed out in [2], and in the same paper the authors show that the BLS aggregate signature scheme satisfies screening but does not satisfy batch verification: two invalid signatures that do not verify individually, but that are conjugate (i.e., they cancel out during aggregation) can pass verification. One way of obtaining conjugate signatures is to take two signatures and , both valid for messages and , respectively, and corrupt them with an “error term” , to give: and . Now, and won’t verify individually for their respective messages but their aggregation will, because the corruption term cancels out: .

Another form of conjugate signatures, first appeared in [3], can be obtained by generating two secret keys such that ; the signatures over any message by these private keys would yield the point at infinity (i.e., they effectively cancel each other out) when aggregated together. As aggregation is just group addition in the curve, and the point at infinity acts as the operation’s neutral element (the “zero” of the group operation), the two invalid signatures just “disappear”. The same applies to the two public keys, and that’s why the verification under the aggregated public key succeeds.

These weaknesses were further expanded upon in [4], which was also the first to explicitly link them to non-repudiation, i.e. the property that prevents the signer from later denying they signed that specific message. Non-repudiation is only possible if the scheme supports message binding, which ensures a signature is inextricably tied to a specific message. As the invalid, conjugate signatures are “lost” after aggregation, it is difficult to obtain message binding with BLS aggregation, and therefore all attempts to single out individual, invalid signatures through aggregate verification are doomed to fail.

We have identified one such attempt in at least one EVM-compatible blockchain we’ll refer to as Protocol P, who devised a mechanism to individuate single, invalid signatures while still reaping the efficiency benefits of BLS aggregation. With that goal, Protocol P built a tree of signature aggregations; the fully aggregated signature exists at the root, each child node is an aggregation of some subset of signatures, where the leaves are the individual signatures over the same message contributing to the scheme. If the aggregate signature is invalid, namely because one of the signatures was for a different message, the tree is recursively traversed to determine which signature was invalid. Crucially, this traversal only occurs if the aggregate signature is invalid; if it is valid, the individual signatures are all assumed to be valid as well. However, this is using BLS signature aggregation for the purposes of Batch Verification which, due to the possibility of conjugates, is not appropriate.

As mentioned, it is not possible to ascertain whether any intermediate signature cancels out with its inverse point because the verification assumes that the signatures are over the same message. It is therefore possible to smuggle a signature for a message in a signature collection which was instantiated to verify the message and still pass verification, by leveraging the conjugate secret keys. It is important to stress that these conjugate keys are perfectly valid in the protocol, as they qualify for Proof of Possession, given that they are controlled by two colluding validators.

More specifically, suppose an aggregation tree is created from , with and signing over and signing over (the honest signature). The first two signatures are such that . This would result in a tree with five nodes as follows:

We can expand the signature merging operation as:

Notice that no individual node is the point at infinity. As said, the verification of the “aggregation tree” starts from the root node, therefore is the first to be verified; the public key aggregation expands to:

And the aggregate verification reduces to:

Since the root node's signature verification passes, no further checks are needed and the verification procedure reports that all the signatures are valid on the same message.

The protocol uses signature collections to process block votes, where signature verification is delayed until the required majority is reached, because the votes are optimistically assumed to be for the same block. True batch verification or the verification of all signatures would be expensive in terms of performance, hence the optimization results in the aggregation being confused for verification. The net result is that, despite the system deploying machinery to detect whether a vote is for a conflicting block, the quorum ends up counting signatures for a different block. More precisely, suppose that A*, B*, C and D are participants involved in the consensus, with A* and B* colluding. When it’s C’s slot to propose, A* and B* send C a vote for block 0x00 but they sign over block 0xFF. D sends C a valid vote for block 0x00, i.e. they sign block 0x00. Block 0x00 achieves quorum despite both signatures from A* and B* being for block 0xFF.

While it might be argued that the two colluding validators effectively vote for the correct block, 0x00, because their invalid signatures are still counted despite cancelling out, this action fundamentally violates the message binding property: a signature attests cryptographically to the object being signed, and not to its interpretation or intent. In this case the object being signed is a Vote for a different block than the one for which the quorum is reached. This makes accountability and non-repudiation hard to achieve.

Conclusion

The case explored underscores an important theme in practical cryptography: the operational capabilities of a primitive must match their intended role in some higher-level protocol.

In the case of BLS signatures, the counterexample offered by conjugate signatures demonstrates that relying on aggregate verification alone, although attractive from a performance standpoint, makes it difficult to establish accountability and non-repudiation via message binding, and requires enforcing them through protocol-level constraints. 

While external controls can address these specific flaws, relying on external application logic to enforce cryptographic assurance diminishes the benefit of verifying the correctness of the system as a whole by virtue of protocol design modularity and composability.