*https://medium.com/loom-network/understanding-blockchain-fundamentals-part-1-byzantine-fault-tolerance-245f46fe8419*
Georgios Konstantopoulos, December 2017
Blockchains are inherently decentralized systems which consist of different actors who act depending on their incentives and on the information that is available to them.
Whenever a new transaction gets broadcasted to the network, nodes have the option to include that transaction to their copy of their ledger or to ignore it. When the majority of the actors which comprise the network decide on a single state, consensus is achieved.
A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires processes to agree on some data value that is needed during computation.¹
These processes are described as consensus.
In order to create a secure consensus protocol, it must be fault tolerant.
Firstly, we will talk briefly about the unsolvable Two Generals Problem. Then we will extend that to the Byzantine Generals’ Problem and discuss Byzantine Fault Tolerance in distributed and decentralized systems. Finally, we will discuss how all this relates to the blockchain space.
This problem (first published in 1975 and given its name in 1978) describes a scenario where two generals are attacking a common enemy. General 1 is considered the leader and the other is considered the follower. Each general’s army on its own is not enough to defeat the enemy army successfully, thus they need to cooperate and attack at the same time. This seems like a simple scenario, but there is one caveat:
In order for them to communicate and decide on a time, General 1 has to send a messenger across the enemy’s camp that will deliver the time of the attack to General 2. However, there is a possibility that the messenger will get captured by the enemies and thus the message won’t be delivered. That will result in General 1 attacking while General 2 and his army hold their grounds.
Even if the first message goes through, General 2 has to acknowledge (ACK, notice the similarity to the 3-way handshake of TCP ) that he received the message, so he sends a messenger back, thus repeating the previous scenario where the messenger can get caught. This extends to infinite ACK’s and thus the generals are unable to reach an agreement.
There is no way to guarantee the second requirement that each general be sure the other has agreed to the attack plan. Both generals will always be left wondering whether their last messenger got through.