What is the Byzantine General question
Students in contact with blockchain, how many have heard of the Byzantine general problem, often see or hear a certain blockchain using a certain algorithm to solve the Byzantine General problem, so what is the Byzantine General problem?
What is the Byzantine general problem
Also known as the “Byzantine fault tolerance”, “Byzantine general problem”. The Byzantine General problem is a famous example that Leslie Lamport (Turing 2013) abstracted from a paper describing the Distributed Consensus problem.
This example goes something like this:
The Byzantine Empire wanted to attack a powerful enemy, so it sent 10 armies to surround it. This enemy was no match for the Byzantine Empire, but it was strong enough to withstand a simultaneous attack by five regular Byzantine armies. The 10 armies attacked simultaneously under separate siege. There was no chance of any one army attacking alone, unless at least six armies (more than half) attacked simultaneously to take the enemy country. They were scattered around the enemy country and relied on the signalmen to communicate with each other on horseback to negotiate the intention of attack and the time of attack. The trouble with these generals is that they are not sure if any of them are traitors, who may change their intentions or timing of attack. In this state, the Byzantine generals were able to ensure that more than six armies could attack together at the same time to win the battle?
The Byzantine general problem did not consider whether the signalman could be intercepted or could not convey the message, that is, there was no problem with the channel of message transmission. Lamport has demonstrated the impossibility of trying to achieve consistency through messaging over unreliable channels where messages can be lost. Thus, in the study of the Byzantine general, it was assumed that there was no problem with the channel.
Problem analysis
The complexity of the problem may not be understood from the above explanation alone, but let’s analyze it briefly:
-
First, in the absence of A traitor, suppose A general A made an attack proposal (e.g. : attack tomorrow at 1 PM, would you join us?). The signalman tells the other generals that, with luck of fortune, he has received the consent of more than six other generals to attack. Unfortunately, other generals are also proposing different attacks at this time (e.g., attack tomorrow at 2pm, 3pm, will you join us?). Because of the time difference, different generals may receive (and approve) different attack proposals, which may result in proposal A having 3 supporters, proposal B having 4 supporters, proposal C having 2 supporters, and so on.
-
“A little more complexity, in the case of A traitor, A traitor to the different general issued A different offensive proposal (notice A attack tomorrow at 1 PM, notify B tomorrow at 2 PM attack, etc.), A traitor would probably agree with multiple attack proposed (i.e. agree attack at 1 PM and 2 PM).
A traitor who sends inconsistent offensive proposals is called a Byzantine error, and the ability to deal with Byzantine fault tolerance is called BFT.
I think you get an idea of the complexity of this problem.
Satoshi nakamoto’s solution
Before the emergence of Bitcoin, the problem of distributed system consistency was mainly solved by Lamport’s Paxos algorithm or its derivative algorithm. Paxos-like algorithms are only suitable for centralized distributed systems where there are no dishonest nodes (no false error messages are sent, but message delays are allowed in the event of network failure or downtime).
Satoshi nakamoto creatively introduced “POW: Proof of Work” in Bitcoin to solve this problem. If you are interested, you can read the Proof of Work further. Proof-of-work increases the cost of sending messages and reduces the rate at which nodes send messages so that only one (or few) nodes are broadcasting at a time and that they are signing up for the broadcast. The process is similar to general A telling other generals (B, C, D…) Initiate an offensive proposal like Generals B, C, D… Upon seeing general A’s signed proposal of attack, an honest general would immediately agree to the proposal of attack rather than launch A new one of his own.
This is how the bitcoin network achieves consensus among individual blocks (ledgers).
Understanding how individual blocks achieve consistency makes it easier to understand if the entire blockchain (the ledger) is in agreement. Let’s change the general question slightly: Assume that capturing A castle to attack many times, before each attack proposal must be based on most times put forward under the victory of the attack (only in this way the enemy has been the biggest loss. And we attack the possibility of victory is larger), after this contract, the general attack on receipt of A proposal, will check the proposal is based on the most victories, General A will not agree to such A proposal if it is not (based on the most wins), and if it is, General A will make A note of the proposal.
This is the longest chain of the Bitcoin network.
Economic analysis
Do work certificate is equivalent to enhance the traitor (the cost of issuing false block), under the work certificate, only the first node to complete proof can broadcast blocks, competition difficulty is very big, need a high force, if not its work force has frittered away (work force is the need to cost), if there is such a work force as honest nodes, There’s also a lot of money to be made (that’s what miners do), and there’s actually no incentive to defect, and the system is more stable.
Many have criticized proof-of-work as a huge waste of electricity, prompting a search for new mechanisms to solve the consensus problem: POS: Proof of Stake is one example. From the perspective of the Byzantine general problem, it also raises the cost of being a traitor, because the account needs to have a large balance in the first place to have a greater chance of broadcasting blocks. POS is not the point of this article, but it will be covered later.
The core of consensus algorithm is to solve the Byzantine general problem (distributed network consistency problem).
Further reading
The Byzantine Generals Problem
Dynamic And Simple Blockchain – Learn blockchain systematically and build the best blockchain technology blog.
Dynamic Planet Of My Knowledge answers blockchain technology questions. Welcome to join the discussion.
Aid To The Public account “Deep And Simple Blockchain Technology” To obtain blockchain technology information for the first time.
