The consensus protocol is the key component of any blockchain. It determines how securely and quickly the blockchain network reach consensus on the next block. The first blockchain consensus protocol which has been powering Bitcoin is the Proof-of-Work (POW) consensus. POW is a process whereby miners race to find the solution to a cryptographic puzzle, the winner of which gets the right to propose the next block and earns some token rewards. POW’s security assumption is that more than 50% of the hashing power is controlled by honest nodes. With such an assumption, the rule for consensus is that the longest chain will be the canonical one, and thus POW consensus is also called chain-based consensus.
Another type of consensus protocol, which has been researched for around two decades in academia, is called PBFT (Practical Byzantine Fault Tolerance) [1]. In PBFT [1], one node is elected as the “leader” while the rest of the nodes are “validators”. Each round of PBFT consensus involves two major phases: the prepare phase and the commit phase. In the prepare phase, the leader broadcasts its proposal to all of the validators, who in turn broadcast their votes on the proposal to everyone else. The reason for the rebroadcasting to all validators is that the votes of each validator need to be counted by all other validators. The prepare phase finishes when more than 2f+1 consistent votes are seen, where f is the number of malicious validators, and the total number of validators plus the leader is 3f+1. The commit phase involves a similar vote counting process, and consensus is reached when 2f+1 consistent votes are seen. Due to the rebroadcasting of votes among validators, PBFT has O(N2) communication complexity, which is not scalable for a blockchain system with hundreds or thousands of nodes.
Harmony’s consensus protocol is a variant of PBFT [1]. Harmony’s consensus reduces the communication complexity from O(N2) to O(N) using BLS (Boneh-Lynn-Shacham) multi-signature. BLS [2] is a pairing-based cryptographic signature scheme that supports multi-party signing with constant-sized signature. The consensus involves following steps:
- The leader constructs the new block and broadcasts the block header to all validators. Meanwhile, the leader broadcasts the content of the block with erasure coding (details will be discussed in another post).
- The validators check the validity of the block header, sign the block header with a BLS signature, and send the signature back to the leader.
- The leader waits for at least 2f+1 valid signatures from validators and aggregates them into a BLS multi-signature. Then the leader broadcasts the aggregated multi-signature along with a bitmap indicating which validators have signed.
- The validators check that the multi-signature has at least 2f+1 signers, verify the transactions in the block content broadcasted from the leader in Step 1, sign the received message from Step 3, and send it back to the leader.
- The leader waits for at least 2f+1 valid signatures from Step 4, aggregates them together into a BLS multi-signature, and creates a bitmap logging all the signers. Finally, the leader commits the new block with all the multi-signatures and bitmaps attached, and broadcasts the new block to all validators.
In Harmony’s BFT (Byzantine Fault Tolerance) consensus, instead of asking all validators to broadcast their votes, the leader runs a multi-signature signing process among all the validators to collect their votes as part of the multi-signature. The idea of using constant-sized multi-signature is inspired by ByzCoin’s BFT [3]. ByzCoin [3] used Schnorr signature scheme for the constant-sized multi-signature aggregation and formed a multicast tree among validators to facilitate the message delivery. However, a Schnorr multi-signature requires a secret commitment round, which leads to a total of two round-trips for a single multi-signature. Moreover, we’ve found that the two-round multi-signature exposes a security issue where a malicious co-signer can sabotage the cosigning process by participating in only the commitment round but not the second round. Harmony improves upon that by using a BLS-based multi-signature, which does not require a secret commit, and thus only includes one round-trip. Besides, Harmony adopts RaptorQ fountain code to speed up the block broadcasting process. The fountain code broadcasting also avoided the security issue in the ByzCoin’s original tree-based multicasting design [4].
Since Harmony’s consensus is based on POS, our actual protocol differs slightly from the one described above. In the actual POS-based consensus, validators’ voting power is proportional to their voting shares gained by staking. Instead of waiting for at least 2f+1 signatures from validators, the leader actually waits for signatures from the validators who collectively possess at least 2f+1voting shares. The details of our POS mechanism will be discussed in future post.
[1] Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI '99), New Orleans, Louisiana, February 1999.
[2] D. Boneh, B. Lynn, and H. Shacham. Short Signatures from the Weil Pairing. In Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, ASIACRYPT ’01, pages 514–532, London, UK, UK, 2001. Springer-Verlag. https://www.iacr.org/archive/asiacrypt2001/22480516.pdf
[3] E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford. Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing. In Proceedings of the 25th USENIX Conference on Security Symposium, 2016.
[4] Drijvers, M., Edalatnejad, K., Ford, B., & Neven, G. (2018). Okamoto Beats Schnorr: On the Provable Security of Multi-Signatures. IACR Cryptology ePrint Archive, 2018, 417.