PBFT

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(n^2)$ messages per request, efficient enough to run under real workloads. Their key insight: you need at least $3f+1$ replicas to tolerate $f$ 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).

Below is a minimal PBFT simulation with 4 replicas ($3 \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.

<!-- {{c_html_comment}} -->
<div class="hint">{{hint_para}}</div>
<div class="controls">
  <label class="phase-label">{{phase_label}}: <span id="phase-name" class="phase-badge">{{phase_idle}}</span></label>
  <div class="btn-row">
    <button id="btn-step" type="button">{{btn_step}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div class="net" id="network">
  <!-- {{c_nodes_rendered}} -->
</div>
<div class="log" id="log">
  <div class="log-title">{{log_title}}</div>
  <div id="log-entries"></div>
</div>

/* {{c_css_comment}} */
* { 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; }

// Code not found

Notice what the quorum counting does: each phase requires $2f+1$ matching messages ($f = 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.

How expensive is Byzantine consensus, really?

• Message cost: each phase broadcasts to all replicas. With $n$ replicas, the prepare and commit phases each cost $O(n^2)$ messages. That is optimal — no Byzantine protocol can do better in the worst case.
• The $3f+1$ lower bound: Lamport, Shostak and Pease (1982) proved that $n \geq 3f+1$ is necessary — you cannot tolerate $f$ Byzantine faults with fewer replicas. Intuitively, if you only had $3f$ nodes, the $f$ traitors could partition the $2f$ honest nodes into two groups of $f$ 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(n^2)$ round but preserves safety.

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

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(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+1$ threshold.
• Satellite and aerospace: space-rated computers use voting logic to mask arbitrary faults, a hardware instantiation of the same $3f+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.

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