Mining pools are an essential part of the Bitcoin ecosystem. They enable many small miners to operate at reasonable business risk. However, they also pose a risk to the currency, as successful open pools have been able to grow dangerously big in the past.
Until now, there have been few forces to counteract this phenomenon. Gavin Andresen, chief scientist of the Bitcoin Foundation, has repeatedly urged miners to use smaller pools, and researchers, including ourselves, have suggested technical fixes to reduce pool size (here, and here). But alas, community pressure has only had limited success, and technical solutions are still under development and far from production.
Today, I will explain why all this may not be necessary. In an analysis I placed in arXiv, I show that open pools face what I call the miner's dilemma -- a version of the prisoner's dilemma where miners can choose to attack or leave each other alone. I found that any open pool can increase its own profits by attacking another open pool. However, if both attack each other, both earn less than if none attacks.
It is well-known that a pool can attack another open pool by pretending to work on its behalf, and thereby taking a cut off of its proceeds, but never contributing by discovering blocks. Until recently, it was believed that this attack could not increase the attacker's profits. See below for details on previous work.
Since block withholding attacks are not prevalent (this is one exception), at least as far as we know, we can surmise that pools make the right choice and agree to refrain from attacking each other. However, my analysis shows that this is an unstable balance. It is worthwhile for a pool to refrain from attacking only as a part of an overall truce agreement in which it is not attacked. If a single pool starts attacking its peers, it will force them to retaliate.
Once this happens, the profitability of public pools will deteriorate, leading miners to choose other pooling options, for example closed pools of miners that trust one another. Such trust circles are naturally going to be much smaller than open public pools. The dismantling of overly large pools will bring Bitcoin to a safer footing than what we have today, where a handful of large pools dominate mining.
Now it's time to get technical. I will outline the attack and the tools used for its analysis, and then go over the main results. The gory details are in arXiv. But first, some background. Skip ahead to Pool Block Withholding if you are familiar with the mechanics of mining, pools and the classical block withholding attack.
Bitcoin's security stems from the vast compute resources of many participants called miners. These participants contribute their compute power, called mining power, and the system rewards them with Bitcoin. We assume that the miners follow the honest mining protocol, and therefore the payoff of a miner is proportional to its ratio of mining power out of all mining power in the system. Reward distribution occurs as blocks are discovered with proofs of work, and each miner produces proof of work with probability proportional to its mining power.
Bitcoin gives out a block reward, 25 BTC as of today, every 10 minutes on average. This means that a miner whose power is a small fraction of the total mining power is unlikely to win in a very long time. Since this can take years, miners congregate in pools. A pool has a manager, and whenever a participant in the pool finds proof of work, the reward goes to the manager, which distributes it among the participants according to their contribution to the pool.
In order to estimate the effort exerted by its participants, the pool manager receives from its miners not only the full proofs of work that go to the Bitcoin system, but also partial proofs of work. Partial proofs are similar to full proofs, but are much easier to produce, so small miners produce them at a sufficient frequency to allow a good estimate of their power. These partial proofs of work enable the pool manager to make sure that a miner indeed put effort into working on behalf of the pool, as a miner would naturally discover them during the effort to find a full proof of work, and they demonstrate just how much effort that miner put into discovering a solution.
Many of the pools are open pools. They have a public web interface where miners log in to register. After registering, miners point their mining hardware to a designated server and receive mining tasks. They send back to the server partial proofs of work as well as full proofs of work, and the pool manager credits their account based on their contribution and the pool's revenue.
Currently, mining pools are much larger than they should be. A pool smaller than 5% can provide sufficient stability for a miner. But large pools sometimes get close to 50%, which can have serious consequences. Moreover, even pools smaller than 50% can break the system. As we will see below, it now turns out that this problem may resolve itself.
The classical block withholding attack is as old as pools themselves. It is an attack performed by pool participants to sabotage the revenue of the pool and its other participants. An attacking miner sends to the pool only partial proofs of work, but discards full proofs if it finds them. The pool therefore shares its revenue with the attacker, but does not benefit from its mining power. This reduces the revenue of all participants in the attacked pool, but also the revenue of the attacker itself, which could earn more by just mining fairly.
We note that a proof of work can only be used by the creator of the task. The attacker cannot repurpose it to collect any revenue.
Can block withholding be used to increase the revenue of a miner? The question was recently raised by Gavin Andresen, chief scientist of the Bitcoin Foundation. And although an exact attack strategy was not published before, it was recently shown that the answer is positive in certain circumstances.
We will now see what happens when pools issue block withholding attacks against one another.
A pool has many loyal miners that work on what the pool manager tells them to. A standard pool uses all its loyal miners for mining on its own behalf. An attacker, however, does the following: The manager uses some of its miners for its own mining, as usual. Concurrently, he infiltrates a victim pool by registering as a regular miner. He then receives mining tasks from the victim, and sends them to some its loyal miners. The mining power the attacker redirects towards the victim's tasks is called the infiltration rate and the miners are infiltrating miners. When the attacker receives partial proofs of work from its infiltrating miners, it sends them to the victim, which estimates their true mining power. However, when it receives full proofs of work from the infiltrating miners, it withholds and discards them, and thereby does not contribute to the victim's revenue (note that the miner could have used the infiltration rate for its own mining, so it incurs a cost of opportunity by diverting these miners). The victim pool is tricked into thinking that the infiltrating work force is doing effective mining and shares its revenue with the attacking pool. The attacker distributes its revenue from its own mining and from its infiltration among all its loyal miners.
The revenue of the pools is influenced by several factors. A victim pool's effective mining rate is unchanged by an attack, but its total revenue is divided among more miners. An attacker's mining power is reduced, since some of its miners are used for block withholding, but it earns additional revenue through its infiltration of the other pool. And finally, the total effective mining power in the system is reduced, causing the Bitcoin protocol to reduce the difficulty.
Taking all these factors into account, we observe that, counter to one's intuition, a pool might be able to increase its revenue by diverting its mining power to attack other pools. Each pool therefore makes a choice of whether to attack each of the other pools in the system, and with what infiltration rate. This gives rise to the pool game.
My analysis of the pool game shows that a pool can always increase its revenue by attacking an honest pool. Whatever the pool sizes may be. This is somewhat surprising: the attacker increases its profit by discarding proofs of work. As always in life and research, the devil is in the details, but here are two factors that are in the attacker's favor. First, he doesn't lose much by discarding proofs of work, since he still submits partial proofs of work to the infiltrated pool, and the victim pays back pretty well. Second, by reducing the overall effective mining power, the revenue of his own mining increases.
But what if the other pool retaliates? This is when things get even more interesting. If two pools attack each other (while the others are mining as usual), the pools should adjust their infiltration rates to their optimum. At this equilibrium point, neither pool can improve its revenue by using more or less miners to infiltrate the other. So the pools have a choice -- whether to attack by optimizing their revenue, or mine without attacking. This is a version of the prisoner's dilemma.
In the classical prisoner's dilemma two partners in crime have to decide whether to testify. If neither testifies, they both go to prison for a year. If one testifies, he is released and his partner is imprisoned for 5 years. If both testify, they are both imprisoned for 2 years. So testifying is a dominant strategy; a prisoner will be better off testifying whatever his partner does. However, if they follow the dominant strategy they end up in a tragedy of the commons where both are worse off than if neither testifies.
The situation in the pool's case is similar. If neither attacks, they both work fairly and their miners earn what they deserve. If one attacks, it improves its revenue, and the revenue of the other deteriorates. If both attack, at equilibrium, each earns less than if neither had attacked, but more than if only the other had attacked. Attacking is therefore a dominant strategy. A pool will improve its revenue by attacking, whether the other pool attacks or not.
To hide the pool block withholding attack, an attacker can register with the victim pool as multiple miners, each with small mining power. Although the victim will realize he is under attack from his reduced revenue, it is difficult for him to realize which of his miners are attacking it. They all send partial proofs of work, but each seldom finds a full proof of work, therefore it takes a long time to have a statistically significant proof that blocks are withheld. This makes defense against block withholding difficult. The attack can also be performed anonymously, since pool registration typically requires only a Bitcoin address for revenue collection and / or an email address. The victim has no idea who his miners are.
The analysis I outlined here shows that it is better for all pools to refrain from attacking. However, for short term profits, a pool might decide to attack its peers and break the balance. If the profits of open pools are reduced, miners will look for alternatives such as smaller, closed pools. They can get steady income from pools well below 10%, and they have only little incentive to use very large pools; it's mostly convenience and a feeling of trust in large entities.
The dismantling of overly large pools is one of the most important and difficult tasks facing the Bitcoin community. My analysis shows that short-term incentives can cause this dismantling to occur spontaneously, making the Bitcoin infrastructure more distributed, and so more robust and secure.