The Byzantine Generals Problem, 51% Attacks, and Proof-of-Work
How Blockchains Combat Common Vulnerabilities in Distributed Computing
The Byzantine Generals problem is a problem in distributed computing that arises at the point of making decisions. In such a decentralized setting, there’s the question: “how do we make collective decisions?”. If it were a centralized system, the answer is obvious: someone at the top is the decision maker and that person is the source of truth. However, in a decentralized system, there are multiple independent actors and the answer becomes complex.
Here’s an illustration: suppose several Byzantine Generals are preparing to attack a city. Each General’s army is located at various points around the city, distant from the others, and has their own resources and supply lines. However, the number of troops needed to successfully take the city is greater than each individual army. Each General is to cast a vote through a messenger(s) to the other generals to attack or to retreat, and they will act together based on the majority vote (>50%). If some Generals attack and others do not, they will be defeated. To survive, they must attack together or retreat together.
Things become complicated by the presence of treacherous Generals (bad actors). They may vote for a subpar decision or even communicate different answers to other Generals. Suppose the Generals are nine in number and the vote is split with four to attack and four to retreat while the bad actor has the deciding vote, the bad actor may send a vote of attack to one General and a vote of retreat to another General. This forks the decision, causing some Generals to attack and some to retreat, thus sabotaging the campaign.
There is a related problem in cryptocurrencies, known as the “Double-Spending” problem. But before looking into that, let’s go through some background basics. Decentralized blockchains have two important characteristics — they are open source and immutable.
Being open source means anyone can write to the blockchain’s database and verify data validity. Immutability means actors can only ever add to the blockchain. Once a user adds data to the blockchain, it cannot be deleted or modified. The state may be updated by an additional block, but the data added to the chain in the original block cannot be modified. Blockchain transactions can be tracked and verified to be legitimate, and users cannot change their balance from 1 to 100 without first receiving funds from somewhere else in the blockchain. These characteristics combine to create a source of truth that anyone can access and write to.
Let’s use the Bitcoin protocol as an example. Typically, transactions will occur like this: Alice has 1 bitcoin and decides to pay Bob 1 bitcoin for a Pokémon card. When Alice sends the funds to Bob, the transaction is recorded by a node (computing unit) on the blockchain network. The node verifies the transaction against transactions in the previous blocks, asking “does this account have enough funds for this transaction?”. If the account has enough funds, the transaction succeeds and the node will include the transaction to the block it is working on adding to the blockchain. If not, the transaction is thrown out.
When the node solves the proof-of-work requirement, it adds the block to the blockchain and collects the bitcoin reward given by the network. Each node races to add blocks to the blockchain to collect the reward and verifies transactions in the process. In our example, the node will verify that the transaction is legitimate by checking Alice’s balance and will apply the funds to Bob’s account after solving the proof-of-work requirement.
Back to the Double-Spending problem…
Now let’s say Alice promises to pay both Bob and Charlotte 1 bitcoin each (for their rare Pokémon cards of course). Although she does not have enough funds to pay both Bob and Charlotte, she can create two transactions on different nodes:
- 1 bitcoin paid to Bob
- 1 bitcoin paid to Charlotte
In both cases, the transactions seem legitimate. One node thinks Alice has 1 bitcoin to pay Bob. Another node thinks Alice has 1 bitcoin to pay Charlotte. If both blocks get added to the chain then Alice has spent double the funds she started with. However, blockchains are protected from such a scenario because only one block can be added to the chain at a time and each block is linked to the previous block.
Blocks are added in a “first-come-first-serve” fashion and each block has a timestamp to show where it is in line. This allows for a clear order of when transactions occurred, so Alice cannot pay Bob and Charlotte the same coin. (This solves the trivial Double-Spending problem).
However, things get more interesting when there’s a tie (the non-trivial Double-Spending problem). What happens if Alice somehow adds each transaction to two different blocks with the exact same timestamp? At this point, there is a fork, and the network must collectively decide which way to go.
If a node receives both blocks, it will do two things: work on the block that arrived first and keep the other block in memory in case that branch’s chain is longer thus becoming the source of truth. Let’s break this down with an example. Suppose node-1 receives Bob’s transaction and begins working on block B and node-2 receives Charlotte’s transaction and adds that to block C. Assuming both blocks satisfy the proof-of-work requirement with the same timestamp, they will tie, broadcast their respective blocks to the network, and continue to work on their respective chains.
Since both nodes added a block simultaneously, the other nodes in the network would work on the block they received first, saving the block they received second. The tie is broken when one chain becomes longer than the other. If a node has been working on the shorter chain, it will discard its work and begin working on the new (longer) chain. If the second set of blocks also ties, the process continues until one chain is longer than the other. In summary, blockchains defend against the double-spending problem by using timestamps to determine the order of transactions.
The scenario with these two chains is analogous to the two decisions offered to the Byzantine Generals. The nodes must act in unison to maintain the integrity of the blockchain, just as the generals must act in unison to be successful in their campaign against the city. Their action is determined by the majority rule, in other words, a decision is made with >50% consensus.
This system works when the majority of nodes are honest players. On the flip side, if the majority are bad actors, they could use their power to process transactions faster and take back the payments they have already made, leading to a 51% attack.
51% Attacks
A 51% attack occurs when an individual entity or a group of miners gain control of more than 50% of a blockchain’s hash rate and thereby compromise the network. An attacker with the majority of computing power can work on one block (with payments they have already made) and switch to another block. The attacker can build a competing chain faster than the other nodes in the network because the attacker controls the majority of computing power.
If the bad actor does this, it de-legitimizes the value of the network. No one would want to put their money into a system that could take their funds away from them at will. To combat this, blockchains offer rewards for successfully adding blocks to the chain. At this point, the attacker can choose to collect the reward and add to their own wealth or take back payments and devalue their own wealth.
[The attacker] ought to find it more profitable to play by the rules, such rules that favour him with more new coins than everyone else combined, than to undermine the system and the validity of his own wealth.
— Satoshi Nakamoto (Bitcoin: A Peer-to-Peer Electronic Cash System).
This reward mechanism is expected to serve as an incentive to keep the blockchain running honestly, thereby maintaining the integrity of the system and preventing a 51% attack even in the case of a 51% control.
A version of this article initially appeared in BanklessDAO’s DeFi Download newsletter on September 1, 2022.
Author Bio
Jake and Stake is a writer and editor at BanklessDAO. He is the creator of and contributor to the DeFi Download, with a background in software engineering and cybersecurity.
Editor Bio
Kornekt is a writer and editor with strong conviction in the world Web3 creates.
Designer Bio
Trewkat is a writer and editor at BanklessDAO. She’s interested in learning as much as possible about crypto and NFTs, with a particular focus on how best to communicate this knowledge to others.
BanklessDAO is an education and media engine dedicated to helping individuals achieve financial independence.
This post does not contain financial advice, only educational information. By reading this article, you agree and affirm the above, as well as that you are not being solicited to make a financial decision, and that you in no way are receiving any fiduciary projection, promise, or tacit inference of your ability to achieve financial gains.
Bankless Publishing is always accepting submissions for publication. We’d love to read your work, so please submit your article here!
More Like This
Programmed To Fail by Psalm_Ogbonna
The Centralization Paradox Limiting DAOs by Kornekt
Technologists Who Don’t Understand Technology by Zero Mass
