Adversarial Failure §

Proof sketch: the proof reduces the Byzantine agreement problem to a “general and lieutenants” problem. The general sends an order to $n - 1$ lieutenants. If $n \leq 3f$, the $f$ traitorous lieutenants can each relay a different version of the order to the remaining lieutenants, making it impossible for the loyal lieutenants to distinguish the true order from the lies. The bound is tight: with $n = 3f + 1$, a simple protocol (each node broadcasts its value, and all nodes take the majority) succeeds.

Relation to FLP: the FLP impossibility (asynchronous + 1 crash → no consensus) is a different impossibility. The 3f+1 bound holds even in a synchronous network; it is about the number of Byzantine nodes, not about timing. See Consensus and Consistency for FLP.

PBFT phases:

1. Pre-prepare: the primary (leader) broadcasts the client request to all replicas.
2. Prepare: each replica broadcasts a “prepare” message to all others. A replica enters the prepare state when it receives $2f$ matching prepare messages (a quorum of $2f + 1$ including itself).
3. Commit: each replica broadcasts a “commit” message. A replica enters the commit state when it receives $2f$ matching commit messages, then replies to the client.

View change: if the primary is Byzantine (does not forward requests), replicas detect the timeout and elect a new primary. The view change protocol itself must be Byzantine-tolerant.

Practical considerations: most production systems assume crash faults (not Byzantine). The exception is blockchain systems (Bitcoin, Ethereum) and some military/aviation systems. The $O(n^2)$ message complexity limits PBFT to small groups (typically $n \leq 100$).

HotStuff (Bafna et al., 2019): reduces PBFT’s O(n²) to O(n) amortized by pipelining: while the current view is in the commit phase, the next view’s pre-prepare is already in flight. Uses a “timeout view change” that is O(n) rather than O(n²).

Tendermint (Buchman et al., 2014): similar to PBFT but uses a round-based structure where each round has a propose, pre-vote, and pre-commit phase. A block is committed when 2/3 of validators pre-commit to it. Tolerates f < n/3 crash or Byzantine faults.

Algorand (Lindell, 2019): eliminates the leader entirely. In each round, a committee is selected by a stake-weighted verifiable random function (VRF). The committee proposes and votes. Because the committee is small (O(√n)), message complexity is reduced. Finality is probabilistic: after k consecutive rounds of agreement, the block is considered final with probability 1 − ε.

Mitigation strategies:

• Permissioned systems (e.g., a blockchain with known validators): identity verification via certificates or a trusted authority.
• Proof-of-work (Bitcoin): creating fake identities requires controlling > 50% of the hash power, which is economically prohibitive.
• Proof-of-stake (Ethereum): creating fake identities requires staking a large amount of capital, which is slashed if the validator misbehaves.
• Reputation systems: weight votes by historical behavior or social graph centrality.

Relation to Byzantine faults: a Sybil attack is a specific type of Byzantine behavior where the attacker’s strategy is to multiply identities rather than to send contradictory messages. The 3f + 1 bound assumes each Byzantine node is a single entity; Sybil attacks violate this assumption by inflating n with fake nodes that all behave identically (as one logical attacker).

Tolerance: PBFT tolerates $f = \lfloor(n-1)/3\rfloor$ Byzantine faults. With $n = 10$: $f = \lfloor(10-1)/3\rfloor = 3$. The system is designed to tolerate 3 Byzantine validators.

Attacker with 4 validators: The attacker controls 4 out of 10 validators. Since $4 > 3$, the attacker exceeds the designed tolerance. The quorum is fixed at design time: $2f + 1 = 2(3) + 1 = 7$ matching messages are required in the prepare phase. This quorum does not change based on how many nodes are actually Byzantine; it is a protocol parameter set when the system was configured for $f = 3$. The attacker simply has more nodes than the protocol can absorb.

With 4 Byzantine nodes, the honest nodes number 6. The attacker can withhold or contradict messages so that no honest node ever collects 7 matching prepare messages (the 4 Byzantine nodes can send conflicting values, and the 6 honest nodes alone cannot reach the quorum of 7). Yes, the attacker can prevent the system from making progress.

Note: In practice, blockchain systems use different mechanisms (proof-of-work, proof-of-stake) rather than PBFT, precisely because the $3f + 1$ bound is too restrictive for large, open networks.