Byzantine general problem bitcoin
imagine that in Byzantine times, there was a rich city-state with all kinds of gold, silver, jewelry, silk and satin, and its Lord Doraemon enjoyed all the luxury and glory. On the outskirts of the city-state, four Byzantine Generals, Daxiong, panghu, Xiaofu and Jingxiang, coveted Doraemon's wealth, so they decided to join hands to capture Doraemon's city-state. According to the strength comparison between the two sides, more than half of the generals must attack at the same time to defeat the enemy, so the winning condition is that at least three of the four can agree on the attack time. What are the odds of the four generals
the answer to this question depends on the cooperation mode of the four people. If it is a centralized system and there is an alliance leader, such as panghu (equivalent to a central server), then there is no doubt about their victory, because it is very easy to reach an agreement on the attack time. As long as panghu calls Daxiong, Xiaofu and Jingxiang to have a meeting to discuss it, Even if we have different opinions, panghu can make a final decision. Now let's go back to the assumption of Byzantine Generals. In a distributed network without trust, what are the odds of four generals winning< br />
?
first of all, e to the lack of trust between the four generals, the possibility of gathering in a small dark room for a conspiracy meeting is ruled out (what if they are kidnapped by panghu in a small dark room?); Secondly, since there is no leader, the opinions of all four people will be equally valued. In this case, the four generals could only negotiate the attack time by sending messages between their camps by messenger. For example, if Daxiong thinks 6 a.m. is a good time to launch an attack, he will send messengers to tell panghu, Xiaofu and Jingxiang their opinions. At the same time, panghu may think it's better to launch a surprise attack at 9 p.m., Xiaofu prefers to launch an attack at 3 p.m., and Jingxiang hopes that it will be 10 a.m., and the three of them will send their own messengers at the same time. In this way, after the first round of communication, each of the four generals had four attack times to choose from, and each of them had to inform the other three of their chosen time in the next round of communication. Because four people make decisions independently, there are 256 possible final choices. Only when more than three people choose the same time can consensus be reached, and there are only 64 such results, that is to say, the probability of reaching consensus is only 1 / 4. This is only the case of four generals. What if the number of generals is 10, 100 or 1000? With a little calculation, we can see that as the number of people increases, the hope of reaching a consensus will become increasingly dim
change the general in the above example into the node in the computer network, the messenger into the communication between nodes, and the attack time into the information that needs to reach a consensus. Then you can understand the dilemma described by the consensus problem. The ability to reach a consensus is self-evident for a payment system. If you remit a sum of money to your family to buy a car and go to the bank the next day for verification, the counter will tell you "about how much money you remit, there are three versions of records in our system". Obviously, you dare not deposit money in such a bank. Before the emergence of bitcoin, the consensus problem is difficult to be solved perfectly. In order to reach a consensus, we need to adopt a centralized system (unless the nodes meet certain conditions), and in order to decentralize the consensus, we can't guarantee it. So how does blockchain technology solve this problem Pay attention to the official account weoption, reply to "block chain", you can view the full text.
Byzantium, located in Istanbul, Turkey, is the capital of the Eastern Roman Empire. Because of the vast territory of Byzantine Roman Empire at that time, for the purpose of defense, each army was separated far away, and the generals could only rely on messenger to transmit information. During the war, all generals and adjutants in the Byzantine army must reach a consensus to decide whether there is a chance to win before attacking the enemy camp. However, there may be traitors and enemy spies in the army, which will influence the decisions of the generals and disrupt the order of the whole army. When consensus is reached, the result does not represent the majority opinion. At this time, in the case of known members of the rebellion, the remaining loyal generals without the influence of traitors how to reach an agreement, Byzantine problem formed
The original description of Byzantine problem is that n generals are separated in different places, and loyal generals hope to reach an agreement on a certain order through some agreement (such as attacking together or retreating together). But some of the betraying generals would send the wrong message to prevent loyal generals from reaching agreement on orders. Lamport proved that when the total number of generals is more than 3m and the defectors are m or less, loyal generals can reach agreement on orders< In order to meet the above requirements, the following two conditions must be met:
1. Every two loyal generals must receive the same value V (I) (V (I) is the order of the ith general)
2. If the ith general is loyal, the order he sends is the same as the V (I) received by every loyal general
in order to simplify the above model, We use the form of a general sending an order to multiple adjutants to prove that the general sending the order is called the starter, and the general receiving the order is the adjutant. Then the above two conditions can be expressed as:
IC1. All loyal adjutants obey the same order
IC2, Then all loyal adjutants obey the command of the commander (the general giving the command)
special note: only one general sends the command at a time, and send it to n-1 adjutants. M stands for the number of traitors, because the total number of generals is n, so the total number of adjutants is n-1. In IC2, adjutant's compliance actually means that the loyal general can correctly receive the command message from the loyal general. If there are m traitorous generals, the total number of generals must be more than 3m + 1. The following are some default conditions in the process of oral message delivery:
A1. Each sent message can be delivered correctly
A2. The information receiver knows who sent the message
A3. He can know the missing message
A1 and A2 assume that there is no interference in the communication between the two generals, There will be no defectors blocking the sending of messages (truncation) and no defectors forging messages (forgery). That is, every general can send his message to every other general without error In the next section, we don't need this necessary condition)
we define the oral message algorithm OM (m). For all non negative integers m, each initiator sends commands to n-1 adjutants through OM (m) algorithm. The following will show that the OM (m) algorithm can solve the Byzantine Generals Problem when there are at most M traitors and the total number of generals is 3M + 1 or more Considering the actual network application environment, the original text uses the received value instead of the received command, this paper does not modify)
the algorithm defines a function: majority (COM1, com2,..., CoMn) is equal to the majority command
OM (0) algorithm
(1) the initiator sends his command to each adjutant
(2) each adjutant uses the command he received from the starter, or defaults to the retreat command, if no command is received
OM (m) algorithm
(1) the initiator sends his command to each adjutant
(2) for each I, VI is the order received by each adjutant I from the originator, and if no order is received, it is the withdrawal order. Adjutant I sends VI to n-2 adjutants as the initiator in OM (m-1)
(3) for each I, and J / NEQ I, VJ is the command sent by adjutant I from adjutant J in step (2) (using OM (m-1) algorithm). If the command from adjutant J in step (2) is not received, it is the retreat command by default. Finally, the adjutant I uses the priority (V1,..., vn-1) to get the command
next, consider the case of n = 4, M = 1:
1. When adjutant D is a traitor
in the first step, the initiator a executes the algorithm OM (1) and sends his command to three adjutants B, C, D. all three adjutants receive the command correctly
in the second step, every adjutant who receives the command executes the algorithm OM (0) as the initiator and forwards the command he receives to the other adjutants. Because adjutant D is a traitor, the message he sends to adjutants B and C may be false. Adjutants B and C decide the command according to the priority function
similarly, such a treacherous adjutant D could not interfere with the decision of the starter. Let's see if the starter is a traitor
2. The initiator is a traitor and the other adjutants are loyal
Step 1: initiator a sends different commands to adjutants B, C and D. in fact, an attacker sends inconsistent values (e.g., 0 or 1) to different parties in an attempt to disturb the adjutants to make a consistent decision
the second step: after the adjutant receives the order, he changes himself into the initiator and executes OM (0) to send the order to all the adjutants. Each adjutant can still reach an agreement through the majority voting algorithm
the paper then proves that OM (m) algorithm can satisfy any m, and introces a lemma (proof by inction):
lemma 1: for any m and K, if there are more than 2K + m generals and K traitors at most, then OM (m) algorithm can satisfy IC2 (review IC2 means that if the general is loyal, all adjutants obey the general's orders)
proof: when m = 0, OM (0) satisfies IC2 when the general is loyal. When M & gt; At 0, the general first passes the command to n-1 adjutants, and then each adjutant performs OM (m-1) algorithm on n-1 generals. Because n & gt; 2K + m (in lemma, the number of generals is greater than 2K + m), so n-1 & gt; 2k+(m-1) >= 2K (that is, the total number of adjutants in each round is not less than twice that of the traitors), so that the commands received by the loyal adjutants in each round of OM (m-k) algorithm are priority (V1, V2,..., V (n-1)), and the commands sent by the loyal adjutants are greater than or equal to half
then solve the problem of Byzantine Generals
theorem 1: for any m, if there are more than 3m generals and at most M defectors, the algorithm OM (m) satisfies the condition IC1 and IC2
proof: through the inctive proof of M, we prove OM (m) M & gt by assuming that OM (m-1) holds; 0 Consider first that the general who gives the order is loyal. If K is set to m in the lemma, then OM (m) satisfies IC2, and IC1 satisfies IC1 even if the commanding general is loyal
then consider that one of the M defectors is the starter, and only M-1 adjutants are defectors at most. Because there are 3M generals, the total number of adjutants is more than 3m-1, and 3m-1 & gt; 3(m-1) Therefore, it is assumed that OM (m-1) satisfies IC1 and IC2 (up to 3 (m-1) generals and up to M-1 traitors). Then, any two loyal adjutants J get the same command VJ in OM (m-1), then in OM (m) algorithm, every loyal adjutant will receive (V1, V2,..., V (n-1)), we can see that the conditions IC1 and IC2 are satisfied
after reading this proof, I was confused ~ ~ ~ ~ I drew a picture to see how the Lamport proved:
besides meeting the three requirements of oral message A1-A3, the signature message should also meet the following A4:
A4 (a) the signature cannot be forged, Once tampered, it can be found
(b) anyone can verify the reliability of the general's signature
a choice () similar to the above major () function is defined to determine the choice of the adjutant: 1. When the set V contains only one element V, then choice (V) = V; 2. choice(o)=RETREAT
based on A4 and choice (), we give SM (m) method:
SM (m) algorithm
initialize VI = empty set
(1) the general signs the command and sends it to each adjutant
(2) for each adjutant I:
(a) if adjutant I receives V: 0 message from the originator and has not received any other command sequence, Then:
(I) make VI {V}
(II) send V: 0: I to all other adjutants
(b) if adjutant I receives the message V: 0: J1:...: JK and V is not in the set VI,
(I) add V to VI
(II) if K & lt; m. Then, send V: 0: J1:...: JK: I to each adjutant who is not in J1,.., JK
(3) for each adjutant I, when no message is received, follow the command choive (VI)
several instructions of the algorithm:
the third step of the algorithm does not explain how the adjutant judges that there is no new message, There are two solutions: one is to ask each adjutant to sign and forward the message after receiving the message, or send a notice that he will not send the message; The second is to set a time-out period. If the message has not been received in this period, the message will not be received any more
in algorithm SM (m), having the adjutant sign is to confirm that he has received the message (it's a bit like sending a document to each leader for review). In SM (1), the adjutant does not need to sign when he receives the message, because he does not need to forward it to other adjutants< Theorem 2: for any m, when there are at most M defectors, the algorithm SM (m) solves the Byzantine general problem
proof: firstly, it proves that IC2, if the originator is loyal, then all the adjutants must receive the same order, because the signature cannot be tampered, and IC1 is satisfied. It is proved that IC1 only considers the case that the originator is a traitor (in retrospect, IC1 means that all loyal adjutants execute the same command). IC1 requires that two loyal adjutants (I, J) must receive the same command set VI and VJ, that is, each V in VI is in VJ. There are two situations. One is that when the adjutant I receives the sequence of V command, he adds it to VI and sends it to adjutant J, where j saves the command v; Second, adjutant I received the command V: 0: J1:...: JK: I, in which Jr = J, so it can be seen from A4 that adjutant J also received the command. If not,
k & lt; m In this case, I send a message V: 0: J1:...: JK: I to adjutant J, then J must receive v This feeling is similar to above)
k = M. The starter is a traitor, and only M-1 adjutants are traitors at most. Therefore, at least one sequence, j 1,..., j m, is loyal. Then J must receive the value V from the loyal adjutant sequence, so adjutant J receives v
proof complete