基于有向无环图的区块链技术综述

doi:10.19678/j.issn.1000-3428.0064002

摘要/Abstract

摘要： 区块链技术已广泛应用于金融、公共服务、物联网、网络安全、供应链等多个领域，但传统单链结构的区块链在吞吐量、交易确认速度和可扩展性方面存在不足，导致其在一些短时高并发量数据场景中难以落地应用。基于有向无环图（DAG）的区块链技术因其具有交易并发确认功能、吞吐量高、可扩展性强等优势受到研究者广泛关注。通过分析研究现有DAG区块链的发展和演化过程、评估方法、优化方向以及应用场景，探索DAG区块链在落地应用中的可行性。阐述主流DAG区块链的研究现状，比较传统区块链与DAG区块链的优势与不足，并分析现有区块链属性评估方法，总结DAG区块链评估结果。在此基础上，从交易确认速度、系统吞吐量、系统安全性、存储结构等方面对比现有DAG区块链的优化方法，介绍DAG区块链在数据管理、基于边缘计算和联邦学习的数据共享以及面向访问控制和隐私保护的数据安全等场景中的应用情况，并指出当前研究中存在的主要问题和挑战，对未来的研究方向进行展望。

关键词: 区块链, 有向无环图, 共识机制, 区块链数据结构, 分布式账本技术, 数据管理

Abstract: Blockchain technology has been widely used in finance, public services, the Internet of Things(IoT), network security, supply chains, and other fields.However, the traditional blockchain with a single chain structure has some deficiencies in throughput, transaction confirmation speed, and scalability, which makes it difficult to apply it in some short-term and high concurrency data scenarios.In this paper, the Directed Acyclic Graph(DAG) based blockchain technology has attracted extensive attention and studied by scholars because of its advantages, such as concurrent transaction confirmation, high throughput, and strong scalability.By analyzing and studying the development and evolution, evaluation methods, optimization direction, and application scenarios of the existing DAG based blockchains, this paper explores the feasibility of DAG based blockchains in landing applications.Through the development of a mainstream DAG based blockchain, it compares the advantages and disadvantages of traditional blockchains and DAG based blockchains, analyzes the existing blockchain attribute evaluation methods, and summarizes the current DAG based blockchain evaluation results.On this basis, this paper summarizes the optimization methods of the existing DAG based blockchain from the aspects of transaction confirmation speed, system throughput, system security, and storage structure, and summarizes the application of a DAG based blockchain in data management, data sharing based on edge computing and federated learning, and data security for access control and privacy protection.Finally, it points out the main problems and challenges in the current studies, and provides further research directions.

Key words: blockchain, Directed Acyclic Graph(DAG), consensus mechanism, data structure of blockchain, Distributed Ledger Technology(DLT), data management

中图分类号:

TP309

王劲松, 杨唯正, 赵泽宁, 魏佳佳. 基于有向无环图的区块链技术综述[J]. 计算机工程, 2022, 48(6): 11-23.

WANG Jinsong, YANG Weizheng, ZHAO Zening, WEI Jiajia. Survey of Directed Acyclic Graph Based Blockchain Technology[J]. Computer Engineering, 2022, 48(6): 11-23.

https://www.ecice06.com/CN/Y2022/V48/I6/11

图/表 6

20220618112701

20220618112704

20220618112708

20220618112712

20220618112716

20220618112719

参考文献

[1] NAKAMOTO S.Bitcoin:a peer-to-peer electronic cashsystem[EB/OL].[2022-02-20].https://bitcoin.org/en/bitcoin-paper.
[2] WOOD G.Ethereum:a secure decentralised generalised transaction ledger[EB/OL].[2022-02-20].http://gavwood.com/Paper.pdf.
[3] LEE G.EOS technical white paper[EB/OL].[2022-02-20].https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.
[4] ANDROULAKI E, BARGER A, BORTNIKOV V, et al.Hyperledger fabric:a distributed operating system for permissioned blockchains[C]//Proceedings of EuroSys'18.Washington D.C., USA:IEEE Press, 2018:1-15.
[5] WOOD G.Polkadot:vision for a heterogeneous multi-chain framework[EB/OL].[2022-02-20].https://polk-adot.network/Polkadot-lightpaper.pdf.
[6] 张亮, 刘百祥, 张如意, 等.区块链技术综述[J].计算机工程, 2019, 45(5):1-12. ZHANG L, LIU B X, ZHANG R Y, et al.Overview of blockchain technology[J].Computer Engineering, 2019, 45(5):1-12.(in Chinese)
[7] WAN C C, TANG S Y, ZHANG Y C, et al.Goshawk:a novel efficient, robust and flexible blockchain protocl[C]//Proceedings of the 15th International Conference on Information Security and Cryptology.Berlin, Germany:Springer, 2019:49-69.
[8] WAN Z G, LIU W, CUI H.HIBEChain:a hierarchical identity-based blockchain system for large-scale IoT[EB/OL].[2022-02-20].https://dblp.uni-trier.de/rec/journals/iacr/WanLC19.html.
[9] LERNER S D.DagCoin:a cryptocurrency without blocks[EB/OL].[2022-02-20].https://bitslog.com/2015/09/11/dagcoin/.
[10] POPOV S.The tangle[EB/OL].[2022-02-20].https://www.doc88.com/p-0857889997312.html.
[11] CHURYUMOV A.Byteball:a decentralized system for storage and transfer of value[EB/OL].[2022-02-20].https://byteball.org/Byteball.pdf.
[12] NANO:digital money for the modern world[EB/OL].[2022-02-20].https://docs.nano.org/living-whitepaper.
[13] LI C X, LI P L, ZHOU D, et al.Scaling Nakamoto consensus to thousands of transactions per second[EB/OL].[2022-02-20].https://arxiv.org/abs/1805.03870.
[14] LI C, LI P, ZHOU D, et al.A decentralized blockchain with high throughput and fast confirmation[C]//Proceedings of 2020 USENIX Annual Technical Conference.[S.l.]:USENIX, 2020:515-528.
[15] BAIRD L.Hashgraph consensus:fair, fast, byzantine fault tolerance[EB/OL].[2022-02-20].http://pages.cpsc.ucalgary.ca/~joel.reardon/blockchain/readings/hashgraph.pdf.
[16] ŽIVIĆ N, KADUŠIĆ E, KADUŠIĆ K.Directed acyclic graph as Hashgraph:an alternative DLT to blockchains and tangles[C]//Proceedings of INFOTEH'20.Washington D.C., USA:IEEE Press, 2020:1-4.
[17] ZHAO L R, YU J S.Evaluating DAG-based blockchains for IoT[C]//Proceedings of the 18th International Conference on Trust, Security and Privacy in Computing and Communications/the 13th IEEE International Conference on Big Data Science and Engineering.Washington D.C., USA:IEEE Press, 2019:507-513.
[18] SOMPOLINSKY Y, LEWENBERG Y, ZOHAR A.SPECTRE:a fast and scalable cryptocurrency protocol[EB/OL].[2022-02-20].https://eprint.iacr.org/2016/1159.pdf.
[19] HYCON whitepaper[EB/OL].[2022-02-20].http://hycon.io/images/HYCONWhitePaper_V1.3_en.pdf.
[20] SOMPOLINSKY Y, ZOHAR A.PHANTOM:a scalable BlockDAG protocol[EB/OL].[2022-02-20].https://dblp.uni-trier.de/rec/journals/iacr/SompolinskyZ18.html.
[21] SOMPOLINSKY Y, WYBORSKI S, ZOHAR A.PHANTOM and GHOSTDAG:a scalable generalization of Nakamoto consensus[C]//Proceedings of the 3rd ACM Conference on Advances in Financial Technologies.New York, USA:ACM Press, 2021:57-70.
[22] LI J X, WU J G, CHEN L, et al.Blockchain-based secure key management for mobile edge computing[EB/OL].[2022-02-20].https://eprint.iacr.org/2018/104.pdf.
[23] LI J X, WU J G, JIANG G Y, et al.Blockchain-based public auditing for big data in cloud storage[J].Information Processing & Management, 2020, 57(6):1-10.
[24] BENČIĆ F M, ŽARKO I P.Distributed ledger technology:blockchain compared to directed acyclic graph[C]//Proceedings of the 38th International Conference on Distributed Computing Systems.Washington D.C., USA:IEEE Press, 2018:1569-1570.
[25] CAO B, ZHANG Z H, FENG D Q, et al.Performance analysis and comparison of PoW, PoS and DAG based blockchains[J].Digital Communications and Networks, 2020, 6(4):480-485.
[26] YEOW K, GANI A, AHMAD R, et al.Decentralized consensus for edge-centric Internet of Things:a review, taxonomy, and research issues[J].IEEE Access, 2017, 6:1513-1524.
[27] 高政风, 郑继来, 汤舒扬, 等.基于DAG的分布式账本共识机制研究[J].软件学报, 2020, 31(4):1124-1142. GAO Z F, ZHENG J L, TANG S Y, et al.State-of-the-art survey of consensus mechanisms on DAG-based distributed ledger[J].Journal of Software, 2020, 31(4):1124-1142.(in Chinese)
[28] LATHIF M R A, NASIRIFARD P, JACOBSEN H A.CIDDS:a configurable and distributed DAG-based distributed ledger simulation framework[C]//Proceedings of the 19th International Middleware Conference.Washington D.C., USA:IEEE Press, 2018:7-8.
[29] ZANDER M, WAITE T, HARZ D.DAGsim[J].ACM SIGMETRICS Performance Evaluation Review, 2019, 46(3):118-121.
[30] FAN C X, GHAEMI S, KHAZAEI H, et al.Performance analysis of the IOTA DAG-based distributed ledger[J].ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 2021, 6(3):10.
[31] DONG Z L, ZHENG E, CHOON Y, et al.DAGBENCH:a performance evaluation framework for DAG distributed ledgers[C]//Proceedings of the 12th International Conference on Cloud Computing.Washington D.C., USA:IEEE Press, 2019:264-271.
[32] WANG Q, YU J S, CHEN S P, et al.SoK:diving into DAG-based blockchain systems[EB/OL].[2022-02-20].https://arxiv.org/abs/2012.06128.
[33] CAO B, HUANG S M, FENG D Q, et al.Impact of network load on direct acyclic graph based blockchain for Internet of Things[C]//Proceedings of International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery.Washington D.C., USA:IEEE Press, 2019:215-218.
[34] WANG T Y, WANG Q, SHEN Z Y, et al.Understanding intrinsic characteristics and system implications of DAG-based blockchain[C]//Proceedings of IEEE International Conference on Embedded Software and Systems.Washington D.C., USA:IEEE Press, 2020:1-6.
[35] WANG T Y, WANG Q, SHEN Z Y, et al.Understanding characteristics and system implications of DAG-based blockchain in IoT environments[C]//Proceedings of ICESS'20.Washington D.C., USA:IEEE Press, 2020:1-6.
[36] GHAEMI S.Analysis and design of open decentralized serverless computing platforms[D].Edmonton, Canada:University of Alberta, 2020.
[37] KOTILEVETS I D, IVANOVA I A, ROMANOV I O, et al.Implementation of directed acyclic graph in blockchain network to improve security and speed of transactions[J].IFAC-PapersOnLine, 2018, 51(30):693-696.
[38] WANG Q.Improving the scalability of blockchain through DAG[C]//Proceedings of the 20th International Middleware Doctoral Symposium.Washington D.C., USA:IEEE Press, 2019:34-35.
[39] PARK S, OH S, KIM H.Performance analysis of DAG-based cryptocurrency[C]//Proceedings of 2019 IEEE International Conference on Communications Workshops.Washington D.C., USA:IEEE Press, 2019:1-6.
[40] ZHOU T, LI X F, ZHAO H.DLattice:a permission-less blockchain based on DPoS-BA-DAG consensus for data tokenization[J].IEEE Access, 2019, 7:39273-39287.
[41] ZHANG X D, LI R, HOU W H, et al.V-lattice:a lightweight blockchain architecture based on DAG-lattice structure for vehicular ad hoc networks[J].Security and Communication Networks, 2021, 2021:1-10.
[42] WANG Q, WANG T Y, SHEN Z Y, et al.Re-Tangle:a ReRAM-based processing-in-memory architecture for transaction-based blockchain[C]//Proceedings of IEEE/ACM International Conference on Computer-Aided Design.Washington D.C., USA:IEEE Press, 2019:1-8.
[43] FERRARO P, KING C, SHORTEN R.IOTA-based directed acyclic graphs without orphans[EB/OL].[2022-02-20].https://arxiv.org/abs/1901.07302.
[44] FERRARO P, KING C, SHORTEN R.On the stability of unverified transactions in a DAG-based distributed ledger[J].IEEE Transactions on Automatic Control, 2020, 65(9):3772-3783.
[45] SAAD A, PARK S Y.Decentralized directed acyclic graph based DLT network[C]//Proceedings of International Conference on Omni-Layer Intelligent Systems.Washington D.C., USA:IEEE Press, 2019:158-163.
[46] DANEZIS G, HRYCYSZYN D.Blockmania:from block DAGs to consensus[EB/OL].[2022-02-20].https://arxiv.org/abs/1809.01620.
[47] CHEN T Y, HUANG W N, KUO P C, et al.DEXON:a highly scalable, decentralized DAG-based consensus algorithm[EB/OL].[2022-02-20].https://arxiv.org/abs/1811.07525.
[48] CHISHTI M S, BANERJEE A.Increasing TPS rate of state-based blockchains by parallel mining[J].Internet Technology Letters, 2021, 4(2):1-10.
[49] KAN J, CHEN S Z, HUANG X.Improve blockchain performance using graph data structure and parallel mining[EB/OL].[2022-02-20].https://arxiv.org/abs/1808.10810.
[50] LEWENBERG Y, SOMPOLINSKY Y, ZOHAR A.Inclusive block chain protocols[C]//Proceedings of International Conference on Financial Cryptography and Data Security.Berlin, Germany:Springer, 2015:528-547.
[51] GUPTA H, JANAKIRAM D.CDAG:a serialized blockDAG for permissioned blockchain[EB/OL].[2022-02-20].https://arxiv.org/abs/1910.08547.
[52] ROCKET T.Snowflake to avalanche:a novel metastable consensus protocol family for cryptocurrencies[EB/OL].[2022-02-20].http://knowen-production.s3.amazonaws.com/uploads/attachment/file/1922/Snowflake%2Bto%2BAvalanche%2B-%2BA%2BNovel%2BMetastable%2BConsensus%2BProtocol%2BFamily.pdf.
[53] Perlin:scalable DAG-based distributed ledger protocolusing avalanche consensus[EB/OL].[2022-02-20].https://drive.google.com/file/d/1vfj1j2OTase4mkj8fj9BmbtUFYgYjwg4/view.
[54] FU X, WANG H M, SHI P C, et al.Jointgraph:a DAG-based efficient consensus algorithm for consortium blockchains[J].Software:Practice and Experience, 2021, 51(10):1987-1999.
[55] WANG B Z, WANG Q, CHEN S P, et al.Security analysis on Tangle-based blockchain through simulation[C]//Proceedings of International Conference on Information Security and Privacy.Berlin, Germany:Springer, 2020:653-663.
[56] CULLEN A, FERRARO P, KING C, et al.On the resilience of DAG-based distributed ledgers in IoT applications[J].IEEE Internet of Things Journal, 2020, 7(8):7112-7122.
[57] LI Y X, CAO B, PENG M G, et al.Direct acyclic graph-based ledger for Internet of Things:performance and security analysis[J].IEEE/ACM Transactions on Networking, 2020, 28(4):1643-1656.
[58] PERVEZ H, MUNEEB M, IRFAN M U, et al.A comparative analysis of DAG-based blockchain architectures[C]//Proceedings of the 12th International Conference on Open Source Systems and Technologies.Washington D.C., USA:IEEE Press, 2018:27-34.
[59] CUI L Z, YANG S, CHEN Z T, et al.An efficient and compacted DAG-based blockchain protocol for industrial Internet of Things[J].IEEE Transactions on Industrial Informatics, 2020, 16(6):4134-4145.
[60] HELLANI H, SLIMAN L, SAMHAT A E, et al.Computing resource allocation scheme for DAG-based IOTA nodes[J].Sensors(Basel, Switzerland), 2021, 21(14):4703.
[61] SON B, LEE J, JANG H.A scalable IoT protocol via an efficient DAG-based distributed ledger consensus[J].Sustainability, 2020, 12(4):1529.
[62] NGUYEN Q, CRONJE A, KONG M, et al.StairDag:cross-DAG validation for scalable BFT consensus[EB/OL].[2022-02-20].https://arxiv.org/abs/1908.11810.
[63] 张震, 李强, 甘俊, 等.基于DAG的区块链新模型设计与实现[J].计算机应用与软件, 2021, 38(10):114-124. ZHANG Z, LI Q, GAN J, et al.Design and implementation of a new blockchain model based on DAG[J].Computer Applications and Software, 2021, 38(10):114-124.(in Chinese)
[64] NILSSON A, BONANDER C, STRÖMBERG U, et al.A directed acyclic graph for interactions[J].International Journal of Epidemiology, 2021, 50(2):613-619.
[65] ZHANG Z Y, VASAVADA V, MA X Y, et al.DLedger:an IoT-friendly private distributed ledger system based on DAG[EB/OL].[2022-02-20].https://arxiv.org/pdf/1902.09031.pdf.
[66] SCHETT M A, DANEZIS G.Embedding a deterministic BFT protocol in a block DAG[C]//Proceedings of 2021 ACM Symposium on Principles of Distributed Computing.New York, USA:ACM Press, 2021:177-186.
[67] DU M, WANG K, LIU Y Q, et al.Spacechain:a three-dimensional blockchain architecture for IoT security[J].IEEE Wireless Communications, 2020, 27(3):38-45.
[68] WATANABE H, ISHIDA T, OHASHI S, et al.Enhancing blockchain traceability with DAG-based tokens[C]//Proceedings of IEEE International Conference on Blockchain.Washington D.C., USA:IEEE Press, 2019:220-227.
[69] YANG W H, DAI X H, XIAO J, et al.LDV:a lightweight DAG-based blockchain for vehicular social networks[J].IEEE Transactions on Vehicular Technology, 2020, 69(6):5749-5759.
[70] FU X, WANG H M, SHI P C, et al.Teegraph:trusted execution environment and directed acyclic graph-based consensus algorithm for IoT blockchains[J].Science China Information Sciences, 2021, 65(3):1-3.
[71] WANG B Y, DABBAGHJAMANESH M, KAVOUSI-FARD A, et al.Cybersecurity enhancement of power trading within the networked microgrids based on blockchain and directed acyclic graph approach[J].IEEE Transactions on Industry Applications, 2019, 55(6):7300-7309.
[72] SHAFEEQ S, ZEADALLY S, ALAM M, et al.Curbing address reuse in the IOTA distributed ledger:a cuckoo-filter-based approach[J].IEEE Transactions on Engineering Management, 2020, 67(4):1244-1255.
[73] WANG T Y, ZHU W B, MA Q, et al.ABACUS:address-partitioned bloom filter on address checking for UniquenesS in IoT blockchain[C]//Proceedings of IEEE/ACM International Conference on Computer Aided Design.Washington D.C., USA:IEEE Press, 2020:1-7.
[74] ZHU W B, MA Q, SHEN Z Y, et al.HF-BF:a hotness-aware fine-grained bloom filter for unique address checking in IoT blockchain[C]//Proceedings of HPCC/SmartCity/DSS.Washington D.C., USA:IEEE Press, 2020:1015-1020.
[75] MAKHDOOM I, ABOLHASAN M, ABBAS H, et al.Blockchain's adoption in IoT:the challenges, and a way forward[J].Journal of Network and Computer Applications, 2019, 125:251-279.
[76] RADHAKRISHNAN R, KRISHNAMACHARI B.Streaming Data Payment Protocol(SDPP) for the Internet of Things[C]//Proceedings of IEEE International Conference on Internet of Things(iThings) and IEEE Green Computing and Communications(GreenCom) and IEEE Cyber, Physical and Social Computing(CPSCom) and IEEE Smart Data.Washington D.C., USA:IEEE Press, 2018:1679-1684.
[77] PARK S, KIM H.DAG-based distributed ledger for low-latency smart grid network[J].Energies, 2019, 12(18):1-22.
[78] ZHANG H W, LENG S P, WU F, et al.A DAG blockchain enhanced user-autonomy spectrum sharing framework for 6G-enabled IoT[EB/OL].[2022-02-20].https://ieeexplore.ieee.org/abstract/document/9528845.
[79] GAO Y, LIU Y L, WEN Q S, et al.Secure drone network edge service architecture guaranteed by DAG-based blockchain for flying automation under 5G[J].Sensors(Basel, Switzerland), 2020, 20(21):6209.
[80] BHANDARY M, PARMAR M, AMBAWADE D.A blockchain solution based on directed acyclic graph for IoT data security using IoTA Tangle[C]//Proceedings of the 5th International Conference on Communication and Electronics Systems.Washington D.C., USA:IEEE Press, 2020:827-832.
[81] JIANG Y M, WANG C X, WANG Y W, et al.A cross-chain solution to integrating multiple blockchains for IoT data management[J].Sensors (Basel, Switzerland), 2019, 19(9):2042.
[82] LIN Y P, MUKHTAR H, HUANG K T, et al.Real-time identification of irrigation water pollution sources and pathways with a wireless sensor network and blockchain framework[J].Sensors (Basel, Switzerland), 2020, 20(13):3634.
[83] HUANG J Q, KONG L H, CHEN G H, et al.Towards secure industrial IoT:blockchain system with credit-based consensus mechanism[J].IEEE Transactions on Industrial Informatics, 2019, 15(6):3680-3689.
[84] KARLSSON K, JIANG W T, WICKER S, et al.Vegvisir:a partition-tolerant blockchain for the Internet-of-Things[C]//Proceedings of the 38th International Conference on Distributed Computing Systems.Washington D.C., USA:IEEE Press, 2018:1150-1158.
[85] CHEN W Y, YANG X, ZHANG H K, et al.Big data architecture for scalable and trustful DNS based on sharded DAG blockchain[J].Journal of Signal Processing Systems, 2021, 93(7):753-768.
[86] BEILHARZ J, PFITZNER B, SCHMID R, et al.Implicit model specialization through dag-based decentralized federated learning[EB/OL].[2022-02-20].https://arxiv.org/abs/2111.01257.
[87] CAO M R, CAO B, HONG W, et al.DAG-FL:direct acyclic graph-based blockchain empowers on-device federated learning[C]//Proceedings of IEEE International Conference on Communications.Washington D.C., USA:IEEE Press, 2021:1-6.
[88] CAO M, ZHANG L, CAO B.Toward on-device federated learning:a direct acyclic graph-based blockchain approach[EB/OL].[2022-02-20].https://arxiv.org/abs/2104.3092.
[89] HUANG J Q, KONG L H, CHEN G H, et al.B-IoT:blockchain driven Internet of Things with credit-based consensus mechanism[C]//Proceedings of the 39th International Conference on Distributed Computing Systems.Washington D.C., USA:IEEE Press, 2019:1348-1357.
[90] JAVAD A M, DIVYAKANT A, EL A A.CAPER:a cross-application permissioned blockchain[J].Proceedings of the VLDB Endowment, 2019, 12(11):1385-1398.
[91] NGUYEN Q, CRONJE A, KONG M, et al.StakeDag:stake-based consensus for scalable trustless systems[EB/OL].[2022-02-20].https://arxiv.org/abs/1907.03655.
[92] KHAN M A, SALAH K.IoT security:Review, blockchain solutions, and open challenges[J].Future Generation Computer Systems, 2018, 82:395-411.
[93] FAN C.Performance analysis and design of an IoT-friendly DAG-based distributed ledger system[D].Edmonton, Canada:University of Alberta, 2019.
[94] FAN C X, KHAZAEI H, CHEN Y X, et al.Towards a scalable DAG-based distributed ledger for smart communities[C]//Proceedings of the 5th World Forum on Internet of Things.Washington D.C., USA:IEEE Press, 2019:177-182.
[95] GUO J X, DING X J, WU W L.A double auction for charging scheduling among vehicles using DAG-blockchains[EB/OL].[2022-02-20].https://arxiv.org/abs/2010.01436v1.

选择文件类型/文献管理软件名称

选择包含的内容