Rogue Key Attack in BLS Signature and Harmony Security

Consensus algorithm is one of the most important components in blockchain. Harmony Blockchain achieves consensus through the Fast Byzantine Fault Tolerance (FBFT) algorithm. In FBFT, instead of asking all validators to broadcast their votes, the leader runs a multi-signature signing process to collect the validators’ votes in a O(1)-sized multi-signature and then broadcast it to all validators. Consensus is reached when all the validators validate the aggregated signature against the aggregated public keys for this round of consensus.

The magic behind FBFT consensus is the Boneh–Lynn–Shacha (BLS) signature algorithm. Under this signature scheme, multiple validators sign a common message (i.e. the current block), their public keys (i.e. validator’s BLS public key) can be aggregated (or added ) together to form a new public key and the resulting signatures (from each validator) can also be aggregated together to form a new signature. Instead of verifying each individual validator’s signature with its corresponding public key, we (or other validators) only need to verify the aggregated signature against the aggregated public key.

However, the BLS signature aggregation is insecure by itself due to rogue public-key attack. The simple explanation to the rogue public-key attack is that it the aggregation algorithm is actually an addition operation on the group field G1 (Harmony use G1 instead of G2 for public key, to better understand what is G1 or the math behind BLS, you can read this article) and its reverse operation subtraction operation on the group field G1 is easily available and trivial.

Rogue public key attack against Harmony consensus can be achieved with a malicious leader. Suppose we have N-1 validators and 1 leader with public key P1, P2, P3…PN for consensus. The leader broadcast blockX to all the validators and validators sign blockX with their keys and send back their signatures S1,S2,S3…SN to the leader. The leader then broadcasts the aggregated signature S=S1+S2+…+SN to all the validators. The consensus is reached when the validators validate S with P=P1+P2 +…+PN. Please note that I used a simplified version of the FBFT consensus protocol in my description, the actual FBFT includes more things like Quorum, etc. But what if the current leader is malicious and wants to modify the content of blockX (e.g. double-spend etc). The leader can generate a new key pair P’ and sign blockXmod with the new key and get new signature S’. To make the signature aggregation work, the leader needs to replace the original PN with a rouge public key PN’, where PN’ =P’- P1-P2-…PN-1 and replace original aggregated signature SN with SN’ =S’ -S1-S2-…-SN-1 . All the other validators then do key aggregation and get P’ = P1+P2 +…+PN’ and S’ = S1+S2+…+SN’ as the aggregated public key and signature. The validators will validate the signature and consensus is reached with blockXMod!

Rogue public key attack is possible because it is trivial to calculate the rogue public key PN’ using subtraction operation on field G1. The first defense is knowledge of the secret key (KOSK) which is to check and make sure the owner of PN’ has a matching secret key. This can be done by asking the owner to sign a simple message. Please note that similar to another asymmetric signing algorithm, it is computationally impossible to derive a S’ from PN’ =P’- P1-P2-…PN-1, therefore the malicious leader simply can’t come up with a valid signature for PN’.

As Harmony blockchain uses the Effective Proof-Of-Stake (EPOS) to elect validators and leaders. New validators / leaders will be created through staking. In particular, all new validator need to provide BLS signature by signing the string “harmony-one” using their BLS public keys in the create validator message field here. This implementation blocks rogue public keys from been introduced to consensus committee.

While KOSK is an effective defense against rogue public key attack, a recent paper by Dan Boneh, Manu Drijvers and Gregory Neven introduced a new defense which eliminates the need of KOSK. The paper modifies the BLS algorithm by adding a hash algorithm h over G1(as a random oracle) to the aggregation step. Specifically, the aggregated public key aggP and aggregated signature aggS is calculated using:

aggP=h(P1)×P1+h(P2)×P2 +…+h(PN)×PN

aggS=h(P1)×S1+h(P2)×S2 +…+h(PN)×SN

And verification is successful if and only if aggS can be verified by aggP. By introducing a hash algorithm to the aggregation algorithm, it is extremely difficult to derive a rogue public key from the aggregated public key.
The newly improved BLS algorithm is currently been developed and tested and can replace the original BLS algorithm if all the testing goes well. Stay tuned…