and spent some time reading about blockchain, fortunately not from a crypto-bro perspective, but rather from genuine curiosity about how it actually works. And while I was going down that rabbit hole, I kept bumping into a concept I had never heard of before. That was Byzantine Fault Tolerance.
In a nutshell, Byzantine Fault Tolerance is a system property that allows a system to continue to operate properly, even when some malicious actors are included in the system. So this Water Cooler Small Talk is going to be about Byzantine Fault Tolerance: what it is, where it comes from, why it matters, and how blockchain ended up being one of the most elegant solutions to a very old problem.
So, let’s take a look!
from Byzantine generals to computers
So, Byzantine Fault Tolerance is a system property that owes its name to the following game theory problem, namely the Byzantine Generals Problem:
A group of Byzantine generals has surrounded a fortress. They must reach a collective decision to either attack or retreat. Both the decisions of retreating and attacking can work, but only if everyone acts in coordination. A coordinated attack succeeds. A coordinated retreat also succeeds. But if some generals attack while others retreat, the result is defeat.
The communication between the generals is all-to-all and the generals can only communicate by sending messengers to each other. However, some of the generals may be traitors. In particular, a traitor does not only vote the wrong way, but also tries to deceive the other generals by sending conflicting messages to different generals. For example, a traitor may tell one general to attack and another to retreat, deliberately trying to create a split. Meanwhile, the loyal generals have no way of knowing in advance who the traitors are.
The problem is: is it possible, and if yes how and under which conditions, can such a setup of generals reach consensus?
This problem was first formally described by computer scientists Leslie Lamport, Robert Shostak, and Marshall Pease in their 1982 paper. And while the setting is medieval and military, the described problem is one of the most fundamental challenges in computer science. That is, how do you reach a reliable consensus in a distributed system when some of the participants might be sending false information?
In a distributed computer system, instead of generals we have nodes: individual computers or servers, each holding a copy of some shared state (a database, a ledger, a record of transactions). All nodes of a distributed system need to agree on what that shared state of truth is. Like the generals, they communicate by sending messages to each other, and like the generals, some of those nodes might be faulty.
But why not just vote? Intuitively, one may assume that each general could just send their vote (attack or retreat) to all other generals, then count the votes, and do what the majority proposes. Attack if more than half say attack, retreat if more than half say retreat.
The trouble is that this only works if each general (node) really trusts the messages that they receive. But in such a network, traitors may also be included, which may send different votes to different generals, with the goal of creating a split decision. General A might receive a message saying “I vote attack”, while General B receives a message from the same traitor saying “I vote retreat”. So, generals A and B may end up with different ideas on what the majority of the network decided to do. In other words, we can no longer just trust the majority vote because the majority for each node might be counting different messages. And this inability to reach consensus is a real issue for those hypothetical Byzantine generals, as much as for distributed computer networks.
Essentially, this is the definition of what a Byzantine fault is. A Byzantine fault is a fault in a distributed system where a component does not simply fail, but instead behaves in an unpredictable way. This means sending conflicting information to different nodes, appearing to be functioning correctly to some nodes while malfunctioning for others, actively producing false outputs, and so on. Nonetheless, a Byzantine fault doesn’t necessarily originate from a malicious actor in the network, since it can also occur from electrical faults, software bugs, or hardware failures that cause a node to produce arbitrary outputs. A node with such behaviour is called a Byzantine node.
In any case, in the original 1982 paper, the authors mathematically prove that for a system with n nodes to continue normal operation (that is, to tolerate) f Byzantine (traitor) nodes, at least n ≥ 3f + 1 total number of nodes is needed. In other words, if more than one-third of the nodes are Byzantine, it is mathematically impossible for such a system to reliably reach consensus, and there’s no algorithm to make such a system continue to operate. A system that has at least two-thirds of the total nodes uncorrupted and can also operate normally, reaching consensus, has the property of Byzantine Fault Tolerance, or is called a Byzantine Fault Tolerant system.
What about blockchain?
For decades after the 1982 paper, Byzantine Fault Tolerance remained a theoretical problem with practical solutions only in tightly controlled environments like aerospace systems, nuclear power plants, or any other place where every node could be vetted in advance and guarantee that fewer than a third would go rogue. In other words, a certain trust was needed among the nodes comprising the network, so even if some of the nodes turned to traitors, those traitors would still be under the 1/3 threshold (hopefully).
1. Bitcoin and Proof of Work
This was the case until 2008, when the Bitcoin whitepaper was published, completely sidestepping the classical voting approach. Unlike distributed networks that existed up to this point, where consensus is reached by majority vote of (hopefully) trusted parties, the Bitcoin whitepaper proposed a mechanism for operating a trustless distributed system. This means that, unlike nuclear power plants, where there was trust among the nodes in advance, Bitcoin can operate without any of the nodes trusting one another, because the Bitcoin consensus mechanism itself guarantees the transactions.
The specific mechanism through which Bitcoin manages to do this is called Proof of Work (PoW). To put it simply, PoW makes it computationally expensive to participate in the consensus process, and even more expensive (practically impossible) to be a traitor. More specifically, to add a new transaction, a node must solve a cryptographic puzzle that requires enormous amounts of computing power. This puzzle is hard to solve for the node that proposes the transaction, but easy for other nodes to verify if the solution of the puzzle is correct.
A traitor node that wants to corrupt the system and propose a false transaction would need to redo the computational work, not just for the transaction it wants to corrupt, but for every subsequent transaction. This is A LOT of computation! On top of this, it would need to do this faster than the rest of the honest network combined. In practice, this would require controlling more than 50% of the total computational power of the network, which is extraordinarily expensive – practically impossible. So in this way, the cost of cheating exceeds any potential benefit one might expect from cheating, rendering it economically irrational. Having said that, even if PoW allows for reliable transactions in a trustless, decentralized system, it also comes with high costs and high latency (Bitcoin transactions may take up to 10 minutes to finalize), due to the massive computation required.
2. modern blockchains and Proof of Stake
Building further on this “making it economically irrational to cheat” concept, but also trying to make the system itself faster, another consensus approach is Proof of Stake (PoS). PoS has been used on Ethereum’s blockchain since 2022, and on other modern blockchains like Solana and Sui. The rationale behind PoS is the same as PoW, but instead of making cheating economically expensive indirectly through computation, it makes it expensive directly by making network nodes submit economic collateral. In particular, in a PoS blockchain, validators (nodes proposing transactions) must lock up a significant amount of the blockchain’s token to have the ability to propose and verify transactions. If a node proposes a transaction that is incorrect, then the system penalizes it and keeps part of the submitted collateral. The difference with PoW is that in PoS, Byzantine behaviour is punished economically rather than made computationally infeasible.
Another thing about PoS is that it does make the system more BFT-like. Unlike Proof of Work, which sidesteps the classical BFT voting model entirely and sets the corruption threshold at 50% of total computational power, Proof of Stake brings us back closer to the original Byzantine Fault Tolerance framework. In a PoS system, validators vote on the validity of transactions using their staked tokens as weight. This means the 1/3 threshold from the original 1982 paper applies again: if more than 1/3 of the total staked value is controlled by Byzantine validators, consensus can break down. PoS is explicitly Byzantine Fault Tolerant in the classical sense, while PoW is not – it just solves a different version of the same problem.
On my mind: BFT beyond blockchain
What struck me the most about BFT is how old the problem is and how long it took to go from documenting the theoretical problem to working solutions. In particular, the problem is identified and formalised in the original 1982 paper, but the first practical algorithm for handling it in real computer systems, called Practical Byzantine Fault Tolerance (PBFT), didn’t appear until 1999. And the first system to actually deploy it in a real-world setup (Bitcoin) didn’t come until 2008.
The other thing I keep thinking about is how universal the problem is. Beyond blockchain, Byzantine fault tolerance, or more generally, the problem of reaching consensus among potentially unreliable participants, is everywhere around us. Anytime you have multiple independent parties that need to agree on something, and you cannot fully trust all of them, you have a version of the Byzantine Generals Problem.
In distributed databases, BFT protocols ensure that a cluster of database servers can agree on the current state of the data even if some servers are corrupted or sending wrong information. In aerospace, flight control computers use BFT-style voting to ensure that a single faulty sensor cannot cause a catastrophic failure. A committee making a decision with some bad-faith members. A supply chain where some suppliers might send fraudulent information. A distributed AI training setup where some devices might send poisoned updates. The generals are everywhere. The question is always the same: how do you reach a reliable consensus when you can’t trust everyone in the room?
✨ Thank you for reading! ✨
If you made it this far, you might find pialgorithms useful: a platform we’ve been building that helps teams securely manage organisational knowledge in one place.
Loved this post? Join me on 💌 Substack and 💼 LinkedIn
All images by the author, except where mentioned otherwise