從區塊鏈到DAG（二）MEERDAG的前世今生

前言

 區塊鏈 3.0 的發展前景曾一度被人們熱議，其中 DAG 被認為是繼比特幣、以太坊後最有潛力崛起的新一代區塊鏈技術，那么 DAG 區塊鏈的由來是什么？其技術理念是什么？

                           左為Aviv Zohar    右為Yonatan Sompolinsky

 DAG 與區塊鏈原本是兩項不同的技術，而將兩者結合，提出“DAG 區塊鏈”這一概念並首次現身在人們視野，離不开兩位以色列人 Yonatan Sompolinsky 和 Aviv Zohar，他們是這一先鋒概念的提出者。

Aviv Zohar 提出的 GHOST 協議曾被以太坊早期採用過，該協議解決的是鏈分叉所帶來的安全性問題，分叉的區塊鏈數據結構在 GHOST 協議規則下從一條單鏈演變成一個樹鏈（ Tree chain ）。之後 Aviv Zohar 進一步提出 Inclusive 協議，在 Inclusive 協議規則下，區塊鏈的數據結構演變成有向無環圖即 DAG。隨着 DAGlabs 對 DAG 不斷探索逐漸建立 BlockDAG 框架概念與技術架構，期間相繼發布 SPECTRE 協議、PHANTOM 協議與 GHOSTDAG 協議。

Qitmeer 在立項之初就在探索不犧牲去中心化(分區容錯性)和安全性（一致性）解決可擴容性（可用性）的共識協議，發現與 BlockDAG 的設計理念不謀而合。

BlockDAG 從狹義上可以理解為一種共識協議的技術框架，旨在保證去中心化與安全性的前提下，進一步提升高並發性能的 DAG 技術。基於工作量證明 PoW 共識機制能確保區塊鏈網絡足夠去中心化，因此挖礦產生區塊成為其重要的技術特點，故稱為 BlockDAG。

Qitmeer Team 針對 GHOSTDAG 和 SPECTRE 的共識算法做了大量的工程級優化，保留兩方協議的優點，創造出了具有自身特色的 MeerDAG 協議。

一、   DAG 的基本結構

1.1   DAG 長什么樣

我們都非常熟悉 Merkle 樹的這種數據結構，比特幣每個區塊的內部就是用 Merkle 樹來記錄交易信息的，見圖1。

圖1 區塊結構

可以看出來，Merkle 樹屬於一種有向樹結構，樹裏的每個頂點只能指向一個之前的頂點，整個數據有個明顯流動方向。

DAG 結構則可以允許每個頂點指向多個之前的頂點，整個數據流也有一個明顯的方向。另一種數據結構為有向圖，與 DAG 不同的是有向圖允許有數據回流，整個結構的數據流不是很明顯。三者之間的區別見圖2。

圖2 有向樹、DAG圖和有向圖示意

1.2   區塊鏈是一種特殊的 DAG 結構

在對 DAG 結構有一個直觀的認識之後，我們來梳理一下為什么認為區塊鏈是一種特殊 DAG 結構？

區塊鏈是否分叉和出塊速度以及廣播速度有關。當出塊速度超過廣播速度的時候，會出現多個區塊同時在廣播的情況，分叉也就產生了，分叉越多安全性越差。比特幣為了減少分叉，在性能和安全性中找到的平衡點為：每十分鐘出一個塊。現在我們假定每次出塊的時間足夠長，長到不會出現前一個區塊還沒廣播結束就有新區塊挖出的情況。那么這個區塊鏈的結構就是一條單鏈，如圖3。

圖3 單鏈結構

實際上，由於網絡延遲等原因難免出現分叉的情況，所以實際的區塊鏈結構會如圖4所示，再通過账本共識的最長鏈原則只取其中一條有效的主鏈（白色），剩下的區塊（紅色）裏的交易信息都是無效的，不會被採納。

圖4 結合账本共識的區塊鏈結構

現在先拋开账本共識，即先不考慮如何選取有效的主鏈，單從底層網絡結構上看，一個典型的區塊鏈結構如圖5所示，一個典型的 DAG 結構如圖6所示。

圖5 區塊鏈結構

圖6 DAG結構

可以看到，兩種結構唯一的不同就是 DAG 的區塊可以指向之前的多個區塊，而區塊鏈的只能指向之前的唯一的區塊。具體來說區塊鏈的區塊頭只能包含一個區塊的哈希值，指向唯一的父區塊；而 DAG 結構下區塊的區塊頭可以包含多個區塊的哈希值，指向不同的前代區塊。如圖7所示。

圖7 區塊鏈和DAG結構的區塊頭指向

現在我們引入分叉系數 K，指代網絡可以允許的分叉個數。當 K=0 的時，整個網絡不允許分叉，如圖3。這種不允許分叉的網絡就是區塊鏈。比特幣就符合這個定義；以太坊雖然有叔區塊的分叉，但是這些叔區塊僅僅用作判斷主鏈權重的計數，他們最後是不會被添加到主鏈上的（叔區塊記錄的交易信息不計入主鏈），所以以太坊也符合這個定義。DAG 網絡的 K 值一定是大於 0 的整數。所以從結構上看 DAG 是區塊鏈結構的拓展，區塊鏈是一種特殊的、簡化的 DAG 。

1.3   DAG 結構對性能的影響

簡單來說，我們可以把 DAG 看成一種允許分叉的網絡結構，允許的分叉個數由分叉系數 K 決定。那么一個允許分叉的網絡到底意味着什么？意味着出塊的速度可以超過廣播速度。這一方面導致單位時間內打包的交易變多了；另一方面當一個區塊 A 在被全網廣播的時候，另一個分叉區塊 B 也在被全網廣播，最後一些節點只會確認 A，另一些節點只會確認 B，所以 DAG 允許網絡中的節點在同一時間記錄的不一樣的信息。這兩方面綜合起來就使 DAG 呈現出高並發，弱同步的特點。DAG 是一種異步記账，這種記账方式可以極大的提高網絡處理信息的速度，即 TPS。而區塊鏈是一種強同步記账的網絡，它要求網絡中的每個節點在同一時間記錄相同的信息。然而這一要求往往限制住了區塊鏈網絡處理信息的能力，使 TPS 比較低。

那么問題來了，這種允許分叉的異步記账網絡要用什么樣的共識？在上一篇文章中我們將詳細提到基於 DAG 的共識機制。共識機制分為出塊共識和账本共識，DAG 的出塊共識可以和區塊鏈一樣，比如也採用 PoW，由於允許分叉，所以出塊時間可以被設置的非常短。出塊共識也可以和區塊鏈不一樣比如 IOTA 項目，直接取消了打包出塊這一過程，只要發生交易就立刻寫入網絡（ DAG 圖中的每個方塊不是區塊而是一筆筆的交易），由此獲得超高速處的交易處理的能力。

DAG 账本共識要比區塊鏈復雜得多。要如何預防節點作惡？當出現兩個相互矛盾的交易時要怎么篩選？如何防止“雙花”？隨着底層網絡結構的復雜化，账本共識也被賦予更高的要求。在後續的文章中將會着重介紹。

1.4   TXDAG 和 BlockDAG

廣義的 BlockDAG (區塊圖)和 TxDAG (Transactional DAG , 交易型 DAG )的區別。廣義上或從數據結構上說，BlockDAG 和 TxDAG 只是兩種不同的數據結構。區別只是前者會將多筆交易打包成區塊，账本是由區塊組織而成；而後者並沒有區塊的概念，账本是由交易組成，也可以理解為一個區塊裏面只有一筆交易。由於交易有許多共同的交易描述性信息，即頭部信息，這部分信息可以存在區塊中，交易只需保存交易間不同的部分，這樣就跳過 HASH 的過程（即挖礦），直接上鏈。由於 BlockDAG 既保留了 DAG 的高並發，同時一個區塊內打包多筆交易，而因此 BlockDAG 账本的存儲效率以及傳輸效率會比 TxDAG 高。

1.5   DAG 的優勢

DAG 相比於區塊鏈來說，其實是圖和鏈的區別，對於鏈而言，無法只處理一個局部，因為鏈的入度和出度只有一個，不能把鏈上的節點拆成好幾個節點去處理，但是對於圖卻可以，因為圖可以有多個出度，那么可以同時處理多個出度連接的節點。

對於鏈式網絡而言，不是節點的處理能力不強，只是鏈式結構不能並行計算，浪費的時間其實主要為等待時間：一個是發起交易，需要將交易同步所有節點；另一個確認時間，當有一個節點確認，需要向全網同步。對於 DAG 而言則不存在這樣的問題，錢包發起交易時不需要等待自己之前有多少交易，只需要經歷局部校驗、全網廣播、其他局部校驗，相當於是把交易確認分散化，每一個節點都在做類似於拼圖的工作，把自己的和別人確認的交易拼接起來。

因此總結發現 DAG 有着以下幾個優勢：

1.5.1   交易速度塊

在達到與比特幣和以太坊相同級別的去中心化和安全性的同時，DAG 局部處理和並行結算可以使得交易速度大幅度提升，使交易吞吐量 (TPS) 和最終延遲方面超過兩個數量級的提升。

1.5.2   拓展性強

由於 DAG 支持異步記账，網絡中的節點無需等待其他節點數據同步即可並行處理新的交易，避免了時間浪費，提高了交易效率，讓每一個參與記账的節點能夠快速得到大幅度延展。因此DAG 很適用於支付類項目，例如 Qitmeer Team 所倡導的跨境小額支付和普惠金融業務場景。

1.5.3.   作惡難度更大

相比於鏈式結構，在 DAG 中惡意修改的難度會大很多，因為 DAG 擁有着很多的出度和入度，假如要修改某一個節點，那么對應的出入度都要進行修改。

二、   MeerDAG的前世今生

2.1   DAG 技術的起源

2013年在著名的區塊鏈發源地 bitcointalk.org 一名 ID 為 Avivz78 的以色列希伯來大學學者，他提出將 DAG 概念作為一種共識算法引入到區塊鏈結構中，並創造出 GHOST 協議。

圖8 GHOST協議

在 GHOST 協議提出後，Yonatan Sompolinsky 提出另一種新的設想，新產生的區塊指向所有已知的分叉末端區塊，即一個區塊有多個父親，此時區塊鏈就從一條鏈變為多條分叉鏈共同組成的的結構，這樣的鏈結構就被叫做 DAG(有向無環圖)。

圖9 DAG(有向無環圖)

2016年發布 SPECTRE 技術協議論文，該論文進一步完善了技術架構的細節，形成了初代 BlockDAG 協議雛形，並提出了網絡延遲無參數化（或稱延遲參數自適應）的宏偉構思。

圖10 SPECTRE區塊鏈示意圖

2018年，DAGlabs 推出了 PHANTOM 協議，解決了 SPECTRE 協議不能交易线性排序的問題，並在不斷優化後形成了 GHOSTDAG 協議，算是第一個工業級的 BlockDAG 協議，同時也標志着 BlockDAG 走向成熟。

圖11 連通度為2的GHOSTDAG協議下的DAG圖

Yonatan Sompolinsky 在 GHOSTDAG 協議論文結尾處，曾設想將 GHOSTDAG + SPECTRE 結合起來的可能協議，但最終沒有詳細展开介紹。

三、  MeerDAG 的技術選型的思考

3.1   MeerDAG 技術選型思考

在 Qitmeer Network 的第一個階段麥加時期（Mecca Network），正值擴容技術探索的熱潮，面對着衆多鏈上鏈下主流擴容方案，在進行 Qitmeer 公鏈技術選型的時候，也面臨着艱難的抉擇。

在擴容技術選型上，業界普遍面臨着一個不可能三角的難題， 無法同時達到可擴展性（Scalability）、去中心化（Decentralization）、安全（Security），三者只能得其二。當時的 Qitmeer 團隊也同樣面臨着這樣的難題，在研究過衆多擴容方案後，最終一種稱為 BlockDAG 的技術受到了團隊的青睞。

3.2   SPECTRE 協議簡介

SPECTRE 是一個支持快速確認的 blockDAG 協議。SPECTRE 的共識算法是一個投票算法，一旦發現有衝突交易，則包含衝突交易的區塊作為候選人接受所有區塊的投票，每個區塊一票。SPECTRE 的投票有放大效應，比如說區塊會跟隨其過去集中票數的大多數投票，所以收斂速度很快，一點細微的票數差異就能造成優勝者的巨大優勢。讓誠實區塊投票給誠實的區塊，後邊的誠實區塊會給前邊的堆疊算力，從而讓惡意攻擊失敗，保障網絡的安全性。

SPECTRE 只能保證誠實區塊的快速確認，對於發布時間接近的兩個衝突區塊，SPECTRE 的確認時間是不確定的，這就是 SPECTRE 提出的弱活性的概念，即不能保證所有區塊都能在某個合理的時間內得到最終確認。

SPECTRE 是基於交易系統的共識協議，在交易系統中只有作惡者才能制造雙花交易，也就是說，雙花交易並不會對誠實區塊造成太大的影響。而制造雙花交易對於時間的控制又是異常苛刻，一般情況下很難造成攻擊。因此 Qitmeer Team 認為 SPECTRE 這個弱活性的問題在實際項目中是可以接受的。

3.3   GHOSTDAG 協議簡介

從上面 SPECTRE 的簡介可以看出，SPECTRE 可以很好的排除衝突交易，抵御攻擊。如果項目和比特幣一樣只作為支付用途的話，SPECTRE 協議的快速確認已經足夠，但若是要集成智能合約功能，那 SPECTRE 無法勝任。

因為 SPECTRE 只能對衝突交易做一個相對排序（判斷衝突交易間的先後順序），無法給所有的區塊都做一個絕對排序。又因為智能合約的語言是圖靈完備，就像我們編寫一段計算機程序一樣，需要按嚴格的順序執行各種運算，所以，具備智能合約功能的網絡都有一個特徵：網絡中的交易可以按時間先後做线性排序（時序性）。

對此 Yonatan Sompolinsky 新設計了 GHOSTDAG 協議來對 DAG 區塊形成一個线性順序，其中 SPECTRE 和 GHOSTDAG 則是兩個完整的獨立協議，而不是一個協議對另一個協議的補充。

GHOSTDAG 的挖礦機制和 SPECTRE 一樣，會產生同樣類型的 DAG 結構，不同的是 GHOSTDAG 通過對區塊連通度分析，判定區塊誠實還是惡意，按照分類對區塊排序，對 DAG 區塊產生一個嚴格的线性順序，通過线性順序來判斷衝突交易有效性。

GHOSTDAG 協議不僅使 DAG 獲得了交易线性排序能力，也解決 SPECTRE 協議的弱活性問題。同時，GHOSTDAG 協議也是第一個支持交易线性排序的 BlockDAG 協議。

3.4   MeerDAG 協議

Yonatan Sompolinsky 在 GHOSTDAG 協議論文結尾曾設想的 GHOSTDAG + SPECTRE 結合起來的可能協議，更多的是在思路上提供指導，側重點還是在論證算法的嚴謹性，涉及到諸多工程實踐問題，還需要依據實際情況不斷實踐與測試，其中最典型的一個問題就是性能，如果按照原文的參考算法直接去實現，性能幾乎是沒法接受的。

Qitmeer Team 考慮到公鏈底層的應用場景主要是普惠金融、數字資產交易、供應鏈管理。在綜合考慮區塊的獎勵機制和账本共識對於线性排序能力要求，同時兼顧對價值交換體驗更加重要的交易確認速度。雖然 GHOSTDAG 的藍色集（誠實區塊）比較難以穩定，確認時間會比 SPCTRE 長很多。但由於區塊獎勵對於確認時間的要求不高，並不會對網絡造成影響。所以，選擇了 GHOSTDAG 協議為基礎共識協議、 SPECTRE 協議作為輔助共識協議。

MeerDAG 這種融合了 SPECTRE 和 GHOSTDAG 的混合共識方案，便是一個符合經典區塊鏈設定（开放，公平，安全，可擴展性）、並且能兼容經典區塊鏈模型 UTXO 。雖然經典區塊鏈會把最長鏈之外的區塊全部拋棄，但 MeerDAG 的 BlockDAG 協議的合作模型，會保留所有的區塊，因此，保障真實交易級的高吞吐量的同時也能對交易進行快速確認。其次，BlockDAG 是基於最重鏈規則，能達到跟比特幣相當的51%容錯性。再者，BlockDAG 網絡是不存在任何特殊節點的, 也不對節點在线與否做要求。在挖礦中，這種協作模型在安全性、开放性、公平性和可擴展性之間實現了經典區塊鏈度量的理想平衡，通過工作量證明機制，可以自由進出網絡。

在Qitmeer Network Medina 時期，網絡引入真實算力環境測試，團隊不斷迭代 PoW 算法並提升算法運行效率，充分保留 GHOSTDAG + SPECTRE 協議優點，在工程實現中不斷降低協議的實現難度，例如：按照初版的 GHOSTDAG 算法論文，算反錐體是要去窮舉的，算法復雜度是 O（n^3），經過大量工程級別測試將復雜程度降低兩個數量級達到 O（n），極大的滿足可用性需求。在保證安全性、去中心化和公平性的基本要求下，TPS 性能得到最大的釋放。為高性能的區塊鏈網絡提出了自己的解決方案，Qitmeer Network旨在構建為去中心化應用程序提供的一個更高效、安全、开放的去中心化平臺。

Qitmeer Team 創新性的將 GHOSTDAG+SPECTRE 協議結合起來並形成具有自身特色的 MeerDAG 協議，成為新一代 BlockDAG 的技術原型。Qitmeer 的 BlockDAG 底層網絡核心定位便是作為價值流通網絡， 在 Layer2 層結合 Meer DAG驅動的可拔插虛擬機系統構建豐富的區塊鏈應用，擁抱整個區塊鏈生態。

參考資料：

[1] 從區塊鏈到DAG（二）—— DAG的基本結構：https://mp.weixin.qq.com/s/Mc2uEOLtT_Z3OMapNh1TGg

[2] 從區塊鏈到區塊DAG：https://www.youtube.com/watch?v=tk38AAV_whw

[3] Jeff Zhou：DAG高速異步區塊鏈技術：https://www.jianshu.com/p/45d73e0e74ec

[4] GHOST, SPECTRE, PHANTOM的技術原理：https://mp.weixin.qq.com/s/nGR0ld73oXgs_p_MtDcv-Q

[5] Qitmeer Team：《Qitmeer中文白皮書》：https://github.com/Qitmeer/whitepaper/releases/download/v0.6.5/qitmeer_whitepaper_cn.pdf

[6] Yonatan Sompolinsky、Yoad Lewenberg 和 Aviv Zohar： 《SPECTRE：工作量證明事件的排序: 通過遞歸投票來確認交易》 https://eprint.iacr.org/2016/1159.pdf

[7] Sompolinsky、Yonatan、Shai Wyborski 和 Aviv Zohar：《PHANTOM GHOSTDAG：可擴展的中本聰共識的泛化》 https://dl.acm.org/doi/abs/10.1145/3479722.3480990

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播信息之目的，不構成任何投資建議，如有侵權行為，請第一時間聯絡我們修改或刪除，多謝。