Byzantine Fault Tolerance (In a Blockchain)

Byzantine Fault Tolerance (In a Blockchain)

Arpan Pandey
·Dec 27, 2021·

3 min read

Subscribe to my newsletter and never miss my upcoming articles

Play this article

Table of contents

  • The Story
  • Communication
  • Simple Majority Vote
  • The Commander as Traitor
  • How tolerant?
  • Wrap up...

Welcome Again! Today, we are going to learn about a core fundamental that is essential to building any decentralised system not just blockchain. Let's start as always with a good old-fashioned Wikipedia definition.

A Byzantine fault (also Byzantine generals problem, interactive consistency, source congruency, error avalanche, Byzantine agreement problem, and Byzantine failure[1]) is a condition of a computer system, particularly distributed computing systems, where components may fail and there is imperfect information on whether a component has failed. The term takes its name from an allegory, the "Byzantine generals problem",[2] developed to describe a situation in which, in order to avoid catastrophic failure of the system, the system's actors must agree on a concerted strategy, but some of these actors are unreliable.
-Wikipedia

Also, this article will contain a lot of pictures to better illustrate things.

The Story

There is this story that goes around. According to the problem, there are these 4 generals who need to attack a castle. They can either attack or retreat. The thing is tho that they need to reach a consensus, an agreement of sorts. If they do not, then the enemy will easily decimate them. Let's visualise this. Visualisation 1.png Out of these generals, one is the Commander (denoted with a crown) and the one is a traitor. But, they don't know who the traitor is. The job of the traitor is to put some obstacles in the way so don't come to a consensus.

Communication

The generals, for the sake of the problem, can only pass around one-to-one oral messages. Visualisation 2.png Now, we need to come up with an algorithm to communicate without being manipulated by the traitor.

This problem may seem very easy at first but this is a very complex problem. It is backed up by a lot of research and mathematical proofs.

Simple Majority Vote

Let's say that the Commander issues an order to attack. (The general in red is the traitor). Visualisation 3.png The generals have decided to relay what the Commander has said to each other and then vote accordingly. Visualisation 4.png If the Commander asked them to attack the traitor will obviously relay the opposite. Now can they come to a consensus? Let's see. Visualisation 5.png

  • The Commander- He has made up his mind and he is attacking.
  • General 2- He has got 2 people telling to attack and 1 to retreat. Therefore, he will attack.
  • General 3- Similar to General 2, he will attack.
  • The traitor- He will ask to retreat.

Therefore, a consensus would have been reached and all is good. Or is it? What is the commander is the traitor?

The Commander as Traitor

Now, let's discuss a scenario where the commander is a traitor. If he issues the same command then of course they would form a consensus. Therefore, to mess things up he would have to issue different orders to the generals. In our example,

  • The Commander asks General 2 and 3 to attack.
  • But he asks General 4 to retreat.

Visualisation 6.png
In this scenario,

  • 2nd and 3rd General would be attacking.
  • 4th General would have bee asked to retreat by the Commander and to attack by the other 2 generals. Therefore, he would also be attacking. Again, there would have been a consensus.
    This is called Byzantine Fault Tolerance. Our basic algorithm here is sufficiently tolerant.

How tolerant?

But exactly how tolerant is it? If for example there were 2 traitors instead of 1, it would have been impossible to form a consensus.
In fact, a lot of research was done around this and it was found that there should be no more than 33% or 1/3 of traitors, to be able to reach a consensus.

Wrap up...

This was all there is to the Byzantine Fault Tolerance. We have now set the stage for the next post on Consensus Protocol. See you in the next one!

Did you find this article valuable?

Support Arpan Pandey by becoming a sponsor. Any amount is appreciated!

See recent sponsors Learn more about Hashnode Sponsors
 
Share this