Your Journey To Consensus (Part 4) — HotStuff
Welcome again into this series of articles, Your Journey to Consensus. In this article, we will be discussing a BFT solution named HotStuff which improves the performance of PBFT in a significant way.
The previous articles:
What is HotStuff
HotStuff is a leader based BFT replication protocol for the partially synchronous model. It works under the Partially synchronous communication hypothesis which means a known bound on message transmission holds after some unknown global stabilization time.
The practical aspect about HotStuff is that a stable leader can drive a consensus decision in just two rounds of message exchanges:
- The first phase guarantees proposal uniqueness through the formation of a Quorom certificate (QC) consisting of (n-f) votes. With n being the number of replicas and f the number of faulty nodes.
- The second phase guarantees that the next leader can convince replicas to vote for a safe proposal.
Problem with View-Change
The view-change is far from simple, is bug-prone, and incurs a significant communication penalty for even moderate system sizes:
- It requires the new leader to relay information from (n-f) replicas, each reporting its own highest known QC.
- makes a huge impact on the practicality of PBFT since it requires a complexity of O(n³) in view change. Also, PBFT face the problem of number of messages being exchanged during the normal case operations which is O(n²) and thats a lot.
Basic HotStuff:
Hotstuff solves the State Machine Replication (SMR) via:
- The protocol works in a succession of views numbered with monotonically increasing view numbers.
- Each view Number has a unique dedicated leader known to all.
- Each replica stores a tree of pending commands as its local data structure.
- To be committed, the leader of a particular view proposing the branch must collect votes from aQuorom of (n-f) replicas in three phases: Prepare, Pre-commit, Commit.
HotStuff algorithm:
HotStuff also is a three phases protocol. However it defers from PBFT in the leader election, since a leader can only do one commit then the view changes.
So the Phases are:
Prepare Phase:
- The protocol for a new leader starts by collecting new-view messages from (n-f) replicas.
- The new-view message is sent by a replica as it transitions into view-number (including the first view) and convinces the highest prepare QC that the replica received. (0 if none)
- The leader processes these messages in order to select a branch that has the highest preceding view in which a prepare QC was formed.
- The leader selects the prepare QC with the highest view, denoted HighQC, among the new view messages.
- The leader extends the tail of highQC.node with a new proposal.
- The leader then sends the the new node in a prepare message to all other replicas.
- If the replica accepts it, it sends a prepare vote with a partial signature.
Pre-commit phase:
- When the leader receives (n-f) Prepare votes for the current proposal CurProposal, it combines them into a preapreQC then broadcast.
- A replica responds to the leader with a signed Pre-Commit vote.
Commit Phase:
- When the leader receives (n-f) pre-commit votes, it combines them into a preCommitQC and broadcasts it in commit messages.
- Replicas respond to it with a commit vote.
Decide Phase:
- When the leader receives (n-f) commit votes, it combines them into a CommitQC.
- Sends it to all replicas and they execute it.
- Replicas increment view number and starts the next view.
And in a more algo-oriented way:
Conclusion
With this we finish our series of articles, Your Journey To Consensus.
This series wasn’t too technical because it was meant to give basic understanding about what consensus is, how it works, and build basic intuition why decentralized systems converge.
Hope you had enjoyed and im open to any discussion.
Reference:
- HotStuff: BFT Consensus in the Lens of Blockchain: https://arxiv.org/abs/1803.05069
