A Biform Game Approach to Preventing Block Withholding Attack of Blockchain Based on Semi-CIS Value
- DOI
- 10.2991/ijcis.d.191030.001How to use a DOI?
- Keywords
- Blockchain; Mining pool; Block withholding attack; Biform game; Big data
- Abstract
In proof-of-work (PoW)-based blockchain network, the blockchain miners publish blocks by contributing computing power to solve crypto-puzzles. Due to the weak computing power of single miner, miners tend to join a mining pool and share the profits from the mining pool according to the contribution proportions of the miners. However, some miners may initiate block withholding attack which may result in wasting computing power, even threatening the efficiency of the blockchain network. To address this problem, in this paper, we use the biform game model to optimize the miners' strategy choices. We firstly formulate the mining process as a non-cooperative–cooperative biform game model. We use the model to exhibit miners' strategy choices (non-cooperation stage) and the cooperation mining process (cooperation stage). Then we set the conditions to maintain the voluntary honest behavior of miners. After that, we employ the semi-CIS (semi-the center of imputation set value) value to compute the solutions of the cooperative games in the cooperation stage, and optimize miners' strategy choices to prevent the block withholding attack. Hence we can ensure the blockchain network is secure. Finally, the validity and applicability of the proposed model and method are verified by a numerical example.
- Copyright
- © 2019 The Authors. Published by Atlantis Press SARL.
- Open Access
- This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).
1. INTRODUCTION
In recent years, blockchain technology has received extensive attention due to its auditability, immutability, security and anonymity. But strictly speaking, the technology is immature. There are many security problem. As the typical application, bitcoin has been running steadily for many years. However, the blockchain mining security issue is remain tough. With the increasing popularity of the blockchain technology, the blockchain mining has attracted more and more attention. And the proof-of-work (PoW) is a commonly used consensus mechanism for blockchain mining. Its operation principle is as follows: miners publish blocks by contributing computing power to solve crypto-puzzles and acquire profits when solving successfully. Since the blockchain system generates one block about 10 minutes, it is difficult for most miners to produce a block in a given period of time. In order to increase the possibility of obtaining stable profits, miners will choose to join the open mining pool for computational share (i.e., cooperative mining). Specifically, the miners acquire profits through accepting the less difficult tasks released by the mining pool manager and submitting the PoWs to the mining pool manager. However, in the mining pool system, there are some miners may initiate block withholding attack. This attack is an action that the attackers only submit partial PoWs (PPoWs) to the mining pool manager as the computational share. They will not submit the integral PoWs, but discard them when they find the integral PoWs. When the mining pool manager detects that the mining pool is suffering from block withholding attack, it is very difficult to identify the attacking miners. So without contributing the integral computing power, the attackers obtain profits from the mining pool, which result in reducing the profit of the mining pool and wasting computing power, even threatening the efficiency of the blockchain network. To address this challenge, Sarker et al. [1] and Tosh et al. [2] researched the solutions to this problem from the perspective of mining rewards model improvement. Siamak and Maria [3] and Chang and Park [4] improved the timestamp technology to prevent the block withholding attack. Meanwhile, to prevent block withholding attack, a solution to model the mining process as a stochastic game has been investigated [5], which used the reinforcement learning method to simulate the mining pools how to launch the block withholding attacks. Wang et al. [6] researched the mining process with a two-stage game model and analyzed the existence conditions of the Nash equilibrium and strategy choice stability. Tang et al. [7] applied non-cooperative iterated game to analyze miners behaviors, and resorted Zero-Determinant (ZD) strategy to design strategy mechanism to solve the tragedy of the commons problem in mining pool. Similarly, Hu et al. [8] applied the ZD strategy to analyze the strategy choices of arbitrary two mining pools to stop block withholding attack, and the application conditions of ZD strategy was given and the validity of the method was verified. Wu et al. [9] employed pure strategy and hybrid strategy to prove that information hiding mechanism which can increase information asymmetry can reduce the occurrence of block withholding attack. Bag et al. [10] proposed cryptographic commitment schemes combined the hash function to counter block withholding attack. According to the above analysis, we can learn that the non-cooperative game or the evolutionary game method is generally used to avoid the block withholding attack in the mining pool.
In actual mining process, miners are not just the single relationship of competition or cooperation. The relationship among them is showing the interweaving of competition and cooperation. That means cooperation in competition and competition in cooperation. So a single non-cooperative or cooperative game approach is not well used to demonstrate the essence of the mining problem. In view of this, we adopt the concept of the biform game that was firstly proposed in 2007 by Brandenburger and Stuart [11] to research the strategy optimization of miners to avoid block withholding attack. This kind of game is mainly divided into two stages: the first stage is the non-cooperative game, the players in the game choose strategies and form the strategy situations, but the strategy situations only form the competitive environment of the second stage, not directly generate payments; the second stage is the cooperative game, the players cooperate and form coalitions in the strategy situations which formed in the first stage. Moreover, this stage distributes benefits among the players, and the benefit allocation values are as the payments of the players in the first stage.
Generally, the non-cooperative game and cooperative game are used to solve different problems. The non-cooperative game is to solve the strategy choice problems. Specifically, it is to study how the players make decisions to maximize their own benefits in the interactional situation. And it does not consider whether the players cooperate with each other and how to distribute cooperative incomes. While the cooperative game is to solve income distribution problems. It studies how to distribute the benefits among people when they reach cooperation. And the cooperative game does not consider the strategy choice problems. In reality, the miners want to obtain the benefits brought by the strategy when they make strategy choices. The biform game realizes the combination of the non-cooperative game and cooperative game. So it can be used to solve the game problems including both strategy selection and profit distribution. That is to say, the miners can obtain the strategy and the benefits brought by the strategy at the same time, rather than just acquiring one of the two.
Since the introduction of the biform game theory, its theoretical and applied research has been in the ascendant. Such as, Ryall and Sorenson [12] analyzed the competition problem of agents in the framework of biform game. Gui et al. [13] used the biform game approach to construct an incentive mechanism to encourage producers to participate in the design of recyclable products. Mahjoub and Hennet [14] applied the biform game to describe the supply network design problem under the market expectation price elasticity demand. Feess and Thun [15] researched the biform game model based on the Shapley value, and used it to solve the strategy choice and revenue distribution problems in the supply chain. Kim [16] solved the low flexibility and adaptability problem of wireless body area network (WBAN) by building a WBAN resource sharing reverse-biform game model. In this paper, we formulate the mining process as a biform game model to optimize miners' strategy choices. For the two stages of the non-cooperative–cooperative biform game, we employ the semi-CIS (semi-the center of imputation set value) value to compute the solutions of the cooperative games in the cooperation stage. And the obtained benefit allocation values are as the payments of the players in the non-cooperation stage. Then the pure strategy Nash equilibrium solution in the non-cooperation stage is obtained. Special emphasis on one point: the biform game method can always guarantee to be the pure strategy Nash equilibrium solution, while the Nash equilibrium of the non-cooperative game is a mixed strategy in most cases. Due to the fact that the mixed strategy cannot be implemented or applied well in practical problems, we apply the biform game model to better instruct miners to choice strategy. Finally, we achieve the goal of preventing block withholding attack.
The rest of this paper is organized as follows. Section 2 constructs the mining pool biform game model. This section describes the problem of miners strategy choices in the non-cooperation stage, the problem of miners mining in cooperation stage and the characteristic functions of cooperative games. On the basis of the definitions and properties of the semi-CIS value in the cooperation stage and the Nash equilibrium solutions in the non-cooperation stage, the solving method and procedures of the mining pool biform game model are summarized in Section 3. In Section 4, the validity and applicability of the proposed model and method are verified by a numerical example. Finally, the conclusions are stated in Section 5.
2. SYSTEM MODELS
2.1. Miner Strategy Choice in Non-Cooperation Stage
There are
All of the miners will form
Strategies | Miner 3 |
||||
---|---|---|---|---|---|
0 |
1 |
||||
Miner 2 |
Miner 2 |
||||
0 | 1 | 0 | 1 | ||
Miner 1 | 0 | ||||
1 |
The strategy situations of three miners with two strategies.
The situation
2.2. Problem and Method in Cooperation Stage
The first stage is non-cooperation in biform game model which is different from the two-stage game model due to payoffs unknown a prior. We have cooperation rather than non-cooperation second-stage games for the following reasons.
In the mining pool system, the mining pool manager divides the mining task into a number of subtasks which are less difficult and sends them to the miners. Then the miners receive the subtasks and submit the completed PoWs to the mining pool manager, which means that the miners participate in cooperative mining. So how to pay profits to the cooperative miners is a cooperative game problem, where the miners are regarded as the players. Another reason is that the benefits of miners participating in mining cooperation are more than those they do alone.
In addition, the payoff values of the two-stage game can be directly determined in the first non-cooperation stage, while those of the biform game are computed based on the calculation results of second cooperation stage.
In this paper, the cooperative game is expressed as
The definitions of the parameters used in Eq. (1) are listed in Table 2.
Parameter | Definition |
---|---|
The fixed token-issuing reward decided by the blockchain network | |
The transaction confirmation price per unit data size decided by the blockchain users | |
s | The block size decided by the number of transactions |
The set of the miners with the honest strategy in the coalition |
|
The set of the miners with the malicious strategy in the coalition |
|
The miner |
|
The miner |
|
The total computing power of the blockchain network, which can be obtained by multiplying | |
The number of miners by the average computing power of the miners | |
The computing power of the miner |
|
The computing power of the miner |
|
The computing power of the mining pool | |
The proportion of the submitted PoWs when the miners choose the malicious strategy | |
The cost per unit computing power decided by the mining pool system |
Parameters and their definitions.
Further,
Theorem 1.
Assume that
Proof.
Give a miner
If the miner
Therefore, we have
If
For example, a coalition
If
Simultaneously, the profit of the coalition is
If
Simultaneously, the profit of the grand coalition is
3. MODEL SOLVING METHOD AND PROCEDURES
In this section, based on the analysis of the definitions and properties of the semi-CIS value in the cooperation stage and the Nash equilibrium solutions in the non-cooperation stage, the solving method and procedures of the mining pool biform game model are proposed.
3.1. Semi-CIS Value
The semi-CIS value is one of important single-valued solutions of cooperative games. It first assigns each player (i.e., miner) to individual worth, and then distributes the remaining income of the grand coalition equally among all players [17,18].
Definition 1.
For a n-person (i.e., miner) cooperative game
Here, for any player
The calculation of the semi-CIS value is only related to the values of the grand coalition and the individuals, not related to other intermediate coalitions' values. This is similar to the real miner's profit calculation, which the miner's profit concerns only about the computing power of each miner contributing and the entire computing power of the mining pool.
The semi-CIS value satisfies collective effectiveness. Namely,
Definition 2.
For any players
Definition 3.
Assume that there exist two cooperative games
Definition 4.
Assume that there exist a
According to Definitions 1–4, it is straightforward to prove the following conclusion, i.e., Theorem 2 (Here we omit the proof).
Theorem 2.
The semi-CIS value is the unique value, which satisfies efficiency, equal maximal complaint property, linearity, semi inessential game property, and semi individual monotonicity.
3.2. Nash Equilibrium Solutions in Non-Cooperation Stage
Definition 5.
For a biform game
Definition 6.
Obviously, Definition 6 means the profit of the grand coalition reaches the maximum value in the effective strategy situation.
Further, we can prove the following three conclusions by using Definitions 1–6.
Theorem 3.
Assume that the characteristic function of the biform game
Corollary 1.
For any strategy
Theorem 4.
Assume that the characteristic function of the biform game
Theorem 5.
Assume that the characteristic function of the biform game
Corollary 2.
Assume that the characteristic function of the biform game
Corollary 3.
Assume that the characteristic function of the biform game
3.3. Solution Steps
From the above discussion, the solution steps of the mining pool biform game model are summarized as follows:
Step 1. (the non-cooperation stage): All the miners in the mining pool choose strategies and execute strategy combinations to form strategy situation
Step 2. (the cooperation stage): For any strategy situation
Step 3. (the solution of cooperation stage): We calculate the semi-CIS
Step 4. (the solution of non-cooperation stage): The semi-CIS
According to the pure strategy Nash equilibrium solutions in the fourth step, we can determine the strategy choice of the entire mining pool. That is to say, we can get a mining pool strategy to maximize the profits (or utilities) of each miner and the entire mining pool.
4. A NUMERICAL EXAMPLE
Let us consider a simple example: there are three miners (i.e., players) 1, 2, and 3 in a mining pool. In order to obtain high profit, the miners 1, 2, and 3 have to make strategy choices. Stated as earlier, they have two strategies to choose: the malicious strategy (remark 0) and the honest strategy (remark 1). We set system parameters as follows:
4.1. Solving the Cooperative Game Stage
The above example is related both strategy choices (non-cooperation stage) and mutual cooperation (cooperation stage) among the miners 1, 2, and 3. Consequently, it can be seen as a biform game problem. We can use the solution steps in Section 3.3 to solve this problem.
Stated as earlier, the strategy situations formed by the miners 1, 2, and 3 are shown in Table 1. According to Eq. (1) and Table 1, we calculate the coalitions profits (or utilities) in every strategy situation as shown in Table 3 (This article only lists the profit values of the grand coalition and the individual miner coalition). Remark: When the calculation result is negative, we take 0.
Strategies | Miner 3 |
||||
---|---|---|---|---|---|
0 |
1 |
||||
Miner 2 |
Miner 2 |
||||
0 | 1 | 0 | 1 | ||
Miner 1 | 0 | ||||
1 |
The coalitions profits in every strategy situation.
4.2. Solving the Non-Cooperative Game Stage
According to Eq. (2), we calculate the semi-CIS value
Strategies | Miner 3 |
||||
---|---|---|---|---|---|
0 |
1 |
||||
Miner 2 |
Miner 2 |
||||
0 | 1 | 0 | 1 | ||
Miner 1 | 0 | ||||
1 |
The coalitions profits in every strategy situation.
Then taking the semi-CIS values in Table 4 as the corresponding profit values of the miners in various strategy situations. For each strategy situation, we calculate the sum of the profit values of all the miners, i.e., calculating the total profit value in the situation, which is expressed as
The calculation results are shown in Table 5.
Strategies | Miner 3 |
||||
---|---|---|---|---|---|
0 |
1 |
||||
Miner 2 |
Miner 2 |
||||
0 | 1 | 0 | 1 | ||
Miner 1 | 0 | ||||
1 |
The total profit values in each strategy situation (semi-CIS values).
In the following, we take the maximum value of
And the maximum value is
Thereby, the solution of the biform game is
Further analysis can obtain that
Analogously, the corresponding strategy situation of sub-maximum value
Because
Through the above analysis, we can conclude that
5. CONCLUSIONS
In order to prevent miners from initiating block withholding attack, this paper models the mining process as a biform game, wherein the miners might choose whether to attack or not. And we set constraints to maintain the voluntary honest behavior of miners during the cooperation stage. Though analyzing and researching the numerical example, we can conclude that the biform game can well solve the miners strategy choices and benefits distribution problems, and can prevent the block withholding attack effectively. Moreover, the biform game can make up for the shortcomings of using the single cooperative game or non-cooperative game method. Specifically, it makes up the deficiency of non-cooperative game that the players only care about strategy design without considering the payoff distribution of coalitions. Simultaneously, it also remedy the cooperative game only analyze the coalition formation and its payoff distribution without taking into account strategy design and selection. Besides, the solutions of the biform game must be the pure strategy Nash equilibrium solution, so it can better guide the miners strategy choice.
In this paper, we propose the semi-CIS value, which can guarantee the existence and uniqueness of the solution in the cooperation stage, to solve the payoff values of cooperative game. And the existence conditions of the solution of the biform game are given. In summary, this paper not only provides a new solution to the miners' action of initiating block withholding attack problem, but also enriches the application research of the biform game method.
This study only considers the influence of computing power on the profit of the mining pool, but there are many other factors to affect the profit of the mining pool such as mining machine, mining pool site. And this study is only applicable to the case that the number of miners in the mining pool is constant. Not considering the dynamic change in the number of miners in the mining pool. So we will carry out the above researches in the future.
CONFLICT OF INTEREST
Firstly, there is no potential conflict of interest.
AUTHORS' CONTRIBUTIONS
Xiao-Li Du developed the model, performed the analysis, and wrote the paper. Deng-Feng Li conceived the presented idea, and provided critical feedback and helped shape the research, analysis, and manuscript. Kai-Rong Liang was responsible for collecting the data and writing the first draft.
Funding Statement
Lastly, the funding statement is as follow: The authors would like to acknowledge the financial support from the National Natural Science Foundation of China (Grant Nos. 71231003).
ACKNOWLEDGMENTS
The authors would like to acknowledge the financial support from the National Natural Science Foundation of China (Grant
REFERENCES
Cite this article
TY - JOUR AU - Xiao-Li Du AU - Deng-Feng Li AU - Kai-Rong Liang PY - 2019 DA - 2019/11/22 TI - A Biform Game Approach to Preventing Block Withholding Attack of Blockchain Based on Semi-CIS Value JO - International Journal of Computational Intelligence Systems SP - 1353 EP - 1360 VL - 12 IS - 2 SN - 1875-6883 UR - https://doi.org/10.2991/ijcis.d.191030.001 DO - 10.2991/ijcis.d.191030.001 ID - Du2019 ER -