Source-linked AI summary
HotStuff: BFT Consensus in the Lens of Blockchain
Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, Ittai Abraham
TL;DR
Partially synchronous BFT replication must support safe consensus despite Byzantine faults while scaling leader replacement and avoiding waits for worst-case network delay. HotStuff uses a three-phase leader-based protocol and a graph-based framework to separate safety from liveness. It combines linear view change with optimistic responsiveness and achieves practical throughput and latency comparable to BFT-SMaRt on a deployment with over 100 replicas.
Problem
BFT replication for permissioned blockchains must scale to hundreds or thousands of replicas and handle leader replacement despite wide-area communication variability.
Method
HotStuff uses a three-phase core, a graph-based BFT framework, and a Pacemaker that separates liveness mechanisms from safety mechanisms.
Results
HotStuff is the first partially synchronous BFT replication protocol reported to combine linear view change with optimistic responsiveness, while achieving throughput and latency comparable to BFT-SMaRt.
Takeaways & Limitations
HotStuff provides a simple, expressive bridge between classical BFT foundations and modern blockchains, with constant communication during frequent leader replacements.
Takeaways & Limitations
Progress is guaranteed only after the unknown Global Stabilization Time, because progress before GST is impossible in the partially synchronous model.
Abstract
from arXiv · showhide
We present HotStuff, a leader-based Byzantine fault-tolerant replication protocol for the partially synchronous model. Once network communication becomes synchronous, HotStuff enables a correct leader to drive the protocol to consensus at the pace of actual (vs. maximum) network delay--a property called responsiveness--and with communication complexity that is linear in the number of replicas. To our knowledge, HotStuff is the first partially synchronous BFT replication protocol exhibiting these combined properties. HotStuff is built around a novel framework that forms a bridge between classical BFT foundations and blockchains. It allows the expression of other known protocols (DLS, PBFT, Tendermint, Casper), and ours, in a common framework. Our deployment of HotStuff over a network with over 100 replicas achieves throughput and latency comparable to that of BFT-SMaRt, while enjoying linear communication footprint during leader failover (vs. quadratic with BFT-SMaRt).
1 Introduction
HotStuff addresses the scaling and responsiveness challenges of partially synchronous BFT replication with a three-phase, leader-based protocol. It combines linear view change, optimistic responsiveness, a graph-based framework, and practical performance comparable to BFT-SMaRt.
- Motivation: HotStuff targets permissioned blockchains with hundreds or thousands of replicas, where wide-area variability makes the synchrony bound ∆ large.The model requires n ≥ 3f + 1 replicas and deterministic progress only after GST.
- Motivation: Two-phase view change is complex and communication-intensive, reaching O(n4) authenticators in PBFT or O(n3) with threshold signatures across cascading failures.A new leader must collect and relay information about the highest known QC from n − f replicas.
- HotStuff: HotStuff uses a three-phase core so a new leader can select its highest known QC, simplify leader replacement, and pipeline frequent leader rotation.The additional phase lets replicas change their mind after voting without requiring a leader proof.
- HotStuff: After GST, each correct leader sends O(n) authenticators for consensus, while cascading leader failures cost O(n2) authenticators in the worst case.The new leader’s communication cost is no greater than the current leader’s, supporting frequent succession.
- HotStuff: After GST, a correct leader waits only for the first n − f responses to create a proposal that makes progress, including after leader replacement.This is the protocol’s optimistic responsiveness property.
- Framework and evaluation: HotStuff separates safety rules over voting and commit graphs from liveness handled by a Pacemaker, and represents DLS, PBFT, Tendermint, and Casper in one framework.A prototype with over a hundred replicas achieved throughput and latency comparable to, and sometimes exceeding, BFT-SMaRt; leader-replacement communication remained constant versus quadratic growth.
2 Related work
Related work spans synchronous, asynchronous, partially synchronous, randomized, and blockchain-based approaches to Byzantine consensus and replication. HotStuff is motivated by the need to combine practical BFT replication with rotating leaders in blockchain settings.
- Consensus foundations: Synchronous Byzantine consensus has optimal O(n3) communication, while deterministic asynchronous consensus is impossible with even one failure.Randomization and partial synchrony provide two ways around asynchronous impossibility results.
- Partially synchronous protocols: DLS preserves safety during asynchronous periods and guarantees termination after synchrony, but incurs O(n4) total communication and O(n) rounds per decision.DLS was not designed as a practical solution.
- BFT replication: PBFT uses O(n2) communication and two round-trips per decision for a stable leader, while leader replacement incurs O(n3) communication.Randomized asynchronous Byzantine solutions amortize O(n3) communication through batching.
- Subsequent work: A later protocol based on HotStuff’s idea further improves randomized asynchronous communication complexity to O(n2).The passage identifies this as a parallel submission to PODC’19.
- Blockchain context: Blockchain systems such as Nakamoto Consensus use a synchronous model with probabilistic safety and no finality, motivating work on rotating leaders in hybrid blockchain-BFT systems.Permissionless participation and Proof-of-Work distinguish Nakamoto Consensus from permissioned BFT replication.
3 Model
HotStuff assumes authenticated reliable point-to-point communication among n = 3f + 1 replicas in a partially synchronous network. It measures communication through authenticators and uses threshold signatures and collision-resistant hashing.
- System and faults: The system has n = 3f + 1 replicas, of which up to f may be Byzantine and coordinated by an adversary that learns faulty replicas’ internal state.The remaining replicas are correct.
- Network model: Communication is authenticated and reliable point-to-point, with a known delay bound ∆ applying after an unknown Global Stabilization Time.Safety is guaranteed always, while bounded progress is guaranteed after GST; progress before GST is impossible.
- Cryptography: HotStuff uses threshold signatures, combining k partial signatures into one verifiable digital signature under a shared public key.Each replica holds a distinct private key used to produce a partial signature.
- Cryptography: A collision-resistant hash function maps arbitrary-length inputs to fixed-length identifiers for unique protocol inputs.The adversary’s probability of finding colliding inputs must be negligible.
- Complexity measure: Authenticator complexity sums authenticators received by all replicas to reach consensus after GST, hiding transmission topology while capturing signature-related communication costs.An authenticator is either a partial signature or a signature.
4 Basic HotStuff
Basic HotStuff organizes Byzantine state-machine replication into views led by designated leaders, using quorum certificates, chained proposals, and safety checks. Its three-phase structure supports safe leader replacement, liveness after GST with a correct stable leader, and linear authenticator complexity.
- Protocol structure: HotStuff orders client commands through views in which a unique leader proposes nodes extending a growing branch.Replicas maintain a tree of pending commands, and committed branches are executed consistently.
- Protocol structure: A quorum certificate represents n −f signed votes for a leader proposal and can be compressed into one threshold signature.QCs are associated with a node and view number and justify subsequent proposals.
- Leader replacement: The leader selects the highest prepareQC from n −f new-view messages to choose a safe branch for the new view.An incumbent leader may optimize this by using its own highest prepareQC; the unified protocol retains the collection step.
- Safety and liveness: The safeNode predicate accepts a proposal when it extends the locked node or when its justification has a higher view than the current lock.These safety and liveness rules allow a replica to override a stale lock under the three-phase design.
- Safety and liveness: After GST, a bounded period Tf suffices for a decision when all correct replicas remain in a view and its leader is correct.This is the protocol’s stated liveness condition after network stabilization.
- Complexity: O(n) authenticators are received per phase because leaders broadcast proposals and replicas return one partial signature, while QCs use threshold signatures.The protocol’s phases therefore have linear authenticator complexity under the stated measure.
5 Chained HotStuff
Chained HotStuff pipelines Basic HotStuff phases across successive views, allowing one generic QC to serve multiple logical phases while preserving chained commit and locking rules.
- Pipeline: Chained HotStuff changes the view on every prepare phase, enabling pipelined decisions and reducing the number of message types.The pipeline embeds prepare, pre-commit, and commit phases across successive proposals and views.
- Pipeline: A generic QC is relayed to the next leader, whose new prepare phase simultaneously performs the next logical phase for the preceding proposal.The generic QC functions in all logically pipelined phases.
- Pipeline: Only new-view and generic-phase messages are needed because one generic QC serves the logically pipelined phases.Locking and committing occur only in the commit and decide phases of Basic HotStuff.
- Chain rules: Dummy nodes extend a justified branch to the proposing view height when a QC does not directly reference the preceding view.This equates view numbers with node heights and can create ancestry gaps.
- Chain rules: A node forms a One-Chain, Two-Chain, or Three-Chain when its justified ancestry contains one, two, or three successive direct-parent links.These chain structures correspond respectively to successful prepare, pre-commit, and commit phases.
- Chain rules: A Three-Chain commits its grandparent, while a Two-Chain updates the lock and a One-Chain updates the generic QC.These updates remain safe even when the relevant chain is not direct, provided the generic QC is higher when updated.
6 Implementation
The implementation separates progress from the core protocol through a Pacemaker and provides an event-driven specification, while also supporting a two-phase variant with fewer phases but weaker responsiveness.
- Implementation: The implementation extracts liveness from the protocol body into a Pacemaker, simplifying the event-driven specification and decoupling safety from liveness.Algorithm 4 remains safe even with arbitrary Pacemaker proposal or parent choices and scheduling delays.
- State: The implementation tracks votes, voting height, the locked node, the last executed node, the highest QC, and the Pacemaker’s current leaf.All correct replicas share a genesis node and initialize these structures from its QC.
- Pacemaker: The Pacemaker guarantees progress after GST by synchronizing correct replicas and a unique leader, then helping the leader choose a supported proposal.Synchronization uses increasing delay periods and rotating leadership; proposal selection uses the highest QC collected through new-view messages.
- Two-phase variant: The two-phase HotStuff variant requires a Two-Chain for commit and a One-Chain for locking, reducing phases but losing Optimistic Responsiveness.Its liveness may instead be addressed through the Pacemaker.
7 One-Chain and Two-Chain BFT Protocols
Earlier BFT protocols use One-Chain or Two-Chain commit rules with distinct liveness mechanisms, whereas HotStuff combines linear leader communication with responsiveness through an extra QC step.
- DLS: DLS uses a One-Chain rule, but conflicting locks can deadlock and its unlocking protocol is complex and expensive.Only the leader can decide, and DLS requires n leader rotations and O(n4) message transmissions per decision in the best timely fault-free case.
- PBFT: PBFT’s Two-Chain rule avoids conflicting One-Chains, but higher unseen locks require an involved leader proof to unlock replicas.The original proof costs O(n3) communication, while signature-combining variants reduce this to O(n2).
- PBFT: PBFT leader replacement guarantees liveness during synchrony but incurs quadratic communication per leader replacement.Correct replicas unlock even when their One-Chain is higher than the leader’s proof.
- Tendermint and Casper: Tendermint and Casper use Two-Chain rules and unlock replicas using a higher One-Chain supplied with the leader’s proposal.Casper relaxes the direct-parent requirement for the leaf.
- Tendermint and Casper: Tendermint and Casper require waiting the maximal network delay for progress, so they lack Optimistic Responsiveness.Waiting only for the first n −f messages provides no progress guarantee.
- HotStuff: HotStuff uses a simple leader protocol with linear communication complexity and avoids maximal-delay waiting through an extra QC step.Threshold signatures encode a QC as one value, allowing the leader to collect and disseminate the highest One-Chain linearly.
8 Evaluation
HotStuff’s evaluation compares throughput, latency, scalability, and leader-replacement communication against BFT-SMaRt across batching, payload, replica-count, and network-delay settings. HotStuff generally matches or exceeds BFT-SMaRt while avoiding extra authenticators during view changes, although real-time replacement comparison is not meaningful.
- Evaluation setup: HotStuff’s prototype evaluation compares end-to-end performance with BFT-SMaRt across baseline and scalability experiments.The experiments vary batch size, payload size, replica count, and inter-replica delay.
- Base performance: HotStuff achieved comparable latency and higher maximum throughput than BFT-SMaRt across batch sizes 100, 400, and 800.HotStuff’s batching reduces signature cost per decision, but batching above 400 operations increases latency.
- Base performance: At payload sizes 0/0, 128/128, and 1024/1024 bytes, both HotStuff variants outperformed BFT-SMaRt in throughput with similar or comparable latency.The payload configurations are denoted p0, p128, and p1024.
- Scalability: HotStuff consistently delivered better throughput than BFT-SMaRt with comparable latency as replica count increased, scaling better when n < 32.The evaluation attributes current overhead to using a list of secp256k1 signatures for a quorum certificate.
- Scalability: With 1024-byte payloads, BFT-SMaRt’s throughput scaled worse than HotStuff because of its quadratic bandwidth cost.Under 5ms or 10ms inter-replica delays, HotStuff consistently outperformed BFT-SMaRt in throughput and latency.
- View change: HotStuff used no extra authenticators for view changes, while BFT-SMaRt processed cubic numbers of MACs and quadratic numbers of signatures.Extra authenticators are those not sent when the leader remains stable.
- View change: A meaningful real-time leader-replacement comparison was impossible because BFT-SMaRt became stuck under frequent view changes and timing depends on timeout and election parameters.The authenticator benchmark therefore averaged successful view changes before the system got stuck.
9 Conclusion
HotStuff’s three-phase design simplifies leader replacement and supports pipelining and frequent leader rotation. The supplied conclusion passages also point to Figure 10’s comparison of extra authenticators in BFT-SMaRt view changes.
- Conclusion: HotStuff lets a new leader select the highest known QC, simplifying leader replacement compared with the two-phase paradigm.The three-phase core also makes the protocol easy to pipeline and frequently rotate leaders.
- Conclusion: Figure 10 measures the number of extra authenticators used for each BFT-SMaRt view change.The supplied passage identifies the figure’s subject but does not state a numerical result.
A Proof of Safety for Chained HotStuff
The proof shows that conflicting nodes cannot both become committed by honest replicas. It uses a minimal conflicting quorum certificate and the protocol’s voting conditions to derive a contradiction; liveness additionally assumes two consecutive correct leaders after GST.
- Conflicting nodes cannot both become committed by honest replicas.
- The contradiction proof selects the lowest higher view containing a quorum certificate for a node conflicting with w.This switching point is denoted qcs.
- A correct replica in the intersection of the relevant quorum certificates will not vote for qcs.node because both voting conditions are false.The lock condition is false, and the required ancestor condition is also false by minimality and conflict.
- After GST, deciding requires two consecutive correct leaders.The liveness argument is otherwise stated to follow Basic HotStuff.
B Proof of Safety for Implementation Pseudocode
The implementation-level proof establishes that conflicting nodes cannot both obtain valid quorum certificates or become committed, and that execution preserves command order. The argument relies on quorum intersection, ancestry, and the chained commit structure.
- Conflicting nodes at the same height cannot both have valid quorum certificates.Two quorum certificates would provide at least f + 1 honest voters for each node, forcing an honest replica to vote for both.
- Nodes are organized by parent links into branches, and branches conflict when neither extends the other.
- Conflicting nodes cannot both become committed by honest replicas.The proof analyzes conflicting QC three-chains and chooses the lowest higher conflicting certificate.
- The minimal conflicting quorum certificate prevents an intersecting correct replica from voting for the conflicting proposal.Its lock and ancestry checks both reject the proposal.
- If one command executes before another at an honest replica, every honest replica executing the latter executes the former first.The recursive commit logic preserves ancestry order.
B.1 Remarks
The remarks explain why HotStuff’s safety constraints are necessary. Monotonic voting and direct-parent commit chains prevent executions in which replicas switch branches too late to preserve safety.
- Weakening monotonic voting can break safety by allowing a replica to vote first for b and later for w at the same height.The replica can then switch branches after learning additional certificates.
- The direct-parent commit constraint ensures the height ordering used in the safety proof.
- Without direct-parent commit links, a replica may vote for w′′ and later discover b′′ after w has already become committed.The example uses the ordering w′.height < b.height < b′.height < w′′.height < b′′.height.