What is Byzantine Generals Problem and How Blockchain solves it?

Byzantine Generals

Anyone interested in cryptography has at some point heard of the “Byzantine Generals” problem. This problem has been the main stepping stone for every secure, decentralized voting system created in the past. Originally written about in a paper created by Leslie Lamport, Marshal Pease and Robert Shostak, it describes a situation where several involved parties need to vote and create a consensus about their future actions. The problematic part is the possible existence of rogue and malicious members who might vote in a way which could cause the entire system to fail.

The problem can be practically described with three imaginary Byzantine generals preparing themselves to either attack or retreat from a siege (an example with three generals is the easiest one to understand). Each general has an army of his own, and these armies are positioned at various sides of the besieged city. The city is strong enough to handle a single army attacking it, maybe even two of them at the same time; it will buckle if it has to defend against all of them. The generals need to communicate with each other and ensure that their armies attack simultaneously, as this is the only way the city can be taken. Every general will send a message to the other two, saying if and when he wants to attack. They can either come to a consensus on performing an attack (if two thirds agree on an exact date) or can also decide that the city cannot be taken right now and retreat.

army attacking

A single army attacking alone is doomed to fail

The communication is handled with the help of messengers. These messengers will run through the enemy city, exposing themselves to danger, and try to deliver their generals message to other armies. The General 1 might survey the city and with the help of his military tacticians decide to, for example, attack on the next Tuesday night. He will then send out a messenger to other two generals and inform them of his desired attack date. Ideally, both generals will get the same message to attack on Tuesday night. To further confirm the attack plans, general 2 might agree on general 1’s plan and send messengers to signal his readiness to attack at Tuesday night. His messenger will, again ideally, reach the other generals unharmed and deliver his message. This way, the decision on when to attack has been confirmed; the attack can commence as soon as the sun sets on Tuesday.

However, every time a messenger is on his way towards a general, it risks getting caught by the city’s defenders. If the messenger is caught, the defenders will know what the plan of one of the armies is. Naturally the defenders will want to prevent a coordinated attack so they might replace the original messenger with one of their own people. This messenger could then deliver a fake message to one of the generals; this message might suggest a retreat or to attack on a different date, which would endanger the entire operation. Also, the original messenger himself could see the suffering that the besieged city is being put through and decide to work in their interest instead. Finally, one of the generals might have a gripe with one of the other two generals; this gripe might cause him to become malicious against the general he doesn’t like. In his maliciousness, he might send out a retreat message to the general he likes and an attack message to the general he doesn’t like, causing the despised general’s army to perish in battle alone.

If any of these scenarios unfolds, a traitor becomes active inside the system; as a result, a miscommunication will happen and the consensus will not be achieved. Chances are, one of the generals will make a wrong decision and will doom his men to a battlefield death.

The issue here is the lack of ability to check if the message is authentic or not. The generals need to believe that their message was properly delivered to the other armies. Even if the messengers are caught, the message needs to be encrypted somehow to ensure that city defenders don’t realize the attack strategy or that malicious generals don’t lead the entire army to slaughter. This problem of creating a trustless system that allows the “good guys” to communicate without revealing their plans to the malicious players is what is known as the Byzantine Generals problem.

How Bitcoin Blockchain Solves This Problem

With Bitcoin, Byzantine Generals problem turns into an even more complicated beast. The number of generals increases, and now each one of them needs to communicate their intentions to every other general safely and quickly. At the same time the number of malicious players and possible traitors increases, meaning that every one of them needs to be neutralized somehow.

Byzantine Generals problem

Source: https://medium.com/@DebrajG/how-the-byzantine-general-sacked-the-castle-a-look-into-blockchain-370fe637502c

By utilizing blockchain technology, the Byzantine Generals problem can be solved. A distributed, digital ledger operating on a computer network has millions of members/generals who aren’t under any hierarchy but are actually considered equal. Every member of the network gets to vote on what message the network should agree on.

Blockchain offers a decentralized, self-governed method of managing this network of users. Each blockchain contains data on all previously conducted and recorded transactions. The blockchain is constantly updated with new data and new transactions, tracking every single token that was ever created or spent on the network. Bitcoin creators made sure that this blockchain data is tamper-proof by utilizing special cryptographic solutions based on SHA256 hashing algorithm.

Bitcoin’s cryptography solution deals with this problem by adding a nonce (a string of numbers and letters unique to your communication) to your text message and then putting it through the SHA256 hash algorithm. This nonce is a key element of this systems safety; when put through the SHA256 hash algorithm alongside the message, IF it was sent by a trusted source, it will give a hash that starts with a certain number of zeros.

Now, to apply this to our generals, every general needs to agree on a single message. Every general can’t trust any other general on the network. Every general can’t trust the communication channel itself (the city through which the messenger is passing through); they have to assume the message can be intercepted and replaced with fake data. This would result in loss of value and create an unstable network. Therefore sending a pure text message is out of the question.

First, the general who sends the message finds a nonce (usually takes millions, even billions of attempts) which will, when put through the hashing algorithm, give a hash function that starts with a set number of zeroes. The message is then sent to the other general together with the nonce. The receiving general then hashes the message + nonce through the same hash algorithm. If the resulting hash has the same number of zeroes that the initial hash you made had, then the general can be certain the message was sent by you. If the number of zeroes is less than the original hash, it was probably intercepted and definitely tampered with.

There is still a way for the city to create a fake message. If they replace the message itself, the hash function will not start with the same number of zeroes. The city will now have to spend billions of attempts themselves to find a nonce that will, when ran through a hashing algorithm alongside the fake message, create a hash function that will have the same number of zeroes as the original.

This problem is solved by making the number of attempts it takes to find the hash that starts with set number of zeroes practically impossible to perform. As we have multiple generals, each of them will have his own message related to the day of the attack. To fool the city, multiple generals will add their message into a single block and will collectively try to find a nonce such that the hash of the messages and said nonce will start with a certain number of zeroes (the more zeroes, the harder it is to find the nonce). All of the generals will need to use a lot of computational power and energy to find this nonce. When it has been found, the message + nonce are finally sent.

As you can deduce from here, the city will have a very hard time with editing the contents of the message even if they catch the messenger. With multiple messages and multiple generals investing a lot of computational power, it is practically impossible for the city to tamper with the message.

And this is how it all works. To make the parallel to the Bitcoin network itself, people who want to transact on the network protect their transactions by shielding them behind hash algorithms and nonces powered by a network of powerful mining nodes (which basically discover block nonces and add blocks to the blockchain). A network user that wants to tamper with the blockchain simply cannot compete with the entire Bitcoin ecosystem, making the transactions secure and tamper-proof.

This article was inspired by a great video made by Ivan on Tech, which you should definitely watch for more details and illustrations. You can also check out this hour long presentation by Andreas Antonopoulos which goes into even greater depths to explain this problem.

intelligent crypto
How are  regular people making returns of as much as 70% in a year with no risk?  By properly setting up a FREE Pionex grid bot - click the button to learn more.
Crypto arbitrage still works like a charm, if you do it right! Check out Alphador, leading crypto arbitrage bot to learn the best way of doing it.

Torsten Hartmann
Torsten Hartmann

Torsten Hartmann has been an editor in the CaptainAltcoin team since August 2017. He holds a degree in politics and economics. He gained professional experience as a PR for a local political party before moving to journalism. Since 2017, he has pivoted his career towards blockchain technology, with principal interest in applications of blockchain technology in politics, business and society.

We will be happy to hear your thoughts

Leave a reply