How Greedy Miners Are Breaking DAG Blockchains

Authors: (1) Martin Peresıni, Brno University of Technology, Faculty of Information Technology (iperesini@fit.vut.cz); (2) Ivan Homoliak, Brno University of Technology, Faculty of Information Technology (ihomoliak@fit.vut); (3) Federico Matteo Bencic, University of Zagreb, Faculty of Electrical Engineering and Computing (federico-matteo.bencic@fer.hr); (4) Martin Hruby, Brno University of Technology, Faculty of Information Technology (hruby@fit.vut.cz); (5) Kamil Malinka, Brno University of Technology, Faculty of Information Technology (malinka@fit.vut). Table of Links Abstract and I. Introduction II. Background III. Problem Definition IV. DAG-Oriented Solutions V. Game Theoretical Analysis VI. Simulation Model VII. Evaluation VIII. Countermeasures IX. Discussion and Future Work X. Related Work XI. Conclusion and References Abstract—Several blockchain consensus protocols proposed to use of Directed Acyclic Graphs (DAGs) to solve the limited processing throughput of traditional single-chain Proof-of-Work (PoW) blockchains. Many such protocols utilize a random transaction selection (RTS) strategy (e.g., PHANTOM, GHOSTDAG, SPECTRE, Inclusive, and Prism) to avoid transaction duplicates across parallel blocks in DAG and thus maximize the network throughput. However, previous research has not rigorously examined incentive-oriented greedy behaviors when transaction selection deviates from the protocol. In this work, we first perform a generic game-theoretic analysis abstracting several DAG-based blockchain protocols that use the RTS strategy, and we prove that such a strategy does not constitute a Nash equilibrium, which is contradictory to the proof in the Inclusive paper. Next, we develop a blockchain simulator that extends existing opensource tools to support multiple chains and explore incentivebased deviations from the protocol. We perform simulations with ten miners to confirm our conclusion from the game-theoretic analysis. The simulations confirm that greedy actors who do not follow the RTS strategy can profit more than honest miners and harm the processing throughput of the protocol because duplicate transactions are included in more than one block of different chains. We show that this effect is indirectly proportional to the network propagation delay. Finally, we show that greedy miners are incentivized to form a shared mining pool to increase their profits. This undermines the decentralization and degrades the design of the protocols in question. To further support our claims, we execute more complex experiments on a realistic Bitcoin-like network with more than 7000 node I. INTRODUCTION 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[**2] 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 [26] – whose game theoretic analysis (and missing assumption about creating a mining pool) we contradict in this work. In contrast, Prism [6] 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. This paper is available on arxiv under CC BY 4.0 DEED license. Note that RTS involves a certain randomness in transaction selection but does not necessarily equals to uniformly random transaction selection (to be in line with the works utilizing Inclusive [26], such as PHANTOM, GHOSTDAG [44], SPECTRE [43], as well as the implementation of GHOSTDAG called Kaspa [42]). Greedy actors deviate from the protocol to increase their profits. Authors: (1) Martin Peresıni, Brno University of Technology, Faculty of Information Technology (iperesini@fit.vut.cz); (2) Ivan Homoliak, Brno University of Technology, Faculty of Information Technology (ihomoliak@fit.vut); (3) Federico Matteo Bencic, University of Zagreb, Faculty of Electrical Engineering and Computing (federico-matteo.bencic@fer.hr); (4) Martin Hruby, Brno University of Technology, Faculty of Information Technology (hruby@fit.vut.cz); (5) Kamil Malinka, Brno University of Technology, Faculty of Information Technology (malinka@fit.vut). Authors: Authors: (1) Martin Peresıni, Brno University of Technology, Faculty of Information Technology (iperesini@fit.vut.cz); (2) Ivan Homoliak, Brno University of Technology, Faculty of Information Technology (ihomoliak@fit.vut); (3) Federico Matteo Bencic, University of Zagreb, Faculty of Electrical Engineering and Computing (federico-matteo.bencic@fer.hr); (4) Martin Hruby, Brno University of Technology, Faculty of Information Technology (hruby@fit.vut.cz); (5) Kamil Malinka, Brno University of Technology, Faculty of Information Technology (malinka@fit.vut). Table of Links Abstract and I. Introduction Abstract and I. Introduction II. Background II. Background III. Problem Definition III. Problem Definition IV. DAG-Oriented Solutions IV. DAG-Oriented Solutions V. Game Theoretical Analysis V. Game Theoretical Analysis VI. Simulation Model VI. Simulation Model VII. Evaluation VII. Evaluation VIII. Countermeasures VIII. Countermeasures IX. Discussion and Future Work IX. Discussion and Future Work X. Related Work X. Related Work XI. Conclusion and References XI. Conclusion and References Abstract—Several blockchain consensus protocols proposed to use of Directed Acyclic Graphs (DAGs) to solve the limited processing throughput of traditional single-chain Proof-of-Work (PoW) blockchains. Many such protocols utilize a random transaction selection (RTS) strategy (e.g., PHANTOM, GHOSTDAG, SPECTRE, Inclusive, and Prism) to avoid transaction duplicates across parallel blocks in DAG and thus maximize the network throughput. However, previous research has not rigorously examined incentive-oriented greedy behaviors when transaction selection deviates from the protocol. In this work, we first perform a generic game-theoretic analysis abstracting several DAG-based blockchain protocols that use the RTS strategy, and we prove that such a strategy does not constitute a Nash equilibrium, which is contradictory to the proof in the Inclusive paper. Next, we develop a blockchain simulator that extends existing opensource tools to support multiple chains and explore incentivebased deviations from the protocol. We perform simulations with ten miners to confirm our conclusion from the game-theoretic analysis. The simulations confirm that greedy actors who do not follow the RTS strategy can profit more than honest miners and harm the processing throughput of the protocol because duplicate transactions are included in more than one block of different chains. We show that this effect is indirectly proportional to the network propagation delay. Finally, we show that greedy miners are incentivized to form a shared mining pool to increase their profits. This undermines the decentralization and degrades the design of the protocols in question. To further support our claims, we execute more complex experiments on a realistic Bitcoin-like network with more than 7000 node Abstract —Several blockchain consensus protocols proposed to use of Directed Acyclic Graphs (DAGs) to solve the limited processing throughput of traditional single-chain Proof-of-Work (PoW) blockchains. Many such protocols utilize a random transaction selection (RTS) strategy (e.g., PHANTOM, GHOSTDAG, SPECTRE, Inclusive, and Prism) to avoid transaction duplicates across parallel blocks in DAG and thus maximize the network throughput. However, previous research has not rigorously examined incentive-oriented greedy behaviors when transaction selection deviates from the protocol. In this work, we first perform a generic game-theoretic analysis abstracting several DAG-based blockchain protocols that use the RTS strategy, and we prove that such a strategy does not constitute a Nash equilibrium, which is contradictory to the proof in the Inclusive paper. Next, we develop a blockchain simulator that extends existing opensource tools to support multiple chains and explore incentivebased deviations from the protocol. We perform simulations with ten miners to confirm our conclusion from the game-theoretic analysis. The simulations confirm that greedy actors who do not follow the RTS strategy can profit more than honest miners and harm the processing throughput of the protocol because duplicate transactions are included in more than one block of different chains. We show that this effect is indirectly proportional to the network propagation delay. Finally, we show that greedy miners are incentivized to form a shared mining pool to increase their profits. This undermines the decentralization and degrades the design of the protocols in question. To further support our claims, we execute more complex experiments on a realistic Bitcoin-like network with more than 7000 node Abstract I. INTRODUCTION 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 soft fork orphaned 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. transaction collision In this work, we focus on the impact of **greedy[**2] 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 [26] – whose game theoretic analysis (and missing assumption about creating a mining pool) we contradict in this work. In contrast, Prism [6] 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. transaction collision Contributions . The contributions of this work are as follows: Contributions 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. 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. 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. 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 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. 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. 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. 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. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv available on arxiv Note that RTS involves a certain randomness in transaction selection but does not necessarily equals to uniformly random transaction selection (to be in line with the works utilizing Inclusive [26], such as PHANTOM, GHOSTDAG [44], SPECTRE [43], as well as the implementation of GHOSTDAG called Kaspa [42]). Note that RTS involves a certain randomness in transaction selection but does not necessarily equals to uniformly random transaction selection (to be in line with the works utilizing Inclusive [26], such as PHANTOM, GHOSTDAG [44], SPECTRE [43], as well as the implementation of GHOSTDAG called Kaspa [42]). Greedy actors deviate from the protocol to increase their profits. Greedy actors deviate from the protocol to increase their profits.