HotStuff: the Consensus Protocol Behind Facebook’s LibraBFT
Recently, Facebook’s cryptocurrency Libra published its whitepaper and open-sourced its testnet codes on GitHub. In its whitepaper, we can see that Libra uses LibraBFT, a Byzantine Fault Tolerance consensus protocol. Since this protocol is derived from another consensus protocol HotStuff, it will help us understand what LibraBFT is by learning how HotStuff works.
1. What is HotStuff
HotStuff is a leader-based Byzantine fault-tolerant replication protocol proposed by VMware Research in March 2018. Its pre-printed version has been revised five times and will be officially published at PODC 2019 (2019 Symposium on Principles of Distributed Computing). Similar to many consensus protocols, its network is assumed to be a reliable and secure peer-to-peer network and its communication model adopts the partial synchrony model, which means there exists in the network an upper bound on message transmission delay. This upper bound is either unknown to the nodes in the network, or all the nodes know the upper bound and follow it after a certain unknown point.
In this article, we will briefly explain how HotStuff works and break down how HowStuff achieves its goal by first introducing the PBFT consensus protocol.
2. What is PBFT
Generally speaking, the goal of consensus protocols is to reach an agreement on system state in the decentralized network so that all (honest) nodes can transition from one state to another.
Normally, PBFT uses two rounds of peer-to-peer message exchanges to achieve this goal.
When the leader broadcasts its proposed (legal) state transition request to other nodes, as an honest node in the system, it first needs to know that enough nodes have also received this state transition request, that is, it can confirm this request is valid. Based on this, it also needs to know that enough nodes also confirm that the state transition is valid, thus confirming there is a consensus among enough nodes about the state transition.
When the leader fails during the running of the protocol, for example, the node finds that it cannot communicate with the leader, then the leader needs to be replaced, which means there will be a view change. At this point, the node in the system broadcasts a view change request. When a node receives enough view change requests, it sends a view change confirmation to the new leader. The next view will start when the new leader receives enough view change confirmations.
3. What is Basic HotStuff
We believe that the first change made by HotStuff, and the most important one, is to change PBFT’s mesh communication network to a star communication network, which means each communication will rely on the leader. The node no longer broadcasts the message to other nodes through the P2P network, instead, it sends the message to the leader, which processes it and sends it to other nodes. Thanks to the star communication network, the communication complexity of the system has been greatly reduced. Similar to PBFT, the leader proposes a state transition request, and other nodes check its legitimacy after receiving the request.
The second important change HotStuff made is to merge the view change process with the normal process, which means there is no longer a separate view change process, thus reducing the complexity of view change. It can be seen that during view change in HotStuff, a node in the system does not need to confirm the message “enough nodes want to carry out view change” before notifying the new leader, instead, it can directly switch to the new view and notifies the new leader. HotStuff puts the behavior of confirming the message “enough nodes want to carry out view change” into the normal process. This is a new approach, but it will inevitably lead to a new phase of confirmation for the normal process. Therefore, HotStuff extends PBFT’s two phases into three phases.
Having introduced these two changes, let us now take a look at the phases of HotStuff. The protocol for a new leader starts by collecting new-view messages from replicas. When the leader has collected requests from enough replicas, it will start a new view and proposes its own state transition request, and then send a prepare message to the other nodes. After receiving the prepare message, other nodes in the system verify its legitimacy and confirm the message by following the three phases below:
- PRE-COMMIT phase: When the leader receives prepare votes for the current proposal, it combines them into a prepare quorum certificate and then broadcasts it in precommit messages to all nodes, which is to show that enough nodes have confirmed the state transition request.
- COMMIT phase: When the leader receives PRE-COMMIT votes, it combines them into a precommitQC and broadcasts it in COMMIT messages to all nodes; replicas who received the message can lock the current state transition request so that a consensus decision can be reached even during a view change.
- DECIDE phase: When the leader receives commit votes, it combines them into a commitQC. Once the leader has assembled a commitQC, it sends a decide message to all the other replicas. Upon receiving a decide message, a replica executes state transition in the committed branch and starts the next view.
4. What is threshold signature?
To further reduce communication complexity, the third change HotStuff made is introducing a new cryptographic primitive: threshold signature.
Assume there is a single public key held by all replicas in a (k, n)-threshold signature scheme, and each of the n replicas holds a distinct private key (shards). As long as there are at least k replicas who contribute a partial signature to the message, then the partial signatures by these k replicas can generate a complete signature, which can be verified by the public key.
Generally, the size of the complete signature is unrelated to the number of replicas. HotStuff uses threshold signature to reduce the number of signatures in the consensus protocol. The Ontology team has done extensive research on the threshold signature scheme and we have come up with a number of solutions applicable to the blockchain. We will introduce these solutions in future tech point articles.
We can see that in the three-phase confirmation of HotStuff, the so-called voting refers to the threshold signature on a message by the replicas, which is then sent to the leader. The complete signature is generated when the leader receives enough votes. The leader will attach this signature to the message of the next phase it sends to the replicas and the signature will be verified by them.
5. The Pipeline of HotStuff
It can be seen that the three confirmation phases of Basic HotStuff have the same structure: other nodes vote on a message, and the leader combines the votes and broadcasts them to other nodes. These phases can be represented uniformly and pipelined. This is the fourth change HotStuff made: the pipeline of the consensus phases.
The pipelined HotStuff has improved on Basic HotStuff and carries out view change at each prepare phase. In fact, we can see that this essentially makes the prepare phase of the next view confirm the prepare phase of the current view, that is, the next prepare phase (implicitly) contains the pre-commit confirmation of the current view. Since all the phases have an identical structure, pipelining HotStuff can be achieved.
6. Afterword
In this article, we introduced how HotStuff consensus protocol works. In terms of communication complexity, the changes HotStuff made have brought about significant changes to HotStuff and have also given it new features, such as “Optimistic Responsiveness” discussed in the paper. Moreover, HotStuff is being used by Libra and some other projects.
Many blockchain projects use BFT consensus protocols today, for example, Ontology’s VBFT consensus protocol, which combines VRF (verifiable random function) and BFT. We hope this short article can help you understand how HotStuff works and encourage you to learn more about LibraBFT, VBFT, and other BFT consensus protocols.
Are you a developer? Make sure you have joined our tech community on Discord. Also, take a look at the Developer Center on our website, there you can find developer tools, documentation, and more.
Find Ontology elsewhere
Ontology website / Ontology GitHub / ONTO website / OWallet (GitHub)
