Discouraging Pool Block Withholding Attacks in Bitcoins

The arisen of Bitcoin has led to much enthusiasm for blockchain research and block mining, and the extensive existence of mining pools helps its participants (i.e., miners) gain reward more frequently. Recently, the mining pools are proved to be vulnerable for several possible attacks, and pool block withholding attack is one of them: one strategic pool manager sends some of her miners to other pools and these miners pretend to work on the puzzles but actually do nothing. And these miners still get reward since the pool manager can not recognize these malicious miners. In this work, we revisit the game-theoretic model for pool block withholding attacks and propose a revised approach to reallocate the reward to the miners. Fortunately, in the new model, the pool managers have strong incentive to not launch such attacks. We show that for any number of mining pools, no-pool-attacks is always a Nash equilibrium. Moreover, with only two minority mining pools participating, no-pool-attacks is actually the unique Nash equilibrium.


Introduction
Bitcoin is a decentralized crypto currency originally proposed by Satoshi Nakamoto in 2008 [15]. Since then, it has attracted wide attention in the world both academically and commercially because of its soaring price and the characteristics of decentralization. Bitcoin realizes its decentralization by blockchain, which is a global ledger maintained by distributed system. This ledger can record historical transactions and other information.
One main difference between Bitcoin and most existing currencies is the way of currency issuance and the method of bookkeeping. Bitcoin is implemented on a P2P network and everyone is able to join or leave the network without any permission. The participants in generating new blocks are called miners, and their tasks are to verify the legitimacy of undetermined transactions and pack those legal transactions into a block. In order to validate the block, every miner needs to work on a cryptographic puzzle, which needs large amount of computational resources (like electricity and hardware). To motivate the miners to generate new blocks, the first miner who solves the puzzle correctly, will get rewarded. Roughly speaking, the probability that a miner can propose a block successfully is proportional to her computational power among all miners. The above protocol of identifying the block generator is called proof of work and the process of solving puzzles is called mining. More detailed of Bitcoin system description can be referred to the Bitcoin white paper [15] and wiki 1 .
To control the frequency of block generation, the difficulty of puzzles is adjusted dynamically in Bitcoin system, which is about every ten minutes in expectation. With the development of Bitcoin, the computational power in the system is extremely large nowadays. Thus, it is very difficult for a solo miner to propose a block successfully. This means the miner may spend several years to obtain (huge) rewards which is of course unacceptable. To pursuit stable reward, a lot of miners join in the mining pools which are gatherings of individual computational powers [16]. Miners in the same mining pool work together on the proof of work protocol, thus a pool can obtain reward much more frequently compared to mining individually. After obtaining reward, the mining pool will distribute the reward among miners in this pool based on the computational power of each miner. For a solo miner, attending a mining pool cannot increase the expected reward, but the variance is improved significantly. Nowadays, there are more than 12 Bitcoin mining pools and more than 90% of Bitcoin mining is done by those pools 2 .
However, it is shown in [7] that the permissionless mining pools have strong incentives to launch the pool block withholding attacks (PBW attacks) on each other: one strategic pool manager sends some of her miners to other pools and these miners pretend to work on the puzzles but actually do nothing. In Bitcoin or any decentralized system, the pool managers are not able to recognize such malicious miners, thus these miners can still obtain the reward from mining pool proportional to their computing powers. Eyal [7] proved that although infiltrating the other pools consumes some of her computational power, the reward from infiltrating miners may still increase the pool's total utility. PBW attack is also demonstrated in [13] with a different reward function.
Eyal [7] modeled the above scenario as pool block withholding games (PBW games) and showed that with any number of pools, no-pool-attacks is not a Nash equilibrium. When there are two pools, the situation faced by the two managers is similar to prisoner's dilemma, which is called miner's dilemma: in an equilibrium, both manages launch the PBW attack and accordingly earn less rewards compared to when they mine honestly.
Alkalay-Houlihan and Shah [1] further studied the miner's dilemma between two strategic mining pools and obtained the bound of the social loss due to noncooperation, i.e., price of anarchy. They showed that the pure Nash equilibrium always exists, and the pure price of anarchy is at most 3 in this game. They also conjectured the tight bound should be 2 and demonstrated this in some special cases.
It is disappointing that launching PBW attacks to be always profitable for the pools, and would dramatically decrease the social welfare. Such bad news is derived from the inaction of the malicious Bitcoin pools. Actually, in both [7] and [1], the authors assume that all the rewards are proportionally distributed to the miners. Accordingly, a natural question to ask would be Is there any other approach to reallocate the rewards such that PBW attacks can be avoided or discouraged.

Main Contributions
Briefly, we resolve the above question affirmatively by refining the PBW games and show that for any number of mining pools, no-pool-attacks is always a Nash equilibrium under a proper way to award the successful miner. Moreover, with only two minority pools participating, no-pool-attacks is the unique Nash equilibrium. We summarize our contributions as follows.
-We refine the PBW game by allowing all pool managers to deduct (different) percentages of their rewards before they distribute the reward to the miners, where the deducted reward is used to award the successful miner.
We call the refined model DPBW game. We believe such a new reward distribution rule in DPBW games is more realistic than the proportional way, as, intuitively, the former provides enough motivation for the miners to work hard on mining. Moreover, it should also be careful that the manager cannot deduct too much from the total reward since the more they deduct, the less incentives are left to the miners to join the pools. -We prove that for arbitrary number of pools, no-pool-attacks is always a Nash equilibrium of DPBW games with reasonable deductions. Thus the price of stability (PoS) of DPBW games is 1. This is intriguing for the situations in which there is some authority that can influence the managers a bit and help them converge to the optimal solution that is also stable. -Particularly, for two minority pools participating, the unique Nash equilibrium of DPBW games with reasonable deductions is no-pool-attacks. This result is more exciting for the special case: even without such authorities, every manager is automatically willing to not launch PBW attacks.
Thus in the present work, we improve the negative results proved in [7] and [1] by designing a new way to allocate the reward to the miners and award the successful miner such that all the computing power will be used to mining.

Related Works
Recent years have seen a number of studies on security issues of blockchain, such as the selfish mining attack [8], the Eclipse attack [10] and the distributed denial-of-service attack [11]. A closely relevant attack to our study is the Block Withholding Attack (BW attack) which is first defined by Rosenfeld in [16]. In this attack, a miner who has found a legal block chooses not to submit it to the mining pool immediately but rather delays to submit or even directly abandons it. Many follow-up studies focus on the simulation and countermeasures of BW attacks.
To resist BW attacks, Schrijvers et al. [17] designed a new incentive compatible reward function and showed proportional mining rewards are not incentive compatible. It was shown in [4] that by giving extra reward to a miner who actually finds the winning block on behalf of the pool, it is possible to discourage BW attacks. Tosh et al. [18] modeled the BW attacks in a blockchain cloud and demonstrates that attacker's access to extra computational power could disrupt the honest mining operation. Very recently, Wu et al. [19] constructed a generalized model where two participants can choose to either cooperate with each other or employ a BW attack. They showed that increasing the information asymmetry by utilizing information conceal mechanisms could lower the occurrence of BW attacks. More studies in this line can be found in [3,14,9].
The Pool Block Withholding Attack (PBW attack) is a variation of BW attacks, the difference is that the PBW attack is launched by a pool manager rather than a miner. Eyal [7] describes PBW attacks from the perspective of game theory in which the players are pool managers and the strategy of each manager is allocating some powers to launch the block withholding attack. Eyal also proves that with any number of pools, all pools mining honestly and not attacking each other is never a Nash equilibrium. Subsequently, [1] follows Eyal's study on the case of two pools attacking each other. They show that this game always admits a pure Nash equilibrium, and its pure price of anarchy is at most 3.
Finally, there are also many other game theoretic studies about Bitcoin and other crypto currencies. For example, [2] studies how to incentivize the users to propagate each transaction in a tree network; [5] shows that with only transaction fees (and negligible block rewards), the miners have strong incentive to fork a block and generate a greater reward; [12] views Bitcoin from a cooperative game theoretic perspective and show under high transaction loads, it is difficult for pool managers to distribute rewards in a stable way; [6] adopts an axiomatic approach to investigate how the reward should be distributed among the miners.

Model
In this section, we formally define the Discouraging pool block withholding games (DPBW games). Similar with [7] and [1], it is assumed that each miner exactly joins one pool and is totally operated by that pool's manager. Thus the players in a DPBW game are the managers of n mining pools, denoted by N . Let m i ∈ R + be the mining power of manager i ∈ N . Assume m is the total mining power in the worldwide Bitcoin system and m ≥ i∈N m i . By m > i∈N m i , we mean there are extra mining power outside of the studied pools N , due to any solo miners or inaccessible mining pools.
In a DPBW game, each player i might only allocate α i fraction of the total reward to her miners proportionally to their mining power and award the left to the successful miner. She might also use a fraction of its mining power to infiltrate another pool j. Such mining power does not actually work for pool j, but gets a fraction of the total reward from j. It is assumed that the mining powers are continuous and can be arbitrarily divided. In this work, we study how to select these α i 's for the players so that all of them do not want to infiltrate others. Thus player i's strategy space is all possible represents the amount of mining power that i wants to infiltrate pool j. Denote by x = (x 1 , · · · , x n ) a full strategy profile.
To make us focus on the pool block withholding behaviors, we assume the reward for each block is fixed, thus the selection of the transactions does not matter. Given a strategy profile x, the players' utilities are defined as follows: Assume each player i first gets a total reward of r i (x) by mining and infiltrating other pools. Then she deducts (1 − α i ) fraction from r i (x) used for award and obviously only her honest miners can get this. The remaining reward α i r i (x) is proportionally allocated to all her miners including both her honest and the infiltrated ones from the other pools. Thus the pool's true utility is the total reward allocated to her honest miners.
More precisely, each player i's reward r i (x) consists of two parts: direct reward and infiltrating reward. Since every player i only uses m i − l =i x il mining power for honest mining, player i's direct reward is proportional to the fraction of the honest mining power contributed by her pool, denoted by since the pools cannot distinguish infiltrating miners from honest miners, player i's infiltrating reward from every other pool j is proportional to the fraction of her infiltrating mining power to j, denoted by Note that both the direct reward and the infiltrating reward will be allocated to all miners. Accordingly, player i's total reward is and her utility is For any vector v = (v 1 , . . . , v n ) and a particular 1 ≤ i ≤ n, denote by v −i the resulting vector of v when element v i is omitted. A strategy profile x is called a Nash equilibrium if for every player i and every possible strategy . In a non-cooperative game, the price of anarchy (PoA) is defined as the ratio between the optimal social welfare and the worst social welfare of any possible Nash equilibria; while the price of stability (PoS) is defined as the ratio between the optimal social welfare and the best social welfare of any possible Nash equilibria. In DPBW games, the social welfare is defined as the total mining power that is used to honest mining.

The PoS of DPBW Games is 1
In this section, we prove that for most reasonable α i 's, no-pool-attacks is always a Nash equilibrium of DPBW games for any number of mining pools, that is, the PoS of DPBW games is always 1. Formally, Theorem 1 Strategy profile (0, . . . , 0) is a Nash equilibrium for any DPBW game if ∀i, α i ≤ 1 − mmax m , where m max = max i∈N m i . Proof Let x = (x 1 , . . . , x n ) be the strategy profile such that x ij = 0 for any i ∈ N and j ∈ N \ {i}. Note that, in Equation (1), the coefficient before r i (x) is always 0 as x ji = 0 for all j = i. Thus, in the rest proof we show Arbitrarily fix a player i and it is easy to see r i (x) = mi m . To prove the theorem, it suffices to show that for any feasible strategy x ′ i with all j = i and Denote i's total infiltrating mining power under strategy Now we claim the following inequality: Note that Inequality (2) , which completes the proof of Theorem 1.
The remaining is dedicated to show the correctness of Inequality (2). By rearranging the terms, the lefthand of Inequality (2) equals .
As the denominator is always positive, we only need to consider the sign of its numerator: where the first inequality is because x ′ ij ≥ 0 and the second is because α i ≤ 1 − mmax m .
Remark. Note that mmax m fraction of the reward cannot be too large for any dencentralized system, thus we believe the requirement of α i ≤ 1 − mmax m in Theorem 1 is a reasonable tradeoff between complementing the maintenance of a pool and incentivizing the miners to join it.

The Uniqueness of Nash equilibrium for Two-Pool Case
In this section, we study a special case of the DPBW game when only two pools are included, which is exactly the same setting with the previous work [1]. However, as will be proved, in PBWA+ game, it is possible for the pool managers to deduct a small fraction from the reward, so that no-pool-attacks is a unique Nash equilibrium.
Theorem 2 For PBWA+ Game with two players, by setting α 1 ≤ 1 − m2 m , α 2 ≤ 1 − m1 m and m > 3(m 1 + m 2 ), the game has a unique Nash equilibrium where both players do not infiltrate the other pool.
We believe the requirement of m > 3(m 1 +m 2 ) in the theorem is reasonable as the statistic website 3 shows that the largest two pools have roughly a third of the total computational power.

Notations and Proof Ideas of Theorem 2
Before we prove Theorem 2, we first simplify our notions to ease our representation. Since there are only two players, we simplify our notions as follows.
her total reward is and her utility is Here note that in U i (x 1 , x 2 ), the first coefficient 1 − α i + miαi mi+xj only depends on x j , thus when we analyze player i's utility gain by unilateral deviation, without loss of generality, we just ignore this coefficient and only consider her total reward r i (x 1 , x 2 ). Solving the reward system of equations in r i (x 1 , x 2 ) for i = 1, 2, we get the closed forms for the reward functions: and x 2 ) the reward gain by unilateral deviation. By definition, the necessary and sufficient condition for strategy profile (x 1 , x 2 ) to be a Nash equilibrium is for any Thus the problem of finding all possible Nash equilibria becomes finding all such (x 1 , x 2 ) strategy profiles.
Since players 1 and 2 are symmetric, in the following, without loss of generality, we often use player 1 for illustration. The formula of f 1 (∆x 1 ) can be simplified as a quadratic function of ∆x 1 : where the formulas of A 1 (x 1 , x 2 ), B 1 (x 1 , x 2 ) and C 1 (x 1 , x 2 ) are shown in Table 1.  x 2 ), B 1 (x 1 , x 2 ) and C 1 (x 1 , x 2 ).
Therefore, combining with players 1's and 2's strategies, we have nine kinds of possible Nash equilibria. By Theorem 1, we already know that (0, 0) is a Nash equilibrium. In the following, we will show that (0, 0) is actually the only possible Nash equilibrium for among the nine situations. Thus in any DPBW game with two players, both the PoA and the PoS are 1. In the remaining of this section, we prove Theorem 2 by showing that all the eight situations, except (0, 0), are not possible to be Nash equilibria.

Case 2 + Case 2:
To simplify our analysis, we first multiply to eliminate the denominator, denoting the resulting polynomial by Q 1 (x 1 , x 2 ). By rearranging every monomials, Q 1 (x 1 , x 2 ) can be denoted as a quadratic function of x 1 : where a 1 (x 2 ), b 1 (x 2 ) and c 1 (x 2 ) are independent of x 1 and their formulas are shown in Table 2. Similarly, we also have all the corresponding definitions of Q 2 (x 1 , x 2 ), a 2 (x 1 ), b 2 (x 1 ), and c 2 (x 1 ) for player 2.
To show the impossibility of Case 1, it suffices to prove the following lemma.
Before we prove Lemma 1, we first prove the following claims (Claim 4.3, Claim 4.3 and Claim 4.3).
Proof To prove Claim 4.3, We first show the following facts: c 1 (x 2 ) achieves its local maximal value at some y < 0.
If the above three facts setting up, the curve of c 1 (x 2 ) can be shown in Figure  2, and c 1 (y) < 0 for any y ∈ [0, m 2 ] (the red part), Combing the three facts, the curve of c 1 (x 2 ) can be shown in Figure 2, and c 1 (x 2 ) < 0 for any x 2 ∈ [0, m 2 ] (the red part), which completes the proof of the claim. To see the second fact, we note that where the last inequality is because m ≥ 2(m 1 + m 2 ) and α 2 − 1 ≤ − m1 m . To prove the third fact, we first compute the derivative of c 1 (x 2 ), which is a quadratic function of x 2 . Combing the previous two facts and the property that 3α 2 m 2 > 0, to show the third fact, it suffices to show the "constant term" of c ′ 1 (x 2 ) is smaller than 0. This sufficient condition can be proved by the following derivation.
Proof As m ≥ 3(m 1 +m 2 ), the claim easily follows by the following inequalities.
Proof Since players 1 and 2 are symmetric, we only prove for player 1. If a 1 (x 2 ) = 0, then the curve of Q(x 1 , x 2 ) (a quadratic function of x 1 ) will degenerate to a line (see Figure 3a). Since its slope b 1 (x 2 ) is negative and y-intercept is non-positive, Q 1 (x 1 , x 2 ) cannot be 0 for any x 1 > 0. By the symmetricity ofQ 1 (m 2 ) andQ 2 (m 1 ), we havē Thus we get a contradiction with m ≥ 3(m 1 + m 2 ), which completes the proof of Lemma 1 and accordingly Case 1 + Case 1 cannot be a Nash equilibrium.

Other Situations
Finally, we briefly discuss the remaining situations: (x 1 , x 2 ) ∈ {(0, m 2 ), (m 1 , 0), (m 1 , m 2 )}. It is not hard to see that neither of them can benefit by sending all her mining power to attack the other: for case (m 1 , m 2 ), both two players get no reward; for case (0, m 2 ), player 2 only gets and the case (m 1 , 0) is symmetric to (0, m 2 ).
In conclusion, all the eight situations, except (0, 0), are not Nash equilibria, which finishes the proof of Theorem 2.

Conclusion and Future Directions
In this work, we refine the game-theoretic model for pool block withholding attacks when the managers of the pools individually deduct small fractions from the total rewards. For most reasonable deductions, we show that no-poolattacks is always a Nash equilibrium for any number of pools, and particularly, when there are only two pools under consideration, it is the unique Nash equilibrium.
A direct open problem is to generalize our second result to more than two pools, that is, is it possible for an arbitrary number of managers to make small deductions so that no-pool-attacks is also a unique Nash equilibrium?
There are many other future directions that deserve exploration. For example, in all works about PBW games that we know, it is assumed that every miner for a pool is always loyal to her pool manager. This assumption does not hold when the miners have their own interests on how to report their solutions. We hope that, by combining tools in cooperative game theory, our work can inspire further study in this direction.