基于有向無環圖的區塊鏈技術綜述

王勁松，楊唯正，趙澤寧，魏佳佳

（1.天津理工大學計算機科學與工程學院，天津 300384；2.智能計算及軟件新技術天津市重點實驗室，天津 300384；3.計算機病毒防治技術國家工程實驗室，天津 300457）

0 概述

區塊鏈概念自2008 年被提出以來，引起了全世界廣泛關注，常見的區塊鏈應用有比特幣［1］、以太坊［2］、EOS［3］、Hyperledger Fabric［4］、波卡［5］等。近年來，區塊鏈逐漸演變為一種提供可信溯源服務的服務架構，各個行業都在積極探索區塊鏈的落地應用［6］。然而，傳統區塊鏈只有一條單鏈，打包出塊無法并發執行。為了提高傳統區塊鏈系統的交易執行速度，一些研究者提出了多層區塊鏈、分片區塊鏈等技術。文獻［7］提出混合協商一致協議Goshawk，將兩層鏈式結構、兩級工作量證明（Proof of Work，PoW）挖掘策略和票證投票機制巧妙地結合起來。文獻［8］提出的HIBEChain 是一個分層區塊鏈系統，可實現物聯網（Internet of Things，IoT）設備和數據的可擴展和可問責管理，其由多個許可區塊鏈組成，這些區塊鏈形成一個層次樹結構。HIBEChain 通過將區塊鏈分片并行處理的方案實現了高可擴展性。為了支持HIBEChain 的層次結構，該文作者設計了一個基于身份的分散層次簽名方案DHIBS，使物聯網設備能夠將其身份用作公鑰。

在上述研究基礎上，如果改變區塊的鏈式存儲結構，將單鏈結構轉變為有向無環圖（Directed Acyclic Graph，DAG）的網狀拓撲結構，就可以實現并發寫入，提高交易確認速度和吞吐量。假設在區塊打包時間不變的情況下網絡中可以并行打包n個區塊，則交易確認速度就提高了n倍。由此，DAG 區塊鏈技術開始迅速發展。

本文介紹DAG 區塊鏈概念的提出和演化革新過程，對比分析該技術與傳統區塊鏈技術，歸納現有的DAG區塊鏈評估系統、方法以及評估結論。同時，從交易確認速度、系統吞吐量、安全性、存儲結構等4 個方面對DAG 區塊鏈的優化方法進行總結分析，介紹DAG 區塊鏈目前在數據管理、數據共享、數據安全等場景中的應用。在此基礎上，闡述DAG 區塊鏈技術的研究現狀，并展望未來的發展方向。

1 DAG 區塊鏈的發展

1.1 DAG 區塊鏈的提出與發展

2013 年，ID 為avivz78 的以色列希伯來大學學者在bitcointalik.org 上首次將DAG 概念引入區塊鏈中作為共識算法（即GHOST 協議），將其作為比特幣的交易處理能力擴容解決方案。

2015 年，LERNER［9］提出一種基于DAG 結構的加密貨幣設計DagCoin，其中沒有固定的塊，并且每個交易都有自己的工作證明。此外，還提出了2 種優化方法，允許存儲和動態更新更低CPU 資源消耗的DAG 區塊鏈。通過將最新的交易存儲在快速緩存中，并在不能引用舊交易的地方使用檢查點，系統可以達到與比特幣一樣快的速度，甚至更快，DAG區塊鏈由此產生。DAG 區塊鏈是面向未來的新一代區塊鏈，是區塊鏈從容量到速度的一次革新。從圖論拓撲模型角度宏觀來看，其從單鏈結構革新到樹狀和網狀結構，從區塊粒度結構細化到交易粒度結構，并從單點寫入過程優化到并發寫入過程。

隨著DAG 區塊鏈技術的發展，早期形成了以IOTA、Byteball、NANO 等3 種結構為代表的DAG 區塊鏈體系，而后發展產生了前景良好的Conflux。目前，這4 個項目是落地運行的主流DAG 區塊鏈項目。

2016 年，POPOV［10］提出了IOTA，其中最主要的創新是基于DAG設計的分布式賬本結構——纏結（Tangle），其是一個既沒有區塊也沒有鏈的區塊鏈。在Tangle中，每一個節點代表的是一個交易。IOTA中沒有區塊的概念，也沒有挖礦和礦工的概念，沒有挖礦和礦工就代表沒有交易費，整個網絡的吞吐量也很高，這是IOTA的顯著特點。IOTA DAG 區塊鏈結構如圖1所示。

圖1 IOTA DAG 區塊鏈結構Fig.1 IOTA DAG based blockchain structure

2016 年，CHURYUMOV［11］提出了Byteball，其在DAGCoin 的基礎上，創新性地引入主鏈與見證人的概念，鼓勵驗證多個父輩交易單元，形成一個隨著交易增長、相互驗證、安全性不斷加強的數字簽名Hash網絡。Byteball中包含一種創新的“主鏈”概念，即經見證人認定的最短路徑MC 的Parents 優選算法。主鏈創造了一個全網共識確定的交易時間序列，巧妙地避免了雙花問題。

文獻［12］提出的NANO 使用了委托權益證明（Delegated Proof of Stake，DPOS）共識機制，賬戶可以指定代表為其投票，得票最多的代表將處理分叉，這個代表會將分叉廣播到網絡，并觀察來自高權賬戶節點在固定時間內的投票結果，以此來確定保留哪一個區塊。NANO 通過DPOS 機制保證了區塊的合理低能耗運行，同時，其也使用到了PoW 機制，以確認交易需要非常少的工作量證明。

Conflux［13］是一家公有區塊鏈系統研發商，其使用DAG 結構并結合獨特的算法，使共識不再是擴容的瓶頸。Conflux 協議將區塊組織成一個新的樹圖區塊鏈結構，這是一個嵌入到有向無環圖中的樹。Conflux 為每個塊指定一個權重，該權重表示這個塊最終對其祖先塊的貢獻度。為了進一步適應環境變化，文獻［14］重新設計了Conflux 的共識協議，編碼了2 種不同的塊生成策略：一種允許快速確認的樂觀策略，以及一種確保交易共識的保守策略。Conflux 使用自適應權重機制將這2 種策略結合到一個統一的一致性協議中，以應對不同的工作場景。

1.2 DAG 區塊鏈的演化與革新

隨著DAG 區塊鏈技術的不斷發展，研究者提出了許多新的DAG 區塊鏈技術（如Hashgraph 共識機制、SPECTRE 協議、PHANTOM 協議等），在去中心化機制、速度與并發方面都取得了進展，但這些技術迄今為止還未落地實施。

文獻［15］提出的Hashgraph 在公鏈環境下實現了異步BFT 共識。傳統BFT 的一大問題是消息復雜度太高，大量消耗網絡帶寬，且無法很好地應對動態網絡，而Hashgraph 引入了Gossip 協議，同時運用虛擬投票機制，避免在共識時引起突發大規模消息傳遞風暴。文獻［16］分析了一種非常強大的區塊鏈替代技術——Hashgraphs，并解釋其架構和功能，給出進一步開發的方向和預測。文獻［17］對基于DAG 的模型IOTA 和Hashgraph 進行了對比分析，并且對模型特征和功能進行概述。同時，定義評估這2種區塊鏈所需標準，對2個系統進行了深入分析，并確定了IOTA 和Hashgraph 在IoT 中的應用面臨的挑戰。

文獻［18］提出的SPECTRE協議采用了Block+DAG的“區塊有向無環圖”技術，可以并行挖礦，從而獲得更大的吞吐量和更快的交易確認速度。該項技術是對中本聰提出的區塊鏈的泛化，解決了前者需要在安全性與擴容能力之間進行取舍的問題，因而更適合建立速度更快或規模更大的區塊。但是該協議在受到“雙花”攻擊時，攻擊區塊在發布以前幾乎不會與誠實節點產生的區塊相關聯，因為在這個階段誠實區塊不知道這些攻擊區塊的存在，所以自然不會引用它們。綜合來看，這些惡意攻擊都有一個顯著特點：惡意節點產生的區塊與誠實節點產生的區塊之間的連通度比較低，反之，誠實節點產生的區塊之間的連通度會比較高。文獻［19］中的Hycon 使用SPECTRE 協議作為共識機制來保證交易速度和靈活性，其主要特性是快速交易確認時間、鏈上交易擴展性（在2 MB/s 的連接中高達3 000 筆交易每秒的吞吐量）、同步出塊（基于DAG 結構位置而不是時間先后鏈接區塊）以及智能合約。

文獻［20］介紹了一種在任何網絡狀況下都是安全的交易確認協議PHANTOM。PHANTOM 不會受到比特幣協議所面臨的安全性和可擴展性需要權衡的問題，其利用帶區塊的有向無環圖blockDAG 作為比特幣區塊鏈的一個擴展，支持生成更快和更大的區塊，但需要更長的時間傳播。PHANTOM 在blockDAG 上使用貪婪算法來區分誠實節點正確挖礦的區塊和選擇偏離挖礦協議的非合作節點創建的塊。利用這一特點，PHANTOM 在blockDAG 上提供了一個健壯的完整命令，最終使得所有誠實節點達成共識。文獻［21］提出的PHANTOM 協議的投票原則正是基于這個原理，通過判斷不同區塊間的連通度進行投票。

1.3 傳統區塊鏈與DAG 區塊鏈的對比

傳統的區塊鏈將交易打包在塊中形成鏈式結構［22］，而基于DAG 的分布式賬本將交易作為邊存儲在有向無環圖中，這就使得傳統區塊鏈在安全性方面更加突出［23］，而DAG 區塊鏈在效率上更為突出。文獻［24］比較了傳統區塊鏈和DAG 區塊鏈在分布式設計上相關的特性，同時研究了優化分類賬戶維護、共識機制、交易確認可信度、分類賬戶大小以及可擴展性問題的數據結構。文獻［25］研究了區塊鏈中的3 種主流共識機制，即PoW、權益證明（Proof of Stake，PoS）和有向無環圖，并根據生成新區塊的平均時間、確認延遲、每秒交易確認數（Transactions Per Second，TPS）和交易確認失敗概率進行評價。結果表明，共識過程受網絡資源（包括計算能力、緩沖區大小等）和網絡負載條件的影響，且PoW 和PoS對網絡資源的變化更敏感，而DAG 對網絡負載條件更敏感。與PoW 和PoS 不同，在DAG 中創建新區塊不存在競爭，所有交易都是直接或間接關聯的。文獻［26］從數據結構、共識機制、交易模型這3 個方面對物聯網的分散共識系統進行了研究。對基于鏈式結構區塊鏈的系統（如比特幣和以太坊）和基于DAG 的分布式賬本（如IOTA 和Byteball）進行了綜合比較，通過分析和總結利弊，發現基于DAG 的分布式賬本在可擴展性、交易確認速度和分散性方面更優異。文獻［27］指出，基于DAG 的分布式賬本因其具有高并發特性，有望突破傳統區塊鏈中的性能瓶頸，且在基于DAG 的分布式賬本中，最為核心和關鍵的技術是共識機制，并為此對該關鍵技術進行了深入研究。本文對DAG 區塊鏈技術與傳統區塊鏈技術進行了對比，如表1 所示。

表1 DAG 區塊鏈技術與傳統區塊鏈技術的對比Table 1 Comparison of DAG based blockchain technology and traditional blockchain technology

2 DAG 區塊鏈的評估

2.1 評估系統

DAG 區塊鏈采用不同的優化機制，為評估這些優化機制的有效性，一些研究者設計實現了DAG 區塊鏈仿真系統對DAG 區塊鏈的關鍵指標進行評估。文獻［28］提出了一個基于DAG 的可配置交互式分布式賬本技術（Distributed Ledger Technology，DLT）仿真框架CIDDS，以實現數千節點級的大規模仿真，使用戶能夠使用數千個節點執行大規模模擬，并在受控條件下研究網絡的不同特性。文獻［29］為基于DAG 的加密貨幣提供了一個異步、連續時間和多代理的仿真框架DAGsim，對系統中誠實和半誠實的參與者進行建模，以分析特定加密貨幣IOTA 的行為。模擬結果表明，具有低延遲和高連接度的代理在網絡中以誠實和半誠實策略接受交易的概率更高。文獻［30］擴展了DAGsim 模擬器，提出分層分析模型來探索確認正態分布，并發現確認正態分布在DAG 層中，這導致了高斯模型的特征化。同時，利用該模型估計專用物聯網的RWT，并通過實驗結果進行驗證。文獻［31］提出一個DAG 區塊鏈的性能評估框架DAGBENCH。該框架提供了許多示例工作負載和適配器，可以有效且輕松地評估不同的DAG，從吞吐量、延遲、可擴展性、成功指標、資源消耗、交易數據大小、交易費用等各個方面衡量性能。

2.2 評估結論

一些研究者對現有DAG 區塊鏈系統不同方面的屬性進行了評估。文獻［32］對基于DAG 的區塊鏈系統進行了全面分析，通過解構開源系統和回顧學術研究，總結系統的主要組成部分和特征屬性，并提出了建立DAG 區塊鏈的方法。該文指出：1）基于DAG 的區塊鏈由于其不兼容的設計、缺乏標準、不可靠的安全性、不同的性能和未完成的實現，距離商業應用仍然較遠；2）DAG 結構有可能提高可擴展性和性能，但不可避免地會犧牲某些屬性，如一致性和終結性；3）基于DAG的系統各不相同，一個統一的形式化模型很難涵蓋所有關鍵點，相反地，一個松散和非正式的模型對于更好地理解不同的DAG區塊鏈系統非常有益；4）雖然將DAG結構應用于經典的分布式系統和區塊鏈系統是一個相當具有挑戰性的問題，但許多相關系統的研究已經取得了很大的進展。文獻［33］研究了物聯網中網絡負載對基于DAG 的區塊鏈共識過程的影響，利用馬爾科夫鏈模型說明基于DAG 的區塊鏈網絡的共識中的動態過程，在交易到達率波動引起的不穩定狀態下，分析了累積權重和交易確認延遲等關鍵性能指標。文獻［34］對具有代表性的基于DAG 的區塊鏈IOTA 進行了一系列全面的實驗研究，主要從性能和安全兩個方面特性出發，揭示了以下事實：1）物聯網的吞吐量高于傳統區塊鏈結構的吞吐量，但是即使是在放大配置的情況下也遠低于白皮書中報告的數千TPS；2）數據庫查詢嚴重影響物聯網的性能，甚至超過PoW 計算過程。文獻［35］介紹了一組關于IOTA的綜合性實驗研究。IOTA是DAG 區塊鏈的代表，該文主要從性能、安全性、系統魯棒性等3 個方面展示其獨特的特性，同時開發了一系列基準工具，并進行了基礎配置，以使用現實中的私有物聯網進行實驗測試。文獻［36］通過調查研究發現，基于DAG 的分布式賬本缺乏詳細的性能評估，與傳統區塊鏈相比，基于DAG 的DLT 在設計上提供了更好的性能和可擴展性，并且重點研究了DAG 區塊鏈在物聯網中的性能評估。綜上所述，DAG 區塊鏈在交易確認速度、吞吐量以及可擴展性方面相對于傳統區塊鏈有較大提升，但在安全性、技術標準、可實施性等方面較傳統區塊鏈還有較大的差距。

3 DAG 區塊鏈的優化

DAG 區塊鏈具有可擴展、不兼容等特性，因此，研究者在設計時對交易確認速度、系統吞吐量、安全性、存儲結構等方面進行優化，以使其適用于不同的應用場景。

3.1 優化交易確認速度的方法

現有優化交易確認速度的方法主要有：1）通過優化交易網絡結構增強并發性，加快交易確認速度；2）通過優化纏結共識算法加快交易確認速度；3）通過優化交易傳輸加快交易確認速度。表2 簡要結歸納了部分DAG 區塊鏈優化交易確認速度的方法。

表2 DAG 區塊鏈優化交易確認速度的方法歸納Table 2 Induction of method for optimizing transaction confirmation speed in DAG based blockchain

文獻［37-41］針對交易網絡進行優化。文獻［37］描述了DAG 區塊鏈的優勢，解決了傳統區塊鏈技術交易確認速度慢、擴展性差等問題，并表明有向無環圖是通過形成平行鏈而不是普通區塊鏈網絡中的單個鏈來優化網絡節點之間的交易速度和擴展信道寬度的。文獻［38］提出一個可擴展性模型3D-DAG。該模型由主鏈和側鏈兩層組成，分別用于維護軸心序列和提高并行性。主鏈使用經典的區塊鏈數據結構和PoW 共識機制來繼承比特幣對資產交易的強大信任和安全性，而DAG用于構建側鏈，以實現細粒度的并行交易處理。文獻［39］對基于DAG 加密貨幣的固有結構進行了分析，通過對現有基于區塊鏈的加密貨幣進行多次嘗試，突破交易處理速度的限制，產生了多種形式的解決方案，如側鏈、鏈外或數據分片，其中，基于DAG 的加密貨幣具有更快的交易發行和確認速度。然而，現有基于DAG 的加密貨幣也存在性能不穩定的問題，因此，研究者構建了基于DAG 的加密貨幣在計算參數時的通用性能模型。根據導出的模型，提出一些新的策略來提高基于DAG 的加密貨幣系統的性能，該系統鼓勵加密貨幣的參與者（包括交易者和節點）在保持賬本健壯性的同時提高交易處理速度。文獻［40］提出一種無權限區塊鏈DLattice，該區塊鏈具有一種新的雙DAG體系結構DLattice，其中每個賬戶都有自己的賬戶DAG，所有賬戶組成一個更大的節點DAG 結構。DLattice 使每個帳戶的DAG 的增長并行，且不受其他帳戶無關交易的影響。文獻［41］提出一種輕型區塊鏈體系結構V-lattice，該體系結構使用了VANET的DAG晶格結構。在V-Lattice 中，每個節點（車輛或路邊單元）都有自己的賬戶鏈，其生成的電子交易可以異步和并行地添加到區塊鏈中，資源受限的車輛可以存儲修剪后的區塊鏈，并正常執行與區塊鏈相關的操作。

文獻［42-44］針對共識算法進行優化。文獻［42］介紹了Re Tangle，這是一種新型的基于DAG 的區塊鏈加速架構，其探索了以低能耗成本執行大規模并行操作的可能性。文獻［43］對IOTA DAG 架構中的纏結連接機制進行了簡單優化，以確保所有交易在有限時間內得到驗證，并保留蒙特卡羅選擇算法的基本特征。該文提出一種新的混合小費選擇算法，解決了DAG 區塊鏈的分叉問題，并可以在有限時間內驗證所有交易。改進后的算法提高了交易入鏈的速度，但在一定程度上降低了原算法的安全性，可能導致惡意纏繞鏈的現象，如雙花攻擊。文獻［44］指出，有向無環圖正成為分布式賬本技術替代傳統區塊鏈體系結構的一個有效的替代方案，通過對IOTA DAG 架構中纏結連接機制改進，能夠確保所有交易在有限時間內得到驗證。

文獻［45-46］針對數據交易傳輸過程進行優化。文獻［45］闡述了區塊鏈和DAG 有向無環圖的基礎及其演變過程，DAG 試圖解決區塊鏈中的大多數問題，并為物聯網產業構建一個穩定的系統。其中，MAM 是一種輔助數據通信協議，其增加了通過DAG 釋放和訪問加密數據流（如RSS）的能力。文獻［46］提出了拜占庭共識協議Blockmania，其中，節點發出的塊形成一個有向無環圖，隨后由每個節點分別解釋，以確保安全、活躍和最終的一致性，由于解釋由每個節點獨立執行，因此不需要跨節點在消息中攜帶證據，從而提高了效率。

3.2 優化系統吞吐量的方法

優化DAG 區塊鏈系統的吞吐量可以進一步增強其應對短時高并發數據的處理能力，更加適用于物聯網等環境。目前在該方向中有分片并行計算、修改區塊鏈結構、優化共識機制這3 種方法。表3 簡要歸納了DAG 區塊鏈優化系統吞吐量的方法。

表3 DAG 區塊鏈優化系統吞吐量的方法歸納Table 3 Induction of method for optimizing system throughput in DAG based blockchain

文獻［47-48］提出分片并行計算方法。文獻［47］設計了一個新的區塊鏈系統DEXON。首先，為區塊鏈提供了一個高度可擴展、采用任意數量的單鏈分片框架，并將該框架轉換為塊晶格數據結構，實現了高可擴展性和低交易確認延遲，且具有漸近最優的通信開銷。塊晶格結構是由許多單鏈組成的有向無環圖。然后，使用總排序算法在區塊鏈上達成共識，從而確保所有用戶認可所有區塊的排序。由于單鏈可以同時增長，因此DEXON 的吞吐量可以很容易地擴展。文獻［48］則構建一個并行挖掘模型來提高基于狀態的區塊鏈的TPS。

文獻［13-14，49-51］針對DAG 區塊鏈結構進行優化。除了上文提到的Conflux 協議［13-14］之外，文獻［49］分析了比特幣和基于區塊鏈的比特幣NG 系統的特點，提出了一種改進的區塊鏈系統實現方法，用圖形數據結構代替原有的區塊鏈結構GraphChain。GraphChain是一種特制的數據結構，并非典型的DAG，其中每個區塊代表一筆交易，同時包含交易員的余額狀態，通過將原有爭奪采礦者的方式改為選舉和平行開采來提高資源利用率。文獻［50］提出了一種鏈的替代結構，由帶區塊的有向無環圖組成，其允許以更高的速率運行。DAG 結構是通過允許塊引用多個前輩而創建的，并且需要交易接受規則，這些規則甚至包含來自看似沖突的塊的交易。該規則從DAG 內選擇主鏈，然后有選擇地將鏈外區塊的內容合并到日志中，前提是它們與以前包含的內容不沖突。因此，系統可以容忍傳播時間較長的較大數據塊，并且可以增加交易量。文獻［51］提出了收斂有向無環圖CDAG 以替代其他區塊鏈協議中使用的鏈和DAG 結構。CDAG 允許對分類賬進行多次并行更新，并在下一步將其聚合，從而保證了區塊鏈的最終一致性。CDAG 將更新劃分為不相交的交易桶，以防止沖突塊的生成，并將時間劃分為多個時隙，以便為它們在網絡中傳播提供足夠的時間，通過多個同步更新提高吞吐量。

文獻［52-54］針對共識機制進行優化。文獻［52］介紹了一個新型亞穩態無領導拜占庭容錯協議族。這些協議在拜占庭對手面前提供了強大的概率安全保障，同時并發性使它們能夠實現高吞吐量和可擴展性。與依賴工作量證明的區塊鏈不同，在Avalanche 協議的網絡系統中，如果有人想在2 筆交易中花費同一筆錢，那么鑒于Avalanche 協議本身的屬性，無法在這2 筆交易中做出選擇，從而會導致這筆錢丟失，間接地懲罰了嘗試攻擊者。因為Avalanche 協議的重點只是達成共識，并不是做出選擇。文獻［53］提出的Perlin 是一個強化并推廣了Avalanche 一致性協議的分布式賬本，其在有向無環圖上基于亞穩態機制構建部分同步拜占庭容錯協議，以實現極高的吞吐量和可擴展性。文獻［54］提出一種基于DAG 的聯盟區塊鏈拜占庭容錯共識算法Jointgraph，以提高安全性和效率。在Jointgraph 中，交易被打包到事件中，并由不少于2/3 的所有成員驗證。在該文設計中，引入了一位監督人以監督成員的行為，提高共識效率。

3.3 優化系統安全性的方法

一些研究者注重于優化DAG 區塊鏈的系統安全性，即提高DAG區塊鏈系統對于抵抗各種攻擊的能力。他們主要從DAG 區塊鏈系統安全性分析、優化協議和共識機制提高安全性、修改DAG 區塊鏈架構提高安全性等3 個方面進行系統安全性優化。表4 簡要歸納了DAG 區塊鏈優化系統安全性的方法。

表4 DAG 區塊鏈優化系統安全性的方法歸納Table 4 Induction of method for optimizing system security in DAG based blockchain

文獻［55-58］針對系統安全性進行分析。文獻［55］指出，在設計基于DAG 的區塊鏈系統時，基于Tangle的結構是較好的解決方案，但性能提升可能會帶來潛在的安全風險。該文提出3 種綜合評估的攻擊類型，即寄生蟲攻擊、雙花攻擊和混合攻擊，以分層建立攻擊策略。在此基礎上，對不同的攻擊進行了多維度分析。文獻［56］考慮了基于DAG 的DLT 不同體系結構在物聯網領域應用的適用性，并著重考慮賬本的防篡改安全性。該文分析了一種常見的攻擊場景——“寄生蟲鏈攻擊”，此攻擊在于破壞IOTA 基金會的基于DAG 的系統中的分類帳的不可逆性，同時使用馬爾科夫鏈模型，研究IOTA的核心提示選擇方法針對該攻擊的漏洞，并對算法進行擴展，以提高該場景中賬本的彈性，其中重點討論了基于有向無環圖的DLT 的不同體系結構。文獻［57］研究了最典型的DAG 共識機制Tangle，并分析網絡負載對區塊鏈性能和安全性的影響。考慮到網絡負載的不穩定，首先提出一個馬爾科夫鏈模型描述動態負載條件下DAG一致性過程的行為，然后利用一個隨機模型分析在不同的網絡負載情況下成功進行雙花攻擊的概率。文獻［58］對基于DAG 的區塊鏈架構進行分析，包括Nxt、IOTA、Orumesh、DagCoin、Byteball、Nano和XDAG，比較基于維護分類賬的功能數據結構、共識算法、交易驗證、分類賬大小、可擴展性和流行性，并提取各種基于DAG 的區塊鏈的最佳特征，通過對上述基于DAG 的區塊鏈進行對比分析，制定出一個安全的DAG 區塊鏈架構框架。

文獻［59-63］針對協議和共識機制進行優化。文獻［59］設計了一個基于壓縮有向無環圖高效、安全的區塊鏈協議CoDAG。在該協議中，區塊按級別和寬度進行組織，新生成的區塊將被適當放置，并指向上一層的區塊，使其成為一個連接良好的通道，并且網絡中的交易將在確定的時間段內確認，同時協議保持簡單的數據結構。文獻［60］提出了一種新的交易驗證機制。該機制依賴于參與節點合作驗證新交易，在將交易包附加到Tangle之前，節點應選擇2個最新提示并被批準。在基于DAG 的分散環境中，必須構建一個健壯的選擇提示算法。設計這種算法的目的是推動節點選擇未經批準的交易包，并解決檢查交易、雙重支出和偽造交易的沖突。文獻［61］指出，基于有向無環圖的模型旨在通過采用與BoStand 鏈中使用的不同協議來避免交易費用。該模型使用馬爾科夫鏈蒙特卡羅算法更新分布式賬本。然而，關于協調器節點集中化的問題仍然存在，并且選擇算法的經濟激勵不足。該文提出了一種輕型高效的分布式賬本更新算法，通過貝葉斯推理，只考慮每一步的子角度。文獻［62］介紹了一種新的共識協議STAIR，實現基于DAG 的無信任系統中的快速協商一致。STAIR 使用了一種在每個節點上創建局部塊DAG 的新方法x-DAG，其構建StakeDag 框架，根據參與者的利害關系將參與者區分為用戶和驗證器，其中兩者都可以創建和驗證交易塊。與StakeDag 的DAG不同，x-DAG 確保每個新塊都必須有來自用戶和驗證者的父塊，以實現更安全的效果。文獻［63］從DAG 的特殊結構出發，采用POS-PBFT 作為主鏈共識算法，將鏈式共識算法與DAG 相結合，提出一種區塊鏈新模型SDAG。該模型提高了系統的擴展性，并且使交易數據的一致性和時序性優于鏈式結構。

文獻［64-67］針對DAG 區塊鏈架構進行優化。文獻［64］提出了一種新型的DAG 結構IDAG，其工作原理與DAG 類似，但沒有包含結果節點，而是包含因果效應節點。IDAG 允許以直觀和嚴格的方式演示交互，有助于區分效應變異背后的因果機制和非因果機制。該文通過實驗研究了如何以經驗評估節點相互作用，以及如何在保證區塊鏈整體性能的基礎上總結區塊鏈接規律。文獻［65］描述了一個輕量級、有彈性的分布式賬本系統DLedger，通過將DLedger 安裝到存儲受限的物聯網設備中，當供應的空間接近耗盡時，實體可以經過修剪一段時間后保持未確認的所有記錄來減小本地DAG的大小，并取出遠離尾部記錄的歷史確認記錄。利用DAG 和PoA，即使是受限制的設備也可以通過“挖掘”自己的記錄并得到確認來參與，從而提高數據的可用性、完整性和真實性。文獻［66］利用形式化方法設計了一種塊DAG 架構，并且提出了維護該架構所需的協議。DAG 區塊本質上是將塊之間的關系用Lamport編碼，且任何確定性拜占庭容錯協議都可以嵌入到這個塊DAG 中，同時保持其安全性和靈活性。文獻［67］介紹了一個具有三維賬本架構的安全、高性能區塊鏈系統Spacechain，以實現區塊鏈在物聯網中的開放性。首先，設計一個具有新穎數據結構的三維體系結構，使用宏塊構造有向無環圖；然后，將許多微型塊連接到DAG區塊鏈形成第3 個維度，從而應對物聯網網絡的異構性和可擴展性；最后，提出空間鏈的三維貪婪最重觀測子樹（3D-GHOST）一致性機制，以提高安全性和網絡性能。

3.4 優化存儲結構的方法

除了DAG 區塊鏈共識機制和架構，DAG 區塊鏈交易的存儲和查找也是限制DAG 區塊鏈系統性能的重要問題，一些學研究者對此進行了研究。表5 簡要歸納了DAG 區塊鏈優化存儲結構的方法。

表5 DAG 區塊鏈優化存儲結構的方法歸納Table 5 Induction of method for optimizing storage structure in DAG based blockchain

文獻［68］提出一種基于有向無環圖的新通證設計模型，允許在不檢查整個區塊鏈的情況下有效地探索通證歷史。該模型將通證的每個狀態從過去關聯到最新，并涵蓋通證之間關系的表達式，例如合并和拆分，這不僅提高了跟蹤效率，而且還有助于跟蹤溯源，包括合并、拆分、分支通證歷史。

文獻［69-71］針對數據存儲方法進行優化。文獻［69］提出了一種基于輕量級有向無環圖的區塊鏈LDV，并提出了基于社會的數據約簡方法。具體而言，每個節點只在感興趣的主題組中存儲感興趣的數據，而忽略不感興趣的數據。為了避免在具有大量數據的大型組中產生巨大的存儲成本，進一步提出了組內歷史數據剪枝方法，通過減少每個節點中存儲的重復數據數量來滿足存儲需求。文獻［70］為物聯網區塊鏈設計一種高效的共識算法Teegraph，其包括基于Gossip協議的消息通信機制，以生成用于高效共識過程的基于有向無環圖的數據結構。當沒有創建新交易時，Teegraph 就像一種節省資源的機制，可以減少通信開銷并節省存儲空間。文獻［71］基于改進的區塊鏈方法，利用有向無環圖，為NMG 提出一個安全的隨機能源管理框架，使用分散透明的區塊鏈技術提高網絡安全性并降低風險，從而消除金融欺詐，降低總運營成本。為解決傳統區塊鏈模型中由于哈希地址計算的存儲和高復雜性問題，該文提出一種基于DAG 方法的改進區塊鏈技術，此外，還設計新的數據恢復技術，以適當精度恢復數據。

唯一地址檢查是確保每個用戶帳戶（錢包）的每筆交易都與唯一的私鑰/公鑰對相關聯的基本過程，其中公鑰和私鑰將分別用作交易的地址和簽名。目前，基于DAG 的區塊鏈系統通常采用基于數據庫的方法，依靠耗時耗空間的數據庫查詢來執行唯一地址檢查過程。文獻［72-74］針對此問題進行研究。文獻［72］設計了一個嵌入IOTA 輕量級客戶端的布谷鳥過濾器，以幫助加速地址檢查過程。這種設計基于這樣一種假設，即在快照之后可以重用地址，快照會定期執行以減少纏結大小。該文為當前混亂中的地址構建bloom 過濾器，以保證唯一性。然而，這種假設是不現實的，使得這種設計很難在實踐中部署。文獻［73］提出了一種稱為ABACUS 的方法，利用兩級分區bloom 過濾器執行地址檢查。分區bloom 過濾器負責根據其前綴存儲所有已用地址，每個分區bloom 過濾器的一個SBF（子bloom過濾器）保存在內存中并寫入緩沖區。然而，這種方法的重點是優化bloom 過濾器更新操作，以加速唯一地址檢查。此外，ABACUS 假設所有地址檢查過程都在支付帳戶內執行，而忽略地址的時間位置。文獻［74］提出了一種熱感知細粒度bloom 過濾器HF-BF，用于對基于DAG 的區塊鏈進行唯一地址檢查。BFU 是細粒度bloom 過濾器散列函數，為了管理BFU 的大存儲空間并盡可能減少用于檢查地址的I/O 數量，該文設計了一種自適應BFU 管理方案，在內存和磁盤之間調度活動BFU。但是此解決方案具有一定的安全性風險，由于地址未存儲，一旦區塊鏈網絡發生錯誤，交易就無法被追溯，從而導致交易無法確認。

4 DAG 區塊鏈的應用

DAG 區塊鏈通常應用在節點計算能力不足、對交易處理時間要求高而對單筆交易可信性要求不嚴格的場景中。本節主要介紹DAG 區塊鏈目前在數據管理、數據共享以及數據安全等場景中的應用。

4.1 數據管理

DAG 區塊鏈因其速度更快、無交易費用同時也無需挖礦等特點，被廣泛應用于物聯網等數據并發量大但設備算力不足的場景中。

文獻［75］對物聯網環境的特點，包括其安全性和性能要求，以及區塊鏈技術的進展進行了系統研究，并且提出一種基于DAG 的區塊鏈來解決區塊鏈在物聯網中應用面臨的一些重大挑戰。文獻［65］描述了一個輕量級、有彈性的分布式賬本系統DLedger。DLedger在一個有向無環圖上構建分類賬，而不是一個單一的區塊鏈。DLedger沒有使用計算密集型工作量證明，而是使用身份驗證證明（PoA），其輕量級操作對物聯網友好以達成共識。此外，DLedger建立在一個名為命名數據網絡（NDN）的以數據為中心的網絡上，這有助于異構物聯網中的對等數據傳播。文獻［76］提出一種應用層協議，稱為流式數據支付協議SDPP。該協議規定，數據提供者可以發送自動發票，數據消費者可以提供簽字收據，以便將數據存儲在不可變的分布式賬本上，用于審計和爭議解決。SDPP 是第一個針對物聯網類型流式數據的集成數據支付記錄協議，其利用了傳統的TCP/IP 以及創新的基于區塊鏈和DAG 的分布式賬本技術。文獻［77］提出一種基于有向無環圖的分布式賬本技術PowerGraph，及其在智能電網中生成、驗證和確認電力交易的方案。由于基于DAG 的分布式賬本不需要生成用于確認的數據塊，PowerGraph 的每筆交易都會單獨經歷驗證和確認過程。此外，PowerGraph中能夠跟蹤能源交易以及其他各種類型的交易，實現智能電網網絡中交易的完全跟蹤。

4.2 數據共享

在大規模網絡環境下難以實現去中心的數據共享，而DAG 區塊鏈可以在一定程度上解決這一問題。為了應對使用異構設備管理大規模物聯網網絡的挑戰，文獻［78］提出一種有向無環圖區塊鏈增強的用戶自治頻譜共享模型。由于所提出的一致性規則與系統效用密切相關，用戶群智能在區塊鏈一致性過程中逐漸達到收斂點。此外，常用的分布式數據共享方法還包括邊緣計算、聯邦學習等。

4.2.1 邊緣計算

文獻［79］提出一種稱為安全無人機網絡邊緣服務（SDNES）的創新架構，該架構將邊緣計算和基于DAG的區塊鏈集成到無人機網絡中，為無人機提供實時可靠的網絡服務，并有效避免惡意行為。文獻［80］提出基于DAG 的分布式邊緣技術，旨在為物聯網系統提供安全和隱私以及新的附加功能，解決物聯網系統的現有問題，同時并使用IOTA 的屏蔽認證消息（MAM）成功地實現了物聯網傳感器數據的TAM 認證和安全傳輸，確保了數據機密性和數據認證。文獻［81］提出一個跨鏈框架來集成多個區塊鏈，以實現高效、安全的物聯網數據管理，并基于Hyperledge Fabric 和IOTA Tangle實現了該框架的原型。在此過程中，一個挑戰是物聯網區塊鏈的可擴展性。由于區塊鏈上的每個條目都需要所有網絡節點達成共識，因此基于單一架構的區塊鏈無法很好地擴展。為了解決這個問題，該文使用有向無環圖數據結構引入纏結，并將網絡分解為多個類似于“側鏈”的較小子纏結。然后，將這些側鏈網絡連接起來，形成一個分散的網絡。文獻［82］研究使用了一個基于物聯網和區塊鏈技術的集成框架，該框架結合了有向無環圖配置的無線傳感器網絡（Wireless Sensor Network，WSN）和用于水污染源實時追蹤的GIS工具。這項研究的新框架使用基于區塊鏈的技術、DAG 配置中的無線傳感器網絡和GIS 技術從灌溉取水數據中追蹤污染路徑。區塊鏈和GIS 工具被用于追蹤繪制的灌溉單元的污染，并在空間上識別灌溉進水口的上游污染單元。文獻［83］為IIoT 提供了一個基于信用的共識機制的區塊鏈系統。該文提出一種基于信用的物聯網設備工作量證明機制，可以同時保證系統安全和交易效率，其系統基于有向無環圖結構區塊鏈構建，利用異步一致性模型提高了系統吞吐量，在性能上比比特幣式區塊鏈更高效。文獻［84］介紹了一個可分區的區塊鏈Vegvisir，用于網絡連接有限、功率受限的物聯網環境，其為一個經過許可的、有向無環圖結構的區塊鏈，可用于創建一個共享的、防篡改的數據存儲庫，以跟蹤數據來源。文獻［85］提出了一個分片有向無環圖區塊鏈DagGridLedger，為可信的DNS 管理提供了可擴展的大數據體系結構，其將區塊鏈分片和DNS 解析器端的DAG 技術相結合，能夠增強大規模DNS 系統的安全性和穩定性。

4.2.2 聯邦學習

文獻［86］提出了一種基于模型更新的有向無環圖聯邦學習中去中心化方法，客戶端不需要訓練統一的全局模型，而是專注于本地數據，同時根據各自數據的相似性使用其他客戶機的模型更新。這種特性隱式地出現在基于DAG 的通信和模型更新的選擇中。與傳統基于DAG 的共識機制相比，其DAG 模型中的交易不屬于絕對類別“有效”或“無效”。為解決聯邦學習（Federated Learning，FL）中的設備異步和異常檢測問題，同時避免區塊鏈造成的額外資源消耗，文獻［87］構建一個基于DAG 的區塊鏈系統授權聯邦學習的框架DAG-FL。首先從三層架構詳細介紹了DAG-FL，然后設計了運行在不同節點上的DAG-FL 控制和DAG-FL更新2 種算法，最后詳細闡述了DAG-FL 共識機制的運行過程。該文作者還在文獻［88］中介紹了一個基于DAG的區塊鏈系統授權聯邦學習的框架，并建立了一個泊松過程模型，討論了在不同的聯邦學習任務中如何設置部署參數以保持DAG-FL 的穩定。

4.3 數據安全

目前DAG 區塊鏈應用于數據安全的場景主要有訪問控制和隱私保護2 種。

4.3.1 訪問控制

文獻［89］推出了一個基于區塊鏈的物聯網系統B-IoT，該系統包含基于信用的共識機制。為了保護敏感物聯網數據的機密性，該文設計一種數據權限管理方法來規范對傳感器數據的訪問。同時，基于有向無環圖結構的區塊鏈構建系統，得到較比特幣類型的區塊鏈更高的效率。文獻［90］介紹了一個許可的區塊鏈系統CAPER，用于支持協作分布式應用程序的內部和跨應用程序交易。在CAPER 中，區塊鏈分類賬形成為一個DAG，其中每個應用程序只訪問和維護自己的分類賬視圖，包括其內部和所有跨應用程序交易。CAPER 還引入了3 種一致性協議，用于在具有不同內部一致性協議的應用程序之間全局排序跨應用程序交易。文獻［91］介紹了一種無信任系統的通用模型StakeDag，其目的是在基于DAG的無信任系統中實現PoS 共識。在該模型中，參與者通過他們的利益或信任來區分用戶和驗證器。用戶是沒有假定信任的正常參與者，而驗證器是具有已建立信任的知名參與者。

4.3.2 隱私保護

文獻［92］提出并調查了物聯網的主要安全問題。除了用于網絡、通信和管理的協議外，還審查并分類了物聯網分層體系結構方面的常見安全問題，并提出了一種DAG 區塊鏈解決方案。文獻［93］指出，基于DAG 的分布式賬本可以通過設計來解決性能和可擴展性問題。首先對分布式賬本技術在物聯網中的應用以及這種分散系統的性能進行全面的評估；然后在對不同基于DAG 的分布式賬本技術進行簡要描述，同時對物聯網進行了詳細的技術概述；最后利用物聯網協議并遵循關注點分離（Separation of Concerns，SoC）設計原則，提出一種可擴展的交易式智能家居基礎設施。文獻［94］通過利用基于有向無環圖的DLT 并遵循SoC 設計原則，提出一種可擴展的交易式智能家居基礎設施，并對40 個家庭節點進行了實驗驗證。結果表明，此解決方案具有高TPS/CTP和良好的可擴展性，以及在物聯網環境中重要的數據安全和小額支付方面的良好性能。文獻［95］針對電動汽車需要的充電樁數量有限且充電比加油更耗時的情況，提出一種基于DAG 區塊鏈和雙拍賣機制的安全高效的計費調度系統，同時設計一個輕量級計費調度框架，該框架集成了DAG 區塊鏈和現代密碼技術，能夠確保在執行調度和完成交易期間的安全性和可擴展性。

5 未來研究展望

DAG 區塊鏈吞吐量高、交易處理速度快等特性使其與傳統區塊鏈技術的優劣對比十分明顯，但在單筆交易安全性上卻存在不足。未來研究可從以下4 個方面進行展開：

1）研究能夠落地應用的高效DAG 區塊鏈技術。盡管目前針對DAG 區塊鏈的研究有較大進展，但是部分協議距離落地應用還存在一定距離，并且現有的DAG 區塊鏈技術形式多樣，難以統一且未形成標準，在未來這些方面還需要完善。

2）優化存儲結構，加快交易查找速度。在DAG區塊鏈共識過程中，數據庫交易查找嚴重影響區塊鏈性能，如何創建高效的數據索引結構加快交易查找速度，以及如何減少共識過程中的交易查找數量，是優化DAG 區塊鏈的重要研究方向。

3）優化共識機制，提高DAG 區塊鏈抗攻擊能力。目前采用DAG 區塊鏈會讓交易序列化變得復雜，“雙花”問題難以得到解決，且DAG 區塊鏈中的交易確認是概率可信，難以實現最終一致性的共識。因此，改進DAG 區塊鏈共識機制，提高DAG 區塊鏈抗攻擊能力是未來重要的研究方向。

4）探索DAG 區塊鏈在工業互聯網等領域的應用。工業互聯網是新一代信息通信技術與工業經濟深度融合的新型基礎設施、應用模式和工業生態。工業互聯網具備和物聯網相同的計算能力差、數據高并發等問題，因此，DAG 區塊鏈在工業互聯網等領域，尤其是在工業互聯網產品溯源、故障處置、供應鏈等方面具有廣泛的應用前景。

6 結束語

本文從DAG 區塊鏈的發展、評估、優化、應用等方面出發，闡述DAG 區塊鏈技術的研究進展，同時指出現有DAG 區塊鏈技術形式多樣未能統一，并且其商業化應用仍存在技術難以落地和安全性問題等諸多不足。在目前DAG 區塊鏈技術不斷創新發展且新應用大量涌現的背景下，未來將對區塊鏈架構、存儲結構、共識機制等方面進行深入研究，探索提高DAG 區塊鏈系統運行效率和安全性的有效方法。