Comparative Study of DAG Protocols and Their Impact on Blockchain Performance

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

X. RELATED WORK

DAG-Based Consensus Protocols The benefits of blockchain protocols come with certain trade-offs when balancing decentralization, scalability, and security. We have already mentioned the bottleneck in Nakamoto’s consensus protocol, and therefore, alternative approaches are emerging, such as DAG-based protocols. Beside DAG-based protocols, also 2nd layer [38], [37], [21] and sharding designs [29], [51], [23], addressing the same problems, had emerged. However, in the current work context, we solely focus on DAG-based designs. Wang et al. [48] performed a detailed systematic overview of DAG-designs. They described six categories containing more than thirty DAG-based blockchain systems classified based on their characteristics and principles. They extend the commonly used classification based on the type of ledgers [47]. GHOST [45], Inclusive Blockchain [26], Conflux [27], Haootia [47], and Byteball [3] represent DAG with the main chain. Hashgraph [24] and Nano [25] represent ledgers with parallel chains.

Nevertheless, out of these categories, DAGs with the main chain are related to our research, such as Inclusive [26], SPECTRE [43], PHANTOM and GHOSTDAG [44]. We refer the reader to Sec. IV for details about these protocols.

Performance Analysis of DAGs While many papers deal with the security and performance analysis of mentioned protocols, they consider neither mining strategy nor features of various incentive schemes. Park et al. [35] address the performance of DAG-based blockchains and relate it to the optimization of profit. They show that the average number of parents n can influence the transaction processing time. As a result, they propose a competitive-based transaction process system using a dynamic fee policy.

Birmpas et al. [8] propose a new general framework that captures ledger growth for a large class of DAG-based implementations to demonstrate the structural limits of DAGbased protocols. Even with honest miner behavior, fairness, and efficiency of the ledger can be affected by different connectivity levels.

One of the key technical problems of DAG-based protocols is identifying honest blocks. Wang proposes a MaxCord [50], a framework using a different approach for honest block identification problems using graph theory. Based on the definition of the disparity measurement between blocks, they convert the problem into a maximum k-independent set problem. Cao et al. [10] compared the performance of three consensus mechanisms: Bitcoin (PoW), Nxt (PoS), and Tangle (DAGPoW) in terms of parameters such as average time to generate a new block or confirmation delay and failure probability, showing how these mechanisms can affect the state of network resources or network load condition.

Sycomore [2] and its extension Sycomore++ [12] is another DAG-oriented consensus protocol that utilizes DAGs to increase Nakamoto consensus throughput. The protocol proposes that the chain responds to the dynamically increased number of transactions and splits them into multiple chains, thus creating DAG structure. When the number of transactions decreases (utilization of blocks is reduced), the branches can be rejoined back into a single chain. Transactions are evenly partitioned based on the prefix of their hash, and they are randomly inserted into their corresponding chain (branch). The protocol does not directly suffer from our proposed attacks, although it might suffer from different problems related to double spending of transactions mined in parallel, which is however common for all DAG-oriented protocols.