區塊鏈共識機制綜述

譚敏生,楊 杰,丁 琳,李行健,夏石瑩

(南華大學 計算機學院,湖南 衡陽 421001)

0 概述

比特幣(Bitcoin)概念[1]由中本聰在2008年11月1日提出,現已成為市值最大的加密數字貨幣[2]。區塊鏈作為加密數字貨幣的底層技術,實際上是一個由所有節點共同維護、共同記賬的分布式數據庫系統,具有匿名、去中心化、可追溯、不可篡改等特性[3]。區塊鏈架構主要包括分布式記賬本、點對點網絡、共識機制、智能合約、激勵機制和應用程序[4]。記賬本由區塊構成,區塊包含區塊頭和區塊體。區塊頭包括指向前一個區塊的哈希指針(prev_hash)、版本號(version)、時間戳(ntime)、隨機數(nonce)和默克爾樹根(Merkle_root),區塊體是由交易構成的默克爾樹。共識機制[5]是區塊鏈系統達成一致的協議,根據其使用的技術路線分為單一共識機制與混合共識機制。單一共識機制主要分為工作量證明(Proof of Work,PoW)、權益證明(Proof of Stake,PoS)和拜占庭容錯(Byzantine Fault Tolerance,BFT)共識機制。

在共識機制中,節點可以分為出塊節點、驗證節點和記賬節點。負責提出區塊的節點稱為出塊節點,也稱為出塊者、記賬者、領導者、主節點或提議者。負責驗證區塊的節點稱為驗證節點,也稱為驗證者或備份節點。驗證節點需要驗證出塊者的合法性、區塊的合法性、簽名的正確性等。負責維護區塊鏈數據庫的節點稱為記賬節點。記賬節點需要存儲所有區塊和驗證區塊。出塊節點、驗證節點和記賬節點統稱為共識節點。共識機制的主要流程包括選舉出塊者、提出區塊、驗證區塊和更新區塊鏈。每一輪都先選舉新的出塊者,再由出塊者提出區塊(將網絡中的合法交易打包進新區塊),然后由驗證者驗證新區塊的合法性,最后記賬節點將達成共識的新區塊寫入本地數據庫末端來更新區塊鏈。

共識機制主要考慮安全性、擴展性、能耗、吞吐量、交易確認時間和一致性等性能。安全性是指抵抗雙花攻擊、日蝕攻擊等安全威脅的能力[5]。擴展性是指系統支持擴展的能力,主要考慮節點數量和交易數量增加時系統負載和網絡通信量的變化。能耗是指每年挖礦消耗的電能。吞吐量是指系統中每秒可以容納的最大交易量。交易確認時間是指從交易上鏈到被確認需要的時間。一致性是指系統抵御分叉的能力。

本文總結區塊鏈共識機制,將其分為單一共識機制與混合共識機制,根據技術路線對混合共識機制進行細分,并分析各類共識機制的基本原理及理論依據,同時指出對應的現實世界信任模型。在此基礎上,闡述包括選舉出塊者、提出區塊、驗證區塊和更新區塊鏈的共識機制流程,并從安全性、擴展性、能耗、吞吐量、交易確認時間和一致性等方面分析現有共識機制的相關性能。

1 單一共識機制

1.1 PoW共識機制

Bitcoin在沒有中心化節點參與的前提下,實現了用戶之間的安全自由匿名支付,目前在加密數字貨幣市場具有較大市值。以Bitcoin為代表的萊特幣(Litecoin)[6]、Bitcoin-NG[7]、GHOST[8-9]等第一代數字貨幣系統大多采用PoW作為共識機制。PoW共識機制基于計算機設備進行數學運算的確定性、公平性、可驗證性來達成共識,從而保障數據庫的一致性,而大部分PoW共識機制使用的數學運算為哈希函數。PoW共識機制相當于自證制度,即自我證明合法性。在PoW共識機制中一般使用兩次哈希函數,具體共識流程如下:

1)構造默克爾樹。礦工收集系統中的交易,使用其認為合法的交易構造默克爾樹。

2)選舉出塊者和提出區塊。在PoW共識機制中選舉出塊者和提出區塊概念同時進行,礦工通過改變nonce的值使Hash(Hash(version+prev_hash+Merkle_root+ntime+nonce))

3)驗證區塊并更新區塊鏈。礦工驗證哈希值和區塊中包含的交易,若哈希值小于給定的難度并且所有交易合法,則將新區塊寫入到區塊鏈末端,更新區塊鏈,開啟下一輪共識;否則直接將其丟棄并繼續進行本輪挖礦。

PoW共識機制保障了系統安全性,能抵抗小于51%礦力的雙花攻擊、自私挖礦攻擊和日蝕攻擊等安全威脅[10-11],但是中心化礦池使系統安全性下降,如Bitcoin中最大的3個礦池的算力之和已超過51%[12],若3個礦池勾結,則足以發動51%攻擊,并拒絕其他礦工的交易及服務攻擊等。為保證交易的安全性,PoW共識機制中的交易不能立即被確認,而是需要等待6個區塊時間。PoW共識機制受出塊時間和區塊大小的限制,吞吐量很低,如Bitcoin只有7 TPS。另外,PoW共識機制消耗大量電能[13-14],如2014年Bitcoin挖礦能耗相當于愛爾蘭全年用電總量[15-16]。

針對PoW共識機制存在的問題,一些解決方案被陸續提出。GHOST采用最重子樹策略生成主鏈,解決了自私挖礦問題。以太坊(Ethereum)[17-18]使用默克爾前綴樹替代默克爾樹,引入叔區塊結構大幅縮短了出塊時間,從而將吞吐量增加至15 TPS[5]。Bitcoin-NG改進了區塊結構,將其分為關鍵區塊和微區塊,關鍵區塊在原Bitcoin區塊中添加了獲得記賬權的礦工公鑰,微區塊由獲得記賬權的礦工根據需要創建。默認設置為每10分鐘產生一個關鍵區塊,每10秒產生一個微區塊。挖礦可以在關鍵區塊上進行,也可以在微區塊上進行。Bitcoin-NG為區塊鏈擴容提供了新思路,降低了交易延遲并提高了吞吐量。文獻[13]有效利用了區塊鏈系統的電能。文獻[19]基于區塊鏈的計算能力解決了正交向量、困難性假設等復雜數學計算問題。

1.2 PoS共識機制

為解決PoW共識機制的高能耗問題,文獻[20-21]提出PoS共識機制,基于用戶權益達成區塊鏈數據庫一致性[22],并且在點點幣(PPcoin)中提出基于幣齡的PoS共識機制(幣齡相當于股權),定義幣齡為貨幣數量乘以時期(coin age=coins×age)。幣齡是一個隨時間流逝線性增加的未花費貨幣的權重因子,花費貨幣或者挖礦后消耗幣齡。基于PoS共識機制的區塊鏈項目多數是由PoW共識機制逐步過渡到PoS共識機制,如黑幣(Blackcoin)[22]、Ethereum。PoS共識機制相當于股權制度,所有方案需要持有超過半數股權的用戶表決同意才能通過。

PoS共識機制的具體流程為:

1)選舉出塊者。用戶質押持有的代幣來獲取幣齡,幣齡越長,成為區塊者的概率越大,挖礦需滿足不等式:proofhash

2)提出區塊。出塊者收集系統中的交易,將其認為合法的交易打包進區塊,然后在系統內廣播新區塊。

3)驗證區塊并更新區塊鏈。驗證節點對新區塊進行驗證,若驗證成功,則將其添加到區塊鏈末端,更新區塊鏈,開啟下一輪共識;否則直接將其丟棄,并重新選舉出塊者。

PoS共識機制相比PoW共識機制無需計算無意義的哈希值,因此其能耗大幅降低。PoS共識機制能抵抗小于51%權益的攻擊,惡意節點控制51%權益的概率小于控制51%計算能力的概率,安全性高于PoW共識機制。Blackcoin項目指出PPcoin中的PoS共識機制由于存在幣齡攻擊和長距離攻擊,因此將挖礦需滿足的不等式改進為proofhash

1.3 BFT共識機制

區塊鏈中使用的BFT共識機制主要分為實用拜占庭容錯(Practical Byzantine Fault Tolerance,PBFT)[26-28]、投機拜占庭容錯(Speculative Byzantine Fault Tolerance,SBFT)[29-30]和聯邦拜占庭容錯(Federal Byzantine Fault Tolerance,FBFT)共識機制[31-32]。BFT共識機制中不產生無意義的能耗,相比其他單一共識機制能耗較低,其相當于公民投票制度,大部分參與者投票同意方案,投票確認結果才能達成一致性。

1.3.1 PBFT共識機制

PBFT共識機制解決了原始拜占庭容錯共識機制效率較低的問題,將算法復雜度從指數級降低至多項式級。PBFT共識機制相當于兩輪舉手表決,需要對提議進行表決并對結果進行確認。

PBFT共識機制中每個節點都有一個唯一性編號標識(i),編號逐漸遞增。一次共識從開始到結束所使用的數據集合稱為視圖,每個視圖都由一個唯一性編號v標識,每次視圖變更編號加1,每個視圖中只存在一個主節點,其他節點都為備份節點。PBFT共識機制執行流程[28]如圖1所示,具體步驟如下:

1)發出請求。客戶機發起請求,并將請求消息發送給所有節點。

2)提出區塊。主節點監聽到客戶機發出結構化的服務請求,進入預準備階段。主節點對請求消息格式進行檢查,若不符合,則直接丟棄;若符合,則在當前視圖v中分配請求標記序號n(按序增加),向所有備份節點廣播結構化的預準備消息并將此消息寫入本地日志。

3)驗證區塊。備份節點對預準備消息進行檢查,若通過,則向其他副本節點廣播格式化的準備消息,并將預準備消息和準備消息寫入本地日志。

4)更新區塊鏈。節點將接收到的準備消息都寫入日志,如果一個節點接收到2f+1個來自不同節點(包括其自身)且驗證正確的準備消息,則向所有備份節點廣播結構化的提交消息。

5)答復。備份節點接收到法定數量的提交消息后執行請求操作,并向客戶端發送答復消息。客戶端若收到f+1個不同備份節點的正確答復時,則認為請求得到執行。

圖1 PBFT共識機制執行流程Fig.1 Execution flow of PBFT consensus mechanism

視圖更改協議由備份節點發起,能夠解決主節點發生故障的問題。備份節點監測到主節點發生故障時廣播視圖變更消息并申請成為新的主節點。編號最小(要求此編號比當前發生故障的主節點編號大)且沒有發生故障的備份節點當選為新一輪的主節點。視圖變更流程[28]如圖2所示,具體步驟如下:

1)發起視圖變更。備份節點i廣播視圖變更消息,視圖變更消息格式為Signi(View-change,v+1,h,C,P,Q),其中,h表示備份節點i存儲的最新檢查點編號,C表示由備份節點i存儲的所有檢查點編號及對應憑證集合,P表示由備份節點i收集的所有預準備消息集合(對應請求還沒有進入提交階段),Q表示備份節點i接收到的預準備消息集合(對應請求還沒有進入準備階段)。

2)確認視圖變更。備份節點i收集2f+1個(包括其自身)視圖變更消息后,給視圖v+1對應的主節點發送視圖變更確認消息,視圖變更確認消息格式為Signi(View-change-ACK,v+1,i,j,Hash(m)),其中,j表示發送視圖變更消息的備份節點編號集合,m表示視圖變更消息。

3)廣播新視圖。新的主節點根據存儲的信息和日志更新節點數據,發送新視圖消息,進入新一輪一致性協議。新視圖消息格式為Signi(New-view,v+1,u,χ),其中,u表示主節點收集到的視圖變更證據,χ表示主節點知道的最新檢查點、檢查點到當前視圖中所有已經提交的請求、準備完成的請求和預準備完成的請求。

圖2 PBFT視圖變更流程Fig.2 Procedure of PBFT view change

PBFT共識機制可以容忍的最大拜占庭節點數為f=?(R1)/3」,其中,R表示共識節點總數。在區塊鏈系統中,采用準入制度增加安全性。當主節點為誠實節點時,共識過程能順利進行,不會觸發視圖更換,新產生的區塊可以立即確認,系統吞吐量達到1 000 TPS。由于任意時刻只有一個主節點,因此系統不會發生分叉,并且所有區塊需要經過2f+1個備份節點(包含主節點)驗證,是一種完全去中心化的系統。

由于PBFT共識機制采用準入制度,因此節點只有經過認證才能進入系統及廣播通信方式,造成了系統擴展性差。共識機制中主節點對請求消息排序并提出區塊,然后將預準備消息發送給所有共識節點,時間復雜度為O(n)。在驗證時采取多對多的通信模式,每個備份節點都要廣播準備消息和提交消息,單個備份節點的時間復雜度為O(2n),全體備份節點的時間復雜度為O(2n)×O(n)=O(2n2),所以PBFT共識機制中一致性協議的時間復雜度為O(2n2+n)≈O(n2),當節點數量增加時一致性協議性能顯著下降。在PBFT視圖變更過程中,采取多對多的通信模式,每個備份節點都廣播一次視圖變更消息,時間復雜度為O(n)×O(n)=O(n2),空間復雜度為O(m)×O(n)=O(mn),且消息包含C、P、Q這3個集合,所需的存儲空間巨大。每個備份節點向新主節點發送一次視圖變更確認消息,時間復雜度為O(n),消息含有備份節點編號集合,空間復雜度相比視圖變更消息可以忽略。新主節點向每個備份節點發送一次新視圖(t),時間復雜度為O(n),空間復雜度為O(t)×O(n)=O(tn),且消息包含u、χ兩個集合,所需的存儲空間巨大。所以PBFT視圖變更協議的時間復雜度為O(2n2+n)≈O(n2),空間復雜度為O(mn)+O(tn)。當發生視圖變更時,系統時空復雜度為O(n2)×(O(mn)+O(tn))≈O((m+t)n3),嚴重消耗系統資源。

1.3.2 SBFT共識機制

文獻[29]提出SBFT共識機制,文獻[30]將SBFT共識機制應用于區塊鏈。SBFT共識機制中使用Collector技術和收集器通信模式,共識過程中節點將消息發送給收集器,收集器匯總消息后再發送給節點,顯著降低了通信量。SBFT共識機制相當于有專業計票人的投票制度,由計票人統計并公布結果。收集器相當于計票人,可以由客戶機擔任,也可以由節點擔任。SBFT中備份節點總數為3f+2c+1,其中,c表示故障節點數量,SBFT共識機制執行流程[30]如圖3所示,具體步驟如下:

1)發出請求。客戶機向信任的主節點發出請求。

2)提出區塊。主節點收集客戶機請求,提出區塊,然后發送提出區塊消息給所有節點。

3)驗證區塊。所有節點驗證從主節點發送過來的預準備消息,如果驗證通過,則使用門限聚合簽名技術(threshold BLS)[33-35]對驗證結果進行數字簽名,然后將簽名消息發送給收集器C。

4)統計票數。收集器C收集所有節點發送的簽名消息并驗證合法性。若接收到3f+c+1個不同且合法的簽名消息,則使用聚合簽名技術將消息聚合,然后發送統計票數消息給所有節點。

5)更新區塊鏈。每個節點接收到合法的統計票數消息后,將新區塊寫入本地數據庫并更新區塊鏈,然后發送更新區塊鏈消息給收集器E。

6)公布執行結果。收集器E收集更新區塊鏈消息并對其合法性進行驗證。若收集到f+1個不同且合法的更新區塊鏈消息,則發送執行結果消息給客戶機和所有節點。

圖3 SBFT共識機制執行流程Fig.3 Execution flow of SBFT consensus mechanism

SBFT共識機制的視圖更改協議也使用Collector技術(新的主節點擔任收集器),觸發條件類似于PBFT共識機制,即計時器超時或者收到f+1個備份節點發送的主節點出錯的證據。SBFT共識機制能容忍f個拜占庭節點和c個故障節點。區塊能夠立即確認,不會產生分叉,并且其不再使用多對多的廣播通信模式,降低了通信開銷,時間復雜度降至O(n),顯著節省了系統資源。

1.3.3 FBFT共識機制

FBFT共識機制弱化了主節點和備份節點的概念,典型的區塊鏈代表項目有瑞波(ripple)[31]、恒星(stellar)[32],每個驗證節點在本地維護一個信任節點列表(Unique Node List,UNL),列表中的每個節點都能對交易進行投票。FBFT共識機制相當于他證制度,每個提案都以他人看法為準。

1)驗證請求。每個驗證節點不間斷監聽網絡,接收來自客戶端的請求信息。經過與本地數據庫驗證后,如果是不合法的請求,則將其直接丟棄;反之,放入到交易候選集。交易候選集中還包括之前共識過程中無法確認而遺留的交易。

2)提出區塊。每個驗證節點從自己的交易候選集中取出交易生成提案,并將提案發送給其他節點。

3)驗證區塊。驗證節點在收到其他節點發來的提案后,直接忽略不是來自UNL節點的提案,并對比提案中的交易和本地交易候選集,如果有相同交易,則該交易就獲得一票。在一定時間內,若交易獲得超過50%的票數,則該交易進入下一輪;若沒有獲得超過50%的票數,則在下一次共識過程中再次進行確認。

4)再次驗證區塊。每個驗證節點將超過50%票數的交易作為提案發給其他節點,同時提高所需票數的閾值至60%,重復步驟3和步驟4,直到閾值達到80%。

5)更新區塊鏈。每個驗證節點將超過80%的UNL節點確認的交易正式寫入本地數據庫,并更新交易候選集。

FBFT共識機制可以容忍的最大拜占庭節點數為f=?(R1)/5」。區塊的產生不依賴于主節點,因此加快了效率,使得吞吐量達到1 000 TPS～1 500 TPS[5]。由于每個驗證節點自身提出區塊、決定信任節點集合,因此去中心效果明顯,并且區塊產生具有不可逆性,不會產生分叉,在交易上鏈時就能得到確認,同時用戶能夠動態加入網絡,擴展性高于PBFT共識機制,但其時間復雜度為O(n2)。

2 混合共識機制

2.1 基于PoW與PoS的共識機制

結合PoW與PoS的共識機制有兩種類型:一種是淺結合,即第一階段使用PoW共識機制,達到預定目標后進入第二階段使用PoS共識機制(不再使用PoW共識機制),每次共識過程中只使用一種共識機制(PoW共識機制或者PoS共識機制),如Ethereum、PPcoin、Blackcoin等;另一種是深結合,即每次共識過程同時使用PoW共識機制和PoS共識機制,如活動證明(Proof of Activity,PoA)[36]。淺結合類型的共識機制原理、現實世界模型、流程和性能對應每個階段的單一共識機制;深結合類型的共識機制流程和性能取決于混合共識機制,但由于深結合類型的共識機制模型比較復雜,因此未對應現實世界模型。

基于PoW與PoS的共識機制流程具體如下:

1)選舉出塊者和提出區塊頭。礦工通過改變nonce值(Hash(prev_hash+address+height+nonce)

2)驗證區塊頭和選舉權益代表。全體礦工驗證新區塊頭,驗證成功后選舉N個權益代表(系統初始化時設定N)。具體選舉協議為:將新區塊頭的哈希值、前一個區塊的哈希值和N個固定的后綴連接起來(每次使用一個后綴,共產生N個連接體),然后將連接體的哈希值作為輸入調用follow-the-satoshi算法產生權益代表(一個連接體產生一個權益代表)。

3)提出區塊。全體礦工首先判斷自己是否成為權益代表人:如果成為前N1個代表中的1個,則對新區塊頭簽名并廣播簽名;如果成為第N個代表,則構造新區塊體,然后使用新區塊頭、新區塊體和前N1個代表的簽名構造新區塊并對新區塊簽名,最后廣播新區塊。

4)驗證區塊并更新區塊鏈。所有礦工驗證新區塊的合法性,將合法新區塊寫入到區塊鏈末端。

PoA共識機制采用最長主鏈原則解決分叉問題,由于攻擊者需要同時控制大部分礦力和大部分權益才能攻擊成功,因此安全性高于PoW共識機制和PoS共識機制,但其仍然依靠PoW共識機制選舉出塊者,并且沒有有效降低能耗,相比PoW共識機制通信時間更長、開銷更大,從而造成更低的吞吐量。

2.2 基于PoS與委托投票制度的共識機制

比特股(Bitshare)[37]結合委托投票制度對PoS共識機制做出重大改進,提出委托權益證明(Delegated Proof of Stake,DPoS)共識機制[38-39]。在DPoS共識機制中,代表者稱為見證人,由見證人按順序輪流產生區塊,其他見證人驗證區塊。DPoS共識機制相當于人民代表大會制度,由人大代表提出議案并對提案進行投票。

DPoS共識機制通過選舉見證人行使權利,具體流程如下:

1)選舉出塊者。權益持有者投票選舉見證人。見證人在系統中保持中立,每24小時更新一次,其收益由權益持有者投票決定。Bitshare可以有任意數量的見證人,EOS[40]每輪見證人的數量設置為21,票數最多的前20人自動當選見證人,剩余1人隨機選出,見證人需要100%在線。

2)提出區塊。見證人產生區塊并對區塊簽名和添加時間戳,再在系統中廣播新產生的區塊,如果見證人在某個時隙沒有產生區塊,則該時隙將被跳過,產生區塊的權力交給下一個見證人。Bitshare中每2秒產生一個區塊,EOS中每3秒產生一個區塊。

3)驗證區塊并更新區塊鏈。其他見證人負責驗證新產生區塊的合法性。Bitshare中N個見證人驗證通過就可上鏈(N個見證人要求代表的投票權之和大于50%),EOS中半數以上的見證人驗證通過就可以上鏈。

DPoS共識機制能夠對交易進行秒級驗證,并在短時間內提供比現有股權證明系統更高的安全性,抵抗小于51%權益的攻擊[4]。對系統的任何更改(包括版本更新、添加新功能、對權益的修改等)都必須由大于51%權益持有者同意。見證人按順序產生區塊,意味著一筆交易從廣播開始直至經過1/2區塊時間被確認的概率為99.9%。在通常情況下,有半數以上見證人給出確認后,新區塊就為不可逆。在連續丟失2個區塊后,有95%的確認節點處于分叉中,在連續丟失3個區塊后就有99%的確認節點處于分叉中。EOS的吞吐量理論上可達百萬級[5],但是選舉見證人需要消耗大量資源,實際應用中吞吐量不理想,且區塊的產生依賴于21個見證人,從而造成中心化問題。

2.3 基于PoS、VRF與公證制度的共識機制

文獻[41]結合可驗證隨機函數(Verifiable Random Function,VRF)[42-44]、PoS和公證制度提出Dfinity共識機制。Dfinity共識機制中使用threshold BLS技術構造VRF(稱為信標),輸出一種隨時間變化的數據流。Dfinity共識機制相當于公證制度,提案被任意一個合法的公證人證明后即可認為可信。Dfinity共識機制執行流程[41]如圖4所示,具體步驟如下:

1)選舉出塊者。在每一輪選舉開始時,由信標廣播隨機數,根據隨機數確定所有提議者及其排名。

2)提出區塊。每個提議者都能提議并廣播議案。議案由交易、提議者排名、前一個區塊的證書及對新區塊的簽名組成。系統根據提議者排名,給提案賦予不同的權重。提議者排名越高,權重越大。權重越大的提案越有可能成為新區塊。

3)驗證區塊。每一輪都使用信標隨機選舉出公證委員會,其中公證人對新區塊進行公證。等待一定時間后,每個公證人都將認證成功的消息在區塊鏈系統中進行廣播,若有多個區塊被公證,則將公證消息全部廣播。公證委員會中任意一個公證人公證一個區塊后,區塊鏈系統進入新一輪共識。

4)更新區塊鏈。全體記賬節點根據公證委員會的認證消息更新區塊鏈。

圖4 Dfinity共識機制執行流程Fig.4 Execution flow of Dfinity consensus mechanism

Dfinity共識機制可以容忍的最大惡意公證人數量為f=?(R-1)/3」。由于網絡延遲,每一輪都可能有多個區塊被認證成功進而產生分叉。為解決分叉,根據協議規定,在任意時間如果所有Bk1區塊都有共同的先驅Bk2,則提交Bk2進區塊鏈;當沒有共同的先驅時,提交權重最大的區塊。文獻[45]證明了當系統誠實用戶數量大于f+1時,系統最終會達成一致。Dfinity共識機制中拜占庭節點無法秘密建立和維護被認證的鏈,所以不會存在雙花攻擊、自私挖礦攻擊、長距離攻擊和無危險攻擊這些安全威脅,但存在自適應攻擊。若采用可驗證隨機函數產生提議者,雖然解決了提議者身份的問題,提高了系統安全性,但是所有提議者和公證人都使用廣播方式進行通信,時間復雜度為O(n2)。

2.4 基于PoS、BFT與委托投票制度的共識機制

小蟻鏈(NEO)中結合委托投票制度、PoS共識機制和PBFT共識機制提出委托拜占庭容錯(delegated Byzantine Fault Tolerance,dBFT)共識機制[46],參與者依據所持有的代幣數量進行投票,選舉出記賬人,由全體記賬人運行BFT算法達成共識生成新區塊。dBFT共識機制相當于人民代表大會制度,記賬人相當于人大代表。dBFT共識機制中新產生的區塊可以立即確認,每15秒～每20秒產生一個新區塊,吞吐量實測可達1 000 TPS,可以容忍的最大拜占庭節點數為f=?(R-1)/3」,但在NEO項目[46]中,需要NEO項目方同意才能成為共識節點,其目前只有7個共識節點,其中6個由項目方控制,接近于完全中心化系統。

2.5 基于PoS、BFT與VRF的共識機制

2.5.1 VBFT共識機制

在Ontology項目中,結合PoS、BFT和VRF提出基于可驗證隨機函數的拜占庭共識機制(VBFT)[47],實現了網絡的快速共識。每個區塊的VRF值根據前一個區塊計算得到,具體過程為提取前一個區塊中的交易事務,計算1 024 bit的哈希值并將該哈希值作為輸出。系統中將網絡分為共識網絡和公共網絡。用戶通過質押代幣后參與到共識網絡,共識合約自動更新共識節點列表和相應權益(PoS表),每產生一個區塊更新一次。共識節點分為出塊者、驗證者、確認者,所有驗證者組成驗證者集合,所有確認者組成確認者集合。VBFT共識機制相當于選舉制度,合法的選民都具有投票權、被投票權,由可驗證隨機函數驗證選民身份的合法性。

VBFT共識機制運行時依據VRF值作為索引,從PoS表中選舉共識節點,具體流程如下:

1)選舉出塊者和提出區塊。每一輪依據VRF值從共識網絡中選舉潛在出塊者集合,每個潛在出塊者提出一個區塊。

2)驗證區塊。每一輪依據VRF值從共識網絡中選舉出驗證者集合,每個驗證者從共識網絡中收集被提出的區塊進行執行驗證,并投票給具有最高優先級的區塊,廣播投票消息。

3)確認區塊。每一輪依據VRF值從共識網絡中選舉出確認者集合,確認者統計驗證者的投票,最后確認達成共識的區塊并廣播確認消息。

4)更新區塊鏈。共識網絡中所有的節點復制確認者認可的區塊,只有結束一輪共識,才開啟新一輪共識。

每一個區塊決定了VRF函數的一個輸出,由VRF函數確定共識節點序列,根據節點序列分配優先級,然后通過節點優先級加權決定區塊優先級,最后投票給優先級最高的區塊,從而解決分叉問題。VBFT共識機制中隨機選擇出塊節點、驗證節點、確認節點,能夠抵抗惡意攻擊,去中心化程度和安全性高,吞吐量達到3 000 TPS,交易確認時間為5 s～10 s。另外,VBFT共識機制由共識節點執行BFT共識機制,資源消耗低,可以容忍的最大拜占庭節點數為f=?(R1)/3」,時間復雜度為O(n2),擴展性隨共識節點的增加而降低。

2.5.2 Algorand共識機制

文獻[48]結合PoS、BFT和VRF提出Algorand共識機制,實現同步網絡的快速共識。VRF由可驗證概率函數構造.Hash(Signi(r,s,Qr)),其中,r表示節點對共識輪數,s表示共識步數,Qr表示隨機數種子,.表示小于1的小數且其后面是小數位,i表示節點數。Algorand共識機制[49-50]相當于多委員會制度,包括出塊節點委員會和驗證節點委員會。

1)選舉出塊節點和區塊驗證節點。在第rk輪中的每個驗證節點運行VRF函數判斷自身身份:若在rk輪中沒有當選為驗證節點,則不參與本輪共識;若.Hash(Signi(r,s,Qr))

2)提出區塊。每個潛在出塊節點生成Br并將其在區塊鏈系統中廣播。區塊形式為Br=(r,PAYr,Signi(Qr),Hash(Br-1)),其中PAYr表示區塊Br中包含的交易集合,若PAYr≠?,則Qr=Hash(QR-1,s);否則,Qr=Hash(Sign(QR-1,s))。

3)驗證區塊。委員會成員運行BA*共識機制驗證本輪區塊的合法性,其是一種新的拜占庭一致性共識機制。BA*共識機制包含分級共識(Graded Consensus,GC)算法和改進型二元拜占庭一致性(Binary Byzantine Agreement,BBA)算法,委員會成員驗證潛在出塊節點的合法性,找出概率值最小的潛在出塊節點并選舉為出塊節點,同時阻止傳播概率值較大的潛在出塊節點提出區塊,并驗證其提出區塊的合法性,廣播驗證消息。

4)更新區塊鏈。參與記賬的用戶根據委員會的驗證消息更新區塊鏈。

Algorand共識機制隨機選舉出塊節點和驗證節點,能夠抵抗惡意攻擊,去中心化程度和安全性高,吞吐量高于Bitcoin,交易確認時間低于1 min。BA*共識機制類似PBFT共識機制,資源消耗低,每個步驟都要求拜占庭節點數少于f=?(R-1)/3」,算法時間復雜度為O(n2),但其至少需進行6輪通信,通信開銷高于PBFT共識機制。

2.5.3 Omniledger共識機制

文獻[51]結合VRF、PoS、BFT和鎖機制提出Omniledger共識機制,從未花費幣池(Unspent Transaction Output,UTXO)的角度實現跨分片鏈交易的原子性,每條分片鏈都擁有并維護自身的UTXO。Omniledger共識機制使用PoS共識機制挑選出驗證節點,利用VRF將驗證節點分配到分片鏈,每個分片鏈內部使用BFT共識機制達成一致,并通過鎖機制保證跨分片鏈操作時的原子性和正確性。Omniledger共識機制較復雜,沒有對應的現實世界信任模型,具體流程如下:

1)初始化。客戶端創建跨分片鏈交易(cross-TX)。cross-TX被廣播給所有花費UTXO的分片鏈(ISs)。

2)加鎖。所有ISs與cross-TX關聯,每個ISs鎖定自身UTXO并檢查交易合法性。若驗證通過,則先寫日志,分片鏈領導者提交接收證明;若驗證失敗,分片鏈領導者提交拒絕證明。

3)解鎖。客戶端根據階段2的結果發出提交交易信息或者取消交易消息。若所有ISs都驗證通過,則發出提交消息;若其中有任意一個ISs提交了拒絕證明,則發出取消交易消息。ISs接收并驗證提交消息后,將交易寫入分片鏈,并在UTXO中使用對應的代幣并解鎖交易;接收UTXO的分片鏈(OSs)并在UTXO創造對應的代幣。

Omniledger共識機制利用PoS共識機制抵抗女巫攻擊,可容忍的最大拜占庭節點數為f=?(R1)/4」。吞吐量隨分片鏈數量線性增加。

2.6 基于BFT與鎖機制的共識機制

2.6.1 Tendermint共識機制

文獻[52]提出的Tendermint共識機制使用鎖機制深度改進PBFT共識機制而得到,具體流程如圖5所示,包含預投票、預提交和提交3個步驟,其中提交包含得到區塊和等待超過2/3節點提交兩個步驟。任何共識節點不論處于哪個階段,只要接收到合法的提交消息,都進入提交階段。Tendermint共識過程中對預投票消息進行加鎖,保證了數據正確性和一致性,無需視圖變更協議和錯誤恢復協議,減少了系統資源消耗,但是一致性協議的時間復雜度為O(n2)。由于Tendermint共識機制較復雜,因此沒有對應的現實世界信任模型,目前其已應用于Cita[53]項目。

圖5 Tendermint共識機制執行流程Fig.5 Execution flow of Tendermint consensus mechanism

2.6.2 Chainspace共識機制

文獻[54]結合BFT與鎖機制在Chainspace中提出S-BAC共識機制,保證了存儲分片中智能合約的正確性和安全性。S-BAC分片鏈內部和分片鏈之間都使用BFT共識機制,區別在于對拜占庭節點數量要求不同。S-BAC分片鏈內部相當于公民投票制度,分片鏈之間相當于否決權制度。

共識機制中的分片鏈和誠實節點均指與交易相關的分片鏈和誠實節點,跨鏈通信由分片鏈領導者發起,Chainspace共識機制執行流程[54]如圖6所示,具體步驟如下:

1)初始化。一個用戶初始化交易,將準備消息至少發送給一個誠實節點。為保證至少一個誠實節點接收到準備消息,需要在一條分片鏈中將消息發送給f+1個節點,或者在每條分片鏈中都將消息發送給f+1個節點。

2)分配序號。接收到準備消息,分片鏈進入活動狀態,內部使用BFT共識機制給準備消息分配序號。

3)驗證消息和加鎖。分片鏈內部使用BFT共識機制驗證交易,若超過f個節點驗證通過,則進入鎖定狀態并廣播準備提交消息和證據;否則廣播拒絕準備消息和證據。如果節點處于鎖定狀態時,則不接收其他交易并廣播拒絕其他交易消息。

4)接收。每條分片鏈都監聽網絡,如果收到一條拒絕準備消息,則廣播拒絕提交消息和證據;反之,廣播接收提交消息和證據。

5)提交和解鎖。若分片鏈接收到提交消息,則將其與交易相關的對象設置為不活躍狀態并提交交易,同時更新分片鏈及解鎖交易。若接收到拒絕提交消息,則釋放相應的鎖,將相關的對象設置為活躍狀態,等待下一次共識。

圖6 Chainspace共識機制執行流程Fig.6 Execution flow of Chainspace consensus mechanism

分片鏈中可以容忍的最大拜占庭節點數為f=?(R1)/3」,分片鏈之間不能容忍拜占庭節點。如果不同交易涉及的節點不同,則共識操作可以并發進行。分片鏈內部和分片鏈之間的交易可以立即確認,但是S-BAC只解決了分片鏈的一致性問題,而沒有解決Chainspace全局一致性問題。

3 其他共識機制

能力證明(Proof of Capacity,PoC)是根據參與者的計算機硬盤空閑空間作為標準選舉出塊者的共識機制,如Permacoin[55]、Spacemint[56]。消逝時間證明(Proof of Elapsed Time,PoET)是根據可信硬件芯片執行某個命令的等待時間作為標準選舉出塊者的共識機制,等待時間最短的用戶即為出塊節點[57]。權威證明(Proof of Authority,PoA)是基于權威人士聲譽的共識機制,由聲譽高的權威人士證明交易的合法性[58]。燃燒證明(Proof of Burn,PoB)是通過可驗證的方式銷毀基礎代幣來獲得獎勵的共識機制[59]。

4 共識機制分析

目前,區塊鏈已經發展到第三代,第一代和第二代為公鏈,主要使用PoW共識機制、PoS共識機制和混合共識機制;第三代為聯盟鏈,主要使用PBFT共識機制。本節將從能耗、安全性、生成區塊時間、交易確認時間、是否存在代幣和是否需要專業記賬人等方面對單一共識機制進行分析比較,如表1所示。同時,對現有典型的區塊鏈項目進行比較,如表2所示,其中“—”表示沒有對應數據。

表1 單一共識機制性能比較Table 1 Performance comparison of single consensus mechanisms

表2 典型的區塊鏈項目性能比較Table 2 Performance comparison of typical blockchain projects

5 研究展望

在區塊鏈共識機制的設計過程中主要考慮能耗、效率、一致性和安全性等性能,現有區塊鏈技術是在效率、安全性和去中心化之間進行有側重的取舍。共識機制作為區塊鏈的核心技術,未來的研究方向主要包括以下4個方面:

1)研究被委托人不遵守規則時對委托人賠償的共識機制。在基于委托的共識機制中,目前研究的重點是減少委托人不遵守規則時的懲罰,因此下一步將研究被委托人不遵守規則時如何對委托人進行賠償。

2)研究結合VRF與Bitcoin-NG的共識機制。將VRF應用于Bitcoin-NG中可以極大提高關鍵區塊的產生效率,從而降低能耗并提高資源利用率。

3)研究結合VRF與網絡分片技術的共識機制。將VRF應用于網絡分片中可以提高共識機制效率并降低驗證區塊時間,從而增加吞吐量。

4)研究基于高效Rollup方法的共識機制。在儲存分片中,目前主要研究基于ZK-Rollup和Optimistic Rollup方法的共識機制,但由于ZK-Rollup方法使用ZK-SNARK技術,計算過程復雜,計算時間長達10 min,因此可以通過基于其他零知識證明技術的Rollup方法降低計算時間,提高共識機制效率,加快區塊產生速度。在Optimistic Rollup方法中,新產生的區塊需要等待1周到2周的審查期才能被確認,因此可將其與BFT共識機制相結合,使新區塊能夠立即被確認,從而提高共識機制的執行效率。

6 結束語

區塊鏈技術發展至今,受到各行各業的廣泛關注。共識機制作為區塊鏈的核心技術,能夠保障區塊鏈數據庫的一致性和正確性,從而決定區塊鏈的安全性、擴展性、能耗等相關性能。本文從一致性、容錯性等角度歸納現有區塊鏈共識機制,分類介紹區塊鏈共識機制的技術路線。基于現實世界的信任模型,分析各種共識機制的原理,闡述包括選舉出塊者、提出區塊、驗證區塊和更新區塊鏈的共識機制流程,并從安全性、能耗、吞吐量和區塊確認時間等方面對現有共識機制的相關性能進行對比總結。隨著區塊鏈技術在新型基礎設施建設中發揮愈加重要的作用,大規模、跨領域的區塊鏈會得到更加廣泛的應用和發展,因此后續將對具有完善的獎懲制度且高容量、高效率的共識機制做進一步研究。