The problem
As Comrade Prmottajr said in his answer, the problem of the Byzantine generals is to allow a distributed decision to be made (to attack/retreat or to attack/wait) in the face of the possibility of some of them being traitors and in the face of the possibility of messages between them being lost. The time for the decision to be made is finite.
It’s important that all non-contracting generals reach a consensus. If half of them decide to attack and half decide to retreat, the armies that attack will be massacred and those that have retreated will not be numerous enough to carry the war forward. And that’s the purpose of traitors.
Traitors not only vote against the group’s decision, but do so selectively. You can now send real messages, and sometimes send fake messages, and you can choose when and to whom you will send what messages. Traitors may or may not also operate in collusion to try to thwart the goal of loyal generals. On the other hand, loyal generals always obey what they believe to be the decision of the majority.
Constraints of the problem
There are some possible solutions, depending on the restrictions adopted. However, in all solutions, all loyal generals must have the same process/algorithm and follow it rigorously.
The loyal generals must then give their vote and communicate it to all the other generals. After a general receives the vote of the other generals, he knows the group’s decision. If most loyal generals vote to attack, then the small number of traitors won’t be enough to change the consensus. If loyal generals divide more or less half-to-half, then it is probably because both alternatives must be equally good or equally bad, and the traitors' vote will only exchange six for half-dozen.
In fact, this corresponds to a class of problems since there are several restrictions that may or may not apply depending on the particular case:
Messages between generals can be lost?
Messages between generals can be changed on the way?
Which generals can communicate with which other generals?
Senders of messages can be forged?
There is a commander among the generals?
How many and which are the traitors?
Communication between generals is synchronous or asynchronous?
The number of generals is fixed?
There are limitations on the number of messages?
Messages lost or not sent can be detected?
What to do when a message is lost?
There are cases where there is no solution. For example:
If all the generals are traitors, there’s not much to do and the war is lost.
If traitors are able to forge, intercept, alter, and/or destroy any messages at any time, even if sent between two loyal generals, then they effectively control any and all communication and can induce loyal generals to do whatever they want.
There are also cases where the solution is simple and easy, for example:
If the messages between the generals cannot be forged, intercepted or destroyed and there is a commander who is known to be loyal, then all the commander has to do is send a message to each general and the loyal generals will obey that message.
If traitors can be easily identified, or alternatively loyal generals can easily prove their loyalty, then simply identify traitors and exclude them.
But there are scenarios where the solution is something very complicated.
Scenario 1
The first scenario considers that:
Messages sent between two loyal generals are never lost or intercepted. That is, all messengers are reliable.
The sender of a message from a loyal general cannot be forged/falsified.
The absence of a message is detectable (e.g., timeout).
All generals can communicate with all other generals directly.
One of the generals is the commander, he makes the decision.
The number of traitorous generals is less than, but not equal to, one third of the total generals.
If the commander is a traitor, still all the other generals come to a consensus.
The algorithm in this case is as follows:
All loyal generals must send messages to all others relaying the commander’s decision.
A standard strategy is defined for the case that no message is received within a reasonable time (for example: back).
All messages sent from one general to the other must have the sender ID.
The incoming messages contain the ordered list of the generals through which they passed before reaching the recipient. The recipient will send it to all other generals who are not on that list, placing himself at the end of that list of generals the message went through.
Each general follows the commander’s decision. In case of incoming messages with conflicting information about what the commander’s decision is, then the one expressed in the largest number of incoming messages.
Messages from the same excess sender should be ignored.
In this scenario, since the sender cannot be forged, there is no way the traitors send messages posing as other loyal generals to try to deceive them (a traitor may pose as another traitor, but this is of little use to them).
Nor is there any way for a message sent by a loyal general to be corrupted on the way to its recipient. Nor is it very interesting for a traitor to fail to send a message to some loyal general because it would reveal to that loyal general his status as a traitor.
Note that traitors can lie and provide messages with false lists of generals, out of order and/or with incorrect decisions.
In this case, the messages between loyal generals effectively say the following:
Of: Commander
To: General 1
I decided X.
From: General 1
To: General 2
The commander decided X.
From: General 2
To: General 3
According to General 1, the commander decided X.
Of: General 3
To: General 4
According to General 2, General 1 said the commander decided X.
Of: General 4
To: General 5
According to General 3, General 2 said General 1 said the commander decided X.
That means being n the number of generals and m the maximum number of traitors (m = n-1/3, rounded down), the commander shall send n-1 messages in the first round. In the second round, each of the other n-1 generals will send n-2 messages to the other generals. In the third round, each general will send n-3 messages to the other generals (except those who already have their name on the list of generals in the message). In the fourth round, each will send n-4 messages. And so on, supplementing n-m-1 rounds.
After all the messages have been collected, each general observes what each other general sent and decides what is the opinion of each general regarding the consensus to then understand what is the consensus.
The proof that this algorithm works is quite complicated. However, it is not very applicable in practice, as it needs a very large number of messages to work and requires that all generals can communicate with everyone. This is not something realistic when you have an implementation where there are millions of generals for example. Another problem is that if the commander is a traitor, although the other generals reach a consensus, it will be of little value since any decision taken will be determined by the traitor.
Scenario 2
The main problem of scenario 1 is that traitors can lie. This can be solved if:
Messages from loyal generals are signed.
False signatures cannot be forged.
Messages with signatures that cannot be verified or unsigned are discarded by loyal generals.
In practice, these constraints are easily modeled by a digital signature scheme. See more in that reply.
With this signature scheme. It is possible to create messages like this:
Of: General 4
To: General 5
I attest that what follows is true.
Of: General 3
To: General 4
I attest that what follows is true.
From: General 2
To: General 3
I attest that what follows is true.
From: General 1
To: General 2
I attest that what follows is true.
Of: Commander
To: General 1
I decided X.
[Signature of the Commander]
[Signature of General 1]
[Signature of General 2]
[Signature of General 3]
[Signature of General 4]
In this scheme, the messages are placed inside each other, demonstrating the sequence of generals through which she passed and accumulating signatures. General 5, when you receive this, can attest to the authenticity of all signatures.
If, for example, General 3 is a traitor and he tries to forge a false message, the signatures of the commander, General 1 and General 2 will not be validated and in doing so he would quickly be unmasked.
If the commander is a traitor and send "I decided X." for General 1 and "I decided Y." for General 2, when General 1 and General 2 exchange messages, they will realize the inconsistency, and since the signatures cannot be forged, they will deduce that the commander gave different orders to different generals and therefore would be a traitor.
This scheme also reduces the number of messages and eliminates the need for all generals to talk to all other generals, if all loyal generals can communicate with each other in ways where the messages do not pass through any traitor (but since it is not known who the traitors are, they will also receive and send messages). Still, this is a very complicated thing to manage properly.
Application of the problem
Many algorithms for cases of Byzantine generals require that the number of traitors does not reach one third of the total number of generals. There are circumstances for which it is sufficient that the number of traitors does not reach half the number of generals.
The problem of the Byzantine generals is actually a family of related and similar problems, but they may have very different solutions to each other depending on the conditions of the problems.
In bitcoin, for example, generals represent nodes that can make transactions and each of them maintains a blockchain. Bitcoin uses digital signatures to ensure that messages cannot be forged. In each transaction, the commander is the one who initiates it, that is, a person who is sending some amount of Bitcoins to someone else. A blockchain is a gigantic ledger that stores everyone’s transaction pool, and as each has a copy, the idea is that when a transaction is announced, everyone records it in their ledgers. Loyal generals are those who record transactions honestly in their blockchains and send messages to the other generals so that they also do so.
In the case of bitcoin, traitors would be those who try to forge nonexistent transactions, spend money they don’t have, create money out of thin air, or keep separate books. If there are enough traitors acting in collusion on bitcoin, they can impose a fraudulent blockchain on honest users. One of the security premises of bitcoin is that the number of traitors is small enough.
Several other situations are analogous to the problems of the Byzantine generals:
In practice, loyal generals represent those legitimate users and software who aim to work as expected honestly for the benefit of all. Traitors are those who have vested interests, such as hackers attempting to circumvent or abuse the system, fake or hacked software, users wanting to troll, mock and disrupt. Traitors may also be equipment that has defective parts and does not work properly or software that has bugs that are causing problems.
As there are many scenarios in which this can be applied, and the algorithm to be applied varies greatly according to the constraints of the problem, it is not possible to create a generic implementation without more details. However, even so some exist, including in Java:
I don’t know the details of any of them and surely there must be other projects for that out there. But with this list, it should be enough to start.
I believe that "implementing the problem" was a typo. A program is a solution to the problem. The problem itself it simply exists without needing implementation or solution. For example, there is the halting problem HALT but there is no implementation for it. There is also the co-NP primality problem (
nis cousin? ), that you do not encode the problem, but its solution– Jefferson Quesado
Taking advantage: this problem was formally described in 1982 by Leslie Lampourt (the "La" in "Latex") in an article submitted to ACM
– Jefferson Quesado
@Jeffersonquesado, really can mislead! I have already edited. As for the problem is well documented. But I did not find an answer here at Sopt.
– pss1suporte
The question in item 2 is too wide.
– Victor Stafusa
@Victorstafusa, I believe it is not. Because it is about implementing a solution to a problem. Common exercise of building algorithmic projects. Show the applications of algorithms for solving different problems; What applies for the purpose of the question. It is not a matter of right or wrong. But to demonstrate a practical solution. What may imply a distributed processing solution due to the context of the problem!
– pss1suporte
@Victorstafusa, the solution already exists, but not here at Sopt (see Satoshi Nakamoto).
– pss1suporte