HotStuff: BFT Consensus in the Lens of Blockchain

Introduction

The Scaling Problem

1. Proposal uniqueness through the formation of quroum certificate consisting of (n - f) votes.
2. Second phase guarantees next leader can convince replicas to vote for a safe proposal.

• The new leader needs to collect data from (n − f) replicas, each sharing its highest known QC.
• When just considering the authenticators (like digital signatures), the communication demand for this proposal is O(n^3) in PBFT.
• Some modifications reduce this, but even then, it's still significant (O(n^2) for some variations).
• If O(n) view-changes happen before consensus is reached, communication goes up even more, with potential needs of O(n^4) in PBFT, and O(n^3) with some modifications.

1. New leader simply selects the highest QC they are aware of.
2. Replicas can change their minds after voting without the need of the leader’s proof. This design reduces complexity and simplifies the leader replacement process.
3. Having canonized all phases, HotStuff can be easily pipelined and leaders can be rotated frequently.

• Only a few BFT protocols in the blockchain space, like Tendermint and Casper, have a leadership model as straightforward as HotStuff's.
• These blockchain protocols operate on a synchronous basis. Proposals are made at fixed intervals considering the longest time required to relay messages in a vast peer-to-peer network.
• Optimistic Responsiveness:
• Many practical BFT SMR solutions prioritize "optimistic responsiveness."
• It means that a reliable leader, once chosen, can achieve consensus based only on actual message delays, not on some predetermined delay maximum.
• In essence optimistic responsiveness allow synchronous protocols to commit instantaneously when some optimistic conditions are met.
• This feature, however, is missing in protocols like Tendermint and Casper. There may be scenarios where the leader is unaware of an honest replica with the highest QC, which could hinder progress indefinitely.
• If necessary delays are not integrated into essential protocol steps, liveness (a system's ability to progress) can be compromised. Such failures have been documented in various deployments.

Hotstuff Contributions

• The expense for a new leader to achieve consensus is the same as for the existing leader.
• This feature supports the frequent rotation of leaders, which is beneficial for blockchain systems to maintain chain quality.

• HotStuff introduces an extra phase in each view, which adds a slight latency. This trade-off simplifies the leader replacement process and the added delay is often negligible compared to other protocols.

• Hotstuff provides a BFT replication framework over node graphs, where safety is defined by voting and commit graph rules, and liveness is dicated by a “Pacemaker”.

• Hotstuff stands out for its simplicity with just two message types and clear rules for replica behavior.
• The protocol cleanly separates liveness mechanisms (within a Pacemaker) from safety mechanisms.
• Its design is versatile, able to represent multiple known protocols with slight variations.
• This adaptability results from its operation over a node graph, bridging traditional BFT principles and modern blockchain technologies.

Model

• The system comprises a set of n=3f+1 replicas.

n = 3f + 1

• Replicas are indexed from 1 to n (i.e., i ∈ [n] where [n] = {1, . . . , n}).

• A subset F of the replicas, containing up to f=∣F∣ replicas, may be Byzantine faulty.
• The remaining replicas are correct.
• Byzantine replicas might behave arbitrarily and are assumed to be controlled by a single adversary.
• This adversary has access to all internal states of the Byzantine replicas, including their cryptographic keys.

• It's point-to-point, meaning each message is sent from one replica directly to another.
• Communication is authenticated (verifiable) and reliable.
• A message sent by one correct replica will only be received by another correct replica if it was intended for them.
• "Broadcast" means that the broadcasting replica sends the same message to all replicas individually, including itself.

• The system operates under the "partial synchrony" model proposed by Dwork et al.
• There's a known time limit, ∆, and an unknown Global Stabilization Time (GST).
• After GST, any message sent between two correct replicas is guaranteed to arrive within the ∆ time limit.

• The protocol always ensures "safety", meaning it avoids incorrect decisions.
• "Progress", or moving forward in the consensus process, is guaranteed after GST within a specified time limit. Before GST, ensuring progress is not possible.
• In real-world scenarios, the protocol assures progress if the system remains stable after GST, with messages arriving within the ∆ time frame.

Cryptographic Primitives

Basic HotStuff