The Byzantine Generals’ Problem is one of the most well-known and classic problems faced by decentralized networks. Solving this problem was one of the key developments in the creation of Bitcoin and, by extension, all other cryptocurrencies. In this article, we will see what the Byzantine Generals’ Problem is and how Bitcoin manages to solve this perplexing problem.
What is Byzantine Consensus?
The Byzantine generals’ problem was first theorized by the mathematicians Leslie Lamport, Marshall Pease, and Robert Shostak. The generals are a metaphor for nodes in a decentralized network. The core idea behind this thought experiment is this – How do you ensure that a peer-to-peer, distributed network with no central authority can make correct decisions, even if some of the nodes in it turn rogue? Can we make a distributed system that is “trustless” and doesn’t automatically assume that the participants are going to act ethically and work in the interest of the group?
What is a Byzantine Attack?
Imagine this scenario:
We have a castle in the middle, which is extremely well stocked and fortified.
The lieutenants have surrounded the castle. The general (symbolized by the crown) plans to launch an attack. However, since the army is so scattered, the general doesn’t have centralized control.
The only way that the castle could be defeated is if the byzantine army launches a planned and synchronized attack. If there is any miscommunication, the offense will fail.
Speaking of communication, the only way that the generals can synchronize a strike is by sending messages via messengers.
Now, this leads to several failure scenarios:
Imagine that the messengers are traitors, and they convey information that is contrary to the army’s strategy?
Presume that one messenger out of four is a traitor, and he passes along the message of “RETREAT” to some lieutenants when the actual strategy is to “ATTACK”?
What if the messenger gets captured by the enemy, and their message is tampered with?
Ponder whether some of the Byzantine lieutenants are traitors and plan on betraying the army?
What if the general himself is corrupt and looking to spread discord among the generals?
With context to blockchains, each lieutenant is a node in the network, and these nodes need to reach a consensus to determine the current state of the protocol. For anything to happen, a supermajority (>2/3rd) of the network in a distributed system will need to come to a consensus. What this also means is that if a supermajority of the network is malicious (like in the case of a 51% attack), the system is vulnerable to failures.
Is Byzantine Generals’ Problem Solvable for 3 Nodes?
An interesting thing to note about distributed systems is that more than two-thirds of the participants need to be “loyal” for it to work. In fact, Berkely.edu did an interesting thought experiment to check whether a system with three nodes can bypass the Byzantine generals’ problem or not.
NOTE: This experiment uses the term “commanders” instead of “generals” as we have used so far.
The experiment has the following predefined assumptions:
All loyal lieutenants will obey the same order.
If the commander is loyal, then the loyal lieutenant obeys the order sent to them.
The content of the message sent is entirely under the control of the sender.
Only two messages can be sent: “attack” or “retreat.
Case #1: One of the lieutenants is dishonest
The loyal commander commands the lieutenants to attack.
Since Lieutenant 2 is a traitor, he reports to Lieutenant 1 that they received an order to retreat.
However, since we stated in our predefined assumptions that the honest lieutenant would obey the order of a commander, Lieutenant 1 will attack.
Case #2: The commander is dishonest
The dishonest commander sends contradictory messages to both the lieutenants.
Lieutenant 1 and 2 have no idea that they have received different messages.
As such, Lieutenant 1 will attack, while Lieutenant 2 retreats.
In both the cases defined above, the consensus breaks (the system doesn’t attack or retreat as a whole) because it fails to achieve a >2/3rd supermajority.
Now, let’s do something fun. Let’s increase the total network participants to four by adding one more lieutenant. [Images taken from this article]
We are going to repeat the same thought experiment as we did earlier, but this time, we are going to get a clear 2/3rd majority. So, if three out of the four nodes come to a consensus, then we are going to get a clear majority. Let’s explore the two cases we have explored above from the POV of Lieutenant 2.
Case #1: One of the lieutenants is dishonest
Lieutenant 3 (L3) is dishonest, while everyone else in the network is honest.
L3 plans to sow discord in the community by feeding L2 with false information.
The honest commander gives the message “v” to all the lieutenants.
L1 sends the message “v” to L2.
L3 attempts to confuse L2 by sending the message “x.”
L2 receives the following messages – (v,v,x). By taking a 2/3rd majority, L2 concludes that the correct message is “v.”
As you can see, the 2/3rd majority allows the system to be Byzantine fault-tolerant. So, even if one of the nodes turns corrupt, the entire system can still function.
Case #2: The commander is dishonest
Now, this is where things get a little complicated. What if the command center of this overall system itself is corrupt? Let’s see what happens:
The corrupt commander sends different messages x,y, and z to L1, L2, and L3, respectively.
Since the lieutenants are all honest, by the predefined conditions, since they believe that the commander is honest, they will forward the message verbatim.
After all the nodes have transferred their messages, each node will receive (x,y,z).
By the majority rule, the final consensus will be a majority(x,y,z). Since this majority is consistent among all the nodes, the system becomes fault-tolerant.
Now that we have a basic understanding of the mechanism, let’s take things one step further.
The Lamport, Pease and Shostak Byzantine Generals Algorithm
When Lamport, Pease, and Shostak first identified the problem, they created an algorithm to mitigate this issue. The algorithm assumes that:
There are n total nodes.
There are m malicious nodes.
N>3m, which ensures that a 2/3rd majority is maintained.
The algorithm has two stages:
Stage 1: This is the data collection stage, which has m+1 rounds. During this stage, the nodes are continuously sending and receiving messages.
Stage 2: This is the decision-making stage. Based on the data collected in stage 1, the system, as a whole, comes to a decision.
Now, let’s take a look at how this works in practice. We will be observing a system with one corrupt general (P1) and six honest lieutenants (P2-P7).
Note: The images used in Stage 1 and Stage 2 sections below have been taken from this article.
Stage 1: Data Collection
In the first stage, the algorithm conducts m+1 rounds of messaging between the nodes:
The corrupt general P0 sends orders to his lieutenants. The general doesn’t send any more messages after this round, and he doesn’t get any messages back either.
Since there is only one malicious element(m), the algorithm will run for m+1 = 2 rounds.
The commander gives a value “0” to lieutenants P2, P3, and P4. On the other hand, P5, P6, and P7 receive the value “1.” This happens in Round 0.
In the remaining rounds, each lieutenant creates a batch of messages, which consists of the value and a path. So, {0,12} -> means that P1 has messaged P2 with the value “0.”
So, at the end of round 1, the messages received look like this:
Now, let us look at what happens at the end of round 2:
Each node had six messages each at the end of round 1. In the second round, each node will once again send out these six messages to the six nodes, meaning each node sends out 36 messages in the second round.
During the first round, P2 received the following messages – {0,12}, {0,13}, {0,14}, {1,15}, {1,16}, and {1,17}.
In this new tuple, {0,132} will read like this – P2 says that in round 1, it got to know that P3 received the value “0” in round 0.
Now, P2, will send each of these messages to all the lieutenants, which means the new outputs from P2 are going to be – 0,122}, {0,132}, {0,142}, {1,152}, {1,162}, and {1,172}. {0,122} is redundant so as it signifies that P2 is talking to itself. So, it gets cancelled out.
Stage 2: Decision Making
Each node is accumulating multiple messages at the end of each round. The messages inside each node are stored in a tree format. Here are some properties of the tree that you must note:
Each round of messages occupies a corresponding rank within the tree.
Each component in the tree has three data points – an input value, a path, and an output value.
During Stage 1, we have already identified the input value and the path. We will determine the output value, aka the value that the system agrees upon via a 2/3rd majority in stage 2.
The following diagram is the tree representation of a system with six overall nodes with five honest lieutenants and one corrupt general.
Stage 2: Tree Representation
This tree has the following features:
The output part in each data set, aka the third value in the data set, has been initially set to “?”. This is because we don’t know the output value of the network yet.
Since there is only one malicious element (m), there will be two rounds of messaging (m+1). This is why the tree shown above has two levels.
In the first round, the general sends a value to the lieutenant. In the second round, each lieutenant broadcasts the value received to each other.
Each leaf node copies its input value to its output value. The value that occurs most frequently is assigned to the level above it.
This process continues until a majority value is assigned to the whole tree.
In the image above, the input values of the leaf nodes are {1,1,1,0,0}. Because the majority value is “1,” the output value of the level above it, aka level 0, is determined to be “1.”
Considering there are no other levels beyond that, the overall output value of a particular lieutenant tree is “1.”
In the system, all the lieutenants are honest, they will all come to the same output value: “1.” So, even if the general is dishonest, the lieutenants will still agree on the same value, becoming Byzantine fault-tolerant.
How does Blockchain Solve the Byzantine Generals Problem?
Now, let’s look beyond the generals and war metaphors and understand this problem with respect to blockchains and cryptocurrency. One of the fundamental issues that a decentralized payment system must solve is the issue of “double-spending.”
When a user spends the same instance of a cryptocurrency more than once, it’s known as a double-spending problem. To get a clearer picture of this, imagine spending the same $10 bill to conduct two different transactions at the same time. As you can imagine, this is impossible in cash-based transactions. However, for digital currencies, this is a genuine possibility. We can’t always trust the users to act in the interest of the system. Repeated double-spending attacks can and will render the entire system irrelevant.
So, how do you prevent the generals’ problem and double-spending? The solution lies in Byzantine fault-tolerant consensus algorithms.
What is a Byzantine fault tolerance algorithm?
Byzantine fault tolerance means that the algorithm should allow the system to make a cohesive, uniform decision, even if there are some corrupt elements present in the network. The way it does so is by seeking consensus within the distributed group. Consensus is a dynamic process of achieving agreement within a group, and the method with which they can reach consensus is known as “consensus mechanism.”
The properties of an ideal consensus mechanism are as follows:
It should seek to bring about as much agreement from the group as possible.
All participants should collaborate to achieve the best possible solution for the majority.
Every participant’s vote should have equal weightage.
As many people as possible should be involved in the process so that it addresses the true majority.
Prior to Bitcoin, there were several attempts at creating a decentralized digital currency like David Chaum’s DigiCash, Wei Dai’s B-Money, and Nick Szabo’s Bit Gold. However, they all failed because they weren’t able to implement a Byzantine generals fault-tolerant algorithm successfully. When Satoshi Nakamoto created Bitcoin, he mitigated this issue by integrating the protocol with a special class of consensus mechanisms called “Nakamoto Consensus.”
What is the solution to the Byzantine generals’ problem and how does it address double-spending?
In simple terms, in Nakamoto consensus, the nodes need to have some “skin-in-the-game” to incentivize them into participating honestly in the system. The Nakamoto consensus used in Bitcoin is called “proof-of-work (POW),” aka, “mining.” In this system, the participants or “miners,” spend a vast amount of computing resources to solve cryptographically hard puzzles. This spending of resources is also known as “work.” This is the skin that the miners have in the game.
How to mine cryptocurrency?
This is how the mining process works:
The distributed network agrees on a metric called “difficulty.” The value of this metric changes depending on the ease of mining within the system.
The miners pick up transactions that are waiting in the mempool and assembles them in a block.
The contents of the block are hashed.
A pseudorandom hexadecimal value called “nonce” is added in from the hash and the overall value is hashed again.
This value is then compared against the difficulty. If the value is smaller than difficulty, the network accepts the block and adds it to the main blockchain. In return, the miner is awarded a block reward.
If the hashed value is higher than the difficulty, the miner chooses a new nonce and the process is repeated until they find a value that’s less than the difficulty.
This process of finding the nonce and comparing it to the difficulty is extremely hard (especially in Bitcoin) and requires a lot of computational power.
POW with respect to the Byzantine Army
Now, let’s bring back the Byzantine generals problem and see how POW mitigates the original problem.
The general and his army decide on a difficulty metric. Let’s say that this metric states that the final hashed value must be less than “00001000.”
The general creates a message and hashes it until the value is lesser than the difficulty metric.
The general then passes along the nonce, the message, and the final hashed value to the messenger and tells them to relay it to the lieutenants.
If the messenger tries to tamper with the message, the final hash will change drastically. This is one of the properties of cryptographic hash functions called “snowball effect.” The idea is that a slight change in input can cause a drastic change in the output.
The only other option that the traitors have is to find another nonce that will result in a final hash that’s lesser than the difficulty metric. Since we already know that this is a resource-intensive process, the traitors won’t be able to find a new hash.
When the lieutenants receive the message, they can easily test the validity of it by hashing the nonce and the message and checking it against the final hash provided. This is the core theory behind POW – the process of procuring the hash is difficult; however, checking the validity of the solution is simple.
Dealing With Double Spending
Now, let us see how Bitcoin utilizes the blockchain to remediate double-spending. Suppose Alice has 1 BTC and wants to send it to two public addresses simultaneously. Both of these transactions end up in the mempool, after which either of the following happens:
The first transaction that receives enough confirmation is accepted into the block. The second transaction is recognized as invalid.
If both the transactions are simultaneously pulled from the mempool, the one with the highest amount of confirmation is included in the blockchain.
It should be noted that the POW algorithm isn’t byzantine fault-tolerant because of some mathematic or algorithmic magic. It’s secure only because the mining process itself is extremely expensive. For an attacker to take over more than 50% of the network’s hashing power, it would cost them a whopping $1.4 billion. Even if someone does manage to get that much hash power and conduct a 51% attack and start double-spending the coins, it will get devalued instantly. So:
The attack itself is extremely expensive.
The subsequent pay-off will be comparatively negligible.
Byzantine Generals Problem Summary
Bitcoin achieves byzantine fault tolerance via its POW algorithm and cleverly mitigates the traditional pitfalls of decentralized systems. By economically incentivizing miners by ensuring that they have some skin-in-the-game, Bitcoin has assured that its protocol is as fail-safe as possible. By solving this quandary, both Satoshi Nakamoto and Bitcoin have introduced us to the game-changing phenomenon known as the decentralized economy. Several other consensus algorithms have since come out like Proof-of-Stake (POS), Delegated Proof-of-Stake (DPOS), etc. which are not as wasteful as POW.
As use cases and innovations continue to grow, cryptocurrencies and blockchain technology will leave an indelible mark in global finance. Now more than ever, you should do everything you possibly can to equip yourself with as much knowledge about this space as you possibly can. At Ivan on Tech Academy, we have several high-value accredited courses on blockchain and cryptocurrency that have been created by our in-house trainers and industry experts. The information provided in the courses is beginner-friendly and will get you work-force ready in an industry that has become one of the fastest-growing sectors in the world today. If you want to know more about these courses, then click here.
