What Are the Byzantine Generals Problem and Byzantine Fault Tolerance

What is the Byzantine Generals Problem, and how does a Byzantine fault tolerant system work? In this post, we'll look at the situation in which the Byzantine Generals Problem arises and at Byzantine fault tolerance, a systematic way to solve it.

What Is the Byzantine Generals Problem?

The concept of Byzantine fault tolerance was devised to solve the Byzantine Generals Problem described below. So what is the Byzantine Generals Problem? The Byzantine Generals Problem refers to a logical dilemma first presented in 1982. It describes the difficulty that generals in a place called Byzantium may face in reaching agreement.

The Byzantine Generals' dilemma assumes that each general commands a separate army and that they are stationed in different cities, yet must communicate with one another. Each general has to decide whether to attack or retreat. Whether they attack or retreat doesn't actually matter, as long as all the generals agree on one common decision.

• Each general is stationed in a different city.
• Each general must decide whether to attack or retreat (yes or no).
• Once a decision is made, it cannot be changed.
• All generals must agree on the same decision and carry it out at the same time.

In this situation, the generals can communicate with one another only through soldiers who deliver letters. The problem is that, along the way, messages may arrive late or get lost. And even if a message is delivered correctly, one or more generals could betray the others and pass a different message on to the next general. If that happens, the generals can't reach agreement.

Does the Byzantine Generals Problem make sense now? Next, let's look at Byzantine fault tolerance, an attempt to solve this dilemma systematically.

Byzantine Fault Tolerance

Byzantine Fault Tolerance refers to a system property that can cope with the Byzantine Generals Problem we looked at above. In other words, it means the system keeps working as long as ⅔ of the generals are honest, even if some generals fail to communicate or act maliciously.

To sum up, Byzantine fault tolerance means that even if not all generals (100%) agree, the system is considered safe and keeps operating as long as ⅔ or more agree. The Byzantine problem can be solved in many different ways, so that ratio could also be 51% rather than 75%.

Byzantine fault tolerance was first used in aviation. Aircraft use navigation systems to determine their position. To prevent accidents, each sensor must always send accurate, correct information. If even one sensor gives different information, a Byzantine Generals Problem arises: the system has to compare it with the other sensors and decide which value to accept. By applying a Byzantine fault tolerant system here, if a navigation system has 3 sensors and 2 of them are working properly, it can ignore the faulty signal from the remaining 1.

The Byzantine Generals Problem and Blockchain Consensus Algorithms

Now let's apply the Byzantine problem and fault tolerant systems to blockchain. Each general represents a network node, and the nodes must reach consensus on the system. In other words, participants in a decentralized network must agree on the same thing and act on it.

But reaching consensus in a safe and efficient way on a decentralized network is never easy. That's because someone might act dishonestly in pursuit of their own interests. The most extreme form of attack is the 51% attack. If a 51% attack happens, the network can collapse.

So how do blockchains like Bitcoin reach smooth consensus on a decentralized network made up of computer nodes all over the world? The way to achieve consensus in such a decentralized system is to have at least ⅔ of the network nodes be trustworthy and honest.

There are many ways to solve the Byzantine Generals Problem, and therefore many ways to build a Byzantine fault tolerant system. In blockchain, these solutions are called consensus algorithms.

In blockchain, a consensus algorithm refers to the method of reaching consensus. The most common consensus algorithms are Proof of Work (PoW) and Proof of Stake (PoS). Bitcoin uses Proof of Work, and Ethereum uses Proof of Stake.

A blockchain network follows its consensus algorithm to verify transactions and check their validity. For example, Proof of Work rewards miners who act honestly with bitcoin, giving each node an incentive to behave honestly. If a node acts maliciously, it loses its mining costs. In other words, it works hard and ends up losing money instead.

Mapped onto the Byzantine fault tolerance we discussed earlier, the Proof of Work consensus algorithm is designed so that each general (node) receives bitcoin as a reward for acting honestly. In other words, it's a Byzantine fault tolerant system designed so that it pays for each general to relay messages to the other generals accurately and on time, without tampering with them.

The Proof of Work consensus algorithm designed by Satoshi Nakamoto has so far proven to be the most reliable one for blockchain networks.

Final Summary

The Byzantine Generals Problem refers to the dilemma of having to achieve trust in a situation where participants cannot trust one another. In this situation, a Byzantine fault tolerant system gives each general an incentive to act honestly and, for example, keeps the system running as long as ⅔ or more of its members agree. In blockchain, Byzantine fault tolerant systems are called consensus algorithms, and through them each node can reach network consensus in a decentralized way.