The Byzantine General’s Problem and Blockchain

The Byzantine General’s Problem and Blockchain

Over the past five years, there has been a deluge of a surge on Google’s search for blockchain. Both the media and various companies have increased investing time and capital on it. In order to appreciate the magnitude of interest in blockchain, we first need to understand the problem which remained unsolved for more than 2000 years and was finally solved by blockchain!

What was the Byzantine General’s Problem ?

Imagine that the Byzantine Empire has decided to capture a city and, unfortunately for the invading army, there is a fierce resistance from within the city. The army has many divisions and each division has lieutenants and it has completely surrounded the city. The General will need to communicate with all his lieutenants only through messengers.

As shown in the diagram above, lieutenants and the General have to agree on one of the two plans of action – attack or retreat. If the attack or the retreat is without full strength, then it will result in a defeat. If all the lieutenants and the messengers were reliable and trustworthy, then it would have been a very simpler scenario. However, some of the messengers and even some lieutenants of the general could be traitors, spies or even enemy soldiers. There could be a great possibility that they would not follow orders and transmit the wrong message.

A solution to the General’s dilemma must pass three tests: termination, agreement and validity. These three tests are:

  1. A solution has to guarantee that all correct processes eventually reach a decision regarding the value of the order they have been given.

  2. All correct processes have to decide on the same value of the order they have been given.

  3. If the General’s command is correct, all the lieutenants have to decide on the value that was originally given by the General.

An interesting “side effect” of this is that if the General’s command was faulty, then all lieutenants  still would have to agree on the same value. It doesn’t matter what value they agree on, they simply all have to agree. Then, if the General is a traitor, all the lieutenants still have to reach a common and unanimous decision. This agreement is called the consensus.Let us illustrate it with an example.

 Diagram from the original Byzantine General’s Problem paper

In the figure above, traitors have been indicated by boxes with hatched lines. In Figure 1, a loyal General sends a message to Lieutenant 1 and 2. L2 is a traitor and sends a conflicting message to his peer. L1 does not know who the traitor is: is the General a traitor or is his peer a traitor? In Figure 2, the General is a traitor and sends conflicting messages to L1 and L2. Since both Lieutenants are loyal, L2 sends L1 the message he received from the General. From L1’s point of view, he again does not know who is the traitor: the General or L2? In both scenarios, the army attacks with less than full strength. An animated elucidation of this problem of can be found in  this video.

Solution Using Only Oral Communications

Before the war, the Byzantine army could agree on a method to determine whether to attack or not by a simple rule given below:

  1. Each Lieutenant forward orders to all the other lieutenants either to retreat or to attack

  2. Each Lieutenant take the final decision as majority vote that he gets from other Lieutenants and General

To understand the above process, let us consider the following example

 

There are three Lieutenants and a General, so there are total four members in the army let us name them L1 , L2 and L3 from top to bottom and L3 is traitor and is transmitting a wrong order.

  • L1 has received :{Attack , Attack , Retreat} from {General , L2 , L3} simultaneously and similarly we can say that

  • L2 has received :{Attack , Attack , Retreat} from {General , L1 , L3} and

  • L3 has received :{Attack , Attack , Attack} from {General , L1 , L2} simultaneously

If L1 takes the a majority vote, then it is Attack which indeed was the general’s order. Now if we apply the same method to other lieutenants to take a decision, then they all will agree to Attack. As a result, all three Lieutenants will Attack simultaneously! We can see that, in this system, there is no need to trust anyone for authentication. This kind of system is called trustless, which means the trust is engendered by the system and not by the participants in the system (many people confuse the meaning of “trustless” as having no trust in the system.)! One does not need to trust anyone, hence the name, trustless. It is worthy to note that this works only if less than one-third of the participants in the network are traitors.

Solution Using Blockchain

Let’s relate this scenario to the blockchain. In a distributed ledger, all inputs (messages) to the ledger (the agreed attack time) must be trusted and reliable. Digital networks usually have millions of members (lieutenants) who are dispersed globally and there is no centralized command (without central governance), also, it is impossible for you to know all the members. So how can you trust the other members of the network and ensure that the inputs to the distributed ledger are accurate and moreover, ensure that the ledger itself has the correct information? Blockchain solves this problem and in the case of our Byzantine general, ensures that he can send trusted messages and lead a successful coordinated attack.

The algorithm in the previous solution which uses only oral communication is one of the solution which solves the Byzantine general’s problem. However, that solution is not efficient enough, and it has constraints, that less than one-third of the network is dishonest, also it is slow for a large network.

Running time of solving the Byzantine General’s Problem with the algorithm proposed by Lamport, Shostak and Pease (n = number of actors, m = number of traitors)

 

In Proof of Work, in order to choose the next block to be added to the blockchain we  have to find a solution to a particular complex mathematical problem.

Let that mathematical problem be:

Given data X, find a number n such as that the hash (consider it as a machine which generates a unique number for each given input) of n appended to X results is a number less than Y.

Example – Y = 10, X = ‘attack tomorrow’

hash(X) = hash(‘attack tomorrow’)     = 0x0e = 14 > 10

hash(X+1) = hash(‘attack tomorrow+1’) = 0xfe     = 254 > 10

hash(X+2) = hash(‘attack tomorrow+2’) = 0x08   = 8 < 10 OK, Solved.

And the number ‘n’ (2 here) is the proof that work was done to find that number hence number ‘n’ is called “Proof of Work”.

The only way to find a solution to that problem is by brute-force (trying all possible combinations) because of the property of hash function. The person who solves this problem is called a miner and the process is called mining.

This process is successful due to its following properties:

  • It is hard to find a solution for that given problem

  • It is easy to verify that it is correct when a solution is given to that problem

In order to forbid any malicious or bad behaviour by these “miners” all the blocks (informations) are made dependent on all of the previous blocks! In other words the blocks are chained so it is called blockchain. This process of chaining every block is simple and same as what is shown in the diagram below.

 

This process is much faster than our previous solution and also can handle even if half of the network is dishonest! So it is a great jump from 33% to 50% in terms of handling malicious nodes on network. Note that you cannot achieve more than 50% anyway (it’s consensus) so this is the best result.There are informations about each and every transactions for public to view and verify but they will not get to know anything about transactions from it. This is known as zero-knowledge proof.

Proof of Work (PoW) is one of the a blockchain consensus algorithm, and is used in projects such as Bitcoin and Ethereum. It enables users on a blockchain network to reach an agreeable ‘truth’. A proof of work is essentially an answer to a complex mathematical problem. It takes a lot of work to create (hence the name) but is easy for others to validate and this was the magnificent breakthrough by Satoshi Nakamoto.

Conclusion : Proof of Work is the consensus algorithms that solves Byzantine general’s problem and is practically used in today’s blockchain systems (like Bitcoin and Ethereum) other consensus algorithms such as Proof of Stake (Steem), Practical Byzantine Fault Tolerance (Tendermint , Hyperledger) or Distributed Byzantine Fault Tolerance (NEO) also exist.

 

Blockchain has the power to disrupt any industry working on a centralized system and make it decentralized and trustless.

 

Spread the network
  • 12
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
    12
    Shares

 

One Response

  1. Varun Gohil says:

    Very informative. Fun to read!

Leave a Reply

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

indiaChains
unblocking the blockchain

© 2018 ipLockChain