Directed Acyclic Graphs (DAGs) are an appealing design for Distributed Ledger (DL) architectures. Specifically, DAG-based DLs offer valuable benefits compared to blockchains, such as improved scalability, lightweight consensus mechanisms and lower transaction costs. However, due to the communication delays and distributed nature of the DL, some transactions may remain unapproved. Previous works have provided bounds on the expected number of unapproved transactions when the transactions selection strategy is uniform. Still, a transaction should be preferably validated by multiple nodes so as to increase the trust in the ledger. In this paper, we introduce a bound on the expected number of transactions that are approved by at most one node. For this purpose, we define a new stochastic model based on stochastic sets, which captures the evolution of DAG-based DL. The proposed model enables us to establish a quadratic bound on the drift in the number of tips. We then demonstrate that the expected volume of transactions validated by at most one node is bounded. These results indicate that the occurrence of large volume of transactions validated by at most one node happens with sufficiently low probability.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Stability of DAG-Based Distributed Ledger with Heterogeneous Delays

  • Hajer Rejeb,
  • Alexandre Reiffers-Masson

摘要

Directed Acyclic Graphs (DAGs) are an appealing design for Distributed Ledger (DL) architectures. Specifically, DAG-based DLs offer valuable benefits compared to blockchains, such as improved scalability, lightweight consensus mechanisms and lower transaction costs. However, due to the communication delays and distributed nature of the DL, some transactions may remain unapproved. Previous works have provided bounds on the expected number of unapproved transactions when the transactions selection strategy is uniform. Still, a transaction should be preferably validated by multiple nodes so as to increase the trust in the ledger. In this paper, we introduce a bound on the expected number of transactions that are approved by at most one node. For this purpose, we define a new stochastic model based on stochastic sets, which captures the evolution of DAG-based DL. The proposed model enables us to establish a quadratic bound on the drift in the number of tips. We then demonstrate that the expected volume of transactions validated by at most one node is bounded. These results indicate that the occurrence of large volume of transactions validated by at most one node happens with sufficiently low probability.