The article below first appeared on bitcoin.nl on April 11, 2017.

Please note : this is a theoretical article, to provide background for the interested reader. This article was previously published in MCA?? with introductory text.

The Byzantine Generals problem

The Byzantine Generals problem is an example of a thought experiment in which communication and knowledge play an important role. The main question in this problem is whether unanimity can be achieved in a distributed system. This article looks at how proof-of-work, which we know from Bitcoin, is a solution to this problem.

The classic problem

Computer networks must be able to deal with conflicting information in order to make the right decisions. Several requests to a server can cause conflicts in the processes. The problem of receiving different, conflicting, requests from computers or people is similar to the scenario from the original Byzantine Generals problem where a group of generals wants to work together. The classic version of this problem is applicable to several systems.

The classic version of the Byzantine Generals problem is as follows:

Several units of the Byzantine army are stationed outside an enemy city. Each unit is commanded by a separate general. The generals are under orders to attack the city with a majority of the units at the same time, because the chance of an attack succeeding with a limited number of units is too small. The generals must agree on whether to attack or retreat.

However, there is uncertainty in the communication: what if one of the generals is a traitor with evil intentions? In order to arrive at a good solution to this problem, the solution must satisfy two conditions:

1. All loyal generals must come to the same plan of action and, because the plan must also be a reasonable plan,
2. a small number of traitors must not be able to ensure that the generals choose a bad plan.

These conditions can be met if all generals observe the enemy and communicate their observations to the other generals. Based on the information gathered by other generals, each general can determine the best plan and vote for that plan.

We look at these conditions from a simplified variant where two different plans are possible: attack or retreat. The solution is then that the official plan is determined on the basis of which option received the most votes. In this scenario, a small number of traitors can only influence the outcome if the generals are all equally divided in their choice. There are no bad plans as long as the loyal generals come to the same plan of action. Voting thus offers a solution to the problem that satisfies both conditions.

Reframe the problem

The Byzantine Generals problem can be more generally stated as a multi-actor decision problem. Several actors are uncertain about the information they receive from others and must therefore be able to verify the information to ensure that the information is true. An example of where this problem occurs is Bitcoin’s peer-to-peer network.

Satoshi Nakamoto reformulated the classic problem to apply to modern computer networks. We now look at the problem from this situation where the generals are able to communicate with each other over a computer network:

All generals in the Byzantine army have a computer and orders to attack the king’s wi-fi, by brute forcing the wi-fi’s password . Once the attack is launched, there is only a limited time to crack the password and cover traces before the attack is discovered. The generals only have enough processing power if the majority of the generals attack at the same time. The generals don’t care what the exact time of the attack is, as long as the majority attack at the same time.

The generals agree that the first suggested time is the official time of the attack. It doesn’t matter if the proposed time comes from a traitor who tries to sabotage the plan, because as long as the majority agrees on the moment of the attack, there are no bad plans in this scenario.

The problem in this scenario is that there is always some delay in communication over a network; a message is not received immediately and the amount of delay varies by location. As a result, when several generals send out a proposal around the same time, the generals can receive the messages in different orders.

We can now modify the two conditions from the classic problem so that they are applicable to the computer network version of the problem. The conditions are as follows:

1. All processes must agree unanimously on a given value, despite a minority of erroneous processes arbitrarily deviating from the protocol
2. The generals must be able to check that together they have enough computing power to launch a successful attack at the proposed time.

These two conditions can be met by using a more complex voting system, similar to the voting system used in the classic variant of the problem

Bitcoin

The consensus mechanism in Bitcoin should ensure that the participants in the network agree unanimously on which bitcoins belong to whom ( ie which bitcoins belong to which public keys). The problem that emerges is that the network must be able to verify that the bitcoins in one transaction have not already been spent in another transaction. As in the Byzantine Generals problem, with Bitcoin there is no central authority that can verify that transactions (or messages, in the case of the computer network version of the Byzantine Generals problem) are valid. This therefore requires a solution without a single trusted party: decentralized.

The problem can be solved by announcing all transactions publicly and adhering to the rule that the transaction seen first is valid. Each node in the network then checks whether the bitcoins in a specific transaction have not been spent before. However, there is still uncertainty in this proposal: due to the delay in the network, not all transactions may arrive at the same time everywhere. As a result, the set of new transactions may not be consistent across nodes.

To solve this problem and to reach consensus on the order of transactions, the transactions are included in a proof-of-work block with a timestamp. This allows agreement on the order of transactions: the block hash includes a reference to the previous block, new transactions, and a timestamp, proving that the data in a block existed at that point in time. After all, the data as in the block could not have been included in the hash if it did not exist at that point in time.

Proof of Work

proof-of-work to timestamp and hash transaction data . Each miner in the network works to solve a fairly complex cryptographic puzzle to meet the conditions of a valid proof-of-work block. The solution to each puzzle is a SHA-256 hash of all data in a block. The puzzles are designed in such a way that a solution is found every ten minutes on average.

As soon as a solution is found, the hash of the block is published on the network. The amount of computing power spent on finding a solution works like a proof-of-work: a block cannot be modified without redoing the work (after all, every modification to the data leads to a different solution). Also, by including a reference to the previous block in each block, the blocks are linked together in order (this gives us the blockchain ). Changing the data and recreating a block therefore also means that all subsequent blocks must be redone. The network sees the longest chain as a valid chain, because the assumption is that the majority of the network has an interest in acting benignly.

This process can also be seen as a voting process, where each added block counts as a vote for that specific transaction history and all honest nodes work to extend the longest chain.

Attack on the network

When an attacker tries to do a so -called double-spend ( ie spending the same bitcoins twice), the attacker will have to recreate the block containing the transaction. Not only that block, but also all blocks that have come after that have to be redone to produce a longer chain than the current ‘fair’ chain. After all, the attack is only successful if the majority of the network switches to the counterfeit chain. With every added block, the chance that a transaction in a block will be counterfeited decreases: with every added block, more work has to be done again. The chance that an attacker with limited computing power can catch up with the fair chain is very small after six to eight blocks and quickly becomes negligible after that.

Byzantine Consensus by Proof-of-Work

Bitcoin’s proof-of-work serves as a solution to the computer network version of the Byzantine Generals problem. Where the Bitcoin network reaches consensus on the order of transactions, the generals should be able to reach consensus on attack time. To reiterate, the generals of the Byzantine army want to brute force the king’s wi-fi and each general is allowed to propose a time to attack. The first plan received becomes the official attack plan. The problem, as we wrote earlier, is that two or more generals can send out a different plan at about the same time. This problem can be solved by a simplified version of proof-of-work. Instead of applying proof-of-work to track transactions, proof-of-work can be applied to ensure that the generals reach consensus on the plan.

Each general considers the first attack time plan received as the official plan and begins working on a solution to a proof-of-work puzzle. Again, each puzzle is so difficult that a solution is found every ten minutes on average, but only if all generals work on the same puzzle. As soon as one of the generals finds a solution, this general publishes his solution on the network together with the plan.

When the other generals receive the solution along with the plan, they adapt the plan they are working on to the received plan. The generals now proceed to solve the next proof-of-work puzzle so that it can be linked to the first solution received. Again, the rule is that the longest chain is followed, as the assumption is that the majority of generals act benevolently. If there are still generals working on another plan after a number of solutions, they will now also focus on the longest chain. This fulfills the first condition: all generals agree on the time of attack.

The second condition can be met by continuing to find proof-of-work solutions for a while. After all generals work on the same chain, an average of six solutions will be added to the longest chain after an hour. The generals can now verify that they have enough processing power to carry out the attack based on the number of solutions found within a certain time. The generals can now conclude that the majority are working on the same attack plan and they have enough computing power to safely execute the attack.

Conclusion

Bitcoin’s consensus protocol can function as a substitute for trusted parties by establishing a peer-to-peer network where no central authority is present. Bitcoin’s consensus protocol, proof-of-work, solves the absence of a central authority in the Byzantine Generals problem. In addition to the generals reaching consensus on the time of the attack, the generals can also estimate the probability of success based on the amount of computing power working on the same plan. It removes uncertainty about different attack plans due to network delays and makes the risk of sabotage negligible.