Byzantine Fault and Consensus Mechanism

So we have seen the types of blockchain but what makes blockchain so successful? The model is no doubt good but nothing in life is fully perfect, isn’t that so? This distributed ledger which is maintained by all, sounds like a good concept but what if some nodes or a group of nodes try to corrupt the data. Like when there is a transaction and the blockchain is updated, all the nodes have an option of whether to add the new data or not to. When the majority of the nodes reach a common decision, that is known as a consensus and this is the main factor which decides the fault tolerance level and self-correcting nature of a blockchain.

Satoshi Nakamoto had in detail given a probabilistic solution, a solution which has a very high probability of solving this problem of data mismatch or incoherency, like imagine if there are two nodes and one node tries to tamper or edit the last data block it had. This will lead to a difference in data between one node and the other and since blockchain works on the concept of a distributed ledger, everyone has to maintain the same copy of the ledger to match and authentic the data on it. Thus corrupt data or without a fault tolerance check in the blockchain, it will soon become inconsistent and the whole purpose of the blockchain will be lost. Thus to create a full consensus network of blockchain, there should be a good fault tolerance system in place.

Thus to understand the problem in detail we need to think about a hypothetical situation which consists of two generals with their armies are at two sides of the enemy camp and are ready to attack but they need to do it together or the enemy might outnumber them as they are single handedly not enough to defeat them. Hence the two generals have decided to coordinate and the first general would send the attack timing, like maybe a command like ; attack at dawn, to the second general but there is a chance that the messenger might get captured by the enemy and hence the message won’t get through. This will result in only the first general attacking and eventually facing defeat. If even the messenger goes through and delivers the message to the second general, then they need to send an “Acknowledgement Signal” back to the first general and hence we see a repeat of the previous scenario of whether the messenger can deliver the message or not.

Here during every interchange of messages we can say for certain that there exists a real chance of the messenger being caught which will lead to a lack of messages and this problem has been proven to be unsolvable but yes what you can do is to provide a probabilistic answer to this which has a chance that it will yield a possible solution in some cases but even that is not guaranteed to answer it. Thus to put it in simple words, this question falls under the category where there exists no definitive answer to this question ever but we can devise a logic which has a good chance of solving this problem.

Doesn’t this sound familiar a bit? Yes because this is the very solution which did give birth to the blockchain network and Satoshi Nakamoto's famous email. One possible solution to this problem is there but it requires a minimum of 3 generals and the problem does have a possible solution for that. The solution goes like this that the goal is to reach a consensus, there can be two possibilities for all the general, either they attack or they retreat. It doesn’t matter what final decision they take but it matters that they reach a consensus and if there are 3 nodes and even some of the generals are dishonest or they send out fake signals, then if the number of such bad nodes is less than one third of the total number of nodes, the whole network is fault-tolerant and a consensus can be reached among all the nodes. Thus imagine a scenario where there are 3 Generals waiting to attack the enemy. One general is the supreme leader and the other two are his followers, The Supreme General sends the signal to attack to both of his followers like let's say the message reads “Attack at dawn”, and then each of the followers will send each other the same signal. Here even if one of the messengers fails to deliver the message, The chance that 2 of the initial messengers of the general fail is very low and if either of those messengers fails, then the other follower will send the message again.

Thus redundancy is the key to this solution and the network is designed such that despite any faults or losses, the messages are set to be redundant so that there is a high probability that everyone does receive the message. One thing you should always remember that it is not a definitive answer, and there never can be one as this is an unsolvable problem, rather it is a probabilistic solution to the problem. The Byzantine General problem was proposed by Lamport Shostak in 1982 and it was a development on the Two General problem but with a twist that it consists of the same scenario but there are more than two generals who need to coordinate their time of the attack. The extra thing to this is that one or more of the generals can be actually a traitor. Which will lead to a false statement or they simply forwarding wrong messages to other followers or generals?

For Simplicity lets assume only two states of the message which are “Attack” and “Retreat”. Let us imagine this scenario with the sort of Commander and his Lieutenants and we want to reach a consensus here. Now there can be a total of two conditions which are discussed below in details. A commanding General must send an order to his n-1 Lieutenant generals such that these criteria are met. Incident 1 - All the Loyal Lieutenants must obey the same order. Incident 2 – If the Commander is loyal, then all the loyal lieutenants obeys the order he sends. Thus according to Incident 1, it is interesting to see that is the Commander is disloyal, then also a consensus will be achieved and all the lieutenants take the vote of the majority. The algorithm to reach the consensus is to take the side of the majority that lieutenant observers. Thus the Theorem can be summarized as an Algorithm OM(m) reaches a consensus only if there are more than 3m generals and at the very most, only m traitors, not exceeding that.

Thus the algorithm can reach consensus as long as there 2/3 of the total nodes are honest and the traitors in the network don’t exceed 1/3. If the traitor number is greater than 1/3 then we can say for sure that no consensus is reached and the armies don’t coordinate their attacks and the enemy wins. The algorithm for the solution goes like this where “m” means the number of traitors. Algorithm OM(0). The Commander sends his value to all the Lieutenants. Each lieutenant uses the value he receives from the commander or uses “Retreat” if he receives no value. Algorithm OM(m), where m>0. The Commander sends his value to all the lieutenants. Let us assume that for each Lieutenant i, let vi be the value that Lieutenant i receives from the commander or else he uses the value retreat. Lieutenant i then acts as a new commander in the algorithm OM(m-1) and sends the value vi to each of the remaining n-2 Lieutenants. For each value of i and where i not equal to j, let us assume that vj is the value that Lieutenant i receives from Lieutenant j or else Retreat if he receives no value. Thus by now Lieutenant I will have received n-2 values from all the remaining generals and then Lieutenant i makes a decision which is based on the majority of the value in the set of (v1,v2,…..vn-1)

Thus this Algorithm might sound too complex and if we use simpler words and give an example like let's imagine a situation with 1 commander and 3 Lieutenants and the 3rd Lieutenant is dishonest. Then let x be the value sent out by the commander to all the Lieutenant. The steps that take place are these: The commander sends out the values to all the Lieutenants. ( C to L1, L2 and L3) Then all the Lieutenants send the rest of the Lieutenants the value received from the commander. ( L1 to L2 and L3, L2 to L1 and L3 and L3 to L1 and L2 ) Each Lieutenant acts on the majority of the values that they receive.

Let us assume the commander sent out the message ‘x’ and Since L1 and L2 are honest, they send everyone else ‘x’ too. Now, L3 being dishonest sends out ‘y’ to the rest of the network. Thus If we take a case in point of L2 for example, It receives x from the Commander, x from L1 and y from L3. Hence it’s values consists of (x,x,y). Thus according to the rule of the majority, he will always choose the value that appears as a majority to reach consensus and hence L2 choose x over y and thus the network integrity remains intact. We should remember that the goal of the mission is for the majority of the Lieutenants to choose the same decision and any specific one. Consensus can either be reached with any two of the values, it doesn’t need to be a particular value. If we imagine another special case of the commander being dishonest, we can deduce another flow of algorithm like these.

Commander sends out x,y and z to L1, L2 and L3 respectively. L1 sends x to L2 and L3 and so does the rest of them send their values to each other. L1 has to choose from the majority of (x,y,z) and so does L2 and L3 as they have received 3 different values and now must choose the majority of the values. Thus a consensus is reached as you can take a moment to analyze this an see that thought x,y and z can be different values, the value of the majority shall remain the same or in other words, theke inputs and the process is the same and hence they will reach the same output and maintain consensus. In this case of x,y and z being totally different commands, we can assume that maybe all the Lieutenants acted on their default value of Retreat.

Byzantine Fault tolerance is a set of characteristics which belong to the group of systems that tolerates a class of failures which belong to the Byzantine Generals’ problem. It is one of the most challenging failure modes and the most difficult one to correct too. It has no restrictions or assumptions about how a node will behave and whether it will be honest or not. The system works on one Knowledge and probability that the number of dishonest nodes in the system will be less than n/3 or less than one-third of the total number of nodes or else or won't.

Now I know I have talked a lot and you might be thinking that why is it important again? It is because Without BFT, Byzantine Fault Tolerance, the peer to peer network in the blockchain can become erroneous and anyone can insert false transactions and thus defeat the whole purpose of a blockchain by creating confusion and incoherency. Moreover, there is no central authority to take control and correct the damage and hence BFT is preferred for blockchain and this was achieved as a big breakthrough with the invention of Bitcoins.

Proof-of-Work was the Probabilistic solution to the Byzantine Problem which was described in details by the email of Satoshi Nakamoto. The bitcoin protocol does specify the basic rules of the system but the Proof-Of-Work consensus algorithm is what defines how the rules will be followed to reach a consensus. For example, during the validation and verification of the transactions. Proof-Of-Work is not a 100% full proof plan to the Byzantines problem but due to the cost of intensive mining and the underlying cryptographic techniques make it one of the most reliable and secure implementations for blockchain. It is often hailed as the most genius solution to the Byzantine problem.