Byzantine Generals: Why Bitcoin Has Miners and How it is Secure

Through its mining concept, Bitcoin, a relatively small currency with just 2.9 million to 5.8 million unique active users (University of Cambridge, 2016) has created the world's most powerful computer network - far exceeding 100x the power of Google's computers.

It was also the first real world solution to the Byzantine General's Problem - a mathematically unresolvable conflict that disrupts the reliability of all distributed information systems.

Why Bother with Mining?

Bitcoin can be slow and expensive because you need to pay transaction fees to incentivize miners to solve difficult Proof of Work problems. Check out my earlier post for background.

So why don't the nodes just update their ledgers straight away? Alice pays Bob and everyone updates the ledger. Easy right? Well unfortunately not.

Enter the Byzantine Generals

A group of super smart computer scientists published a famous article in 1982 called the Byzantine General's Problem. Why Byzantine Generals? You can read up on it here (basically the lead author thought it was fun and inoffensive).

The generals were planning to invade a city and needed to coordinate a synchronized attack.

They faced two key problems.

• Trust: The generals suspected that one of the army officers was a spy.
• Coordination: To be sure their messages arrived safely, the generals requested confirmation messages to be sent in return. Soon they found themselves sending confirmation messages for confirmation messages ... it quickly got messy.

Bitcoin - Minimizing Trust and Coordination

Satoshi's innovative solution wasn't to resolve these problems but instead, to minimize their importance.

• Trust: What if some of the miners were dodgy? Instead of trusting nodes to update the ledger honestly, Bitcoin pays them with transaction fees and free coins. Of course Bitcoin can't pay them all, so it created a game where only one miner gets paid roughly every 10 minutes.
• Coordination: If one miner doesn't get a transaction message (i.e. his internet is down) the ledgers won't be the same - which one do you trust? Bitcoin doesn't need the miners to agree on a ledger (obtain consensus). The "source of truth" is always the block chain with the most accumulated difficulty (the one that has been mined with the most power). This happens naturally - no miner wants to work on the shorter chain because its Proof of Work puzzle has already been solved. Once a miner solves a Proof of Work (and adds a block of transactions), other miners check if the solution is valid and then immediately move on to the next puzzle to maximize their expected payoff.

Read Satoshi's own explanation of how the Proof of Work concept solves the Byzantine General's Problem.

Preventing Fraudulent Transactions

A few weeks ago, I paid for a dinner in Bitcoin and I walked out of the restaurant before the transaction was mined (it took 5 minutes to mine). So what risk was the merchant taking? What are the potential frauds with Bitcoin?

Fraud 1 - Double Spending (Race Attack)

You can never send or transfer bitcoins you don't have. So there's no way my transaction to the Merchant can even show as pending without me having the right amount of bitcoin in my wallet - it would just get ignored by all the nodes.

Nevertheless, I could set up two unconfirmed transactions using the same bitcoins in my account. The transaction with the highest fee should get mined/confirmed first. Knowing this, I could tailor it so that the transaction to the merchant has the lowest fee and therefore is the least likely to get mined. After I walk out of the restaurant my transaction to the merchant would eventually get rejected.

To mitigate this risk, all the merchant needs to do is wait for a confirmation that the transaction has been mined (for my dinner it took 5 minutes). Only one of the two transactions will be accepted by the network, the other would be rejected.

In my real life example, the Merchant trusted me and let me leave before the transaction was mined. He could see it as "pending" and was reasonably confident that it will eventually be mined.

Fraud 2 - One Dodgy Miner (Finney Attack)

This is a variant of the above attack and involves collusion with a dodgy miner. If a miner solved the last Proof of Work puzzle he has the right to add transactions of his choosing to the blockchain, so he could prioritize the transaction I wanted to go through first.

The mitigant for this is the same as the above. The merchant need only wait until he receives a confirmation to be sure my transaction wasn't rejected.

Fraud 3 - Alternative History

Remember how the miners use the blockchain with the most accumulated difficulty as the ultimate source of truth? In an Alternative History attack, a miner uses this to his advantage.

In an Alternative History attack, one miner solves the Proof of Work and processes the payment to the Merchant. The Merchant receives the confirmation and delivers the good.

But secretly the dodgy miner is mining a separate fork/chain which doesn't include the block that pays the merchant. This attack only works if the miner is able to add more computational power to his folked chain - he wants his forked chain to become the source of truth and to do so he has to mine quicker than all the rest.

Realistically this is very difficult to achieve. The miner would need to have enormous computing power to outpace all the other miners. The merchant can mitigate this attack by waiting for multiple confirmations - the odds that a miner can outpace all the other miners would decrease with each confirmation. A study back in 2012 found that if a miner had 10% of the total computing power, the odds of it succeeding with this attack after 6 confirmations was 0.1%.

Fraud 4 - Majority (51%) Attack

The majority attack (or 51% attack) occurs when a miner controls the majority of the network's computing power. It's the same as the Alternative History attack but in this instance, the miner has control and will eventually outpace the other computers. The miner can choose the ledger it wants to use.

This is bitcoin's greatest vulnerability. Nonetheless, it is extremely costly to build enough computing power to represent 51% of the network.

This website provides an estimate of the cost - currently the hardware alone would cost ~USD3bn and the daily running cost would be ~USD6m.

https://gobitcoin.io/tools/cost-51-attack/

If the community suspected that someone was attempting a 51% attack, they could folk the currency and change the mining algorithm so that the hostile miner was suddenly unable to mine (i.e. you change the hardware needed to mine).

Who Are the Powerful Miners?

Given the Majority attack is bitcoin's greatest vulnerability, it is important to monitor mining market share to identify the concentration and potential threat.

To maximize efficiency, miners have grouped together over time into "mining pools" to share their resources and increase the chance of solving the Proof of Work. It's essentially teamwork - anyone can buy an application-specific integrated circuit ("ASIC") and join a mining pool. Some mining pools have centralized decision making whereas others are more decentralized.

Roughly 60% of these are based in China and 15% is the US (Cambridge University, 2016). They choose sites where the energy and running costs are low.

https://blockchain.info/pools

This was part 5 of a series I'm writing on cryptocurrency. Check out part 1, part 2, part 3 and part 4.

Upvotes are appreciated for motivation. Comments/questions/corrections are welcomed. 🙃