Posted by Summary:
Blockchain needs consensus within large number of nodes, Byzantine Generals Problem articulates the challenge
Byzantine Generals Problem (BGP) is in simple terms arriving at right decisions without full information, or even some part faulty information.
This concept is taken to novel level in Blockchain, a Proof of Work makes it very hard to tamper with information being presented to a large number of independent nodes.
Blockchain (for most of us synonymous with BitCoin) is collection of technological inventions made possible by advent of computing power. One of the central ideas is the consensus (or agreement) between participating computers(/parties/nodes) on what is acceptable state of affairs by mutually agreed rules. Interestingly Satoshi Nakamoto achieved this through a practical and novel solution existing distributed networking problem, Byzantine Generals Problem (BGP). While explaining reliability of a computer system in-spite of having malfunctioning components, Lesle, Robert et all used fictitious battle situation, adding complexity to earlier 2 Generals Dilemma (https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf).
Bit of history – The Byzantine Empire (aka the Eastern Roman Empire) was the continuation of the Roman Empire in its eastern provinces during Late Antiquity and the Middle Ages, when its capital city was Constantinople (modern-day Istanbul). It survived the fragmentation and fall of the Western Roman Empire in the 5th century AD and continued to exist for an additional thousand years until it fell to the Ottoman Turks in 1453. During most of its existence, the empire was the most powerful economic, cultural, and military force in Europe.
Suppose you are a General from Byzantine Army on a campaign and have targeted an enemy city. Along with other Generals you have completely encircled it. You can communicate with other Generals only through messengers. All of you Generals got to agree on a simultaneous action, either attack together or retreat together. If not, a half-hearted at the strong the enemy will ruin your career handing you out a sour defeat. If all generals and/or messengers were trustworthy then it is a very simple solution. But some of the messengers and even a few generals/commanders are traitors.
So the problem statement is that how all loyal generals decide upon the same plan of action, ensuring that a small number of traitors cannot cause the loyal generals to adopt a bad plan. Solving this needs to consider how Generals reach a decision. The first condition can be achieved by having all Generals using same method of combining information, and the second needs a robust method, say a majority vote.
The formal description of the Byzantine Generals’ Problem adapts a strict military chain of command, to achieve common action (attack or retreat),
- All loyal lieutenants obey the same order
- If the commanding general is loyal, then every loyal lieutenant obeys the order he sends.
Consider a decision “attack at Friday 0200 Hrs”. Then the objective is (overly simplified)
Each General sends this message v(i) to each of the other Generals. Then the problem statement becomes
- Every loyal general must obtain same set of information v(1), v(2), …v(i), … v(n), on which they somehow arrive at same decision
But then there may be a traitor General (or his messenger switched), we need to establish the message is from loyal General, hence
- If the ith General is loyal, every other loyal General should use same v(i) from him.
This means that
- Every loyal General must use same information v(i) from ith General, whether he is loyal or traitor!!
With bit of mathematics it can be shown that if there are m traitors, fewer than 3m + 1 generals can’t arrive at consensus. Real life complexity compounds the situation, such as correct delivery of message, knowing who messaged and detection of missing messages etc. But still it works out to be that if less than 1/3rd of the generals are traitors, your army can act coherently and win the city!
How this relates to networking and Bitcoin:
This story maps neatly onto networking; computers are the generals and their digital links are the messengers. Hence a Byzantine Fault is a fault that presents conflicting symptoms to different observers. A Byzantine Failure is the loss of a system component due to a fault in a distributed system that requires consensus. Objective of a Byzantine Fault Tolerant system is to be able to defend against these failures. A correctly implemented Byzantine Fault Tolerant system should be able to still provide service, assuming that the majority of the components are still healthy.
While BGP found practical applications in networking and complex systems like space shuttles, Satoshi Nakamoto (Bitcoin) developed a practical and novel solution. Instead of a signature that validates a message, Proof-of-Work concept was introduced.
In simple terms, list of transactions are bundled together, previous block’s hashed header is added to this list. Then an additional random bit is added to this mixture, and hashed to produce a new-sealed-chained block. Finding a suitable random bit used is purely a guessing game requiring hashing repeatedly using different random bits, such that the hashed output is less than a certain target number (all hashed outputs are represented by a number). This repeated hashing requires immense computing power, but once found it is easy to verify that someone has spent effort doing this, hence PoW.
How does this help to get consensus? Satoshi designed an ingenious consensus method. A block on blockchain is voted as right one being chosen by thousands of nodes by simple rules, validating asynchronously. Key is not being able to alter long chain without spending a large effort within impossible short time window.
Suppose as a Byzantine General you take 10 mins (average time targeted to create block in BitCoin) to create the message and seal it, sealing needs a special mix of gums (or equivalent to a random bit). It’s a long message role with all previous messages too. So you (node A) send the (sealed, sealing takes 10 minutes) message to all other Generals, ‘attack’.
A General (say node B) gets your message , takes 10 minutes to further seal with his own message, and sends out all generals. A general C would see, for example, “B says attack | A orders attack”. Now C is a traitor. C wants to change messages to “withdraw”. To make this happen he also has to change messages of A and B. That takes 20 more minutes as he has to recreate the random bits used by A and B over and above 10 minutes to find his own random bit satisfying sealing requirements.
Next a General D receives either in 10 minutes “C orders withdraw | B orders attack | A orders attack” or in 30 minutes (after C spent time fiddling with earlier messages) “C orders withdraw | B orders withdraw| A orders withdraw”. In the first case it is easy to see him as traitor, and in second case too the inordinate delay gives him away. By design it is practically impossible for C is to prepare all 3 messages in just 10 minutes.
This is a neat way to solve to avoid double spending the Bitcoin money. Someone can’t send two differing transactions to nodes, as well as go back in time and alter the transactions. First one is rejected by consensus rules of validation, and the second is impossible given current computing power.
Bitcoin’s decentralized consensus results by its design. The nodes independently verify each transaction based on a comprehensive list of criteria. Mining nodes aggregate those transactions into new blocks and add a random bit through lots of guess work to meet a criteria on hashed number output. Testing whether the random bit meets the condition is easy, but arriving at the first right random bit meeting the conditions is not. Hence you can easily check if someone has spent enough time (hence prove the work) to find right random bit. Every node continuously validates these random bits and selects the longest chain of blocks that has longest cumulative linked and proved chain. Anyone wants to change a past entry will need to solve all the past random bits to represent an alternative chain to all nodes, longer the chain it becomes impossible to beat the system, because another block would have added and longest one gets selected!
This novel way to solve BGP has proved useful and is creating new thinking in the field of distributed computing and econometrics. The time-stamping and immutability help in say, digital money (of course BitCoin), fairness in election voting, asset registers, digital notarization etc. This seems to be only the beginning of massive decentralized consensus economy.
I currently work full-time at Swiss Re, Bengaluru. The blogs and articles on this website www.balajos.com are the personal posts of myself, Balachandra Joshi, and only contain my personal views, thoughts, and opinions. It is not endorsed by Swiss Re (or any of my formal employers), nor does it constitute any official communication of Swiss Re.