摘要：有向無環(huán)圖，以下簡稱是其中的代表之一。的去中心化和可擴(kuò)展性可認(rèn)為是一體兩面的，因為基于數(shù)據(jù)結(jié)構(gòu)帶來的異步記賬特性，同時實現(xiàn)了高度的參與網(wǎng)絡(luò)節(jié)點(diǎn)的去中心化和交易的可擴(kuò)展性。因此，目前對于雙花問題，需要綜合考慮實際情況進(jìn)行設(shè)計。

本報告由火幣區(qū)塊鏈研究院出品，作者：袁煜明、胡智威。原文地址

相關(guān)報告：

【超越白皮書2】EOS主網(wǎng)上線前夕的實測分析與技術(shù)建議

【超越白皮書1】EOSIO程序?qū)崪y分析與技術(shù)建議

火幣區(qū)塊鏈應(yīng)用研究院從技術(shù)角度對基于有向無環(huán)圖（DAG）數(shù)據(jù)結(jié)構(gòu)的分布式賬本技術(shù)進(jìn)行研究，并通過對典型代表項目IOTA的具體技術(shù)測試，主要得到以下研究結(jié)果:

DAG技術(shù)與狹義的區(qū)塊鏈技術(shù)相比，有其創(chuàng)新之處，理論上在不考慮作惡情況下可實現(xiàn)高可擴(kuò)展性和高去中心化，因此存在一些安全隱患。

DAG項目往往以偏中心化的方式來實際運(yùn)行，即降低去中心化程度來提高安全度，但同時其交易速率并沒有接近理論上限。

采用基于VPS（CPU進(jìn)行PoW）的40個節(jié)點(diǎn)網(wǎng)絡(luò)對代表性項目IOTA進(jìn)行交易壓力測試，可發(fā)現(xiàn)TPS很低：可達(dá)到的最優(yōu)結(jié)果為4.19。

經(jīng)分析，其性能瓶頸目前主要還在于硬件的算法實現(xiàn)本身。如果采用FPGA等其他方式來實現(xiàn)，應(yīng)可進(jìn)一步挖掘出DAG的性能潛力。

同時，為保持良好的交易處理能力，應(yīng)建立足夠規(guī)模的節(jié)點(diǎn)網(wǎng)絡(luò)。

區(qū)塊鏈?zhǔn)且环N分布式賬本技術(shù)，而分布式賬本技術(shù)卻不局限于“區(qū)塊鏈”這一種技術(shù)形式。在數(shù)字經(jīng)濟(jì)發(fā)展的浪潮中，為了改進(jìn)原有技術(shù)、滿足更多的實際業(yè)務(wù)應(yīng)用場景，更多的分布式賬本技術(shù)正在被探索和應(yīng)用當(dāng)中。有向無環(huán)圖（Directed Acylic Graph，以下簡稱“DAG”）是其中的代表之一。

DAG技術(shù)以及它背后的設(shè)計思想是什么？實際應(yīng)用效果如何？我們嘗試通過對DAG技術(shù)進(jìn)行深層解析以及對代表性項目IOTA的實際測試運(yùn)行獲得分析結(jié)論。

另外需要注意的是：測試得到的指標(biāo)數(shù)據(jù)結(jié)果不是也不應(yīng)被視為是對IOTA平臺或項目最終效果的證明或確認(rèn)。特此聲明。

經(jīng)過研究與測試分析，我們得到以下主要結(jié)論及技術(shù)建議：

DAG技術(shù)與狹義的區(qū)塊鏈技術(shù)相比，有其創(chuàng)新之處，理論上在不考慮作惡情況下可實現(xiàn)高可擴(kuò)展性和高去中心化，因此存在一些安全隱患。

DAG項目往往以偏中心化的方式來實際運(yùn)行，即降低去中心化程度來提高安全度，但同時其交易速率并沒有接近理論上限。

采用基于VPS（CPU進(jìn)行PoW）的40個節(jié)點(diǎn)網(wǎng)絡(luò)對代表性項目IOTA進(jìn)行交易壓力測試，可發(fā)現(xiàn)TPS很低：可達(dá)到的最優(yōu)結(jié)果為4.19。

經(jīng)分析，其性能瓶頸目前主要還在于硬件的算法實現(xiàn)本身。如果采用FPGA等其他方式來實現(xiàn)，應(yīng)可進(jìn)一步挖掘出DAG的性能潛力。

同時，為保持良好的交易處理能力，應(yīng)建立足夠規(guī)模的節(jié)點(diǎn)網(wǎng)絡(luò)。

DAG（Directed Acyclic Graph，有向無環(huán)圖）是一種數(shù)據(jù)結(jié)構(gòu)，表示的是一張有向圖，并且在這個圖中，從任意頂點(diǎn)出發(fā)都無法回到該點(diǎn)（無環(huán)），如圖所示：

基于DAG技術(shù)的分布式賬本（以下簡稱DAG）技術(shù)在近年來被提出后，被很多人認(rèn)為有希望替代狹義上的區(qū)塊鏈技術(shù)。因為DAG在設(shè)計時的目標(biāo)就是保留區(qū)塊鏈的優(yōu)點(diǎn)并且改進(jìn)區(qū)塊鏈的缺點(diǎn)。

和傳統(tǒng)線性區(qū)塊鏈結(jié)構(gòu)不同，以IOTA為代表的分布式賬本平臺的交易記錄之間形成的是一個有向無環(huán)圖的關(guān)系結(jié)構(gòu)，如下圖所示。

由于采用了不同于以往塊鏈?zhǔn)降臄?shù)據(jù)結(jié)構(gòu)，基于DAG的分布式賬本技術(shù)，擁有高可擴(kuò)展、高并發(fā)等特性并適用于物聯(lián)網(wǎng)場景。

傳統(tǒng)線性區(qū)塊鏈（如以太坊）的數(shù)據(jù)同步機(jī)制是同步的，這可能造成網(wǎng)絡(luò)的擁堵。DAG 網(wǎng)絡(luò)采用異步通訊機(jī)制，允許并發(fā)寫入，多個節(jié)點(diǎn)可以按照不同的節(jié)奏同時交易，而不必有明確的先后順序，因此同一時刻網(wǎng)絡(luò)的數(shù)據(jù)可能不一致，但最終會是同步的。

在傳統(tǒng)的區(qū)塊鏈網(wǎng)絡(luò)中，每個區(qū)塊中有很多筆交易，礦工打包好后統(tǒng)一發(fā)送，涉及到多個用戶；而在 DAG 網(wǎng)絡(luò)中并沒有“區(qū)塊”的概念，網(wǎng)絡(luò)的最小單元是“交易”，每筆新的交易需要驗證前面兩筆交易才能進(jìn)行，這樣DAG網(wǎng)絡(luò)并不需要礦工傳遞信任，轉(zhuǎn)賬無需手續(xù)費(fèi)，這使得 DAG 技術(shù)適用于小額支付。

不可能三角（trilemma），或被稱為“三難困境”，是指在特定的情形下，只能選擇三個有利選項中的兩個或者是在三個不利選擇中必須選擇一個。這一類選擇困境在宗教、法律、哲學(xué)、經(jīng)濟(jì)學(xué)、企業(yè)管理等多種領(lǐng)域均有相關(guān)案例。區(qū)塊鏈也不例外。區(qū)塊鏈中的不可能三角為：可擴(kuò)展性（Scalability）、去中心化（Decentralization）、安全性（Security）這三者中只能選擇其中兩個。

如果按照這種思路來分析DAG技術(shù)，根據(jù)前文介紹，那么無疑DAG已占據(jù)了去中心化、可擴(kuò)展性這兩個方面。DAG的去中心化和可擴(kuò)展性可認(rèn)為是一體兩面的，因為基于DAG數(shù)據(jù)結(jié)構(gòu)帶來的異步記賬特性，同時實現(xiàn)了高度的參與網(wǎng)絡(luò)節(jié)點(diǎn)的去中心化和交易的可擴(kuò)展性。

既然是數(shù)據(jù)結(jié)構(gòu)上的特性同時帶來了去中心化和可擴(kuò)展性，所以按照不可能三角的理論來推測，安全性會是一個隱患。但由于DAG是一個比較創(chuàng)新、特殊的結(jié)構(gòu)，是否也可比較完美的實現(xiàn)安全性？目前從實際效果來看并非如此。

DAG 異步通訊的特性為雙花攻擊創(chuàng)造了可能。例如，攻擊者在網(wǎng)絡(luò)的兩個不同的位置添加了兩筆沖突的交易（雙花），交易在網(wǎng)絡(luò)中不斷向前驗證，直到它們出現(xiàn)在同一筆交易的驗證路徑上，網(wǎng)絡(luò)才會發(fā)現(xiàn)沖突，這時這兩筆交易匯聚成的共同祖先節(jié)點(diǎn)才能判斷哪一筆交易是雙花攻擊。

而如果將交易路徑控制的過短又會存在類似“Blowball”的問題：當(dāng)極端情況下絕大多數(shù)交易都較為“懶惰”（Lazy Tip）、只參考早期交易時，交易網(wǎng)絡(luò)會形成一個以少數(shù)早期交易為核心的中心拓?fù)洹＿@對依賴于交易的不斷增加而提高網(wǎng)絡(luò)可靠性的DAG來說，也不是一件好事。

因此，目前對于雙花問題，需要綜合考慮實際情況進(jìn)行設(shè)計。不同的DAG網(wǎng)絡(luò)有各自的解決方案。

由于存在雙花的潛在問題，當(dāng)攻擊者可以構(gòu)建出足夠數(shù)量的交易后，就可能從真實的網(wǎng)絡(luò)數(shù)據(jù)中分叉出一個欺詐性分支（影子鏈），其中包含著雙花交易，然后將這個分支合并到DAG網(wǎng)絡(luò)中，特定情況下這個分支有可能取代原有交易數(shù)據(jù)。

目前項目主要都是通過犧牲一部分DAG的原生特性來保證安全性。

IOTA項目中采用了馬爾科夫鏈蒙特卡洛（Markov chain Monte Carlo，以下簡稱MCMC）的方式來解決該問題。IOTA為交易引入了累積權(quán)重（Cumulative Weight）的概念用來記錄該筆交易被引用的次數(shù)，目的是表示其交易的重要性。MCMC算法通過對累積權(quán)重進(jìn)行加權(quán)隨機(jī)游走，選擇目前網(wǎng)絡(luò)中已存在的交易作為新增交易的參考。即被參考越多的交易路徑越容易被算法選中。游走策略在1.5.0版本中也進(jìn)行了優(yōu)化，可將交易拓?fù)涞摹皩挾取笨刂圃谝粋€合理范圍內(nèi)，使得網(wǎng)絡(luò)更加安全。

但在平臺啟動初期，由于參與節(jié)點(diǎn)和交易數(shù)量均有限，所以很難避免一個惡意機(jī)構(gòu)通過大量節(jié)點(diǎn)發(fā)送出海量的惡意交易使得整個網(wǎng)絡(luò)受到影子鏈的攻擊。因此就需要一個權(quán)威的仲裁機(jī)構(gòu)來判定交易的有效性。在IOTA中，這一節(jié)點(diǎn)為Coordinator，它會定期對目前交易數(shù)據(jù)網(wǎng)絡(luò)（Tangle）進(jìn)行快照；包含在快照中的交易即被確認(rèn)為有效交易。但Coordinator并不會一直存在。隨著整個網(wǎng)絡(luò)的運(yùn)行和成長，IOTA會在未來某一時間取消掉Coordinator。

Byteball改進(jìn)方案的特色在于其對于見證人（witness）和主鏈的設(shè)計。因為DAG的結(jié)構(gòu)帶來了很多偏序關(guān)系的交易，而要避免雙花則需要對這些交易建立一個全序關(guān)系，形成一個交易主鏈。主鏈上較早的一筆交易作為有效交易。而由知名用戶或機(jī)構(gòu)擔(dān)任的見證人通過不斷的發(fā)送交易確認(rèn)其他用戶交易，從而形成主鏈。

以上方案也可能會對基于DAG結(jié)構(gòu)的平臺帶來不一樣的改變。以IOTA為例，因為引入了Coordinator，一定程度上降低了去中心化特性。

采用了除了解決安全問題之外，以上方案還可以在一定程度上解決智能合約問題。

由于DAG原生特性帶來的兩個潛在問題：（1）交易時長不可控，當(dāng)前通過請求重發(fā)的機(jī)制需要在客戶端進(jìn)行一些較為復(fù)雜的超時機(jī)制設(shè)計，希望能夠存在更簡單的一次性確認(rèn)機(jī)制；（2）不存在全局排序機(jī)制，導(dǎo)致系統(tǒng)支持的操作類型受限。因此在基于DAG技術(shù)的分布式賬本平臺上，較難實現(xiàn)出圖靈完備的智能合約體系。

為了保證智能合約可以運(yùn)行，需要一個機(jī)構(gòu)來完成上述工作。目前的Coordinator或主鏈可實現(xiàn)類似的效果。

作為最為直觀的指標(biāo)之一，DAG的TPS在理論上應(yīng)該是可以無限的。如果把IOTA平臺的最大TPS比喻為一個工廠的產(chǎn)能，那么日常運(yùn)行的TPS就是工廠的日常產(chǎn)量。

對于最大TPS，2017年4月份的IOTA壓力測試顯示，網(wǎng)絡(luò)具有112CTPS和895TPS的交易處理能力。這是在一個由250個節(jié)點(diǎn)所組成的小型測試網(wǎng)絡(luò)上得到的結(jié)果。

對于日常運(yùn)行的TPS，從目前可公開獲取的數(shù)據(jù)看到，近期主網(wǎng)平均TPS為8.2左右，CTPS（每秒確認(rèn)交易數(shù)量）為2.7左右。

而測試網(wǎng)近期的平均TPS為4左右，CTPS為3左右。

這是否與Coordinator的存在有關(guān)？需要實際測試來進(jìn)一步論證。

公開測試網(wǎng)的運(yùn)行統(tǒng)計數(shù)據(jù)與諸多因素都有關(guān)系。為了進(jìn)一步分析，我們繼續(xù)以IOTA平臺為例，搭建一個私有測試環(huán)境進(jìn)行技術(shù)實測分析。

我們本次測試搭建的各組件間關(guān)系如下圖所示。

其中：

為了避免主網(wǎng)或測試網(wǎng)上的其他因素對測試結(jié)果的影響，我們搭建了一個40個節(jié)點(diǎn)的小型私有IOTA測試網(wǎng)絡(luò)。構(gòu)建過程參考“Private IOTA Testnet”項目（https://github.com/schierlm/p...），并對其中使用的IRI（IOTA Reference Implementation）版本更新為了最新的v1.5.0版本。此外，在測試過程中，使用該工具提供的Coordinator模擬工具，定期生成快照對交易進(jìn)行確認(rèn)。

使用基于Python的開源負(fù)載測試工具Locust（https://locust.io/），以便控的發(fā)送出交易數(shù)據(jù)。在開始測試后，隨機(jī)向所有私有網(wǎng)絡(luò)中的節(jié)點(diǎn)發(fā)送出交易數(shù)據(jù)。

在節(jié)點(diǎn)啟動時，增加“--zmq-enabled”參數(shù)，以便啟動IOTA的ZeroMQ支持，將節(jié)點(diǎn)得到的交易數(shù)據(jù)中通過消息隊列方式發(fā)送給觀測端。在觀測端使用ZeroMQ事件解析腳本（https://github.com/lunfardo31...）觀察節(jié)點(diǎn)交易數(shù)據(jù)情況。

服務(wù)器采用亞馬遜AWS EC2 C5.4xlarge: 16 核 3GHz, Intel Xeon Platinum 8124M CPU，32GB內(nèi)存，服務(wù)器間為10Gbps局域網(wǎng)網(wǎng)絡(luò)，通訊延遲（ping）小于1ms，操作系統(tǒng)為Ubuntu 16.04。

雖然沒有“礦工”等概念，但在發(fā)送交易前，IOTA節(jié)點(diǎn)仍然需要進(jìn)行工作量證明，以避免發(fā)送大量交易淹沒網(wǎng)絡(luò)。PoW難度值（Minimum Weight Magnitude）與比特幣類似，是PoW的結(jié)果應(yīng)得出“9”的位數(shù)，其中9在IOTA采用的三進(jìn)制中為“000”。IOTA難度值可在節(jié)點(diǎn)啟動前進(jìn)行設(shè)置。

目前對于生產(chǎn)網(wǎng)絡(luò)，IOTA的難度值設(shè)置為14；測試網(wǎng)設(shè)置為9。因此，我們首先采用測試網(wǎng)的默認(rèn)難度值9來進(jìn)行測試，得到以下測試結(jié)果。

由于每個IOTA的交易包（bundle）中會包含多筆transfer，因此實際處理的TPS會比發(fā)送速率高。但通過執(zhí)行解析zmq的腳本可觀察到，目前TPS很低。而另一個現(xiàn)象是，每秒可發(fā)送成功的請求數(shù)量也很低。

經(jīng)過分析，原因在于測試使用的是VPS，所以在PoW時，主要使用CPU來進(jìn)行運(yùn)算，因此交易速度主要受發(fā)送速度的影響。

將難度值降低為1后重新進(jìn)行測試，得到以下結(jié)果。

從結(jié)果可看到，降低難度后，TPS會有所上升。所以目前IOTA項目的TPS并沒有到達(dá)Coordinator所在的瓶頸，而主要是發(fā)送交易的客戶端本身硬件以及網(wǎng)絡(luò)等方面原因?qū)е隆OTA社區(qū)目前在研發(fā)基于FPGA的Curl算法實現(xiàn)以及CPU指令集優(yōu)化等工作。我們的測試結(jié)果也印證可通過這一方式繼續(xù)挖掘DAG平臺的性能潛力。

由于DAG的特性，平臺實際TPS和網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量可能也存在著關(guān)系。因此在難度值保持為1的情況下，將網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)減為10后重新進(jìn)行測試，得到以下結(jié)果。

從結(jié)果可看到，隨著節(jié)點(diǎn)數(shù)降低，實際處理TPS也有所下降，而且低于發(fā)送速率。這說明在DAG環(huán)境下，維持足夠規(guī)模節(jié)點(diǎn)將有助于交易的處理。

https://www.iota.org/
https://en.wikipedia.org/wiki...
https://blog.iota.org/new-tip...
https://en.wikipedia.org/wiki...
https://byteball.org/
https://www.iotachina.com/iot...
https://www.iotachina.com/iot...