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 IV. DAG-ORIENTED SOLUTIONS In this section, we briefly review a few DAG-PROTOCOLs potentially vulnerable to the incentive attacks we are investigating. Inclusive Protocol. Lewenberg et al. [26] proposed a new way to structure the chain that can operate at much faster rates than Bitcoin. The authors utilize the DAG to form blocks in a structure called the blockDAG. This structure is created by allowing blocks to reference multiple previous blocks, enabling less strict transaction inclusion rules that can potentially store conflicting transactions in parallel blocks due to allowing λ < τ . This means that the system can process larger blocks faster than is possible to gossip within the bounds of τ , allowing for an increase in transaction throughput. The authors propose the protocol as a building block for other DAG-oriented protocols, and they claim that they reduce the advantage of highly connected miners in single-chain protocols since even stale blocks (of a single-chain) are included. Further, the authors present the key concept of randomly selecting transactions (i.e., RTS) to avoid collisions; however, according to their definition, the random selection does not necessarily equals to uniformly random selection. The authors theoretically analyze this assumption by modeling the protocol and its transaction selection as a game, in which rational miners opt to avoid collisions. According to the authors, the game’s outcome is a sequential equilibrium, where the growing fraction of greedy miners causes a decrease in their profits, which should make such a strategy less attractive (we show this phenomenon in Fig. 6). However, the authors do not assume that the miners can create a mining pool, in which they can achieve significantly higher profits than honest miners (we demonstrate it in Fig. 7a). PHANTOM. The PHANTOM protocol [44] is a generalization of the NC’s longest-chain protocol. While in NC each block contains a hash of the previous block in the chain it extends, PHANTOM organizes blocks in a DAG. As a result, each block may contain multiple hash references to predecessors, like in Inclusive [26] that is the bases for PHANTOM. The key contribution of PHANTOM is that it totally orders all blocks by solving the maximum k-cluster SubDAG problem, which utilizes the concept of the main chain and the distance from it. Unlike NC which discards the blocks out of the main chain (i.e., orphan blocks), PHANTOM includes these blocks in a DAG, except for the attacker-created blocks that would be weakly connected to DAG. PHANTOM uses the RTS strategy proposed by the (partially overlapping) authors of the Inclusive protocol. The incentive scheme of PHANTOM revolves around rewarding all miners who include a transaction within a new block A, while assuming that transactions in the parallel blocks are unique and due to a DAG will not be discarded as in single-chain blockchains. If there are some duplicate transactions, PHANTOM rewards them only once – in the first block that includes them, which is evaluated after establishing the total ordering. However, such an incentive scheme must be constructed with care, as sidechain blocks might also be the result of an attack. Therefore, the reward a miner receives for publishing A is indirectly proportional to the discretized delay at which A was referenced by the main chain. For this reason, the protocol defines a measure of the delay in publishing A w.r.t. the main chain, called the gap parameter c. The value by which the reward is “decayed” is determined by the discount function γ, where γ(c(A)) ∈ [0, 1] and γ is weakly decreasing.[6] Finally, the miner is rewarded for including transactions in A using the payoff function. In detail, the miner gets rewarded for all nonduplicate transactions contained in A, and after γ was applied to the respective transaction fees. GHOSTDAG. PHANTOM is considered impractical for efficient use [44], because it requires the solution of an NPhard problem (the maximum k-cluster SubDAG problem). Therefore, the authors of PHANTOM have developed a greedy (heuristic) algorithm to find block clusters, obtaining the GHOSTDAG protocol. This protocol uses greedy ordering of the DAG, which has practical advantages. Kaspa. The RTS strategy is utilized even in the already running blockchain Kaspa [42], which is the implementation of the GHOSTDAG protocol. Kaspa selects transactions using a variant of the RTS strategy, in which a small fraction of a block is dedicated to prioritized transactions with higher fees and remaining part of a block serves for transactions selected uniformly at random. We argue that even this approach is vulnerable to our incentive attacks since the part of the block relying on uniformly random selection cannot be enforced/verified, and thus miners might still prioritize transactions with higher fees, which can consequently result in throughput problems and incentive attacks. Nevertheless, the current Kaspa mainnet is not saturated, and its blocks usually contain only 1 to 5 transactions,[7] not fully utilizing the concept of DAG for increased throughput. Prism. Prism [6] is a protocol that aims to achieve a total ordering of transactions with consistency and liveness guarantees while achieving high throughput and low latency. Prism differs from traditional single-chain blockchains since it involves a few parallel chains rather than a single chain. It decouples transaction confirmation, validation, and proposal, whereas these processes are traditionally tightly coupled. Prism replaces traditional blocks with (1) transaction blocks (i.e., blocks that contain transactions), (2) voter blocks (i.e., blocks that vote for proposer blocks), and (3) proposer blocks (i.e., blocks that reference transaction blocks). The authors of Prism recognize that blocks mined in parallel chains might contain duplicate transactions. To cope with this problem, they propose to randomly divide unprocessed transactions of the local mempool into multiple queues and then create blocks using transactions only from one randomly selected queue, which is a variant of RTS strategy and thus enables incentive attacks based on greedy strategy. However, the authors do not provide any analysis related to such incentive attacks. 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). This paper is available on arxiv under CC BY 4.0 DEED license. I.e., later inclusion of the side-chain block imposes lower reward.


https://explorer.kaspa.org/ 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 IV. DAG-ORIENTED SOLUTIONS In this section, we briefly review a few DAG-PROTOCOLs potentially vulnerable to the incentive attacks we are investigating. Inclusive Protocol. Lewenberg et al. [26] proposed a new way to structure the chain that can operate at much faster rates than Bitcoin. The authors utilize the DAG to form blocks in a structure called the blockDAG . This structure is created by allowing blocks to reference multiple previous blocks, enabling less strict transaction inclusion rules that can potentially store conflicting transactions in parallel blocks due to allowing λ < τ . This means that the system can process larger blocks faster than is possible to gossip within the bounds of τ , allowing for an increase in transaction throughput. The authors propose the protocol as a building block for other DAG-oriented protocols, and they claim that they reduce the advantage of highly connected miners in single-chain protocols since even stale blocks (of a single-chain) are included. Inclusive Protocol. blockDAG Further, the authors present the key concept of randomly selecting transactions (i.e., RTS) to avoid collisions; however, according to their definition, the random selection does not necessarily equals to uniformly random selection. The authors theoretically analyze this assumption by modeling the protocol and its transaction selection as a game, in which rational miners opt to avoid collisions. According to the authors, the game’s outcome is a sequential equilibrium, where the growing fraction of greedy miners causes a decrease in their profits, which should make such a strategy less attractive (we show this phenomenon in Fig. 6). However, the authors do not assume that the miners can create a mining pool, in which they can achieve significantly higher profits than honest miners (we demonstrate it in Fig. 7a). randomly selecting PHANTOM . The PHANTOM protocol [44] is a generalization of the NC’s longest-chain protocol. While in NC each block contains a hash of the previous block in the chain it extends, PHANTOM organizes blocks in a DAG. As a result, each block may contain multiple hash references to predecessors, like in Inclusive [26] that is the bases for PHANTOM. The key contribution of PHANTOM is that it totally orders all blocks by solving the maximum k-cluster SubDAG problem , which utilizes the concept of the main chain and the distance from it. Unlike NC which discards the blocks out of the main chain (i.e., orphan blocks), PHANTOM includes these blocks in a DAG, except for the attacker-created blocks that would be weakly connected to DAG. PHANTOM the maximum k-cluster SubDAG problem PHANTOM uses the RTS strategy proposed by the (partially overlapping) authors of the Inclusive protocol. The incentive scheme of PHANTOM revolves around rewarding all miners who include a transaction within a new block A, while assuming that transactions in the parallel blocks are unique and due to a DAG will not be discarded as in single-chain blockchains. If there are some duplicate transactions, PHANTOM rewards them only once – in the first block that includes them, which is evaluated after establishing the total ordering. However, such an incentive scheme must be constructed with care, as sidechain blocks might also be the result of an attack. Therefore, the reward a miner receives for publishing A is indirectly proportional to the discretized delay at which A was referenced by the main chain. For this reason, the protocol defines a measure of the delay in publishing A w.r.t. the main chain, called the gap parameter c . The value by which the reward is “decayed” is determined by the discount function γ, where γ(c(A)) ∈ [0, 1] and γ is weakly decreasing.[6] Finally, the miner is rewarded for including transactions in A using the payoff function. In detail, the miner gets rewarded for all nonduplicate transactions contained in A , and after γ was applied to the respective transaction fees. gap parameter c A A GHOSTDAG . PHANTOM is considered impractical for efficient use [44], because it requires the solution of an NPhard problem (the maximum k -cluster SubDAG problem). Therefore, the authors of PHANTOM have developed a greedy (heuristic) algorithm to find block clusters, obtaining the GHOSTDAG protocol. This protocol uses greedy ordering of the DAG, which has practical advantages. GHOSTDAG k Kaspa . The RTS strategy is utilized even in the already running blockchain Kaspa [42], which is the implementation of the GHOSTDAG protocol. Kaspa selects transactions using a variant of the RTS strategy, in which a small fraction of a block is dedicated to prioritized transactions with higher fees and remaining part of a block serves for transactions selected uniformly at random. We argue that even this approach is vulnerable to our incentive attacks since the part of the block relying on uniformly random selection cannot be enforced/verified, and thus miners might still prioritize transactions with higher fees, which can consequently result in throughput problems and incentive attacks. Nevertheless, the current Kaspa mainnet is not saturated, and its blocks usually contain only 1 to 5 transactions,[7] not fully utilizing the concept of DAG for increased throughput. Kaspa Prism . Prism [6] is a protocol that aims to achieve a total ordering of transactions with consistency and liveness guarantees while achieving high throughput and low latency. Prism differs from traditional single-chain blockchains since it involves a few parallel chains rather than a single chain. It decouples transaction confirmation, validation, and proposal, whereas these processes are traditionally tightly coupled. Prism replaces traditional blocks with (1) transaction blocks (i.e., blocks that contain transactions), (2) voter blocks (i.e., blocks that vote for proposer blocks), and (3) proposer blocks (i.e., blocks that reference transaction blocks). Prism The authors of Prism recognize that blocks mined in parallel chains might contain duplicate transactions. To cope with this problem, they propose to randomly divide unprocessed transactions of the local mempool into multiple queues and then create blocks using transactions only from one randomly selected queue, which is a variant of RTS strategy and thus enables incentive attacks based on greedy strategy. However, the authors do not provide any analysis related to such incentive attacks. 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). 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 I.e., later inclusion of the side-chain block imposes lower reward. https://explorer.kaspa.org/ I.e., later inclusion of the side-chain block imposes lower reward. I.e., later inclusion of the side-chain block imposes lower reward. https://explorer.kaspa.org/ https://explorer.kaspa.org/

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

DAG-Oriented Solutions and the Risk of Greedy Mining

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Comparative Analysis of Crypto API Misuses Across Programming Languages

7 Consensus Mechanisms Developers Must Know to BUIDL for Web3

BFT Consensus: Will Your Car Full of Passengers Turn Right, Left, or Fly Over a Cliff?

Consensus Protocol in Blockchain

ConsensusPedia: An Encyclopedia of 30+ Consensus Algorithms

Could Block Proposals Be Fair and Efficient Without Proof of Work (PoW)?

A Comparative Analysis of Crypto API Misuses Across Programming Languages

7 Consensus Mechanisms Developers Must Know to BUIDL for Web3

BFT Consensus: Will Your Car Full of Passengers Turn Right, Left, or Fly Over a Cliff?

Consensus Protocol in Blockchain

ConsensusPedia: An Encyclopedia of 30+ Consensus Algorithms

Could Block Proposals Be Fair and Efficient Without Proof of Work (PoW)?

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps