Greedy-Mine: A Profitable Mining Attack Strategy in Bitcoin-NG

BY KEYHUNTER 05.03.2025
Greedy-Mine: A Profitable Mining Attack Strategy in Bitcoin-NG

Bitcoin-NG is an extensible blockchain protocol based on the same trust model as Bitcoin. It divides each epoch into one Key-Block and multiple Micro-Blocks, effectively improving transaction processing capacity. Bitcoin-NG adopts a special incentive mechanism (i.e., the transaction fees in each epoch are split to the current and next leader) to maintain its security. However, there are some limitations to the existing incentive analysis of Bitcoin-NG in recent works. First, the incentive division method of Bitcoin-NG only includes some specific mining attack strategies of adversary, while ignoring more stubborn attack strategies. Second, once adversaries find a whale transaction, they will deviate from honest mining strategy to obtain extra reward. In this paper, we are committed to solving these two limitations. First, we propose a novel mining strategy named Greedy-Mine attack. Then, we formulate a Markov Decision Process (MDP) model to analyze the competition of honest miners and adversaries. Furthermore, we analysis the extra reward of adversaries and summarize the mining power proportion range required for malicious adversaries to launch Greedy-Mine to obtain extra returns. Finally, we make a backward-compatibility progressive modification to Bitcoin-NG protocol that would raise the threshold of propagation factor from 0 to 1. Meanwhile, we get the winning condition of adversaries when adopting Greedy-Mine, compared with honest mining. Simulation and experimental results indicate that Bitcoin-NG is not incentive compatible, which is vulnerable to Greedy-Mine attack.

\textbf{Keywords:} Blockchain, Bitcoin-NG, Mining Strategy, Incentive Mechanism, Markov Decision Process.

1 Introduction

1.1 Related Work

In 2008, Nakamoto proposed the Bitcoin blockchain protocol, trying to achieve consensus under a permissionless setting [1]. Bitcoin blockchain, based on Proof of Work (PoW), effectively deters sybil attacks [2]. The blockchain can be seen as a decentralized ledger, which is composed of continuous blocks that follow certain rules and linked through specific cryptographic methods. In Bitcoin blockchain, the first block (which does not reference any other block) is called the genesis block. Each block is composed of block header and block body. The block header mainly includes hash of previous block, time stamp, etc. The block body includes complete transaction data. The successful applications of blockchain in the financial field [3, 4], the Internet of Things [5, 6, 7, 8], the network security field [9, 10], the public service field [11, 12], the digital copyright field [13, 14], and the insurance field [15], which have made blockchain technology widely concerned by all walks of life. In the process of continuous development of blockchain, its scalability problems are gradually emerging. Compared with the global payment system Visa with an average of 50000 TPS (Transactions Per Second), the current blockchain system, such as Bitcoin with an average of 7 TPS, ETH with an average of 20 TPS [16], and EOS with an average of 3000 TPS, is not enough to meet the needs of modern financial transactions. In Bitcoin, Nakamoto chooses a fairly secure system parameter, namely, the average block output time is 10 minutes and the block size is limited to 1MB. Relevant researches show that modifying the blockchain system parameters (such as increasing the block size limit or reducing the average block output time) can increase TPS to a certain extent, but will reduce the security level of the blockchain system [9, 17]. Therefore, redesigning the consensus protocol at the underlying blockchain has become a research hotspot in recent years.

The design of the new blockchain consensus protocol can be roughly divided into three categories: Block Classification, Parallel Chains, and Directed Acyclic Graph (DAG). In the area of block classification, FruitChain [18], Bitcoin-NG [19] divide blocks into two categories: the main blocks are responsible for choosing the longest chain of consensus protocol, and the micro blocks are responsible for packaging transactions, which can effectively improve the system throughput of blockchains. In parallel chains, OHIE [20] and Prism [21] can improve system throughput while ensuring system security. The design of Monoxide [22] is more complex. From the perspective of academic analysis, it can effectively improve throughput without certain security. And there is a trade-off between scalability and security in Monoxide. In a DAG-based design approach, Inclusive [23] only proposes basic design principles without detailed introduction to complement the protocol. In Spectre [24], transactions can be confirmed in seconds and throughput is increased by orders of magnitude over bitcoin. Phantom [25] uses a greedy algorithm to distinguish blocks mined by honest miners legally from blocks mined by malicious miners that deviate from the DAG mining protocol, and ultimately provides full order on the BlockDAG in a uniform manner by all honest nodes to meet the specific requirements for ledger timeline in smart contracts. In Conflux [26], it improves the performance of the blockchain through reasonable design and optimization of system, while ensuring the security of the blockchain. Conflux has improved the throughput of the blockchain at the consensus level and has reduced the waiting time of block confirmation. Among them, Bitcoin-NG blockchain has received extensive attention from blockchain practitioners.

Bitcoin-NG [19] is among the first and the most prominent PoW-based blockchains to approach the near-optimal throughput, which has the same trust model as Bitcoin. It divides blocks into two categories: Key-Blocks and Micro-Blocks. Key-Blocks are responsible for participating in consensus protocol, while Micro-Blocks are responsible for packaging transactions. Bitcoin-NG improves performance by separating consensus protocols and packaging transactions. More specifically, each Key-block is generated through the leader election process, and the corresponding leader will obtain a block reward, which is called mining process. Furthermore, the leader can package multiple Micro-blocks and receive transaction fees until the next key block is generated, which is called process of packaging transactions. More intuitively, Bitcoin-NG separates transaction serialization process from leader election process, which brings Bitcoin-NG to approach the near-optimal throughput, since Micro-blocks can be generated at a rate up to the network capacity. It is precisely for this reason that Bitcoin-NG has been applied to cryptocurrencies Waves [28] and Aeternity [29].

The idea of separation has inspired many novel blockchain protocols including ByzCoin [30], Hybrid consensus [31], Prism [21] and so on. Although these protocols can achieve lower latency or higher throughput than Bitcoin-NG, the design and analysis of their incentive mechanisms are still unclear. However, as the foundation of these protocols, Bitcoin-NG still has certain limitations in incentive analysis, which will be explained in detail in section 3.3.

In Bitcoin-NG, Eyal [19] proposes two possible malicious attacks (Transaction Inclusion Attack and Longest Chain Extension Attack), which derives the division proportion of transaction fees. Jiayuan Yin [27] proposes Modified Transaction Inclusion Attack, which reallocates transaction fees and improves the imperfection of original transaction inclusion attack. The above incentive analysis based on Bitcoin-NG only includes the limited mining attacks of adversaries, while ignoring more novel mining strategies. Besides, they do not consider the extreme cases that may occur in the blockchain, e.g., whale transaction. Once whale transactions are detected by adversaries, they will deviate from honest mining strategy to obtain extra reward (whale transactions are more profitable).

1.2 Our Contributions

To address the above issues, we first propose a novel mining strategy: greedy-mine, which can increase the reward of adversaries. Furthermore, we model greedy-mine strategy through Markov Decision Process (MDP) to analyze the competition of honest miners and adversaries. Finally, we model Markov Reward process and calculate the extra reward of adversaries, which indicates that Greedy-Mine is more profitable than honest mining strategy. Specifically, we have the following contributions:

We first represent the Bitcoin-NG incentive mechanism and visually redescribe the design principle of Bitcoin-NG, which greatly enhances the understanding of Bitcoin-NG’s underlying design principle.

Second, we propose a novel mining strategy named Greedy-Mine and model Greedy-Mine strategy through Markov Decision Process (MDP) to analyze the competition of honest miners and adversaries. We further calculate the extra reward of adversaries, which demonstrates that Bitcoin-NG mining is not incentive compatible.

Third, we summarize the mining power proportion range required for adversaries to launch Greedy-Mine to obtain excess returns. When the greedy pool has more than 18% of the system mining power, launching Greedy-Mine is more profitable than honest mining. Furthermore, miners with more mining power are more motivated to adopt Greedy-Mine.

Finally, we make a backward-compatibility progressive modification to Bitcoin-NG protocol that would raise the threshold of propagation factor from zero to 1. Meanwhile, we get the winning condition of adversaries when adopting Greedy-Mine and honest mining, respectively, which indicates Bitcoin-NG is vulnerable to Greedy-Mine attack.

2 Preliminaries

2.1 Overview of Bitcoin-NG

Bitcoin-NG is an extensible blockchain protocol based on the same trust model as Bitcoin. On the basis of Bitcoin blockchain, Bitcoin-NG improves the blockchain performance under the Nakamoto consensus by separating consensus protocols and packaging transactions. The time is divided into multiple epochs, and each epoch contains a leader (i.e., block in the main chain). The tenure of each leader is about 10 minutes, during which the transactions in the transaction pool will be packaged. Each leader can obtain corresponding block reward (coinbase reward) and transaction reward, which ensures that miners are willing to participate in the Bitcoin-NG.

2.2 Key-Block and Micro-Block

Bitcoin-NG divides blocks into two categories: Key-Blocks and Micro-Blocks. Key-Blocks are responsible for consensus agreements, meanwhile, Micro-Blocks are responsible for packaging transactions.

Key-Blocks: Consensus Protocol. Key-blocks are responsible for leader election, which ensures the security of consensus protocol. Similar to Bitcoin, the Key-Block contains reference to the previous block, current GMT time, coinbase transactions to pay out the reward, target value, nonce, and public keys for packaged micro-blocks. Miners must traverse nonces until the PoW Puzzle is successfully solved, which means the hash of Key-Block header smaller than the target. The miner who finds a valid key-block will set the coinbase transaction to output to his own account address, which is calculated through the hash of public key. The process of a miner trying a nonce can be seen as a Bernoulli trail. Multiple Bernoulli trails form a Bernoulli process. Therefore, the process of miners mining Key-Blocks is memoryless. Furthermore, Bitcoin-NG adjusts the difficulty of mining puzzle through changing the target value to maintain the average block generation rate, which ensures the security of Bitcoin-NG.

Micro-Blocks: Packaging Transaction. When a miner generates a valid Key-Block, he becomes the leader within the current epoch. Leader can package transactions to generate Micro-Blocks at a rate below the predefined maximum rate. The predefined maximum rate of the Micro-Blocks is deterministic and can be much higher than the average generation rate of the Key-Blocks, which increases the throughput of system. Therefore, leaders will generate Micro-Blocks with unpackaged transactions to obtain corresponding transaction fees. The Micro-Block header contains a reference to the previous block, the current GMT time, the hash of its account, and the signature of the Micro-Block header. Micro-Blocks are responsible for packaging transactions, which is critical to improve Bitcoin-NG’s throughput. However, they have no contribution to consensus protocol.

2.3 Protocol of Bitcoin-NG

In Bitcoin-NG, the current local state of each node may be inconsistent due to frequent generation rate of Micro-Blocks, which brings forking. As shown in Fig. 1, when the Key-Block 1 is generated, the Micro-Blocks 1’ and 2’ may not have been received yet, which enables them to become orphan blocks. Meanwhile, transactions in these orphan blocks will not be executed. Therefore, users who detect the Micro-Blocks in the blockchain should wait for a period of network propagation until other Key-Blocks are generated on top of these Micro-Blocks (e.g., in Bitcoin, users need to wait for 6 blocks (approximately 60 minutes) to ensure that the blocks are executed).

To motivate miners to mine honestly and ensure the security of the system, leaders in each epoch will obtain two rewards: coinbase reward for generating Key-Blocks and transaction fees for generating Micro-Blocks. Meanwhile, the transaction fees should be shared by two adjacent leaders before and after the current epoch. Specifically, 40% of these transaction fees are earned by the leader of current epoch and 60% by subsequent leaders, as illustrated in Fig. 2 for details. The reason for choosing this distribution is explained in Section 3.

3 Incentive Analysis of Bitcoin-NG

3.1 Original Incentive Analysis

Original incentive analysis of Bitcoin-NG contains two types of malicious attack strategies: Transaction Inclusion Attack and Longest Chain Extension Attack. We first define following parameters in Bitcoin-NG:

( \alpha ): The total mining power of the adversary pool.

( \gamma ): The ratio of other miners that choose to mine on the adversary’s branch when forking competition occurs.

( r_{\text{leader}} ): The ratio of transaction fees earned by the leader of current epoch.

Transaction Inclusion Attack. When adversaries generate a Key-Block and a series of Micro-Blocks with transactions, they may potentially increase their revenue of the transaction fees through selfish mining. To do so, adversaries first generate (reserve) Micro-Blocks with transactions, but do not publish them. Meanwhile, they try to mine on top of these unpublished Micro-Blocks, while other honest miners have to mine on published Key-Blocks. If adversaries find a subsequent Key-Block, they will publish it at once, which brings them 100% of the transaction fees (with probability ( \alpha )). However, if other honest miners find a subsequent Key-Block and publish Micro-Blocks with these secret transactions, adversaries will try to mine on top of these Micro-Blocks, which brings them only ( 100% – r_{\text{leader}} ) of the transaction fees (with probability ( (1 – \alpha) \cdot \alpha )). Fig. 3 shows the transaction inclusion attack in Bitcoin-NG. In order to urge all miners to adopt honest mining strategy, the revenue through transaction inclusion attack should be smaller than the revenue through honest mining. Therefore, we can get equation 1.

[ \alpha \cdot 100% + (1 – \alpha) \cdot \alpha \cdot (100% – r_{\text{leader}}) < r_{\text{leader}} ]

Fig. 3. Transaction inclusion attack in Bitcoin-NG

According to equation 1, we can get $r_{leader} > 1 – \frac{1 – \alpha}{1 + \alpha – \alpha^2}$. We assume that adversary owns the mining power $\alpha < \frac{1}{4}$, we can get $r_{leader} > 37%$.

Lonest Chain Extension Attack. In order to improve revenue, the adversary can avoid Micro-Blocks, and directly mine on the previous Key-Block to generate a new valid Key-Block. Then he would generate Micro-Blocks with transactions. Once he finds a subsequent Key-Block, he will obtain 100% of the transaction fees (with probability $\alpha^2$). Otherwise, he obtains $r_{leader}$ of the transaction fees (with probability $\alpha \cdot (1 – \alpha)$). Fig. 4 shows the details of longest chain extension attack in Bitcoin-NG. The revenue that adversaries can obtain by longest chain extension attack must be smaller than the revenue obtained by honest mining. Therefore, we can derive equation 2.

$$\frac{\text{Win} \cdot 100%}{\alpha^2 \cdot 100%} + \frac{\text{Win} \cdot r_{leader}}{\alpha \cdot (1 – \alpha) \cdot r_{leader}} < \alpha \cdot (1 – r_{leader})$$

(2)

According to equation 2, we can get $r_{leader} < \frac{1 – \alpha}{2 – \alpha}$. Assume that adversary owns the mining power $\alpha < \frac{1}{4}$, we can get $r_{leader} < 43%$.

3.2 Modified Incentive Analysis

Modified Transaction Inclusion Attack. Yin [27] improves Bitcoin-NG Transaction Inclusion Attack in relevant research, which modifies the transaction inclusion attack. More specifically, when adversaries find a valid Key-Blocks on top of these secret Micro-Blocks, they will publish these secret Micro-Blocks with transactions and the new valid Key-Block, which brings them 100% of transaction fees (with probability $\alpha$). However, once honest miners find a valid Key-Block, they will publish it and Micro-Blocks with transactions. Meanwhile, adversaries will try to mine on top of these Micro-Blocks, which bring them 100% – $r_{leader}$ of transaction fees (with probability $(1 – \alpha) \cdot \alpha$). Modified transaction inclusion attack in Bitcoin-NG is shown in Fig. 5. Therefore, we can derive equation 3.

According to equation 3, we can get $r_{leader} > \frac{\alpha}{1 + \alpha}$. Assume that adversaries own the mining power $\alpha < \frac{1}{4}$, we can get $r_{leader} > 25%$.

To sum up, we can get $\frac{\alpha}{1 + \alpha} < r_{leader} < \frac{1 – \alpha}{2 – \alpha}$. Assume that adversaries own the mining power $\alpha < \frac{1}{4}$, we can get 20% < $r_{leader}$ < 43%. Therefore, the incentive parameter $r_{leader} = 40%$ selected in Bitcoin-NG meets the security requirements.

[ \alpha \cdot 100% \quad + \quad (1 – \alpha) \cdot \alpha \cdot (100% – r_{leader}) \quad < \quad r_{leader} + \alpha \cdot (1 – r_{leader}) ]

\begin{figure}[h] \centering \includegraphics[width=\textwidth]{figure5.png} \caption{Modified transaction inclusion attack in Bitcoin-NG} \end{figure}

3.3 Defects of The Traditional Incentive Analysis

The above incentive analysis based on Bitcoin-NG only includes the limited mining strategies, while ignoring more stubborn mining strategies. For example, in the first stage, the adversary fails to package the whale transaction, but he may reverse the longest chain by generating new Key-Blocks, which could bring them more reward. On the basis of Bitcoin-NG’s original incentive analysis above, we propose a novel mining strategy named Greedy-Mine and model it through Markov Decision Process (MDP) to analyze the competition of honest miners and adversaries (in section 4). We further calculate the extra reward of adversaries, which demonstrates that Bitcoin-NG mining is not incentive compatible (in section 5).

4 Markov Model of Greedy-Mine Strategy

4.1 Assumption

To simplify our analysis, we make some reasonable assumptions. Our assumptions are similar to those of other selfish mining attacks, such as selfish mining [32], stubborn mining [33], bribery semi-selfish mining and bribery stubborn mining [34].

  1. We normalize the total mining power of the system to 1. The normalized mining power of adversary is a value greater than 0 but less than 1.
  2. Miners are profit-driven. Honest miners can adopt the optimal mining strategy they consider to increase their profits, but will not launch mining attacks. This is reasonable because miners are honest but selfish. When the blockchain forks and the lengths of each branch are equal, miners could choose any branch.
  3. There are no unintentional forks in the Bitcoin system. This assumption is rational because the probability of unintentional forks occurring in the Bitcoin system can be negligible, approximately 0.41% [35].
  4. Block rewards can be ignored, compared with whale transaction. In our analysis, miner’s rewards are expected as well as normalized.

4.2 Greedy-Mine Strategy

For the sake of simplicity and generality, we assume that mining power is divided into two categories: one is the minority mining pool following the Greedy-Mine strategy, and the other is the majority pool following the honest mining strategy. Furthermore, it is not significant whether honest miners are a single pool, a series of pools or individual miners.

The key intuition of Greedy-Mine strategy is that the greedy pool tries to compete with honest pool for the longest legal chain, which wastes the mining power of honest pool on the non-longest legal chain. Therefore, the greedy pool obtains all the transaction fees in each epoch. Therefore, adversaries have the motivation to exploit Greedy-Mine strategy to try to obtain excess returns.

When greedy pool finds a new Key-Block, he will publish it selectively, which makes greedy branch the longest legal chain and brings greedy pool all the transaction fees in each epoch. Generally, once a whale transaction occurs (whale transaction refers to the transaction involving very high transaction fees, and block rewards can be ignored, compared with whale transaction), greedy pool will try to generate Key-Blocks and Micro-Blocks with whale transactions, even if the whale transactions have been packaged into Micro-Blocks by other honest pool. Greedy pool will attempt to make their branch the longest legal chain, which wastes the mining power of honest pool. In this case, adversaries can obtain disproportionate reward under Greedy-Mine strategy.

With the above intuition, we propose Greedy-Mine strategy, which is driven by the mining events of greedy pool or honest pool. The decision of greedy pool is determined by the specific state of whale transactions. We divide ( \text{state}_t ) into three categories: ( \text{state}_t = 0 ) refers that whale transaction has not been packaged, ( \text{state}_t = 1 ) refers that whale transaction has been packaged by greedy pool and ( \text{state}_t = 2 ) refers that whale transaction has been packaged by honest pool. The initialization of Greedy-Mine is described in the following algorithm 1.

Algorithm 1. Initialization of Greedy-Mine

1: ( \text{On Init} ) 2: ( \text{state}_t = 0 ) 3: ( \text{length(honest branch)} = 0 ) 4: ( \text{length(adversarial branch)} = 0 ) 5: ( \text{Mine at the head of longest branch.} )

Fig. 6. Initialization of Greedy-Mine

When greedy pool finds a Key-Block and whale transactions have not been packaged at this time, he will publish the Key-Block with whale transactions, which brings the ( \text{state}_t ) to 1 and adds one to the length of adversarial branch. If whale transactions have been packaged by greedy pool and the length of adversarial branch is not shorter than the length of honest branch, he will publish the Key-Block and add one to the length of greedy branch. If whale transactions have been packaged by honest pool and the length of honest branch is longer than adversarial branch, greedy pool will generate the Key-Block and add one to the length of the branch. The specific strategy of greedy pool is described in the following algorithm 2.

Algorithm 2. Greedy-Mine strategy when greedy pool finds a Key-block

1:
2: ( \Delta = \text{length(adversarial branch)} – \text{length(honest branch)} ) 3:
4: ( \text{if } \text{state}{tx} = 0 \text{ then} ) 5: ( \text{state}{tx} = 1 ) 6:
7: ( \text{else if } \text{state}_{tx} \neq 0 \text{ then} ) 8: ( \text{if } \Delta < 0 \text{ then} ) 9: ( \text{length(adversarial branch)} + 1 ) 10:
11: ( \text{else if } \Delta > 0 \text{ then} ) 12: ( \text{Competition ends} ) 13:
14: ( \text{else if } \text{honest pool appends adversarial branch} \text{ then} )

Fig. 7. Greedy-Mine strategy when greedy pool finds a Key-block

When honest pool finds a Key-Block, he will continue to mine with honest strategy. If whale transactions have not been packaged, he will generate the Key-Block with whale transactions and set ( \text{state}_{tx} = 1 ). If whale transactions have been packaged, the strategy of honest pool is determined by the system state. If the length of honest branch is longer than greedy branch, honest pool will publish a Key-Block on honest branch and add one to the length of the honest branch. If the length of honest branch is equal to the length of the adversarial branch, the results of competition is determined by the choice of honest pool. Specifically, if honest pool appends honest branch, the length of honest branch adds one. Otherwise, the length of adversarial branch adds one. If the length of adversarial is longer than the length of honest branch, competition ends and adversarial pool gets all whale transaction fees. The specific strategy of honest pool is described in the following algorithm 3.

Algorithm 3. Greedy-Mine strategy when honest pool finds a Key-block

1:
2: ( \Delta = \text{length(adversarial branch)} – \text{length(honest branch)} ) 3:
4: ( \text{if } \text{state}{tx} = 0 \text{ then} ) 5: ( \text{state}{tx} = 2 ) 6:
7: ( \text{else if } \text{state}_{tx} \neq 0 \text{ then} ) 8: ( \text{if } \Delta < 0 \text{ then} ) 9: ( \text{length(honest branch)} + 1 ) 10:
11: ( \text{else if } \Delta > 0 \text{ then} ) 12: ( \text{Competition ends} ) 13:
14: ( \text{else if } \text{honest pool appends adversarial branch} \text{ then} )

Useful information for enthusiasts:

Contact me via Telegram: @ExploitDarlenePRO