Students in contact with blockchain, how many have heard of the Byzantine general problem, often see or hear: XXX blockchain uses XXX algorithm to solve the Byzantine General problem, so what is the Byzantine General problem? “Blockchain 100 Lectures” today talk to you about what is the Byzantine general problem.

1

Question of the Byzantine general

This Problem is proposed by Leslie Lamport et al. In The paper The Byzantine Generals Problem, part of The text is as follows:

We imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching agreement.

** It is a well-known example of the problem of consistency in distributed systems. ** It is still difficult to understand this problem through literal translation of this paper. Appropriate supplements or explanations can be added to make a better interpretation.

Imagine the Byzantine Empire in the Middle Ages, with its vast wealth and its long-established neighbors. But Byzantium was so walled and impenetrable that no single neighbor could successfully invade. Any invasion by a single neighbor will fail and may itself be invaded by other neighbors. The Byzantine Empire was so well defended that it needed at least half of its neighbors to attack at the same time.

However, if one or more of the neighbors themselves agree to join in the attack, but the actual process betrays, the invaders may all be annihilated. So each side treaded cautiously, wary of trusting its neighbour. (Actually, this is a little different from the original description, but it is easier to understand.)

In the Case of Byzantium, the most important thing for the neighboring countries was how all the generals could reach a consensus to attack the Byzantine Empire.

Reaching consensus is not as simple as sitting down and having a meeting. Some generals are deeply scheming and duplicitous. If there is a traitor, all kinds of problems may arise:

  • The traitor may delude some generals into taking offensive action.

  • A traitor may incite other generals to action.

  • A traitor may confuse other generals by confusing them with inconsistent information.

We assume here:

There are generals A, B and C, and when A gives the order to attack, B, if he is A traitor, may tell C that he has received the order to “retreat”. At this time, C receives an “attack” and a “retreat”, so C is confused by the information and does not know what to do.

If “A” is A traitor. He tells B to “attack” and C to “retreat”. When C tells B that he has been ordered to “retreat”, B is unable to agree with C because he has been ordered to “attack”.

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.

For this reason, in a system with only three characters, the Byzantine problem becomes unsolvable as long as one of them is a traitor, i.e. the number of traitors equals 1/3.

2

The essence of the Byzantine general problem

Reviewing the problem, a group of generals want to achieve a certain goal (attack or retreat together), but acting alone does not work. The generals did not know how to reach agreement because of the traitors.

Note that “consistency” is the question of the Byzantine generals ** if there are already too many traitors to solve the problem, this is the question of “rebellion”; At the same time, the goal is for the loyal generals to reach agreement, and for the loyal generals to attack or retreat, as long as they reach agreement.

But will consensus alone solve the problem? Consider that, if everything was ready, every loyal general would objectively have won if he had attacked, but they “unanimously” did not attack because of the traitors; On the other hand, the generals were not supposed to attack, but all “united” because of the traitors.

It can be seen that “consistency” alone is not enough to solve the Byzantine general problem, we also need to propose a “correctness” requirement. ** This requirement is worth considering, because there may be an “absolutely right” judgment if we look at it objectively, but everyone’s judgment may be different for each general. How do we define “right”? We may simply say that correctness means that every loyal general expresses himself correctly, and does not reject his message because a traitor makes other generals think that a loyal general is a traitor.

At this point, we have simplified the Byzantine general problem to the point that all loyal generals were able to convince other generals of their true intentions and eventually act in undivided agreement; The formal requirements are consistency and correctness.

If the problem is generalized, the algorithm for consistency and correctness does not require the command to be “attack/retreat” or “1/0”, but “send message 1/ send message 2/ standby” or “X/Y /z/ W”. This means that the Byzantine General problem algorithm can provide inspiration for a variety of distributed systems. Like a power system or a network.

It follows that the problem boils down to an algorithm of consistency and correctness for loyal generals, since traitors can make any judgment that goes beyond convention. We’re just trying to find an algorithm that doesn’t interfere with the traitors.

3

Satoshi nakamoto’s solution

The question puzzled scientists for decades, until the advent of blockchain.

Now let’s imagine a computer for each general (equivalent to a distributed node), reducing the cost of information flow and allowing information to be synchronized to each general in a very short time.

Also, to avoid confusion, only one general can send messages at a time.

How do you determine which general is sending the message? Blockchain systems typically use proof of work (POW) to determine who speaks first. (Proof of workload will be introduced in a follow-up article)

We can imagine it as a sudoku game, where the general who solves it first has the right to send the message first. Generally, sudoku rows and columns can be added or deleted, and the difficulty can be adjusted to ensure that this is a relatively certain value for a period of time. On the Bitcoin system, that number is 10 minutes, which means that bitcoin generates a block on average about every 10 minutes.

When a node sends a message of unified attack or retreat, each node must sign and seal the message from the initiator to confirm their identity. Bitcoin here uses modern asymmetric cryptography to sign the message.

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.

Asymmetric encryption algorithms encrypt and decrypt using two different keys, the public and private keys we often hear about. Public keys are generally public and used for encryption. The private key is used to decrypt the public key to obtain information. For example, General A wants to send A message to General B. To prevent message leakage, General A only needs to use B’s public key to encrypt the message, and the encrypted message can only be decrypted using B’s private key. (Asymmetric encryption algorithms will be introduced in a subsequent article)

In addition to encrypting the information, at the same time, the information is backed up at each node as it passes through, with each node storing the same complete data to prevent a few traitors from tampering.

Ok, let’s go through the whole process again:

General each assigned A computer, A general solution, which first game has the first right to speak, A attack information, and immediately broadcast to all general, everyone can according to A public key to verify the identity of A, to ensure the credibility of information, and issue the vote for or against himself, after in the entire network to verify the results.

An untrusted transmission of information then becomes a distributed trusted network, where participants are entitled to voice their opinions and agree on one thing.

The Byzantine general problem is solved, and I’m sure you already have the answer to the question at the beginning of this article. I’ll stop there and continue in the next video.

The content of this article comes from: Baidu Encyclopedia, Babbitt, Coin Line observation, etc

Activity recommended

Theme: Blockathon, challenge blockchain development, dare to come! (Click for details)

May 25-27, Blockathon2018 Beijing station, recruit 100 developers to challenge blockchain development.

Developers free, registration is subject to review. To register, identify the QR code below or click “Read the original text”.

Click “Read the original” to sign up.