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) 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", 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.
Also, this article will contain a lot of pictures to better illustrate things.
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. 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.
The generals, for the sake of the problem, can only pass around one-to-one oral messages. 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). The generals have decided to relay what the Commander has said to each other and then vote accordingly. If the Commander asked them to attack the traitor will obviously relay the opposite. Now can they come to a consensus? Let's see.
- 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.
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.
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.
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!