Tyler Kot
Tyler Kot
Sep 5, 2018 · 6 min read

Blockchain — Introduction of BFT Algorithm

Author: Star Li

BFT (Byzentine Fault Tolerant) algorithm was proposed by Leslie Lamport and 2 other co-authors in a thesis in 1982. Leslie Lamport, recipient of Turing Award in 2013, ACM member. Lamport is also the inventor and developer of Latex.

This thesis can be downloaded at

http://research.microsoft.com/en- us/um/people/lamport/pubs/byz.pdf

We will discuss BFT algorithm from this thesis in detail.

1). Byzantine General Problem

When a complex system is consisted of multiple computer systems, BFT algorithm solves the problem of guaranteeing the accuracy and uniformity of the whole system when some of the computer system is at fault. For example, when some Byzantine generals are attacking a city, in case some generals are traitors, how the remaining loyal generals obey the orders from their commander in sync. This is also the origin of BFT algorithm.

The thesis first stated the problem faced by the Byzantine generals: 1 commander gives an order to n-1 generals, guaranteeing:

IC1) All loyal generals will obey the order in sync

IC2) If the commander is loyal, all loyal generals will obey commander’s order

The thesis then points out that if the generals pass the messages to each other verbally, the loyal generals must exceed 2/3 of the total in order for the BFT problem to be resolved. It provides 2 extreme examples: there are 3 Byzantine generals in total, one of them is the commander. There are only 2 choices: attack or retreat. The diagram below shows that if there are only 2/3 honest generals, the BFT problem can’t be resolved.

In Fig 1, Lieutenant 2 is dishonest, and told “retreat” to Lieutenant 1 even though the order the commander gave him was “attack”. In Fig 2, the commander was dishonest, and gave “retreat” order to Lieutenant 2 and “attack” order to Lieutenant 1. Under both scenarios, Lieutenant 1 receives 2 messages: 1 is to attach, and 1 retreat. He can’t distinguish if Lieutenant 2 or the commander is being dishonest. Based on IC2, Lieutenant 1 choose to “attack” based on the message from Commander, and Lieutenant 2 choose to “retreat”. Lieutenant 1 and 2 chose different actions, and don’t meet IC1 condition. This means, when there are only 3 generals, if one of them is dishonest, the rest can’t judge who is being dishonest.

The thesis also verifies 2 algorithms:

a. If the Byzantine generals pass messages orally

b. If the Byzantine generals pass messages with signature

2). BFT Algorithm based on Oral Messages

The thesis provides 3 conditions for Oral Messages:

A1. The message can be delivered to intended recipient accurately

A2. The recipient knows the sender of the Oral message

A3. The integrity of the message can be inspected.

Based on the above, a dishonest, yet smart general can use the following methods to attack without being discovered:

1) Send different messages to different generals

2) Delay sending the messages

OM Algorithm is proposed:

OM (m) Algorithm is a Recursive Algorithm. m is the number of the dishonest generals. Please see diagram below:

It’s obvious that, there is n-1 OM(m-1) in OM(m), and for every OM(n01) there is n-2 OM(m-2). The complexity of OM(m) algorithm is O(n^m).

For example, per diagram below, there are 4 Byzantine generals, out of which the commander is honest, and lieutenant 3 is dishonest.

Step 1, Commander gives the order v to other 3 lieutenants.

Step 2, 3 lieutenants broadcast the order to the other 2 (only lieutenant 2 receives the order in the diagram above). Lieutenant 3 is dishonest, and sends order x to lieutenant 2.

Step 3, lieutenant 2 receives orders (v, v, and x), and uses v as the order (majority order is v).

Thesis uses deduction to prove the conclusion: among 3m generals, if the dishonest general is no more than m, OM(m) algorithm satisfy condition of IC1 and IC2. In another words, the fault tolerance of OM(m) algorithm is 1/3.

1) BFT Algorithm based on Signed Messages.

The definition of Signed Message, there is one additional condition over Oral Message:

The signature of honest general cannot be altered. Any alternation will be discovered, and anyone can verify the signature.

The Thesis proposed SM (Signed Message) Algorithm:

SM Algorithm solves the BFT General problem when the generals can communicate via signed messages. v:0 means the order is v, with the signature from general 0. v:i:j means order v, has a signature from I, received and broadcasted by j. The theory of this algorithm is pretty straight forward. It guarantees that every order v will be broadcasted at least once by at least one honest general. Specifically, to step 2, ii of condition B, under condition of k<m, general i needs to sign and broadcast the order he received again. Because the commander is also one of the generals, with a code 0, when k=m, there are a total of m+1 general broadcasted the same order. There are at most m dishonest generals, so at lease 1 honest general broadcasted the order. As long as 1 honest general broadcasted the order, other honest generals will know, and maintain the integrity of the data amongst the honest generals. Please refer to the thesis for detailed proof process.

Based on the assumption of SM Algorithm, a smart and dishonest general can only attack as the diagram below without being discovered: delay sending messages.

For example, please see diagram:

There are 3 generals in total, the Commander is the dishonest one, and sends “attack” and “retreat” to lieutenant 1 and 2. Lieutenant 1 and 2 discover from the signed messages that the commander sent out contradicting orders, and determine that commander is dishonest. The complexity of SM(m) algorithm is O(n^m).

1) Others

The Thesis also describes that in OM or SM Algorithm, if the communication between the generals is not “full connection”, it must meet certain connection conditions. Interested parties please read the full thesis on your own.

Conclusion

Leslie Lamport, Recepient of 2013 Turing Award, propsed BFT Algorithm in 1982 to solve the BFT general problem. The thesis proposed the algorithm under 2 assuptions:

1. Oral Message. Dishonest generals can send different orders to different generals. The complexity of OM Algorithm is O(n^m), and the fault tolerance of OM Algorithm is 1/3.

2. Signed Message. Dishonest general sends different orders and will be discovered. Complexity of the Algorithm is O(n^m), and SM Algorithm guarantees that so long as the dishonest generals are no more than m, the BFT problem can be resolved.

Dora Network will grow with the ecosystem of Blockchain, pay close attention to the latest and greatest trends in the blockchain research, absorb and improve upon what we have accomplished. Please join our public channel for technology enthusiasts and receive updates from us about Dora Network and Blockchain technologies in general. Our wechat ID is Blockheader.

Dora Network

Dora Network is a highly parallelized, high performance, next generation public blockchain dedicated to the execution of dApps.

Tyler Kot

Written by

Tyler Kot

COO of Dora Network, a highly parallelized, high performance public blockchain dedicated to the execution of dApps. https://dora.network.

Dora Network

Dora Network is a highly parallelized, high performance, next generation public blockchain dedicated to the execution of dApps.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade