Byzantine Fault Tolerance and Blockchains

When nodes may lie

Raft and Paxos tolerate f crash failures with 2f + 1 nodes. If nodes can behave arbitrarily (Byzantine: bugs, compromised machines, malicious operators), you need 3f + 1 nodes. The reasoning: a node can wait for only n - f replies, since f may never answer; of those replies, up to f may come from liars, and the honest ones must still outnumber them, giving n - 2f > f. Protocols such as PBFT use three phases (pre-prepare, prepare, commit) with quorums of 2f + 1 and cryptographically signed or authenticated messages, so a faulty leader cannot send different orders to different replicas undetected. Message complexity is higher, often quadratic in the number of nodes, which limits cluster size. Newer designs such as HotStuff reduce communication and are used in some permissioned blockchains. Public blockchains such as Bitcoin use a different approach, proof of work, and offer only probabilistic finality. Inside a single company's data centre, where nodes are trusted, crash fault tolerance is the norm.

Replicas needed for crash vs Byzantine faults

The same number of tolerated faults costs more machines when nodes may lie.

for f in (1, 2, 3):
    print(f"tolerate f={f}: crash-fault (Raft/Paxos) needs {2 * f + 1} nodes, "
          f"Byzantine (PBFT-style) needs {3 * f + 1} nodes")

Output:

tolerate f=1: crash-fault (Raft/Paxos) needs 3 nodes, Byzantine (PBFT-style) needs 4 nodes
tolerate f=2: crash-fault (Raft/Paxos) needs 5 nodes, Byzantine (PBFT-style) needs 7 nodes
tolerate f=3: crash-fault (Raft/Paxos) needs 7 nodes, Byzantine (PBFT-style) needs 10 nodes

An exam answer key

If teachers may only be absent, a majority of present teachers can confirm the key. If some teachers might deliberately give wrong answers, you need enough honest teachers to outvote the liars even after the absentees are removed, so the panel must be larger.

Quick check: How many replicas does a classic BFT protocol need to tolerate 2 Byzantine nodes?

• 5
• 6
• 4
• 7