The Byzantine Generals’ Problem is a practical solution to the Byzantine faults’ problem given by Lamport in 1982[cite: 8]. The best way to explain the analogy is through a historic tale. The depicted scenario consists of an army that has besieged the city[cite: 8]. The army has n divisions with n > 0, and each division has a lieutenant[cite: 8]. In particular, there is a commanding general plus n lieutenants that are close to the enemy target[cite: 8].
The commanding general must take a decision whether to attack or retreat and send the order to the other lieutenants[cite: 8]. Be aware that the army has a good chance to win if and only if a majority of 2/3 of the lieutenants agree to the same overall decision (attack or retreat)[cite: 8].
In order to find the agreement, the lieutenants propagate the commanding general’s decision to the other members, but there might be some traitors among them, including the commanding general[cite: 8]. These traitors are assumed to misbehave and send conflicting messages to others with the aim of prejudicing the consensus[cite: 8].
At the end of the day, we would like that a small number of traitors cannot influence the commanding general’s decision and everyone agrees to the same order[cite: 8].
It is possible to prove that the Byzantine General’s Problem is still unsolved if we have only two lieutenants[cite: 8]. In this case, a tie-breaker is needed to reach a 2/3 majority; otherwise, the nodes will continue sending conflicting messages[cite: 8].
As an example, lieutenant A receives a message from the commanding general ordering to attack. At the same moment, he receives another message from lieutenant B, ordering to retreat[cite: 8]. They never come to an agreement and thus, the consensus cannot be reached[cite: 8].
Theorem. If t is the number of traitors for any given value of t ≥ 1, the Byzantine Generals’ Problem has not a solution when less than 3t + 1 members are employed[cite: 8].
This theorem means that to have a solution to the Byzantine Generals’ Problem at least 2/3 of the members must be loyal[cite: 8]. If there is only one malicious member, we need at least three lieutenants plus one commanding general to find a consensus[cite: 8].
Unfortunately, the number of messages exchanged between the parties grows quadratically with the number of members of the network[cite: 8]. Thus, increasing the number of lieutenants comes at a cost of increasing the complexity of finding the agreement[cite: 8]. This is an important limitation to the adoption of these protocols in distributed systems because it requires a huge number of messages exchanged between the parties[cite: 8].
The messages can carry out a binary value, such as “attack” or “retreat”, or they can contain one value out of more different values[cite: 8]. If there are three possible values, such as x, y and z, we might think of one message as an order to disable the previous condition[cite: 8]. As an example, x and y can be disabled by z[cite: 8].
Back to our blockchain, the lieutenants are the nodes, while the commanding general is the leader, in charge of delivering the next block[cite: 8]. Both of them can communicate over a bi-directional channel and both of them can potentially be traitors[cite: 8].
For the blockchain, the leader does not propagate any order but rather a block[cite: 8]. The nodes check that all transactions in the block are correct and have not already been spent[cite: 8]. Then, they propagate their vote through the network[cite: 8].
The main idea is that every node should reach a final consensus on the state of the shared ledger[cite: 8]. Such types of approaches that allow an arbitrary (or Byzantine) behavior of a small number of nodes without affecting the outcome are called Byzantine Fault Tolerance protocols (BFT)[cite: 8].
The BFT protocol can be applied to every distributed system, including the blockchain, to allow overall reliability in asynchronous networks[cite: 8].