HotStuff: BFT Consensus with Linearity and Responsiveness

Paper: [1]

Notes

  • It is an SMR Protocol.
  • It uses the traditional SMR definition.
  • It is in the partially synchronous network model.
  • HotStuff is adaptively secure. [https://decentralizedthoughts.github.io/2023-01-05-player-replaceability-I/]
  • \(n \geq 3f + 1\).
  • Optimistic responsiveness: progress at network speed when leader is honest, not bound by \(\Delta\) timeouts.
  • \(O(n)\) per-view communication via linear leader and threshold signatures.
  • The \(O(n)\) claim is scoped to the per-view happy path; it excludes pacemaker costs.
  • Basic HotStuff: 4 phases within a single view: PREPARE \(\to\) PRE-COMMIT \(\to\) COMMIT \(\to\) DECIDE. Each phase collects a quorum certificate (QC) from \(n - f\) replicas.
  • Chained HotStuff: Pipelining optimization. Each view runs one phase; a proposal carries the QC from the previous view. A block commits when it reaches depth 3 in a chain of QCs (the 3-chain rule).
  • The 3-chain solves the force-locking problem without PBFT's [2] heavy \(O(n^3)\) view change or Tendermint's [3] timeout-bound rounds. An extra round of voting ensures that if a leader is replaced, the new leader can always determine the highest committed or locked block from the QCs alone.
  • \(O(n)\) view change (a headline contribution vs PBFT's \(O(n^3)\)): in Basic HotStuff, the new leader collects NEW-VIEW messages from \(n - f\) replicas, each containing the sender's \(prepareQC\). The leader picks the highest \(prepareQC\) and proposes extending it. This is \(O(n)\) messages of \(O(1)\) size. The 3-chain commit rule ensures safety despite the leader only using the highest QC.

  • Comparison:

    Protocol Per-view comm. View change Responsive
    PBFT \(O(n^2)\) \(O(n^3)\) Yes
    Tendermint \(O(n)\) N/A No
    HotStuff \(O(n)\) \(O(n)\) Yes
  • The third QC is the price for achieving both linearity and responsiveness simultaneously.
  • In chained HotStuff, consecutive views are effectively required via a structural parent-pointer equality check (\(b^*.parent = b''\)). When a view produces no proposal, a dummy node fills the gap. This mechanism was made explicit as a view-number arithmetic constraint by [4].

Pacemaker

  • The 2019 paper defines only abstract properties for the pacemaker (guaranteeing unique leaders per view, view advancement after GST), not a concrete protocol.
  • This is a deliberate design choice: the protocol is modular, with the pacemaker treated as a replaceable subcomponent. But it means the end-to-end communication complexity is underspecified.
  • Total end-to-end complexity depends on which pacemaker is plugged in. Matching the Dolev-Reischuk [5] \(O(n^2)\) worst-case lower bound took until 2022.
  • Pacemaker lineage:
    • [6]: first dedicated view synchronizer protocol
    • DiemBFT (LibraBFT) v1–v4 (2019–2021): production instantiation of HotStuff with a concrete TC-based pacemaker. Published as a technical report, not peer-reviewed. Most widely deployed pacemaker in practice. Preserves HotStuff's linear view-change communication (proposal carries only \(qc_{high}\), not the full TC). [4] later showed this linear view-change forces 3-chain; making it quadratic enables 2-chain.
    • [7]
    • [8] (RareSync): first to match Dolev-Reischuk \(O(n^2)\) end-to-end in partial synchrony
    • [9]: also matches Dolev-Reischuk
    • [10] (Fever)
    • [11] (Lumiere): current theoretical state-of-the-art
  • There is no single canonical pacemaker. DiemBFT / [4]-style TCs are the practical standard; Lumiere is the theoretical frontier.

Notes

  • [4] showed that HotStuff's underspecified pacemaker forces the 3-chain for liveness. With a concrete TC-based pacemaker, 2-chain suffices (Jolteon achieves this).
  • [12] showed a liveness problem in chained HotStuff when views are not consecutive: the chain can stall if the parent-pointer equality check fails across a view gap. Their protocol eliminates the consecutive-view requirement entirely.
  • The force-locking attack [13] targets Sync HotStuff [14] specifically, not the partially synchronous HotStuff in this paper.

References

[1] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. “HotStuff: BFT Consensus with Linearity and Responsiveness.” https://doi.org/10.1145/3293611.3331591.
[2] Miguel Castro, and Barbara Liskov. 2002. “Practical byzantine fault tolerance and proactive recovery.” https://doi.org/10.1145/571637.571640.
[3] Ethan Buchman, Jae Kwon, and Zarko Milosevic. 2019. “The latest gossip on BFT consensus.” http://arxiv.org/abs/1807.04938.
[4] Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. 2021. “Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback.” http://arxiv.org/abs/2106.10362.
[5] Danny Dolev, and Rüdiger Reischuk. 1985. “Bounds on information exchange for Byzantine agreement.” https://dl.acm.org/doi/10.1145/2455.214112.
[6] Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman. 2021. “Cogsworth: Byzantine View Synchronization.” https://cryptoeconomicsystems.pubpub.org/pub/naor-cogsworth-synchronization/release/5.
[7] Manuel Bravo, Gregory Chockler, and Alexey Gotsman. 2020. “Making Byzantine Consensus Live (Extended Version).”
[8] Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. 2022. “Byzantine Consensus is Theta(n 2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony! [Extended Version].” http://arxiv.org/abs/2208.09262.
[9] Andrew Lewis-Pye. 2022. “Quadratic worst-case message complexity for State Machine Replication in the partial synchrony model.” http://arxiv.org/abs/2201.01107.
[10] Andrew Lewis-Pye, and Ittai Abraham. 2023. “Fever: Optimal Responsive View Synchronisation.” http://arxiv.org/abs/2301.09881.
[11] Andrew Lewis-Pye, Dahlia Malkhi, Oded Naor, and Kartik Nayak. 2023. “Lumiere: Making Optimal BFT for Partial Synchrony Practical.” http://arxiv.org/abs/2311.08091.
[12] Neil Giridharan, Florian Suri-Payer, Matthew Ding, Heidi Howard, Ittai Abraham, and Natacha Crooks. 2023. “BeeGees: Stayin’ Alive in Chained BFT.” https://dl.acm.org/doi/10.1145/3583668.3594572.
[13] Atsuki Momose, and Jason Paul Cruz. 2019. “Force-Locking Attack on Sync Hotstuff.” https://eprint.iacr.org/2019/1484.
[14] Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Maofan Yin. 2020. “Sync HotStuff: Simple and Practical Synchronous State Machine Replication.” https://ieeexplore.ieee.org/document/9152792/.