Skip to main content



A Simple Expanation of The Game Theory Behind Bitcoin’s Proof of Work System

Link: Bitcoin: A Peer-to-Peer Electronic Cash System

This is oversimplified and assumes a very basic understanding of digital signatures and hash functions.

Blockchains attempt to solve the problem of coordinating distributed and untrustworthy players into a single secure and global network. As there can be no master coordinator (like in a modern client-server database) all of the players must reach consensus only by talking to other players. This requires Practical Byzantine Fault Tolerance, which comes from a 1982 paper The Byzantine General’s Problem.

This game goes as such: There are a number of generals plotting to attack a town. However, they all have to agree on whether to attack or retreat to get a reward. Additionally, communication between the generals is unreliable (messengers might be killed or could be traitors) and one or more might be traitors, sending different information to different generals. Bitcoin was the first to solve this problem in a practical sense, where the network aligned the economic incentives of the majority around acting truthfully using public/private key cryptography and the proof of work system.

A miner first cryptographically verifies that every message it received from other parties is genuine (it actually came from the party the message states it came from) using public keys attached to the transactions. After that, it verifies that every message makes sense. For example, if the miner receives two messages signed by the same private key saying opposite things (attack/retreat or send all my money to person a/b) it will ignore one of them (in Bitcoin the miner chooses based on the message with the highest bounty or “transaction fee” attached to it by the sender). Additionally, the miner ignores transactions that try to spend money that doesn’t exist. Finally, the miner is ready to start the most computationally intensive portion of the process.

The miner next bunches these verified transactions together into a block, adds a small random number called a nonce, and runs the resulting data through a hash function. Using an arbitrary difficulty (which the network previously agreed upon) the miner will change this nonce and run the hash function again and again until it finds a combination that results in a hash that meets some arbitrary specification (e.g., it must end in five zeros). After that, other miners independently verify the block is valid begin to build their own blocks on top of it if and only if this block is the head of the longest chain those other miners know about. If a different miner found a valid solution first that other miners build on that block and pretend the new one doesn’t exist (the block is orphaned). The dominant strategy for miners in a network where the majority not colluding is therefore to act truthfully, as otherwise they lose the reward (block reward and transaction fees) they reap if their block is accepted and built upon by the majority.

As more and more Bitcoin miners compete for a limited allowed number of blocks per hour (currently at 6) the difficulty increases, necessitating more and more computing power. The Proof of Work system dooms Bitcoin to cost more and more money to secure and take a larger and larger toll on the environment (through the miners’ increasing demand for electricity). However, the world of blockchain is changing as innovative new solutions to the Generals Problem are introduced. One of the most fascinating of these to me is Ethereum’s Casper Sharding+Beacon Chain system. However, I’ll save that for the next post.

Comments

Leave a Reply

Blogging Calendar

October 2018
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
293031  

Archives