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

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

相關(guān)報(bào)告：

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

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

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

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

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

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

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

同時(shí)，為保持良好的交易處理能力，應(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ù)、滿(mǎn)足更多的實(shí)際業(yè)務(wù)應(yīng)用場(chǎng)景，更多的分布式賬本技術(shù)正在被探索和應(yīng)用當(dāng)中。有向無(wú)環(huán)圖（Directed Acylic Graph，以下簡(jiǎn)稱(chēng)“DAG”）是其中的代表之一。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

目前項(xiàng)目主要都是通過(guò)犧牲一部分DAG的原生特性來(lái)保證安全性。

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

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

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

以上方案也可能會(huì)對(duì)基于DAG結(jié)構(gòu)的平臺(tái)帶來(lái)不一樣的改變。以IOTA為例，因?yàn)橐肓薈oordinator，一定程度上降低了去中心化特性。

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

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

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

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

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

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

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

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

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

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

其中：

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

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

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

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

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

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

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

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

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

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

從結(jié)果可看到，隨著節(jié)點(diǎn)數(shù)降低，實(shí)際處理TPS也有所下降，而且低于發(fā)送速率。這說(shuō)明在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...