Read the Byzantine General

Author | Yu Liebing

Editor | Carol

Production | Blockchain Camp (ID: blockchain_camp)

The Byzantine Generals Problem provides a contextual description of distributed consensus problems and was first published in 1982 by Leslie Lamport et al. The paper "The Byzantine Generals Problem" also provides two algorithms to solve the Byzantine general problem:

• A solution with oral message;
• A solution with signed message.

paper:

https://www-inst.eecs.berkeley.edu/~cs162/sp16/static/readings/Original_Byzantine.pdf

• Technical Primer | Explore the key details of BFT and Libra's Consensus components
• Crypto Custody Company Copper Completes Series A Financing, MMC Ventures, LocalGlobe Participate
• Blockchain helps public welfare charity research report: feasibility analysis, application scenarios, challenges and prospects

These two algorithms are described in detail later in this article. In fact, the General Byzantium problem is the most complex fault-tolerant model in the field of distributed systems. It describes how to make a distributed system agree in the presence of malicious behavior (such as message tampering or forgery). It is an important basis for our understanding of distributed consensus protocols and algorithms.

Byzantine General Problem Description

The Byzantine General question describes such a scenario:

Figure 1. General Byzantium issue

Several divisions of the Byzantine Empire army were stationed outside the enemy city, and each division was commanded by its own general. Generals can only communicate with each other through messengers. After observing the enemy's situation, they must formulate a common action plan, such as attack or retreat , and only win when more than half of the generals jointly launch an attack. However, some of these generals may be traitors, trying to prevent loyal generals from agreeing on a plan of action. To make matters worse, the messengers responsible for messaging may also be traitors, they may tamper with or falsify the message, or they may lose it.

In order to understand the question of Byzantine generals in depth, we take the problem of three generals as an example. When the three generals are loyal, a consistent action plan can be determined by voting. Figure 2 shows a scenario, namely General A, B can launch an attack by observing the military situation of the enemy and combining his own situation, while General C observes the enemy The military situation and the judgment based on its own situation should retreat. In the end, the three generals voted to get the attack: retreat = 2: 1, so they will launch an attack together to win. For the three generals, each general can perform two kinds of decisions (offensive or retreat), there are 6 different scenarios, Figure 2 is one of them, and the other 5 scenarios can be simply pushed, Vote on all three generals to agree on a plan of action.

Figure 2. Scenario where all three generals are loyal

When one traitor exists among the three generals, it will likely disrupt normal battle plans. Figure 3 shows a scenario where General C is a traitor. He sends different messages to General A and General B. In this scenario, General A gets an attack by voting: retreat = 1: 2, and eventually retreat will be made. Plan; General B gets the offense by voting: Retreat = 2: 1, and will eventually make an offensive action plan. Only General B launched the attack and was defeated.

Figure 3. Two loyalty and one rebellion scene

In fact, in the case of a traitor in the three generals, it is impossible to always reach a consistent plan of action. Detailed proofs can be found in the paper by Leslie Lamport. In addition, the paper gives a more general conclusion: if there are m rebels, then at least 3m + 1 generals are needed to finally reach a consistent action plan.

solution

Leslie Lamport gives two solutions to the Byzantine general problem in the paper, namely a solution with oral message and a solution with signed message.

1.Message-based solution

First, the definition of Oral message is as follows:

• A1. Any message that has been sent will be correctly communicated;
• A2. The receiver of the message knows who sent the message;
• A3. Absence of messages can be detected.

Based on the definition of the message, we can know that the message cannot be tampered with but can be forged. Based on the derivation of the scenario in Figure 3, we know that when there is a rebel, we must add three more loyalty to achieve the final consensus. In order to deepen our understanding, we will use the scenario of 3 loyal and 1 rebels to develop a message-based solution. In a message-based solution, the general who sends the message first is called the commander, and the remaining generals are called deputies. For the scenario of 3 loyalty and 1 rebellion, two rounds of combat information negotiation are required. If no combat information is received, the default retreat. Figure 4 is a scenario where the commander is a loyal general. In the first round of operational information negotiation, the commander sent an offensive message to three deputies; in the second round, the three deputies again conducted operational information negotiation. B and B were loyal generals, so they sent offensive messages to the other two deputies according to the commander's message, while General C was a rebel general. In order to disrupt the battle plan, he sent two other deputies to retreat. In the end, Commanding General, General A and B reached a consensus attack plan and could win.

Figure 4. Scenario where the commander is a loyal general

Figure 5 is a scenario where the commander is a rebel. In the first round of operational information negotiation, the commander sent a retreat message to General A and B, but sent an attack message to General C in order to disrupt the decision of General C. In the second round, since all deputies were loyal generals, the messages from the commander were correctly sent to the two remaining deputies. In the end, all loyalists could agree on a plan to withdraw.

Figure 5. Scenario where the commander is a rebel

As mentioned above, for the message-general Byzantine general issue, if the number of generals is m and the number of generals is not less than 3m + 1, then a consensus action plan can be reached. It is worth noting that in this algorithm, the number of rebels m is known, and the number of rebels m determines the number of recursions, that is, the number of rebels m determines the number of rounds for negotiation of combat information. If there are m Rebels need to conduct m + 1 rounds of operational information negotiation. This is also the reason why two rounds of operational information negotiation are needed when there is a rebel.

2.Signed message solution

Similarly, the definition of a signed message is based on the definition of a message message with the following two additions:

• A4. The loyal general's signature cannot be forged, and any changes to the content of his signed message will be found;
• A5. Anyone can verify the authenticity of the general's signature.

Based on the definition of a signed message, we can know that a signed message cannot be forged or tampered with. In order to understand the signature message type solution in depth, we also use the three generals problem as an example to derive. Figure 6 is the scene where loyal generals took the lead in initiating combat negotiations. General A took the lead in sending offensive messages to General B and C. Once general C has tampered with messages from General A, General B will find that the combat information has been tampered with by General C. , General B will execute the message sent by General A.

Figure 6. The loyalty first initiates operational negotiations

Figure 7 is the scene where the rebel generals initiated the battle negotiation. The general rebel General C took the lead in sending misleading combat information. Then General A and B will find that the combat information sent by General C is inconsistent, so they are judged to be rebel generals. It can be processed before negotiation of operational information.

Figure 7. Betrayal takes the lead in combat negotiations

Signed messaging solutions can handle any number of rebel scenarios.

to sum up

In the field of distributed systems, the correspondence between the role of the Byzantine General and the computer world is as follows:

• General, corresponding computer node;
• Loyal generals, corresponding to well-run computer nodes;
• Renegade general, computer node under illegal control;
• The messenger was killed, and the communication failure caused the message to be lost;
• Messengers are replaced by spies, communications are attacked, and attackers falsify or falsify information.

As mentioned above, the Byzantine General Problem provides a contextual description of distributed consensus problems and is the most complex model in the field of distributed systems. In addition, it also provides a framework for us to understand and classify the many distributed consensus protocols and algorithms available. The existing distributed consistency protocols and algorithms can be divided into two categories:

One is the Crash Fault Tolerance (CFT) algorithm, which is a non-Byzantine fault tolerance algorithm. It solves the consensus problem in the scenario where there is a fault in the distributed system but there is no malicious attack. That is, in this scenario, there may be message loss and message duplication, but there is no scenario where the message is tampered or forged. Generally used in distributed systems in LAN scenarios, such as distributed databases. Common algorithms that fall into this category include Paxos algorithm, Raft algorithm, and ZAB protocol.

One type is the Byzantine fault-tolerant algorithm, which can solve the problem of consensus in distributed systems with both faults and malicious attacks. It is generally used in distributed systems in Internet scenarios, such as in the digital currency blockchain technology. Common algorithms that fall into this category include the PBFT algorithm and the PoW algorithm.

After reading this article, what is your opinion on these two solutions? Welcome to discuss with us in the comment area!

We will continue to update Blocking; if you have any questions or suggestions, please contact us!