How Not to Use Aggregate Signatures in Your Blockchain

The blockchain community struggles with scalability issues of the Proof-of-Work and Proof-of-Stake mechanisms. Indeed, both storage and compute requirements of the most popular blockchains (Bitcoin, Ethereum) are very high. Clearly, this is the inherent problem of the blockchains — one must store every block of transactions. One optimization that is quickly gaining popularity is to use aggregate signatures. The idea is simple:

1. Suppose users with public keys PK_1, …, PK_n sign messages M_1, …, M_n to obtain signatures s_1, …, s_n.
2. If we can compress signatures (s_1, …, s_n) into a small signature s, that can be used to verify the collection of messages (M_1, …, M_n) under the respective collection of the public keys, then we can save on storage and bandwidth.
3. This leads to significant savings. For instance, if signatures are 32 Bytes, and n=1000, then instead of storing 32 KB of data, one only needs to store 32 Bytes. That’s a factor of 1000 improvement!

(For many applications one also needs to store the public keys that were used to compute the aggregate signature. But, there are usually efficient ways to link to public keys directories stored elsewhere).

Some claim, that given aggregate signatures, Bitcoin could say ~25% on bandwidth and storage: https://bitcoincore.org/en/2017/03/23/schnorr-signature-aggregation/

One can imagine compressing blocks of transactions, random beacons used in PoS systems, and so on.

Techniques for aggregating signatures are known for a variety of schemes: DSA, Schnorr, pairing-based, and lattice-based. However, classical schemes from groups require either (a) interactive key-generation, or (b) interactive signing from the participants to compute the joint signature. This makes the schemes less than useful in many contexts. Fully non-interactive schemes are also known, most famously based on the Boneh–Lynn–Shacham pairing-based construction.

However, the careless use of the basic scheme leads to many security pitfalls. To understand one of the issues, let me summarize the scheme:

• Let e: (G, G) → G_T be a bilinear map.
• The secret key is an integer x, and the public key is PK= g^x.

To sign a message M:

• Map the message it to a group element h=H(M)
• Output a signature s = h^x.

To verify a tuple (s, M):

• check that e(s, g) == e(H(M), PK)

By construction, e(s, g) = e(H(M)^x, g) = e(H(M), g)^x. Similarly, e(H(M), g^x) = e(H(M), g)^x. (Here, the equalities hold by the properties of the bilinear map).

Aggregation of BLS Signatures

To aggregate signatures s_1, …, s_n (of messages M_1, …, M_n) under public keys PK_1, …, PK_n, one simply computes their product: s = s_1 * s_2 * … * s_n (where operations are performed over the source group of the bilinear map).

To verify the aggregate signature s:

• Check that e(s, g) == e(H(M_1), PK_1) * e(H(M_2), PK_2) * … * e(H(M_n), PK_n)
• Clearly, in a good case, e(s_1 * s_2 * … * s_n, g) = e(s_1, g) * e(s_2, g) * … * e(s_n, g), and we already established above that e(s_i, g) = e(H(M_i, PK_i) for all i.

An Attack

Suppose the system requires to produce an aggregate signature from two (or more) users with public keys PK_1, PK_2 of the same message M.

(Indeed, this could be a common requirement. For instance, two or more users may be required to sign the same root of the Merkle Tree corresponding to a block of transactions. Alternatively, two or more users may be asked to sign and validate a random nonce R users as a random seed in protocols).

Then, an adversary can carefully craft a public key PK_2 such that his signature alone would suffice to fake an aggregate signature!

That is, suppose the adversary knows PK_1. Then, he chooses a secret x_2 and computes PK_2 = g^{x_2}. However, instead of publishing PK_2, he publishes PK_2' = PK_2/PK_1.

Then, s = H(M)^{x_2} is a valid aggregate signature under joint public key PK_1*PK_2 (which the adversary can easily compute knowing the secret key x_2). Indeed:

• e(H(M)^{x_2}, g) =e(H(M), g)^{x_2}.
• Also, e(H(M), PK_1) * e(H(M), PK_2') = e(H(M), g)^{x_1} * e(H(M), g)^{x2 — x1} = e(H(M), g)^{x_2}.

Hence, the verification will pass. The attack extends to any arbitrary number of participants.

Few Possible Remedies

1. Note that the attack above relies on the fact that two users must sign the same message M. To solve it, the system can insist on never signing the same message. This seems like an add-hoc patch, but one could require that every message that needs to be signed is first mapped to the group via hash H(PK, M), where PK is the key of the user that is computing the signature. This is a rather heuristic solution and breaks many use-cases of aggregate signatures where users must sign the same message.
2. A better approach is to require every user to prove that he/she computed the public key correctly. That is, require users to publish proofs of knowledge of the exponent x.