The Byzantine Generals’ Problem

Developing a system like Bitcoin that is both distributed and reliable is incredibly difficult. This applies to any form of distributed system however, not just crypto currencies, where there is no central control enforcing trust. This issue has become known as the Byzantine Generals’ Problem (BGP).

Definition

The BGP was first proposed in 1982 relating to computer science fault tolerance and describes it as the following:

"We imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching agreement. The generals must have an algorithm to guarantee that (A) All loyal generals decide upon the same plan of action and (B) A small number of traitors cannot cause the loyal generals to adopt a bad plan.”

Marshall Pease, Robert Shostak & Leslie Lamport

What does this mean?

Taking a look at the diagram, we can see that traitors can prevent a group from arriving at consensus. Whilst in the Byzantine army, this could be a commander relaying false information, or a rogue lieutenant not passing on messages correctly, within distributed ledger technology this would be a malicious player seeking to process fraudulent transactions.

Send in Satoshi!

Our diagram is a simplistic one, so as you can imagine as a network grows and new users and connections develop, complexity increases exponentially and reaching consensus is far more difficult. This therefore explains why before Bitcoin, decentralised ledgers were not feasible.

The pseudonym Satoshi Nakamoto penned the famous Bitcoin whitepaper on 31st October 2008. It contained arguably the best solution to the BGP developed so far, and now enjoys the broadest adoption.

So how does Bitcoin actually solve this?

The BGP manifests itself within the issue of blockchain synchronisation. How does everyone’s ledger remain in sync and reach consensus in a distributed way? When a transaction is sent across the network, it is broadcast to all users. It is unconfirmed initially however due to the BGP. Users don’t know if a dishonest player has attempted to double spend the same Bitcoin for example, therefore which transaction do they accept? Bitcoin resolves the BGP and is able to confirm transactions through mining.

Mining solves the BGP by ensuring that transactions can only be confirmed if enough computational power was used to solve the block that contained them. This process can be generalised in 3 steps:

1. Compile Input Data - Miners collate a new block of broadcasted transactions and verify they are valid. The hash of the last blockchain block is added to this along with a random number (called a “nonce”).

2. Perform a cryptographic calculation (SHA-256 in Bitcoin’s case) to the data from step 1, producing an output hash (a series of characters).

3. This hash is checked against a desired pattern. If it matches this pattern, the “puzzle” is solved and that miner wins the prize for that block (currently 12.5 BTC, plus the transaction fees from the block). If not, another nonce is tried and the steps are repeated (until someone successfully mines that block and therefore solves the “proof-of-work” problem). The mining difficulty of solving this puzzle is automatically adjusted according to the overall computing power on the network. This way the amount of time it takes to solve a block remains at 10 minutes on average.

The winning block is then verified by nodes and broadcast to the network. In this way it acts like a lottery for who gets to enter the next transactions in the chain, preventing one party from controlling the ledger.

Some may suggest doesn’t this just shift the BGP to the miners however? What if two miners produce blocks at similar times or an attacker is attempting to reverse transactions, how do nodes choose which block to include? In reality it doesn’t shift the problem as nodes must always choose the chain that is the “longest”, therefore the chain that took the most computational power to create. The shorter blockchain is subsequently discarded as an orphan block and its transactions must be processed again if they weren’t already part of the successful block. A traitor cannot statistically act maliciously (such as spending BTC in one block and erasing that transaction in the next) as block creation is random, unless they have enough hash power to produce the majority of new blocks (a 51% attack). The costs and risk of such an attack are so severe in the Bitcoin blockchain that it is highly unlikely. Although mining pools can be made up of many thousands of separate entities working together (for the time being - there is no fixed coalition here) to solve blocks and are therefore unlikely to collude, some have concerns over the combined hashing power of certain pools or related pools. Whenever these percentages have risen too high in the past however, members of these pools have moved voluntarily in order to preserve confidence in the system.

Therefore the process of randomly selecting a nonce to produce a chain, combined with always selecting the longest (most difficult) chain, and provided honest miners have at least 50% of the overall hash power, Bitcoin solves the BGP.

Conclusion

There are certainly caveats, though for the first time in our history, Bitcoin presented a feasible means of creating decentralised ledgers and reaching distributed consensus. As a result it currently enjoys the highest adaption of any such solution. Whilst this may or may not last in the future, it was the zero to one innovation breakthrough in solving the BGP and the implications of this will no doubt extend beyond its initial use case.

By James Hunt (@humanjets)