Presenting the Byzantine Generals’ Problem


Abstract

The Byzantine Generals’ Problem is a practical solution to the Byzantine faults’ problem given by Lamport in 1982. The best way to explain the analogy is through a historic tale. The depicted scenario consists of an army that has besieged the city. The army has n divisions with n > 0, and each division has a lieutenant. In particular, there is a commanding general plus n lieutenants that are close to the enemy target. The commanding general must take a decision whether to attack or retreat and send the order to the other lieutenants. 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). 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. These traitors are assumed to misbehave and send conflicting messages to others with the aim of prejudice the consensus. 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.

Image

It is possible to prove that the Byzantine General’s Problem is still unsolved if we have only two lieutenants. In this case, a tie-breaker is needed to reach a 2/3 majority otherwise the nodes will continue sending conflicting messages. 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. They never come to an agreement and thus, the consensus cannot be reached. Based on this fact, we can provide the following theorem:

Theorem 1. 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.

This theorem means that to have a solution to the Byzantine Generals’ Problem at least 2/3 of the members must be loyal. If there is only one malicious member, we need at least three lieutenants plus one commanding general (as depicted in figure A.1) to find a consensus. Unfortunately, the number of messages exchanged between the parties grows quadratically with the number of members of the network. Thus, increasing the number of lieutenants comes at a cost of increasing the complexity of finding the agreement. This is an important limitation to the adoption of these protocols in any distributed system because it requires a huge number of messages exchanged between the parties.

The messages can carry out a binary value, such as “attack” or “retreat”, or they can contain one value out of more different values. 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. As an example, x and y can be disabled by z.

Back to our blockchain, the lieutenants are the nodes, while the commanding general is the leader, in charge to deliver the next block. Both of them can communicate over a bi-directional channel and both of them can potentially be traitors. For the blockchain, the leader does not propagate any order but rather a block. The nodes check that all transactions in the block are correct and have not already been spent. Then, they propagate their vote through the network. The main idea is that every node should reach a final consensus on the state of the shared ledger. 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). The BFT protocol can be applied to every distributed system, including the blockchain, to allow overall reliability in asynchronous networks.



GitHub - LinkedIn
© Cristian Lepore