HotStuff

Imagine a network of servers that must all agree on a single value — even if some of them are actively lying or sending conflicting messages. This is Byzantine fault tolerance (BFT): agreement in the face of arbitrary failure.

Classical BFT protocols solved the problem, but they were expensive. Every time a round stalled — because the leader crashed or misbehaved — the protocol had to broadcast $O(n^2)$ messages just to replace the leader. With hundreds of nodes, that is a traffic explosion.

HotStuff, published in 2018 by Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta and Ittai Abraham, made a key insight: by adding one extra voting phase and chaining rounds together into a pipeline, you can change leaders with only $O(n)$ messages instead of $O(n^2)$. The result is a protocol that is simultaneously safe, live, responsive — and cheap enough to power real blockchains.

DiemBFT (the consensus layer of Meta's Diem blockchain), Aptos, and several other production systems are direct descendants of HotStuff.

Each HotStuff round passes a block through three consecutive voting phases: Prepare, Pre-Commit, and Commit. A block is finalized only once all three phases succeed for it — forming a chain of three consecutive certified blocks (the three-chain rule).

<!-- {{c_html_intro}} -->
<div class="hs-wrap">
  <p class="hint">{{hint_para}}</p>
  <div id="pipeline" class="pipeline"></div>
  <div class="controls">
    <button id="btn-next" type="button">{{btn_next}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div id="status" class="status"></div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hs-wrap { padding: .5rem; max-width: 680px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }

/* {{c_pipeline_grid}} */
.pipeline { display: flex; flex-direction: column; gap: 6px; margin-bottom: .7rem; }
.row { display: flex; align-items: center; gap: 0; }
.row-label { width: 80px; font-size: .78rem; font-weight: 700; color: #555; flex-shrink: 0; }

/* {{c_phase_cell}} */
.cell {
  width: 68px; height: 52px; border-radius: 8px; border: 1.5px solid #cdd9e3;
  display: flex; flex-direction: column; align-items: center; justify-content: center;
  font-size: .7rem; font-weight: 600; transition: background .25s, border-color .25s;
  background: #f0f4f8; color: #667; cursor: default; flex-shrink: 0; position: relative;
}
.cell + .cell { margin-left: 4px; }
.cell .blk { font-size: .85rem; font-weight: 800; color: #1d3557; }
.cell .phase { font-size: .62rem; text-transform: uppercase; letter-spacing: .04em; margin-top: 2px; }

/* {{c_phase_colors}} */
.cell.prepare  { background: #dbeafe; border-color: #3b82f6; color: #1d3557; }
.cell.precommit { background: #fef9c3; border-color: #eab308; color: #713f12; }
.cell.commit   { background: #dcfce7; border-color: #22c55e; color: #14532d; }
.cell.done     { background: #bbf7d0; border-color: #16a34a; color: #14532d; opacity: .75; }
.cell.empty    { background: #f8f9fa; border-color: #e2e8f0; color: #aaa; }

/* {{c_arrow_style}} */
.arrow { font-size: 1.1rem; color: #94a3b8; padding: 0 1px; flex-shrink: 0; }
.status { font-size: .92rem; font-weight: 600; min-height: 1.3em; color: #1d3557; }
.status.commit-msg { color: #15803d; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1.5px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

The key insight is pipelining: the Prepare vote for block $k+1$ doubles as the Pre-Commit vote for block $k$ and the Commit vote for block $k-1$. Each new block advances the entire pipeline by one step, so the throughput stays linear even as the chain grows.

BFT consensus in a network of $n$ replicas can tolerate up to $f < n/3$ Byzantine faults. The classical protocol PBFT (Castro & Liskov, 1999) achieves this but requires $O(n^2)$ messages during a view-change — the procedure that replaces a faulty leader.

HotStuff's breakthroughs:

• One extra phase. Classical two-phase BFT conflates "did a quorum vote?" and "does a quorum know a quorum voted?" HotStuff separates these into three phases (Prepare, Pre-Commit, Commit), which makes each phase's logic identical and simple to pipeline.
• Linear view-change. When a leader is replaced, the new leader collects only $O(n)$ messages (one vote per replica), not $O(n^2)$. This is safe because threshold signatures let $n - f$ partial signatures be combined into one small certificate that proves a quorum agreed.
• Responsiveness. After a period of synchrony, the protocol advances as fast as actual network delay, not a worst-case timer. This is called optimistic responsiveness.
• The three-chain commit rule. A block $b$ is committed when there exist three consecutive certified blocks $b \leftarrow b' \leftarrow b''$ in the chain. This elegant rule is what allows the three phases to be pipelined — the Prepare QC for $b''$ simultaneously acts as the Pre-Commit QC for $b'$ and the Commit QC for $b$.

The result: view-change cost drops from $O(n^2)$ to $O(n)$, making HotStuff practical for networks with hundreds or thousands of validators.

For contrast, see how Byzantine agreement and consensus relate to the broader limits of distributed computation.

HotStuff's linear complexity is not just theoretical elegance — it enables a new class of practical BFT systems:

• DiemBFT / LibraBFT: Meta's Diem blockchain (formerly Libra) adopted HotStuff as its core consensus engine. DiemBFT added pacemaker logic and explicit liveness proofs on top of the basic protocol.
• Aptos: Aptos, built by former Diem engineers, uses AptosBFT — a direct HotStuff descendant — to run a validator network with sub-second finality.
• Flow blockchain: uses a variant of HotStuff to achieve high throughput for NFT and gaming applications.
• Academic BFT research: HotStuff became a reference point for a generation of follow-on protocols (Fast-HotStuff, Jolteon, Bullshark) that push latency and throughput further.
• Permissioned enterprise blockchains: any setting that needs deterministic finality (banks, supply-chain networks) benefits from HotStuff's tight safety guarantees.

Understanding HotStuff means understanding why distributed agreement is hard and how a clean abstraction — the linear pipeline — can make an intractable-looking problem manageable at scale.

HotStuff is a masterclass in protocol design: by adding one extra voting phase and chaining rounds into a pipeline, it transformed Byzantine fault-tolerant consensus from a $O(n^2)$ traffic storm into a lean $O(n)$ heartbeat.

The three-chain commit rule is the central idea. It separates the notions of "a quorum voted" and "a quorum knows a quorum voted" into three clean phases — and the pipeline makes those phases overlap so that throughput never stalls.

Every time you finalize a transaction on Aptos or another HotStuff-based chain, you are benefiting from that insight: distributed agreement does not have to be expensive. It just needs the right structure.