Paper review: HotStuff Protocol
In this post, I summarize the HotStuff protocol. There are many versions of HotStuff, but this post focuses on THIS paper.
HotStuff BFT is a replicate state machine to solve the consensus problem. It assumes the byzantine model where nodes can behave arbitrarily. The time model is a partially synchronous model where delta time is unknown at the beginning of the protocol, but it will be known after some time called GST. The protocol guarantees the client request to be committed within the stabilization period.
HotStuff delivers its messages in a network speed. This gives the protocol a responsiveness property. The HotStuff leader election mechanism is very simple and costs a linear message of communication. HotStuff uses a threshold signature scheme to sign n-f votes in a single authentication message to measure the complexity of the protocol.
The basic HotStuff protocol works in a succession of views numbered with a dedicated leader known to all nodes. In chained HotStuff, the idea is to change the view on every preparation phase, so each proposal has its own view. The leader does not actually carry a pre-commit phase, but instead initiates a new prepare phase and adds its own proposal. This preparation phase for view v+1 simultaneously serves as the pre-commit phase for view v. The prepare phase for view v+2 simultaneously serves as the pre-commit phase for view v+1 and as the commit phase for view v. This is possible because all the phases have identical structures.
Prepare phase: After receiving n-f view messages, the leader chooses the highest branch where prepareQC was formed and is known as highQC. The leader sends HighQC in a prepare message to all replicas. Upon receipt, replicas vote back on the prepare message.
Pre-commit phase: When a leader receives n-f prepare votes for the current proposal, it combines them into a prepareQC and broadcasts prepareQC in a pre-commit message. Upon receipt, replicas vote back on a pre-commit message.
Commit phase: When a leader receives n-f pre-commit votes, it combines them into a pre-commitQC and broadcasts it in a commit message. Upon receipt, replicas vote back on a commit message and set lockedQC to pre-commitQC. This is a safety guard.
Decide phase: When a leader receives n-f commit votes, it combines them into a commitQC and broadcasts commitQC in a decide message. Upon receipt of a decide message, replicas execute the commands in the committed branch. The replicas increment viewNumber and start the next view.
HotStuff decouples the safety and the liveness properties. Safety is specified via voting and commit rules while liveness is specified separately via a Pacemaker. The pacemaker guarantees liveness after GST and synchronizes all correct replicas and a unique leader into a common height for a sufficiently long period of time. Pacemaker needs to provide the proposer with a way to choose a proposal that does not conflict with the preferred branch of any correct proposer. This is done so that indeed, all correct proposers will vote for it.
The HotStuff defines responsiveness as the correct leader finishing the consensus in time that doesn’t depend on the timeout. The leader itself can be faulty and can be offline. Replicas must wait for the timeout of the leader’s proposal if the leader is malicious before moving to the next view. HotStuff efficiently switches primaries for every consensus decision, providing the potential of decentralization; however, the design of HotStuff does not favor local communication, and the usage of threshold signatures strongly centralizes all communication for a single consensus decision to the primary of that round. HotStuff has very high latencies due to its 4-phase design. As evident, HotStuff clients face severe delays in receiving a response for their client requests.
