HotStuff: BFT Consensus with Linearity and Responsiveness
Introduction
HotStuff is a Byzantine Fault Tolerance (BFT) consensus protocol that achieves much lower time complexity than previous BFT consensus implementations (i.e., PBFT, SBFT, etc). HotStuff is implemented for partially synchronous systems. It achieves a lower time complexity by using a 4-step design, pipelining (in chained HotStuff), and message cryptography. HotStuff also provides optimistic responsiveness.
There are several parts of any BFT protocol: first, the BFT protocol must provide a view-change, which is an algorithm that allows a new leader to collect information and send it to the follower nodes. Second, the BFT protocol must provide a way for all the nodes to come to a consensus, which is dependent on the BFT protocol itself.
Keywords
- BFT: Byzantine Fault Tolerance; toleration of faulty/malicious nodes.
- Consensus: Multiple nodes coming to an agreement on a subject.
- GST: Global Synchronization Time, or the point in time where afterwards a message has a known transmission bound.
- Optimistic responsiveness: A guarantee that a non-faulty leader node will be able to drive a system to consensus after a known condition (i.e., after GST) in a time frame dependent on the actual delays of messages on the network.
Problem
Current BFT protocols do not scale well for larger-node distributed systems (PBFT, SBFT, etc.); some protocols accomplish consensus in O(N2) time, with N being the number of nodes. Hotstuff remedies this problem by having a time complexity of O(N) for consensus and O(N) for leader replacement. See the below figure (Table 1) for a breakdown of the time complexities of different BFT protocols.
Implementation
HotStuff has 4 steps:
- Prepare - The leader node sends a proposal to all follower nodes; the follower nodes determine if the proposal is valid and if so, they send prepare votes to the leader.
- Pre-Commit - The leader waits for the followers to agree to a proposal (get pre-commit votes from follower nodes), then combines these votes into a pre-commit QC and sends it to all nodes for authentication.
- Commit - Follower nodes vote on moving to the Commit stage. If n-f nodes agree to move to the Commit stage, then they are locked into that commit QC.
- Decide - Hotstuff moves to the next view.
HotStuff uses Cryptography for messages: each node has a signature assigned to it, which is used to provide proof that a message comes from a given node. The signatures from each node are aggregated and merged into a Quorum Certificate (QC), which allows for a simple and fast way to see if a consensus has been reached or not. This decreases the number of signatures required to be authenticated to O(N) time.
The chained implementation of HotStuff allows for pipelining - a set of nodes can be in different views at the same time, with each view being in a different HotStuff stage. This allows for more parallelism and better performance.
Class Discussion
Is the paper and accompanying slides based on the basic version of HotStuff, or the pipelined version of HotStuff?
- The paper goes over both versions, with performance comparisons being drawn between the two in the slides.
Can a leader election happen between the two command stages? Does it ever happen?
- HotStuff can have different leaders between commands. The table in the slides showcases a chained HotStuff pipeline example.
What does optimistic responsiveness mean?
- Optimistic responsiveness ensures that even with a faulty leader, a system can elect a new leader and can keep going.
For all the protocols being tested in Table 1, are all the protocols in the table partially synchronous models or partially asynchronous?
- Asynchronous BFT protocols cannot exist (they cannot reach consensus); partially synchronous means the same thing as partially asynchronous, but the table uses BFT protocols that are labeled as partially synchronous.
Is HotStuff used in industry?
- Hotstuff was used for quite a bit at Facebook, it’s still recent, so there is not as much adoption as one would expect.
For a distributed system that requires consistent data, would BFT be the beneficial choice?
- If your system and nodes are secured, you probably don’t need BFT.
sources
https://dl.acm.org/doi/10.1145/3293611.3331591
https://courses.corelab.ntua.gr/pluginfile.php/9663/course/section/1387/22-23.atc.balla.pdf