What is the so-called "Byzantine generals" problem?

What is the "Byzantine Generals' Problem"?

The Byzantine Generals Problem was first proposed by Leslie Lamport et al. in 1982, known as The Byzantine Generals Problem or Byzantine Failure. The problem is described like this:

The Byzantine Empire wanted to attack a powerful enemy country, so the empire sent 10 troops to surround the empire. Although this enemy is not as strong as the Byzantine Empire, it is enough to resist the simultaneous attack of 5 regular Byzantine armies. For some reason, these 10 armies could not gather together to attack, and had to disperse and then attack or retreat together according to a unified command. Any one of their armies has no chance of winning if they attack alone, unless at least 6 armies attack at the same time to capture the enemy's country. They are scattered around the enemy's country, relying on signal soldiers to communicate with each other to negotiate attack intentions and attack time.

There may be traitors in the army, who may send wrong orders to other generals. In this case, how to maintain the unity of war instructions and win victory has become a problem.

Further, the Byzantine generals problem can be described as:

A general sending an order sends an order to the remaining n-1 generals so that all loyal receiving generals obey the same order If the sending general is loyal, then all loyal receiving generals obey the received Commanding this problem to develop into the computer field is the Byzantine Fault Tolerance problem. A core problem that the blockchain needs to solve is how to ensure that in a distributed environment, the data of each node (even if there are malicious nodes) can achieve final consistency and correctness.

EKT's consensus algorithm is DPoS. On the basis of DPoS consensus, we also introduce a Byzantine fault-tolerant scheme based on routing strategies.

How to implement the "Byzantine fault tolerance" scheme?

In EKT, we use the mechanism of public-private key encryption and routing strategy to achieve Byzantine fault tolerance. How is this achieved?

The public key of each DPoS node on the EKT main chain is public, and the specific routing strategy is:

1. Block broadcast

When a node completes packaging, it will sign the block. After signing, the node will broadcast the block and signature to other nodes in the network. When another node receives the block and signature, it will verify the signature information to confirm that the block was broadcast from the packaging node. After other nodes are confirmed, they will judge the distance between their own node and the packaging node in the current round, if the condition is met (currentIndex - miningIndex + len(DPoSNodes)) % len(DPoSNodes)

2. Block verification and voting

On each block header, there will be a Hash check value of the block body. Nodes can obtain the block body from other nodes. After processing the body, vote on the currently packaged block. All nodes will sign the verification result of the block and send it to the node satisfying (currentIndex - miningIndex + len(DPoSNodes) ) % len(DPoSNodes)

3. Node downtime

When a node has not produced a block for a certain period of time, the next node in the current round will start packaging the next block at the time point of 3*interval/2, and enter the packaging process of the next block. Similarly, if the node goes down continuously, the condition for judging whether the current node needs to be packaged is currentTime - lastBlockTime > (2*(currentIndex -LastIndex)+1)*interval/2. Once the current condition is met, the current node starts to package. If the last n blocks are down continuously, the order of the next round will be judged according to the hash value of the last block of the current round, and the calculation will be performed according to the algorithm of incrementing each block plus a block interval to judge the currently packaged node and package it. When more than n/2 nodes are down, all nodes will automatically stop producing blocks until more than 1/2 of the nodes survive.

The complexity of this scheme is in the best case: message complexity O(n^2), time complexity O(1). It can also be achieved in the worst case: message complexity O(n^2), time complexity O(n). Based on the Byzantine fault tolerance mechanism of this routing strategy, the system can guarantee that the system will not fork when less than n/2 nodes go down or defect, which is a solution that trades computing resources for fault tolerance.