The Byzantine Generals Problem

In the following chapters, we will start addressing more business-oriented topics. Until then, I should provide you with some context on the whys and wherefores of blockchain and go back to where it all started, with the Byzantine Generals Problem.

The Byzantine Generals Problem is a real-life analogy for computer science that was expressed and partly answered in 1982 by Leslie Lamport, a famous American scientist and Turing Award winner, who raised the following question: how can you achieve a consensus in the presence of traitors or faults? Translated to the computer science world, this means: how can you achieve consensus in a distributed system where some computers may be malfunctioning or give conflicting information? This is how the issue came to be illustrated and known as the Byzantine Generals Problem.

The following diagram is an illustration of the Byzantine Generals Problem:

Explanation—multiple byzantine generals surrounding a city must coordinate their attack to take the city. To coordinate themselves, they use messengers to indicate to each other which decision they took: attack or retreat. Since this situation happens under war circumstances, some generals could be traitors and some messengers could be captured or die trying to send the news.

If we draw a comparison with blockchain, the generals are the miners and the messengers are the communication links between them. Several researchers have concluded that the generals can't agree on a strategy if one third or more are traitors.

So how does blockchain solve it?

One instrument was introduced into the blockchain to make consensus work: incentives. A blockchain usually includes incentives for the miners who validate the transactions. In Chapter 1, Basics of Blockchains and the Illustration of Village Beta, the villager who validated the transactions was rewarded with 5 Villagecoin.

In a blockchain, this is how a consensus is reached:

1. All of the miners start constructing their local block.
2. A random miner solves the mathematical problem of the block.
3. The random miner sends his/her block to the other miners.
4. The other miners receive the block of the random miner.
5. The other miners check that the result found by the random miner is correct and that the previous hash points to the previous block's hash.
6. If it is valid, they cancel the block they were building and add to the copy of their blockchain the new block sent by the random miner.
7. The random miner is rewarded with an incentive.
8. Then, the process repeats.

If a dishonest miner solved the mathematical problem and incorporated an invalid transaction in its block, the other miners would reject it because it contains an invalid transaction (the hash would totally be different). This miner would have to discard his/her block and, therefore, will not be able to receive any incentive. Let's look at how incentives work in more detail.