loader-logo

The Byzantine Generals Problem and Consensus Protocol BFT

Perhaps people hear about PoS, DPoS consensus protocols a lot more than BFT, and it seems to be easier to understand.

But there is a fact that BFT is the 2nd most popular after PoW (Now it may have surpassed PoW), because BFT is often used in combination with other protocols such as PoS, PoW, POA,… or only use each BFT. So what is BFT and how does it work?

BFT stands for Byzantine Fault Tolerance

To understand BFT, first let’s talk about the origin of this name.

The Byzantine generals problem was proposed by three computer scientists Leslie Lamport, Robert Shostak and Marshall Pease in 1982. The Byzantine generals problem describes a group of generals in the Byzantine army (the army of the Byzantine Empire), conducting a siege of a city, each of which is stationed at a different location around the city. this. The generals need to talk to reach an agreement on the battle plan.In the simplest case, champions need to reach a consensus on whether to attack or retreat. If attacking and to win, it takes most of the generals to attack, if only a small part attacks, they will fail because of the thin force.

The main problems of this are:

If there are some generals who betray, send confusing and inconsistent information to other generals.

For example, there are 3 generals, A wants to attack, B wants to retreat. C betrays, sends an attack message to A, but sends a retreat message to B. A thought that the majority (⅔) attacked, can be sure of winning then A decided to attack. Unexpectedly, when going to battle, only A engaged the battle thus A failed because of being weaker.

The messenger was arrested and the message was altered. One general impersonates another to send false information.

One general and one army was destroyed without the other generals knowing, so they just wait.

That is the problem given, and it is very similar to the problem of communication to reach consensus among nodes in the blockchain network.

In blockchain systems, fortunately, digital signatures can be used, so there will be no problems with impersonation, or the content of messages being modified. The biggest problem will lie in the problem of “cheating”, or “treason”, or error

To solve the problem of Byzantine generals, PoW is also a solution.

Satoshi Nakamoto also directly explained how Bitcoin uses PoW to solve the Byzantine generals problem in an email sent on November 14, 2008. See here https://satoshi.nakamotoinstitute.org/…/cryptogr…/11/…

—–

In addition, there are many other ways to solve this problem, including a method called BFT (Byzantine Fault Tolerance). BFT has many variations, like PBFT, rBFT,IBFT,… and so on.

In the scope of this article, I would like to summarize the principle of the BFT consensus protocol as follows:

Among blockchain nodes, there are special nodes involved in block generation and voting for blocks, called validators. The validators take turns creating blocks (when it’s their turn to create, and generate, they don’t have the same difficulty as PoW). After creating, propose to the council of validators to vote. The goal is that the system can continue to function normally if at most 1/3 of the validator fails, or cheats

(namely f validator out of a total of 3f+1 validators, or have some variation like 5f+1.7f+1). The whole network will accept when at least total number of nodes agree (namely >= 2f+1 out of a total of 3f+1 validators). There are some variations like 5f+1, 7f+1,..). If a block does not reach consensus (doesn’t reach , or 2f+1), then skip it and move to another node to create a new block.

Normally BFT will be divided into 3 rounds:

  1. Propose: A validator when its turn proposes a new block, and sends it to all remaining validators.
  2. Pre-vote: The validators vote together on the preparation of the commit for the block (1st vote).
  3. Pre-commit: The validators together vote on agreeing for this block to be included in the chain (commit). If this step is OK, the block will be distributed to the whole network (commit) to normal nodes. And the validators start the new block generation process.

Surely many of you will wonder, why do you have to vote twice? The answer is that for 3f+1 node systems (withstanding up to f fault nodes) 1 round is not secure enough. If at lower tolerances (like 5f + 1 for example) then maybe only 1 suggestion and 1 vote, I may write another in-depth article.

Advantages of BFT:

It is energy-saving, no mining required, and highly fault-tolerant.

Defects:

For each new block, the validator council needs 3 rounds of communication, therefore, it happens too much communication. When the number of validators is huge, the process of creating 1 block will be very slow. But if the number of validators is too small, there is no guarantee of decentralization.

How BFT combines with other consensus protocols:

Example combined with PoS: Proposed block rate based on stake ratio. The weight of the demand vote is based on the share rate. instead of ⅔ of validators, of total stake

0 Points


One thought on “The Byzantine Generals Problem and Consensus Protocol BFT”

Leave a Reply

Your email address will not be published. Required fields are marked *