Bitcoin is a game within a game

In this series on Bitcoin and game theory, I’ve argued that Bitcoin’s stability is fundamentally a game-theoretic proposition and shown how we’ve had blind spots for years in our theoretical understanding of mining strategy. In this post, I’ll get to the question of the discrepancy between theory and practice. As I pointed out, even though there are many theoretical weaknesses in Bitcoin’s consensus mechanism, none of these ever appear to have been exploited.

A blunt way to explain the discrepancy is to entirely reject the ability of game-theoretic models to predict practice. For example, some people argue that since miners don’t know any game theory, game-theoretic analysis of their behavior is not meaningful. This objection is easily dismissed — animals know even less game theory than miners, and yet their behavior is one of the classic applications of game theory. And most pairs of prisoners facing a dilemma have never heard the term prisoner’s dilemma. Knowledge of game theory by agents is not a prerequisite for the applicability of game theory.

A related objection is that deviating from the default strategy is hard, from the miners’ point of view. After all, it’s not as if  Bitcoin Core comes with deviant strategies built in that can be enabled with the flip of a command-line switch. What’s a miner to do? While superficially plausible, I think this objection gets the cause and effect exactly backwards. In reality, no one’s bothered to implement non-default strategies because they didn’t think there were profits to be made from it. Otherwise there would likely be a flourishing ecosystem of patches — or replacements — to bitcoind that would execute these deviant strategies, just as we see with mods to video games.

A more sophisticated objection, and perhaps the most frequent one, is that it’s not in miners’ interest to employ non-default strategies, because it will cause people to lose confidence in Bitcoin’s stability, tanking the price of bitcoins. A drop in the exchange rate is bad for miners it will devalue their investment in mining hardware.

This is a valid argument, but things get tricky. We do know that miners launch denial-of-service attacks against their competitors; does a similar worry about Bitcoin’s stability and the exchange rate not apply? Besides, it seems that even though it’s phrased as an objection to game-theoretic reasoning, the argument actually co-opts game theory: essentially, it says that non-default strategies are a losing move because they will be met by a certain response from other players, namely investors selling off their bitcoins.

Similarly, consider the argument that attacks on consensus won’t work because developers will notice and push out an update that defeats it. This is also a game-theoretic argument; the set of participants has now expanded to include developers, and perhaps people running Bitcoin nodes, in addition to miners and investors (an investor being anyone who’s holding bitcoins).

So we have one kind of game-theoretic argument — that miners could earn more bitcoins by changing their mining strategy — being met with another kind of game-theoretic argument, one that expands the strategy space to reach a different conclusion.

Notice that we’re talking about two very different kinds of strategy here. Mining strategy is executed by software, happens at the time-scale of minutes, and can be analyzed as a “closed” system where the strategy space can be formally described and analyzed mathematically. On the other hand, movements in price and pushing out updates to software involve human decisions, are typically much slower, and are hopeless to try to precisely model mathematically.

In other words, we seem to have a nested game, a game within a game. The inner game is played by automated agents according to the way they’re programmed. On the other hand, moves in the outer game consist of human operators changing the agents in response to what’s happening on the block chain as well as making moves that are not available to the automated agents. Many moves in the inner game happen between consecutive moves in the outer game, which is one reason that we’re forced to treat the two levels separately.

If we start looking for this nested-game structure, we find it everywhere. Malware and malware-detection mechanisms are in a constant cat-and-mouse game. In this game, malware must make instantaneous decisions such as where to spread next and whether to attack or wait. But both malware and anti-malware tools are under the control of their respective operators who evolve them over time in response to each others’ moves. Similarly, packets are routed instantaneously but routing policy evolves over time based on traffic patterns.

My central claim is that for game-theoretic models of Bitcoin mining strategy to better model practice, we must recognize the existence of this two-level structure. The surprising results I talked about in the previous post can all potentially be explained by analyzing the nested game and concluding that it isn’t profitable for miners to deviate after all. Nested games seem to be a popular method for analyzing the behavior of politicians who’re under the influence of voters. It hasn’t been used so far for analyzing Bitcoin.

This research direction is likely to yield dividends beyond cryptocurrencies. Computer scientists are mechanism designers, from ad auctions to routing protocols. Any of these situations can be seen as a nested game since the creators of the software that plays these games regularly modify it in response to strategies employed by others. The question of which elements of strategy should be programmed into the machines and which ones left to human judgment is relevant to every such scenario.

In the next post, I’ll present a simple illustrative example of how a nested-game analysis of mining strategy can result in an interesting and non-obvious prediction. Specifically, I’ll look at what happens if a fork-and-double-spend inner game strategy is met by an outer game strategy of the developers deciding to kill the forking chain even though it’s longer.

Thanks to Joe Bonneau who suggested the nested game formulation.