The Byzantine General’s Problem

During war, the exchange of trustworthy information between involved parties has been a critical factor determining the desired outcome; that holds true both today and thousands of years ago. The Byzantine Generals Problem describes a situation that has been subject to game theorists and military strategists for the past decades.

Imagine a setting where multiple stakeholders must agree on one common strategy to achieve a mutual goal. The twist is that some of those stakeholders might be corrupt, unreliable, or simply chaotic, spreading false information. The famous metaphor of the Byzantine Generals problem was first theorized by Lamport, Pease and Shostak in 1982. Let’s play this thought experiment:

Imagine that we have a village surrounded by two armies on the opposite of each other. Their goal is to conquer this village, however, to do so they need to attack at the exact same time. Otherwise, the villagers can easily defend against a single army.

The difficulty is that as the two armies are somewhat scattered the respective generals need to coordinate the attack – they do not have centralized control (you see where we are going…). For the sake of communication, the only way to send messages is to send out messengers of the respective armies. Keep in mind: they are in a hostile environment. They could be kidnapped and replaced by a villager or bribed to send false information, leading the attack to fail.

Lamport, Pease, and Shostak went even further, describing different traitor scenarios where they argue that the armies’ generals could also be corrupt and send misleading information (see below).

Illustration: Lamport, Pease & Shostak (1982)

In fact, only decentralized systems face the problem of the Byzantine Generals. Such systems are lacking a reliable source of information. There is no way of verifying if the delivered information holds true. Centralized systems, however, not only possess a trusted authority (source of information) but also prevent false or fraudulent information from being spread.

As you might have understood already, the above setting wants to illustrate the characteristics of a decentralized network where the armies’ generals stand for the nodes of that network. The core problem is how to ensure correct decisions in a decentralized peer-to-peer network. It requires the network to be cautious or even somewhat “trustless”. This way it might be possible to prevent it from automatically assuming that all nodes act in the group’s interest.

Those who are a little familiar with the blockchain technology know: this agreement between all participating nodes is referred to as consensus. Nevertheless, the solution to the Byzantine Generals Problem is not simply resolved through a consent between nodes – it requires some heavy computing work to verify the communication between nodes (generals) and thus the message itself.

As you can imagine we unfortunately cannot always trust all participants of a network to act in the group’s interest. One prominent problem related to cryptocurrencies is the issue of “double-spending”: imagine paying with the same euro bill to buy a pizza in Rome and a salad in Paris at the exact same time. It sounds weird with cash, however, for digital currencies that presents a genuine problem, as such “double-spendings” would turn the system irrelevant.

So, there must be some sort of tolerance that allows the algorithm to make a cohesive decision even though there might be corrupt elements inherent to the network. Fortunately, such a tolerance exists. It is referred to as Byzantine fault tolerance (BFT) as those corrupt elements are called Byzantine Faults. Any failure within the system, presenting different symptoms to the network’s participants are referred to as Byzantine Fault, however, they deserve an article for their own. What is important is the way the network still can keep on going: consensus. We briefly mentioned it above. The consensus mechanism is a dynamic process with the goal to derive a fail-safe decision through e.g., proof-of-work (Bitcoin) or proof-of-stake (Etherum).