Before Satoshi Nakamoto created Bitcoin, he needed to solve the Byzantine Generals problem in a decentralized network. The existing algorithms and protocols are all solutions based on centralized networks. Satoshi Nakamoto creatively used the POW consensus algorithm to solve this problem, so what is the Byzantine Generals' problem?
Long, long ago, Byzantium was the capital of the Eastern Roman Empire. At that time, the Roman Empire had a vast territory, and for defense purposes, each army was separated by a long distance, and the generals could only rely on messengers to transmit messages. When going to fight, all the generals in the Byzantine army must reach a consensus in order to better win the victory. However, there may be traitors within the army, disrupting the decisions of the generals. At this point, with members known to be unreliable, the remaining loyal generals need to reach a consensus without being influenced by traitors or spies. This “Byzantine” is not Byzantine, it has a close connection with the blockchain
We can easily find 2 problems from above
- Is the information source of the messenger reliable? In computer networking, we can refer to the stability of my network channel.
- Did all the generals in the army achieve a certain goal (unanimously attack or retreat), and how to achieve it in the event of a traitor? In a distributed computer network, how to ensure the consistency of all computers, but also allow the failure or error of the node computer.
American computer scientist (Leslie Lamport proposed the Byzantine Generals problem in 1982) Computers can be distributed all over the world, we call them distributed nodes, distributed nodes may fail, go down, or malicious nodes (hackers), so how do we maintain consistency, faithful computers maintain the same, correctness.
Oral Agreement: General-Adjutant Model
1: Loyal Adjutant: Follow the same order (consistency) (either attack together or retreat together)
2: Accuracy: If the general is loyal, all loyal lieutenants must carry out his orders
Suppose m=the number of malicious people (traitors) ,n=the total number of people (the total number of computer nodes) when n>3m this event can be solved, You may ask why n>3m, you can see the below example
m=1 n=3
C (commander) will give orders to two adjutants 1 and 2, but 2 is a traitor, so there will be a problem at this time, the general will tell 1 and 2 to attack respectively, but 1 will not attack immediately after receiving the order because he does not sure whether the general is a traitor or not, so 1 will ask 2 what the order is. Since 2 is a traitor, even if 2 receives an order to attack, it will tell 1 that it has received an order to retreat. So at this time, 1 will be very confused, because he received the order from the general to attack and 2 tells him to retreat, so he is not sure which of the general and 2 will be the traitor. So 1 at this time is very confused and the situation is unsolved.
Suppose the general is a traitor
1 and 2 are both loyal, the traitor is the general will give two different orders, telling 1 to attack, and telling 2 to retreat, at this time 1 and 2 will communicate with each other, because 1 and 2 received different orders, so they will doubt The general and one of them would be a traitor, so both examples are unsolvable.
If n>3m the problem is solvable
Suppose m=1,n=4 (a general and 3 adjutants, one adjutant is a traitor)
The general told the three adjutants that the orders were to Attack, and the three adjutants would communicate with each other. The result of the communication between 1 and 2 was an Attack. Because 3 was a traitor, when communicating with 1 and 2, they would be told that the order they received was Retreat.
So we can conclude that the orders received by 1 are (attack, attack, retreat) v1=(A, A, R) So number 1 will choose to attack. Because 2 is also a loyal adjutant, so the order he received (attack, attack, retreat) makes №2 also choose to attack.
Suppose the general is a traitor and the three adjutants are loyal
If the general is a traitor, so now just need to satisfy the consistency and the loyal adjutant obeys the same order, regardless of whether the order is issued by the general or not. For example, if the traitor general told 1 and 2 to attack, and 3 to retreat, then they would communicate. 1 would tell 2 that the order he received was an attack order, and 2 would tell 1 to accept. The order received is an attack order, 2 will tell 3 that it is an attack order. 3 will tell 2 that it has received an order to retreat, 1 will tell 3 that it has received an attack order, and 3 will tell 1 that it has received an order to retreat. So the set of orders received by 1 is (attack, attack, retreat), the set of orders received by 2 is (attack, attack, retreat), and the set of orders received by 3 (retreat, attack, attack) So this All three adjutants will choose to attack, so they reach an agreement. The three adjutants can reach an agreement. Because the order issued by the general is chaotic, it doesn’t matter which one to execute, just reach an agreement.
The above example is a simple case where there is only one traitor, but what if the number of traitors is greater than one? m=2, so how are we supposed to do now?
Since m=2, n is at least 7, and if it is less than 7, there is no solution. At this time, an idea called recursion will be used, which is very common in computers. Eg: What happens when the camera is facing you, and as a result, you use the camera to face the computer screen, at this time, you will find that one computer is set to another computer, and then another computer is set, we can think it is a kind of nesting.
First, a general will send an attack order to 6 adjutants, because there are two traitors now, let’s assume that the general is not a traitor, and assume that 5 and 6 are traitors (below pic I didn't draw the connection lines because looks so messy :)
When 1 receives the order to attack, he will not go to attack immediately, because he is not sure whether the general is a traitor or not, so he will ask 2 what is the order you received from the general? But he wouldn’t believe 2 either, because he wasn’t sure if 2 was a traitor too. So it will continue to ask 3, 4, 5, 6. Q2 tells you what order he received, we will look at the table next
First adjutant №1 received an attack order from the general, so A stands for attack, so A will ask everyone about the order received, because №2 is faithful, so the order he received is also an attack, adjutant №3 It is also loyal, and will tell the truth about №2, №4 is also loyal, and №5 adjutant is a traitor and nonsense, so the given is not necessarily what so we replace it with a in the table. Adjutant №6 is also a traitor, so he is also talking nonsense, and he doesn’t necessarily say anything, so we use b in the table. Therefore, the information obtained by №1 will find that there are three people in the statement of Adjutant №2 who say that the order obtained by Adjutant №2 is A, and two people do not know what they are talking about, so we take the maximum principle, In the end, we decided that the order received by the adjutant 2 was indeed an attack (take the maximum principle), and we will do the same thing again, adjutants 1, 2, 3, and 4, the order received is A, and the orders received by adjutants 5 and 6 are uncertain. , so in the first column we take the maximum value A = attack, so the final result is that 1, 2, 3, 4 adjutants will choose to attack while ensuring consistency and accuracy.
The above problems do not take into account the network delay. On the actual Internet, there is network delay, so a simple and practical Byzantine fault tolerance algorithm called PBFT was born, and this algorithm can still be used in the case of network delay. Guarantee the consistency and accuracy of the majority of loyal nodes in the presence of a few nodes and faulty nodes. For example, Satoshi Nakamoto proposed Bitcoin. The core problem of blockchain is to maintain consistency. How to maintain consistency? We can define a consensus algorithm as the mechanism by which a blockchain network reaches consensus. The most common examples are Proof of Work (PoW) and Proof of Stake (PoS). Compared with the Byzantine general problem, this increases the cost of the traitor. If you don’t have any cost, malicious nodes on the network can spread freely. The Bitcoin protocol specifies the main rules of the system, and the proof-of-work consensus algorithm describes how to follow these rules to reach consensus (for example, during the verification and validation of transactions).
Although the concept of proof-of-work predates digital currencies, Satoshi Nakamoto modified the original version and developed an improved proof-of-work algorithm that can generate Bitcoin as a Byzantine fault-tolerant system.
Note that this proof-of-work algorithm is not fully resistant to Byzantine failures, but due to the high-cost mining process and underlying encryption technology, proof-of-work has proven to be one of the most secure and reliable methods in blockchain networks. In this sense, the proof-of-work consensus algorithm devised by Satoshi Nakamoto is considered by many to be one of the most brilliant solutions to Byzantine fault tolerance.
Join Coinmonks Telegram Channel and Youtube Channel learn about crypto trading and investing
