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

(南華大學(xué) 計(jì)算機(jī)學(xué)院,湖南 衡陽(yáng) 421001)

0 概述

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

在共識(shí)機(jī)制中,節(jié)點(diǎn)可以分為出塊節(jié)點(diǎn)、驗(yàn)證節(jié)點(diǎn)和記賬節(jié)點(diǎn)。負(fù)責(zé)提出區(qū)塊的節(jié)點(diǎn)稱為出塊節(jié)點(diǎn),也稱為出塊者、記賬者、領(lǐng)導(dǎo)者、主節(jié)點(diǎn)或提議者。負(fù)責(zé)驗(yàn)證區(qū)塊的節(jié)點(diǎn)稱為驗(yàn)證節(jié)點(diǎn),也稱為驗(yàn)證者或備份節(jié)點(diǎn)。驗(yàn)證節(jié)點(diǎn)需要驗(yàn)證出塊者的合法性、區(qū)塊的合法性、簽名的正確性等。負(fù)責(zé)維護(hù)區(qū)塊鏈數(shù)據(jù)庫(kù)的節(jié)點(diǎn)稱為記賬節(jié)點(diǎn)。記賬節(jié)點(diǎn)需要存儲(chǔ)所有區(qū)塊和驗(yàn)證區(qū)塊。出塊節(jié)點(diǎn)、驗(yàn)證節(jié)點(diǎn)和記賬節(jié)點(diǎn)統(tǒng)稱為共識(shí)節(jié)點(diǎn)。共識(shí)機(jī)制的主要流程包括選舉出塊者、提出區(qū)塊、驗(yàn)證區(qū)塊和更新區(qū)塊鏈。每一輪都先選舉新的出塊者,再由出塊者提出區(qū)塊(將網(wǎng)絡(luò)中的合法交易打包進(jìn)新區(qū)塊),然后由驗(yàn)證者驗(yàn)證新區(qū)塊的合法性,最后記賬節(jié)點(diǎn)將達(dá)成共識(shí)的新區(qū)塊寫入本地?cái)?shù)據(jù)庫(kù)末端來更新區(qū)塊鏈。

共識(shí)機(jī)制主要考慮安全性、擴(kuò)展性、能耗、吞吐量、交易確認(rèn)時(shí)間和一致性等性能。安全性是指抵抗雙花攻擊、日蝕攻擊等安全威脅的能力[5]。擴(kuò)展性是指系統(tǒng)支持?jǐn)U展的能力,主要考慮節(jié)點(diǎn)數(shù)量和交易數(shù)量增加時(shí)系統(tǒng)負(fù)載和網(wǎng)絡(luò)通信量的變化。能耗是指每年挖礦消耗的電能。吞吐量是指系統(tǒng)中每秒可以容納的最大交易量。交易確認(rèn)時(shí)間是指從交易上鏈到被確認(rèn)需要的時(shí)間。一致性是指系統(tǒng)抵御分叉的能力。

本文總結(jié)區(qū)塊鏈共識(shí)機(jī)制,將其分為單一共識(shí)機(jī)制與混合共識(shí)機(jī)制,根據(jù)技術(shù)路線對(duì)混合共識(shí)機(jī)制進(jìn)行細(xì)分,并分析各類共識(shí)機(jī)制的基本原理及理論依據(jù),同時(shí)指出對(duì)應(yīng)的現(xiàn)實(shí)世界信任模型。在此基礎(chǔ)上,闡述包括選舉出塊者、提出區(qū)塊、驗(yàn)證區(qū)塊和更新區(qū)塊鏈的共識(shí)機(jī)制流程,并從安全性、擴(kuò)展性、能耗、吞吐量、交易確認(rèn)時(shí)間和一致性等方面分析現(xiàn)有共識(shí)機(jī)制的相關(guān)性能。

1 單一共識(shí)機(jī)制

1.1 PoW共識(shí)機(jī)制

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

1)構(gòu)造默克爾樹。礦工收集系統(tǒng)中的交易,使用其認(rèn)為合法的交易構(gòu)造默克爾樹。

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

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

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

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

1.2 PoS共識(shí)機(jī)制

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

PoS共識(shí)機(jī)制的具體流程為:

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

2)提出區(qū)塊。出塊者收集系統(tǒng)中的交易,將其認(rèn)為合法的交易打包進(jìn)區(qū)塊,然后在系統(tǒng)內(nèi)廣播新區(qū)塊。

3)驗(yàn)證區(qū)塊并更新區(qū)塊鏈。驗(yàn)證節(jié)點(diǎn)對(duì)新區(qū)塊進(jìn)行驗(yàn)證,若驗(yàn)證成功,則將其添加到區(qū)塊鏈末端,更新區(qū)塊鏈,開啟下一輪共識(shí);否則直接將其丟棄,并重新選舉出塊者。

PoS共識(shí)機(jī)制相比PoW共識(shí)機(jī)制無(wú)需計(jì)算無(wú)意義的哈希值,因此其能耗大幅降低。PoS共識(shí)機(jī)制能抵抗小于51%權(quán)益的攻擊,惡意節(jié)點(diǎn)控制51%權(quán)益的概率小于控制51%計(jì)算能力的概率,安全性高于PoW共識(shí)機(jī)制。Blackcoin項(xiàng)目指出PPcoin中的PoS共識(shí)機(jī)制由于存在幣齡攻擊和長(zhǎng)距離攻擊,因此將挖礦需滿足的不等式改進(jìn)為proofhash

1.3 BFT共識(shí)機(jī)制

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

1.3.1 PBFT共識(shí)機(jī)制

PBFT共識(shí)機(jī)制解決了原始拜占庭容錯(cuò)共識(shí)機(jī)制效率較低的問題,將算法復(fù)雜度從指數(shù)級(jí)降低至多項(xiàng)式級(jí)。PBFT共識(shí)機(jī)制相當(dāng)于兩輪舉手表決,需要對(duì)提議進(jìn)行表決并對(duì)結(jié)果進(jìn)行確認(rèn)。

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

1)發(fā)出請(qǐng)求?？蛻魴C(jī)發(fā)起請(qǐng)求,并將請(qǐng)求消息發(fā)送給所有節(jié)點(diǎn)。

2)提出區(qū)塊。主節(jié)點(diǎn)監(jiān)聽到客戶機(jī)發(fā)出結(jié)構(gòu)化的服務(wù)請(qǐng)求,進(jìn)入預(yù)準(zhǔn)備階段。主節(jié)點(diǎn)對(duì)請(qǐng)求消息格式進(jìn)行檢查,若不符合,則直接丟棄;若符合,則在當(dāng)前視圖v中分配請(qǐng)求標(biāo)記序號(hào)n(按序增加),向所有備份節(jié)點(diǎn)廣播結(jié)構(gòu)化的預(yù)準(zhǔn)備消息并將此消息寫入本地日志。

3)驗(yàn)證區(qū)塊。備份節(jié)點(diǎn)對(duì)預(yù)準(zhǔn)備消息進(jìn)行檢查,若通過,則向其他副本節(jié)點(diǎn)廣播格式化的準(zhǔn)備消息,并將預(yù)準(zhǔn)備消息和準(zhǔn)備消息寫入本地日志。

4)更新區(qū)塊鏈。節(jié)點(diǎn)將接收到的準(zhǔn)備消息都寫入日志,如果一個(gè)節(jié)點(diǎn)接收到2f+1個(gè)來自不同節(jié)點(diǎn)(包括其自身)且驗(yàn)證正確的準(zhǔn)備消息,則向所有備份節(jié)點(diǎn)廣播結(jié)構(gòu)化的提交消息。

5)答復(fù)。備份節(jié)點(diǎn)接收到法定數(shù)量的提交消息后執(zhí)行請(qǐng)求操作,并向客戶端發(fā)送答復(fù)消息?？蛻舳巳羰盏絝+1個(gè)不同備份節(jié)點(diǎn)的正確答復(fù)時(shí),則認(rèn)為請(qǐng)求得到執(zhí)行。

圖1 PBFT共識(shí)機(jī)制執(zhí)行流程Fig.1 Execution flow of PBFT consensus mechanism

視圖更改協(xié)議由備份節(jié)點(diǎn)發(fā)起,能夠解決主節(jié)點(diǎn)發(fā)生故障的問題。備份節(jié)點(diǎn)監(jiān)測(cè)到主節(jié)點(diǎn)發(fā)生故障時(shí)廣播視圖變更消息并申請(qǐng)成為新的主節(jié)點(diǎn)。編號(hào)最小(要求此編號(hào)比當(dāng)前發(fā)生故障的主節(jié)點(diǎn)編號(hào)大)且沒有發(fā)生故障的備份節(jié)點(diǎn)當(dāng)選為新一輪的主節(jié)點(diǎn)。視圖變更流程[28]如圖2所示,具體步驟如下:

1)發(fā)起視圖變更。備份節(jié)點(diǎn)i廣播視圖變更消息,視圖變更消息格式為Signi(View-change,v+1,h,C,P,Q),其中,h表示備份節(jié)點(diǎn)i存儲(chǔ)的最新檢查點(diǎn)編號(hào),C表示由備份節(jié)點(diǎn)i存儲(chǔ)的所有檢查點(diǎn)編號(hào)及對(duì)應(yīng)憑證集合,P表示由備份節(jié)點(diǎn)i收集的所有預(yù)準(zhǔn)備消息集合(對(duì)應(yīng)請(qǐng)求還沒有進(jìn)入提交階段),Q表示備份節(jié)點(diǎn)i接收到的預(yù)準(zhǔn)備消息集合(對(duì)應(yīng)請(qǐng)求還沒有進(jìn)入準(zhǔn)備階段)。

2)確認(rèn)視圖變更。備份節(jié)點(diǎn)i收集2f+1個(gè)(包括其自身)視圖變更消息后,給視圖v+1對(duì)應(yīng)的主節(jié)點(diǎn)發(fā)送視圖變更確認(rèn)消息,視圖變更確認(rèn)消息格式為Signi(View-change-ACK,v+1,i,j,Hash(m)),其中,j表示發(fā)送視圖變更消息的備份節(jié)點(diǎn)編號(hào)集合,m表示視圖變更消息。

3)廣播新視圖。新的主節(jié)點(diǎn)根據(jù)存儲(chǔ)的信息和日志更新節(jié)點(diǎn)數(shù)據(jù),發(fā)送新視圖消息,進(jìn)入新一輪一致性協(xié)議。新視圖消息格式為Signi(New-view,v+1,u,χ),其中,u表示主節(jié)點(diǎn)收集到的視圖變更證據(jù),χ表示主節(jié)點(diǎn)知道的最新檢查點(diǎn)、檢查點(diǎn)到當(dāng)前視圖中所有已經(jīng)提交的請(qǐng)求、準(zhǔn)備完成的請(qǐng)求和預(yù)準(zhǔn)備完成的請(qǐng)求。

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

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

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

1.3.2 SBFT共識(shí)機(jī)制

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

1)發(fā)出請(qǐng)求?？蛻魴C(jī)向信任的主節(jié)點(diǎn)發(fā)出請(qǐng)求。

2)提出區(qū)塊。主節(jié)點(diǎn)收集客戶機(jī)請(qǐng)求,提出區(qū)塊,然后發(fā)送提出區(qū)塊消息給所有節(jié)點(diǎn)。

3)驗(yàn)證區(qū)塊。所有節(jié)點(diǎn)驗(yàn)證從主節(jié)點(diǎn)發(fā)送過來的預(yù)準(zhǔn)備消息,如果驗(yàn)證通過,則使用門限聚合簽名技術(shù)(threshold BLS)[33-35]對(duì)驗(yàn)證結(jié)果進(jìn)行數(shù)字簽名,然后將簽名消息發(fā)送給收集器C。

4)統(tǒng)計(jì)票數(shù)。收集器C收集所有節(jié)點(diǎn)發(fā)送的簽名消息并驗(yàn)證合法性。若接收到3f+c+1個(gè)不同且合法的簽名消息,則使用聚合簽名技術(shù)將消息聚合,然后發(fā)送統(tǒng)計(jì)票數(shù)消息給所有節(jié)點(diǎn)。

5)更新區(qū)塊鏈。每個(gè)節(jié)點(diǎn)接收到合法的統(tǒng)計(jì)票數(shù)消息后,將新區(qū)塊寫入本地?cái)?shù)據(jù)庫(kù)并更新區(qū)塊鏈,然后發(fā)送更新區(qū)塊鏈消息給收集器E。

6)公布執(zhí)行結(jié)果。收集器E收集更新區(qū)塊鏈消息并對(duì)其合法性進(jìn)行驗(yàn)證。若收集到f+1個(gè)不同且合法的更新區(qū)塊鏈消息,則發(fā)送執(zhí)行結(jié)果消息給客戶機(jī)和所有節(jié)點(diǎn)。

圖3 SBFT共識(shí)機(jī)制執(zhí)行流程Fig.3 Execution flow of SBFT consensus mechanism

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

1.3.3 FBFT共識(shí)機(jī)制

FBFT共識(shí)機(jī)制弱化了主節(jié)點(diǎn)和備份節(jié)點(diǎn)的概念,典型的區(qū)塊鏈代表項(xiàng)目有瑞波(ripple)[31]、恒星(stellar)[32],每個(gè)驗(yàn)證節(jié)點(diǎn)在本地維護(hù)一個(gè)信任節(jié)點(diǎn)列表(Unique Node List,UNL),列表中的每個(gè)節(jié)點(diǎn)都能對(duì)交易進(jìn)行投票。FBFT共識(shí)機(jī)制相當(dāng)于他證制度,每個(gè)提案都以他人看法為準(zhǔn)。

1)驗(yàn)證請(qǐng)求。每個(gè)驗(yàn)證節(jié)點(diǎn)不間斷監(jiān)聽網(wǎng)絡(luò),接收來自客戶端的請(qǐng)求信息。經(jīng)過與本地?cái)?shù)據(jù)庫(kù)驗(yàn)證后,如果是不合法的請(qǐng)求,則將其直接丟棄;反之,放入到交易候選集。交易候選集中還包括之前共識(shí)過程中無(wú)法確認(rèn)而遺留的交易。

2)提出區(qū)塊。每個(gè)驗(yàn)證節(jié)點(diǎn)從自己的交易候選集中取出交易生成提案,并將提案發(fā)送給其他節(jié)點(diǎn)。

3)驗(yàn)證區(qū)塊。驗(yàn)證節(jié)點(diǎn)在收到其他節(jié)點(diǎn)發(fā)來的提案后,直接忽略不是來自UNL節(jié)點(diǎn)的提案,并對(duì)比提案中的交易和本地交易候選集,如果有相同交易,則該交易就獲得一票。在一定時(shí)間內(nèi),若交易獲得超過50%的票數(shù),則該交易進(jìn)入下一輪;若沒有獲得超過50%的票數(shù),則在下一次共識(shí)過程中再次進(jìn)行確認(rèn)。

4)再次驗(yàn)證區(qū)塊。每個(gè)驗(yàn)證節(jié)點(diǎn)將超過50%票數(shù)的交易作為提案發(fā)給其他節(jié)點(diǎn),同時(shí)提高所需票數(shù)的閾值至60%,重復(fù)步驟3和步驟4,直到閾值達(dá)到80%。

5)更新區(qū)塊鏈。每個(gè)驗(yàn)證節(jié)點(diǎn)將超過80%的UNL節(jié)點(diǎn)確認(rèn)的交易正式寫入本地?cái)?shù)據(jù)庫(kù),并更新交易候選集。

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

2 混合共識(shí)機(jī)制

2.1 基于PoW與PoS的共識(shí)機(jī)制

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

基于PoW與PoS的共識(shí)機(jī)制流程具體如下:

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

2)驗(yàn)證區(qū)塊頭和選舉權(quán)益代表。全體礦工驗(yàn)證新區(qū)塊頭,驗(yàn)證成功后選舉N個(gè)權(quán)益代表(系統(tǒng)初始化時(shí)設(shè)定N)。具體選舉協(xié)議為:將新區(qū)塊頭的哈希值、前一個(gè)區(qū)塊的哈希值和N個(gè)固定的后綴連接起來(每次使用一個(gè)后綴,共產(chǎn)生N個(gè)連接體),然后將連接體的哈希值作為輸入調(diào)用follow-the-satoshi算法產(chǎn)生權(quán)益代表(一個(gè)連接體產(chǎn)生一個(gè)權(quán)益代表)。

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

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

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

2.2 基于PoS與委托投票制度的共識(shí)機(jī)制

比特股(Bitshare)[37]結(jié)合委托投票制度對(duì)PoS共識(shí)機(jī)制做出重大改進(jìn),提出委托權(quán)益證明(Delegated Proof of Stake,DPoS)共識(shí)機(jī)制[38-39]。在DPoS共識(shí)機(jī)制中,代表者稱為見證人,由見證人按順序輪流產(chǎn)生區(qū)塊,其他見證人驗(yàn)證區(qū)塊。DPoS共識(shí)機(jī)制相當(dāng)于人民代表大會(huì)制度,由人大代表提出議案并對(duì)提案進(jìn)行投票。

DPoS共識(shí)機(jī)制通過選舉見證人行使權(quán)利,具體流程如下:

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

2)提出區(qū)塊。見證人產(chǎn)生區(qū)塊并對(duì)區(qū)塊簽名和添加時(shí)間戳,再在系統(tǒng)中廣播新產(chǎn)生的區(qū)塊,如果見證人在某個(gè)時(shí)隙沒有產(chǎn)生區(qū)塊,則該時(shí)隙將被跳過,產(chǎn)生區(qū)塊的權(quán)力交給下一個(gè)見證人。Bitshare中每2秒產(chǎn)生一個(gè)區(qū)塊,EOS中每3秒產(chǎn)生一個(gè)區(qū)塊。

3)驗(yàn)證區(qū)塊并更新區(qū)塊鏈。其他見證人負(fù)責(zé)驗(yàn)證新產(chǎn)生區(qū)塊的合法性。Bitshare中N個(gè)見證人驗(yàn)證通過就可上鏈(N個(gè)見證人要求代表的投票權(quán)之和大于50%),EOS中半數(shù)以上的見證人驗(yàn)證通過就可以上鏈。

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

2.3 基于PoS、VRF與公證制度的共識(shí)機(jī)制

文獻(xiàn)[41]結(jié)合可驗(yàn)證隨機(jī)函數(shù)(Verifiable Random Function,VRF)[42-44]、PoS和公證制度提出Dfinity共識(shí)機(jī)制。Dfinity共識(shí)機(jī)制中使用threshold BLS技術(shù)構(gòu)造VRF(稱為信標(biāo)),輸出一種隨時(shí)間變化的數(shù)據(jù)流。Dfinity共識(shí)機(jī)制相當(dāng)于公證制度,提案被任意一個(gè)合法的公證人證明后即可認(rèn)為可信。Dfinity共識(shí)機(jī)制執(zhí)行流程[41]如圖4所示,具體步驟如下:

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

2)提出區(qū)塊。每個(gè)提議者都能提議并廣播議案。議案由交易、提議者排名、前一個(gè)區(qū)塊的證書及對(duì)新區(qū)塊的簽名組成。系統(tǒng)根據(jù)提議者排名,給提案賦予不同的權(quán)重。提議者排名越高,權(quán)重越大。權(quán)重越大的提案越有可能成為新區(qū)塊。

3)驗(yàn)證區(qū)塊。每一輪都使用信標(biāo)隨機(jī)選舉出公證委員會(huì),其中公證人對(duì)新區(qū)塊進(jìn)行公證。等待一定時(shí)間后,每個(gè)公證人都將認(rèn)證成功的消息在區(qū)塊鏈系統(tǒng)中進(jìn)行廣播,若有多個(gè)區(qū)塊被公證,則將公證消息全部廣播。公證委員會(huì)中任意一個(gè)公證人公證一個(gè)區(qū)塊后,區(qū)塊鏈系統(tǒng)進(jìn)入新一輪共識(shí)。

4)更新區(qū)塊鏈。全體記賬節(jié)點(diǎn)根據(jù)公證委員會(huì)的認(rèn)證消息更新區(qū)塊鏈。

圖4 Dfinity共識(shí)機(jī)制執(zhí)行流程Fig.4 Execution flow of Dfinity consensus mechanism

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

2.4 基于PoS、BFT與委托投票制度的共識(shí)機(jī)制

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

2.5 基于PoS、BFT與VRF的共識(shí)機(jī)制

2.5.1 VBFT共識(shí)機(jī)制

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

VBFT共識(shí)機(jī)制運(yùn)行時(shí)依據(jù)VRF值作為索引,從PoS表中選舉共識(shí)節(jié)點(diǎn),具體流程如下:

1)選舉出塊者和提出區(qū)塊。每一輪依據(jù)VRF值從共識(shí)網(wǎng)絡(luò)中選舉潛在出塊者集合,每個(gè)潛在出塊者提出一個(gè)區(qū)塊。

2)驗(yàn)證區(qū)塊。每一輪依據(jù)VRF值從共識(shí)網(wǎng)絡(luò)中選舉出驗(yàn)證者集合,每個(gè)驗(yàn)證者從共識(shí)網(wǎng)絡(luò)中收集被提出的區(qū)塊進(jìn)行執(zhí)行驗(yàn)證,并投票給具有最高優(yōu)先級(jí)的區(qū)塊,廣播投票消息。

3)確認(rèn)區(qū)塊。每一輪依據(jù)VRF值從共識(shí)網(wǎng)絡(luò)中選舉出確認(rèn)者集合,確認(rèn)者統(tǒng)計(jì)驗(yàn)證者的投票,最后確認(rèn)達(dá)成共識(shí)的區(qū)塊并廣播確認(rèn)消息。

4)更新區(qū)塊鏈。共識(shí)網(wǎng)絡(luò)中所有的節(jié)點(diǎn)復(fù)制確認(rèn)者認(rèn)可的區(qū)塊,只有結(jié)束一輪共識(shí),才開啟新一輪共識(shí)。

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

2.5.2 Algorand共識(shí)機(jī)制

文獻(xiàn)[48]結(jié)合PoS、BFT和VRF提出Algorand共識(shí)機(jī)制,實(shí)現(xiàn)同步網(wǎng)絡(luò)的快速共識(shí)。VRF由可驗(yàn)證概率函數(shù)構(gòu)造.Hash(Signi(r,s,Qr)),其中,r表示節(jié)點(diǎn)對(duì)共識(shí)輪數(shù),s表示共識(shí)步數(shù),Qr表示隨機(jī)數(shù)種子,.表示小于1的小數(shù)且其后面是小數(shù)位,i表示節(jié)點(diǎn)數(shù)。Algorand共識(shí)機(jī)制[49-50]相當(dāng)于多委員會(huì)制度,包括出塊節(jié)點(diǎn)委員會(huì)和驗(yàn)證節(jié)點(diǎn)委員會(huì)。

1)選舉出塊節(jié)點(diǎn)和區(qū)塊驗(yàn)證節(jié)點(diǎn)。在第rk輪中的每個(gè)驗(yàn)證節(jié)點(diǎn)運(yùn)行VRF函數(shù)判斷自身身份:若在rk輪中沒有當(dāng)選為驗(yàn)證節(jié)點(diǎn),則不參與本輪共識(shí);若.Hash(Signi(r,s,Qr))

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

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

4)更新區(qū)塊鏈。參與記賬的用戶根據(jù)委員會(huì)的驗(yàn)證消息更新區(qū)塊鏈。

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

2.5.3 Omniledger共識(shí)機(jī)制

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

1)初始化?？蛻舳藙?chuàng)建跨分片鏈交易(cross-TX)。cross-TX被廣播給所有花費(fèi)UTXO的分片鏈(ISs)。

2)加鎖。所有ISs與cross-TX關(guān)聯(lián),每個(gè)ISs鎖定自身UTXO并檢查交易合法性。若驗(yàn)證通過,則先寫日志,分片鏈領(lǐng)導(dǎo)者提交接收證明;若驗(yàn)證失敗,分片鏈領(lǐng)導(dǎo)者提交拒絕證明。

3)解鎖?？蛻舳烁鶕?jù)階段2的結(jié)果發(fā)出提交交易信息或者取消交易消息。若所有ISs都驗(yàn)證通過,則發(fā)出提交消息;若其中有任意一個(gè)ISs提交了拒絕證明,則發(fā)出取消交易消息。ISs接收并驗(yàn)證提交消息后,將交易寫入分片鏈,并在UTXO中使用對(duì)應(yīng)的代幣并解鎖交易;接收UTXO的分片鏈(OSs)并在UTXO創(chuàng)造對(duì)應(yīng)的代幣。

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

2.6 基于BFT與鎖機(jī)制的共識(shí)機(jī)制

2.6.1 Tendermint共識(shí)機(jī)制

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

圖5 Tendermint共識(shí)機(jī)制執(zhí)行流程Fig.5 Execution flow of Tendermint consensus mechanism

2.6.2 Chainspace共識(shí)機(jī)制

文獻(xiàn)[54]結(jié)合BFT與鎖機(jī)制在Chainspace中提出S-BAC共識(shí)機(jī)制,保證了存儲(chǔ)分片中智能合約的正確性和安全性。S-BAC分片鏈內(nèi)部和分片鏈之間都使用BFT共識(shí)機(jī)制,區(qū)別在于對(duì)拜占庭節(jié)點(diǎn)數(shù)量要求不同。S-BAC分片鏈內(nèi)部相當(dāng)于公民投票制度,分片鏈之間相當(dāng)于否決權(quán)制度。

共識(shí)機(jī)制中的分片鏈和誠(chéng)實(shí)節(jié)點(diǎn)均指與交易相關(guān)的分片鏈和誠(chéng)實(shí)節(jié)點(diǎn),跨鏈通信由分片鏈領(lǐng)導(dǎo)者發(fā)起,Chainspace共識(shí)機(jī)制執(zhí)行流程[54]如圖6所示,具體步驟如下:

1)初始化。一個(gè)用戶初始化交易,將準(zhǔn)備消息至少發(fā)送給一個(gè)誠(chéng)實(shí)節(jié)點(diǎn)。為保證至少一個(gè)誠(chéng)實(shí)節(jié)點(diǎn)接收到準(zhǔn)備消息,需要在一條分片鏈中將消息發(fā)送給f+1個(gè)節(jié)點(diǎn),或者在每條分片鏈中都將消息發(fā)送給f+1個(gè)節(jié)點(diǎn)。

2)分配序號(hào)。接收到準(zhǔn)備消息,分片鏈進(jìn)入活動(dòng)狀態(tài),內(nèi)部使用BFT共識(shí)機(jī)制給準(zhǔn)備消息分配序號(hào)。

3)驗(yàn)證消息和加鎖。分片鏈內(nèi)部使用BFT共識(shí)機(jī)制驗(yàn)證交易,若超過f個(gè)節(jié)點(diǎn)驗(yàn)證通過,則進(jìn)入鎖定狀態(tài)并廣播準(zhǔn)備提交消息和證據(jù);否則廣播拒絕準(zhǔn)備消息和證據(jù)。如果節(jié)點(diǎn)處于鎖定狀態(tài)時(shí),則不接收其他交易并廣播拒絕其他交易消息。

4)接收。每條分片鏈都監(jiān)聽網(wǎng)絡(luò),如果收到一條拒絕準(zhǔn)備消息,則廣播拒絕提交消息和證據(jù);反之,廣播接收提交消息和證據(jù)。

5)提交和解鎖。若分片鏈接收到提交消息,則將其與交易相關(guān)的對(duì)象設(shè)置為不活躍狀態(tài)并提交交易,同時(shí)更新分片鏈及解鎖交易。若接收到拒絕提交消息,則釋放相應(yīng)的鎖,將相關(guān)的對(duì)象設(shè)置為活躍狀態(tài),等待下一次共識(shí)。

圖6 Chainspace共識(shí)機(jī)制執(zhí)行流程Fig.6 Execution flow of Chainspace consensus mechanism

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

3 其他共識(shí)機(jī)制

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

4 共識(shí)機(jī)制分析

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

表1 單一共識(shí)機(jī)制性能比較Table 1 Performance comparison of single consensus mechanisms

表2 典型的區(qū)塊鏈項(xiàng)目性能比較Table 2 Performance comparison of typical blockchain projects

5 研究展望

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

1)研究被委托人不遵守規(guī)則時(shí)對(duì)委托人賠償?shù)墓沧R(shí)機(jī)制。在基于委托的共識(shí)機(jī)制中,目前研究的重點(diǎn)是減少委托人不遵守規(guī)則時(shí)的懲罰,因此下一步將研究被委托人不遵守規(guī)則時(shí)如何對(duì)委托人進(jìn)行賠償。

2)研究結(jié)合VRF與Bitcoin-NG的共識(shí)機(jī)制。將VRF應(yīng)用于Bitcoin-NG中可以極大提高關(guān)鍵區(qū)塊的產(chǎn)生效率,從而降低能耗并提高資源利用率。

3)研究結(jié)合VRF與網(wǎng)絡(luò)分片技術(shù)的共識(shí)機(jī)制。將VRF應(yīng)用于網(wǎng)絡(luò)分片中可以提高共識(shí)機(jī)制效率并降低驗(yàn)證區(qū)塊時(shí)間,從而增加吞吐量。

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

6 結(jié)束語(yǔ)

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