🔥

HotStuff: BFT Consensus in the Lens of Blockchain

Introduction

The Scaling Problem

Since the introduction of PBFT (Practical Byzantine Fault Tolerance), numerous BFT solutions were build around its core two-phase paradigm. The practical aspect is that a stable leader can drive consensus in two rounds of message exchange

  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.

View change is the algorithm for a new leader to collect information and propose it to replicas. Unfortunately, view changed based on the two-phase paradigm is complex, bug-prone, and incures a significant amount of communication penalty.

Communication Challenges

  • 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.

HotStuff’s Core Mechanism

Hotstuff uses three-phase approach:

  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.

Comparison with other BFT Protocols

  • 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

Linear View Change: Post GST, a correct leader sends only O(n) authenticators to achieve consensus. This leads to a worst-case communication cost of O(n^2) authenticators during consecutive leader failures.

Optimistic Responsiveness: After GST, a proper leader only waits for the initial n-f responses to ensure a proposal will progress, even if there's a leader replacement.

Leader Succession and Costs

  • 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.

Protocol Design

  • 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.

Theoretical Insights and Practical Implementations

  • 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”.

Simplicity and Flexibility

  • 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.
image

Model

Replicas

  • 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}).

Faults

  • 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.

Network Communication

  • 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.

Synchrony Model

  • 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.

Safety and Progress

  • 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