C
The problemAs the prmottajr companion said on https://pt.stackoverflow.com/a/267167/132 , the problem of the Byzantine generals is to allow a distributed decision to be taken (to attack/recover or then to attack/wait) in view of the possibility of some of them being traitors and in view of the possibility of messages among them being lost. The time for the decision to be made is finite.It is important that all non-traitor generals reach consensus. If half of them decide to attack and half decide to retreat, the armies that attack will be massacred and those who retreated will not be numerous enough to carry the war forward. And that is the goal of the traitors.The traitors not only vote against the group's decision, but do so selectively. They may pray to send true messages, and pray to send false messages, and they may choose when and for whom they will send which messages. The traitors may also or may not operate in collusion to try to frustrate the goal of the loyal generals. On the other hand, loyal generals always obey what they believe to be the majority decision.Problem RestrictionsThere 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 strictly.The loyal generals should 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 for attacking, then the small number of traitors will not be enough to change consensus. If the 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 vote of the traitors will only exchange six for half-dozenship.In fact, this corresponds to a class of problems since there are several restrictions that may or may not apply depending on the concrete case:Can messages between the generals be lost?Can the messages between the generals be changed on the way?Which generals can communicate with which other generals?Can message senders be forged?Is there a commander among the generals?How many are the traitors?Is the communication between the generals synchronous or asynchronous?Is the number of generals fixed?Are there limitations on the number of messages?Lost or unsubmitted messages can be detected?What to do when a message gets lost?There are cases where there is no solution. For example:If all the generals are traitors, there is not much to do and the war will be lost.If the 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 all communication and can induce the 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 it is enough the commander to send a message to each general and the loyal generals will obey this message.If the traitors can be easily identified, or alternatively the loyal generals can easily prove their loyalty, then just identify the traitors and delete them.But there are scenarios where the solution is quite complicated.Scenario 1The first scenario considers that:The messages sent between two loyal generals are never lost and cannot be 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 traitoring generals is smaller, but not equal, to a third of the total generals.If the commander is a traitor, yet all the other generals reach 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 in case no message is received within a reasonable time space (e.g.: backing).All messages sent from one general to the other must have the sender's identification.The messages received contain the orderly list of the generals they passed through before reaching the recipient. The recipient will send it to all other generals who are not on that list, placing themselves at the end of that list of generals where the message passed.Each general follows the commander's decision. In the event of messages received with conflicting information about what the commander's decision is, it follows that which is expressed in the greatest number of messages received.Messages from the same incoming sender must be ignored.In this scenario, since the sender cannot be forged, there is no way that the traitors send messages by passing through other loyal generals to try to trick them (a traitor go through another traitor, but that is of little use to them).There is also no means of a message sent by a loyal general to be corrupted on the way to his recipient. It is also not very interesting for a traitor to stop sending a message to some loyal general because it would reveal to this loyal general his condition as a traitor.Note that traitors can lie and provide messages with lists of false generals, out of order and/or with incorrect decisions.In this case, the messages between the loyal generals effectively say the following:From: CommanderTo: General 1I decided X.From: General 1To: General 2The commander decided X.From: General 2To: General 3According to General 1, the commander decided X.From: General 3To: General 4According to General 2, General 1 said the commander decided X.From: General 4To: General 5According to General 3, General 2 said that 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 will send No Messages in the first round. In the second round, each of the others No generals will send No. messages to the other generals. In the third round, each general will send 3 messages to the other generals (except those who already have the name in the list of generals of the message). In the fourth round, each will send No-4 messages. And so successively, completing n-m-1 rounds.After all the messages were collected, each general observes what each other general sent and decides what the opinion of each general is about the consensus to then understand what the consensus is.Proof that this algorithm works is quite complicated. However, it is not very applicable in practice, as it requires a very large number of messages to work out and needs all generals to 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, this will be of little value when any decision taken will be determined by the traitor.Scenario 2The main problem with scenario 1 is that traitors can lie. This can be solved if:The messages of the loyal generals are signed.It is not possible to forge false signatures.Messages with signatures that cannot be verified or unsigned are discarded by loyal generals.In practice, these restrictions are easily modeled by a digital signature scheme. See more https://pt.stackoverflow.com/a/194055/132 .With that signature scheme. You can create messages like this:From: General 4To: General 5I hate that what follows is true.From: General 3To: General 4I hate that what follows is true.From: General 2To: General 3I hate that what follows is true.From: General 1To: General 2I hate that what follows is true.From: CommanderTo: General 1I decided X.[Commander's signature][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 where it passed and will accumulate signatures. General 5, when you receive this, may attest to the authenticity of all signatures.If, for example, General 3 is a traitor and he tries to forge a false message, the commander's signatures, General 1 and General 2 will not be validated and by doing so he would quickly be unmasked.If the commander is a traitor and send "I decided X."for General 1 and "I've decided Y." for General 2, when General 1 and General 2 exchange messages, they will notice inconsistency, and since 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 allows to reduce the number of messages and eliminates the need for all generals to have to talk to all other generals, enough that all loyal generals can communicate with each other on paths where messages do not pass by any traitor (but as it is unknown who the traitors are, they will also receive and send messages). Still, this is a very complicated thing to manage properly.Problem applicationMany algorithms for cases of Byzantine generals require that the number of traitors does not reach a third of the total number of generals. There are circumstances for which it is enough 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 depend on the conditions of the problems.In bitcoin, for example, the generals represent the 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. Blockchain is a gigantic accounting book that stores everyone's set of transactions, and as each one has a copy, the idea is that when a transaction is announced, everyone registers them in their accounting books. The loyal generals are those who register transactions honestly in their blockchains and send messages to the other generals so that they also do so.In the case of bitcoin, the traitors would be those who try to forge non-existent transactions, spend money they do not have, create money from nothing or keep accounting books distinct from others. If there are a sufficient number of traitors acting in collusion in bitcoin, they can impose on honest users a fraudulent blockchain. One of the premises of bitcoin security is that the number of traitors is small enough.Several other situations are analogous to the problems of the Byzantine generals:drone networks controlled by artificial intelligence.P2P file sharing.Anti-missile air defense systems.In practice, loyal generals represent those legitimate users and software that aim to work as expected honestly for the benefit of all. The traitors are those who have dark interests, such as hackers trying to scam or abuse the system, fake software or that have been hacked, users wanting to troll, mock and hinder. Traitors can also be equipment that have defective parts and do not work properly or software that have 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 cannot be created a generic implementation without further details. However, still some exist, including in Java:Archistar https://github.com/Archistar/archistar-core and https://github.com/Archistar/archistar-bft . http://bft-smart.github.io/library/ . http://ball.askemos.org/ . https://github.com/tendermint/tendermint .I don't know the details of any of them and there must be other projects for that. But with that list, you should start.
