摘要
火幣區塊鏈應用研究院從技術角度對基于有向無環圖（DAG）數據結構的分布式賬本技術進行研究，并通過對典型代表項目IOTA的具體技術測試，主要得到以下研究結果:
DAG技術與狹義的區塊鏈技術相比，有其創新之處，理論上在不考慮作惡情況下可實現高可擴展性和高去中心化，因此存在一些安全隱患。
DAG項目往往以偏中心化的方式來實際運行，即降低去中心化程度來提高安全度，但同時其交易速率并沒有接近理論上限。
采用基于VPS（CPU進行PoW）的40個節點網絡對代表性項目IOTA進行交易壓力測試，可發現TPS很低：可達到的最優結果為4.19。
經分析，其性能瓶頸目前主要還在于硬件的算法實現本身。如果采用FPGA等其他方式來實現，應可進一步挖掘出DAG的性能潛力。
同時，為保持良好的交易處理能力，應建立足夠規模的節點網絡。
報告正文
1. 引言
區塊鏈是一種分布式賬本技術，而分布式賬本技術卻不局限于“區塊鏈”這一種技術形式。在數字經濟發展的浪潮中，為了改進原有技術、滿足更多的實際業務應用場景，更多的分布式賬本技術正在被探索和應用當中。有向無環圖（Directed Acylic Graph，以下簡稱“DAG”）是其中的代表之一。
DAG技術以及它背后的設計思想是什么？實際應用效果如何？我們嘗試通過對DAG技術進行深層解析以及對代表性項目IOTA的實際測試運行獲得分析結論。
另外需要注意的是：測試得到的指標數據結果不是也不應被視為是對IOTA平臺或項目最終效果的證明或確認。特此聲明。
2.主要結論
經過研究與測試分析，我們得到以下主要結論及技術建議：
DAG技術與狹義的區塊鏈技術相比，有其創新之處，理論上在不考慮作惡情況下可實現高可擴展性和高去中心化，因此存在一些安全隱患。
DAG項目往往以偏中心化的方式來實際運行，即降低去中心化程度來提高安全度，但同時其交易速率并沒有接近理論上限。
采用基于VPS（CPU進行PoW）的40個節點網絡對代表性項目IOTA進行交易壓力測試，可發現TPS很低：可達到的最優結果為4.19。
經分析，其性能瓶頸目前主要還在于硬件的算法實現本身。如果采用FPGA等其他方式來實現，應可進一步挖掘出DAG的性能潛力。
同時，為保持良好的交易處理能力，應建立足夠規模的節點網絡。
3.DAG介紹
3.1.DAG原理簡介
DAG（Directed Acyclic Graph，有向無環圖）是一種數據結構，表示的是一張有向圖，并且在這個圖中，從任意頂點出發都無法回到該點（無環），如圖所示：
基于DAG技術的分布式賬本（以下簡稱DAG）技術在近年來被提出后，被很多人認為有希望替代狹義上的區塊鏈技術。因為DAG在設計時的目標就是保留區塊鏈的優點并且改進區塊鏈的缺點。
和傳統線性區塊鏈結構不同，以IOTA為代表的分布式賬本平臺的交易記錄之間形成的是一個有向無環圖的關系結構，如下圖所示。
3.2.DAG特性
由于采用了不同于以往塊鏈式的數據結構，基于DAG的分布式賬本技術，擁有高可擴展、高并發等特性并適用于物聯網場景。
3.2.1.高可擴展性、高并發性
傳統線性區塊鏈（如以太坊）的數據同步機制是同步的，這可能造成網絡的擁堵。DAG 網絡采用異步通訊機制，允許并發寫入，多個節點可以按照不同的節奏同時交易，而不必有明確的先后順序，因此同一時刻網絡的數據可能不一致，但最終會是同步的。
3.2.2.適用于物聯網場景
在傳統的區塊鏈網絡中，每個區塊中有很多筆交易，礦工打包好后統一發送，涉及到多個用戶；而在 DAG 網絡中并沒有“區塊”的概念，網絡的最小單元是“交易”，每筆新的交易需要驗證前面兩筆交易才能進行，這樣DAG網絡并不需要礦工傳遞信任，轉賬無需手續費，這使得 DAG 技術適用于小額支付。
4.技術思路分析
不可能三角（trilemma），或被稱為“三難困境”，是指在特定的情形下，只能選擇三個有利選項中的兩個或者是在三個不利選擇中必須選擇一個。這一類選擇困境在宗教、法律、哲學、經濟學、企業管理等多種領域均有相關案例。區塊鏈也不例外。區塊鏈中的不可能三角為：可擴展性（Scalability）、去中心化（Decentralization）、安全性（Security）這三者中只能選擇其中兩個。
如果按照這種思路來分析DAG技術，根據前文介紹，那么無疑DAG已占據了去中心化、可擴展性這兩個方面。DAG的去中心化和可擴展性可認為是一體兩面的，因為基于DAG數據結構帶來的異步記賬特性，同時實現了高度的參與網絡節點的去中心化和交易的可擴展性。
5.存在問題
既然是數據結構上的特性同時帶來了去中心化和可擴展性，所以按照不可能三角的理論來推測，安全性會是一個隱患。但由于DAG是一個比較創新、特殊的結構，是否也可比較完美的實現安全性？目前從實際效果來看并非如此。
5.1.雙花問題
DAG 異步通訊的特性為雙花攻擊創造了可能。例如，攻擊者在網絡的兩個不同的位置添加了兩筆沖突的交易（雙花），交易在網絡中不斷向前驗證，直到它們出現在同一筆交易的驗證路徑上，網絡才會發現沖突，這時這兩筆交易匯聚成的共同祖先節點才能判斷哪一筆交易是雙花攻擊。
而如果將交易路徑控制的過短又會存在類似“Blowball”的問題：當極端情況下絕大多數交易都較為“懶惰”（Lazy Tip）、只參考早期交易時，交易網絡會形成一個以少數早期交易為核心的中心拓撲。這對依賴于交易的不斷增加而提高網絡可靠性的DAG來說，也不是一件好事。
因此，目前對于雙花問題，需要綜合考慮實際情況進行設計。不同的DAG網絡有各自的解決方案。
5.2.影子鏈問題
由于存在雙花的潛在問題，當攻擊者可以構建出足夠數量的交易后，就可能從真實的網絡數據中分叉出一個欺詐性分支（影子鏈），其中包含著雙花交易，然后將這個分支合并到DAG網絡中，特定情況下這個分支有可能取代原有交易數據。
6.目前改進方案簡介
目前項目主要都是通過犧牲一部分DAG的原生特性來保證安全性。
IOTA項目中采用了馬爾科夫鏈蒙特卡洛（Markov chain Monte Carlo，以下簡稱MCMC）的方式來解決該問題。IOTA為交易引入了累積權重（Cumulative Weight）的概念用來記錄該筆交易被引用的次數，目的是表示其交易的重要性。MCMC算法通過對累積權重進行加權隨機游走，選擇目前網絡中已存在的交易作為新增交易的參考。即被參考越多的交易路徑越容易被算法選中。游走策略在1.5.0版本中也進行了優化，可將交易拓撲的“寬度”控制在一個合理范圍內，使得網絡更加安全。
但在平臺啟動初期，由于參與節點和交易數量均有限，所以很難避免一個惡意機構通過大量節點發送出海量的惡意交易使得整個網絡受到影子鏈的攻擊。因此就需要一個權威的仲裁機構來判定交易的有效性。在IOTA中，這一節點為Coordinator，它會定期對目前交易數據網絡（Tangle）進行快照；包含在快照中的交易即被確認為有效交易。但Coordinator并不會一直存在。隨著整個網絡的運行和成長，IOTA會在未來某一時間取消掉Coordinator。
Byteball改進方案的特色在于其對于見證人（witness）和主鏈的設計。因為DAG的結構帶來了很多偏序關系的交易，而要避免雙花則需要對這些交易建立一個全序關系，形成一個交易主鏈。主鏈上較早的一筆交易作為有效交易。而由知名用戶或機構擔任的見證人通過不斷的發送交易確認其他用戶交易，從而形成主鏈。
以上方案也可能會對基于DAG結構的平臺帶來不一樣的改變。以IOTA為例，因為引入了Coordinator，一定程度上降低了去中心化特性。
7.實際運行情況
7.1.正面效果
采用了除了解決安全問題之外，以上方案還可以在一定程度上解決智能合約問題。
由于DAG原生特性帶來的兩個潛在問題：（1）交易時長不可控，當前通過請求重發的機制需要在客戶端進行一些較為復雜的超時機制設計，希望能夠存在更簡單的一次性確認機制；（2）不存在全局排序機制，導致系統支持的操作類型受限。因此在基于DAG技術的分布式賬本平臺上，較難實現出圖靈完備的智能合約體系。
為了保證智能合約可以運行，需要一個機構來完成上述工作。目前的Coordinator或主鏈可實現類似的效果。
7.2.負面效果
作為最為直觀的指標之一，DAG的TPS在理論上應該是可以無限的。如果把IOTA平臺的最大TPS比喻為一個工廠的產能，那么日常運行的TPS就是工廠的日常產量。
對于最大TPS，2017年4月份的IOTA壓力測試顯示，網絡具有112CTPS和895TPS的交易處理能力。這是在一個由250個節點所組成的小型測試網絡上得到的結果。
對于日常運行的TPS，從目前可公開獲取的數據看到，近期主網平均TPS為8.2左右，CTPS（每秒確認交易數量）為2.7左右。
而測試網近期的平均TPS為4左右，CTPS為3左右。
數據來源 discord bot: generic-iota-bot#5760
這是否與Coordinator的存在有關？需要實際測試來進一步論證。
8.實測分析
公開測試網的運行統計數據與諸多因素都有關系。為了進一步分析，我們繼續以IOTA平臺為例，搭建一個私有測試環境進行技術實測分析。
8.1.測試架構
我們本次測試搭建的各組件間關系如下圖所示。
其中：
為了避免主網或測試網上的其他因素對測試結果的影響，我們搭建了一個40個節點的小型私有IOTA測試網絡。構建過程參考“Private IOTA Testnet”項目（https://github.com/schierlm/private-iota-testnet.git），并對其中使用的IRI（IOTA Reference Implementation）版本更新為了最新的v1.5.0版本。此外，在測試過程中，使用該工具提供的Coordinator模擬工具，定期生成快照對交易進行確認。
使用基于Python的開源負載測試工具Locust（https://locust.io/），以便控的發送出交易數據。在開始測試后，隨機向所有私有網絡中的節點發送出交易數據。
在節點啟動時，增加“--zmq-enabled”參數，以便啟動IOTA的ZeroMQ支持，將節點得到的交易數據中通過消息隊列方式發送給觀測端。在觀測端使用ZeroMQ事件解析腳本（https://github.com/lunfardo314/tps_zmq.git）觀察節點交易數據情況。
8.2.測試硬件環境
服務器采用亞馬遜AWS EC2 C5.4xlarge: 16 核 3GHz, Intel Xeon Platinum 8124M CPU，32GB內存，服務器間為10Gbps局域網網絡，通訊延遲（ping）小于1ms，操作系統為Ubuntu 16.04。
8.3.測試場景及結果分析
8.3.1.默認PoW難度值
雖然沒有“礦工”等概念，但在發送交易前，IOTA節點仍然需要進行工作量證明，以避免發送大量交易淹沒網絡。PoW難度值（Minimum Weight Magnitude）與比特幣類似，是PoW的結果應得出“9”的位數，其中9在IOTA采用的三進制中為“000”。IOTA難度值可在節點啟動前進行設置。
目前對于生產網絡，IOTA的難度值設置為14；測試網設置為9。因此，我們首先采用測試網的默認難度值9來進行測試，得到以下測試結果。
由于每個IOTA的交易包（bundle）中會包含多筆transfer，因此實際處理的TPS會比發送速率高。但通過執行解析zmq的腳本可觀察到，目前TPS很低。而另一個現象是，每秒可發送成功的請求數量也很低。
經過分析，原因在于測試使用的是VPS，所以在PoW時，主要使用CPU來進行運算，因此交易速度主要受發送速度的影響。
8.3.2.降低PoW難度值
將難度值降低為1后重新進行測試，得到以下結果。
從結果可看到，降低難度后，TPS會有所上升。所以目前IOTA項目的TPS并沒有到達Coordinator所在的瓶頸，而主要是發送交易的客戶端本身硬件以及網絡等方面原因導致。IOTA社區目前在研發基于FPGA的Curl算法實現以及CPU指令集優化等工作。我們的測試結果也印證可通過這一方式繼續挖掘DAG平臺的性能潛力。
8.3.3.減少測試網絡節點數量
由于DAG的特性，平臺實際TPS和網絡節點數量可能也存在著關系。因此在難度值保持為1的情況下，將網絡節點數減為10后重新進行測試，得到以下結果。
從結果可看到，隨著節點數降低，實際處理TPS也有所下降，而且低于發送速率。這說明在DAG環境下，維持足夠規模節點將有助于交易的處理。
9.參考資料
https://www.iota.org/
https://en.wikipedia.org/wiki/Trilemma
https://blog.iota.org/new-tip-selection-algorithm-in-iri-1-5-0-61294c1df6f1
https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo
https://byteball.org/
https://www.iotachina.com/iota.html
https://www.iotachina.com/iota_tutorial_1.html
本報告由火幣區塊鏈研究院出品，作者：袁煜明、胡智威
