Economics, Games and Proof of Work
An introduction
The Economics
Economist have long studied different market conditions and have figured out why certain markets are highly competitive with many players (i.e., restaurants in a major city) as opposed to less competitive markets with fewer players (i.e., graphic chips) or like Microsoft in the 90’s, one main player.
Market structure, on a spectrum between highly competitive (i.e., monopolistic competition) and less competitive markets with fewer players (i.e., varieties of oligopoly) serves as a precursor to understanding game theoretic attacks in Proof of Work consensus mechanism.
Why? When conceptualizing Proof of Work as a consensus mechanism, we might imagine miners scattered throughout the world and a distributed network of nodes. As this provides the very features we want in PoW: censorship and reversion resistance.
And yet, this picture, although widely shared, is a misleading picture of miners and mining behavior.
Miner profitability, like anything in life, is driven by both marginal cost structures and earnings — potential block rewards (see here as Dr. Nicola Dimitri illustrates bitcoin mining activity driven by marginal costs and here, as Max Fang discusses solo mining vs. pool mining earnings). Both of these forces create pressures for miners to join mining pools, which trends towards aggregation and centralization of resources.
Fundamentally, mining is a competition, miners spend tremendous resources to compete and ‘winning’ is probabilistic. These features lend themselves to game theory analysis where miners must act strategically to maximize returns on their investments. At first glance, the game appears to be zero-sum (i.e., non-cooperative game) with competition happening between individual miners, but the economics above suggests that the game may be closer to a cooperative game, where coalitions of miners form, but still compete with each other.
What is needed to profitably mine are:
- large capital investments (i.e., mining equipment ain’t cheap)
- economies of scale (i.e., joining a pool allows one to be more productive per unit of computational input; mining solo lacks the kind of scale needed for profitability)
- ability to eliminate rivals (i.e., rival miners who are not part of mining pools, over time, may shift to other activities as they cannot lower their marginal costs)
- barriers to entry (i.e., capital costs, technical know-how, computational power, electricity) these things make life for smaller entrants harder
Incidentally, all these factors drive oligopolistic behaviors in any markets.
Ideally, miners are geographically distributed with equal hashrate distribution, but in reality the picture is closer to this donut chart:
Overtime, large mining pools accrue significant advantage over smaller, solo miners.
The Game
To recap, the broad distinctions between different games that can be used to analyze mining behavior in PoW are non-cooperative games and cooperative games.
Most game theoretic analyses tend to start with non-cooperative games, because they are more general.
Game theory helps players make decisions as to which course of action would lead to the highest payoff. With certain assumptions in place, a game is typically modeled on a two-by-two matrix illustrating how two players would have different payoffs depending on how they move in relation to how the other player moves.
Take the prisoner’s dilemma.
Interrogated in separate rooms, the detectives are trying to get each of them to betray the other (i.e., is there honor among thieves?). If they both rat each other out, they both serve two years, the worst outcome for both of them. If they both stay silent, then they both serve one year, a less bad outcome. If one person betrays, while the other stays silent, the one betraying goes free.
While considering their options, the prisoners reason: ‘If I stay silent, at best I serve one year, at worst I serve three years; however, if I betray, I could serve two years (which wouldn’t be as bad as serving three), but I could also go free’. Betraying has a higher payoff than staying silent. Game theory suggests that the, rational, albeit selfish, strategy would be to betray. Since this is a dominant strategy for both, it is also a Nash Equilibrium; neither players benefit from changing their strategy.
In PoW similar mechanisms are at play. The combination of incentives (block rewards) and punishment (mining off the wrong chain means you’re block is invalid) means that consensus on the main chain is a Nash Equilibrium and, generally, it is a miner’s dominant strategy to remain on the longest chain.
However, when there are attacks, a miner’s dominant strategy may be to switch chains.
A Compendium of Attacks
Here’s a list of various attacks under the Game Theory framework discussed above.
P + Epsilon (bribing attack): Vitalik has written extensively about this attack. Under normal circumstances (no attack), the PoW consensus mechanism has a self-reinforcing Nash Equilibrium for miners to remain on the longest chain. If others are mining on chain A, then you mine on chain A; if others switch to chain B, you follow suit.
The assumption under Nash Equilibrium is that there is no ‘incentive’ for you or others to change their strategies and begin mining on a different chain. Although miners are competing for the right to mine the next block, the structure of incentives (i.e., block rewards) and potential for punishment (Rule 1: a block that is mined on top of an invalid block becomes an invalid block; Rule 2: if you don’t mine on the longest chain, you’re mining on an invalid block; see here) means that the dominant strategy is to mine on the main chain that everyone else is mining on.
Suppose the network is mining in chain A. If an attacker double spends on chain B, he’ll want to convince the network to switch over to chain B. He will proceed to change the incentives (payoff matrix) of other miners so the majority switch to chain B (i.e., bribe a small fee so miners can earn a little more by mining on chain B; 25.01). The potential for such a bribe changes the dominant strategy for miners such that they mine on chain B.
In short, an attack happens when miner’s payoff structure changes.
Here, when people notice the higher potential payoff for chain B, that chain suddenly becomes the ‘valid’ chain, then the attacker will have gotten the network to migrate to his chain (successfully double spending in the process), thus jeopardizing reversion resistance of the PoW consensus — compromising security for everyone.
Under non-cooperative game theory, the P + Epsilon attack is an illustration of what happens when incentive structures change and serves as a foundation for understanding what goes on with other attacks.
51% attack and Double spending: An attacker submits a payment transaction to the network (i.e., chain A), while privately mining on a secret chain (chain B) to engage in double spending. After a certain number of confirmations, the merchant will send over the goods for the money and the attacker, with sufficient hashrate (theoretically 51%), can get the network to mine on his chain.
Unlike in the P + Epsilon attack where an external attacker bribes miners to switch over to another chain, any attacker with over 51% of the hashrate, could simply get all miners within his network to mine on another chain.
In both cases there is switching over away from the main chain.
As described above, the economics of mining suggests that it will be more rational for miners to join larger mining pools, in which case, a scenario where one pool, or several pools acting in unison, managing to acquire >51% hashrate becomes more likely.
Once the perspective shifts from an individual miner to miners forming coalitions, the game theory lens shifts from non-cooperative (zero sum) to cooperative games. Cooperative games examine the behavior of coalitions.
Accompanying this shift is the importance of coordination. On one hand, miners will switch to chains with a higher payoff (i.e., if the new chain is the longest, valid, chain), but what gives that chain a higher payoff is the fact that everyone else is mining on it. Thus, the challenge is coordinating other miners to mine on a new chain.
This very challenge plays an important role in ensuring protocol security and is an important feature of Ethereum’s current governance protocol (EIPs). Vitalik described this as using coordination problems to the protocol designer’s advantage (see here).
Nevertheless, the coordination problem, which serves as both a challenge and a security enhancer, is alleviated in the presence of larger mining pools — it’s much easier to coordinate a few large mining pools than it is to coordinate many small miners.
Censorship Attacks (Punative Forking/Feather Forking): Punative forking assumes the attacker has >51% of the network. With the majority of the network, an attacker can censor certain transactions, threatening to fork if they see specific transactions. Alternatively, through feather forking, the attacker can indirectly censor specific transactions by making a targeted individual pay an unreasonably high fee (these two outcomes of an attacker acquiring >51% hashrate are described in detail here).
In both cases, censorship resistance is compromised. In theory, it may not matter how small the mining pools are, as long as they collude to achieve non-trivial (i.e., 25%, 33% or >51%) amount of hashrate, these attacks can be carried out.
Selfish Mining: As centralization pressures persists driving the mining market towards oligopoly, the ‘payoff’ for displaying malicious behavior increases. One example is selfish mining where by a miner (or mining pool) will fool the rest of the network into thinking that they are mining on the longest chain, only to broadcast a secret block later on to render the other network blocks invalid.
As long as a pool has >25% of the mining power, this strategy of selfish mining can work. The question becomes, what happens when all miners (mining pools) selfishly mines? In that case, we will no longer know what the ‘longest chain’ in PoW is and we’re now in doubt of the ‘state’ of the protocol; the network is no longer secured. From game theoretic perspective, the dominant strategy has again shifted the incentive payoff from mining on the main chain to a different chain (similar to the P + Epsilon attack).
Network Attacks: To recap, anything that causes miners to deviate from consensus (away from the main chain) could be classified as an attack. Attacks could come from bribery, controlling non-trivial portions of the network (25 — 51%) of the network, through threats or deception.
In addition, mining pools can also attack each other.
In PoW, as a precaution, nodes reject new blocks with timestamps that are more than 2 hours ahead of its internal clock. An attacker can launching a sybil attack against the targeted node by reporting its (fake) nodes’ clock behind by 70 minutes; meanwhile, for every other node, turn the clock time ahead by 70 minutes (140 minutes exceeds 2 hrs threshold). The targeted node will, unwittingly, reject new blocks and will find itself on a separate chain. The attacker then has an opportunity to get several confirmation’s worth of time to mine their double spend chain. This effectively splits the network (more details in this talk here by Philip Hayes).
A game theoretic analysis of such network attacks would need to account for the payoff between investing computational powers in regular mining activity or using it to conduct attacks against other mining pools. Interestingly, Johnson et al., (2014) found that larger mining pools not only tended to initiate attacks, but were also frequent targets of such attacks. The reason is, it is easier to attack, and eliminate, a few large pools than it is to go after many small pools.
Overtime, this not only partitions the network, but filters out the competition between mining pools, leading to further oligopolistic landscape.
Implications
We can be begin drawing some conclusions about PoW in the above analysis. The economics of PoW, in terms of costs and revenue, compel miners to form coalition (mining pools/cartels). The payoff for malicious mining behavior is greater the larger the mining pool. Thus, larger the mining pool are more likely to begin attacking other mining pools (and also itself face attacks as it gets bigger) and this may fuel further consolidation as the market trends towards oligopoly.
This undermines censorship and reversion resistance.
The very economic structure of PoW undermines its ability to deliver on qualities it is intended for.
This is why the research efforts at Ethereum moves towards proof of stake (PoS), which will be a topic for another post.
