The Byzantine General Problem and NEO’s DBFT consensus mechanism

Ray Wong
Ray Wong
Aug 4, 2018 · 5 min read

To understand consensus protocol design of Blockchain networks, one must first have some basic understanding about a classic problem known as the Byzantine General Problem.

The Byzantine General Problem is the dependability of a fault-tolerant computer system, particularly distributed computing systems. It is very relevant to the design of consensus protocols of a DLT system. The example below is a classical illustration of the problem.

The Byzantine General Problem

The strength of the Byzantine army is said to be in their uniformly coordinated attacks and retreat protocols. Since the generals are not based at the same locations at any given time, the information to attack or retreat needs to be sent via messengers.

In order to decide the timing of attack, voting exercises are being carried out on a regular basis. Through this voting exercises, any option (attack/retreat) having more than 50% of the total votes will become the agreed course of action. Once decided, the result of the vote is being relayed back to the Generals through a messenger. With each general getting the same message either to retreat or attack at a fixed time, the possibility of winning the war becomes greatly increased.

The system seems straightforward but is subject to possibility of manipulations. Since the Generals are far apart, a messenger is needed to carry the finalized instructions. A couple of problems could occur:

1. If the messenger has been compromised and delivered a corrupted message, the General would get the wrong instruction and act accordingly not knowing the message has been tampered with.

2. The general himself could be corrupted and act differently from the instructions received.

3. The general may not act at all if the messenger was either killed or captured.

4. In some case, the corruption is not only limited to the General and the messengers, some subsection of the battalion might decide to act contrary to the consensus.

The above Byzantine Generals’ problem scenario best described the problem faced by all distributed network. The typical mapping of this story onto computer systems is that the computers are the generals and their digital communication system links are the messengers.

The problem concerns how consensus could be reached when one or more network participants act maliciously or are not trust worthy.

Delegated Byzantine Fault Tolerance(“DBFT”) as a solution

To address the Byzantine Generals’ Problem (“BGP”) faced by the delegated system, different consensus mechanisms have been developed. NEO uses a Delegated Byzantine Fault Tolerance protocol (“dBFT) to address the BGP problem. The protocol aims at limiting the effect of the “BGP” on the overall networks. We illustrate below how DBFT works below.

There are three types of entities in the NEO consensus network.

A. Nodes- These are the network participants. They are the ones with NEO tokens in their wallets. The nodes are responsible for voting delegates and also making transactions on the network.

B. Delegates- The delegates are voted for by the network participants (Nodes) to represents their various interests. They are the one responsible for voting and verifying a block before it is added to the blockchain network. Delegates also have the responsibility to make sure all block written on the blockchain are accurate and verified.

C. Speaker- The speaker is formerly a delegate, who is randomly selected by other delegates to propose the block to the delegates.

The speaker is responsible for the construction of new blocks. A randomly selected delegate will become the speaker and propose a block to be added to the blockchain. The speaker will have to calculate and also verify the transactions as well as the hash. Once done, the proposed block will be sent to the other delegates for verification. At least 66% of the delegates need to confirm the block before it could be finalized and added to the chain.

We have illustrated how the network consensus works, we will now walk through how DBFT overcomes the BGP.

A. The Dishonest Speaker

There is always a chance that the selected speaker is incompetent or dishonest. The speaker could propose an invalid/malicious block.

Assuming the speaker sends a malicious block to two of the three representative delegates and send an accurate block to one of the three delegates. After verification, the malicious block will be nullified by the two delegates, the malicious block proposed by the speaker is then canceled. However, the delegate who received the accurate block will confirm it to be the right block. Since the malicious block was disapproved by 66.6% of the delegates (2 out of 3), the malicious block would be rejected and not added to the chain. The speaker will be removed and the process will start all over again.

B. The Dishonest Delegate

Now we consider the scenario where there is a dishonest delegate but a honest speaker.

In this scenario, a block is proposed by the speaker to the delegates but the dishonest delegate would tamper with the record and verify a malicious block. Since the honest delegates would verify the original block proposed by the speaker, the original block would get confirmed and added to the blockchain while the malicious block would be nullified. The result would be broadcast to the network and the other users will be aware of the malicious behaviour of the dishonest delegate.

C. The Dishonest Speaker & Delegate

What happens if both the speaker and delegate are dishonest? If the speaker sends the right block to the honest delegates and the malicious block to the dishonest delegate for verification, what would happen?

Upon receiving the block from the speaker, the two honest delegates will verify the right block to be accurate. The block gotten by the dishonest delegate will also be verified by the dishonest delegate. However, during the cross-verification process, the malicious block will be rejected. This information will also be made available to those who voted for the dishonest delegate so that he would unlikely be chosen again in the next round.

As we can see, under such setup, unless most of the nodes are corrupted, the system will be able to resist the BGP.

NEO token holders do not directly participate in consensus mechanisms. They rather just vote in Consensus nodes through a specialized transactional voting. Dishonest speakers and delegates will need to make up about 66 percent of the consensus nodes to corrupt the system. The delegates achieve consensus block by block using a Byzantine Fault Tolerance protocol. The number of delegates is determined and voted for by the NEO token holders. Their number is between the range of 7 to 1024 at any given time. At the moment the NEO network has not opened up the voting process yet.

Currently there are only 7 consensus nodes on the network mostly controlled by the NEO foundation. In July 2018, NEO has announced its plan to allow voting on the network, a move to further decentralize the network. It is interesting to see if the network would be able to achieve true decentralization with its consensus mechanism.

Hashcademy

Edtech platform with a mission to help you advance your blockchain career

Ray Wong

Written by

Ray Wong

Hashcademy

Edtech platform with a mission to help you advance your blockchain career