The Byzantine Generals problem

In computing, we usually consider that a reliable computer system must be able to cope efficiently with the failure of one or more of its components. Indeed, a failed component may at any time sends conflicting informations to different part of the system and we must be able to rely on an algorithm in order to cope with this problematic, also known as the Byzantine Generals problem.

However, before the creation of the Blockchain technology in 2009 by Satoshi Nakamoto,  we didn't really have any computer algorithm capable to solve this problematic whitout having to use a third trusted party. In this sense, it appears interesting to analyze what is the Byzantine Generals problem and present its basic algorithm in order to then be able to grasp the full potential of the blockchain technology in future articles.

1 The Byzantine General Problem

Let's imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors trying to prevent the loyal generals from reaching agreement similarly to the failing nodes in a computing network. As such, it's easy to see that we have to create an algorithm in order to prevent it from happening.

In this sense, let's assume that :

A. All loyal generals decide upon the same plan of action.

Here, the loyal generals will all do what the algorithm says, but the traitors may do anything they wish which is problematic due to the fact that the algorithm must guarantee condition A regardless of what the traitors do. Indeed, the loyal generals should not only reach agreement but also agree upon a reasonable plan. Therefore we also need to insure that :

B. A small number of traitors cannot cause the loyal generals to adopt a bad plan.

Asumming that v(i) is the information communicated by the ith general. Then each general uses some method for combining the values v(1), . . . , v(n) into a single plan of action, where n is the number of generals and we can easily note that condition A can only be achieved by having all generals use the same method for combining the information and condition B by using a robust method.

Example :

If the only decision to be made is wheter to attack or retreat, then v(i) can be General i's opinion of which option is best, and the final decision can be based upon a majority vote among them. As we can see, here, a small number of traitors can affect the decision only if the loyal generals were almost equally divided between the two possibilities in which case neither decision could be called "bad".

Currently this approach is the only one known. However, it require a way for the generals to communicate their value v(i) to one another and the obvious method consisting for each generals to send v(i)  by messengers to each other does not appear to be sufficient here by itself. Indeed, if we are to met the requirement of condition A and B given the ability of traitorous generals to send different values to  different generals we must satisfy the following assertions :

1. Any two loyal generals uses the same value of v(i)

2. If the ith general is loyal, then the value that he sends must be used by every loyal general as the value of v(i).

Moreover, given the fact that those priors conditions both relies on the single value sent by the ith general, we can therefore restrict  the problem to a single general sending his values to the others by considering a commanding generals sending an order to his lieutenants :

Byzantine Generals Problem :  A commanding general must send an order to his n - 1 lieutenant generals such that :

IC1 : All loyal lieutenant obey the same order.

IC2 : If the commanding general loyal, then every loyal lieutenant obeys the order he sends.

(here we consider general i as the commanding general and treat the other generals as his lieutenants)

Even though, the Byzantine Generals problem appears simple it can become surprisingly difficult if the generals can only send "oral" ⁽¹⁾ messages. Indeed, in this case the message content is completely under the control of the sender, so a traitorous sender can transmit any possible message and no solution exists in the case where we have 3 generals and a single traitor :

⁽¹⁾ _{Oral message corresponds to the type of message that computer usually send to one another}

In Figure 1, we can see that the commander is loyal and sends an attack order, but lieutenant 2 is a traitor and reports to lieutenant 1 that he received "retreat". So, for IC2, to be satisfied, lieutenant 1 must obey the order attack.

Now, considering the other scenario shown in Figure 2, we can see that here the commander is a traitor and sends an attack order to lieutenant 1 and a retreat order to lieutenant 2. However, lieutenant 1 is not able to determine who is the traitor and cannot tell the difference with the scenario of the Figure 1 leading him to choose by default to follow the order attack sent by the traitorious commander.  Moreover, if we look now at the case of the lieutenant 2 in the Figure 2, we can see that he will equally follow the order sent by the traitorious commander leading at a situation violating our IC1 condition. As such, we can state that no solution exists for three generals in the presence of a single traitor and using this result prove by contradiction that no solution with fewer than 3m + 1 generals can cope with m traitors.

That is all for our brief presentation of the Byzantine Generals problem today.