Raft and Paxos are incredibly robust, but they share one fundamental assumption: Nodes don't lie. They assume that if a node fails, it simply crashes and goes silent (a Crash Fault). They assume nodes don't actively try to deceive the cluster.
But what if they do? What if a node has a bug, or is compromised by a hacker, and starts sending conflicting messages to different parts of the cluster? This is known as a Byzantine Fault.
Imagine 4 generals surrounding a city. They must agree to either all ATTACK or all RETREAT. However, some of the generals might be traitors. A traitor might tell General 1 "I vote to Attack" but tell General 2 "I vote to Retreat" to confuse the loyalists and cause a split decision (which results in defeat).
There are 4 nodes. Click on a node to turn it malicious. See if the cluster can still reach consensus.
Requires 3f + 1 nodes to survive f traitors.
To survive Byzantine faults, algorithms like Practical Byzantine Fault Tolerance (PBFT) are required. While Raft only requires a simple majority (2f + 1) to survive crash faults, PBFT requires 3f + 1 nodes to survive f Byzantine faults. So to survive 1 traitor, you need 4 nodes. To survive 33 traitors, you need 100 nodes.
Furthermore, the amount of message passing required is exponential. Every node must ask every other node what they heard from every other node to verify nobody is lying. This is why private PBFT networks cap out at around a few dozen nodes before the network traffic becomes overwhelming.
Proof of Work (Bitcoin) was the first algorithm to solve Byzantine Fault Tolerance at a truly global, permissionless scale. It solves the Sybil attack (where a traitor spins up millions of fake nodes) by tying voting power to physical computational energy, rather than IP addresses.