Selfish Mining in Bitcoin
Last updated
Last updated
Recall that in block chain paradigm we have two expectations of honest miners: mine over the selected tip, and immediately rebroadcast any valid block they learn of. We naturally asked ourselves what justifies these assumptions, and partially solved it by appealing to rationality (in the game theoretic, non-judgmental meaning of the word). We defined a rational miner as one seeking to maximize their mining revenue (and do not care about other incentives such as bribes or vindictiveness), and noted that such a miner is incentivized by Bitcoin's block rewards to always mine over the selected tip. The current section deals with the second expectation, that of not withholding blocks. It turns out that there are subtle and fascinating gaps between the honest and rational strategy.
Those gaps are described as a strategy called selfish mining, that allows large enough miners to increase their profit by withholding blocks. Selfish mining was first reported by Ittay Eyal and Emin Gün Sirer in their 2013 paper Majority is not Enough: Bitcoin Mining is Vulnerable.
Applying selfish mining is traditionally called an attack, as it very much resembles one: participants deviating from the protocol to obtain unwanted results. However, from a more modern mechanism design point of view, I find "attack" to be a bit of a misnomer, as it depicts participants maximizing the profit according to the incentives set for them by the protocol designer as nefarious. The term "selfish mining attack" is very commo in the literature, which is fine, but for didactive reasons I will just refer to it as a rational strategy.
Consider a scenario where there are only two miners: Alice the honest, and Sally the selfish. Alice acts as expected while wants to maximize her profit. This simplification does not really harm generality (beyond the assumption of a single selfish miner), since one large honest miner behaves exactly the same as many small honest miner (or any other division of hashing power among honest miner).
It turns out that by withholding blocks, Sally can increase the probability that blocks made by Alice are orphaned. Some of Sally's blocks will also be orphaned in the process, but it turns out that if Sally is large and well connected enough, she can increase the relative amount of Alice's blocks that get orphaned. In other words, Sally can increase her own share of non-orphaned blocks.
Now, why is that a problem? If that's the rational strategy, why not just let all miners follow it? For many reasons, let us list two:
It would create a disproportionate advantage for larger miners, making the fraction of a small miner even smaller.
It increases the orphan rates, degrading the security of the network.
Fortunately for Bitcoin, it seems that selfish mining is only feasible for very large miners, and selfish mining attacks (that are detectable by e.g. following orphan rate from the point of view of a non-selfish sufficiently large miner) have not been witnessed in the wild.
They key to a selfish mining attack is withholding blocks. I assume the reader is familiar with double-spending attacks (if not, fret not. We will cover them very soon). If you think about it, a double-spend boils down to orphaning a particular block. The attacker attempts to accomplish this by mining and withholding a competing chain starting below that blocks, in the hopes that it will eventually be heavier than the honest chain. At this point she could reveal the withheld chain and orphan the targeted block. (Technically, she, as well as Sally the selfish, are allowed to reveal some of their blocks while the attack is still happening, but we will ignore this).
You can think of selfish mining as a refined version of this idea, exploiting the fact that Sally doesn't care about which of Alice's blocks are orphaned, just that sufficiently many of them are. This allows Sally to constantly restart a "shallow double-spend attack", targeting a different block each time. Lets see how this go.
Sally begins by normally mining over the current selected tip. As long as she did not mine a block. She will always update the tip as Alice produces more blocks (remember, Sally is rational, and we already know that rational miners mine above the latest tip). At some point, she will hit a block:
Alice, in Sally's place, would have honestly reported the block right away. But Sally thinks it is more rational to wait a little and see where the wind blows. Say that the wind blew Alice's way, and she created the next block:
Sally is now at an impasse. She could either release her block, hoping that it would orphan Alice's block, or keep mining over it, hoping to make the next block, knowing that if she fails to beat Alice, there is a good chance that her blocks would be orphaned and Alice wouldn't.
Say that Sally, in a gambling mood, decides to keep mining, and does create the next block:
She can now keep mining her (now, heaviest) chain in secret, or she could publish both blocks, orphaning Alice's single block. The second option will lead us to this situation:
The point is this: if Sally immediately published the first block, the honest network would have considered it the selected tip and switched to mining above it. Sally took the risk of orphaning her block, but the risk paid off, as she orphaned Alice's block instead, increasing her own fraction of non-orphaned blocks.
But what if Sally hasn't published her chain and kept pushing? If Alice creates the next block, we are here:
What if the honest network mined a block first, bringing us to this situation:
Sally again has a choice of publishing her blocks and hoping for the best, or pushing forward trying to beat Alice.
Whatever choices Sally makes, if she is smaller than Alice, she will eventually publish her blocks, either because she garnered an advantage too large to risk, or because she is at a disadvantage too large to recover from. She then restarts the entire thing from the current selected tip, ad infinitum.
So the gaping question is: what choices should have Sally made along the way to maximize her profit? Is it possible that this strategy is more profitable than honest mining?
In their paper, Eyal and Sirer analyzed a particular strategy. This strategy is not optimal, but it is profitable enough to be very interesting. It goes like this:
Otherwise, you are already leading by two blocks, good job! Keep going!
Assuming that you have less than half of the total hashing power, at some point the honest network will start to catch up, and your advantage will have shrunk to one block!
This is too close for comfort! Publish your chain. All the honest block created since we started will be orphaned, congratulations! Now restart everything from the top.
Computing the profitability of this strategy is a fun exercise, but one a bit too involved for our intents. The result of the computation is depicted in this graph:
These results are obviously striking, but there is a common misconception that they imply something much more sinister: that a majority of one third can double-spend. The argument goes like "a majority of one third creates more than half of the blocks, so they can create a competing chain and revert any transaction". This mistake follows from not understanding the strategy. By watching closely one notes that Sally's block must piggyback on Alice's, if she ever hopes to reorg some of them. This interleaves Alice's and Sally's block along the chain.
A successful double spend attack looks something like this:
whereas successful selfish mining might look like this:
In our vantage, the motivation for presenting selfish mining was twofold: to better understand rationality and the mechanism design of Bitcoin, and to give a concrete example to our discussion about security notions, where we stressed that a security notion is only defined with respect to some goal. When discussing the security of Bitcoin, many become tunnel visioned on security against double-spends. We already stressed that this property is not quite enough. The inability to double spend is a security property called safety. If we combine it with another security property called liveness, that guarantees an attacker cannot arbitrarily delay consensus, we get a security property that is, not confusingly at all, called security.
Do not read my last statement in a sardonic tone. It is very common and very useful to have, for the variety of cryptographic schemes, a default security notion that is implicitly assumed to underwrite the statement that the primitive is secure. When someone talks about "the security of digital signatures", I automatically assume that they actually means a particular property that is actually called "universal unforgeability under a posteriory chosen message attack", unless the context dictates otherwise. Having these conventions follows naturally from having to navigate the jungle of security definitions, and is not a bad habit. It's downside, though, is that it can be confusing to non-professionals, and impart inaccurate impressions such that "a blockchain (or any other primitive) that is secure according to the standard formal definition is also secure in any other sense that can be relevant to us". The antidote to falling for these too broad generalizations is to always make sure you understand what is hanging on the word "security".
However, I made a hopefully fruitful effort to convince you that there is no such thing as "the security", as there could always be other malicious goals that furnish other security properties.
Selfish mining is just that. A selfish miner is not prohibited by the standard Bitcoin security definition. If we want to discuss the security implications of such a miner, we need a suitable definition.
We can recast Eyal and Sirer's work in the terminology later introduced by Garay et al.: Eyal and Sirer proved that Bitcoin is an example of a protocol that (assuming a honest majority) satisfies the common prefix property, but fails to satisfy the chain quality property.
Garay et al. showed that Bitcoin does not have perfect chain quality, but they also derived bounds on the profitability of a selfish miner. They showied that Bitcoin does admit chain quality to an extent that is arguably sufficient (in particular, it is implied by they work that the Eyal-Sirer strategy is pretty close to optimal)
This is a striking example of how attackers (or worse, cryptographers!) can surprise you.
Consider again this situation:
The impact of a deterministic selfish mining attack was analyzed by Ren Zhang and Bart Preneel in their 2019 paper Lay Down the Common Metrics: Evaluating Proof-of-Work Consensus Protocols' Security, concluding that a deterministic tie-breaking law must degrade chain quality.
In PoEM this seems to even be slightly exacerbated: if the competing block has considerably less weight than Sally's, she knows that her advantage will carry over for the remainder of the attack. Say that Sally's block is significantly heavier than the competing honest block:
Then she knows that even if the honest network creates the next block, there's some chains that both blocks together will be lighter than her block:
Since Eyal and Sirer's initial observation, selfish mining has become a central theme in PoW research. Bitcoin is thankfully quite resilient to selfish mining, but this observation means that other protocols should be on their toes, providing at least some evidence that they are not susceptible to cheap selfish mining attacks. Unfortunately, some chains tend to ignore this issue, despite concerning evidence. One such example is the Kadena network, whose developers have yet to respond to an analysis by Wang et al. in their 2022 paper An Analytical Study of Selfish Mining Attacks on Chainweb Blockchain, that provides evidence that selfish mining becomes easier as more chains are added.
In 2017, Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar published the paper Optimal Selfish Mining Strategies in Bitcoin, where they noted that Eyal and Sirer’s attack is not optimal and provided an optimal strategy. Their improvement is particularly interesting as it relies on optimization techniques: the authors noted that for any set of parameters α,γα,γ the optimal strategy is slightly different, and provided an efficient algorithm that computes the optimal policy from these parameters. They noted that the original selfish mining strategy coincides with theirs for γ=1γ=1 and small values of αα.
In the 2018 paper On Profitability of Selfish Mining, Cyril Grunspan and Ricardo Pérez-Marco provide a subtler analysis of selfish mining. They note that the assumption that γγ is constant is unrealistic (as γγ depends on how long it took to create each block), and show that when incorporating the time variance of γγ into the computation, the honest mining strategy becomes optimal. They conclude that selfish mining attacks are actually attacks on the difficulty adjustment algorithm. In particular, they conclude that a successful selfish mining attack on Bitcoin must persist over several difficulty windows, making it impractical.
However, in the 2020 paper Selfish Mining Re-Examined, Kevin Negy, Peter Rizun, and Emin Gün Sirer pointed out a mistake in the computation by Grunspan and Pérez-Marco. Fixing it, they found that selfish mining can be profitable in the constant difficulty setting. They carefully analyze selfish mining in scenarios of varying difficulty and find it is even more confusing. A surprising property is that the attack is affected by how the difficulty adjustment works, and different approaches to adjusting difficulty furnish different efficacies for selfish mining attacks.
A year before that, Guy Goren and Alexander Spiegelman published the paper Mind the Mining, where they revisit mining in face of variable difficulty. The attacks in this paper “complement” selfish mining, as they are based on the miner deliberately shutting off some of their hardware. This kind of attack has very different flavor than selfish mining, which assumes attackers have a fixed hash rate. In other words, the analysis of selfish mining implicitly ignores the expenses of the miner, and treat income as pure profit. Taking expenses into account, Goren and Spiegelman find that Bitcoin’s long difficulty epochs enable “win-win” situations: a miner can increase the profits of all miners by reducing their mining efforts (where the reducing miner is “rewarded” in lower energy bills, while the rest are rewarded in higher mining income due to increased difficulty). The loser of this “win-win” is obviously the network itself, whose hash rate, and whereby security, is reduced.
(My deepest gratitude to Ittay Elay for reviewing a much earlier version of this section and making invaluable comments and suggestions)
Mine over the selected tip:
If the honest network found a block before you, restart the attack from the new tip:
Otherwise, you have a lead of one block over the honest network, good job! Keep this block to yourself and keep mining!
If the honest network mined the next block, you are at an impasse: Release your block to the wild, and hope for the best. For future reference, let be the probability you win in this situation (in a sense, encodes how well connected you are)
Here we see an interesting phenomenon: Sally does not need a majority of the hash rate to create a majority of the blocks! For (poorly Connected sally) we see that sally needs to have one third of the hash power (that is, she needs to be at least half as large as Alice) for some increase to her profit. For (extremely well connected Sally), this strategy will benefit Sally regardless of her fraction, and if she has one third of the fraction, she can create a majority of the blocks.
Note that in the second image , Sally created out of non-orphaned blocks, which is a majority. However, Alice created a total of blocks in this time, which are more than the Sally's blocks. If the Sally had arranged her block in a chain, she would not have been able to orphan any of Alice's blocks, and her chain would have been shorter.
In their 2014 paper The Bitcoin Backbone Protocol: Analysis and Applications, Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos proposed a model that called "the backbone protocol" that more accurately captures the Bitcoin protocol and provides a unified framework that can express many more of the subtleties of a blockchain. The proceeded to define two properties, the common-prefix property, that is equivalent to what we just called "security", and the chain quality property, that measures the fraction of blocks a miner with a fraction of of the hash rate.
The statement above is a bit harsh, and that follows from my choice to present a security property as binary. Any protocol is either secure or insecure. In practice, security notions are often parameterized, where the parameter indicates how secure the protocol is. We've actually already seen an example: recall that when we talked about fault tolerance we said that BFT can only provide fault tolerance, while Bitcoin can provide fault tolerance. We implicitly used the term "fault tolerance" as a parametrized security property.
Recall the discussion about tie breaking in the block chain paradigm. We said in passing that selfish mining and tie breaking is related, and we can see why if we consider the strategy above. In particular the number .
We said that the number measures how well connected you are. But that's because we were following the Bitcoin "seen first" tie breaking rule. What would have happened if we chose a deterministic tie breaking rule like lowest hash or PoEM?
To discuss the subtleties of tie breaking, we have to jettison the simplification that the entire honest network is a single entity called Alice, and think of them as many independent miners. Recall that is the probability that if Sally releases her block, she would orphan the honest block. For the "first seen" tie breaking rule, is directly connected to how well connected Sally is. It quantifies her ability to make sure that most miners see her block first, despite the honest block already being in circulation.
But if the tie breaking rule is deterministic, she knows that if her block is losing, then and if her block is winning, then is very close to . (It is not exactly because there are some scenarios where she still loses, e.g. if by the time she releases her block, the honest network mines another block, or if suddenly a third parallel block joins the party that wins the tie break rule over both other blocks). This can affect her decision in a way that can increase the profitability of a selfish mining attack.
The question is, how probable these scenarios are, and what is the expected profit increase when they occur. I haven't done the math, buy my educated guess is that it will reveal that PoEM allows a selfish miner to create a majority of the blocks regardless of how well connected they are.
