基于有向無環圖的高效區塊鏈共識算法

王壹銘, 初劍峰, 王永軍, 陳彥東

(1. 吉林大學 計算機科學與技術學院, 長春 130012； 2. 長春市公安局 網安支隊, 長春 130051； 3. 吉林大學第二醫院 信息中心, 長春 130041)

區塊鏈技術[1]最早作為比特幣的底層技術被提出, 具有去中心化及不可篡改等特性. 但由于實現區塊鏈技術的工作量證明(proof of work, PoW)算法對計算資源要求過高, 導致浪費大量的計算資源, 且吞吐量低, 因此并不實用. PoW算法從生成交易單到出塊的時間約需10 min, 一個交易的確認需后續連續6個區塊附著在該區塊后, 即一個區塊需約1 h才能被確認放置在主鏈上. 而且PoW共識算法的區塊鏈系統每秒只能處理7筆交易, 導致區塊鏈技術不能用于物聯網或金融系統. 針對該問題, 以太坊平臺提出了一種股權證明(proof of stake, PoS)共識算法, 但該算法存在其他問題, 如出塊速度不穩定導致分叉的出現及持幣不出塊等[2]. 文獻[3]嘗試通過Gossip協議與實用拜占庭容錯(practical Byzantine fault tolerance, PBFT)算法相結合的方式改進區塊鏈共識算法. 文獻[4]提出基于零行列式策略[5]解決礦工挖礦問題, 對節點的策略選擇進行優化, 促進節點與系統獲得更高的收益[6-7], 該算法雖能解決PoW算法中的算力浪費問題, 但無法解決區塊鏈技術不能在高業務量系統中快速處理交易塊的問題. 事實上, 在比特幣的PoW共識算法中, 目標Hash值要求以42位0開頭, 平均需要242次嘗試, 從而導致了比特幣的專用集成電路(application specific integrated circuit, ASIC)問題, 即大量設備被設計用于做礦機的芯片, 導致巨大的計算硬件浪費[8]. 由于現行區塊鏈技術存在的諸多瓶頸, 導致區塊鏈技術并不適用于目前的物聯網或者金融系統. 本文通過改變區塊鏈的數據存儲結構并使數據存儲結構成為共識算法的一部分, 實現區塊鏈高效處理大量交易的目標.

1 預備知識

在區塊鏈的3種經典共識算法PoW中, 能實現去中心化的區塊鏈中心目標, 但需消耗大量的硬件資源, 而PoS共識算法為了解決該問題提出了采用股權證明機制, 但該共識算法可能導致擁有權益的用戶有過大的權利而影響區塊鏈工作. PoS共識算法在一定程度上是基于PBFT算法設計的, PBFT算法能避免PoW共識算法中的算力浪費問題, 但該算法達成共識的時間較長, 不利于區塊鏈項目在短時間內處理大量交易, 這是由傳統的鏈式結構導致的. 因此本文提出使用有向無環圖結構取代傳統的鏈式結構, 基于這種數據結構的共識算法能更好地在短時間內處理大量交易且不必占用過多的計算資源. 因此， 該算法適用于醫療大數據服務系統[9]或車載自組網系統[10].

1.1 工作量證明算法

圖1 常見的區塊鏈結構Fig.1 Normal blockchain structure

PoW算法的核心思想是通過分布式節點的算力競爭保證數據的一致性和共識的安全性. 其中每個區塊的結構中都包含了上一個區塊的Hash值, 從而形成鏈狀結構, 交易被以Merkle樹的形式組織. 圖1為區塊鏈常見的區塊結構, 比特幣項目的區塊就采用了這種結構. 其中, Nonce為一個隨機數, 礦工Bob在收集交易單并打成塊后, 對區塊頭部進行Hash運算, 只有在計算結果開頭0的位數滿足當前區塊鏈要求且當前沒有其他礦工比Bob的計算更快時, Bob才可將該區塊發布至區塊鏈網絡中, 其他礦工則負責同步這一區塊, 此時Bob需等待后續的6個區塊生成, 如果這6個區塊附著在該區塊后, 則該區塊確認添加至區塊鏈中, 礦工Bob獲得獎勵.

1.2 權益證明算法

以太坊在前期均采用PoW共識算法初始積累權益, 而后期以太坊則轉向PoS共識算法, 通過權益證明機制縮短達成共識的時間, 并在一定程度上解決了PoW算力浪費的問題, 因此比特幣后的許多區塊鏈項目均采用了PoS共識算法. 在PoS共識機制中, 由系統中具有最高權益而非最高算力的節點獲得記賬權, 其中權益體現為節點對特定數量貨幣的所有權, 成為幣齡或幣天數(coin days)[11]. 在采用PoS共識機制的區塊鏈項目中, 礦工所獲得的收益獎勵主要來自于用戶交易.

采用PoS共識算法的區塊鏈項目前期需使用PoW共識算法公平分配權益, 在一定程度上仍會導致算力浪費, 且PoS共識算法并不能解決區塊鏈技術在處理大量交易時效率較低的問題, 從而導致基于PoS共識算法的區塊鏈技術不能應用在物聯網或金融系統中.

1.3 實用拜占庭算法

實用拜占庭算法[12-13]用于解決分布式系統中各節點達成共識的問題, 當系統中錯誤節點少于1/3時系統可達成共識. 該算法分為如下3個階段.

1) pre-prepare: 主節點向所有備份節點發送準備消息, 此時節點狀態為pre-prepare;

2) prepare: 包括主節點在內的所有備份節點在收到準備消息后, 確定無誤, 向外廣播消息, 并且進入prepare階段；

3) commit: 當收到若干來自其他副本的prepare信息后即可進入commit階段.

PBFT算法相對PoW算法計算簡單, 不需要消耗大量計算資源, 但如果在大規模的區塊鏈網絡中使用, 其通信量會急速上升導致出現系統瓶頸[14]. PBFT算法并不能解決區塊鏈處理區塊時的效率低問題[15].

2 區塊鏈數據結構設計

2.1 基本區塊結構

圖2為一個基于ID分類的有向無環圖結構. 該數據結構的主要功能是建立高效的生成區塊機制. 基本區塊結構由ID塊、 交易塊和起始塊組成. 在該區塊鏈系統中, 每個用戶都可以擁有多重身份, 用戶既可作為交易方尋求與他人交易, 也可作為礦工幫助其他用戶認證交易塊. 其中, 每個用戶都擁有一個獨立的ID, 當用戶注冊并進入區塊鏈系統時即產生一個與該ID相關的ID塊, 交易塊附于相對應的ID塊后, 負責記錄每筆交易的內容. 而起始塊是所有ID塊的父節點. 通過基于ID分類的有向無環圖結構可實現所有礦工能在同一時間生成區塊而不必等待其他礦工打包區塊, 該機制從根本上解決了區塊鏈無法應用于短時間內處理大量交易的問題. 圖2中箭頭表示區塊的先后附屬關系, 在每個ID塊的后續區塊都應根據雙方的交易筆數有序地附著在區塊后, 標號為0的區塊即為起始塊, 其為所有ID塊的父節點, 其中A/B/C/D為ID塊,BA為用戶ID為B的用戶與ID為A的用戶產生交易的交易鏈起始區塊(區塊結構為交易塊, 但交易內容為空),BA1為B與A之間的第一筆交易. 圖2中的4位用戶可同時開展交易并等待礦工簽名完成即可確認區塊, 不需像PoW類共識算法等待6個區塊才能確認區塊. 通過這種基于ID分類的有向無環圖結構能有效提升區塊鏈項目處理交易的效率.

2.2 ID塊

ID塊的內容包括身份編號、 公鑰和數字簽名, 其中ID編號為有向無環圖中交易塊分類的標準, 其子節點記錄的交易塊內容為該ID擁有者與其他用戶交易的記錄. 同時, ID塊中存儲的內容可用于證明該ID擁有者的身份, 并能輕松被他人驗證.

2.3 交易塊

系統中的每個用戶擁有一個公開的包含一系列交易的區塊鏈, 交易塊內容包括交易塊身份編號、 交易發起方身份編號、 交易發起方數字簽名、 交易接收方身份編號、 交易接收方數字簽名、 前一區塊身份編號、 前一區塊Hash值、 Merkle樹根節點值、 前一區塊礦工簽名列表、 交易內容、 剩余簽名次數、 本區塊礦工簽名列表、 礦工獎勵列表、 區塊完成時間. 其中交易塊ID編號表明交易塊所處區塊鏈中的位置, 交易雙方簽名用于確保交易內容為真, 前一區塊信息用于礦工比對交易塊位置, Merkle樹記錄當前區塊礦工簽名列表, 但只保留根節點值(如果同時有兩組礦工完成區塊出塊, 則擁有更小的Merkle樹根節點值的區塊完成區塊出塊操作), 避免了不同礦工之間不能公平獲得挖礦機會的問題, 如果剩余簽名次數為0, 則表明該交易塊正處于完成礦工簽署階段等待被同步至區塊鏈網絡中, 或該區塊已經簽署失敗, 此時需交易發起方重新組織區塊發布至區塊鏈網絡中等待簽署.

2.4 起始塊

起始塊是所有ID塊的父節點, 本身不記錄信息, 用于維持整個區塊鏈的有向無環圖結構.

3 共識算法設計

3.1 交易塊生成算法

交易塊生成算法主要分為三階段: 第一階段由交易雙方生成交易單并完成創建起始交易塊, 對交易塊的交易內容進行簽名以保證交易塊的合法性; 第二階段即礦工驗證區塊并簽名階段, 礦工簽名完成即表示完成對交易塊內容合法性的確認； 第三階段則是最后一位參與簽名的礦工將第二階段完成的交易塊廣播至整個區塊鏈網絡, 所有節點同步新的區塊, 至此交易成功并被記錄至區塊鏈中.

在第一階段中, 交易雙方需要協商并完成對交易內容的簽名, 完成簽名后, 由交易發起方創建區塊, 完成交易區塊的主體結構后將交易塊廣播至區塊鏈網絡中, 等待被礦工簽名并驗證合法性, 最終生成的區塊需要被附著到交易發起方所在ID區塊的鏈上.

在第二階段中, 礦工需要完成對第一階段生成的初始交易塊的簽名驗證工作：

1) 礦工端首先檢查rst字段, 如果該字段值為0, 則該區塊(T-Block)被拒絕并廣播給網絡中的其他礦工, 這一區塊在該礦工端的交易塊生成算法終止, 表示為

(1)

其中:m為區塊信息;T-Block為區塊; Forward( )函數表示廣播區塊;Tpbml表示區塊進行第二步操作; pbml為前一區塊的礦工簽名列表;

2) 檢查前一區塊礦工簽名列表, 如果該礦工的ID出現在此列表中, 則說明該礦工已參與過該區塊的簽名, 此時區塊應該被拒絕并廣播給網絡中的其他礦工, 這一區塊在該礦工端的交易塊生成算法終止;

3) 判斷已簽名礦工ID(p)是否出現在前一礦工簽名列表中, Serch( )函數表示如果發現存在已簽名礦工ID與前一礦工簽名列表中的礦工ID匹配成功, 則說明存在礦工違反操作規則的情況, 區塊被拒絕并廣播給網絡中的其他礦工, 這一區塊在該礦工端的交易塊生成算法終止, 表示為

Tcheck=Search(msl,pbml,p),

(2)

其中msl為本區塊礦工簽名列表;

4) rst值自減1, 表示為

rst=rst-1;

(3)

5) 通過區塊中交易雙方的公鑰驗證雙方簽名是否合法, 如果簽名合法性驗證失敗, 則礦工拒絕簽名并將區塊廣播給網絡中的其他礦工, 這一區塊在該礦工端的交易塊生成算法終止, 表示為

Tsignature=Ω(CheckSign(T-Block,ga,Pub-keya),CheckSign(T-Block,gb,Pub-keyb)),

(4)

其中:Ω表示對雙方簽名驗證結果的校驗函數; CheckSign( )函數表示對礦工簽名合法性驗證;ga,gb分別為交易雙方數字簽名; Pub-keya,Pub-keyb分別為交易雙方公鑰;

6) 檢查區塊是否被放在正確的位置, 如果檢查失敗, 則拒絕區塊并將區塊廣播給網絡中的其他礦工, 這一區塊在該礦工端的交易塊生成算法終止;

7) 依次檢查礦工簽名列表中其他礦工的簽名是否合法, 如果任意一個簽名驗證失敗, 則該區塊簽名失敗, 拒絕該區塊并將其廣播給網絡中的其他礦工, 這一區塊在該礦工端的交易塊生成算法終止;

8) 礦工對該區塊進行簽名, 使用橢圓曲線數字簽名(ECDSA)方式通過區塊m、 隨機數r及私鑰Keyprivate生成數字簽名(m,g), 表示為

Tsign=ECDSA(m,r,keyprivate)=(m,g);

(5)

9) 礦工需確認自己是否為最后一位參與簽名的礦工, 即檢查待簽名人數(rst)字段, 如果rst≠0, 則該礦工不是最后一位參與簽名的礦工, 該區塊則廣播給網絡中的其他礦工, 該礦工對這一區塊的工作完成, 表示為

(6)

10) 若該礦工為最后一位參與簽名的礦工, 則需檢查簽名失敗次數是否符合設計要求(不能多于2次), 如果簽名失敗次數超過2次, 則宣告該區塊簽名失敗, 此時應通知交易發起方重新組織區塊, 表示為

(7)

q=10-count(msl),

(8)

其中: msl為礦工獎勵列表中的礦工ID; count( )函數用于統計數量;q表示失敗次數;

11) 最后一位礦工創建一個獎勵列表以標明每位參與簽名礦工的獎勵, 當他完成了該項工作時, 區塊正式生成并添加至區塊鏈中, 每位區塊鏈中的全部節點記錄這一區塊.

在第三階段中, 已經簽署完成的區塊由最后一位參與簽名的礦工廣播至區塊鏈網絡中, 每位參與該區塊簽名的礦工此時得到獎勵, 如果最后一位礦工在獎勵發放部分作弊, 則每位參與簽名的礦工都可向區塊鏈網絡中廣播最后一位礦工作弊的信息, 如果超過1/3的參與該區塊簽名的礦工發布該信息, 則該區塊簽名過程中作弊礦工的獎勵作廢, 并由參與簽名前兩位礦工生成交易塊, 將作弊礦工的失信信息作為交易內容存儲于區塊鏈中. 由于本系統采用有向無環圖結構, 記錄礦工失信信息并不影響后續區塊的生成, 因此不會對交易塊的高效處理產生影響.

3.2 算法分析

3.2.1 有向無環圖結構 該算法中采用的數據結構有別于有向無環圖結構, 是在有向無環圖的基礎上根據用戶ID再進行分類. 這種數據結構能保證所有用戶均可在同一時間創建起始區塊, 而不必如傳統區塊鏈那樣等待其他區塊生成完畢后才獲得機會生成區塊, 并且在生成區塊后, 不需要如PoW共識算法那樣需連續6個區塊的確認才能保證區塊成功添加至區塊鏈系統中.

3.2.2 獎勵機制 在PoW類型的區塊鏈共識算法中, 獎勵機制是基于礦工挖礦的速度決定獎勵值, 只有計算最快的那個礦工可獲得獎勵, 而其他參與計算的礦工則浪費了算力資源. 本文算法中區塊生成后參與簽名的礦工都可獲得獎勵, 且不以簽名的先后次序決定獎勵值, 從而避免了PoW類型的區塊鏈共識算法中由于礦工競爭而導致的資源浪費.

3.2.3 安全性 由于算法中同一組礦工不能在1 d內一起簽署超過一個區塊, 因此當惡意礦工控制多個用戶時也不會影響區塊鏈系統的整體運行. 該機制同時也保證了每位礦工挖礦的公平性, 不同于PoW類型的區塊鏈共識算法中擁有更多計算能力的礦工可獲得簽署區塊的權利, 在本文算法區塊鏈系統中, 所有活躍的礦工均可公平地獲得簽署區塊的權利.

3.2.4 出塊效率分析 不同于PoW類型共識算法, 本文算法中參與簽名的礦工只在計算Merkle樹時會占用計算資源, 顯著低于PoW共識算法, 且不同于PoS共識算法中根據用戶具有多少權益決定出塊權利, 因此本文算法減少了投票的步驟, 同時保證了礦工參與挖礦過程的公平性.

綜上所述, 針對傳統區塊鏈算法存在效率低和大量資源浪費的問題, 本文提出了一種將區塊鏈設計成有向無環圖結構, 并通過設計區塊生成共識算法將礦工簽名與區塊存儲結構相結合的算法, 解決了現存區塊鏈項目在面對大量交易時效率較低的問題, 同時節省了計算資源. 該算法能快速處理大量交易, 并支持全體用戶在同一時間進行交易同時生成區塊, 解決了現存區塊鏈項目中礦工由于等待其他區塊生成所需耗費更多時間的問題. 不需要采用PoS類算法的區塊鏈項目通過選舉產生記錄區塊權力的方法, 因此本文算法比PoS類算法能更公平且高效地生成區塊.