Bitcoin and game theory: we’re still scratching the surface

In an earlier post I argued why Bitcoin’s stability is fundamentally a game-theoretic proposition, and ended with some questions:

Can we effectively model the system with all its interacting components in the language of strategies and payoff-maximization? Is the resulting model tractable — can we analyze it mathematically or using simulations? And most importantly, do its predictions match what we observe in practice?

Let’s look at those questions in the context of a “block withholding attack” between mining pools.

Recall that mining pools are groups of individual miners who pool their computing power as well as their rewards. Suppose two mining pools — let’s call them blue and red — are both seeking to maximize their mining rewards.  Let’s say the manager of the red pool decides to infiltrate the blue pool and decrease their efficiency using some of the mining power that red (directly or indirectly) controls. This can be done by submitting shares (partial proofs of work) to earn a share of rewards, but withholding any valid blocks which are found and therefore not contributing any productive work to the blue pool. At first sight this seems like cutting off your nose to spite your face — sure, blue’s efficiency will be hurt, but red is wasting hash power as well.

To get a handle on this situation, let’s write down three rules that govern rewards in pooled mining:

1. A pool’s revenues in any period are proportional to the number of Bitcoin blocks that its members mine, measured as a fraction of the total blocks mined in that period.
2. A miner’s rewards are proportional to the number of “shares” submitted, as a fraction of the total shares submitted by all members of that pool.
3. Miners can easily create numerous pseudo-identities (“sybils”), each contributing a very small amount of mining power. Therefore pools can’t easily detect if a miner is withholding valid blocks (and can’t punish a miner for doing so).

These rules are somewhat of an approximation, but they are widely accepted as a starting point due to their analytical clarity. Within this framework, we’d like to determine if a block withholding attack can be profitable. This is obviously an important question, and it’s also well-defined mathematically. We’ve taken all elements of human behavior out of the equation, so we can do some arithmetic to check the answer.

Let’s say that initially, blue and red both manage 50% of mining power. For this example, let’s ignore 51% attacks.

Now red devotes half its power (25% of the total) to infiltrating blue’s pool, and sends only shares and not blocks to the pool. This means that of all the blocks reaching the Bitcoin network, 2/3 are coming from blue and 1/3 from red. Mining rewards will therefore be distributed between the two pools in the same ratio, 2/3 and 1/3.

But of blue’s rewards, blue will pay a third out to red and only keep two-thirds for itself. That’s because red contributes 1/3 of blue’s shares and pools pay out on the basis of shares, not blocks. Recall that blue can’t tell which miners the misbehavior is coming from. In other words, blue keeps four-ninths of global mining rewards, and pays two-ninths out to red. Combined with the one-third that red earns directly, red’s share is five-ninths.

This means that block withholding attacks can in theory be profitable, which is an extremely interesting fact on its own.

What is mind-boggling, though, is that while people had asked the question for a long time of whether block withholding could be profitable, somehow no one had done the arithmetic presented in the last few paragraphs to discover the answer. The profitability of this attack was first pointed out in a paper by Courtois and Bahack last year that didn’t get much attention. Recently Ittay Eyal analyzed it rigorously, doing some neat game theoretic analysis of a situation with multiple attacking pools, and also brought it to wider attention.

This is not the only example of an obvious-in-retrospect break of widely held assumptions about the stability of Bitcoin mining. There’s at least Eyal and Sirer’s selfish mining and Andrew Miller’s feather fork. In each case, miners can potentially gain by deviating from the default protocol. Even though the models of mining used in these analyses are very simple, it took years to spot these bugs. And we can be sure we haven’t found the last of them.

I’m using the word bugs for a reason. If you think about the tremendous progress that’s been made in software testing and model checking for finding software bugs and writing correct programs, it’s hard to believe we haven’t found a way to represent Bitcoin’s strategy space in a formal language and automatically probe for deviant strategies. Is it simply a matter of the game theory and Bitcoin research communities having no overlap? Or are the tools developed in game theory for automated analysis of equilibria not capable of handling the domain of Bitcoin mining for some reason? [1]

Bitcoin offers an excellent testbed to explore and improve our knowledge of game theory. Due to the large financial incentives at stake, theoretical knowledge about strategies is considered very valuable. And yet, unlike, say, the stock market, the system is “closed” and relatively amenable to modeling and analysis. [2] We’re only slowly starting to exploit this opportunity, and further work in this area can enrich both Bitcoin and game theory.

Finally, there’s been little or no evidence of miners employing deviant strategies in practice so far. While this doesn’t in any way diminish the importance of the type of analysis we’ve talked about, it’s important to ask what’s causing the gap between models and observed behavior. I’ll take up this question in the next post.

[1] There’s been some work in the Bitcoin community on building mining simulators. This is a different approach, but also an interesting direction.

[2] For the system to be closed we have to ignore factors like the impact of mining strategies on the Bitcoin exchange rate. This will be the focus of the next post.