基于DAG的區塊鏈新模型設計與實現

張 震 李 強 甘 俊 張 超(四川大學計算機學院 四川 成都 610065)

0 引 言

自2008年中本聰發布比特幣白皮書以來，比特幣這類點對點電子現金系統引起了社會各界的極大重視。學者在對該系統深入研究之后，從比特幣的基礎架構凝煉出了區塊鏈技術。

區塊鏈技術巧妙融合了以共識算法為核心的諸多技術，它以去中心、自治、開放、匿名、不可篡改的特性為人知曉。區塊鏈系統的安全性基于密碼學算法，而不是傳統意義上的“信用”。區塊鏈被認為是人類社會關于信任和協作的跨越式進步。2015年10月，《經濟學人》封面文章稱區塊鏈是制造信任的機器。

學術界和商業界都對區塊鏈技術顯示出了極大的興趣。眾多研究人員共同推動了區塊鏈技術的發展，Swan[1]在《Blockchain：Blueprint for a New Economy》中將區塊鏈技術的發展分為了3個階段。

區塊鏈1.0時代是以比特幣為代表的加密數字貨幣時代。去中心的比特幣系統在全球范圍內平穩運行近十年更加彰顯了區塊鏈技術的不平凡之處。比特幣之后，眾多加密貨幣如雨后春筍般涌現。隨著加密數字貨幣的興盛，區塊鏈的去中心特性逐漸深入人心并被更多的人接受。比特幣更像是一次極為成功的社會實驗，驗證了區塊鏈強大的生命力。然而，作為區塊鏈1.0時代的標志性產物，比特幣系統存在著諸多缺憾。

比特幣系統采用的共識算法是PoW(Proofof Work)。自2008年至今，PoW算法始終安全可靠地維護著比特幣系統的運行。然而，PoW的弊端也隨之顯露。弊端之一是世界范圍內大算力礦池的出現，在一定程度上削弱了區塊鏈去中心化的設計初衷，也消減了大部分小算力參與者的熱情，為51%攻擊提供了更多的可能性。弊端之二是PoW會導致巨量的能源浪費，每年消耗資源數十億美元。弊端之三是區塊的建議最終確認時間長達60 min左右，吞吐量是7筆/s，效率較低。

PoS(Proofof Stake)共識算法的提出正是為了解決PoW共識算法所引起的低效高耗能問題。從2011年出現相關概念開始，就出現了一大批PoS的簇擁者，他們以PoS思想為核心，提出了各自的鏈式結構系統。如Casper[2]、Algorand[3]、Nxt[4]、Peercoin[5]等知名區塊鏈系統。PoS算法在改善PoW算法的同時也引進了新的弊端，如PoS類系統極易分叉、記賬人權力過大等。

區塊鏈2.0時代是以智能合約為代表的可編程金融時代。1995年Nick S首次提出智能合約概念。之后，Ethereum(以太坊)將智能合約與區塊鏈相結合，極大地擴展了區塊鏈的應用場景，諸如股票、債券、產權等數字資產領域紛紛與區塊鏈結合。區塊鏈將會重塑相關領域的交互方式，重構商業環境。

區塊鏈2.0時代的主要工作就是擴容，提升區塊鏈的擴展性。以以太坊為代表的諸多系統從增大區塊容量、提升記賬節點帶寬、提升記賬節點處理性能、減小區塊時間和減小記賬節點數量等角度對鏈式結構做了研究。然而，鏈式結構從基礎架構上限制了區塊鏈整體性能的提升。作為一種數據結構，有向無環圖(Directed Acyclic Graph，DAG)從數據層給了區塊鏈更大的性能提升，是區塊鏈邁向3.0時代的關鍵技術。

區塊鏈3.0時代是區塊鏈技術的廣泛應用時代。以去中心化自洽組織(Decentralized Autonomous Organizations，DAO)和去中心化自洽公司(Decentralized Autonomous Corporations，DAC)標志的自我管理組織常態化，人類社會協作方式出現新的可能。人們的生產、生活各個方面都會接受相應的區塊鏈概念。萬物互聯互信時代是區塊鏈3.0時代的愿景。區塊鏈3.0時代的數據量必然是海量的，鏈式結構難以承受海量數據中蘊含的信息運作方式。目前看來，DAG架構是區塊鏈性能提升的首選。

DagCoin[6]最早闡述了有關DAG式區塊鏈的理論設想，后由IOTA[7]和ByteBall[8]一脈相承，對DAG式區塊鏈做了擴展。DAG中融合了極多的分叉，這些分叉構成了局部交易之間的相對順序。DAG式區塊鏈憑借異步通信機制打破了鏈式區塊鏈的性能瓶頸。眾多DAG模型均自稱達到了物理極限，TPS(Transaction Per Second)僅受制于物理因素。海量TPS的提升為區塊鏈挺進3.0時代指明了方向。

DAG最大的弊端來自于異步通信造成的全局無序狀態。一種解決方案是控制用戶的規模，進而弱化無序狀態的影響，如應用于聯盟鏈的Hashgraph[9]系統；另一種解決方案是主鏈延遲選擇策略。系統從過去一段時間內的歷史交易中選出一些符合標準并且持續相連的交易組成主鏈，通過主鏈順序為所有交易排序，如Byteball、Conflux[10]等。

目前，DAG式區塊鏈的研究集中在主鏈延遲選擇策略上。一方面，如果不同用戶本地歷史交易數據不一致，那么這種方法必定會造成不同用戶主鏈的不一致，如Conflux采用的GHOST[11]主鏈選擇算法，子樹節點最多的區塊當選主鏈區塊。另一方面，目前的DAG式區塊鏈主鏈共識機制多為見證人共識，易造成系統安全性降低、交易時長不可控等問題，如ByteBall。本文提出一種基于DAG的區塊鏈新模型——權益有向無環圖模型(SDAG)，將DAG這種最底層的數據組織方式與POS鏈式共識算法結合起來。通過DAG結構去解決鏈式結構吞吐量有限、易分叉等問題，同時PoS鏈式共識會即時構建DAG式區塊鏈的主鏈，控制全局狀態，控制交易時長，縮短共識時間。

1 已有研究

PoS類共識算法根據用戶的資源占比賦予用戶相應的投票權重。通過某種規則被選擇的礦工具有發布下一個區塊的權利，有投票權的一組用戶對每一個合法區塊進行驗證并投票。主流的PoS共識模型有兩種，一種是需要累積確認的鏈式模型，另一種是結合BFT共識的模型。Nxt和Peercoin都是對比特幣鏈式結構的模仿，屬于需要累積確認的模型。而Algorand等系統則是屬于結合BFT共識的模型。

傳統分布式一致性算法中，Paxos[12]和Raft[13]比較有代表性，在非拜占庭(Byzantine Fault Tolerance)環境下較為適用。Pease和Lamport 在20世紀80年代提出BFT問題和解決算法，Castro等[14]提出了實用拜占庭容錯共識算法PBFT(Practical Byzantine FaultTolerance)。PBFT共識算法中，如果某個交易通過了三分之二節點的驗證，那么該交易就會被所有人接受，無須等待即可達成共識。

在DAG式區塊鏈模型中，PHANTOM[15]要求新區塊的反錐面中節點數小于等于k才被允許加入系統。雖然PHANTOM具有良好的擴展性，但是不能保證強的線性排序和一定的活性。SPECTRE[16]通過一種投票算法，依據錐面節點數對區塊進行排序，排序靠前的區塊可信度越高。不同于SPECTRE和PHANTOM中的區塊之間只有父子連接，Conflux采用了父子連接和引用連接，引用連接用來標記所有未被主鏈區塊所引用的葉子區塊，極大地提升了排序效率。

1.1 DAG式區塊鏈和鏈式區塊鏈

區塊鏈系統是一種運行在不受控環境中，可以解決拜占庭問題的分布式系統。共識算法是區塊鏈的核心。區塊鏈通過設定某一條件作為分布式節點達成共識的基礎。共識算法負責區塊鏈中信息的完整性，同時防御雙重花費攻擊，因此是區塊鏈技術的重要組成部分。最終目標是在沒有中央機構的分布式網絡中實現共識，并且與不一定相互信任的參與者達成共識[17]。

根據系統中數據的組織形式(鏈式或者DAG式)可以將區塊鏈分為鏈式區塊鏈和DAG式區塊鏈，其中的共識算法也多有不同。

1.1.1鏈式區塊鏈

結構上，鏈式區塊鏈中的每個區塊有自己的時間戳，每個時間戳應當將前一個區塊的時間戳納入其隨機散列值中，每一個隨后的時間戳都對之前的一個時間戳進行增強，這樣就形成了一個鏈條。圖1是鏈式區塊鏈的結構。區塊是區塊鏈的網絡節點，是用于記錄交易的數據結構。時間戳是對區塊鏈中的每個區塊上的信息加上時間驗證，對每一個數據的輸入追本溯源、根據時間順序排列、驗證、確保數據的真實性，不容數據被篡改，證明數據的原創性和所有權的歸屬。

圖1 鏈式區塊鏈

區塊鏈的鏈式結構是對比特幣系統的延續，是鏈式區塊鏈共識算法的理論基礎。其共識算法是為了維護系統中只有一條唯一的合法鏈，任何分叉鏈都被視作對系統的攻擊。正是基于此種考慮，比特幣系統產生新塊的時間被設定為10 min，系統需要足夠的時間保證新塊被傳遞給所有的用戶節點，保證最長鏈的產生者會有更多的競爭者，保證系統會有更少的分叉(這些沒有收到最新區塊的用戶節點會產生不合法的區塊)。

在鏈式結構的場景中，系統內節點的周期性工作是：

(1) 接收驗證。用戶節點時刻監聽網絡中的新交易，對接收的新交易進行驗證，將合法的新交易放入本地緩沖區。

(2) 選擇礦工。用戶節點根據共識算法程序選擇出唯一的礦工，即該礦工獲得記賬權。

(3) 打包廣播。取得記賬權的礦工從緩沖區中篩選出部分合法且有利的交易，將其打包并廣播給所有用戶節點。

(4) 最終確認。在一定時間后，該區塊所在的鏈被逆轉的風險低于用戶的承受度，即完成最終確認，交易完成。

在最終確認階段，區塊鏈中交易順序被改變的可能性可以被接受時，則認為完成了交易。如在比特幣安全實驗中，在假設攻擊節點的算力占全網算力10%時，等待6個區塊的確認，攻擊行為成功的概率為0.059%，小于0.1%，所以比特幣系統的建議確認時間是60 min左右，即歷史交易需要6個新塊的確認。

1.1.2DAG式區塊鏈

在圖論中，如果一個有向圖無法從某個頂點出發經過若干條邊回到該點，則這個圖是一個DAG。有向無環圖常被用于交易速度極為重要的領域，比如編譯器、人工智能、統計和機器學習等。

Nxt社區首次提出將DAG跟區塊鏈結合起來。區塊鏈本質上是DAG的受限版本，僅允許在單軌道上進行連接[6]。DAG式區塊鏈的結構如圖2所示。

在結構上。首先，不同于鏈式區塊鏈中每個塊只能有一個父節點，它允許每個區塊指向兩個或者兩個以上的區塊，容納了很多分叉，這些分叉共同構成了一幅有向無環圖。其次，它允許每個區塊只有一個交易，如IOTA，而鏈式區塊鏈中每個區塊中的交易可能多達幾千筆，如比特幣。最后，該結構中的交易在進入系統之前就已經確立了相互之間的引用關系，該引用關系為交易確立了局部的時間先后關系，而鏈式區塊鏈中默認交易之間是無序的，交易之間的順序是由礦工來隨機決定的。

在DAG式結構的場景中，每個用戶節點把接收到的全部交易經初步驗證后存儲到本地緩沖區，然后根據主鏈共識算法從交易中挑選出能構成主鏈的交易，再剔除掉重復和雙重支付的交易，最終在交易的總順序上達成共識。系統內節點的周期性工作是：

(1) 接收驗證。用戶節點時刻監聽網絡中的新交易。

(2) 緩存交易。對接收的新交易進行驗證，將合法的新交易放入本地緩沖區。

(3) 確定主鏈。系統根據某種主鏈共識算法從近期交易(區塊)中篩選出唯一一條區域合法主鏈，進而延長從創世區塊貫穿到葉子交易(區塊)的主鏈。

(4) 最終確認。在一定時間后，主鏈區塊被逆轉的概率小于用戶所能承受的風險，即交易順序已經被絕大部分用戶同意，并且很難再發生改變，則完成最終確認。

目前的主鏈研究工作中，主鏈交易(區塊)均是從歷史交易中篩選出來的，所以在最終確認階段，采用累積確認的方式較多。SDAG從DAG的特殊結構出發，通過BFT類共識算法即時發布主鏈交易，達到快速確認的目的。

1.1.3鏈式區塊鏈與DAG式區塊鏈的不同

鏈式區塊鏈與DAG式區塊鏈除了結構上的不同，兩者之間其他方面的不同如下：

(1) 鏈式區塊鏈中，礦工在存入每一條交易數據之前會在全局范圍內查找是否有交易與將要存儲的交易數據沖突。DAG式區塊鏈在存入數據交易之前沒有全局狀態，故而選擇將所有數據先存儲，再按某種共識將所有交易排序和剔除。

(2) 鏈式區塊鏈中的交易只能由礦工按照固定時間周期添加至系統，屬于定期存儲策略。DAG式區塊鏈中的交易可以由任何用戶在任何時候向系統中添加，屬于異步并發策略。

(3) 鏈式區塊鏈的共識算法發生在階段2(選擇礦工)中，發生在將數據存入本地緩沖區之前。DAG式區塊鏈的共識算法發生在階段3(確定主鏈)，發生在將所有數據存入本地緩沖區之后。

(4) 即使某些非合法鏈上的區塊是由誠實節點發布的，鏈式結構也會放棄它，并且礦工會重新打包提交給系統，浪費了很多誠實節點的算力。DAG式區塊鏈則會保留所有人發來的交易，在排序之后剔除不合法交易。

(5) 鏈式區塊鏈的共識算法的作用對象是用戶節點，輸出的是礦工。DAG式區塊鏈的主鏈共識算法的作用對象是區塊(交易)，輸出的是可以構成主鏈的區塊(交易)，是所有交易的線性順序。

(6) 鏈式區塊鏈通過保證礦工的唯一，進而確保鏈中交易順序的唯一，最后通過累計確認階段將這種交易順序固化。DAG式區塊鏈借助有向無環圖節點(代表交易和區塊)之間局部有序特性，通過主鏈順序為系統中的所有交易確定順序，最終使得所有用戶在交易總順序上達成共識。

(7) 當同時存在兩個不沖突或者沒有任何關系的區塊(交易)的時候，鏈式結構規定只能保留一個，DAG式區塊鏈則暫時全部保留。

(8) 由于DAG式區塊鏈中，沒有固定的角色向系統添加交易數據，幾乎不會存在單點故障，任何人想要重建歷史交易網絡的可能性幾乎為0。

1.2 現有DAG區塊鏈系統

現有區塊鏈系統中，國外以IOTA和ByteBall最為知名，國內以Conflux最為知名。

IOTA的系統模型是Tangle。系統中每個區塊只有一個交易，DAG結構的節點是一條交易，每個交易必須引用兩個或兩個以上歷史交易，以此構建DAG。新交易對歷史交易的引用代表新交易的發送者對歷史交易的認可，可進行分區并行驗證。IOTA的共識機制是置信度共識，即新交易對歷史交易的認可度。只有置信度達到一定閾值的交易才被認為是被完全確認。IOTA的優勢是并行驗證，劣勢是無全局狀態、交易時長不可控、安全性取決于活躍用戶占比。目前的IOTA系統依靠中心化的協調器維護。

ByteBall系統是對IOTA的發展，引入了主鏈共識等重要概念。ByteBall系統采用特定人數的權威見證人幫助用戶達成共識，屬于主鏈共識。用戶節點通過在歷史交易有向無環圖中選擇出富集權威見證人交易最多的一條鏈，依此錨定其他交易的全局順序，是主鏈延遲選擇的策略。ByteBall的優勢在于主鏈共識能夠幫助交易確定全局狀態，劣勢是主鏈選擇算法復雜，本地交易視圖不同的用戶選擇出的主鏈容易出現不一致，見證人選擇及操作偏向中心化。

Conflux系統是對比特幣系統的擴展，通過使用DAG提升比特幣系統的擴展性。Conflux采用主鏈共識機制，主鏈共識算法采用GHOST協議，通過挑選出子樹最多的交易來延長主鏈，也是主鏈延遲選擇策略。由于依然使用PoW算法，Conflux的劣勢是耗時耗資源，并且主鏈延遲選擇會導致主鏈不一致。

本文提出的SDAG模型主要是對主鏈延遲選擇策略的改進，利用DAG的特殊結構，提出一種主鏈并行即時選擇策略。

2 SDAG區塊鏈模型設計

DAG結構中交易之間天然部分有序，整體無序。每個用戶節點都有向系統寫入數據的權利，并且可以為交易指定前置交易。只需要維護一條貫穿整個有向無環圖的主鏈，所有交易間的順序就可以被線性化。基于BFT的PoS類共識算法能夠即時確認歷史交易，具有數學可證的安全性、不分叉等特點，可以被用來維護主鏈。

2.1 SDAG模型中的角色和交易

模型中有兩種角色，一類是普通用戶，另一類是主鏈委員會用戶。普通用戶節點中權益排名靠前的節點成為主鏈委員會用戶，主鏈委員會用戶可以同時保留普通用戶的角色。

普通用戶負責將自己的交易廣播給其他人，同時將監聽到的交易緩存到本地緩沖區。主鏈委員會用戶負責周期性共識出一個主鏈交易。

SDAG模型中沒有區塊，只有交易，可類比于區塊鏈中的一個塊中只有一筆交易，而不是上千筆交易。交易有兩種類型，一種是普通交易，另一種是主鏈交易。普通交易由普通用戶發出，只包含用戶自己的交易數據以及該交易引用了哪些父交易。這些引用構成了有向無環圖的單向箭頭，而每一筆交易成為了有向無環圖的節點。

如圖3所示是SDAG中的交易結構。一個交易由時間戳、交易hash值、簽名、引用hash值、交易內容組成。時間戳標識了該交易的產生時間，交易hash值確保交易數據的完整性和不可篡改，簽名標識交易的發出者是哪一個用戶，引用hash值用來指明該交易的父交易是哪些，交易內容則記錄了用戶的交易數據或者操作信息。

主鏈交易是由主鏈委員會周期性共識產生的，每個主鏈交易不包含任何有效交易內容，交易內容僅僅是主鏈交易的標識。主鏈交易只包含交易發出時主節點本地視圖中的所有葉子節點，如圖4中主鏈交易A1引用了交易I和交易J，主鏈交易A2引用了交易I2、交易H2、交易J2。

圖4 SDAG的數據結構

模型規定普通用戶必須引用兩個或兩個以上的歷史交易，主鏈交易引用所有的葉子節點交易。主鏈交易引用的交易數量可能遠超普通交易。兩個主鏈交易之間的時間段是一個時間間隙，如圖4中主鏈交易A1和主鏈交易A2之間存在時間間隙。

在交易構成的DAG中，將一個時間間隙內的所有交易稱作交易子圖，如圖4中的(A2,B1,C1,D1,E1,F1,G1,I1,H1,J1)構成了一幅交易子圖。

2.2 SDAG的主鏈共識算法

模型中的主鏈交易通過主鏈共識算法周期性產生。主鏈共識算法是PoS-PBFT，它僅僅是將PoS構想和PBFT相結合，是對PBFT中的角色進行定義。

2.2.1PBFT算法

PBFT算法中有三種角色：客戶端、主節點、從節點。功能如下：

(1) 客戶端：發送交易請求消息。

(2) 主節點：將接收到的消息排序編號，廣播消息給從節點。

(3) 從節點：驗證從主節點和其他從節點處接收到的消息并回應。

如果所有節點中存在f個惡意節點，那么PBFT算法需要2f+1個誠實節點就可以保證系統的正常運行。

如圖5所示，PBFT共有五個階段：request，pre-prepare，prepare，commit和reply。

圖5 PBFT的共識階段

request階段：客戶端c向主節點0發送請求消息m，格式是，其中：o代表的是請求的操作；t代表消息的時間戳；c代表消息的發出者是客戶端。

pre-prepare階段：主節點0給消息m編號，并將消息廣播給從節點1、從節點2、從節點3。消息的格式是<,m>，其中:v代表視圖編號；d代表消息m的摘要。

prepare階段：三個從節點對收集到的pre-prepare消息進行驗證，并將自己的驗證結果廣播給其他人。如果從節點認為消息有誤，則不會發送消息。只有收集到包含自身在內超過2f+1個一致的回復，節點才會進入下一階段。消息的格式是，其中i是節點自身的編號。

commit階段：節點完成消息對應操作后，會把自己的完成狀態廣播給其他人，消息的格式是。節點同樣需要收集包含自身在內超過2f+1個一致的回復才會進入下一個階段。

reply階段：節點收集足夠的消息后進入reply階段，然后向客戶端發送完成消息，消息的格式是，其中r是節點的執行結果。客戶端只有收集到f+1個不同節點的響應才會認為request請求被完成。

一個交易經過3個階段驗證，就會被系統中的絕大部分人確認，那么該交易就可以被認為是完全確認的。

2.2.2POS-PBFT主鏈共識算法

PBFT運行最少需要3f+1個節點，也就是4個節點。系統中參與共識的節點越少，共識的速度越快，去中心化越低。本文從每個用戶節點的權益值出發，使得權益占有總數大于一半的普通節點參與共識，既保證了系統的共識速度，又保證了系統的去中心化程度。由于實驗節點規模所限，本文從所有用戶中篩選出權益最高的5個用戶節點，這5個用戶節點共同組成了主鏈交易委員會，在每輪交易周期后，系統會計算出排名靠前的用戶節點，用來替換上一周期的主鏈交易委員會，而主鏈交易委員會的席位總是固定的。

在PBFT中有三種角色：客戶端、主節點、從節點。將權益最高的用戶節點作為主節點，主節點同時也作為客戶端發起request請求，權益排名第2至第5的用戶節點作為從節點。

不同于礦工獨享記賬權，SDAG中的所有普通節點都擁有向系統添加普通交易的權利。但是，主鏈交易只有主節點可以作為客戶端的身份發起。主鏈交易不包含任何交易信息，只包含主鏈交易引用了哪些葉子交易。主節點提交的主鏈交易會經歷PBFT共識，通過共識的主鏈交易才會被所有的用戶接收。

所有用戶接收到主鏈交易后，會根據主鏈交易提供的葉子節點信息對本地交易子圖進行更新，如果缺少對應的交易，用戶可以向其他節點請求同步，保證數據的一致性。在數據一致性的基礎上，用戶在本地運行排序算法。排序算法輸入的是交易子圖，輸出的是交易子圖內交易的線性順序。并把該交易子圖的順序連接在上一個交易子圖的線性順序之后，主鏈得以延伸，全局狀態取得一致。

由于模型SDAG中數據的一致性，用戶節點能夠依據本地數據同步更新各節點的權益，每一輪主鏈交易委員會由最新一輪狀態中的前5名用戶擔任，這保證了委員會的去中心性。而作為模型中權益最多的前5名用戶，他們的權益之和會遠遠大于其他用戶，只要委員會保持行動一致，他們的行動就能代表系統中絕大多數誠實節點的利益，因為如果系統受到攻擊，委員會成員的利益將會受損最大。

2.2.3POS-PBFT算法流程

系統初始化，所有用戶節點中權益前五的用戶節點成為主鏈交易委員會成員，權益第一的用戶節點成為主節點。

主鏈交易的產生和普通交易的產生并行執行。主鏈委員會周期性產生主鏈交易，并且更新委員會成員，成員更換信息可以被用戶節點在本地感知，無須消耗額外通信資源。網絡中所有用戶節點監聽其他用戶的交易信息，對于接收到的消息進行判斷，如果是普通交易則緩存至本地緩沖區，如果是主鏈交易，則用戶執行交易子圖的排序算法，執行完畢后將排在后面的雙花交易剔除，最后緩沖區中的數據被持久化到本地數據庫。圖6是SDAG模型中一個普通用戶節點的工作流程，算法1是主鏈共識算法偽代碼。

圖6 SDAG普通節點工作流程

算法1主鏈共識算法

輸入：交易子圖。

輸出：達成共識的主鏈交易。

// NEW_ROUND:

State=NEW_ROUND

//從交易子圖中更新每個用戶的權益值變化，取出權益值排名

//前5的節點作為委員會節點，權益值最高的節點作為主節點

proposer=get_proposers_address(transactionsGraph)

if (current_validator==proposer)

MCtransaction=create_MainChainTransaction(transactionsGraph)

broadcast_block(MCtransaction)

State=PRE_PREPARED

// PRE_PREPARED:

On MCtransaction.type==PRE_PREPARE

verify_transaction (MCtransaction)

verify_validator(MCtransaction)

broadcast_prepare(MCtransaction)

State=PREPARED

// PREPARED:

On MCtransaction.type==PREPARE

verify_prepare(MCtransaction.prepare)

verify_validator(MCtransaction.prepare)

prepare_pool.add(MCtransaction.prepare)

if (prepare_pool.length>2F+1)

broadcast_commit(MCtransaction.prepare)

State=COMMITTED

// COMMITTED:

On MCtransaction.type==COMMIT

verify_commit(MCtransaction.commit)

verify_validator(MCtransaction.commit)

commit_pool.add(MCtransaction.commit)

if (commit_pool.length>2F+1)

transactions.append(MCtransaction)

State=FINAL_COMMITTED

// FINAL_COMMITTED:

broadcast_ commited(MCtransaction)

2.3 SDAG的交易排序

交易之間的引用拓撲關系是交易的發送者指定的，為用戶交易的執行設定前置條件。但是這種順序只能是局部的，全局交易之間是完全無序的，雖然DAG追求的是所有交易都應有一個準確的線性順序，但是這種順序是不可求解的，也不是必須的。如在比特幣系統中，雖然區塊之間是線性關系，但是一個區塊中有幾千筆交易，這些交易之間的順序并不是交易的發送者指定的，比特幣系統默認這幾千筆交易并行執行。如圖7所示的那樣，區塊內的所有交易之間是毫無關聯的。

圖7 鏈式結構中的區塊和交易

本文所述SDAG模型將區塊解構為交易子圖，等同于將區塊中的交易展開，并附加上交易之間的原始先后關系，這種細粒度的交易執行關系對于智能合約等時序性和嚴謹性要求較高的適用場景是極為必要的。

交易子圖的排序規則如下：

(1) 被引用的交易一定先于發出引用的交易。可以傳遞引用，如a引用b，b引用c，那么a一定晚于c。傳遞引用按照最長路徑計算。

(2) 對于不在引用關系的交易按照時間戳進行排序。

(3) 對于時間戳相同的交易，按照hash值的字典順序進行排序。

交易子圖越小，該子圖內的交易順序越精確，反之越模糊。交易之間最精確的順序是由引用關系推導出來的，把交易的時間戳納入排序因素得到的順序精確度次之，把交易hash值納入排序因素得到的交易順序最模糊。

交易排序算法見算法2。

算法2排序算法

輸入：交易子圖。

輸出：交易子圖中交易的鏈式順序。

//從主鏈交易開始， 依據葉子節點把交易子圖中的交易按照引

//用關系導出為幾條交易鏈,返回鏈表頭部

List lists=getAllTransactionList();

List newList=new List();

While(allLisyIsNotNull){

//依次取出每條交易鏈表中的交易，按照時間戳和交易hash值

//的字典順序插入到新的交易鏈中

newList.add( transctionFromLists );

}

return newList；

2.4 SDAG的數據一致性

雖然DAG中的交易順序沒有唯一的解，但是只要每個用戶節點接收到的交易是完全一致的，并且按相同的原則處理，那么依然可以保證所有用戶數據的一致性。

由于每個交易都會存儲父交易的hash值，并且會把父交易的hash值作為自己交易的一部分進行hash。這種增強的關系，確保了只要葉子交易(未被其他交易引用的交易)是一致的，那么交易子圖就是一致并且完整的。用戶可以根據葉子節點中父交易的hash進行回溯遍歷，遍歷的起點是此時的主鏈交易，終點邊界是被上一個主鏈交易引用過的已排序交易。

SDAG模型的一致性不僅代表交易內容的一致性，還隱含有交易執行順序的一致性。

2.5 確認交易

由于普通交易的順序完全取決于主鏈交易，所以只需要確認主鏈交易即可。主鏈共識采用PoS-PBFT共識算法，每一個新交易的產生都需要經過主鏈交易委員會的投票確認。獲得委員會的多數通過即代表該主鏈交易已經被確認，該主鏈交易引用的交易子圖中的交易也被確認。這種確認是即時的，并不依賴于后續主鏈交易對該主鏈交易的引用。

主鏈交易的定期產生和即時確認特性保證了SDAG中交易的確認時間是可控的，不會出現DAG式區塊鏈中常見的交易時長不可控問題和主鏈偏差問題。

3 SDAG區塊鏈模型的實現

3.1 SDAG架構

SDAG模型中的普通交易由普通用戶實時產生并廣播，主鏈交易由主鏈交易委員會周期性共識產生并廣播，這兩部分工作可以并行進行，只要用戶節點在收到主鏈交易的時候對本地數據進行同步檢查即可。

如圖8是SDAG的架構，由網絡層、共識層、緩沖區和本地數據庫四部分組成。圖中的加粗黑色圓環代表主鏈交易，而細實線圓代表普通交易。網絡層負責用戶節點間的點對點通信，所有交易通過網絡層進行廣播。共識層負責定期產生主鏈交易。緩沖區負責對接收到的數據進行初步驗證，保留合法數據。本地數據庫用以持久化經過全局驗證的合法交易。

3.2 系統平臺和開發工具

本文使用Java平臺實現SDAG模型，開發環境如表1所示。

3.3 程序結構

圖9是SDAG系統的程序結構，分為以下幾個部分：dao部分用來實現用戶節點的數據持久化；service部分實現了節點收到交易后的一系列操作；socket部分實現了節點間的網絡通信；resources部分存儲了節點的配置文件；test部分用以對相關功能的測試。

圖9 SDAG系統的程序結構

3.4 網絡層實現

SDAG系統采用P2P網絡結構，各節點之間無須通過服務器或者其他節點中轉。節點之間使用TCP協議，通過Socket套接字通信。交易數據通過指定的端口和用戶節點的IP地址進行傳輸。

主鏈交易和普通交易都是通過網絡層傳輸。transocket部分用來實現普通交易的傳輸和接收，MCsocket部分用來實現主鏈交易的共識算法部分的通信。模型實現過程中，使用5個用戶節點，分別為2種交易分配端口1和端口2，每個用戶對端口1保持監聽從而收集網絡中的普通交易，對端口2進行監聽從而收集網絡中的主鏈交易。

3.5 數據層實現

數據層實現了對交易進行hash運算和存儲。系統采用SHA-256算法對交易進行hash運算。具體做法是在生成交易信息后，對時間戳、交易內容和引用的父hash三部分進行hash運算得到一串字符串，并將它作為交易的唯一識別標識。

系統采用MySQL數據庫對交易數據進行持久化。在交易數據被持久化到數據庫中之前，系統會使用一個緩沖隊列去保存被初步驗證過的普通交易，直到接收到主鏈交易后，緩沖區內的所有交易作為一個交易子圖被持久化到數據庫中。

3.6 普通交易的方法實現

3.6.1普通交易的產生

當普通用戶節點P1產生一條新交易時，他會首先為自己的交易選擇兩個歷史交易作為父交易。這兩個歷史交易可以是該用戶指定的，也可以是系統隨機選擇的，其中選擇最新的歷史交易最佳。P1發出的普通交易結構如圖10所示。

3.6.2普通交易的廣播和接收

用戶在廣播的時候，會選擇所有其他用戶的IP地址，使用端口1進行發送數據。多個用戶可以同時發起并廣播交易。

所有用戶在通過Java ServerSocket接收方式監聽端口1的時候，會接收到P1發送的交易數據。由于實際運行過程中會接收到很多不同用戶的交易，SDAG系統中的用戶需要使用線程池提供多線程的方式接收突然而至的大量數據。在接收到P1的交易數據時，用戶節點會調用普通交易的驗證方法，并把合法交易放在緩沖區中。

3.7 主鏈交易的方法實現

系統初始化的時候會為所有用戶節點分配一定的權益值，權益值是總數一定的積分，無論各節點間的權益如何轉讓，系統中的權益總和是不變的。權益值最高的用戶節點會自動當選為PoS-PBFT主鏈共識算法中的主節點。

收到主鏈交易后，每個用戶節點會自動根據交易子圖中的交易信息感知該時間間隙內的權益變化。權益值最高的用戶自動當選下一周期的主鏈節點，權益值最高的5個節點當選為下一個周期內的主鏈委員會用戶。如果交易子圖中并無權益流動轉移，則原有節點的角色不變。

模型實現的過程中分配給P1最多的權益，即P1當選主鏈委員會中的主節點，P2、P3、P4和P5為主鏈委員會用戶中的從節點。主鏈交易由主節點P1發起，并引用主節點本地的所有葉子節點。主節點P1將主鏈交易通過端口2和IP地址發送給其他主鏈委員會用戶進行投票確認。主鏈交易結構如圖11所示。

3.8 主鏈交易的共識過程

(1) 從節點Pi(i=2,3,4,5)收到主節點P1的交易后，驗證并生成準備消息，對準備消息進行簽名后進行廣播。

(2)Pi(i=1,2,3,4,5)接收到其他用戶節點的準備消息后進行驗證。若來自不同節點的消息數量超過2f+1(f為作惡節點)并且消息一致無誤，Pi節點生成提交消息，簽名后廣播。

(3)Pi(i=2,3,4,5)接收到其他用戶節點的提交消息后進行驗證。若來自不同節點的消息數量超過2f+1并且消息一致無誤，Pi節點生成確認提交消息，簽名后廣播。

(4) 主節點P1收到包含自己在內f+1個一致的確認提交消息后，即可認為發出的主鏈交易獲得了主鏈委員會的共識。

3.9 交易的確認和存儲

在接收到共識的主鏈交易后，所有用戶會做出調整，保證在該時間間隙內與主節點具有相同的葉子節點交易和交易子圖。主鏈交易的連續性和hash值的持續增強，保證了該時間間隙內所有節點的交易子圖完整性和唯一性。

所有用戶節點根據主鏈交易內引用的葉子節點構造該時間間隙內的交易子圖。用戶節點運行交易子圖排序方法，進而為每一個交易安排一個唯一的全局順序。最后每個用戶會對雙重花費交易等惡意交易進行剔除。至此，所有用戶對歷史交易的順序達成共識。

交易子圖內的交易和主鏈交易會被存儲到每個用戶的本地數據庫中。

4 模型分析

由于SDAG數據組織方式是DAG，并且每個用戶節點都有普通交易的讀寫權限，系統可以實現并行寫入。同時普通交易的產生和主鏈交易的產生也可以并行進行，因為主鏈交易僅僅只是在普通交易子圖中做了個標記。主鏈交易不包含需要被復雜程序驗證的交易數據，驗證簡單，帶寬消耗少。以下公有鏈數據均來自官方文檔。

本文實驗采用30個用戶節點去實現SDAG模型。實驗環境所用帶寬是10 Mbit，表2是實驗節點的配置。

4.1 吞吐量分析

TPS代表每秒系統交易數，計算公式為:

TPS=TransactionNum/t

式中：t代表時間段；TransactionNum代表系統處理的交易數量。TPS是系統承載能力的指標，單位時間內系統能夠處理的交易越多，系統的TPS越高。圖12是本系統在實驗環境下的5節點吞吐量測試數據，5個節點時系統TPS最高為380。如圖13所示，隨著普通用戶節點的增多，參與共識節點數量不變的情況下，TPS穩定在330左右。

4.2 確認時間測試

由于SDAG采用PoS-PBFT共識算法，參與共識節點少，主鏈交易處理程序簡單，故而系統確認時間可以達到秒級，并且隨著系統規模的擴大，系統的確認時間僅與網絡規模相關性較強。而比特幣的確認時間是10 min左右，conflux的確認時間在7 min左右。

如圖14所示，隨著節點數的增多，SDAG的確認時間穩定在3 350 ms左右，可以為系統提供即時確認。

4.3 數據一致性分析

SDAG的主鏈共識算法采用PoS-PBFT，通過主鏈交易這個檢查點，能夠以點帶面，保證交易子圖的完全一致，進而使得所有用戶節點的本地狀態保持一致。SDAG的一致性相對于Conflux采用的GHOST共識更高，比Byteball等采用的見證人共識等滯后確定主鏈方案更可靠即時。

此外，DAG能給交易附加引用邊，該引用可以由用戶為交易設定，用來控制交易的細粒度執行順序，使得SDAG的一致性在交易的執行順序上更加深入細膩。SDAG較高的一致性使它更符合重要場景的需求，更符合智能合約的部署。

4.4 安全性分析

SDAG應用PoS-PBFT共識算法來選擇主鏈交易，因此，SDAG主鏈的安全性不低于PBFT共識算法的安全性，只要惡意用戶節點的權益低于系統總權益的三分之一，系統就是安全的。由于系統中的權益是封閉的，非系統節點不會獲得權益，權益也無法從外部補充，只能在封閉系統內部流轉，所以系統的安全性要高于PBFT的安全性。

主鏈共識算法為系統所有交易確定了線性順序，只要主鏈交易得到確認，那么全局順序就是確定的，是不可逆的。

由于系統內的最小數據單元是交易，完全重復的交易很容易被識別并被清除，所以系統不會出現鏈式結構中重復區塊分叉現象，誠實算力不會被浪費，惡意節點會被最大程度地壓制。

DAG是一種特殊的數據組織結構，其拓撲排序是唯一的。一方面，DAG中海量的分叉結構使得交易之間聯系更加緊密，另一方面普通用戶也有存儲數據的權利，所以即使攻擊者獲得了系統的掌控權，他也不可能偽造一份新的歷史交易，從而消除自己的歷史花費。特殊的結構使得SDAG也不會遭受PoS鏈式結構中的無風險支持分叉攻擊、理性分叉、幣齡攻擊、長程攻擊等攻擊。

5 結 語

本文提出一種基于DAG的區塊鏈新模型，并將PBFT共識算法與PoS結構相結合作為新模型的主鏈共識算法PoS-PBFT。由于DAG結構的特性，該模型吞吐量較高，交易間聯系更緊密。特殊的主鏈共識方法使得模型一致性比多數DAG模型更高。該模型同時還具有快速確認、交易更有序等特點。

未來工作將會進一步降低網絡通信量，根據實際場景對主鏈共識算法進行優化，尋求主鏈交易時間間隙和網絡傳輸交易數量的平衡。