Byzantine Generals Problem#
If you see this name for the first time, you might think it's a problem encountered by a historical figure during a battle. But it's actually not. It's a problem proposed by a computer scientist to solve the problem of distributed network communication.
The Byzantine Generals Problem is a fault-tolerant problem in distributed peer-to-peer network communication proposed by Leslie Lamport in his paper of the same name.
Let's introduce the proposer of the problem briefly:
Leslie Lamport, an American computer scientist. He is also the developer of the typesetting system LaTeX. In 2013, he received the Turing Award.
Open Your Mind#
Before exploring the complex problem of the Byzantine Generals Problem, I would like to start with a small problem to open your mind (to adapt to the way of thinking).
There are two gatekeepers, A and B, and two doors, a and b. Our goal is to find the correct door among a and b, given that:
- We can ask A and B one question each.
- One of A and B tells the truth, and the other tells lies.
So, how do we ask the questions to find the correct door?
Take a moment to think about it. It's quite interesting, and actually, you only need to ask one question to get the answer.
Answer: Ask A: "Which door do you think B would say is the correct door?" (The correct answer is the other door that A didn't answer)
Achieving Consensus#
The example given for the Byzantine Generals Problem is quite complex, so let's use a simpler example to help you understand:
A group of good friends (generals) wants to discuss whether to go to the park together at 10 am tomorrow. However, they can only communicate privately one-on-one, and it is known that there are friends who want to cause trouble or disrupt their relationship (intentionally mislead). How can they achieve the goal of unified action (either going together or not going)?
For example, there are a total of 9 people, and they adopt the principle of majority rule. When four people agree to go and four people disagree to go, the troublemaker tells the four who agree that they agree to go, and tells the four who disagree that they disagree to go. Both sides think they have won, which will result in the failure of the goal.
The story mentioned above can be mapped to a computer system, where the generals become computers and private chats become the communication system. Although the above problem involves electronic decision support and information security, it cannot be solved purely by cryptography and digital signatures. Circuit errors can still affect the entire encryption process, which is not the problem that cryptography and digital signature algorithms are solving. Therefore, computers may submit incorrect results and may also lead to incorrect decisions.
In blockchain, if consensus cannot be reached, there will be problems such as forks and system crashes. When a consensus problem occurs in a chain, it will cause a crisis of trust and a fatal blow to the chain. Therefore, consensus algorithms in blockchain are the underlying foundation for the development of the ecosystem.
Verbal Agreement#
In fact, consensus algorithms are constantly improving, and very clever people are constantly proposing novel solution ideas. In the paper where this problem was proposed, Leslie Lamport has already proposed two solutions, and today I will share the solution of verbal agreement.
The following content is not the original solution, but an expression based on personal understanding. If there are any errors, I hope for understanding.
Definition:
- Divided into two categories: good people (desire for unity) and bad people (desire for disunity).
- The person who proposes the plan automatically becomes the leader (general).
Goals:
- If the leader is a good person, ensure that all good people execute the leader's proposal.
- Ensure that all good people maintain consistent execution.
Failed Case#
Continuing with the example of going to the park, this time there are 3 people, a, b, and c, discussing whether to go to the park tomorrow, with one person being a troublemaker.
b proposes the idea of going to the park and becomes the leader.
(There is a diagram below)
Possibility 1#
b, the leader, is not a troublemaker, and c is the troublemaker.
a receives the idea of going to the park from b, but doesn't know if b is a good person, so a asks c: "What does b propose, to go or not to go?" c responds with "not to go," so a receives one vote for going and one vote for not going. a knows that either b or c is a troublemaker, but doesn't know who.
So consensus cannot be reached: failure
Possibility 2#
b, the leader, is a troublemaker, and a and c are good people.
a receives the proposal to go to the park from b, and c receives the proposal not to go from b. At this point, a and c exchange information and both receive one vote for going and one vote for not going.
So consensus cannot be reached.
Successful Case#
This time there are 4 people, a, b, c, and d, discussing whether to go to the park tomorrow, with one person being a troublemaker.
Possibility 1:#
The leader c is a good person and proposes not to go to the park, and d is a troublemaker.
After a receives the idea of not going to the park, a asks b and d for their opinions as leaders. The responses are "not to go" (b) and "to go" (d).
So a receives (not to go, not to go, to go), and the majority is not to go. The same conclusion applies to b, who also decides not to go.
In the end, a, b, and c all don't go, achieving goal 2 and following the leader's command, achieving goal 1.
Possibility 2:#
The leader c is a troublemaker and tells a and b to go, and tells d not to go.
After a receives the proposal to go, a asks b and d for their opinions as leaders. The responses are "to go" (b) and "not to go" (d).
So a receives (to go, to go, not to go), and the majority is to go. The same conclusion applies to b, who also decides to go.
After d receives the proposal not to go, d asks a and b for their opinions as leaders. The responses are "to go" (a) and "to go" (b).
So d receives (not to go, to go, to go), and the majority is to go.
In the end, a, b, and d all agree to go, achieving goal 2. Since the leader is a troublemaker, goal 1 is not considered.
In fact, when Leslie Lamport proposed the verbal agreement, he already gave the conclusion that if there are n participants and m of them are troublemakers, consensus can only be reached when n > 3m. In other words, when there are 2 troublemakers, it requires a total of 7 people to reach consensus. The specific deduction process can be seen in the video by Professor Li Yongle, which is very interesting.
Of course, in blockchain, both Bitcoin and Ethereum use the PoW (Proof of Work) consensus mechanism, which solves the consensus problem remarkably well. After more than a decade of stable operation, it has proven the feasibility of this method. However, PoW also has many criticisms, so it would be interesting to study the underlying logic of PoW in detail when there is an opportunity.