Introduction to Blockchain through Cryptoeconomics, Part 2: Proof of Work and Nakamoto Consensus
This is part two of an introductory series about the cryptoeconomic incentive systems that underlie different blockchain protocols and emerging research questions in the blockchain technology space. Check out part 1 here — this post assumes a reading of part 1.
Section 1: Proposed Solutions to DoS
In the previous post, we established a need for a method to prevent denial of service attacks launched by miners themselves. That is, we needed to figure out how to prevent those who “own” the network from destroying it, which is a fundamentally difficult problem. Here we discuss some of the proposed solutions to this specific problem, and dive deeply into one the solutions in particular: Proof of Work (PoW).
We pose three potential solutions:
- Only have trusted miners . In this proposed model, the only nodes allowed to propose blocks to the network are the ones that the rest of the network trusts to not act subversively. This is the model that Ripple, Stellar, and “permissioned chains” follow. (A permissioned blockchain is one that only pre-selected entities have write access to.)
- Costly Puzzles: make it difficult and costly to include any new block. In such a scheme, proposing one block will cost a miner $100, and proposing 100 blocks will cost $10,000, so it is too costly for a miner to DoS the network with loads of blocks. This is the idea of Proof of Work, and it is used by Bitcoin and most other public blockchains today.
- Create trust through severe punishments for misbehavior and rewards for honest behavior. This is a characteristic of many “Proof of Stake” blockchain systems.
In this post, we discuss the first two potential solutions — trusted miners and costly puzzles. We will discuss Proof of Stake in the next blog post.
Section 2: Trusted Miners
The first proposed solution, to only have trusted nodes, seems to be viable from a technical point of view, but maybe not from a philosophical point of view in that the network is not fully decentralized. Remember why we wanted to disincentivize excessive block creation in the first place — because anyone at all could become a miner and DoS the network by creating multiple blocks. If we could trust that those that add to the blockchain wouldn’t spam it or attack it, then we wouldn’t need to impose costs on them, and thus, on the blockchains.
In this case, these trusted nodes would need to register an ID that corresponds to their real life identity. Some protocols like Stellar utilize a method in which each node designates what other nodes in the network they believe are honest. As a node gets more attestations from peers that it is honest, it attains more “voting power” in the network.
(For a beginner friendly, but more nuanced explanation of Stellar’s protocol, see Adventures in Galactic Consensus.)
Ripple, EOS, and other permissioned ledgers, utilize this idea of having trusted nodes propose blocks. Though these solutions work fine in theory, there remains a fundamental problem. They require trust and centralization (because only a central few nodes can add to the blockchain), and forgo privacy by making public IDs known. This may defeat the purpose of creating a blockchain, or ‘trustless’ ledger, in the first place. If we know the identities of each node on the network, blockchains lose one of their fundamental benefits for miners, (pseudo)anonymity, in which case the advantages of using a blockchain over a centralized solution are primarily restricted to auditability and tamper-resistant data. If we want to preserve the decentralization and (pseudo)anonymity of blockchains for miners, protocols like Ripple and Stellar do not work. We cannot rely on real-world identity for evidence of future good behavior in order to preserve these properties. So the problem of creating a trustless, secure ledger remains to be solved in order to not impose costs on miners.
Section 3: Costly Puzzles
What if we made it very difficult and costly for miners to propose each and every block? We could have these costs scale linearly in the number of blocks a miner proposes. This means that if it takes $1,000 to propose a block, and $10,000 to propose 10 blocks, a miner would never propose a useless block or try to spam the blockchain with multiple blocks, because that would be extremely expensive. That is, in order to propose a block, miners would have to expend a serious amount of time, money, and electricity. Thus, in order to recoup their losses, miners would have to be extremely choosy and only include transactions in their blocks that contain sufficiently high transaction fees. As such, the idea of bloating the chain with trivial blocks is no longer economically feasible.
This idea is a very good one, and it is called Proof of Work. It is Bitcoin’s solution to the DoS problem. In order to propose a block, a miner has to solve a very difficult Proof of Work puzzle, which takes heavy duty mining equipment and a lot of electricity. As seen in practice, Proof of Work has been effective in preventing DoS Attacks. Proof of Work has a number of real, tangible further benefits which we discuss later.
(Side note: The kind of algorithmic puzzles that Bitcoin requires are computationally “hard” to find an answer to, but easy to check the answer to. They are outside the scope of this post. If interested, read up on HashCash.)
Section 4: Advantages of PoW
The concept of PoW has some notable advantages over other methods. By slowing down transaction speeds:
1. Consensus is easier: When it is hard to propose a valid block, this limits the number of blocks that can be created. Imagine there were millions of blocks created every second — in this case it would be extremely difficult to deduce which blocks are valid following the longest chain consensus rule (described below). Therefore, with a limited number of blocks created, nodes have a sufficient amount of time to propagate the block across the network before a new block is proposed.
2. Attacks are expensive: attacks have a large economic cost for an attacker, as the attacker has to do more work than the rest of the network has done, requiring a significant amount of computational power, electricity, time, and hardware resources. In fact, Bitcoin is designed such that attacks are more expensive than the gains an attacker could make (with the exception of selfish mining attacks).
Section 5: Game Theory of the Longest Chain
So now, we have miners who are listening responsibly for transactions, and transactors who are transacting on an as-needed basis. Miners compile their transactions into a block and then solve a difficult PoW puzzle so that they can propose their block. The Bitcoin protocol is set such that the network will create one block every 10 minutes on average.
However, there remains a fundamental issue: What happens if two different miners solve their PoW puzzle at the same time? Which block gets included in the blockchain? Said another way, how do we get everyone to agree on the same version of the blockchain?
There is value to be gained by disagreeing with or ignoring blocks proposed by others; if you are the miner to propose the next block, you receive extra monetary gain in the form of coinbase transaction rewards (the namesake for the Coinbase company) and transaction fees, so you should just ignore blocks found by other miners before you, right? This also presents a difficult game theory question, one of consensus.
Satoshi’s answer is that everyone should always mine on the longest chain.
This is akin to a majority-vote system. The reason is because the longest chain is the version of the blockchain that the majority of CPUs have informally agreed to honor; it has become the longest because most miners have put their time, electricity, and computational resources behind mining it. A miner doesn’t get money for a block that is not eventually included in the longest chain. Therefore, in order for the miner’s coinbase transactions to be honored, it is optimal for them to start mining on top of the longest chain. Since each miner expects every other miner to start mining on the longest chain, every miner will mine on the longest chain, thus honoring the longest chain rule. This is higher-order thinking and superrationality at work. Said succinctly, you default to the longest chain because you know most people already have and you expect everyone else to do so. This is known as Nakamoto consensus.
However, this means that if a miner starts mining on a chain, and then sees a new chain that is longer, she should stop mining on the original chain and start mining on the new longer chain. Contrary to popular belief, this implies that the Bitcoin blockchain is mutable by design! There is no transaction finality because, regardless of what you think you know about the transaction history, your history will be overwritten by any other longer, legitimate chain. For example, in your view of the blockchain where Alice and Bob are transactors and Alice sends a 5 BTC transaction to Bob, Alice’s 5 BTC transaction to Bob may be included, but if someone sends you a longer chain that does not include Alice’s transaction, you switch chains, and you start to accept that Alice never sent Bob 5 BTC! If the majority of miners switch over to this longer chain (as they should), then Bob will be unable to spend those 5 BTC that he thought he owned because miners agree that he never received them!
As you can see, the Bitcoin blockchain is subjective by nature. Fortunately, you can usually assure that a transaction will be part of the longest chain with some high probability and in normal conditions, it is very unlikely someone can rewrite the chain’s history.
To illustrate this point in economic terms, imagine that you see a chain which has Alice and Bob’s transaction contained in a block that was mined roughly 10 blocks ago and this is the longest chain you are aware of. In order for someone to create a longer version of the blockchain that doesn’t include the transaction sent from Alice to Bob, they must mine at least 11 blocks. If each block’s PoW algorithm takes $100,000 to mine, then that attack costs at least $1.1 million. Proof of Work therefore makes the economic cost of creating a different longest chain very expensive. In the meanwhile, the current version of the blockchain is also growing, probably faster than the attacker’s version of the chain. It’s a game of catch-up that, normally, is futile for the attacker.
But what happens if conditions aren’t normal?
Section 6: The 51% Attack
Given that there is no finality in traditional Proof of Work blockchains like Bitcoin, this exposes a potential attack vector; the 51% attack. The ‘finality’ of a block is probabilistic, contingent upon it being the chain with the majority/plurality of mining power behind it. But if someone gets 51% of the hashpower, they will be able to solve PoW puzzles at a faster rate than any other network participant and so their version of the blockchain will grow faster than all other versions of the chain combined. Therefore, the attacker can theoretically start mining from the genesis block (i.e. the first block) and mine until their chain is longer than others, thereby wiping out the history of the blockchain and undoing every transaction that ever happened.
This is a bleak situation for the blockchain. Unfortunately, in the future, every block will be from the attacker (this may be undetectable because of Sybil accounts). They can arbitrarily censor transactions, and essentially, in the long run, the blockchain is controlled by the 51% attacker. Even though the attacker will only find 51% of future blocks, they know their chain will grow faster than any other miner’s, and so the attacker will ignore other transactions that are mined before theirs.
This distributed systems attack has a strong economic argument that defends against it. In the Bitcoin whitepaper, Satoshi says that the economics of the system will again prevent a 51% attacker from acting maliciously; if someone has a majority of mining power, they will obviously gain all future mining rewards and transaction fees in the system. That is, they have great future earning power in Bitcoin. The detection of an attack would ostensibly tank the value of the Bitcoin cryptocurrency, and so, would diminish the future earning power of the attacker. So an attacker will refrain from an attack.
In the next post, we will talk about some of the cryptoeconomic shortcomings and attacks in Bitcoin and how other projects aim to fix them.
Acknowledgements: A special thanks to Alexis Gauba and Aparna Krishnan who heavily contributed to the ideas in this post.
-zk
Twitter: @snarkyzk
