Introduction

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(n2)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)O(n) messages instead of O(n2)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.

Pipeline the Phases

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

<!-- HotStuff pipeline demo — three-phase BFT consensus visualization -->
<div class="hs-wrap">
  <p class="hint">Each round, a new block enters at <b>Prepare</b> and every active block advances one phase. A block is <b>committed</b> (finalized) only after three consecutive certified phases. Click <b>Next round</b> to step through the pipeline.</p>
  <div id="pipeline" class="pipeline"></div>
  <div class="controls">
    <button id="btn-next" type="button">Next round →</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div id="status" class="status"></div>
</div>

/* Styles for the HotStuff pipeline demo */
* { 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; }

/* Pipeline grid: rows = phases, columns = blocks */
.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; }

/* Individual pipeline cell styling */
.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; }

/* Color-coding by phase: blue=prepare, yellow=precommit, green=commit/done */
.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; }

/* Arrow between cells and status message */
.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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// HotStuff pipelined BFT consensus demo.
// Three phases: Prepare, Pre-Commit, Commit. A block is committed
// once all three phases complete (the three-chain rule).

// Internal phase identifiers (not shown to user)
const PHASES = ['prepare', 'precommit', 'commit'];
const PHASE_LABELS = { prepare: 'Prepare', precommit: 'Pre-Commit', commit: 'Commit' };

// Pipeline configuration: total blocks and lane count
const TOTAL_BLOCKS = 5;
const ROWS = 3; // one lane per phase

// Global simulation state
// step = number of "next block" clicks fired so far
let step = 0;

// Phase index per block: -1=not started, 0=prepare, 1=precommit, 2=commit, 3=done
// pipelinePhase[i] = index into PHASES for block i (0=prepare,1=precommit,2=commit,3=done)
// -1 = not yet entered pipeline
const pipelinePhase = Array(TOTAL_BLOCKS).fill(-1);

// Set of block indices that have been fully committed
const committed = new Set();

function advance() {
  // Advance all in-flight blocks by one phase; introduce a new block each step
  // Each click introduces one new block into the pipeline and advances all active blocks by one phase.
  // Block i enters on step i+1 (so block 0 on step 1, block 1 on step 2, ...).
  for (let i = 0; i < TOTAL_BLOCKS; i++) {
    if (step >= i + 1 && pipelinePhase[i] < 3) {
      pipelinePhase[i]++;
      if (pipelinePhase[i] === 3) committed.add(i);
    }
  }
}

function phaseClass(p) {
  // Map phase index to CSS class name for color-coding
  if (p === -1) return 'empty';
  if (p === 0) return 'prepare';
  if (p === 1) return 'precommit';
  if (p === 2) return 'commit';
  return 'done';
}

function phaseLabel(p) {
  if (p === -1) return '';
  if (p === 3) return '✓ done';
  return PHASE_LABELS[PHASES[p]];
}

function render() {
  const container = document.getElementById('pipeline');
  container.innerHTML = '';

  // Build the grid: one row per pipeline phase lane
  // Row k shows blocks whose pipeline phase == k (i.e., which "lane" they are in).
  // We render one row per phase lane, labeling it with the phase name.
  for (let lane = 0; lane < ROWS; lane++) {
    const row = document.createElement('div');
    row.className = 'row';

    const lbl = document.createElement('div');
    lbl.className = 'row-label';
    lbl.textContent = PHASE_LABELS[PHASES[lane]];
    row.appendChild(lbl);

    // Render each block's cell in this lane
    for (let i = 0; i < TOTAL_BLOCKS; i++) {
      if (i > 0) {
        const arr = document.createElement('span');
        arr.className = 'arrow';
        arr.textContent = '→';
        row.appendChild(arr);
      }
      const cell = document.createElement('div');
      const p = pipelinePhase[i];
      // Highlight a block only in its current active lane
      // A block is "active" in this lane if it is currently at that pipeline phase.
      const activeInLane = (p === lane);
      const isCommitted = (p === 3);
      if (activeInLane) {
        cell.className = 'cell ' + phaseClass(p);
      } else if (isCommitted && lane === ROWS - 1) {
        cell.className = 'cell done';
      } else {
        cell.className = 'cell empty';
      }
      cell.innerHTML = '<span class="blk">B' + (i + 1) + '</span>' +
        '<span class="phase">' + (activeInLane ? PHASE_LABELS[PHASES[lane]] : (isCommitted && lane === ROWS - 1 ? '✓ done' : '')) + '</span>';
      row.appendChild(cell);
    }
    container.appendChild(row);
  }
}

function updateStatus() {
  const s = document.getElementById('status');
  const btn = document.getElementById('btn-next');
  if (step === 0) {
    s.textContent = 'Press "Next round" to introduce the first block.';
    s.className = 'status';
  } else if (committed.size > 0) {
    const list = [...committed].map(i => 'B' + (i + 1)).join(', ');
    s.textContent = fmt('Committed: %list% — finalized by the three-chain rule!', { list: list });
    s.className = 'status commit-msg';
  } else {
    s.textContent = fmt('Round %step% — blocks advancing through the pipeline.', { step: step });
    s.className = 'status';
  }
  if (step >= TOTAL_BLOCKS + 2) {
    btn.disabled = true;
    btn.textContent = 'Pipeline full';
  }
}

document.getElementById('btn-next').addEventListener('click', () => {
  if (step < TOTAL_BLOCKS + 2) {
    step++;
    advance();
    render();
    updateStatus();
  }
});

document.getElementById('btn-reset').addEventListener('click', () => {
  step = 0;
  pipelinePhase.fill(-1);
  committed.clear();
  document.getElementById('btn-next').disabled = false;
  document.getElementById('btn-next').textContent = 'Next round →';
  render();
  updateStatus();
});

// Initialize the display on page load
render();
updateStatus();
Result
Console

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

The Real Complexity

BFT consensus in a network of nn replicas can tolerate up to f<n/3f < n/3 Byzantine faults. The classical protocol PBFT (Castro & Liskov, 1999) achieves this but requires O(n2)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)O(n) messages (one vote per replica), not O(n2)O(n^2). This is safe because threshold signatures let n−fn - 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 bb is committed when there exist three consecutive certified blocks b←b′←b′′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′′b'' simultaneously acts as the Pre-Commit QC for b′b' and the Commit QC for bb.

The result: view-change cost drops from O(n2)O(n^2) to O(n)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.

Where It Matters

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.

Conclusion

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(n2)O(n^2) traffic storm into a lean O(n)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hotstuff/Content licensed under CC BY-NC 4.0.