Performance Analysis for DAG-based Blockchain Systems Based on the Markov Process

Abstract

As an innovative approach, Direct Acyclic Graph (DAG)-based blockchain is designed to overcome the scalability and performance limitations of traditional blockchain systems, which rely on sequential structures. The graph-based architecture of DAG allows for faster transactions and parallel processing, making it a compelling option across various industries. To enhance the analytical understanding of DAG-based blockchains, this paper begins by introducing a Markov model tailored for a DAG-based blockchain system, specifically focusing on the Tangle structure and the interaction between tips and newly arrived transactions. We then establish a continuous-time Markov process to analyze the DAG-based blockchain, demonstrating that this process is a level-dependent quasi-birth-and-death (QBD) process. We further prove that the QBD process is both irreducible and positively recurrent. Building on this foundation, we conduct a performance analysis of the DAG-based blockchain system by deriving the stationary probability vector of the QBD process. Notably, we introduce a novel method to calculate the average sojourn time of any arriving internal tip within the system using first passage times and Phase-type (PH) distributions. Finally, numerical examples are provided to validate our theoretical findings and to illustrate the influence of system parameters on the performance metrics.

An erratum to this article is available online at https://doi.org/10.1007/s11518-025-5676-6.

An erratum to this article is available online at https://doi.org/10.1007/s11518-025-5676-6.

Keywords

Blockchain / direct acyclic graph (DAG) / QBD process / performance analysis / sojourn time

References

[1] AlshaikhliM, ElfoulyT, ElharroussO, MohamedA, OttakathN. Evolution of Internet of Things from Blockchain to IOTA: A survey. IEEE Access, 2022, 10: 844-866

[2] AttiasV, BramasQ. How to choose its parents in the Tangle. International Conference on Networked Systems, 2019June 19–21, 2019

[3] AttiasV, VigneriL, DimitrovV. Implementation study of two verifiable delay functions. International Conference on Blockchain Economics, Security and Protocols, 2020October 25–27, 2020

[4] AttiasV, VigneriL, DimitrovV. Preventing denial of service attacks in IoT networks through verifiable delay functions. GLOBECOM 2020-2020 IEEE Global Communications Conference, 2020Virtual, Decemeber 7–11, 2020

[5] BenčićF M, ŽarkoI P. Distributed ledger technology: Blockchain compared to directed acyclic graph. The IEEE 38th International Conference on Distributed Computing Systems, 2018July 2–5, 2018

[6] CaoB, HuangS, FengD, ZhangL, ZhangS, PengM. Impact of network load on direct acyclic graph based Blockchain for Internet of Things. International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC), 2019October 17–19, 2019

[7] ChenY, GuoY, BieR. Tangless: Optimizing cost and transaction rate in IOTA by using Lyapunov optimization theory. 2022 18th International Conference on Mobility, Sensing and Networking (MSN), 2022December 14–16, 2022

[8] ChenY, GuoY, ChenJ, BieR. Addressing the Tangle vulnerability: A preventive strategy for IOTA by using large deviation theory. GLOBECOM 2022-2022 IEEE Global Communications Conference, 2022December 4–8, 2022

[9] ChenZ, ChenX, LiY. Performance and security analysis of distributed ledger under the internet of things environments with network instability. IEEE Internet ofThings Journal, 2023, 10(5): 4213-4225

[10] Choi S M, Park J, Nguyen Q, Cronje A (2018). Fantom: A scalable framework for asynchronous distributed systems. arXiv preprint. arXiv:1810.10360: 1–37.

[11] ChoiT M. Financing product development projects in the Blockchain era: Initial coin offerings versus traditional bank loans. IEEE Transactions on Engineering Management, 2020, 69(6): 3184-3196

[12] ContiM, KumarG, NerurkarP, SahaR, VigneriL. A survey on security challenges and solutions in the IOTA. Journal of Network and Computer Applications, 2022, 203103383

[13] CullenA, FerraroP, KingC, ShortenR. Distributed ledger technology for smart mobility: Variable delay models. 2019 IEEE 58th Conference on Decision and Control (CDC), 2019December 11–13, 2019

[14] CullenA, FerraroP, KingC, ShortenR. On the resilience of DAG-based distributed ledgers in IoT applications. IEEE Internet of Things Journal, 2020, 7(8): 7112-7122

[15] DongZ, ZhengE, ChoonY, ZomayaA Y. Dag-bench: A performance evaluation framework for dag distributed ledgers. 2019 IEEE 12th International Conference on Cloud Computing (CLOUD), 2019July 8–13, 2019

[16] FanCPerformance analysis and design of an IoT-friendly DAG-based distributed ledger system, 2019, Edmonton, Canada. Department of Electrical and Computer Engineering, University of Alberta.

[17] FanC, GhaemiS, KhazaeiH, ChenY, MusilekP. Performance analysis of the IOTA DAG-based distributed ledger. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 2021, 6(3): 1-20

[18] FanCBlockchain-based design for performant peer-to-peer energy trading systems, 2023, Edmonton, Canada. Department of Electrical and Computer Engineering, University of Alberta.

[19] FerragM A, DerdourM, MukherjeeM, DerhabA, MaglarasL, JanickeH. Blockchain technologies for the internet of things: Research issues and challenges. IEEE Internet of Things Journal, 2018, 6(2): 2188-2204

[20] FerraroP, KingC, ShortenR. Distributed ledger technology for smart cities, the sharing economy, and social compliance. IEEE Access, 2018, 6: 62728-62746

[21] FerraroP, KingC, ShortenR. On the stability of unverified transactions in a DAG-based distributed ledger. IEEE Transactions on Automatic Control, 2020, 65(9): 3772-3783

[22] FuX, WangH, ShiP. A survey of Blockchain consensus algorithms: Mechanism, design and applications. Science China Information Sciences, 2021, 64: 1-15

[23] GardnerR, ReineckeP, WolterK. Performance of tip selection schemes in DAG Blockchains. Mathematical Research for Blockchain Economy: 1st International Conference MARBLE 2019, 2020May 6–9, 2019

[24] GuoF, XiaoX, HeckerA, DustdarS. A theoretical model characterizing Tangle evolution in IOTA Blockchain network. Internet of Things Journal, 2023, 10(2): 1259-1273

[25] GorbunovaM, MasekP, KomarovM, OmetovA. Distributed ledger technology: State-of-the-art and current challenges. Computer Science and Information Systems, 2022, 19(1): 65-85

[26] HalgamugeM N. Optimization framework for best approver selection method (BASM) and best tip selection method (BTSM) for IOTA Tangle network: Blockchain-enabled next generation industrial IoT. Computer Networks, 2021, 199108418

[27] HaoY, PiaoC, ZhaoY, JiangX. Privacy preserving government data sharing based on hyper-ledger Blockchain. Advances in E-Business Engineering for Ubiquitous Computing: Proceedings of the 16th International Conference on e-Business Engineering (ICEBE 2019), 2020October 12–13, 2019

[28] KhanM, HartogF D, HuJ. Toward verification of DAG-based distributed ledger technologies through discrete-event simulation. Sensors, 2024, 2451583

[29] KumarN, Reiffers-MassonA, AmigoI, RinconS R. The effect of network delays on distributed ledgers based on directed acyclic graphs: A mathematical model. Performance Evaluation, 2024, 163102392

[30] KuśmierzB. The first glance at the simulation of the Tangle: Discrete model. IOTA Found. White Paper, 2017, 2017: 1-10

[31] KuśmierzB, StaupeP, GalA. Extracting Tangle properties in continuous time via large-scale simulations. IOTA Found. White Paper, 2018, 2018: 1-18

[32] KuśmierzB, SandersW, PenzkoferA, CaposseleA, GalA. Properties of the Tangle for uniform random and random walk tip selection. 2019 IEEE International Conference on Blockchain, 2019July 14–17, 2019

[33] LathifM R A, NasirifardP, JacobsenH A. CIDDS: A configurable and distributed DAG-based distributed ledger simulation framework. Proceedings ofthe 19th International Middleware Conference, 2018December 10–14, 2018

[34] LeMahieuCNano: A feeless distributed cryptocurrency network, 2018Nano. Accessed March 24, 2018

[35] LiQ L, CaoJ. Two types of RG-factorizations of quasi-birth-and-death processes and their applications to stochastic integral functionals. Stochastic Models, 2004, 20(3): 299-340

[36] LiQ LConstructive Computation in Stochastic Models with Applications: The RG-Factorizations, 2010, Berlin, Germany. Springer Science and Business Media.

[37] LiS, XuH, LiQ, HanQ. Simulation study on the security of consensus algorithms in DAG-based distributed ledger. Frontiers of Computer Science, 2024, 183183704

[38] LiY, CaoB, PengM, ZhangL, ZhangL, FengD, YuJ. Direct acyclic graph-based ledger for Internet of Things: Performance and security analysis. IEEE/ACM Transactions on Networking, 2020, 28(4): 1643-1656

[39] LinB Y, DziubatowskaD, MacekP, PenzkoferA, MüllerS. TangleSim: An agent-based, modular simulator for DAG-based distributed ledger technologies. 2023 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), 2023May 1–5, 2023

[40] LinIC, TsengP C, ChangY S, WengT C. IOTA data preservation implementation for industrial automation and control systems. Processes, 2023, 1172160

[41] LoS K, LiuY, ChiaS Y, XuX, LuQ, ZhuL, NingH. Analysis of Blockchain solutions for IoT: A systematic literature review. IEEE Access, 2019, 7: 58822-58835

[42] MadenoueiN AExploring the scalability, through-put and security characteristics of the Tangle distributed ledger technology through simulation analysis, 2020, Toronto, Canada. Graduate Program in Computer Science, York University.

[43] NakamotoSBitcoin: A peer-to-peer electronic cash system, 2008Accessed October 31, 2008

[44] ParkS, OhS, KimH. Performance analysis of DAG-based cryptocurrency. The IEEE International Conference on Communications Workshops, 2019May 20–24, 2019

[45] PenzkoferA, SaaO, DziubatowskaD. Impact of delay classes on the data structure in IOTA. International Workshop on Data Privacy Management, 2021October 4–8, 2021

[46] PervezH, MuneebM, IrfanM U, HaqIU. A comparative analysis of DAG-based Blockchain architectures. 2018 12th International Conference on Open Source Systems and Technologies (ICOSST), 2018December 19–21, 2018

[47] PopovSThe Tangle version 1.0, 2016131156

[48] PopovSThe Tangle, 2018Accessed October 1, 2017

[49] PopovS, SaaO, FinardiP. Equilibria in the Tangle. Computers & Industrial Engineering, 2019, 136: 160-172

[50] PopovS, MoogH, CamargoD, CaposseleA, DimitrovV, GalA, GreveA, KusmierzB, MuellerS, PenzkoferA, SaaOThe coordicide, 2020Accessed January 20, 2020

[51] PopovS, BuchananW J. Fpc-bi: Fast probabilistic consensus within byzantine infrastructures. Journal of Parallel and Distributed Computing, 2021, 147: 77-86

[52] RamaswamiV, TaylorP G. Some properties of the rate perators in level dependent quasi-birth-and-death processes with countable number of phases. Stochastic Models, 1996, 12(1): 143-164

[53] ReedJLitecoin: An Introduction to Litecoin Cryptocurrency and Litecoin Mining, 2017, North Charleston, United States. CreateSpace Independent Publishing Platform.

[54] RosenbergerJ, RauterbergF, SchrammD. Performance study on IOTA chrysalis and coordicide in the industrial Internet of Things. 2021 IEEE Global Conference on Artificial Intelligence and Internet of Things (GCAIoT), 2021December 12–16, 2021

[55] SaaO, CullenA, VigneriLIOTA 2.0 incentives and tokenomics whitepaper, 2023Accessed November, 2023

[56] SenguptaJ, RuS, BitS D. A comprehensive survey on attacks, security issues and Blockchain solutions for IoT and IIoT. Journal of Network and Computer Applications, 2020, 149102481

[57] StaupePQuasi-analytic parasite chain absorption probabilities in the Tangle, 2017Accessed June 15, 2019

[58] TikhomirovS. Ethereum: State of knowledge and research perspectives. Foundations and Practice of Security: 10th International Symposium, 2018October 23–25, 2017

[59] ViriyasitavatW, AnuphaptrirongT, HoonsoponD. When Blockchain meets Internet of Things: Characteristics, challenges, and business opportunities. Journal of Industrial Information Integration, 2019, 15: 21-28

[60] WangQ, YuJ, ChenS, XangY. Sok: Dag-based Blockchain systems. ACM Computing Surveys, 2023, 55(12): 1-38

[61] XieZ, DangS, ZhangZ. On convergence probability of direct acyclic graph-based ledgers in forking Blockchain systems. IEEE Systems Journal, 2022, 17(1): 1121-1124

[62] XuX, JianhuaH, HongZ, RuicongT. An optimal stability matching algorithm for DAG Blockchain based on matching theory. Chinese Journal of Electronics, 2021, 30(2): 367-377

[63] YangD, LongC, XuH, PengS. A review on scalability of Blockchain. Proceedings of the 2020 the 2nd International Conference on Blockchain Technology, 2020March 12–14, 2020

[64] YuanY, WangF Y. Blockchain: The state of the art and future trends. Acta Automatica Sinica, 2016, 43(4): 1481-1494

[65] ZanderM, WaiteT, HarzD. DAGsim: Simulation of DAG-based distributed ledger protocols. ACM SIGMETRICS Performance Evaluation Review, 2018, 46(3): 118-121

[66] ZhangJ, TanR, SuC, SiW. Design and application of a personal credit information sharing platform based on consortium Blockchain. Journal of Information Security and Applications, 2020, 55102659

[67] ZhangZ, WuG, NingK. Optimizing the access control system for IOTA Tangle: A game-theoretic perspective. 2023 26th International Conference on Computer Supported Cooperative Work in Design (CSCWD), 2023May 24–26, 2023

[68] ZhuQ, LokeS W, Trujillo-RasuaR, JiangF, XiangY. Applications of distributed ledger technologies to the Internet of Things: A survey. ACM Computing Surveys, 2019, 52(6): 1-34

[69] ZubaydiH D, VargaP, MolnárS. Leveraging Blockchain technology for ensuring security and privacy aspects in Internet of Things: A systematic literature review. Sensors, 2023, 232788

RIGHTS & PERMISSIONS

Systems Engineering Society of China and Springer-Verlag GmbH Germany