How Greedy Miners Are Breaking DAG Blockchains

Blockchains have become popular due to several interesting properties they offer, such as decentralization, immutability, availability, etc. Thanks to these properties, blockchains have been adopted in various fields, such as finance, supply chains, identity management, the Internet of Things, file systems, etc.
Nonetheless, blockchains inherently suffer from the processing throughput bottleneck, as consensus must be reached for each block within the chain. One approach to solve this problem is to increase the block creation rate. However, such an approach has drawbacks. If blocks are not propagated through the network before a new block is created, a soft fork might occur, in which two concurrent blocks reference the same parent block. A soft fork is resolved in a short time by a fork-choice rule, and thus only one block is eventually accepted as valid. All transactions in an orphaned (a.k.a., stale) block are discarded. As a result, consensus nodes that

created orphaned blocks wasted their resources and did not get rewarded.

As a response to the above issue, several proposals (e.g., Inclusive [26], PHANTOM [44], GHOSTDAG [44], SPECTRE [43]) have substituted a single chaining data structure for (unstructured) Directed Acyclic Graphs (DAGs) (see Fig. 1), while another proposal in this direction employed structured DAG (i.e., Prism [6]). Such a structure can maintain multiple interconnected chains and thus theoretically increase processing throughput. The assumption of concerned DAG-oriented solutions is to abandon transaction selection purely based on the highest fees since this approach intuitively increases the probability that the same transaction is included in more than one block (hereafter transaction collision). Instead, these approaches use the random transaction selection (i.e., RTS)[1] strategy as part of the consensus protocol to avoid transaction collisions. Although the consequences of deviating from such a strategy might seem intuitive, no one has yet thoroughly analyzed the performance and robustness of concerned DAG-oriented approaches within an empirical study investigating incentive attacks on transaction selection.

In this work, we focus on the impact of **greedy actors in several DAG-oriented designs of consensus protocols. In particular, we study the situation where an attacker (or attackers) deviates from the protocol by not following the RTS strategy that is assumed by a few DAG-oriented approaches [26], [44], [44], [43], [6]. Out of these approaches, PHANTOM [44], GHOSTDAG, [44], and SPECTRE [43] utilize RTS that was introduced in Inclusive  – whose game theoretic analysis (and missing assumption about creating a mining pool) we contradict in this work. In contrast, Prism does not provide any incentive-oriented analysis and thus did not show that it is resistant to any incentive attacks based on transaction selection. Nevertheless, both lines of works employ RTS and thus enable us to abstract their details and focus on modeling and analysis of this aspect.

We make a hypothesis stating that the attacker deviating from RTS strategy might have two significant consequences. First, such an attacker can earn greater rewards as compared to honest participants. Second, such an attacker harms transaction throughput, as transaction collision is increased. We verify and prove our hypothesis in a game theoretical analysis and show that RTS does not constitute Nash equilibrium. Said in evolutionary terminology, a population of miners following the protocols in question is not immune against the attacker (mutant). Next, we substantiate conclusions from game theoretical analysis by a few simulation experiments, where we focus on an abstracted DAG-PROTOCOL, inspired by existing designs.

Contributions. The contributions of this work are as follows:

We hypothesize that not following the RTS strategy in concerned DAG-based protocols negatively affects the relative profit of honest miners and the effective throughput of the network.
The hypothesis is validated using the game theoretic analysis focusing on all possible scenarios involving two actors: an honest miner following RTS and a greedy miner deviating from it. We conclude that the RTS strategy does not constitute Nash equilibrium.
We build a custom simulator that extends open-source simulation tools to consider multiple chains and various incentive schemes, and thus enable us to investigate properties of concerned DAG-based protocols.
We execute experiments on an abstracted DAGPROTOCOL, and they confirm that a greedy actor who selects transactions based on the highest fee has a significant advantage in making profits compared to honest miners following RTS.
Next, we demonstrate by experiments that multiple greedy actors can significantly reduce the effective transaction throughput by increasing the transaction collision rate across parallel chains of DAGs.
We show that greedy actors have a significant incentive to form a mining pool to increase their relative profits, which degrades the decentralization of the concerned DAG-oriented designs.

Sources: https://hackernoon.com/how-greedy-miners-are-breaking-dag-blockchains