基于有向無環圖的高效并行區塊鏈

洪璇　胡軍

摘? 要： 區塊鏈系統的性能制約了它的推廣應用，主要表現為交易吞吐量低、交易確認時間長和算力浪費等.針對這些問題，提出一種基于有向無環圖（DAG）的區塊鏈及其共識協議，提供區塊鏈的并行工作模式.通過3個指針提供DAG區塊的連通性;根據工作量證明（PoW）機制，將較難的區塊組成一條謎題鏈，保證區塊的有序性和系統的安全性;按照最長鏈原則和最難鏈原則，制定謎題鏈的共識協議.本方案充分利用了網絡節點的計算資源，提高了區塊鏈系統性能，減小了計算冗余度，節省了算力.

關鍵詞： 分布式賬本; 區塊鏈; 并行區塊鏈; 有向無環圖（DAG）; 共識協議

中圖分類號： TP 311??? 文獻標志碼： A??? 文章編號： 1000-5137（2022）02-0135-08

Efficient parallel blockchain based on directed acyclic graph

HONG Xuan， HU Jun

（College of Information， Mechanical and Electrical Engineering， Shanghai Normal University， Shanghai 201418， China）

Abstract：The promotion and application was restricted by the performance of blockchain system， which mainly manifested in low transaction throughput， long transaction confirmation time and waste of computing power. To solve these problems， a blockchain based on directed acyclic graph （DAG） and its consensus protocol was proposed to provide a parallel work mode of blockchain. Three pointers were used to provide the connectivity of DAG blocks. Block order and system security were guaranteed by forming a main chain of difficult blocks through the use of proof-of-work （PoW） mechanism. Aconsensus protocol on the main chain was formulated according to the longest chain principle and the hardest chain principle. This scheme made full use of computing resources of network nodes which improved the performance of blockchain system and reduced computing redundancy and computing power.

Key words：distributed ledger; blockchain; parallel blockchain; directed acyclic graph （DAG）; consensus protocol

0? 引言

近年來，人們對區塊鏈技術的局限性有了更深刻的認識，其主要表現為交易吞吐量低、交易確認時間長和算力浪費等^[1]，這制約了區塊鏈的應用和發展.因此，消除性能瓶頸可以為區塊鏈的廣泛應用提供可能.

區塊鏈采用的共識機制是影響其性能的重要因素，目前大多數有向無環圖（DAG）區塊鏈都使用工作量證明（PoW）共識機制，因為使用其他共識機制失去了區塊鏈去中心化的意義，存在安全性隱患^[2].PoW需要計算哈希難題，爭取記賬權.這種機制的優點是可以完全實現去中心化，缺點是共識達成速度較慢，浪費計算資源且算力集中.PoW共識機制能在完全去中心化的網絡環境中保證數據的安全存儲與共享.

區塊鏈的數據結構本質上是一條單向塊狀鏈表，導致確認交易和生成區塊的過程無法并行執行，性能較低.因此，將基于單向塊狀鏈表的區塊鏈擴展為基于DAG的區塊鏈，使每個DAG節點有多個出度和入度，可以支持多線程并發執行，突破了傳統區塊鏈串行處理模式的限制，提高了系統吞吐量，加快了交易速度^[3].SARFRAZ等^[4]提出了基于DAG的分布式賬本埃歐塔（IOTA），實現了良好的吞吐量性能，其交易是無序的，系統安全性無法保證.LI等^[5]開發的Conflux系統將DAG中的節點按照時間先后順序劃分成若干紀元，在每個紀元內進行選擇具有最高“權重”的區塊，得到紀元的主鏈，進而得到整個系統的主鏈，錨定了所有區塊的全序，在保持并發的情況下，能決定不同區塊的順序，但該方案較復雜，需要計算每個區塊的“權重”后，才能達成區塊之間的共識機制.CUI等^[6]開發的CoDAG系統將圖劃分為不同的級別，并通過計算其“連通性”將區塊分為不同的級別，計算量較大.WANG等^[7]提出了一種基于ID分類的有向無環圖數據結構，但沒有對方案進行詳細的設計，也沒有進行性能評估與安全性分析.322C37E6-F6B0-4DBF-9636-E806FE77B2A6

為了讓網絡節點在完全去中心化的情況下，能對高并發的DAG結構達成共識，本方案結合PoW共識機制與DAG區塊鏈技術，設計了一種基于DAG的區塊鏈結構及其共識機制.通過PoW機制選擇一些哈希難度較高的區塊組成一條謎題鏈，根據謎題鏈的最長鏈原則和最難鏈原則，得出DAG的拓撲排序.相較文獻[4?7]的方案，本方案無需再進行“權重”或“連通性”等額外計算.謎題鏈由一些難度較大的謎題區塊組成，使得區塊鏈更加難被篡改，保證了系統的安全性和一致性.本方案的礦工鏈包含了礦工的歷史記錄，可以應用在基于個人信用的場景中，體現了本方案的擴展性.

1? 數據結構設計

1.1整體結構概述

為了確保DAG上的區塊達成共識機制，設計一種緊密聯系DAG上所有區塊，且能使之有序排列的結構.考慮到生成區塊需要進行PoW計算，選擇哈希難度較高的一些區塊作為謎題鏈區塊，如圖1所示.本方案在DAG中嵌入一條謎題鏈，謎題鏈上的區塊為謎題區塊，比常規區塊更難被挖掘，但謎題區塊與其他區塊的挖掘工作流程相一致.

另外，為了能夠快速地對DAG進行拓撲排序，考慮將DAG分解退化成若干二叉樹，每個節點除了有一條連接謎題鏈節點的邊之外，還需要兩條連接別的節點的邊，以形成二叉樹的左右分支.因此，在礦工準備生成區塊的時候，需要配置3個指針指定區塊之間的關系.第一個指針peer指向礦工的前一個區塊，將礦工挖掘的所有區塊連接到一個礦工鏈中，該礦工鏈包含了礦工的信息，比如他的哈希算力等;第二個指針main指向最長謎題鏈上的最新謎題區塊，如果這個新區塊被確認為謎題區塊，那所有謎題區塊都將通過這個指針與該新區塊保持連接;第三個指針wait指向一個其他礦工挖掘的區塊，以增強DAG節點之間的連通性.根據以上連接規則，某一區塊連接節點的集合中，每個指針對應于一條有向邊，區塊之間按照時間先后順序通過指針連接，即形成了一個DAG^[8].當交易量增多的時候，前驅節點有多個入度，可以同時被多個后繼節點所指向，從而能夠支持數據的并發執行.當交易量減少時，后繼節點有多個出度，可以同時指向多個前驅節點，以加速整個圖形的收斂^[9].

1.2區塊結構

謎題鏈區塊由區塊體及區塊頭組成.區塊體中包含應用數據message，區塊頭中包含了指定區塊關系的3個指針（ptr_peer，ptr_main，ptr_wait）、生成該區塊的礦工信息peer、時間戳Timestamp、應用數據message的Merkle根、解決哈希難題的解nonce等，如圖2所示.

在所有區塊中，整個DAG中的根節點即定義為創世區塊.

1.2.1 指針

指針指定了區塊之間的關系.由于通過指針可以回溯到某個區塊的所有前驅區塊，可以將對于某區塊的共識機制擴展為所有前驅區塊的共識機制.

1.2.1.1 ptr_peer和礦工鏈

指針ptr_peer指向由同一名礦工生成的前一個區塊，如果該礦工此前沒有生成過任何區塊，則指向創世區塊.這個指針將同一礦工挖掘的所有區塊連接成鏈，即礦工鏈.礦工鏈包含了礦工的挖掘歷史，可以根據這些信息得到礦工的狀態，評估礦工的哈希算力.

1.2.1.2 ptr_main和謎題鏈

指針ptr_main指向一個謎題區塊或者創世區塊.謎題鏈以樹形結構指向并確認其他一些常規區塊.因此，只要節點對所有謎題區塊達成共識，就對整個DAG達成了共識.為此，需要將所有謎題區塊集合到一個鏈結構中，進而使所有的區塊能被謎題區塊所指定.

1.2.1.3 ptr_wait和連通性

為了增強DAG區塊間的連通性，將謎題鏈的安全性擴展到DAG中所有的區塊.使用指針ptr_wait指向另一個礦工的常規區塊或者創世區塊.

從一般區塊到謎題區塊的有向邊起到確認所有前驅區塊的作用，DAG的強連通性會帶來更快的交易確認速度.

1.2.2 區塊及其PoW共識機制

礦工為了得到區塊的記賬權，并確定區塊的類型，需要提供區塊的PoW.為了獲得PoW，在配置了指針之后，需要不斷地枚舉nonce值，直到計算出符合要求的區塊哈希.

設H為區塊的哈希值，d為常規區塊的難度值，p表示謎題區塊的難度值，d和p的取值決定了礦工生成區塊的難度和速度.本方案中，將p與比特幣的難度值設為相同值，謎題鏈與比特幣鏈的生長規則相一致，與比特幣鏈具備相同的安全性;而d的取值需要比p的取值更容易，以減小常規區塊的生成時間，提高系統吞吐量.如果H<d，則表示礦工生成了一個常規區塊;如果H<p，則表示礦工生成了一個謎題區塊.

由于謎題區塊的哈希值是難以計算的，由謎題區塊所組成的謎題鏈保證了整個DAG結構的安全性，難以被篡改.

1.3DAG結構

本節引入一些符號和定義來描述DAG結構，根據圖1所示的DAG區塊鏈結構，用G表示區塊集合，用B表示某個謎題區塊.

對于任意謎題區塊B_m∈G，由它確認的子集為：322C37E6-F6B0-4DBF-9636-E806FE77B2A6

2? 共識協議設計

DAG的結構由所有網絡節點以分布式方式集體創建和維護，下文描述了每個節點所要遵循的協議，并描述算法偽代碼.協議的目標是讓所有節點對相同的DAG達成共識，并使用相同的DAG構建有序賬本.

2.1接收區塊

假設節點a本地存儲了（G_a，B_m），G_a是節點a的本地DAG結構，B_m是G_a中的謎題區塊.

此時，節點a通過廣播接收到區塊B.

首先，檢查B對G_a是否合法.如果是，在DAG結構中添加B，并更新G_a;否則，丟棄該區塊.

然后，根據最長鏈原則和最難鏈原則更新B_m：

即如果新的謎題區塊高度比原來的更高，則更新B_m;如果兩個謎題區塊的高度一樣高，但新的謎題區塊的難度比原來的更難，則更新B_m;其他情況，不更新.最長鏈原則和最難鏈原則使得每個謎題區塊都是當前水平集中生成難度最大的區塊，保證了區塊鏈更加難以被篡改.

2.2交易分配

按照DAG的并行工作模式，同一交易可能被多個礦工重復納入多個區塊中，造成數據冗余，增加存儲負載，浪費系統算力.因此，需要設計一種交易分配機制，有效降低一個交易被多個礦工處理的概率.通過計算哈希值H（H（B_i），T）作為交易T和礦工狀態B_i（礦工i的礦工鏈上的最新區塊）之間的距離，動態地限制礦工可以處理交易的數量，再通過礦工鏈統計出該礦工i在水平集中生成的區塊的比例q_i∈[0，1]，作為該礦工哈希算力的評估值.如果滿足條件

2.3生成區塊

生成區塊算法如圖6所示.假設礦工i本地存儲了（G_a，B_m，B_i），其中，G_a是礦工i的本地DAG結構;B_m是G_a中的謎題區塊;B_i是i的礦工鏈上的最新區塊.

如果礦工想生成一個新區塊B_n，并讓它成為其本地DAG的一部分，則需要按如下步驟進行工作：

1） 根據式（1），篩選符合條件的交易信息，生成message.

2） 配置B_n.ptr_main←H（B_m）;配置B_n.ptr_peer←H（B_a），其中，B_n和B_a是礦工i生成的兩個連續的區塊;配置B_n.ptr_wait←H（B_w），其中，B_w是另一條礦工鏈的常規區塊.

3） 進行PoW，生成nonce.不斷地調整nonce值，并對這個區塊進行哈希運算，直到H（B）<d.

4） 最后，通過點對點網絡廣播B_n.

2.4獎勵方案

為了提高區塊鏈系統的性能，在2.3節中定義合法指針的基礎上，指針還應滿足以下約束：

1） 新區塊應指向自己礦工鏈上的最新區塊;

2） 新區塊應指向最新謎題區塊;

3） 新區塊應指向另一條礦工鏈上的最新常規區塊.

因此，為了激勵礦工遵守上述約束規則，設計獎勵方案.礦工可以從一個區塊中獲得多少獎勵取決于三個因素：區塊類型、區塊位置及區塊中交易的有效性.

首先討論區塊類型，因為分叉的謎題鏈形成了一棵謎題樹，在計算獎勵時，將不在最長謎題鏈上的謎題區塊視為常規區塊.為了便于描述，以下將常規區塊和分支謎題區塊統稱為非謎題區塊.因為謎題區塊更難生成，所以設置r_m>r_n，其中，r_m表示謎題區塊的固定獎勵，r_n表示非謎題區塊的固定獎勵.

如果礦工生成了一個謎題區塊，除了固定獎勵r_m和有效交易的費用外，還會獲得額外βR（B_m）獎勵.假設參數β=2%，礦工將額外獲得高于該謎題區塊所在水平集中所有常規區塊2%的獎勵.另外，由于額外的獎勵取決于水平集中的區塊數量，這將激勵礦工將新區塊指向另一個礦工鏈上的最新常規區塊，以最大化該水平集中區塊的數量.礦工鏈的分叉區塊產生的獎勵為0，從而激勵礦工保持自己生成一個沒有分叉的礦工鏈，如表1所示.322C37E6-F6B0-4DBF-9636-E806FE77B2A6

2.5構建分布式賬本

分布式賬本是交易的有序列表，要構建分布式賬本，需要獲得DAG中區塊的有序序列.根據上述共識協議，網絡節點擁有相同的DAG，再使用同一個算法來對相同的交易集進行排序，就能構建出相同順序的分布式賬本，如圖7所示.

根據前文描述，DAG中的區塊是按水平集組織的，因此，首先根據水平集中謎題區塊的高度從低到高劃分每個水平集，再對每個水平集內的區塊進行排序.每個水平集其實是一棵有向二叉樹，樹的根節點是第k個謎題區塊B_m，k，樹的每一條有向邊是指針集合{ptr_peer，ptr_wait}.這里不考慮ptr_main，因為它指向前一個水平集.使用深度優先搜索（DFS）的后序遍歷方法，從根B_m，k開始沿著有向邊遍歷這棵樹，先按ptr_peer遍歷，再按ptr_wait遍歷，即可得到每個水平集中區塊的順序.雖然對二叉樹進行排序，有很多種排序算法，都能夠產生唯一的序列達成共識目的，但采用DFS的后序遍歷能保持礦工鏈上區塊的時間順序排列，優先遍歷到的區塊，即為生成時間較早的區塊.

按照上述的水平集順序和每個水平集中的DFS后序排序即可得到一個有序的交易列表.

2.6應用場景分析

遵循以上DAG區塊鏈結構及其共識協議，最終在點對點網絡上的節點都將擁有相同的本地DAG視圖和相同的分布式賬本.本方案適用于需要去中心化、業務高效并行、記錄個體信用、分離業務數據的應用場景，例如物聯網應用場景.

因為物聯網內的智聯設備需要實現端到端的自動化連接，所以物聯網本身就是一個去中心化的網絡模型.另外，隨著物聯網的發展，在網絡中有海量業務數據需要實時高速地傳輸和共享.傳統區塊鏈的串行工作模式顯然不能滿足物聯網的業務需求，而使用本方案的DAG區塊鏈模型，除了能滿足以上基本需求，還能利用礦工鏈分別記錄單個設備的日志數據，以供網絡維護，并進行精確查詢分析;還能利用指針ptr_wait將不同設備的礦工鏈進行耦合，以表示設備間的通信關系.

3? 結論

本方案結合了經典PoW共識機制與新型DAG區塊鏈技術，設計了一種以謎題鏈為主鏈的DAG區塊鏈結構及其共識機制，在不犧牲安全性且實現去中心化的前提下，提高了系統性能.

對于DAG結構的設計，提供了區塊鏈系統的并行工作模式，提高了系統節點的算力利用率，提高了交易吞吐量，縮短了交易確認時間.并行的區塊和分散的獎勵也減小了礦工們組成大型礦池的需求，避免算力集中和大部分攻擊隱患，進一步提高了系統安全性.

對于謎題鏈的設計，保證了本方案的安全性和一致性.通過哈希值難度即可篩選謎題區塊，不用額外計算區塊的權值、連通性.謎題鏈由難度最大的一些謎題區塊組成，使得區塊鏈更加難以被篡改，而且由于DAG的強連通性，謎題鏈的安全性將擴展到DAG中所有的區塊.此外，謎題鏈還提供了交易順序，以便所有礦工一旦對DAG達成共識，就能夠建立相同的分布式賬本.

礦工鏈的設計，提供了本方案的擴展性.礦工鏈包含了礦工的歷史記錄，可以將本方案應用在基于個人信用的場景，甚至可以抽象為某個業務部門的業務鏈，分離一個集團內不同部門的數據.此外，根據礦工鏈中的礦工信息，能夠設計出一種基于DAG的交易分配機制，該方法可以根據礦工鏈狀態，以不同的概率將交易分配給他們，降低同一個交易被多個區塊重復記錄的概率，降低了數據冗余，從而減少資源的浪費，進一步提高了處理效率，縮短了交易確認時間.

參考文獻：[1]? YUAN Y， WANG F Y. Blockchain： the state of the art and future trends [J]. Acta Automatica Sinica，2016，42（4）：481-494.