IM Engineer Study Notes
← Back to list
Computing & Embedded
#비잔틴장애#BFT#PBFT#분산합의#3f+1
Last updated · 2026-10-27

Byzantine Fault Tolerance (BFT) and PBFT

1. Overview

A. Definition

Byzantine Fault Tolerance (BFT) is the ability of a distributed system to have its honest nodes reach consensus on a single correct value and keep operating consistently, even when some nodes go beyond merely stopping and instead send arbitrarily wrong, conflicting, or malicious messages (a Byzantine fault). PBFT (Practical Byzantine Fault Tolerance), proposed by Castro and Liskov in 1999, is the representative algorithm that achieves Byzantine consensus with practical performance under a partial-synchrony assumption.

BFT is the strongest form of distributed consensus. The crash faults handled by Paxos and Raft assume that a node "only dies or slows down, but never lies," whereas BFT also assumes an adversarial fault model in which "a node may be hacked and send different values to different nodes, attempt forged signatures, or subtly violate the protocol." This is why BFT has become a core foundational technology underpinning the safety of untrusted (permissionless, adversarial) environments—public blockchains, multi-party financial settlement networks, and aerospace control systems.

B. Background and Necessity

The theoretical root of BFT is the Byzantine Generals Problem, formalized by Lamport, Shostak, and Pease in 1982. Several generals each lead their troops surrounding an enemy castle and must all identically choose between "attack" and "retreat," communicating only through messengers (messages), while some generals are traitors who may leak false orders. It is a thought experiment asking whether the loyal generals can always reach the same decision, abstracting the question in distributed systems of "whether consensus is possible even with lying nodes mixed in." The paper mathematically proved that with oral (unsigned) messages alone, tolerating even a single traitor requires the total number of generals to be at least three times plus one—that is, the 3f+1 condition.

Why this matters in practice is clear. The Paxos and Raft family, which assume only simple faults, lose safety in the face of an attack where a single node maliciously sends contradictory logs to different followers. In domains such as financial settlement, electronic voting, and aviation control—where a single wrong consensus is catastrophic—the optimistic premise that "nodes do not lie" cannot be used. In particular, after Bitcoin in 2008, the demand for mutually distrusting anonymous participants to agree on ledger state without a central administrator exploded, elevating Byzantine consensus from an academic hard problem to an industrial necessity.

That said, early BFT algorithms were blocked by the wall of being "theoretically possible but practically unviable in performance." PBFT broke through exactly this point. By introducing partial synchrony (a weak assumption that there is an upper bound on message delay) rather than full asynchrony, and by lowering the number of message exchanges from exponential to polynomial, it demonstrated throughput applicable to a real file system (BFS), earning the name "Practical."

C. Core Properties Guaranteed by BFT

  • Agreement: Every honest node executes the same request at the same sequence number. Even if Byzantine nodes spread different values, cross-verification filters them out.
  • Total Order: Requests are applied in the same order at all honest nodes, so the state of the replicated state machine does not diverge.
  • Integrity: Only requests from honest clients are executed, exactly once (blocking forgery and replay attacks).
  • External consistency (Linearizability): From the client's perspective, the system responds like a single correct server.
  • Liveness: When the network stabilizes (partial synchrony), honest requests are always processed—though this is guaranteed subordinate to safety.

2. Characteristics of Byzantine Faults and the Quorum Principle

The fundamental difference between a Byzantine fault and a crash fault is that there is no constraint on the behavior of a faulty node. A crash-faulty node exhibits only one failure mode—"not responding"—so the remaining nodes can trust that "a value that was answered is honest." A Byzantine node, by contrast, may respond but with false content, and may even perform equivocation—sending different values to different recipients. Therefore, instead of "trusting an incoming value," BFT adopts a multi-verification structure of "trusting only a value that sufficiently many nodes attest to identically."

The core of this structure is the 3f+1 quorum principle. To preserve safety when at most f of the total N nodes are Byzantine, N ≥ 3f+1 must hold. Intuitively, the quorum needed for consensus is 2f+1, which simultaneously satisfies two things. First, even if f Byzantine nodes refuse to respond, a quorum can be filled with f+1 of the 2f+1 normal nodes, so progress (liveness) is guaranteed. Second, any two distinct quorums (each 2f+1) necessarily overlap in at least f+1 nodes within N=3f+1, and since that intersection contains at least one honest node, two contradictory decisions being finalized at once is fundamentally blocked, so safety is preserved. For example, f=1 requires at least 4 nodes and f=2 requires 7 nodes, which demands more redundancy than the 2f+1 of crash faults (3 nodes for f=1).

flowchart TB
    subgraph CFT["Crash Fault Tolerance (CFT, N=2f+1)"]
      direction TB
      C1["Normal node"] --- C2["Normal node"]
      C2 --- C3["Silent (stopped) node"]
      CNOTE["Assumption: nodes only stop, never lie"]
    end
    subgraph BFT["Byzantine Fault Tolerance (BFT, N=3f+1)"]
      direction TB
      B1["Normal node"] --- B2["Normal node"]
      B2 --- B3["Normal node"]
      B3 --- B4["Malicious node (equivocation)"]
      BNOTE["Assumption: nodes may send false, conflicting messages"]
    end
    CFT -->|"Strengthened threat model"| BFT

The figure above shows that even to tolerate the same f=1, CFT needs 3 nodes while BFT needs 4. The one added replica is the cost of preparing for the "possibility of lying," and for this reason BFT carries a fundamental trade-off: it provides stronger safety in exchange for a larger node count, message cost, and latency. The branch point for choosing low-cost CFT inside a trust domain (an in-house data center) versus BFT in a mutually distrusting environment (a public blockchain) is divided right here.

Meanwhile, the original Byzantine Generals paper left an important insight that the presence or absence of message authentication (signatures) changes the fault-tolerance bound. In the unsigned oral message model, a traitor can say "attack to A, retreat to B" with no way to trace it afterward, so 3f+1 is strictly required. But if an unforgeable digital signature is attached to a message, then if a traitor alters the content in transit the signature breaks and is immediately detected, so in theory consensus becomes possible with fewer nodes. Precisely for this reason, modern BFT including PBFT attaches a signature or MAC to every protocol message without exception, and the signature is simultaneously BFT's "lie-detection device" and a performance bottleneck. However, signatures cannot prevent equivocation—an attack where the same signer attaches a legitimate signature to each of two different messages—so quorum-based vote cross-verification via 3f+1 still remains the core safeguard.

Another axis that must be distinguished in BFT design is Safety versus Liveness. Safety means "two distinct honest nodes never finalize different values at the same sequence number" (nothing bad ever happens), and liveness means "a request is eventually processed for sure" (something good eventually happens). By the FLP impossibility theorem, the two cannot be guaranteed deterministically at once in a fully asynchronous environment, so PBFT adopted a design that never sacrifices safety under any circumstance and entrusts only liveness to the partial-synchrony assumption (that a message-delay upper bound exists). In other words, if the network is extremely unstable, PBFT may halt (loss of liveness) but never makes a contradictory decision (safety preserved). This "safety-first" philosophy is the fundamental principle that makes BFT trustworthy in domains such as finance and control where wrong consensus is catastrophic.

3. PBFT's Three-Phase Consensus Protocol

PBFT divides nodes into a primary (leader) and backups, and in a given configuration (view), the primary proposes the order of requests while the backups cross-verify and finalize it. Consensus in the normal-case interval is carried out by a three-phase message exchange of Pre-prepare → Prepare → Commit, and each phase accumulates evidence that "a sufficient number of nodes saw the same content." The guarantees secured by each phase can be summarized at a glance as follows.

  • Pre-prepare: The primary proposes a sequence number (n) → fixes the candidate for "the request in slot n in this view."
  • Prepare (collect 2f+1): Guarantees that no different request can be prepared at the same view and sequence number (first-order ordering agreement within the same view).
  • Commit (collect 2f+1): Guarantees that the decision is retained even after a view change (cross-view finality) → execute and respond.

A. Pre-prepare. The primary that received a client request assigns a sequence number n to that request and broadcasts it to all backups, signed together with the current view v and the request digest. The purpose of this phase is to fix an ordering proposal that "in this view, slot n holds this request." A backup accepts it after verifying the validity of the signature, view, and sequence-number range. Even if the primary is malicious, the cross-verification in the next phase filters out contradictions.

B. Prepare. Each backup that accepted the Pre-prepare broadcasts a Prepare message for the same ⟨v, n, digest⟩ to all nodes along with its own signature. When a node, including itself, collects 2f+1 matching Prepares (signed by distinct nodes), it reaches the "prepared state." When this condition holds, it is guaranteed that among honest nodes no different request can be prepared at the same view and the same sequence number. That is, the Prepare phase secures a "first-order agreement on ordering," but it does not yet guarantee whether this decision survives even if the view changes.

C. Commit. A node that reached prepared also broadcasts a Commit message to all, and when it collects 2f+1 matching Commits it enters the "committed-local" state, executes the request on the replicated state machine, and then responds to the client. The client trusts the result when it receives f+1 identical responses from distinct nodes (since at least one of the f+1 is honest). The reason the Commit phase is additionally needed is that with Prepare alone the decision could be overturned upon a view change. Commit confers finality that "this decision is retained even if the view changes."

sequenceDiagram
    participant C as Client
    participant P as Primary (node0)
    participant B1 as Backup1
    participant B2 as Backup2
    participant B3 as Backup3 (may fail)
    C->>P: request
    Note over P,B3: 1) Pre-prepare phase
    P->>B1: Pre-prepare(v,n,digest)
    P->>B2: Pre-prepare(v,n,digest)
    P->>B3: Pre-prepare(v,n,digest)
    Note over P,B3: 2) Prepare phase (collect 2f+1)
    B1->>P: Prepare
    B1->>B2: Prepare
    B2->>P: Prepare
    B2->>B1: Prepare
    Note over P,B3: 3) Commit phase (collect 2f+1)
    P->>B1: Commit
    B1->>B2: Commit
    B2->>P: Commit
    Note over P,B2: reaches committed-local → execute
    P-->>C: response
    B1-->>C: response
    B2-->>C: response (trusted upon receiving f+1 identical)

D. Checkpoints and Garbage Collection. As consensus accumulates, the message log each node retains grows without bound, so PBFT creates a checkpoint at certain sequence numbers to share a state snapshot and safely discard the log before that point. Once a stable checkpoint—for which 2f+1 nodes have signed the same state digest—is secured, decisions up to that point harden into irreversible fact and memory is reclaimed. A checkpoint is not merely a performance optimization but is also a component of safety, serving as the reference point for "where to resume from" during a view change.

If the primary does not respond or forces a wrong order, the backups trigger a View Change after a timer expires. When 2f+1 nodes agree to the view change, the next primary (the node for v+1) is elected, and the new primary inherits the requests that were prepared and committed up to just before—together with evidence (prepared proofs)—to guarantee that already-finalized decisions are not lost. Thanks to this mechanism, a single malicious primary cannot permanently block overall progress in PBFT. However, normal-interval consensus has a message complexity of O(N²) (all nodes exchange Prepare and Commit with each other), so there is a limit whereby scalability drops sharply once the number of nodes exceeds a few dozen.

4. Comparison of Consensus Models and Application Cases

In practice, "which consensus to use" is a design decision that starts not from performance figures but from trust assumptions. Even for the same distributed consensus, if the assumed fault model differs, the required node count, message volume, and the nature of finality change entirely. Below, three representative models are compared, focusing not on the figures themselves but on why those figures are determined that way.

To use BFT correctly, one must clearly understand the difference from crash-fault consensus and from the probabilistic consensus (PoW) of public blockchains. The table below compares the core differences, but why each difference arises is what matters. CFT has fewer nodes and lower latency than BFT because it "does not assume lying nodes," and PoW has greater participant scalability than BFT at the cost of probabilistic finality because it replaced consensus with hash competition instead of voting.

Category Crash fault (Paxos/Raft) PBFT (deterministic BFT) PoW (probabilistic BFT)
Fault model stop/delay only arbitrary/malicious (lying) arbitrary/malicious (open)
Fault-tolerance bound f < N/2 (N=2f+1) f < N/3 (N=3f+1) hash power < 50%
Finality immediate (deterministic) immediate (deterministic) probabilistic (confirmations accumulate)
Message complexity O(N) O(N²) low (broadcast)
Node scalability few to a few dozen a few dozen (clear limit) thousands to tens of thousands
Representative use etcd, ZooKeeper Hyperledger Fabric, Zilliqa Bitcoin, early Ethereum

Making the quorum calculation concrete with small numbers makes the difference clear. When operating with N=100 nodes like a public blockchain, BFT can tolerate up to f=33 malicious nodes (100 ≥ 3×33+1) and every decision requires at least 67 (2f+1) signed votes. In contrast, CFT could tolerate f=49 stop faults with the same 100 nodes—a higher fault-tolerance "ratio"—but this holds only on the strong premise that "there are no malicious nodes." That is, BFT tolerates a smaller ratio of faults (under 1/3) but in exchange provides the qualitative advantage of preserving safety even if those faults are arbitrary behavior including lying. A designer must first ask not "how many faults do I tolerate" but "what kind of faults must I tolerate."

As a concrete case, the permissioned blockchain Hyperledger Fabric has a limited number of participating organizations with verified identities, so it uses a PBFT-family (or Raft) orderer to obtain immediate finality and high throughput. Conversely, open Bitcoin has anonymous participants numbering in the tens of thousands, making O(N²) voting impossible, so it chose PoW and in return accepted "probabilistic finality," where the probability of a block being overturned decreases exponentially over time. Meanwhile, in aviation, the Boeing 777's flight control computer prepares for sensor and computation faults with a triple-majority (Byzantine-resilient) structure—so the BFT concept was actually applied to safety-critical systems long before blockchain. Thus the three axes of "number of participants, trust assumptions, required finality" determine which consensus to use.

5. Deep Dive — Scalable BFT and Recent Trends

PBFT's O(N²) bottleneck was the greatest challenge in BFT research over the past decade or so, and with the rise of blockchain, next-generation BFT that overcomes it poured out. First, Tendermint (now CometBFT) simplifies PBFT, rotates the leader every block, provides immediate finality, and has been adopted as the consensus engine by numerous chains in the Cosmos ecosystem. Second, HotStuff (2019) lowers message complexity to O(N) and reconstructs all phases into leader-centric linear communication, linearizing even the cost of leader change. HotStuff was inherited by LibraBFT (DiemBFT) of Meta's Libra/Diem and by Aptos, Flow, and others, becoming the de facto standard design of modern proof-of-stake (PoS) chains.

The representative next-generation BFT families can be summarized as follows.

  • Tendermint / CometBFT: PBFT simplification + per-block leader rotation, immediate finality. Adopted by Cosmos, Binance Chain, etc.
  • HotStuff / DiemBFT: linear communication (O(N)) and linearized leader change, throughput improvement via pipelining. Inherited by Aptos, Flow, Diem.
  • Casper FFG + Gasper: committee-sampling BFT combined with proof-of-stake, suppressing malicious behavior via slashing. Ethereum PoS.
  • HoneyBadgerBFT / DAG-based (Narwhal, Bullshark): asynchronous BFT without timeout assumptions, maintaining liveness even under network attack.

Third, proof-of-stake (PoS) itself combines with BFT to circumvent the scalability problem. Ethereum's Casper FFG and Gasper randomly draw a committee from hundreds of thousands of validators to perform BFT voting, and impose a slashing penalty on malicious behavior using stake as collateral, suppressing Byzantine behavior with economic cost. This is a hybrid combining "cryptographic voting (BFT) + economic incentive (stake)," a case of breaking through the node-count limit of traditional BFT with validator sampling. Fourth, asynchronous BFT such as HoneyBadgerBFT, which guarantees safety and liveness even in a fully asynchronous network, has emerged, and robust consensus that works without timeout assumptions is being researched. This trend is treated as especially important in Web3 and CBDC (central bank digital currency) designs that simultaneously pursue "trustless large-scale participation" and "immediate finality."

6. Considerations and Implications (Professional Engineer's Perspective)

  • Consensus selection matched to the threat model: Inside a trust domain (an in-house cluster, etcd) one should choose low-cost CFT (Raft), and in a mutually distrusting, open environment (consortium, public blockchain) one should choose BFT. Excessive BFT adoption incurs unnecessary node and latency cost, while insufficient CFT adoption leads to catastrophic safety collapse, so explicitly documenting the fault model early in design is a core governance task.
  • Scalability–finality trade-off: Owing to PBFT's O(N²) nature, throughput plummets once nodes exceed a few dozen. If large scale is needed, reduce communication with the HotStuff (O(N)) family or committee sampling (voting by a validator subset), but since sampling can probabilistically weaken safety, the committee size and re-election cycle must be quantitatively verified.
  • Key management and signature performance: Because BFT requires a digital signature or MAC on every message, key leakage amounts to turning a node Byzantine. A design that protects signing keys with an HSM, threshold signatures, and key rotation, and offsets verification cost with BLS aggregate signatures and the like, determines operational stability.
  • Network assumptions and liveness guarantees: Because PBFT's liveness depends on partial synchrony (existence of a delay upper bound), a sustained network attack (delay, partition) can halt progress. Defend liveness with DDoS defense, multipath, and view-change timer tuning, and review the HoneyBadgerBFT family if full asynchronous tolerance is required.
  • Outlook for combination with economic incentives: In PoS-based BFT, slashing and reward design become part of safety. Suppressing Byzantine behavior with mechanism design that includes economic incentives, not just cryptographic safeguards, is set to become an essential capability of CBDC and decentralized finance, and the professional engineer must hold an integrated design perspective spanning cryptography, distribution, and economic mechanisms.
  • Phased adoption and verification strategy: Before full BFT adoption, reproduce view-change and malicious-primary scenarios with chaos engineering and fault injection to quantitatively verify safety and liveness, and measure in advance the bottlenecks of node geographic distribution, clock skew, and signature throughput. In particular, given the BFT characteristic that it is "fast in the normal interval but latency explodes in the attack interval," a conservative design that sizes capacity by worst-case latency rather than everyday performance is the key to stable operation.

References

In one line: BFT is the strongest fault-tolerance technology that preserves consensus through an N≥3f+1 quorum and multiple cross-verification even in an adversarial environment where nodes send lying, contradictory messages; PBFT's three phases of Pre-prepare, Prepare, and Commit plus view change are its practical archetype, which today has extended to HotStuff and PoS to become the foundation of trust in blockchain and CBDC.