Introduction

Imagine a small committee of servers that must all agree on a single answer — say, whether to commit a database transaction. Simple majority vote works as long as everyone is honest. But what if one server is compromised, sending contradictory messages to different peers? A simple majority breaks down fast.

This is the Byzantine Generals Problem: a set of nodes must reach a common decision even when some of them behave arbitrarily — lying, staying silent, or colluding. Named after the classic puzzle of generals who must coordinate an attack while some may be traitors, it was formalized by Lamport, Shostak and Pease in 1982.

For decades the problem was considered too expensive for real systems. Then in 1999 Miguel Castro and Barbara Liskov published Practical Byzantine Fault Tolerance (PBFT) — a protocol that achieves consensus in O(n2)O(n^2) messages per request, efficient enough to run under real workloads. Their key insight: you need at least 3f+13f+1 replicas to tolerate ff Byzantine (arbitrarily faulty) nodes, and three carefully designed phases are enough to guarantee both safety (all honest nodes agree) and liveness (the system keeps making progress).

Try It

Below is a minimal PBFT simulation with 4 replicas (3⋅1+13 \cdot 1 + 1, so it can tolerate 1 traitor). The primary broadcasts a request, and the three phases — PRE-PREPARE, PREPARE, and COMMIT — unfold one step at a time. Toggle Byzantine on any replica to watch it send a conflicting message, then see whether the honest nodes still reach agreement.

<!-- PBFT demo layout: controls, node grid, event log. -->
<div class="hint">4 replicas tolerate 1 Byzantine (lying) node — that is the 3f+1 = 4 minimum. Click <b>Step</b> to advance through PRE-PREPARE → PREPARE → COMMIT. Toggle <b>Byzantine</b> on a non-primary replica to make it send a wrong value, then watch the quorum still agree.</div>
<div class="controls">
  <label class="phase-label">Phase: <span id="phase-name" class="phase-badge">Idle</span></label>
  <div class="btn-row">
    <button id="btn-step" type="button">Step</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
</div>
<div class="net" id="network">
  <!-- Replica nodes are injected here by JavaScript. -->
</div>
<div class="log" id="log">
  <div class="log-title">Event log</div>
  <div id="log-entries"></div>
</div>

/* PBFT demo styles: nodes, phases, badges, log. */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin-bottom: .7rem; line-height: 1.5; }
.controls { display: flex; flex-direction: column; gap: .45rem; margin-bottom: .8rem; }
.phase-label { font-weight: 600; font-size: .9rem; }
.phase-badge { display: inline-block; padding: .15rem .55rem; border-radius: 12px;
               background: #e8eef3; color: #1d3557; font-size: .82rem; margin-left: .3rem; }
.phase-badge.pre  { background: #dbeafe; color: #1e40af; }
.phase-badge.prep { background: #fef9c3; color: #854d0e; }
.phase-badge.comm { background: #dcfce7; color: #166534; }
.phase-badge.done { background: #f3e8ff; color: #6b21a8; }
.btn-row { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.net { display: flex; gap: 10px; flex-wrap: wrap; margin-bottom: .9rem; }
.node { width: 120px; border: 2px solid #cdd9e3; border-radius: 10px; padding: 8px;
        background: #f8fafc; display: flex; flex-direction: column; gap: 5px; }
.node.primary { border-color: #1d3557; }
.node.byzantine { border-color: #e63946; background: #fff5f5; }
.node.decided { background: #f0fdf4; border-color: #16a34a; }
.node-title { font-weight: 700; font-size: .85rem; display: flex; align-items: center; gap: 4px; }
.node-title .badge { font-size: .68rem; padding: .1rem .35rem; border-radius: 8px;
                     background: #e8eef3; color: #444; font-weight: 600; }
.node-title .badge.primary-badge { background: #dbeafe; color: #1e40af; }
.node-title .badge.byz-badge { background: #fee2e2; color: #991b1b; }
.node-title .badge.decided-badge { background: #dcfce7; color: #166534; }
.byz-toggle { display: flex; align-items: center; gap: 4px; font-size: .76rem; color: #555; cursor: pointer; }
.byz-toggle input { accent-color: #e63946; cursor: pointer; }
.node-inbox { font-size: .75rem; color: #555; min-height: 28px; line-height: 1.4; }
.node-inbox span { display: block; }
.msg-pre  { color: #1e40af; }
.msg-prep { color: #854d0e; }
.msg-comm { color: #166534; }
.msg-byz  { color: #991b1b; font-style: italic; }
.log { border: 1px solid #cdd9e3; border-radius: 8px; padding: 8px 10px; max-height: 120px;
       overflow-y: auto; background: #f8fafc; }
.log-title { font-weight: 700; font-size: .8rem; color: #555; margin-bottom: 4px; }
.log-entry { font-size: .78rem; color: #333; border-bottom: 1px solid #eef0f2; padding: 2px 0; }
.log-entry.ok  { color: #166534; }
.log-entry.err { color: #991b1b; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// PBFT simulation: 4 replicas, f=1 Byzantine fault tolerance.
// Three phases: PRE-PREPARE (primary broadcasts), PREPARE (all-to-all), COMMIT (quorum commits).

// Replica descriptors. isPrimary = the view leader.
const REPLICAS = [
  { id: 0, label: 'R0', isPrimary: true,  byzantine: false },
  { id: 1, label: 'R1', isPrimary: false, byzantine: false },
  { id: 2, label: 'R2', isPrimary: false, byzantine: false },
  { id: 3, label: 'R3', isPrimary: false, byzantine: false }
];
const F = 1; // number of tolerated Byzantine faults
const QUORUM = 2 * F + 1; // 2f+1 matching messages needed to proceed

// Protocol phases in order.
const PHASES = ['idle', 'pre-prepare', 'prepare', 'commit', 'done'];
const VALUE = 'COMMIT:TX-42'; // the correct value the primary proposes
const BYZ_VALUE = 'COMMIT:TX-99'; // conflicting value a Byzantine replica sends

let phaseIdx = 0;
// inbox[id] = list of messages received by replica id
let inbox = {};
// decided[id] = value decided by replica id, or null
let decided = {};

function byzNode() {
  return REPLICAS.find(r => r.byzantine && !r.isPrimary) || null;
}

function resetState() {
  phaseIdx = 0;
  inbox = {};
  decided = {};
  REPLICAS.forEach(r => { inbox[r.id] = []; decided[r.id] = null; });
}

// Re-render all replica boxes.
function render() {
  const net = document.getElementById('network');
  net.innerHTML = '';
  REPLICAS.forEach(r => {
    const div = document.createElement('div');
    const isByz = r.byzantine;
    const isDec = decided[r.id] !== null;
    div.className = 'node' + (r.isPrimary ? ' primary' : '') +
                    (isByz ? ' byzantine' : '') + (isDec ? ' decided' : '');

    // Build status badge HTML.
    let badgeHtml = '';
    if (r.isPrimary) badgeHtml = `<span class="badge primary-badge">primary</span>`;
    if (isByz) badgeHtml += `<span class="badge byz-badge">Byzantine</span>`;
    if (isDec) badgeHtml += `<span class="badge decided-badge">decided</span>`;

    // Byzantine toggle checkbox — only non-primary replicas can be toggled
    const toggleHtml = !r.isPrimary ? "\n      " + fmt(`<label class="byz-toggle">
        <input type="checkbox" data-id="%id%" %v%> Byzantine
      </label>`, { id: r.id, v: isByz ? 'checked' : '' }) : '';

    // Render inbox messages with phase-coloring.
    const msgs = inbox[r.id].map(m => {
      const cls = m.type === 'pre-prepare' ? 'msg-pre' :
                  m.type === 'prepare'     ? 'msg-prep' :
                  m.type === 'commit'      ? 'msg-comm' : 'msg-byz';
      return `<span class="${cls}">${m.from}: [${m.type}] ${m.value}</span>`;
    }).join('');

    div.innerHTML = `
      <div class="node-title">${r.label} ${badgeHtml}</div>
      ${toggleHtml}
      <div class="node-inbox">${msgs || '<span style="color:#aaa">no messages</span>'}</div>
    `;
    net.appendChild(div);
  });

  // Update the phase badge at the top.
  const ph = PHASES[phaseIdx];
  const badge = document.getElementById('phase-name');
  badge.textContent = phaseLabel(ph);
  badge.className = 'phase-badge ' +
    (ph === 'pre-prepare' ? 'pre' : ph === 'prepare' ? 'prep' :
     ph === 'commit' ? 'comm' : ph === 'done' ? 'done' : '');

  // Wire up Byzantine toggle checkboxes after render.
  net.querySelectorAll('input[data-id]').forEach(cb => {
    cb.addEventListener('change', e => {
      const id = parseInt(e.target.dataset.id);
      REPLICAS[id].byzantine = e.target.checked;
      render();
    });
  });
}

function phaseLabel(ph) {
  if (ph === 'idle')        return `Idle`;
  if (ph === 'pre-prepare') return 'PRE-PREPARE';
  if (ph === 'prepare')     return 'PREPARE';
  if (ph === 'commit')      return 'COMMIT';
  if (ph === 'done')        return `Decided`;
  return ph;
}

function addLog(msg, cls) {
  const el = document.getElementById('log-entries');
  const d = document.createElement('div');
  d.className = 'log-entry ' + (cls || '');
  d.textContent = msg;
  el.appendChild(d);
  el.scrollTop = el.scrollHeight;
}

// Advance one protocol phase and deliver the relevant messages.
function step() {
  if (phaseIdx >= PHASES.length - 1) { addLog(`Already decided. Click Reset to start over.`); return; }
  phaseIdx++;
  const ph = PHASES[phaseIdx];

  if (ph === 'pre-prepare') {
    // PRIMARY broadcasts PRE-PREPARE to all non-primary replicas.
    REPLICAS.forEach(r => {
      if (!r.isPrimary) {
        inbox[r.id].push({ from: 'R0', type: 'pre-prepare', value: VALUE });
      }
    });
    addLog(`PRE-PREPARE: primary (R0) broadcasts value to all replicas.`);

  } else if (ph === 'prepare') {
    // All replicas (including primary) send PREPARE to every replica.
    REPLICAS.forEach(sender => {
      const val = sender.byzantine ? BYZ_VALUE : VALUE;
      REPLICAS.forEach(r => {
        inbox[r.id].push({ from: sender.label, type: 'prepare', value: val });
      });
    });
    addLog(`PREPARE: each non-primary replica broadcasts its prepare (Byzantine replica sends wrong value).`);

  } else if (ph === 'commit') {
    // Replicas that have 2f+1 matching PREPAREs send COMMIT.
    REPLICAS.forEach(r => {
      const matching = inbox[r.id].filter(m => m.type === 'prepare' && m.value === VALUE);
      if (matching.length >= QUORUM) {
        REPLICAS.forEach(r2 => {
          inbox[r2.id].push({ from: r.label, type: 'commit', value: VALUE });
        });
      }
    });
    addLog(`COMMIT: replicas that collected 3 matching PREPARE messages broadcast commit.`);

  } else if (ph === 'done') {
    // Replicas that have 2f+1 matching COMMITs decide.
    let agreedCount = 0;
    REPLICAS.forEach(r => {
      const matching = inbox[r.id].filter(m => m.type === 'commit' && m.value === VALUE);
      if (matching.length >= QUORUM) {
        decided[r.id] = VALUE;
        agreedCount++;
      }
    });
    if (agreedCount >= QUORUM) {
      addLog(fmt(`DECIDED:  %agreedCount% replicas agreed on the correct value.`, { agreedCount: agreedCount }), 'ok');
    } else {
      addLog(`No agreement reached (too many Byzantine nodes).`, 'err');
    }
  }
  render();
}

document.getElementById('btn-step').addEventListener('click', step);
document.getElementById('btn-reset').addEventListener('click', () => {
  resetState();
  render();
  document.getElementById('log-entries').innerHTML = '';
  addLog(`Reset. Toggle Byzantine on a replica and step through again.`);
});

resetState();
render();
addLog(`Ready. Click Step to begin the PRE-PREPARE phase.`);
Result
Console

Notice what the quorum counting does: each phase requires 2f+12f+1 matching messages (f=1f = 1, so 3 matching messages). Even when the traitor sends a lie, the three honest nodes still accumulate enough identical messages to commit the same value.

The Real Complexity

How expensive is Byzantine consensus, really?

  • Message cost: each phase broadcasts to all replicas. With nn replicas, the prepare and commit phases each cost O(n2)O(n^2) messages. That is optimal — no Byzantine protocol can do better in the worst case.
  • The 3f+13f+1 lower bound: Lamport, Shostak and Pease (1982) proved that n≥3f+1n \geq 3f+1 is necessary — you cannot tolerate ff Byzantine faults with fewer replicas. Intuitively, if you only had 3f3f nodes, the ff traitors could partition the 2f2f honest nodes into two groups of ff each and fool them into disagreeing. PBFT meets this bound exactly.
  • Safety and liveness: PBFT guarantees safety unconditionally (honest replicas never disagree) but only guarantees liveness under a weak synchrony assumption — message delays are eventually bounded. In a fully asynchronous network, the FLP impossibility theorem says no deterministic protocol can guarantee both simultaneously.
  • View changes: when the primary is suspected of being Byzantine, replicas trigger a view change to elect a new primary. This adds another O(n2)O(n^2) round but preserves safety.

PBFT was a landmark because it brought the theoretical 3f+13f+1 bound into a real system running at practical throughput — previously considered impossible without cryptographic assumptions beyond message authentication.

Where It Matters

Any system where nodes could be compromised — not just crash — needs Byzantine fault tolerance, and PBFT's ideas show up everywhere:

  • Permissioned blockchains: Hyperledger Fabric's ordering service and Tendermint both derive from PBFT's three-phase structure. They swap the O(n2)O(n^2) all-to-all broadcast for leader-based variants to scale to more replicas.
  • Cloud and storage systems: Google Spanner's Paxos variant and replicated state machines in data centers use crash fault tolerance (CFT), but when the threat model includes compromised nodes — e.g. multi-cloud or cross-organization deployments — BFT variants step in.
  • Secure multi-party computation: threshold protocols that split secrets across parties use quorum counting arguments identical to PBFT's 2f+12f+1 threshold.
  • Satellite and aerospace: space-rated computers use voting logic to mask arbitrary faults, a hardware instantiation of the same 3f+13f+1 principle.

PBFT directly influenced Nash equilibrium reasoning in mechanism design — Byzantine nodes are strategic agents, and the protocol's quorum threshold is an equilibrium where rational traitors cannot gain by deviating. Understanding PBFT is understanding how trust is engineered, not assumed.

Conclusion

PBFT does something remarkable: it takes a problem that was considered practically unsolvable — reaching agreement when some participants actively lie — and solves it with three rounds of messages and careful quorum counting. The bound n≥3f+1n \geq 3f+1 is not a design choice; it is a mathematical wall, proven tight by Lamport, Shostak and Pease.

The next time you trust a permissioned blockchain, a replicated database, or a safety-critical control system, remember that somewhere underneath it three phases of messages are being exchanged, votes are being tallied, and the honest nodes are quietly outvoting the liars — exactly as Castro and Liskov proved they could in 1999.

For the open question of whether Byzantine agreement can be achieved efficiently under full asynchrony without randomness, see the ongoing line of work descending from the FLP impossibility result.

Share this article

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

Comments

Loading comments...

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