劉懿中,劉建偉,張宗洋,2,徐同閣,2,喻 輝

1.北京航空航天大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院,北京100191

2.北京航空航天大學(xué) 合肥創(chuàng)新研究院,合肥230012

1 引言

2008年,Nakamoto 首次提出了比特幣[1],數(shù)字貨幣進(jìn)入了新的篇章.而數(shù)字貨幣底層的區(qū)塊鏈技術(shù)得到各界人士越來(lái)越多的重視[2].區(qū)塊鏈技術(shù)是在分布式、不可信環(huán)境中,所有節(jié)點(diǎn)通過(guò)一定的共識(shí)機(jī)制就公共賬本達(dá)成一致的技術(shù).共識(shí)機(jī)制作為區(qū)塊鏈技術(shù)的核心,從根本上決定了整個(gè)區(qū)塊鏈系統(tǒng)的安全性、可用性和系統(tǒng)性能等.研究區(qū)塊鏈的共識(shí)機(jī)制對(duì)區(qū)塊鏈擴(kuò)容、交易處理速度增快和安全性提升有著重要的意義,區(qū)塊鏈技術(shù)要在未來(lái)得到更廣泛的應(yīng)用,就必須研究共識(shí)機(jī)制.

1.1 區(qū)塊鏈概述

區(qū)塊鏈技術(shù)通過(guò)特定的共識(shí)機(jī)制實(shí)現(xiàn)了分布式節(jié)點(diǎn)之間賬本的一致.區(qū)塊鏈之所以被稱為“鏈”,是因?yàn)槊總€(gè)區(qū)塊(block)都以特定密碼學(xué)的方式鏈接到前一個(gè)區(qū)塊.一般而言,區(qū)塊鏈最開(kāi)始的區(qū)塊被稱為“創(chuàng)世區(qū)塊(genesis block)”,而區(qū)塊中存儲(chǔ)的內(nèi)容主要包括每段時(shí)間網(wǎng)絡(luò)中產(chǎn)生的交易(transaction).

區(qū)塊鏈一般具有以下幾個(gè)特點(diǎn)[3]:第一是去中心化.去中心化是指網(wǎng)絡(luò)中沒(méi)有可信第三方存在,不同于傳統(tǒng)中心化模式的交易,一般有政府、銀行或其他金融機(jī)構(gòu)的存在作為可信第三方; 第二是去信任化.去信任化是指節(jié)點(diǎn)之間不需要彼此信任,通過(guò)特定共識(shí)機(jī)制能夠最終達(dá)成對(duì)賬本的一致認(rèn)知; 第三是公開(kāi)透明性.在非授權(quán)網(wǎng)絡(luò)(permissionless network)中,所有節(jié)點(diǎn)能隨時(shí)加入、退出,節(jié)點(diǎn)能隨時(shí)獲得區(qū)塊鏈的歷史賬本數(shù)據(jù),接收到新生成的區(qū)塊; 第四是不可篡改性.區(qū)塊鏈中歷史數(shù)據(jù)不能被非法篡改,拿比特幣來(lái)說(shuō),當(dāng)區(qū)塊的“深度” 超過(guò)6 個(gè)之后,則可認(rèn)為區(qū)塊中的內(nèi)容大概率不會(huì)被篡改; 第五是匿名性.在比特幣中,雖然通過(guò)一些手段(如交易圖分析[4]等)能對(duì)歷史交易數(shù)據(jù)實(shí)施去隱私化分析,但通過(guò)采用一些隱私保護(hù)技術(shù),如群簽名、環(huán)簽名和零知識(shí)證明等,能夠有效保護(hù)區(qū)塊鏈中的用戶隱私數(shù)據(jù).

1.2 共識(shí)概述

共識(shí)機(jī)制是區(qū)塊鏈技術(shù)的基礎(chǔ)和核心.共識(shí)機(jī)制決定參與節(jié)點(diǎn)以何種方式對(duì)某些特定的數(shù)據(jù)達(dá)成一致.共識(shí)機(jī)制可以分為經(jīng)典分布式共識(shí)機(jī)制和區(qū)塊鏈共識(shí)機(jī)制.早在1975年,Akkoyunlu、Ekanadham和Huber[5]提出了計(jì)算機(jī)領(lǐng)域的“兩軍問(wèn)題”,對(duì)于共識(shí)機(jī)制的研究從此開(kāi)始.Lamport、Shostak和Pease[6]提出了“拜占庭將軍問(wèn)題”,研究在可能存在故障節(jié)點(diǎn)或惡意攻擊的情況下,非故障節(jié)點(diǎn)如何對(duì)特定數(shù)據(jù)達(dá)成一致.拜占庭將軍問(wèn)題成為了共識(shí)機(jī)制研究的基礎(chǔ).Lamport[7]提出了解決拜占庭將軍問(wèn)題的Paxos 算法,該算法能夠容忍網(wǎng)絡(luò)中一定數(shù)量節(jié)點(diǎn)發(fā)生崩潰(crash),在分布式系統(tǒng)中,就某個(gè)特定值達(dá)成一致.1999年,Castro和Liskov[8]提出了實(shí)用拜占庭容錯(cuò)協(xié)議(practical Byzantine fault tolerance,PBFT),作為拜占庭將軍問(wèn)題的解決方案,PBFT 允許網(wǎng)絡(luò)中存在一定數(shù)量的拜占庭節(jié)點(diǎn),這些節(jié)點(diǎn)能夠在共識(shí)達(dá)成過(guò)程中制造虛假信息,以各種手段阻礙其他誠(chéng)實(shí)節(jié)點(diǎn)完成共識(shí).PBFT 能夠在敵手?jǐn)?shù)量占比不超過(guò)全部節(jié)點(diǎn)數(shù)量1/3 的情況下,實(shí)現(xiàn)最終誠(chéng)實(shí)節(jié)點(diǎn)的共識(shí).

2008年,Nakamoto 提出比特幣,共識(shí)機(jī)制進(jìn)入?yún)^(qū)塊鏈共識(shí)時(shí)代.目前區(qū)塊鏈共識(shí)可以分為兩大類,一類是授權(quán)共識(shí)(permissioned consensus)機(jī)制,授權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)一般通過(guò)公鑰基礎(chǔ)設(shè)施(public key infrastructure,PKI)完成身份認(rèn)證后,才能參與后續(xù)共識(shí)機(jī)制; 另一類是以比特幣為代表的非授權(quán)共識(shí)(permissionless consensus)機(jī)制.非授權(quán)網(wǎng)絡(luò)中,節(jié)點(diǎn)隨時(shí)加入和退出,節(jié)點(diǎn)數(shù)量動(dòng)態(tài)變化且不可預(yù)知,非授權(quán)共識(shí)通過(guò)特定算法完成出塊者(block proposer)選舉、區(qū)塊生成和節(jié)點(diǎn)驗(yàn)證更新區(qū)塊鏈等過(guò)程.

本文主要研究區(qū)塊鏈共識(shí)機(jī)制,其基本流程如下:

(1)選舉出塊者.“出塊者” 是指區(qū)塊鏈中負(fù)責(zé)產(chǎn)生區(qū)塊的節(jié)點(diǎn),又被稱為記賬者.目前的出塊者可以分為兩種,一種是單一節(jié)點(diǎn)作為出塊者,另一種是多個(gè)節(jié)點(diǎn)構(gòu)成委員會(huì)(committee),整個(gè)委員會(huì)作為出塊者.出塊者選舉的過(guò)程中,需要充分考慮到女巫攻擊(sybil attack)[9]的存在,參與選舉的節(jié)點(diǎn)需要完成一定的任務(wù)或具備某種條件才能夠成為出塊者.目前區(qū)塊鏈中大多數(shù)采用工作量證明(proof of work)或權(quán)益證明(proof of stake)的方式來(lái)防止女巫攻擊.工作量證明要求參與節(jié)點(diǎn)完成一定的計(jì)算任務(wù),而權(quán)益證明要求節(jié)點(diǎn)擁有一定的財(cái)產(chǎn).

(2)生成區(qū)塊.出塊者主要完成生成區(qū)塊的工作,即將一段時(shí)間內(nèi)網(wǎng)絡(luò)中產(chǎn)生的交易數(shù)據(jù)打包放到當(dāng)前區(qū)塊中,而為了讓區(qū)塊成為鏈狀結(jié)構(gòu),就必須在區(qū)塊中包含其他內(nèi)容.一般來(lái)說(shuō)區(qū)塊可以分為區(qū)塊頭(block header)和區(qū)塊體(block body)兩部分.區(qū)塊頭中一般包括上個(gè)區(qū)塊的哈希值(hash)、時(shí)間戳等內(nèi)容,區(qū)塊體中包含了完整的交易數(shù)據(jù).目前可以按照出塊者與區(qū)塊的對(duì)應(yīng)關(guān)系將區(qū)塊生成過(guò)程分為兩類:一類是“一對(duì)一” 關(guān)系,一個(gè)出塊者對(duì)應(yīng)一個(gè)區(qū)塊,下一個(gè)區(qū)塊由新選舉的出塊者負(fù)責(zé)生成,如比特幣; 一類是“一對(duì)多” 關(guān)系,一個(gè)出塊者在其“任職” 期間,能夠生成多個(gè)區(qū)塊,一般將一個(gè)出塊者的任職時(shí)間稱為一個(gè)時(shí)期(epoch),每個(gè)時(shí)期由多個(gè)輪(round)組成,每一輪生成一個(gè)區(qū)塊.

(3)節(jié)點(diǎn)驗(yàn)證更新區(qū)塊鏈.出塊者生成區(qū)塊后,將區(qū)塊在網(wǎng)絡(luò)中廣播.收到區(qū)塊的節(jié)點(diǎn)驗(yàn)證區(qū)塊正確性并更新本地區(qū)塊鏈.在部分共識(shí)機(jī)制中,節(jié)點(diǎn)可能還需驗(yàn)證區(qū)塊中交易合法性和出塊者身份合法性等.

對(duì)于區(qū)塊鏈共識(shí),主要的評(píng)價(jià)標(biāo)準(zhǔn)有如下幾點(diǎn).

(1)安全性.區(qū)塊鏈共識(shí)機(jī)制的安全性主要是指在敵手存在且能操控一定的網(wǎng)絡(luò)資源和其他資源的情況下,誠(chéng)實(shí)用戶能夠在不可信網(wǎng)絡(luò)環(huán)境中達(dá)成最終的一致,并且能夠抵抗一些針對(duì)共識(shí)機(jī)制的攻擊.安全性是共識(shí)機(jī)制應(yīng)當(dāng)滿足的最基本、最重要的屬性.

(2)交易吞吐率.交易吞吐率是指區(qū)塊鏈系統(tǒng)的交易處理速度,一般采用每秒鐘處理交易的數(shù)量作為評(píng)判標(biāo)準(zhǔn).交易吞吐率受到區(qū)塊產(chǎn)生間隔、區(qū)塊大小和網(wǎng)絡(luò)延時(shí)等因素的影響.

(3)可擴(kuò)展性.可擴(kuò)展性是指網(wǎng)絡(luò)處理交易的性能是否能夠隨著節(jié)點(diǎn)的增多而增強(qiáng),其關(guān)注的是網(wǎng)絡(luò)處理能力的可增長(zhǎng)性.可擴(kuò)展性一般通過(guò)對(duì)網(wǎng)絡(luò)實(shí)施分片(sharding)來(lái)實(shí)現(xiàn),將整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)分為不同的分片,每個(gè)分片并行處理分片內(nèi)部的數(shù)據(jù).

(4)交易確認(rèn)時(shí)間.交易確認(rèn)時(shí)間指得是交易從被提交至共識(shí)網(wǎng)絡(luò),到交易被完全確認(rèn)所需要的時(shí)間.交易完全確認(rèn)是指交易被寫入到區(qū)塊中,且確保大概率不會(huì)被篡改,交易雙方能夠以此作為憑證完成整個(gè)交易過(guò)程.在比特幣中,交易確認(rèn)時(shí)間大約為60 分鐘(6 個(gè)區(qū)塊的生成時(shí)間),60 分鐘過(guò)后,才能保證區(qū)塊大概率不會(huì)出現(xiàn)分叉,即保證交易大概率不會(huì)被篡改.在確定性共識(shí)中,由于區(qū)塊鏈一般不會(huì)產(chǎn)生分叉,因此交易確認(rèn)時(shí)間能夠降低.

(5)去中心化.去中心化是指區(qū)塊鏈采用的共識(shí)機(jī)制中沒(méi)有可信第三方存在.與此同時(shí),區(qū)塊由參與共識(shí)的節(jié)點(diǎn)共同決定,而不是集中在少數(shù)幾個(gè)節(jié)點(diǎn)上.網(wǎng)絡(luò)中節(jié)點(diǎn)的權(quán)力應(yīng)當(dāng)分散化,而不是集中化.目前比特幣挖礦采用的“礦池(mining pool)” 在一定程度上影響了比特幣的去中心化[10].

(6)資源占用.資源占用主要考量的是共識(shí)機(jī)制帶來(lái)的節(jié)點(diǎn)間的通信復(fù)雜度(communication complexity)和節(jié)點(diǎn)需要的計(jì)算復(fù)雜度(computation complexity).資源占用通常與交易確認(rèn)時(shí)間和交易吞吐率指標(biāo)緊密聯(lián)系.

1.3 本文貢獻(xiàn)

本文主要研究了以下內(nèi)容:

(1)總結(jié)了區(qū)塊鏈共識(shí)機(jī)制的基本流程,將其分為出塊者選舉、區(qū)塊生成和節(jié)點(diǎn)驗(yàn)證更新區(qū)塊鏈等幾步.根據(jù)出塊者選舉過(guò)程,將區(qū)塊鏈共識(shí)機(jī)制的特性分為弱一致性和強(qiáng)一致性兩類; 根據(jù)區(qū)塊生成過(guò)程,將出塊者和區(qū)塊關(guān)系分為“一對(duì)一”和“一對(duì)多” 兩類.

(2)總結(jié)了共識(shí)機(jī)制的評(píng)判標(biāo)準(zhǔn),包括安全性、交易吞吐率、可擴(kuò)展性、交易確認(rèn)時(shí)間、去中心化和資源占用等內(nèi)容.

(3)分類研究了共識(shí)機(jī)制的系統(tǒng)模型,將網(wǎng)絡(luò)模型分為同步網(wǎng)絡(luò)、部分同步網(wǎng)絡(luò)和異步網(wǎng)絡(luò),將腐化模型分為靜態(tài)敵手、溫和敵手和適應(yīng)性敵手,將敵手模型分為n=2f+1、n=3f+1和n=4f+1,指出了各類模型之間的區(qū)別.

(4)分類研究了現(xiàn)有共識(shí)機(jī)制,分析了各類共識(shí)機(jī)制的基本原理、典型方案和優(yōu)缺點(diǎn).

經(jīng)典分布式共識(shí)主要在節(jié)點(diǎn)之間完成狀態(tài)機(jī)復(fù)制,實(shí)現(xiàn)一致性和活性.典型方案包括Paxos、PBFT、Hot-Stuff[11]、SBFT[12]、MinBFT[13]和Honey Badger BFT[14]等;

授權(quán)共識(shí)機(jī)制是節(jié)點(diǎn)經(jīng)過(guò)身份認(rèn)證后,通過(guò)分布式一致性算法完成區(qū)塊的生成和維護(hù).典型方案包括Hyperledger[15,16]、DFINITY[17]和PaLa[18]等;

基于工作量證明的共識(shí)機(jī)制,節(jié)點(diǎn)利用自身算力通過(guò)尋找哈希函數(shù)原像完成出塊者選舉.典型方案包括比特幣、以太坊[19]、Bitcoin-NG[20]、FruitChains[21]、GHOST[22]和Spectre[23]等.可能面臨的安全問(wèn)題包括日蝕攻擊、雙花攻擊和自私挖礦等;

基于權(quán)益證明的共識(shí)機(jī)制,在所有合法持幣者中隨機(jī)選取節(jié)點(diǎn)作為出塊者.典型方案包括PPCoin[24]、Casper FFG[25]、Ouroboros[26]、Snow White[27]和DPoS[28]等.可能面臨的安全問(wèn)題包括無(wú)利害關(guān)系問(wèn)題、打磨攻擊、長(zhǎng)程攻擊和權(quán)益竊取攻擊等;

采用單一委員會(huì)的混合共識(shí)機(jī)制主要利用PoW 或PoS 選出部分節(jié)點(diǎn)作為共識(shí)委員會(huì),在委員會(huì)內(nèi)部運(yùn)行類似于PBFT 的分布式一致性算法完成區(qū)塊的生成.典型方案包括PeerCensus[29]、ByzCoin[30]、Solida[31]、hybrid consensus[32]、Thunderella[33]和Algorand[34]等.可能面臨的安全問(wèn)題主要是惡意節(jié)點(diǎn)干擾委員會(huì)選舉和重配置過(guò)程;

采用多委員會(huì)的混合共識(shí)將網(wǎng)絡(luò)劃分為多個(gè)片區(qū),每個(gè)片區(qū)運(yùn)行并行的委員會(huì)對(duì)交易分別處理.典型方案包括ELASTICO[35]、Omniledger[36]、Chainspace[37]和RapidChain[38]等.可能面臨的安全問(wèn)題主要是跨片交易的高效處理和敵手對(duì)重配置過(guò)程的偏置.

(5)分析了未來(lái)共識(shí)機(jī)制的研究熱點(diǎn)和發(fā)展方向.

本文對(duì)區(qū)塊鏈時(shí)代的共識(shí)機(jī)制研究總結(jié)如表1所示.其中,符號(hào)“/” 代表當(dāng)前系統(tǒng)沒(méi)有該特性值或沒(méi)有具體可查的系統(tǒng)參數(shù); 符號(hào)“√” 代表滿足當(dāng)前特性; 符號(hào)“×” 代表不滿足當(dāng)前特性.

1.4 相關(guān)工作

共識(shí)機(jī)制是區(qū)塊鏈技術(shù)的核心,在基本層面上決定了區(qū)塊鏈系統(tǒng)的安全性、可擴(kuò)展性和分布式特性.近幾年國(guó)內(nèi)外對(duì)于區(qū)塊鏈時(shí)代共識(shí)機(jī)制的綜述研究主要包括以下內(nèi)容.

在國(guó)內(nèi)研究方面,文獻(xiàn)[39]研究了區(qū)塊鏈共識(shí)機(jī)制,系統(tǒng)整理了區(qū)塊鏈技術(shù)發(fā)展過(guò)程中有代表性的共識(shí)機(jī)制,將共識(shí)機(jī)制分為傳統(tǒng)分布式一致性算法和區(qū)塊鏈共識(shí)機(jī)制,并提出區(qū)塊鏈共識(shí)機(jī)制的基礎(chǔ)模型和分類方法,該工作側(cè)重于整體層面研究,對(duì)每一類共識(shí)機(jī)制的介紹過(guò)于簡(jiǎn)單,而本文在對(duì)區(qū)塊鏈共識(shí)機(jī)制分類的基礎(chǔ)上,總結(jié)每一類共識(shí)機(jī)制的基本流程,并且深入研究了典型協(xié)議,給出了協(xié)議的具體步驟,指出了協(xié)議可能存在的問(wèn)題.文獻(xiàn)[40]研究了區(qū)塊鏈不同共識(shí)機(jī)制的組合,分析了工作量證明和權(quán)益證明的組合、拜占庭一致和權(quán)益證明的組合,但是對(duì)于混合共識(shí)沒(méi)有給出具體的分類,研究過(guò)于簡(jiǎn)單.文獻(xiàn)[41]側(cè)重分類對(duì)比各種區(qū)塊鏈共識(shí)機(jī)制,指出了部分共識(shí)機(jī)制的不足之處,其對(duì)于共識(shí)機(jī)制的分類較為簡(jiǎn)單.文獻(xiàn)[42]主要關(guān)注拜占庭容錯(cuò)技術(shù),重點(diǎn)研究了PBFT 及其改進(jìn),并給出了拜占庭容錯(cuò)的應(yīng)用場(chǎng)景.文獻(xiàn)[43]簡(jiǎn)單分析了Bitcoin、Ouroboros、ByzCoin和Omniledger 四種典型區(qū)塊鏈共識(shí)機(jī)制.

在國(guó)外研究方面,Bano 等人[44]主要研究了區(qū)塊鏈的可擴(kuò)展性,分析了多種共識(shí)機(jī)制的交易吞吐率和交易處理的可擴(kuò)展性,指出了未來(lái)共識(shí)機(jī)制的研究方向.該工作側(cè)重于研究區(qū)塊鏈共識(shí)機(jī)制,對(duì)于經(jīng)典共識(shí)只是簡(jiǎn)要概括,本文深入研究了PBFT 等經(jīng)典共識(shí)機(jī)制及其改進(jìn),分析了其具體流程.經(jīng)典共識(shí)作為混合共識(shí)的重要組成部分,起到了十分關(guān)鍵的作用.與此同時(shí),本文研究了最新的區(qū)塊鏈共識(shí)機(jī)制,對(duì)每一類共識(shí)機(jī)制的研究更加細(xì)致.Zohar[45]側(cè)重于研究區(qū)塊鏈激勵(lì)機(jī)制,分析了以工作量證明為基礎(chǔ)的區(qū)塊鏈系統(tǒng)中激勵(lì)機(jī)制的重要性,不合理的激勵(lì)能夠?qū)е抡麄€(gè)系統(tǒng)不安全.Cachin和Vukoli?[46]主要分類研究經(jīng)典分布式一致算法,總結(jié)了PBFT 等協(xié)議的核心思想,列舉出其在授權(quán)共識(shí)中的應(yīng)用.他們側(cè)重于授權(quán)共識(shí)機(jī)制的研究,卻沒(méi)有對(duì)整個(gè)區(qū)塊鏈共識(shí)機(jī)制分類并介紹特性.Bano、Al-Bassam和Danezis[47]研究了可擴(kuò)展區(qū)塊鏈體制,提出了區(qū)塊鏈擴(kuò)容可能采取的方法,如分片共識(shí)、基于委員會(huì)的混合共識(shí)等,卻沒(méi)有給出每個(gè)協(xié)議的設(shè)計(jì)細(xì)節(jié).Pass和Shi[48]以形式化的方式描述了非授權(quán)共識(shí)機(jī)制的特性,包括鏈質(zhì)量、鏈增長(zhǎng)和一致性,并且給出了能夠滿足公平性、快速響應(yīng)等特性的非授權(quán)區(qū)塊鏈共識(shí)機(jī)制.Garay和Kiayias[49]研究了區(qū)塊鏈共識(shí)的分類方法,側(cè)重于網(wǎng)絡(luò)模型、敵手模型等分類問(wèn)題.

2 模型和定義

2.1 定義

定義1(狀態(tài)機(jī)復(fù)制)狀態(tài)機(jī)復(fù)制(state machine replication)是指存在一組節(jié)點(diǎn)且所有節(jié)點(diǎn)共同維持一個(gè)線性增長(zhǎng)的日志,并且就日志內(nèi)容達(dá)成一致[50].

一般來(lái)說(shuō),節(jié)點(diǎn)中存在一個(gè)主機(jī)(primary),而其他節(jié)點(diǎn)被稱為從機(jī)(backups),主機(jī)的身份可以變化.狀態(tài)機(jī)復(fù)制具備一定的容錯(cuò)功能,在可容忍的范圍內(nèi),允許一定比例的節(jié)點(diǎn)出現(xiàn)故障或遭受敵手攻擊.它需要滿足兩個(gè)重要的安全特性:第一是一致性(consistency),即所有誠(chéng)實(shí)節(jié)點(diǎn)最終輸出的日志彼此一致;第二是活性(liveness),任一誠(chéng)實(shí)節(jié)點(diǎn)收到的交易在一定時(shí)間之后出現(xiàn)在所有誠(chéng)實(shí)節(jié)點(diǎn)的日志中.

另外,Pass和Shi[32]提出了狀態(tài)機(jī)復(fù)制的快速響應(yīng)特性.

定義2(快速響應(yīng)特性)快速響應(yīng)特性(responsiveness)是指交易確認(rèn)時(shí)間與網(wǎng)絡(luò)真實(shí)時(shí)延δ有關(guān),與網(wǎng)絡(luò)時(shí)延上限?無(wú)關(guān).

狀態(tài)機(jī)復(fù)制過(guò)去經(jīng)常被用于大型數(shù)據(jù)庫(kù)的同步,如Google和Facebook 將狀態(tài)機(jī)復(fù)制用于其數(shù)據(jù)庫(kù)核心部分的同步.

定義3(授權(quán)共識(shí))授權(quán)共識(shí)(permissoned consensus)是指在授權(quán)網(wǎng)絡(luò)中,PKI 存在且為每個(gè)節(jié)點(diǎn)實(shí)施身份認(rèn)證.注冊(cè)完成后,每個(gè)節(jié)點(diǎn)都能獲知所有參與者節(jié)點(diǎn)數(shù)量和身份等信息.所有節(jié)點(diǎn)運(yùn)行內(nèi)部分布式共識(shí)機(jī)制,實(shí)現(xiàn)狀態(tài)機(jī)復(fù)制,完成賬本的生成和維護(hù),并將賬本以區(qū)塊鏈的形式實(shí)現(xiàn).授權(quán)共識(shí)需要滿足一致性和活性.

定義4(非授權(quán)共識(shí))非授權(quán)共識(shí)(permissionless consensus)是指在非授權(quán)網(wǎng)絡(luò)中,節(jié)點(diǎn)不需要經(jīng)過(guò)身份認(rèn)證,網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量隨時(shí)變化,節(jié)點(diǎn)無(wú)法獲知所有參與者節(jié)點(diǎn)數(shù)量和身份等信息.所有節(jié)點(diǎn)通過(guò)一定的共識(shí)機(jī)制實(shí)現(xiàn)非授權(quán)網(wǎng)絡(luò)中的狀態(tài)機(jī)復(fù)制.非授權(quán)共識(shí)同樣需要滿足一致性和活性.

非授權(quán)網(wǎng)絡(luò)與授權(quán)網(wǎng)絡(luò)的區(qū)別主要有以下兩點(diǎn):第一,任何節(jié)點(diǎn)在任意時(shí)間都能隨時(shí)加入或退出非授權(quán)網(wǎng)絡(luò),不需要完成身份認(rèn)證; 第二,參與非授權(quán)共識(shí)的節(jié)點(diǎn)數(shù)目隨時(shí)變化,不可預(yù)知.

定義5(公共賬本)公共賬本(public ledger)是指能夠滿足一致性和活性的可信“公告牌”,任何人都能夠在上面存放消息,任何人都能夠讀取賬本上的內(nèi)容.

公共賬本的概念是對(duì)狀態(tài)機(jī)復(fù)制的延伸,狀態(tài)機(jī)復(fù)制在過(guò)去僅僅被用在授權(quán)網(wǎng)絡(luò)中完成數(shù)據(jù)的同步,而公共賬本意味著在非授權(quán)網(wǎng)絡(luò)中,實(shí)現(xiàn)公開(kāi)透明、任何節(jié)點(diǎn)能夠隨時(shí)訪問(wèn)、添加信息的公共的賬本.

公共賬本應(yīng)當(dāng)滿足以下兩個(gè)安全特性[51].

定義6(持續(xù)性)持續(xù)性(persistance)是指誠(chéng)實(shí)用戶在賬本的某個(gè)位置,如第i個(gè)區(qū)塊的第j個(gè)位置上傳了合法交易tx,則最終所有誠(chéng)實(shí)用戶的賬本中,第i個(gè)區(qū)塊的第j個(gè)位置的交易一定存在,且一定是tx.

定義7(活性)活性(liveness)是指在某個(gè)時(shí)間,誠(chéng)實(shí)用戶上傳了交易tx 至公共賬本,則在等待時(shí)間t之后,交易tx 一定出現(xiàn)在每個(gè)誠(chéng)實(shí)用戶的賬本中.

定義8(共同前綴)共同前綴(common prefix)用符號(hào)Qcp表示,安全參數(shù)k∈N任意兩個(gè)誠(chéng)實(shí)節(jié)點(diǎn)P1,P2在兩輪r1,r2中所提交的鏈C1,C2,一定滿足即當(dāng)r1≤r2時(shí),滿足代表的是鏈C1去掉末尾的k個(gè)區(qū)塊,代表C1是C2的前綴.節(jié)點(diǎn)P1,P2代表的可以是同一個(gè)節(jié)點(diǎn).

表1 共識(shí)機(jī)制總結(jié)Table 1 Summary of consensus mechanisms

共同前綴特性可以這樣理解,誠(chéng)實(shí)節(jié)點(diǎn)產(chǎn)生的鏈最終會(huì)彼此一致,且誠(chéng)實(shí)節(jié)點(diǎn)已經(jīng)確定的鏈不會(huì)被改寫.

定義9(鏈質(zhì)量)鏈質(zhì)量(chain quality)用符號(hào)Qcq表示,安全參數(shù)任何誠(chéng)實(shí)節(jié)點(diǎn)P的鏈C中除去最新的k0區(qū)塊后,任意k個(gè)連續(xù)的區(qū)塊中,惡意區(qū)塊的比例不超過(guò)μ.

鏈質(zhì)量屬性是指連續(xù)的區(qū)塊中必定有足夠比例的區(qū)塊由誠(chéng)實(shí)用戶產(chǎn)生.

定義10(鏈增長(zhǎng))鏈增長(zhǎng)(chain growth)用符號(hào)Qcg表示,安全參數(shù)為對(duì)于任意輪r(r>r0),誠(chéng)實(shí)節(jié)點(diǎn)P在第r輪的輸出的區(qū)塊鏈為C1,在第r+s輪輸出的區(qū)塊鏈為鏈C2,滿足

此外,區(qū)塊鏈特性還包括公平性.

定義11(公平性)公平性(fairness)是指誠(chéng)實(shí)用戶實(shí)際產(chǎn)生的區(qū)塊占比大致與誠(chéng)實(shí)用戶的算力占比(或與誠(chéng)實(shí)用戶所擁有的財(cái)產(chǎn)占比)相符.對(duì)于采用PoW 的區(qū)塊鏈來(lái)說(shuō),如果誠(chéng)實(shí)用戶的算力占全網(wǎng)算力的1/2,那么能夠保證大約1/2 的區(qū)塊由誠(chéng)實(shí)用戶產(chǎn)生.

定義12(弱一致性)弱一致性(weak consistency)也被稱為最終一致(eventual consistency),一般根據(jù)出塊者選舉的方式,同一個(gè)時(shí)期可能有兩個(gè)甚至兩個(gè)以上合法的出塊者,這種情況下,區(qū)塊鏈可能出現(xiàn)分叉,如比特幣.但是經(jīng)過(guò)很長(zhǎng)一段時(shí)間之后,最終區(qū)塊鏈的區(qū)塊是確定的.

定義13(強(qiáng)一致性)強(qiáng)一致性(strong consistency)是指區(qū)塊的生成是確定性的,具有強(qiáng)一致性的共識(shí)又被稱為確定性共識(shí),通過(guò)選取一個(gè)確定的委員會(huì),再由委員會(huì)內(nèi)部運(yùn)行的分布式一致性算法生成新區(qū)塊,每一輪的區(qū)塊都是確定的,一般情況下不會(huì)產(chǎn)生分叉.

相比于弱一致性,強(qiáng)一致性具有以下優(yōu)點(diǎn):

(1)區(qū)塊鏈無(wú)分叉,通過(guò)運(yùn)行分布式一致性算法,實(shí)現(xiàn)狀態(tài)機(jī)復(fù)制,節(jié)點(diǎn)不需要浪費(fèi)大量算力;

(2)交易能夠得到較快速度的確認(rèn),節(jié)點(diǎn)上傳的交易只要被寫入到區(qū)塊中,便可以確認(rèn)交易的合法性,完成整個(gè)交易過(guò)程;

(3)能夠提供前向安全(forward security).只要區(qū)塊被寫入到區(qū)塊鏈上,就可以確保區(qū)塊不會(huì)被篡改,區(qū)塊將一直保持在鏈上.

2.2 模型分類

以下分別介紹共識(shí)機(jī)制的網(wǎng)絡(luò)模型、腐化模型和敵手模型.

2.2.1 網(wǎng)絡(luò)模型

定義14(同步網(wǎng)絡(luò))同步網(wǎng)絡(luò)(synchronous network)是指誠(chéng)實(shí)節(jié)點(diǎn)之間的消息按照輪來(lái)傳播,在每一輪中,誠(chéng)實(shí)用戶發(fā)出的消息能夠在下一輪之前到達(dá)其他所有誠(chéng)實(shí)用戶.同步網(wǎng)絡(luò)是比較強(qiáng)的網(wǎng)絡(luò)模型.

定義15(部分同步網(wǎng)絡(luò))部分同步網(wǎng)絡(luò)(partially synchronous network)是指網(wǎng)絡(luò)中的消息傳輸存在一定的上限?,時(shí)延上限不能作為協(xié)議的參數(shù)使用,但是能夠確保誠(chéng)實(shí)用戶發(fā)出的消息在?時(shí)間之后到達(dá)其他所有誠(chéng)實(shí)用戶[62].部分同步網(wǎng)絡(luò)是區(qū)塊鏈協(xié)議分析中常用的網(wǎng)絡(luò)模型.

定義16(異步網(wǎng)絡(luò))異步網(wǎng)絡(luò)(asynchronous network)是指敵手能夠任意拖延誠(chéng)實(shí)用戶的消息或?qū)⑵浯騺y順序,只要保證最終誠(chéng)實(shí)用戶的消息能夠到達(dá)彼此.

2.2.2 腐化模型

腐化(corruption)是指敵手通過(guò)向目標(biāo)節(jié)點(diǎn)發(fā)動(dòng)攻擊,獲取目標(biāo)節(jié)點(diǎn)的秘密信息,進(jìn)而控制目標(biāo)節(jié)點(diǎn)的輸入輸出消息,使其完全受到自身的控制.

定義17(靜態(tài)敵手)靜態(tài)敵手(static corruption)是指敵手只能在協(xié)議開(kāi)始前選定其腐化的目標(biāo),一旦協(xié)議開(kāi)始運(yùn)行,便不能夠腐化誠(chéng)實(shí)節(jié)點(diǎn).敵手控制的節(jié)點(diǎn)數(shù)量在協(xié)議運(yùn)行期間不會(huì)發(fā)生改變.

定義18(τ-溫和敵手)τ-溫和敵手(τ-mildly corruption)是指敵手腐化一個(gè)節(jié)點(diǎn)需要一定的時(shí)間τ來(lái)完成.敵手發(fā)布對(duì)目標(biāo)節(jié)點(diǎn)的腐化指令,經(jīng)過(guò)τ時(shí)間后,目標(biāo)節(jié)點(diǎn)被腐化,受到敵手的控制,成為惡意節(jié)點(diǎn).在實(shí)施腐化的t時(shí)間內(nèi),節(jié)點(diǎn)仍然屬于誠(chéng)實(shí)節(jié)點(diǎn).溫和敵手是區(qū)塊鏈協(xié)議分析中經(jīng)常采用的腐化模型.

定義19(適應(yīng)性敵手)適應(yīng)性敵手(adaptive corruption)是指敵手能夠根據(jù)協(xié)議運(yùn)行過(guò)程中搜集的信息,動(dòng)態(tài)且適應(yīng)性對(duì)目標(biāo)節(jié)點(diǎn)完成腐化.適應(yīng)性敵手的能力十分強(qiáng)大.

2.2.3 敵手模型

敵手模型是指對(duì)敵手能夠掌握的算力或財(cái)產(chǎn)占比作出一定的限制,一般用f代表敵手?jǐn)?shù)量,n代表網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù),利用n與f的關(guān)系來(lái)刻畫敵手模型,將其分為如下幾類:

定義20(n=2f+1)敵手算力(或財(cái)產(chǎn))占全網(wǎng)算力(或財(cái)產(chǎn))的比例不超過(guò)1/2.

比特幣采用的敵手模型是n=2f+1,敵手算力一旦超過(guò)1/2,便可以制造區(qū)塊鏈的分叉,發(fā)動(dòng)所謂的“51%” 攻擊.

定義21(n=3f+1)敵手算力(或財(cái)產(chǎn))占全網(wǎng)算力(或財(cái)產(chǎn))的比例不超過(guò)1/3.

如PBFT 之類的經(jīng)典分布式共識(shí)機(jī)制要求敵手模型為n=3f+1,而在一些混合共識(shí)中,受到委員會(huì)內(nèi)部分布式一致性算法的限制,同樣需要敵手模型為n=3f+1.

定義22(n=4f+1)敵手算力(或財(cái)產(chǎn))占全網(wǎng)算力(或財(cái)產(chǎn))不超過(guò)1/4.

考慮到自私挖礦導(dǎo)致鏈質(zhì)量下降,某些混合共識(shí)在選舉委員會(huì)時(shí),為了滿足委員會(huì)成員中敵手?jǐn)?shù)量不超過(guò)1/3,需要要求區(qū)塊鏈鏈質(zhì)量大于2/3,這種情況下需要滿足n=4f+1,才能滿足委員會(huì)中誠(chéng)實(shí)用戶占據(jù)2/3 以上的要求.

3 經(jīng)典分布式共識(shí)機(jī)制

3.1 概念

經(jīng)典分布式共識(shí)機(jī)制是指在授權(quán)網(wǎng)絡(luò)中,一組節(jié)點(diǎn)實(shí)現(xiàn)狀態(tài)機(jī)復(fù)制.它主要面向一些分布式數(shù)據(jù)庫(kù)系統(tǒng),像Paxos 算法主要針對(duì)網(wǎng)絡(luò)中可能出現(xiàn)的崩潰節(jié)點(diǎn)而設(shè)計(jì),而PBFT 能夠容忍一定的拜占庭錯(cuò)誤節(jié)點(diǎn).根據(jù)網(wǎng)絡(luò)模型假設(shè),可以將經(jīng)典分布式共識(shí)機(jī)制分為以下三類:第一類是部分同步網(wǎng)絡(luò)分布式一致算法,部分同步網(wǎng)絡(luò)模型是經(jīng)典分布式共識(shí)和區(qū)塊鏈共識(shí)機(jī)制最常用的模型; 第二類是異步網(wǎng)絡(luò)分布式一致算法,異步網(wǎng)絡(luò)模型也是共識(shí)研究中經(jīng)常采用的模型,在完全異步網(wǎng)絡(luò)中實(shí)現(xiàn)共識(shí)通常需要隨機(jī)數(shù)發(fā)生器來(lái)完成; 第三類是同步網(wǎng)絡(luò)分布式一致算法,同步網(wǎng)絡(luò)模型假設(shè)較強(qiáng),在實(shí)際運(yùn)用中可能會(huì)遇到很多問(wèn)題.

3.2 典型方案分析

3.2.1 部分同步網(wǎng)絡(luò)分布式一致算法

(1)Paxos

Paxos 在n=2f+1 模型中,能夠容忍f個(gè)崩潰節(jié)點(diǎn),實(shí)現(xiàn)了基于消息傳遞的一致性算法.Paxos 中提出了主節(jié)點(diǎn)、備份節(jié)點(diǎn)的概念,其主要過(guò)程如下:

Paxos 允許多個(gè)主節(jié)點(diǎn)提議,并對(duì)主節(jié)點(diǎn)賦予不同的等級(jí),等級(jí)高的主節(jié)點(diǎn)的提議能夠打斷等級(jí)低的主節(jié)點(diǎn)提議,即使等級(jí)低的主節(jié)點(diǎn)提議已經(jīng)得到備份節(jié)點(diǎn)的承諾消息.Paxos 協(xié)議被用于分布式系統(tǒng)中數(shù)據(jù)庫(kù)的維護(hù),只能對(duì)崩潰節(jié)點(diǎn)容錯(cuò),不能對(duì)拜占庭節(jié)點(diǎn)實(shí)現(xiàn)容錯(cuò).

(2)PBFT

PBFT 的敵手模型為n=3f+ 1,網(wǎng)絡(luò)模型為部分同步網(wǎng)絡(luò).PBFT 算法中,存在一個(gè)主節(jié)點(diǎn)(primary)和其他的備份節(jié)點(diǎn)(replica),PBFT 共識(shí)機(jī)制主要包含兩部分:第一部分是分布式共識(shí)達(dá)成,在主節(jié)點(diǎn)正常工作時(shí),PBFT 通過(guò)預(yù)準(zhǔn)備(pre-prepare)、準(zhǔn)備(prepare)和承諾(commit)三個(gè)步驟完成共識(shí); 第二部分是視圖轉(zhuǎn)換(view-change),當(dāng)主節(jié)點(diǎn)出現(xiàn)問(wèn)題不能及時(shí)處理數(shù)據(jù)請(qǐng)求時(shí),其他備份節(jié)點(diǎn)發(fā)起視圖轉(zhuǎn)換,轉(zhuǎn)換成功后新的主節(jié)點(diǎn)開(kāi)始工作.主節(jié)點(diǎn)以輪轉(zhuǎn)(round robin)的方式交替更換.

PBFT 的分布式共識(shí)達(dá)成過(guò)程如下:

①請(qǐng)求(propose).客戶端(client)上傳請(qǐng)求消息m至網(wǎng)絡(luò)中的節(jié)點(diǎn),包括主節(jié)點(diǎn)和其他備份節(jié)點(diǎn).

②預(yù)準(zhǔn)備(pre-prepare).主節(jié)點(diǎn)收到客戶端上傳的請(qǐng)求消息m,賦予消息序列號(hào)s,計(jì)算得到預(yù)準(zhǔn)備消息(pre-prepare,H(m),s,v),其中H(·)是單向哈希函數(shù),v代表的是此時(shí)的視圖(view),視圖一般用于記錄主節(jié)點(diǎn)的更替,主節(jié)點(diǎn)發(fā)生更替時(shí),視圖隨之增加1.消息發(fā)送者節(jié)點(diǎn)在發(fā)送消息前需利用自身私鑰對(duì)消息實(shí)施數(shù)字簽名.主節(jié)點(diǎn)將預(yù)準(zhǔn)備消息發(fā)送給其他備份節(jié)點(diǎn).

③準(zhǔn)備(prepare).備份節(jié)點(diǎn)收到主節(jié)點(diǎn)的預(yù)準(zhǔn)備消息,驗(yàn)證H(m)的合法性,即對(duì)于視圖v和序列號(hào)s來(lái)說(shuō),備份節(jié)點(diǎn)先前并未收到其他消息.驗(yàn)證通過(guò)后,備份節(jié)點(diǎn)計(jì)算準(zhǔn)備消息(prepare,H(m),s,v)并將其在全網(wǎng)廣播.與此同時(shí),所有節(jié)點(diǎn)收集準(zhǔn)備消息,如果收集到的合法準(zhǔn)備消息數(shù)量大于等于2f+1(包含自身準(zhǔn)備消息)個(gè),則將其組成準(zhǔn)備憑證(prepared certificate).

④承諾(commit).如果在準(zhǔn)備階段中,節(jié)點(diǎn)收集到足夠的準(zhǔn)備消息并生成了準(zhǔn)備憑證,那么節(jié)點(diǎn)將計(jì)算承諾消息(commit,s,v)并廣播,將消息m放入到本地日志中.與此同時(shí)節(jié)點(diǎn)收集網(wǎng)絡(luò)中的承諾消息,如果收集到的合法承諾消息數(shù)量大于等于2f+1(包含自身承諾消息),那么將其組成承諾憑證(committed certificate),證明消息m完成最終承諾.

⑤答復(fù)(reply).備份節(jié)點(diǎn)和主節(jié)點(diǎn)中任意收集到足夠承諾消息并組成承諾憑證的節(jié)點(diǎn),將承諾憑證作為對(duì)消息m的答復(fù)發(fā)送給客戶端,客戶端確認(rèn)消息m的最終承諾.

PBFT 的分布式共識(shí)過(guò)程如圖1 所示:

圖1 PBFT 算法流程圖Figure 1 Process of PBFT algorithm

在PBFT 中,存在檢查點(diǎn)(checkpoint)機(jī)制,由于每個(gè)消息都被賦予了一定的序列號(hào),如消息m對(duì)應(yīng)的序列號(hào)為118,當(dāng)不少于2f+1 個(gè)節(jié)點(diǎn)組成消息m的承諾憑證,完成消息承諾之后,序列號(hào)118 成為當(dāng)前的穩(wěn)定檢查點(diǎn)(stable checkpoint).檢查點(diǎn)機(jī)制被用于實(shí)現(xiàn)存儲(chǔ)刪減,即當(dāng)歷史日志內(nèi)容過(guò)多時(shí),節(jié)點(diǎn)可以選擇清除穩(wěn)定檢查點(diǎn)之前的數(shù)據(jù),減少存儲(chǔ)成本.另外穩(wěn)定檢查點(diǎn)在PBFT 的視圖轉(zhuǎn)換中也起到了關(guān)鍵作用.

當(dāng)主節(jié)點(diǎn)(主節(jié)點(diǎn))超時(shí)無(wú)響應(yīng)或其他節(jié)點(diǎn)大多數(shù)認(rèn)為其存在問(wèn)題時(shí),會(huì)進(jìn)入視圖轉(zhuǎn)換過(guò)程.PBFT的視圖轉(zhuǎn)換過(guò)程如下:

①視圖轉(zhuǎn)換信息廣播.備份節(jié)點(diǎn)i的當(dāng)前視圖v,當(dāng)前穩(wěn)定檢查點(diǎn)S?,對(duì)于穩(wěn)定檢查點(diǎn)S?的憑證C(即2f+1 個(gè)節(jié)點(diǎn)的有效承諾憑證).U為節(jié)點(diǎn)i當(dāng)前視圖下,序列號(hào)大于S?,且已經(jīng)形成準(zhǔn)備憑證的消息集合.節(jié)點(diǎn)i計(jì)算視圖轉(zhuǎn)換消息:vci:(view-change,v+1,S?,C,U,i),并將其在全網(wǎng)廣播.

②視圖轉(zhuǎn)換確認(rèn).備份節(jié)點(diǎn)收集對(duì)視圖v+1 的轉(zhuǎn)換消息并驗(yàn)證其合法性,驗(yàn)證通過(guò)后計(jì)算視圖轉(zhuǎn)換確認(rèn)消息vcai:(view-change-ack,v+1,i,j,H(vcj)),其中i是當(dāng)前備份節(jié)點(diǎn),j是發(fā)送視圖轉(zhuǎn)換消息vcj的節(jié)點(diǎn),H(vcj)是視圖轉(zhuǎn)換消息的摘要.vcai消息相當(dāng)于對(duì)每個(gè)節(jié)點(diǎn)發(fā)出的視圖轉(zhuǎn)換消息確認(rèn).備份節(jié)點(diǎn)將消息vcai直接發(fā)送給視圖v+1 對(duì)應(yīng)的新的主節(jié)點(diǎn).視圖v+1 的主節(jié)點(diǎn)由輪轉(zhuǎn)方式?jīng)Q定.

③新視圖廣播.對(duì)于每個(gè)視圖轉(zhuǎn)換消息,如節(jié)點(diǎn)j的消息vcj,如果vcj合法,則其他節(jié)點(diǎn)將會(huì)向主節(jié)點(diǎn)發(fā)送對(duì)vcj的視圖轉(zhuǎn)換確認(rèn)消息,因此,當(dāng)主節(jié)點(diǎn)收集到2f?1 個(gè)對(duì)vcj的視圖轉(zhuǎn)換確認(rèn)消息,則可認(rèn)為vcj有效,并將vcj和其對(duì)應(yīng)的視圖轉(zhuǎn)換確認(rèn)消息放入到集合S中.主節(jié)點(diǎn)收集其他節(jié)點(diǎn)的有效視圖轉(zhuǎn)換消息,如果S中消息不少于2f個(gè),則主節(jié)點(diǎn)計(jì)算新視圖消息nv:(new-view,v+1,S,U?).其中U?包括當(dāng)前的穩(wěn)定檢查點(diǎn)和穩(wěn)定檢查點(diǎn)之后序列號(hào)最小的預(yù)準(zhǔn)備消息.

PBFT 中節(jié)點(diǎn)之間采用消息認(rèn)證碼(message authenticated codes,MAC)[63]實(shí)現(xiàn)身份認(rèn)證.MAC是指在消息傳輸時(shí),通過(guò)特定哈希函數(shù)計(jì)算消息摘要,將消息摘要和消息一并傳輸.任意兩個(gè)節(jié)點(diǎn)之間存在一對(duì)會(huì)話密鑰來(lái)計(jì)算消息的MAC.會(huì)話密鑰可以通過(guò)密鑰交換協(xié)議來(lái)產(chǎn)生并實(shí)現(xiàn)動(dòng)態(tài)更換.PBFT 實(shí)現(xiàn)了狀態(tài)機(jī)復(fù)制的一致性和活性,在協(xié)議正常運(yùn)行時(shí),通信復(fù)雜度為O(n3).在視圖轉(zhuǎn)換時(shí),通信復(fù)雜度為O(n4).

(3)Hot-Stuff

Hot-Stuff 算法由Abraham、Gueta和Malkhi[11]提出,它對(duì)PBFT 做出改進(jìn).Hot-Stuff 網(wǎng)絡(luò)模型為部分同步網(wǎng)絡(luò),敵手模型為n=3f+1.其采用并行流水線處理提議,相當(dāng)于將PBFT 中的準(zhǔn)備和承諾階段合并成一個(gè)階段.Hot-Stuff 算法流程如圖2所示.

圖2 Hot-Stuff 算法流程圖Figure 2 Process of Hot-Stuff algorithm

a(1)是指節(jié)點(diǎn)a在第1 輪的提議,當(dāng)節(jié)點(diǎn)a收集到對(duì)a(1)的準(zhǔn)備消息大于等于2f+1 個(gè)時(shí),節(jié)點(diǎn)a便組成了對(duì)a(1)的準(zhǔn)備憑證CC(a(1)),并將CC(a(1))與第二輪的提議a(2)組成第二輪的消息發(fā)送給其他節(jié)點(diǎn).如果其他節(jié)點(diǎn)對(duì)第二輪的消息投票大于等于2f+1 個(gè),相當(dāng)于完成了如下兩個(gè)過(guò)程:第一是確認(rèn)了a(2)的提議,能夠組成對(duì)于a(2)的準(zhǔn)備憑證CC(a(2)); 第二是確認(rèn)了CC(a(1)),即完成了提議a(1)的最終承諾.對(duì)于準(zhǔn)備和承諾的并行流水線處理能夠很大程度上提升內(nèi)部共識(shí)的效率.

與此同時(shí),Hot-Stuff 采用線性視圖轉(zhuǎn)換(linear view change,LVC),降低了視圖轉(zhuǎn)換中的通信復(fù)雜度.在PBFT 中,當(dāng)視圖轉(zhuǎn)換發(fā)生時(shí),新的領(lǐng)導(dǎo)者需要廣播目前的穩(wěn)定檢查點(diǎn),并且提供2f+1 個(gè)節(jié)點(diǎn)的承諾憑證,證明檢查點(diǎn)的合法性,通信復(fù)雜度為O(n4).而在LVC 中,新的領(lǐng)導(dǎo)者只需廣播1 個(gè)承諾憑證.其他節(jié)點(diǎn)只有在收到比本地穩(wěn)定檢查點(diǎn)更高的檢查點(diǎn)時(shí),才判定新領(lǐng)導(dǎo)者的合法性.在這種情況下,如果新的領(lǐng)導(dǎo)者隱藏了更高的檢查點(diǎn),不會(huì)影響到協(xié)議的安全性,只會(huì)讓其受到懲罰.

對(duì)于每個(gè)消息,如對(duì)提議a(1),PBFT 中使用完整的2f+1 個(gè)簽名作為其準(zhǔn)備憑證CC(a(1)),而Hot-Stuff 中使用門限簽名技術(shù),將一個(gè)門限簽名作為準(zhǔn)備憑證CC(a(1)),領(lǐng)導(dǎo)者作為簽名的收集者完成簽名份額的收集和門限簽名的重建.綜合LVC和門限簽名技術(shù),Hot-Stuff 最終每輪的通信復(fù)雜度為O(n2).

Hot-Stuff 利用門限簽名、并行流水線處理和線性視圖轉(zhuǎn)換等技術(shù),極大提高了分布式一致性算法的效率.Abraham 等人[64]提出了同步網(wǎng)絡(luò)模型下的Hot-Stuff 協(xié)議,實(shí)現(xiàn)了快速響應(yīng)特性.交易確認(rèn)時(shí)延為2?+O(δ),?表示網(wǎng)絡(luò)時(shí)延上限,δ表示網(wǎng)絡(luò)真實(shí)時(shí)延.

(4)SBFT

可擴(kuò)展拜占庭容錯(cuò)協(xié)議(scalable Byzantine fault tolerance,SBFT)由Golan-Gueta 等人[12]提出.SBFT 主要解決拜占庭容錯(cuò)協(xié)議在應(yīng)用到區(qū)塊鏈中的去中心化和擴(kuò)容問(wèn)題,SBFT 的敵手模型n=3f+1,能夠允許200 多個(gè)節(jié)點(diǎn)同時(shí)完成共識(shí).SBFT 利用領(lǐng)導(dǎo)者作為信息、簽名的收集者,采用門限簽名降低通信復(fù)雜度.在PBFT 中,每一輪的投票,節(jié)點(diǎn)需要向網(wǎng)絡(luò)中其他節(jié)點(diǎn)廣播投票,并且收集其他節(jié)點(diǎn)的投票,而SBFT 利用領(lǐng)導(dǎo)者收集每一輪投票,收集到的簽名數(shù)量達(dá)到門限要求以后,領(lǐng)導(dǎo)者便能恢復(fù)總的門限簽名,從而將通信復(fù)雜度從O(n3)降低為O(n2).

3.2.2 異步網(wǎng)絡(luò)分布式一致性算法

Fischer、Lynch和Paterson[65]提出了FLP 不可能定理,在網(wǎng)絡(luò)可靠，但允許節(jié)點(diǎn)失效的最小化異步模型系統(tǒng)中，不存在一個(gè)可以解決一致性問(wèn)題的確定性共識(shí)機(jī)制.Rabin[66]和Ben-Or[67]利用所有節(jié)點(diǎn)可見(jiàn)的隨機(jī)數(shù)發(fā)生器實(shí)現(xiàn)了異步網(wǎng)絡(luò)中的分布式一致性協(xié)議,敵手對(duì)于隨機(jī)數(shù)發(fā)生器生成的隨機(jī)數(shù)是不可預(yù)知的,隨機(jī)數(shù)發(fā)生器成為了異步網(wǎng)絡(luò)共識(shí)中常用的工具.

Cachin、Kursawe和Shoup[68]在2005年提出了異步二元拜占庭一致算法(asynchronous binary Byzantine agreement,ABBA),在異步網(wǎng)絡(luò)中實(shí)現(xiàn)分布式一致算法.ABBA 正常運(yùn)行之前需要建立初始化設(shè)置,由可信中心參與,對(duì)協(xié)議和數(shù)據(jù)初始化.初始化階段過(guò)后,利用RSA 門限簽名生成每一輪的隨機(jī)數(shù),作為不可預(yù)知的隨機(jī)數(shù)發(fā)生器.ABBA 算法主要包括預(yù)處理、預(yù)投票、主投票、決策檢驗(yàn)和隨機(jī)數(shù)生成等步驟.ABBA 敵手模型為n=3f+1,通信復(fù)雜度為O(n3).

Veronese 等人[13]提出了MinBFT,在異步網(wǎng)絡(luò)中實(shí)現(xiàn)共識(shí),敵手模型為n=2f+1.MinBFT 主要利用了唯一連續(xù)標(biāo)識(shí)符生成器(unique sequential identifier generator,USIG)作為可信計(jì)數(shù)器,網(wǎng)絡(luò)中節(jié)點(diǎn)均能獲得USIG 的信息.MinBFT 采用與PBFT 類似的流程,網(wǎng)絡(luò)中存在主節(jié)點(diǎn)和備份節(jié)點(diǎn),主節(jié)點(diǎn)即領(lǐng)導(dǎo)者利用USIG 為每一輪提議值分配序列號(hào),序列號(hào)與提議值一一對(duì)應(yīng).由于USIG 產(chǎn)生的序列號(hào)是單調(diào)增加的,且每個(gè)節(jié)點(diǎn)獲得的數(shù)值都保證相同,保證領(lǐng)導(dǎo)者不能對(duì)提議值模棱兩可,即保證領(lǐng)導(dǎo)者不能將一個(gè)序列號(hào)分配給不同的提議值.USIG 作為可信計(jì)數(shù)器確保了每個(gè)序列號(hào)只能對(duì)應(yīng)唯一的提議值,這也是敵手模型為n=2f+1 的原因.MinBFT 的主要步驟包括客戶端請(qǐng)求、準(zhǔn)備、承諾和答復(fù)階段.

Miller 等人[14]提出了蜜獾拜占庭容錯(cuò)協(xié)議(Honey Badger BFT),不需要任何時(shí)間假設(shè)實(shí)現(xiàn)異步網(wǎng)絡(luò)中的分布式一致性共識(shí).該協(xié)議對(duì)文獻(xiàn)[68]提出的ABBA 作出改進(jìn),提出了異步共同子集(asynchronous common subset,ACS),ACS 包括可靠廣播(reliable broadcast,RBC)和異步二元一致算法(asynchronous binary agreement)兩個(gè)階段.Honey Badger BFT 通過(guò)門限加密的方式解決了交易審查(transaction censorship)問(wèn)題.

假設(shè)網(wǎng)絡(luò)中共n個(gè)節(jié)點(diǎn),每一輪共識(shí)就大小為B的數(shù)據(jù)運(yùn)行共識(shí)機(jī)制.Honey Badger BFT 算法的主要過(guò)程如下:

①節(jié)點(diǎn)收集交易.每個(gè)節(jié)點(diǎn)收集交易數(shù)據(jù),放到自身的交易數(shù)據(jù)緩沖區(qū),每一輪共識(shí)運(yùn)行之前,節(jié)點(diǎn)取出緩沖區(qū)中的前B/n個(gè)交易.②交易數(shù)據(jù)門限加密.節(jié)點(diǎn)對(duì)前B/n個(gè)交易門限加密,生成每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的加密后的數(shù)據(jù).③RBC 廣播.節(jié)點(diǎn)將門限加密后的密文數(shù)據(jù)利用RBC 廣播.④ABA 共識(shí).領(lǐng)導(dǎo)者收集節(jié)點(diǎn)發(fā)送的加密后的交易數(shù)據(jù),組成交易集密文,就交易集發(fā)起ABA 共識(shí).⑤交易數(shù)據(jù)門限解密.ABA 共識(shí)完成,即對(duì)交易集密文數(shù)據(jù)達(dá)成一致,此時(shí)節(jié)點(diǎn)運(yùn)行門限解密算法,只要至少f+1 個(gè)節(jié)點(diǎn)完成解密,即可恢復(fù)交易集中的交易明文數(shù)據(jù),完成交易確認(rèn).

Honey Badger BFT 敵手模型為n=3f+1,防止了交易審查,實(shí)現(xiàn)了網(wǎng)絡(luò)性能和吞吐量的提升.

驗(yàn)證的異步拜占庭一致算法(validated asynchronous Byzantine agreement,VABA)由Abraham、Malkhi和Spiegelman[52]提出.在異步網(wǎng)絡(luò)環(huán)境下,VABA 實(shí)現(xiàn)了多值拜占庭一致算法,敵手模型為n=3f+1.VABA 基于隨機(jī)預(yù)言模型,在每次共識(shí)過(guò)程中,采用多個(gè)并行的領(lǐng)導(dǎo)者提議,從中隨機(jī)選取一個(gè)作為最終結(jié)果.VABA 采用門限簽名等技術(shù)使每一輪的通信復(fù)雜度為O(n2).

3.2.3 同步網(wǎng)絡(luò)分布性一致算法

Bazzi[69]在2000年提出了同步拜占庭“法定人數(shù)(quorum)” 系統(tǒng),在同步網(wǎng)絡(luò)模型中,給出了拜占庭法定人數(shù)系統(tǒng)的定義.假設(shè)協(xié)議中敵手?jǐn)?shù)量為f,在一輪中就某個(gè)數(shù)值v運(yùn)行分布式共識(shí)達(dá)成算法,敵手為了擾亂協(xié)議執(zhí)行,可能對(duì)數(shù)值v′投票.此時(shí)協(xié)議需要規(guī)定對(duì)某個(gè)數(shù)值的投票數(shù)必須達(dá)到某個(gè)法定人數(shù),如2f+1(假設(shè)敵手模型為n=3f+1),才能確保一輪共識(shí)運(yùn)行完畢后最多對(duì)一個(gè)特定值達(dá)成共識(shí).因?yàn)榧僭O(shè)v′=v,且v′跟v同樣獲得了2f+1 的投票,此時(shí)對(duì)于二者的投票必然存在交集,其人數(shù)至少為f+1,即這f+1 個(gè)節(jié)點(diǎn)同時(shí)對(duì)v′和v投票.由于敵手個(gè)數(shù)最多為f,所以此f+1 個(gè)節(jié)點(diǎn)至少包含一個(gè)誠(chéng)實(shí)節(jié)點(diǎn),這與誠(chéng)實(shí)節(jié)點(diǎn)不能模棱兩可的假設(shè)相矛盾.拜占庭法定人數(shù)系統(tǒng)在同步網(wǎng)絡(luò)環(huán)境中達(dá)成了共識(shí).

Liu 等人[53]研究了同步網(wǎng)絡(luò)、認(rèn)證信道條件下的拜占庭共識(shí),提出了XFT.XFT 能夠同時(shí)容忍崩潰節(jié)點(diǎn)和拜占庭錯(cuò)誤節(jié)點(diǎn),敵手模型為n=2f+1.XFT 在n和f數(shù)值很小的時(shí)候運(yùn)行較為高效,但隨著節(jié)點(diǎn)和錯(cuò)誤節(jié)點(diǎn)增加,其性能嚴(yán)重下滑.

Abraham 等人[54]提出高效同步拜占庭共識(shí)(efficient synchronous Byzantine consensus,ESBC),在同步網(wǎng)絡(luò)和認(rèn)證信道中,其敵手模型為n=2f+1.該協(xié)議的設(shè)計(jì)借鑒了Paxos 的思路,每個(gè)時(shí)期有一個(gè)領(lǐng)導(dǎo)者,領(lǐng)導(dǎo)者在處理新提議前,必須先處理上個(gè)領(lǐng)導(dǎo)者未處理完的提議.該協(xié)議利用網(wǎng)絡(luò)同步假設(shè)抵抗了拜占庭節(jié)點(diǎn)的攻擊,每一輪提議經(jīng)過(guò)四步便可達(dá)成共識(shí).

Kiayias和Russell[70]提出Ouroboros-BFT,在同步網(wǎng)絡(luò)中,其敵手模型為n=3f+1.在樂(lè)觀情況下,交易能夠以網(wǎng)絡(luò)實(shí)際速度得到確認(rèn),即實(shí)現(xiàn)交易快速響應(yīng).上傳交易的客戶端能夠得到交易確認(rèn)的證明.即使在網(wǎng)絡(luò)情況較差,出現(xiàn)網(wǎng)絡(luò)隔離時(shí),Ouroboros-BFT 仍然能夠確保系統(tǒng)的安全性.

Malkhi、Nayak和Ren 等人[71]提出了Flexible BFT,在同步網(wǎng)絡(luò)中實(shí)現(xiàn)了狀態(tài)機(jī)復(fù)制.Flexible BFT 只有在承諾步驟要求網(wǎng)絡(luò)是同步的,即只在承諾步驟中使用網(wǎng)絡(luò)延時(shí)參數(shù),在其他步驟不需要網(wǎng)絡(luò)同步的假設(shè).

3.3 綜合分析

經(jīng)典分布式共識(shí)主要研究的是在授權(quán)網(wǎng)絡(luò)中實(shí)現(xiàn)狀態(tài)機(jī)復(fù)制,并且保證協(xié)議的安全性和活性.從網(wǎng)絡(luò)模型方面來(lái)說(shuō),最為典型的是部分同步網(wǎng)絡(luò),網(wǎng)絡(luò)中消息能夠在一定的時(shí)間上限內(nèi)到達(dá)所有誠(chéng)實(shí)節(jié)點(diǎn),最貼近現(xiàn)實(shí)網(wǎng)絡(luò),也是目前區(qū)塊鏈協(xié)議經(jīng)常采用的網(wǎng)絡(luò)模型.從容錯(cuò)角度來(lái)看,Paxos 協(xié)議只能容忍崩潰節(jié)點(diǎn),而PBFT 等拜占庭容錯(cuò)協(xié)議能夠容忍網(wǎng)絡(luò)中的拜占庭節(jié)點(diǎn),拜占庭節(jié)點(diǎn)可以是崩潰節(jié)點(diǎn),也可以是被敵手控制的惡意節(jié)點(diǎn),因此拜占庭容錯(cuò)共識(shí)更符合實(shí)際網(wǎng)絡(luò),在區(qū)塊鏈共識(shí)中的應(yīng)用也更為廣泛.經(jīng)典分布式共識(shí)的研究方向主要有以下三點(diǎn):

第一,高效的輪內(nèi)投票算法.經(jīng)典分布式共識(shí)機(jī)制一般采用多輪投票的方式來(lái)對(duì)某個(gè)值達(dá)成共識(shí),如何降低每一輪的通信復(fù)雜度,提高算法的執(zhí)行效率是未來(lái)的研究熱點(diǎn),如采用并行流水線技術(shù)并行處理每一輪提議的數(shù)值、采用門限簽名等技術(shù)降低節(jié)點(diǎn)間的通信復(fù)雜度等[72];

第二,更強(qiáng)的容錯(cuò)能力.經(jīng)典分布式共識(shí)機(jī)制需要假設(shè)網(wǎng)絡(luò)中敵手?jǐn)?shù)量不超過(guò)特定比例,當(dāng)網(wǎng)絡(luò)中敵手?jǐn)?shù)量超過(guò)該比例時(shí),如何有效檢測(cè)以及恢復(fù).如何借助其他可信硬件等使網(wǎng)絡(luò)的整體容錯(cuò)能力更強(qiáng);

第三,高效的視圖轉(zhuǎn)換.視圖轉(zhuǎn)換是經(jīng)典分布式共識(shí)機(jī)制需要解決的重要問(wèn)題,當(dāng)委員會(huì)領(lǐng)導(dǎo)者為惡意節(jié)點(diǎn)或消極怠工時(shí),需要一定的機(jī)制選舉新的領(lǐng)導(dǎo)者,在新領(lǐng)導(dǎo)者接任的過(guò)程中,如何高效地獲取其他節(jié)點(diǎn)當(dāng)前的狀態(tài)、處理之前未處理完的提議是需要研究的問(wèn)題[73].

4 授權(quán)共識(shí)機(jī)制

4.1 概念

授權(quán)共識(shí)機(jī)制是指在授權(quán)網(wǎng)絡(luò)中,節(jié)點(diǎn)首先經(jīng)過(guò)身份認(rèn)證加入網(wǎng)絡(luò)中,然后在節(jié)點(diǎn)之間運(yùn)行某種分布式一致性算法,實(shí)現(xiàn)狀態(tài)機(jī)復(fù)制,對(duì)數(shù)據(jù)達(dá)成共識(shí),進(jìn)而生成和維護(hù)授權(quán)網(wǎng)絡(luò)內(nèi)部的區(qū)塊鏈.授權(quán)共識(shí)機(jī)制產(chǎn)生的區(qū)塊鏈不同于比特幣之類的“公鏈”,節(jié)點(diǎn)只有在獲得身份認(rèn)可之后才能加入授權(quán)網(wǎng)絡(luò)中,進(jìn)入到授權(quán)網(wǎng)絡(luò)內(nèi)部,從而完成共識(shí)過(guò)程.

4.2 典型方案

(1)Hyperledger

超級(jí)賬本(Hyperledger)是Linux 基金會(huì)發(fā)起的開(kāi)源區(qū)塊鏈項(xiàng)目,意在提供企業(yè)級(jí)的開(kāi)源分布式賬本框架和源代碼.Hyperledger 包括八大項(xiàng)目,其中Hyperledger Fabric 是基于社區(qū)的項(xiàng)目,為區(qū)塊鏈的應(yīng)用提供支持框架.Cachin[15]提出了Hyperledger Fabric 的基本框架.Androulaki 等人[16]對(duì)Hyperledger Fabric 進(jìn)一步完善.Hyperledger Fabric 將智能合約稱為鏈碼(chaincode),鏈碼是整個(gè)分布式應(yīng)用平臺(tái)的核心部分,可以由不可信的開(kāi)發(fā)者開(kāi)發(fā).系統(tǒng)鏈碼用來(lái)配置整個(gè)區(qū)塊鏈系統(tǒng)的安全參數(shù).

Hyperledger Fabric 中,主要有以下角色:①客戶端(clients).客戶端主要產(chǎn)生交易并上傳至網(wǎng)絡(luò),在鏈碼執(zhí)行過(guò)程中起到一定的輔助作用.②普通節(jié)點(diǎn)(peers).系統(tǒng)中所有節(jié)點(diǎn)都需要完成身份認(rèn)證,Hyperledger Fabric 采用成員服務(wù)提供商(membership service provider,MSP)來(lái)為每個(gè)節(jié)點(diǎn)授予身份.③背書節(jié)點(diǎn)(endorsers).背書節(jié)點(diǎn)是指在系統(tǒng)中負(fù)責(zé)執(zhí)行鏈碼的節(jié)點(diǎn),每個(gè)交易根據(jù)鏈碼都會(huì)有一組背書節(jié)點(diǎn)負(fù)責(zé)其執(zhí)行.④排序節(jié)點(diǎn)(orderers).排序節(jié)點(diǎn)負(fù)責(zé)對(duì)已執(zhí)行鏈碼運(yùn)行分布式一致性算法,對(duì)交易排序,并將其寫入到區(qū)塊中,形成公共賬本.

Hyperledger Fabric 共識(shí)過(guò)程如下:①執(zhí)行(execute).客戶端首先將交易發(fā)送至背書節(jié)點(diǎn),背書節(jié)點(diǎn)執(zhí)行對(duì)應(yīng)的鏈碼,并記錄執(zhí)行后的結(jié)果.②排序(order).鏈碼在執(zhí)行之后,進(jìn)入排序階段.排序者內(nèi)部運(yùn)行分布式一致性算法來(lái)將已執(zhí)行交易排序,輸出總交易序列,并將其打包寫入到區(qū)塊中.排序者將以上信息廣播給所有節(jié)點(diǎn).Hyperledger Fabric 運(yùn)用拜占庭容錯(cuò)一致性算法實(shí)現(xiàn)對(duì)交易的排序和區(qū)塊的共識(shí).③驗(yàn)證(validate).所有收到新區(qū)塊的節(jié)點(diǎn)驗(yàn)證其中交易的正確性,驗(yàn)證背書節(jié)點(diǎn)對(duì)交易的執(zhí)行是否一致,驗(yàn)證通過(guò)后將新區(qū)塊更新到本地區(qū)塊鏈.

Hyperledger Fabric 采用的模塊化的設(shè)計(jì)思想將智能合約的執(zhí)行、排序和驗(yàn)證分離開(kāi)來(lái),節(jié)點(diǎn)在處理合約時(shí)更加具有針對(duì)性和高效性.

(2)DFINITY

DFINITY 由Hanke、Movahedi和Williams[17]提出.DFINITY 網(wǎng)絡(luò)模型為部分同步網(wǎng)絡(luò),敵手模型為n=2f+1.DFINITY 采用模塊化的設(shè)計(jì)思想,將整個(gè)共識(shí)機(jī)制分為身份層、隨機(jī)信標(biāo)層、區(qū)塊鏈層、公示層.DFINITY 協(xié)議以時(shí)期為單位運(yùn)行,提出了“門限轉(zhuǎn)發(fā)” 算法,將所有參與節(jié)點(diǎn)分為m個(gè)不同的組,每一組相當(dāng)于委員會(huì),每個(gè)時(shí)期由一個(gè)隨機(jī)的委員會(huì)負(fù)責(zé)交易處理、共識(shí)運(yùn)行,而在時(shí)期結(jié)束時(shí),委員會(huì)運(yùn)行隨機(jī)數(shù)生成算法,利用BLS 門限簽名和可驗(yàn)證隨機(jī)函數(shù)生成隨機(jī)數(shù),根據(jù)隨機(jī)數(shù)決定下一時(shí)期的由哪個(gè)組擔(dān)任委員會(huì).DFINITY 共識(shí)機(jī)制如圖3所示.

DFINITY 共識(shí)機(jī)制具體運(yùn)行流程如下:

①節(jié)點(diǎn)身份確認(rèn).DFINITY 是授權(quán)共識(shí),因此所有參與共識(shí)的節(jié)點(diǎn)需要完成身份注冊(cè),注冊(cè)人需要抵押一部分資產(chǎn),若在參與協(xié)議期間,節(jié)點(diǎn)出現(xiàn)惡意操作,則扣除其抵押資產(chǎn).

②協(xié)議初始化.根據(jù)創(chuàng)世區(qū)塊中隨機(jī)數(shù)的設(shè)定,DFINITY 的節(jié)點(diǎn)被隨機(jī)分配到不同委員會(huì),每個(gè)委員會(huì)內(nèi)部運(yùn)行分布式密鑰生成算法(distributed key generation,DKG)[74]生成每個(gè)成員的公私鑰對(duì)和整個(gè)委員會(huì)的總驗(yàn)證公鑰,用于BLS 門限簽名算法[75]對(duì)簽名的計(jì)算和驗(yàn)證.DKG 算法由多個(gè)并行的可驗(yàn)證秘密分享算法(verifiable secret share,VSS)[76]構(gòu)成.根據(jù)創(chuàng)世區(qū)塊中的隨機(jī)數(shù)選擇初始委員會(huì).

③隨機(jī)數(shù)生成.當(dāng)前委員會(huì)內(nèi)部成員運(yùn)行(t,n)-BLS 門限簽名算法,t是指門限值,n是委員會(huì)內(nèi)成員個(gè)數(shù),令n=2t+1,當(dāng)敵手?jǐn)?shù)量f小于t時(shí),可以保證能夠順利恢復(fù)BLS 門限簽名.委員會(huì)成員將上一輪隨機(jī)數(shù)作為消息并產(chǎn)生BLS 簽名,任意節(jié)點(diǎn)如果收集到t個(gè)有效簽名份額,便能利用BLS 門限簽名的簽名重建函數(shù)恢復(fù)總簽名.BLS 門限簽名的唯一性保證了所有節(jié)點(diǎn)恢復(fù)出的總簽名完全一致,不會(huì)因?yàn)檫x擇的簽名份額集合不同而導(dǎo)致最終簽名的不同.將總簽名作為可驗(yàn)證隨機(jī)函數(shù)(verifiable random function,VRF)[77]的輸入,運(yùn)行哈希運(yùn)算得到本輪的隨機(jī)數(shù)ξr.

④區(qū)塊提議和公示.委員會(huì)成員將本輪隨機(jī)數(shù)ξr作為偽隨機(jī)數(shù)生成器(pseudo-random number generator,PRG)[78]的種子,為每個(gè)節(jié)點(diǎn)生成對(duì)應(yīng)的隨機(jī)數(shù).然后將每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的隨機(jī)數(shù)放入到偽隨機(jī)置換函數(shù)(pseudo-random permutaions,PRP)[79]中,確定每個(gè)成員在委員會(huì)中的排序等級(jí).DFINITY允許委員會(huì)中的每個(gè)成員作出區(qū)塊提議,但排序等級(jí)高的成員提出的區(qū)塊具有更高的“重量”.類似于比特幣采取的“最長(zhǎng)鏈” 原則,DFINITY 采用“最重鏈” 原則來(lái)處理區(qū)塊鏈的分叉.為了防止自私挖礦攻擊,DFINITY 采用區(qū)塊公示機(jī)制,只有在一定時(shí)間范圍內(nèi)公開(kāi)的區(qū)塊才合法.在計(jì)算區(qū)塊鏈“重量”時(shí),合法區(qū)塊才被計(jì)算入內(nèi).

⑤區(qū)塊最終確認(rèn).區(qū)塊最終確認(rèn)是指網(wǎng)絡(luò)中的所有節(jié)點(diǎn)在觀察到已公示區(qū)塊達(dá)到一定的深度時(shí),將其確定為最終確認(rèn)區(qū)塊,其中的交易也完成最終確認(rèn).

⑥下一任委員會(huì)工作.在當(dāng)前時(shí)期結(jié)束后,根據(jù)本時(shí)期隨機(jī)數(shù)ξr隨機(jī)選取下一任委員會(huì).

DFINITY 利用門限簽名實(shí)現(xiàn)了抗偏置隨機(jī)數(shù)的生成,并利用隨機(jī)數(shù)隨機(jī)選取委員會(huì)工作.與此同時(shí),DFINITY 加入的區(qū)塊公示步驟有效防止了自私挖礦攻擊和無(wú)利害關(guān)系攻擊.

圖3 DFINITY 算法流程圖Figure 3 Process of DFINITY algorithm

(3)PaLa

PaLa 由Chan、Pass和Shi[18]提出,PaLa 實(shí)現(xiàn)了授權(quán)網(wǎng)絡(luò)中的快速共識(shí).PaLa 的網(wǎng)絡(luò)模型為部分同步網(wǎng)絡(luò),敵手模型是n=3f+1.

PaLa 主要在兩方面對(duì)授權(quán)共識(shí)作出改進(jìn),一方面是對(duì)拜占庭容錯(cuò)協(xié)議作出改進(jìn),在PBFT 中,對(duì)每個(gè)區(qū)塊需要3 個(gè)階段的投票和節(jié)點(diǎn)之間的信息交互,而PaLa 利用并行流水線的方式處理對(duì)區(qū)塊的投票.如果區(qū)塊Br首先被提出,經(jīng)過(guò)一輪投票后得到超過(guò)2/3 的票,則區(qū)塊Br提議被確認(rèn),在下一輪中,區(qū)塊Br+1被提出,此輪的投票包括對(duì)區(qū)塊Br的最終確認(rèn)票和對(duì)區(qū)塊Br+1的公示票,如果此輪的得票數(shù)超過(guò)2/3,那么認(rèn)為區(qū)塊Br被最終確認(rèn),區(qū)塊Br+1提議被確認(rèn).并行流水線的處理方法能夠在一定程度上提升委員會(huì)共識(shí)的效率.

另外一方面,PaLa 改進(jìn)了了委員會(huì)重配置的方式.在PaLa 中,每個(gè)委員會(huì)包含兩個(gè)子委員會(huì)(C0,C1).在投票時(shí),需要每個(gè)子委員會(huì)都有超過(guò)2/3 的成員投票才代表投票通過(guò).在委員會(huì)重配置時(shí),委員會(huì)由(C0,C1)切換到(C1,C2),只有其中一個(gè)子委員會(huì)發(fā)生變動(dòng).這樣的重配置方式既能保證充分的安全性,又能確保在委員會(huì)重配置期間,協(xié)議處理交易的可持續(xù)性.

PaLa 利用并行流水線的方式,提高了區(qū)塊處理的效率,采用子委員會(huì)滑窗式的重配置方式,能夠保證重配置期間交易處理的可持續(xù)性.

4.3 綜合分析

授權(quán)共識(shí)機(jī)制中的所有節(jié)點(diǎn)在參與共識(shí)前,必須要經(jīng)過(guò)身份注冊(cè).授權(quán)共識(shí)主要適用于企業(yè)、組織之間的聯(lián)盟等,在聯(lián)盟節(jié)點(diǎn)參與共識(shí)的情況下,能夠?qū)崿F(xiàn)較高的交易吞吐率.授權(quán)共識(shí)中,網(wǎng)絡(luò)處理交易的性能受到參與節(jié)點(diǎn)計(jì)算能力的影響較大.目前,由于授權(quán)共識(shí)的應(yīng)用場(chǎng)景大多為聯(lián)盟之間的數(shù)據(jù)處理和存儲(chǔ),授權(quán)共識(shí)需要考慮智能合約的處理問(wèn)題,因此授權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)分工的明確化和數(shù)據(jù)處理的模塊化顯得越來(lái)越重要.

5 基于工作量證明的共識(shí)機(jī)制

5.1 概念

工作量證明最早被用來(lái)防止垃圾郵件,由Dwork和Naor[80]在1992年提出.郵件在被發(fā)送之前,必須要求郵件發(fā)送方完成一定量的計(jì)算,如找到某個(gè)特定數(shù)學(xué)難題的解答.Back 在1997年提出,并在2002年正式發(fā)表了Hashcash[81],對(duì)工作量證明作出了改進(jìn),利用單向哈希函數(shù)實(shí)現(xiàn)工作量證明,即找到哈希函數(shù)原像才能完成工作量證明的過(guò)程.比特幣的出現(xiàn),將工作量證明運(yùn)用到非授權(quán)網(wǎng)絡(luò)的共識(shí)中,主要用來(lái)防止敵手制造假身份發(fā)動(dòng)女巫攻擊.

5.2 典型方案分析

(1)比特幣

基于工作量證明的共識(shí)機(jī)制最典型的代表是比特幣.在比特幣區(qū)塊鏈系統(tǒng)中,用戶可以上傳自身的交易,交易的實(shí)質(zhì)是將一個(gè)賬戶中的比特幣轉(zhuǎn)移到另外賬戶中,一個(gè)交易可能存在多個(gè)輸入和多個(gè)輸出.合法交易被打包放到區(qū)塊中,區(qū)塊最大為1MB(在實(shí)施隔離見(jiàn)證[82]之后,區(qū)塊有適度增大).區(qū)塊包括區(qū)塊頭和區(qū)塊體兩部分,區(qū)塊頭主要包括指向上個(gè)區(qū)塊的哈希值、交易默克爾樹(shù)樹(shù)根值、時(shí)間戳和隨機(jī)數(shù)等,區(qū)塊體主要包括產(chǎn)生的交易.

在比特幣中,每個(gè)區(qū)塊的生成者,即上文提到的出塊者,會(huì)得到一定數(shù)量的比特幣獎(jiǎng)勵(lì)(目前為12.5 BTC),因此節(jié)點(diǎn)為了成為出塊者獲得收益而持續(xù)執(zhí)行哈希運(yùn)算,以期尋找到工作量證明,這一過(guò)程也被稱為“挖礦”,而尋找工作量證明的節(jié)點(diǎn)被稱為“礦工”.比特幣中,每隔大約10 分鐘產(chǎn)生一個(gè)區(qū)塊,比特幣的區(qū)塊間隔時(shí)間跟比特幣的安全性緊密相關(guān),而區(qū)塊間隔跟當(dāng)前挖礦難度相關(guān).忽略與共識(shí)無(wú)關(guān)的細(xì)節(jié),簡(jiǎn)化的比特幣的共識(shí)流程如下:

①節(jié)點(diǎn)獲取挖礦難度、交易信息.比特幣中,節(jié)點(diǎn)能夠自由加入、退出網(wǎng)絡(luò),不需要完成身份注冊(cè).節(jié)點(diǎn)在挖礦前,首先獲取當(dāng)前工作量證明難度D,并且收集本時(shí)期內(nèi)網(wǎng)絡(luò)中產(chǎn)生的交易,將交易排列成默克爾樹(shù)形式,并計(jì)算交易構(gòu)成的默克爾樹(shù)樹(shù)根Merkle.與此同時(shí),根據(jù)比特幣的最長(zhǎng)鏈原則,選取合適的區(qū)塊鏈,獲取其最末端區(qū)塊哈希值A(chǔ)r?1.

②節(jié)點(diǎn)尋找工作量證明.節(jié)點(diǎn)通過(guò)工作量證明函數(shù)開(kāi)始挖礦:H(Ar?1,Merkle,Nonce)

③新區(qū)塊廣播與驗(yàn)證.找到工作量證明的節(jié)點(diǎn)廣播新區(qū)塊和其哈希值,收到新區(qū)塊的節(jié)點(diǎn)驗(yàn)證其區(qū)塊的合法性和其中包含交易的合法性,檢查是否存在雙花交易,通過(guò)后更新本地區(qū)塊鏈并在更新后的區(qū)塊上繼續(xù)挖礦.比特幣對(duì)礦工的激勵(lì)除了每個(gè)區(qū)塊能夠獲得的基礎(chǔ)獎(jiǎng)勵(lì)外,還包括區(qū)塊中所有交易的交易費(fèi)(transaction fees).

Garay、Kiayias和Leonardos[51]提出了比特幣區(qū)塊鏈骨干協(xié)議,分析了其基本安全特性.Pass、Seeman和Shelat[83]分析了區(qū)塊鏈在部分同步網(wǎng)絡(luò)環(huán)境下的安全性.根據(jù)上述文獻(xiàn)定義,區(qū)塊鏈具有共同前綴、鏈質(zhì)量、鏈增長(zhǎng)、公平性、強(qiáng)一致性和弱一致性等特性.

(2)以太坊

以太坊(Ethereum)由Buterin[19]提出.以太坊是能夠運(yùn)行智能合約(smart contract)的公共區(qū)塊鏈平臺(tái).智能合約是以信息化方式傳播、驗(yàn)證或執(zhí)行合同的計(jì)算機(jī)協(xié)議,以腳本代碼的形式出現(xiàn).智能合約允許雙方在沒(méi)有可信第三方存在的情況下實(shí)現(xiàn)可信交易.

以太坊的區(qū)塊大約每隔15 s 產(chǎn)生,為了解決比特幣中礦工利用專用集成電路ASIC 挖礦而導(dǎo)致的算力中心化和挖礦資源集中化問(wèn)題,以太坊設(shè)計(jì)了抵抗ASIC 且支持輕客戶端(light client)快速驗(yàn)證的PoW 算法Ethash,在一定程度上緩解了挖礦中心化問(wèn)題.

為了解決PoW 挖礦帶來(lái)的巨大能源消耗問(wèn)題,以太坊正在從PoW 共識(shí)機(jī)制向PoS 共識(shí)機(jī)制轉(zhuǎn)變,并且提出了轉(zhuǎn)變需要經(jīng)歷的四個(gè)具體階段:前沿(frontier)、家園(homestead)、大都會(huì)(metropolis)和寧?kù)o(serenity)階段.前沿階段是2015年以太坊剛開(kāi)始發(fā)布時(shí)的試驗(yàn)階段,家園階段是以太坊正式發(fā)布的版本,完全采用PoW 共識(shí)機(jī)制.大都會(huì)階段又被分為拜占庭硬分叉和君士坦丁堡硬分叉階段,2017年10 月,以太坊拜占庭硬分叉成功,為后期引入ZK-Snarks 零知識(shí)證明技術(shù)[84]提供準(zhǔn)備.而君士坦丁堡硬分叉將引入混合PoW和PoS 的共識(shí)機(jī)制.在寧?kù)o階段,以太坊將完全實(shí)行PoS 共識(shí)機(jī)制.對(duì)以太坊和智能合約的研究可以參考文獻(xiàn)[85,86].

以太坊中,區(qū)塊出塊間隔大約為15 秒,短暫的區(qū)塊間隔時(shí)間造成了以太坊區(qū)塊鏈容易產(chǎn)生分叉.如果某個(gè)礦池算力較大,且由于節(jié)點(diǎn)數(shù)量多導(dǎo)致其與網(wǎng)絡(luò)中其他節(jié)點(diǎn)的連接數(shù)量更多,那么其產(chǎn)生的區(qū)塊在網(wǎng)絡(luò)中傳播速度較快.當(dāng)出現(xiàn)分叉時(shí),其他算力較小的礦池或單一節(jié)點(diǎn)只能淪為被裁剪掉的分叉,導(dǎo)致這些節(jié)點(diǎn)失去了挖礦的動(dòng)力,進(jìn)而影響到整個(gè)以太坊系統(tǒng)的安全.為了解決上述問(wèn)題,以太坊調(diào)整了區(qū)塊結(jié)構(gòu).在比特幣中,只有在主鏈上挖礦得到區(qū)塊的礦工才會(huì)得到酬金,也只有主鏈的區(qū)塊能夠被接下來(lái)的區(qū)塊所引用.而以太坊允許主鏈包含分叉,分叉上的區(qū)塊被稱為后產(chǎn)生區(qū)塊的“叔區(qū)塊(uncle block)”,能夠被后產(chǎn)生的區(qū)塊所引用,且叔區(qū)塊的引用者和被引用者都能夠獲得一定比例的酬金.以太坊的區(qū)塊結(jié)構(gòu)如圖4所示.

圖4 以太坊區(qū)塊鏈結(jié)構(gòu)Figure 4 Structure of Blockchain in Ethereum

第二個(gè)位置的區(qū)塊首先由算力較大的礦池M產(chǎn)生,稱之為M(2),礦池M將區(qū)塊M(2)在全網(wǎng)廣播,由于區(qū)塊間隔時(shí)間只有15 秒,而由于網(wǎng)絡(luò)延遲的存在區(qū)塊的廣播需要花費(fèi)一定的時(shí)間,在M(2)還未完全到達(dá)網(wǎng)絡(luò)中其他節(jié)點(diǎn)的時(shí)間,節(jié)點(diǎn)a,b和c分別挖到了第二個(gè)位置的區(qū)塊a(2),b(2)和c(2),并在全網(wǎng)廣播,此時(shí)礦池M 收到了這三個(gè)區(qū)塊,由于其算力較大,很可能最先挖到第三個(gè)位置的區(qū)塊M(3),此時(shí)為了防止其他節(jié)點(diǎn)在其他分叉上挖礦,礦池M可以選擇將在M(3)中引用第二位置的區(qū)塊,即M(3)區(qū)塊的叔區(qū)塊.根據(jù)以太坊的設(shè)定,每個(gè)區(qū)塊中能夠引用叔區(qū)塊的個(gè)數(shù)最多為2 個(gè),每個(gè)叔區(qū)塊的引用能夠?yàn)橐谜邘?lái)額外的1/32 的出塊酬金(block reward),出塊酬金為每個(gè)區(qū)塊對(duì)應(yīng)的基本酬金,以太坊中為5個(gè)以太幣(ETH),因此礦池M選擇在a(2),b(2)和c(2)中選出兩個(gè)區(qū)塊,如a(2)和b(2),在M(3)區(qū)塊中引用它們.被成功引用的叔區(qū)塊,其對(duì)應(yīng)的礦工,能夠獲得一定比例的酬金,“直系” 叔區(qū)塊,即叔區(qū)塊與主區(qū)塊相隔“一代”,其對(duì)應(yīng)礦工能夠獲得7/8 的出塊酬金,相隔“二代” 的被引用叔區(qū)塊,其礦工能夠獲得6/8 的出塊酬金,酬金以此規(guī)則遞減,直到相隔“八代” 的叔區(qū)塊不會(huì)得到酬金,以防止惡意節(jié)點(diǎn)在歷史區(qū)塊上制造分叉.在本文所述情境中,由于M(3)區(qū)塊引用了a(2)和b(2)區(qū)塊,因此節(jié)點(diǎn)a和b分別能夠獲得7/8 的出塊酬金,而礦池M獲得了1 個(gè)完整的出塊酬金和2/32 的額外出塊酬金.此時(shí),理智的節(jié)點(diǎn)a和b應(yīng)當(dāng)選在M(3)區(qū)塊后繼續(xù)挖礦.而在第四個(gè)位置,如果礦池M找到了新的區(qū)塊M(4),仍可以選擇將相隔二代的叔區(qū)塊c(2)在M(4)中引用,此時(shí)c節(jié)點(diǎn)將獲得6/8 的出塊酬金,礦池M將獲得1 個(gè)完整的出塊酬金和1/32 的額外出塊酬金.

(3)Bitcoin-NG

Bitcoin-NG 由Eyal 等人[20]提出,意在提升比特幣處理交易的能力,其敵手模型為n=2f+1.Bitcoin-NG 的區(qū)塊分為兩種,第一種是關(guān)鍵塊(key block),關(guān)鍵塊類似于比特幣中的區(qū)塊,每十分鐘產(chǎn)生一個(gè)關(guān)鍵塊,節(jié)點(diǎn)同樣通過(guò)工作量證明的方式成為關(guān)鍵塊的出塊者,關(guān)鍵塊包括上個(gè)區(qū)塊哈希值、時(shí)間戳、隨機(jī)數(shù)和出塊者公鑰等信息,主要用來(lái)選定一個(gè)時(shí)期的出塊者,不用來(lái)記錄交易; 第二種是微塊(micro block),微塊在關(guān)鍵塊之間,由本時(shí)期的出塊者負(fù)責(zé)生成,微塊中包含了當(dāng)前發(fā)生的交易,微塊以不超過(guò)10秒/個(gè)的速度產(chǎn)生.Bitcoin-NG 共識(shí)機(jī)制如圖5所示.

Bitcoin-NG 的激勵(lì)機(jī)制與比特幣有所不同,在Bitcoin-NG 中,激勵(lì)主要包括兩部分,一部分是挖到關(guān)鍵塊的礦工直接獲得一定數(shù)量的新幣,這一點(diǎn)類似于比特幣,另一部分是交易費(fèi)的分配,假設(shè)兩個(gè)連續(xù)的關(guān)鍵塊分別由節(jié)點(diǎn)A和節(jié)點(diǎn)B產(chǎn)生,則其中間包含的微塊中的交易費(fèi)的40% 分配給前一個(gè)節(jié)點(diǎn)A,60% 分配給后一個(gè)節(jié)點(diǎn)B,為了預(yù)防區(qū)塊鏈產(chǎn)生分叉,Bitcoin-NG 中的酬金在100 個(gè)關(guān)鍵塊之后才能使用.Bitcoin-NG 的激勵(lì)機(jī)制存在一定的問(wèn)題,交易費(fèi)的分配比例能夠優(yōu)化[87].敵手對(duì)Bitcoin-NG 發(fā)動(dòng)自私挖礦等攻擊獲得的收益相比于Bitcoin 更高[88].

圖5 Bitcoin-NG 共識(shí)機(jī)制Figure 5 Consensus mechanism of Bitcoin-NG

在Bitcoin-NG 中,微塊的產(chǎn)生不需要工作量證明,因此節(jié)點(diǎn)能夠快速廉價(jià)的產(chǎn)生微塊,惡意節(jié)點(diǎn)可能通過(guò)產(chǎn)生微塊分叉來(lái)發(fā)起雙花攻擊,因此Bitcoin-NG 采用“毒藥交易(poison transaction)”,允許后面的出塊者對(duì)惡意節(jié)點(diǎn)舉報(bào),舉報(bào)成功則惡意節(jié)點(diǎn)獲得的酬金無(wú)效,舉報(bào)者能夠獲得惡意節(jié)點(diǎn)酬金5% 的獎(jiǎng)勵(lì).

Bitcoin-NG 與比特幣相比,能夠在增加交易區(qū)塊頻率、提升交易吞吐率的同時(shí),保證協(xié)議的安全性和公平性.其提出的微塊思想,將交易區(qū)塊與出塊者選舉的過(guò)程分離開(kāi)來(lái),體現(xiàn)了協(xié)議設(shè)計(jì)的模塊化思想.

(4)FruitChains

FruitChains 由Pass和Shi[21]提出,主要為了解決比特幣區(qū)塊鏈系統(tǒng)中存在的公平性問(wèn)題,即由于自私挖礦攻擊導(dǎo)致的誠(chéng)實(shí)用戶鏈質(zhì)量的下降,其敵手模型為n=2f+1.

FruitChains 首次提出了“水果(fruit)” 的概念,一個(gè)水果可能包含多個(gè)交易,而一個(gè)區(qū)塊可能包含多個(gè)水果,水果的產(chǎn)生也是通過(guò)尋找工作量證明來(lái)完成,FruitChains 中水果和區(qū)塊的挖礦同時(shí)運(yùn)行,且利用同一個(gè)哈希函數(shù)完成,該算法的設(shè)計(jì)主要受到Garay、Kiayias和Leonardos[51]的比特幣骨干協(xié)議中提出的“2 合1 PoW” 算法的啟發(fā).FruitChains 共識(shí)機(jī)制過(guò)程如圖6所示.

FruitChains 中,水果被定義為f=(h?1;h′;η;digest;m;h),其中h?1是指上個(gè)區(qū)塊的哈希值,h′是指水果f指向的區(qū)塊,此處,水果指向的區(qū)塊只能為區(qū)塊鏈末端幾個(gè)區(qū)塊之一,以此保證水果的新鮮性.η長(zhǎng)度為128 位,它是挖礦的隨機(jī)數(shù),即工作量證明的解.digest 是指目前有效水果集合F的哈希摘要,有效水果集合F是指當(dāng)前新鮮的且未被區(qū)塊包含的水果的集合.m是指要被寫入水果f中的交易集合.h長(zhǎng)度是256 位,它是指當(dāng)前水果f的哈希值.如果h的后128 位小于水果挖礦難度Df,則代表找到了水果.在水果f中,h?1和digest 對(duì)于水果本身是沒(méi)有含義的,它們被用于同時(shí)運(yùn)行的區(qū)塊挖礦中.

FruitChains 中,區(qū)塊被定義為B=((h?1;h′;η;digest;m;h),F).其中h?1,h′,η,digest,m和h的含義與之前水果中的含義相同,注意此處的h值是指前面元素的哈希值,即h=H(h?1;h′;η;digest;m),與水果挖礦中的h相同,并不包含水果集合F.F是指要被包含到區(qū)塊中的有效水果集合.當(dāng)哈希值h的前128 位小于區(qū)塊挖礦難度DB時(shí),表示節(jié)點(diǎn)成功挖到了區(qū)塊,此時(shí)的隨機(jī)數(shù)η便是工作量證明的解.

在FruitChains 中,交易是與水果綁定的,新挖到的水果被放入到有效水果集(fruit set)F中,有效水果集隨著水果的挖出和使用不斷更新,新挖到的區(qū)塊負(fù)責(zé)將F中的水果放入到區(qū)塊中,此時(shí)敵手如果針對(duì)底層區(qū)塊采取自私挖礦或是扣塊攻擊,便毫無(wú)意義,因?yàn)榘灰椎乃麜?huì)被其他誠(chéng)實(shí)節(jié)點(diǎn)產(chǎn)生的區(qū)塊收錄.因此FruitChains 防止了自私挖礦攻擊,實(shí)現(xiàn)了公平性.

FruitChains 重新設(shè)計(jì)了礦工的激勵(lì)機(jī)制,將連續(xù)幾個(gè)區(qū)塊的獎(jiǎng)勵(lì)和其中包含的所有交易費(fèi)平均分給找到工作量證明的節(jié)點(diǎn).與此同時(shí),FruitChains 為了解決目前比特幣礦池算力集中化的問(wèn)題,將水果挖礦難度降低,礦工能夠以比特幣1000 倍的頻率獲得回報(bào),平均每2 天獲得一次,因此在FruitChains 中,節(jié)點(diǎn)不再需要參與礦池就能頻繁獲得挖礦收益,降低了礦池帶來(lái)的算力集中化.

圖6 FruitChains 共識(shí)機(jī)制Figure 6 Consensus mechanism of FruitChains

(5)GHOST

GHOST 協(xié)議由Sompolinsky和Zohar[22]提出.GHOST 協(xié)議是一種主鏈選擇算法,利用最重子樹(shù)原則來(lái)代替最長(zhǎng)鏈原則.在區(qū)塊鏈出現(xiàn)分叉時(shí),計(jì)算每個(gè)分叉所有子區(qū)塊的個(gè)數(shù),作為該分叉的“重量”,將重量最大的分叉作為主鏈.GHOST 協(xié)議設(shè)計(jì)的目的在于提高吞吐率時(shí)保證區(qū)塊鏈的安全性.Kiayias和Panagiotakos[89]對(duì)GHOST 協(xié)議作出了形式化的安全分析,通過(guò)提出的“新鮮區(qū)塊定理(fresh block lemma)” 證明了GHOST 協(xié)議能夠滿足一致性和活性兩大安全特性.

(6)Spectre

基于有向無(wú)環(huán)圖(derected acyclic graph,DAG)的共識(shí)機(jī)制Spectre 由Sompolinsky、Lewenberg和Zohar[23]提出.不同于比特幣中單一主鏈的方式,Spectre 采用并行區(qū)塊,利用多條鏈跟隨主鏈的形式,支鏈與主鏈的目標(biāo)方向一致,且彼此之間不存在環(huán)路.DAG 采用的數(shù)據(jù)結(jié)構(gòu)已經(jīng)不是簡(jiǎn)單的鏈狀結(jié)構(gòu),每個(gè)新加入的區(qū)塊都會(huì)鏈接到之前的多個(gè)區(qū)塊,將其哈希值包含在自身區(qū)塊中,通過(guò)溯源可以到達(dá)創(chuàng)世區(qū)塊,所有交易區(qū)塊最終形成圖狀結(jié)構(gòu).歷史交易數(shù)據(jù)不可篡改,一旦更改,則會(huì)引起整個(gè)DAG 區(qū)塊圖的變更.采用DAG 結(jié)構(gòu)的區(qū)塊鏈技術(shù)能夠?qū)崿F(xiàn)交易處理的可擴(kuò)展性,隨著網(wǎng)絡(luò)中節(jié)點(diǎn)的增多,交易處理速度提高,交易吞吐率增加.采用DAG 結(jié)構(gòu)的區(qū)塊示意連接方式如圖7所示.

IOTA[55]、Byteball[90]]和Hashgraph[91]同樣采用DAG 結(jié)構(gòu)處理數(shù)據(jù).Conflux[92]在DAG 結(jié)構(gòu)的基礎(chǔ)上,引入?yún)^(qū)塊排序算法,將所有區(qū)塊確定性排列為單鏈結(jié)構(gòu),不產(chǎn)生分叉,充分利用每個(gè)區(qū)塊,將交易吞吐率提升到每秒鐘數(shù)千次.

除此之外,關(guān)于區(qū)塊鏈擴(kuò)容問(wèn)題的研究還有許多[93],如比特幣鏈下支付[94–96]等,由于不屬于共識(shí)機(jī)制的研究范圍,本文不作討論.相關(guān)工作可參考綜述[97,98].

5.3 綜合分析

采用工作量證明的共識(shí)機(jī)制主要面臨以下幾個(gè)問(wèn)題:

(1)巨大的能源消耗

工作量證明的尋找需要投入大量的算力,而算力的維持需要消耗巨額的電力.挖礦可能采用的CPU、GPU、FPGA和專用集成電路(ASIC)都需要連接至電網(wǎng)不間斷運(yùn)行,導(dǎo)致消耗的電量十分巨大.據(jù)統(tǒng)計(jì)[99],截止到2018年11 月11 日,僅僅比特幣挖礦造成每年的電量消耗為73.12 TW·h,TW·h 是太千瓦時(shí),與千瓦時(shí)之間的換算關(guān)系為:1 TW·h=109kW·h.相當(dāng)于全球電力總消耗的0.33%,與整個(gè)澳大利亞消耗的電力持平.每年比特幣挖礦消耗的電力大概相當(dāng)于3656 073 069 美元.而其中每個(gè)交易需要消耗746 kW·h 的電量,可見(jiàn)造成的能源浪費(fèi)十分嚴(yán)重.

圖7 DAG 結(jié)構(gòu)示例圖Figure 7 Structure of block using DAG

(2)存在安全隱患

任何共識(shí)機(jī)制都可能存在被敵手攻擊的可能性,基于工作量證明的共識(shí)機(jī)制也不例外,主要面臨以下幾種攻擊:

1)日蝕攻擊(eclipse attack)

Heilman 等人[100]分析了針對(duì)比特幣的日蝕攻擊.日蝕攻擊屬于網(wǎng)絡(luò)層攻擊的一種,在比特幣網(wǎng)絡(luò)中,每個(gè)節(jié)點(diǎn)有117 個(gè)信息輸入連接(incoming connections)和8 個(gè)信息輸出連接(outgoing connections),攻擊者首先占據(jù)目標(biāo)節(jié)點(diǎn)的網(wǎng)絡(luò)地址,然后利用非比特幣網(wǎng)絡(luò)ID 地址來(lái)覆蓋目標(biāo)節(jié)點(diǎn)的連接地址,目標(biāo)節(jié)點(diǎn)此時(shí)會(huì)實(shí)施網(wǎng)絡(luò)重啟,而重啟后的信息輸入連接很大概率都是處于敵手控制下的節(jié)點(diǎn),此時(shí)目標(biāo)節(jié)點(diǎn)所接收到的網(wǎng)絡(luò)中的消息全是敵手控制之下的消息.Marcus、Heilman和Goldberg[101]分析了以太坊網(wǎng)絡(luò)可能遭受的日蝕攻擊,指出了以太坊點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)的脆弱性.

2)雙花攻擊(double spending)

雙花攻擊是指攻擊者將已經(jīng)花費(fèi)過(guò)的代幣重新花費(fèi).一般來(lái)說(shuō),攻擊者可以通過(guò)制造區(qū)塊鏈分叉的方法來(lái)實(shí)施雙花攻擊.攻擊者首先通過(guò)代幣完成一筆交易,假設(shè)交易被包含在區(qū)塊鏈的區(qū)塊B上,在交易完成后,攻擊者通過(guò)分叉產(chǎn)生一條更長(zhǎng)的新鏈,使得區(qū)塊B作廢,這樣一來(lái),區(qū)塊B中的交易也作廢,因此攻擊者拿回了自己的代幣.

攻擊者還可以結(jié)合日蝕攻擊來(lái)實(shí)施雙花攻擊.攻擊者選定要交易的目標(biāo)節(jié)點(diǎn)T,對(duì)其實(shí)施日蝕攻擊,控制節(jié)點(diǎn)T的信息輸入通道,攻擊者將與節(jié)點(diǎn)T的交易放到自己生成的私鏈上,通過(guò)網(wǎng)絡(luò)傳播給節(jié)點(diǎn)T,這時(shí)節(jié)點(diǎn)T由于信息缺失,只能看到攻擊者的區(qū)塊鏈,因此相信交易的合法性,與攻擊者完成交易.然而實(shí)際的區(qū)塊鏈上并不存在這筆交易,因此攻擊者成功實(shí)施雙花攻擊.雙花攻擊也是其他共識(shí)機(jī)制面臨的主要安全威脅之一.

雙花攻擊一般針對(duì)具有弱一致性的區(qū)塊鏈系統(tǒng),礦工能夠在同一個(gè)區(qū)塊的不同分叉挖礦,當(dāng)敵手算力超過(guò)50%時(shí),敵手便能夠發(fā)起雙花攻擊; 當(dāng)敵手算力不足或接近50%時(shí),敵手可以實(shí)施賄賂攻擊(bribe attack)[102,103],通過(guò)一定的利益交換來(lái)獲取其他敵手的算力,使自身的算力超過(guò)50%.

3)自私挖礦(selfish mining)

文獻(xiàn)[104,105]針對(duì)比特幣提出了自私挖礦攻擊.自私挖礦是指敵手在挖到新區(qū)塊后,暫時(shí)不公布自己的區(qū)塊,而是在自己的區(qū)塊之后繼續(xù)私下挖礦,私下尋找自己的“私鏈”,當(dāng)網(wǎng)絡(luò)中其他節(jié)點(diǎn)挖到新區(qū)塊時(shí),敵手再選擇性的釋放自己私鏈中的區(qū)塊,如果敵手此時(shí)私鏈的長(zhǎng)度大于主鏈的長(zhǎng)度,那么敵手的私鏈將被網(wǎng)絡(luò)中大部分節(jié)點(diǎn)認(rèn)可,敵手的私鏈成為了主鏈; 如果敵手此時(shí)私鏈長(zhǎng)度等于主鏈長(zhǎng)度,則敵手可以配合日蝕攻擊控制網(wǎng)絡(luò)中其他節(jié)點(diǎn)獲取的消息內(nèi)容,使其先收到自己發(fā)出的私鏈,獲得其認(rèn)可.在自私挖礦攻擊中,敵手浪費(fèi)了誠(chéng)實(shí)用戶的算力,造成了誠(chéng)實(shí)用戶鏈質(zhì)量的下降.

其他對(duì)自私挖礦攻擊策略拓展的攻擊方式,還有頑固挖礦(stubborn mining)[106]、優(yōu)化自私挖礦(optimal selfish mining)[107]、扣塊(block withholding,BWH)[108]和扣塊后分叉(fork after withholding,FAW)[109]等攻擊.另外,攻擊者能夠?qū)⑷瘴g攻擊、雙花攻擊、自私挖礦等攻擊相結(jié)合,侵害誠(chéng)實(shí)節(jié)點(diǎn)的利益.對(duì)于以上攻擊方式的研究可以參考文獻(xiàn)[110,111].

6 基于權(quán)益證明的共識(shí)機(jī)制

6.1 概念

為了解決工作量證明帶來(lái)的巨大能源消耗問(wèn)題,基于權(quán)益證明的共識(shí)機(jī)制被提出.權(quán)益是指節(jié)點(diǎn)或用戶擁有的資產(chǎn),如代幣,根據(jù)用戶擁有資產(chǎn)比例決定成為下一個(gè)區(qū)塊生產(chǎn)者的概率,擁有資產(chǎn)比例越高，其成為生產(chǎn)者的概率就越大.

6.2 典型方案分析

(1)PPCoin

PPCoin 由King和Nadal[24]提出,首次引入了權(quán)益證明的概念,其敵手模型為n=2f+1.PPCoin首先通過(guò)一定階段的PoW 生成一定數(shù)量的代幣,然后進(jìn)入PoS 階段.PPCoin 提出了“幣齡” 的概念,節(jié)點(diǎn)擁有的幣數(shù)量越多,擁有幣的時(shí)間越長(zhǎng),其被選為出塊者的概率越大.PPCoin 采用的幣齡機(jī)制存在著被攻擊的可能性,節(jié)點(diǎn)可能首先保持離線狀態(tài),在積累一定的幣齡之后才參與共識(shí)網(wǎng)絡(luò),然后再次離線,這樣PPCoin 中節(jié)點(diǎn)沒(méi)有充分的激勵(lì)保持在線狀態(tài).

(2)Casper FFG

Casper FFG[25]是以太坊PoS 共識(shí)機(jī)制,由Buterin和Griffith 提出.Casper FFG 的區(qū)塊產(chǎn)生仍然依靠以太坊的Ethash 工作量證明算法,但是每隔50 個(gè)區(qū)塊出現(xiàn)一個(gè)檢查點(diǎn),驗(yàn)證者(validator)通過(guò)PoS 的方式來(lái)對(duì)檢查點(diǎn)完成最終確定.

想要成為驗(yàn)證者的成員首先需要將持有的以太幣押注到Casper FFG 的智能合約中.在驗(yàn)證者選擇過(guò)程中,節(jié)點(diǎn)被選中概率與押注的以太幣數(shù)量成正比.被選中的驗(yàn)證者驗(yàn)證檢查點(diǎn),每個(gè)檢查點(diǎn)需要經(jīng)過(guò)預(yù)確認(rèn)、最終確認(rèn)兩輪驗(yàn)證才能完成最終確認(rèn),每一輪中需要得到不少于2/3 驗(yàn)證者的合法投票.經(jīng)過(guò)最終確認(rèn)的檢查點(diǎn)作為合法的當(dāng)前狀態(tài),能夠被新加入節(jié)點(diǎn)成功獲取.

Casper FFG 的押注機(jī)制主要為了解決PoS 共識(shí)可能面臨的“無(wú)利害關(guān)系(nothing-at-stake)” 問(wèn)題.如果節(jié)點(diǎn)試圖實(shí)施無(wú)利害關(guān)系攻擊,則節(jié)點(diǎn)的保證金將被沒(méi)收.與此同時(shí)Casper FFG 對(duì)離線礦工采取了一定的懲罰機(jī)制,使得節(jié)點(diǎn)有充分的理由保持在線,維持以太坊網(wǎng)絡(luò)的安全性.

PPCoin和Casper FFG 都屬于PoW 與PoS 結(jié)合的共識(shí)機(jī)制,類似的共識(shí)機(jī)制還有2-hop[56]和活動(dòng)證明(proof of activity,PoA)[57].

(3)Ouroboros 系列

Ouroboros 由Kiayias 等人[26]提出,利用形式化的方法建立了PoS 共識(shí)機(jī)制的模型,并證明了Ouroboros 能夠滿足安全性.Ouroboros 在所有的持幣者中,利用隨機(jī)數(shù)隨機(jī)選取每一輪的出塊者,其敵手模型為n=2f+1,網(wǎng)絡(luò)模型為同步網(wǎng)絡(luò).

Ouroboros 將時(shí)間分為多個(gè)時(shí)期,每個(gè)時(shí)期包含多個(gè)輪,一輪中最多產(chǎn)生一個(gè)區(qū)塊,而如果區(qū)塊對(duì)應(yīng)的出塊者不在線時(shí),該輪不產(chǎn)生任何區(qū)塊.Ouroboros 假設(shè)每個(gè)時(shí)期內(nèi)的權(quán)益分布是不變的,在時(shí)期e發(fā)生的權(quán)益改變將在之后的時(shí)期體現(xiàn).與此同時(shí),Ouroboros 要求在連續(xù)的幾個(gè)時(shí)期內(nèi),權(quán)益分布情況的變化不能太大,即權(quán)益分布的統(tǒng)計(jì)距離應(yīng)當(dāng)有限.在每個(gè)時(shí)期的最開(kāi)始,將有一個(gè)該時(shí)期的創(chuàng)世區(qū)塊,記錄在該時(shí)期所有合法的出塊者候選人和本輪的隨機(jī)數(shù)ξe.在每個(gè)時(shí)期,Ouroboros 利用以下函數(shù)選出時(shí)期e第j輪的出塊者:Uj=F(Se,ξe,rj),其中Se是指時(shí)期e所有合法出塊候選人組成的集合(U1,U2,··· ,Un),每個(gè)候選人持有的權(quán)益分別為(s1,s2,··· ,sn).rj代表第j輪,Uj代表第j輪的出塊者,函數(shù)F(·)根據(jù)隨機(jī)數(shù)從集合Se中隨機(jī)選取出塊者.

在Ouroboros 中,每一輪的隨機(jī)數(shù)ξe由安全多方計(jì)算協(xié)議[112]產(chǎn)生,該協(xié)議使用公開(kāi)可驗(yàn)證秘密分享算法[113],保證在敵手存在的情況下,能夠產(chǎn)生抗偏置的隨機(jī)數(shù).Ouroboros 共識(shí)機(jī)制如圖8所示.

圖8 Ouroboros 共識(shí)機(jī)制流程圖Figure 8 Consensus mechanism of Ouroboros

在Ouroboros 中,每一輪除了選出單一的出塊者之外,還選出多個(gè)交易的驗(yàn)證者,被稱為“背書節(jié)點(diǎn)(endorsers)”.背書節(jié)點(diǎn)驗(yàn)證交易的合法性,并將合法交易打包發(fā)送給出塊者.Ouroboros 在設(shè)計(jì)激勵(lì)機(jī)制時(shí),充分考慮理性節(jié)點(diǎn)的存在,為了鼓勵(lì)權(quán)益持有者保持在線,并執(zhí)行交易驗(yàn)證和出塊的工作,Ouroboros把多個(gè)區(qū)塊的交易費(fèi)放入到交易費(fèi)池中,并根據(jù)參與節(jié)點(diǎn)的貢獻(xiàn)度按比例分配給相應(yīng)節(jié)點(diǎn).

David 等人[58]提出了Ouroboros Praos,改進(jìn)了Ouroboros 中出塊者的選舉方式,其敵手模型為n=2f+1,網(wǎng)絡(luò)模型為部分同步網(wǎng)絡(luò).Ouroboros 中出塊者的選舉結(jié)果是公開(kāi)可驗(yàn)證的,所有節(jié)點(diǎn)都知道本輪的出塊者的身份,而Ouroboros Praos 中,節(jié)點(diǎn)私下確定是否被選為出塊者,節(jié)點(diǎn)之間不能提前判斷其他節(jié)點(diǎn)是否被選中,直到出塊者成功將區(qū)塊生成,這樣有效防止了敵手可能對(duì)出塊者發(fā)起的賄賂攻擊或DDoS 攻擊.Ouroboros Praos 中,參與者通過(guò)可驗(yàn)證隨機(jī)函數(shù)VRF 產(chǎn)生可驗(yàn)證隨機(jī)數(shù),如果其數(shù)值低于某個(gè)目標(biāo)值,則可確定被選中為出塊者.出塊者在生成區(qū)塊時(shí),將其產(chǎn)生的隨機(jī)數(shù)和由VRF 產(chǎn)生的對(duì)隨機(jī)數(shù)的證明一起在全網(wǎng)廣播,網(wǎng)絡(luò)中其他節(jié)點(diǎn)可以確認(rèn)其合法性.Ouroboros Praos 的激勵(lì)制度跟Ouroboros 相同.Ganesh、Orlandi和Tschudi[114]改進(jìn)了Ouroboros Praos,加入了隱私保護(hù),并且提出了匿名可驗(yàn)證隨機(jī)函數(shù)的概念.

Badertscher 等人[59]提出了Ouroboros Genesis,詳細(xì)設(shè)計(jì)了新節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)的自啟(bootstrap)過(guò)程,解決了PoS 共識(shí)機(jī)制存在的長(zhǎng)程攻擊.Ouroboros Genesis 保留了Ouroboros Praos 中利用VRF隨機(jī)選擇出塊者的部分,修改了最長(zhǎng)鏈原則,新節(jié)點(diǎn)在加入網(wǎng)絡(luò)時(shí),需要從不同節(jié)點(diǎn)獲得多個(gè)鏈,并將其對(duì)比,最終選定的區(qū)塊鏈需要與其他鏈具有共同前綴且是最長(zhǎng)鏈.Ouroboros Genesis 在沒(méi)有采用檢查點(diǎn)機(jī)制的前提下能夠抵抗長(zhǎng)程攻擊,并且在通用可組合(universally composability)模型下,形式化證明了協(xié)議的安全性.

Kerber 等人[115]提出了Ouroboros Crypsinous,首次提出了基于PoS 的隱私保護(hù)區(qū)塊鏈,并且給出了形式化安全證明.Ouroboros Crypsinous 采用了UC 通用可組合安全證明框架,能夠抵抗適應(yīng)性攻擊.

(4)Snow White

Snow White 由Daian、Pass和Shi[27]提出,其敵手模型為n=2f+1.Snow White 提出了適合PoS 的可重配置共識(shí)機(jī)制,重配置的間隔時(shí)間短暫,能夠滿足節(jié)點(diǎn)隨機(jī)加入和退出網(wǎng)絡(luò)的需求.每次重配置過(guò)程選出系統(tǒng)中最近的權(quán)益擁有者作為活動(dòng)成員集合,然后按集合中成員權(quán)益占比隨機(jī)選擇出塊者.Snow White 每個(gè)時(shí)期運(yùn)行重配置的目的是,根據(jù)系統(tǒng)目前的權(quán)益分布來(lái)選擇活動(dòng)成員集合和出塊者,即活動(dòng)成員集合隨著系統(tǒng)中權(quán)益的變化而重新選擇,防止敵手的后來(lái)腐化(posterior corruption)攻擊.Snow White 要求系統(tǒng)中權(quán)益分布變化不能過(guò)快,在此基礎(chǔ)上達(dá)成了節(jié)點(diǎn)投票權(quán)與其持幣數(shù)量成正比的目的.

Snow White 采用的網(wǎng)絡(luò)模型為睡眠模型(sleepy model)[116],即節(jié)點(diǎn)不會(huì)保持永久在線,可能在某段時(shí)間內(nèi)在線,也可能在某段時(shí)間內(nèi)離線,間斷參與共識(shí).該模型中節(jié)點(diǎn)的狀態(tài)更加符合現(xiàn)實(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)的狀態(tài).Snow White 采用與FruitChains 類似的激勵(lì)制度,并且同樣采用區(qū)塊和水果同時(shí)生成的挖礦機(jī)制,交易放在水果中,水果放在區(qū)塊中,將連續(xù)幾個(gè)區(qū)塊的獎(jiǎng)勵(lì)和其中包含的交易費(fèi)平均分給區(qū)塊對(duì)應(yīng)的出塊者,實(shí)現(xiàn)了公平性.

(5)DPoS

委托權(quán)益證明(delegated proof of stake,DPoS)[28]采用委托人的形式,權(quán)益持有者投票給信任的委托人,票數(shù)與其權(quán)益大小成比例關(guān)系,最終選出101 名委托人以平等的權(quán)利輪流作為區(qū)塊生產(chǎn)者行使權(quán)利.如果委托人在委任期間未按規(guī)則產(chǎn)生正確區(qū)塊,該委托人將會(huì)被除名,所有權(quán)益持有者選出新的超級(jí)節(jié)點(diǎn)將其替代.比特股(Bitshares)以DPoS 為原理實(shí)現(xiàn).DPoS 以選舉委托人的形式實(shí)現(xiàn)共識(shí),帶來(lái)了嚴(yán)重的中心化問(wèn)題.

6.3 綜合分析

6.2 節(jié)簡(jiǎn)單介紹了基于權(quán)益證明的共識(shí)機(jī)制的典型方案,側(cè)重于具體流程.下面介紹基于權(quán)益證明共識(shí)機(jī)制面臨的主要攻擊.

(1)無(wú)利害關(guān)系攻擊(nothing at stake attack)

無(wú)利害關(guān)系攻擊[117]是指攻擊者在過(guò)去鏈的不同分叉上挖礦試圖獲取更高利益.在PoS 共識(shí)機(jī)制中,制造區(qū)塊鏈的分叉不像PoW 共識(shí)機(jī)制中需要花費(fèi)一定的算力成本,攻擊者不會(huì)對(duì)自身利益造成損失.如果沒(méi)有預(yù)防機(jī)制,當(dāng)區(qū)塊鏈出現(xiàn)分叉時(shí),節(jié)點(diǎn)為了增加自身獲利的可能性,在區(qū)塊鏈的每個(gè)分叉上都挖礦.無(wú)利害關(guān)系攻擊可以通過(guò)在PoS 共識(shí)中引入相應(yīng)的懲罰機(jī)制來(lái)預(yù)防,即對(duì)在不同分叉上產(chǎn)生區(qū)塊的節(jié)點(diǎn)作出懲罰.

(2)打磨攻擊(grinding attack)

打磨攻擊[118]是指在某些PoS 共識(shí)機(jī)制中,第r+1 輪的出塊者選舉受到第r輪出塊者的影響,選舉結(jié)果不隨機(jī),不能抗偏置.在這些PoS 共識(shí)機(jī)制中,第r+1 輪的出塊者通常與第r輪生成的區(qū)塊相關(guān),這樣一來(lái),如果第r輪的出塊者被敵手控制,敵手為了繼續(xù)成為第r+1 輪的出塊者,便在第r輪嘗試不斷生成新的區(qū)塊,對(duì)生成的區(qū)塊不斷的“打磨”,直到最終生成的區(qū)塊對(duì)自身有利.打磨攻擊可以通過(guò)使用抗偏置隨機(jī)數(shù)決定每一輪出塊者的方式來(lái)防止.

(3)長(zhǎng)程攻擊(long range attack)

長(zhǎng)程攻擊[119]主要是PoS 網(wǎng)絡(luò)中的離線節(jié)點(diǎn)或新節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí),敵手偽造一條從創(chuàng)世區(qū)塊到最新區(qū)塊的區(qū)塊鏈,試圖讓新加入節(jié)點(diǎn)相信其偽造的區(qū)塊鏈.在PoW 為基礎(chǔ)的區(qū)塊鏈中,通常采用最長(zhǎng)鏈原則或最重鏈原則來(lái)判斷哪條區(qū)塊鏈?zhǔn)钦嬲戏ǖ闹麈?假設(shè)主鏈為A,敵手想制造假的鏈B來(lái)讓新加入的節(jié)點(diǎn)相信B為主鏈,在PoW 為基礎(chǔ)的區(qū)塊鏈中,新節(jié)點(diǎn)可以通過(guò)判斷兩條鏈中挖礦難度輕松判斷A為主鏈,因?yàn)锳中區(qū)塊的挖礦難度一定非常明顯的高于B,而敵手想要制造一條類似于A的主鏈,將花費(fèi)相當(dāng)龐大的算力,攻擊成本將大大超過(guò)可能帶來(lái)的收益.而在PoS 為基礎(chǔ)的區(qū)塊鏈中,想要仿造一條主鏈A則容易的多,敵手可以通過(guò)賄賂節(jié)點(diǎn),使其出售過(guò)去使用過(guò)的重要私鑰,不需要花費(fèi)太多的成本便可以偽造出一條假鏈B,讓新加入的節(jié)點(diǎn)認(rèn)為鏈B才是真正的主鏈,從而達(dá)到其他不法目的.長(zhǎng)程攻擊可以通過(guò)檢查點(diǎn)機(jī)制來(lái)防范.

(4)權(quán)益竊取攻擊(stake bleeding attack)

Ga?i、Kiayias和Russell[120]提出了針對(duì)PoS 共識(shí)機(jī)制的權(quán)益竊取攻擊.權(quán)益竊取攻擊主要在長(zhǎng)程攻擊成功后實(shí)施,對(duì)于未采用檢查點(diǎn)機(jī)制的PoS 共識(shí)系統(tǒng),敵手發(fā)動(dòng)長(zhǎng)程攻擊后,使得新加入的節(jié)點(diǎn)相信敵手的鏈B為當(dāng)前主鏈,則新節(jié)點(diǎn)產(chǎn)生的交易將會(huì)被提交到鏈B處理,鏈B中的節(jié)點(diǎn)完全由敵手控制,因此交易費(fèi)全部歸敵手所有.

7 采用單一委員會(huì)的混合共識(shí)機(jī)制

7.1 概念

混合共識(shí)機(jī)制的含義是將經(jīng)典分布式共識(shí)機(jī)制與區(qū)塊鏈共識(shí)機(jī)制相結(jié)合,即采用PoW 或PoS 的方式選舉特定的委員會(huì),在委員會(huì)內(nèi)部運(yùn)行經(jīng)典分布式共識(shí)機(jī)制,生成區(qū)塊.采用單一委員會(huì)的混合共識(shí)機(jī)制選舉一個(gè)委員會(huì)負(fù)責(zé)全網(wǎng)所有交易的處理,而采用多委員會(huì)的混合共識(shí)機(jī)制選舉多個(gè)并行運(yùn)作的委員會(huì),將全網(wǎng)劃分為多個(gè)片區(qū),分片處理網(wǎng)絡(luò)中的交易.混合共識(shí)機(jī)制的一般過(guò)程如下:

(1)選舉委員會(huì)成員.委員會(huì)成員通過(guò)PoW 或PoS 的方式選舉,用來(lái)防止女巫攻擊.采用PoW 的選舉方式需要設(shè)定一定的挖礦難度,保證每個(gè)時(shí)期找到PoW 的節(jié)點(diǎn)數(shù)目替換掉委員會(huì)內(nèi)部分節(jié)點(diǎn).采用PoS 的選舉方式，需要在持幣者中，根據(jù)持幣者擁有幣數(shù)量，隨機(jī)選取一定數(shù)量節(jié)點(diǎn)作為委員會(huì)新成員.

(2)選舉委員會(huì)領(lǐng)導(dǎo)者.委員會(huì)內(nèi)部共識(shí)的運(yùn)行需要領(lǐng)導(dǎo)者發(fā)起,并且采取一定的機(jī)制防止領(lǐng)導(dǎo)者不作為或者發(fā)生惡意行為.委員會(huì)領(lǐng)導(dǎo)者可以通過(guò)隨機(jī)數(shù)或投票的方式選擇.

(3)運(yùn)行委員會(huì)內(nèi)分布式一致性算法.委員會(huì)領(lǐng)導(dǎo)者在委員會(huì)內(nèi)部對(duì)區(qū)塊發(fā)起共識(shí)請(qǐng)求,一般可以運(yùn)行類似PBFT 或其改進(jìn)協(xié)議,實(shí)現(xiàn)委員會(huì)內(nèi)部的拜占庭容錯(cuò),達(dá)成分布式一致性共識(shí),進(jìn)而生成和維護(hù)區(qū)塊鏈.

(4)廣播區(qū)塊.委員會(huì)成員將生成的區(qū)塊廣播至全網(wǎng),使得網(wǎng)絡(luò)中非委員會(huì)的節(jié)點(diǎn)和客戶端收到新產(chǎn)生的區(qū)塊,更新交易和區(qū)塊鏈.

(5)重配置委員會(huì).一個(gè)委員會(huì)工作的時(shí)間對(duì)應(yīng)為一個(gè)時(shí)期,系統(tǒng)應(yīng)當(dāng)合理設(shè)置每個(gè)時(shí)期的時(shí)間長(zhǎng)度,用來(lái)防止敵手腐化委員會(huì)成員.在一個(gè)時(shí)期過(guò)后,委員會(huì)開(kāi)始重配置過(guò)程,按照一定的方式替換原本的委員會(huì),然后新委員會(huì)接任下個(gè)時(shí)期的工作.委員會(huì)的更新方式一般有滑窗式、隨機(jī)更新等方式,隨機(jī)更新是指新找到PoW 或被PoS 選中的節(jié)點(diǎn)成為委員會(huì)新的成員,替換原委員會(huì)中的部分成員,進(jìn)入新時(shí)期.

采用單一委員會(huì)的混合共識(shí)機(jī)制流程如圖9所示.

圖9 單一委員會(huì)混合共識(shí)Figure 9 Single-committee based hybrid consensus

7.2 典型方案分析

(1)PeerCensus

PeerCensus 由Decker、Seidel和Wattenhofer[29]提出,首次將經(jīng)典分布式一致性算法PBFT 與區(qū)塊鏈結(jié)合,其敵手模型為n=4f+1.PeerCensus 利用比特幣作為底層鏈,選出一定數(shù)量的節(jié)點(diǎn),對(duì)其完成身份認(rèn)證后通過(guò)鏈一致(chain agreement,CA)算法,來(lái)完成最終區(qū)塊的生成,鏈一致算法通常采用PBFT 來(lái)實(shí)現(xiàn).PeerCensus 允許加入新節(jié)點(diǎn),新節(jié)點(diǎn)需要通過(guò)委員會(huì)的共識(shí)決定才能加入到委員會(huì)中.PeerCensus 的委員會(huì)管理存在一定問(wèn)題,它采用離開(kāi)檢測(cè)機(jī)制來(lái)判斷節(jié)點(diǎn)是否離開(kāi).正常節(jié)點(diǎn)通過(guò)發(fā)送ping 消息,如果未收到相應(yīng)節(jié)點(diǎn)的回復(fù),則判斷其離線,然后正常節(jié)點(diǎn)發(fā)起對(duì)該離線節(jié)點(diǎn)的“ 離開(kāi)” 提議,提議通過(guò)委員會(huì)共識(shí)后,委員會(huì)才完成重配置.這樣一來(lái),惡意用戶能夠通過(guò)不斷制造離開(kāi)提議的方式降低整個(gè)系統(tǒng)的運(yùn)行效率.

(2)ByzCoin

ByzCoin 由Kokoris-Kogias 等人[30]提出.ByzCoin 同樣是將PoW 與PBFT 相結(jié)合,ByzCoin 采用的敵手模型為n=4f+11在 ByzCoin 原文中,敵手模型為 n=3f +1,后來(lái)hybrid consensus [32]指出由于自私挖礦導(dǎo)致鏈質(zhì)量下降,ByzCoin敵手模型應(yīng)為n=4f +1..其共識(shí)流程如下:

①委員會(huì)成員選舉.ByzCoin 采用工作量證明的方式選取委員會(huì).它借鑒了Bitcoin-NG 的思想,將區(qū)塊分為關(guān)鍵塊和微塊,關(guān)鍵塊決定委員會(huì)成員和領(lǐng)導(dǎo)者,找到最近 144 個(gè)關(guān)鍵塊(相當(dāng)于一天)或 1008個(gè)關(guān)鍵塊(相當(dāng)于一周)的節(jié)點(diǎn)進(jìn)入委員會(huì).節(jié)點(diǎn)的投票權(quán)由其產(chǎn)生的關(guān)鍵塊的比例決定.

②委員會(huì)內(nèi)分布式一致性算法.委員會(huì)成員采用改進(jìn)的PBFT 算法完成共識(shí),每?jī)蓚€(gè)節(jié)點(diǎn)之間利用MAC 實(shí)現(xiàn)通信,在每一輪共識(shí)的每一個(gè)階段,節(jié)點(diǎn)需要利用跟每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的私鑰,向每個(gè)節(jié)點(diǎn)廣播消息.而B(niǎo)yzCoin 利用群體簽名(collective signing,CoSi)[121]來(lái)替換MAC,采用默克爾樹(shù)的形式對(duì)每個(gè)消息的節(jié)點(diǎn)簽名排列2Cosi 簽名方案的安全性并沒(méi)有得到證明[122]..每一輪對(duì)微塊達(dá)成共識(shí),微塊中包括當(dāng)前時(shí)間內(nèi)發(fā)生的交易.

③委員會(huì)重配置.ByzCoin 的委員會(huì)重配置采用“滑窗” 的形式,即新找到關(guān)鍵塊的節(jié)點(diǎn)進(jìn)入委員會(huì),并成為當(dāng)前委員會(huì)的領(lǐng)導(dǎo)者,將委員會(huì)中“最久遠(yuǎn)” 的區(qū)塊的出塊者踢出委員會(huì).

在144 個(gè)委員會(huì)成員且區(qū)塊大小為32 MB 的情況下,ByzCoin 能夠達(dá)到的交易吞吐率為974 tps.

(3)Solida

Solida 混合共識(shí)機(jī)制由 Abraham 等人[31]提出.Solida 主要解決了委員會(huì)重配置時(shí)可能出現(xiàn)的問(wèn)題.首先,Solida 的領(lǐng)導(dǎo)者選舉方式借鑒了 Paxos 的思想,為每個(gè)領(lǐng)導(dǎo)者賦予不同的等級(jí)(c,e,v),其中c代表委員會(huì)序號(hào),當(dāng)新節(jié)點(diǎn)通過(guò)委員會(huì)重配置加入到新委員會(huì)中后,(c,e,v)變?yōu)?c+1,0,0),新加入的節(jié)點(diǎn)成為委員會(huì)領(lǐng)導(dǎo)者.e代表一個(gè) PoW 對(duì)應(yīng)的生存時(shí)期,如果有節(jié)點(diǎn)新找到 PoW,則(c,e,v)變?yōu)?c,e+ 1,0),新找到 PoW 的節(jié)點(diǎn)成為領(lǐng)導(dǎo)者.v的含義是視圖,當(dāng)現(xiàn)任領(lǐng)導(dǎo)者停滯不前,利用函數(shù)L(c,e,v)=H(c,e)+vmodn(其中n代表委員會(huì)成員個(gè)數(shù))在委員會(huì)內(nèi)部選出新的領(lǐng)導(dǎo)者,(c,e,v)變?yōu)?c,e,v+1).

Solida 共識(shí)機(jī)制的流程如下:

①委員會(huì)內(nèi)分布式一致性算法.Solida 改進(jìn)了PBFT 算法,刪除了預(yù)準(zhǔn)備階段,增加了公示階段,包括(a).提議(propose).領(lǐng)導(dǎo)者將交易打包并廣播 tx和(propose,c,e,v,s,h),其中h是交易的哈希值.(b).準(zhǔn)備(prepare).收到上述信息的成員檢查交易和領(lǐng)導(dǎo)者身份的合法性,驗(yàn)證通過(guò)后廣播消息(prepare,c,e,v,s,h).如果委員會(huì)成員收到超過(guò)2f+1 個(gè)對(duì)h的準(zhǔn)備消息,那么該成員接受(accept)提議h,并將該 2f+1 個(gè)準(zhǔn)備消息組成接受證明(accept certificate)A.(c).承諾(commit).如果成員接受了h,那么廣播消息(commit,c,e,v,s,h),同樣,如果其收到超過(guò) 2f+1 個(gè)合法的承諾消息,則認(rèn)為h被最終確認(rèn),并將 2f+1 個(gè)合法承諾消息組成承諾憑證(commit certificate)C.(d).公示(notify).節(jié)點(diǎn)完成對(duì)h的承諾之后,在全網(wǎng)廣播公示消息((notify,c,e,v,s,h),C),收到該消息的用戶驗(yàn)證其合法性,通過(guò)后完成交易的確認(rèn).

②重配置.(a).新時(shí)期(new-lifespan).節(jié)點(diǎn)獲取當(dāng)前PoW 的難題,為了防止自私挖礦,Solida 將難題設(shè)置為任取f+1 個(gè)合法公示消息(notify,c,e,v,s,h).找到PoW 的節(jié)點(diǎn)將其廣播給委員會(huì)成員.委員會(huì)成員確認(rèn)PoW 的合法性,并進(jìn)入(c,e+1,0),將發(fā)現(xiàn)PoW 的節(jié)點(diǎn)視為新的領(lǐng)導(dǎo)L′=(c,e+1,0).(b).狀態(tài)上傳(status).節(jié)點(diǎn)進(jìn)入新時(shí)期后,向新領(lǐng)導(dǎo)發(fā)送當(dāng)前狀態(tài)信息((status,c,e,0,s?1,h,s,h′),C,A),其中h是已承諾交易的哈希值,C為對(duì)應(yīng)的承諾憑證,h′為已接受交易的哈希值,A為對(duì)應(yīng)的接受憑證.新領(lǐng)導(dǎo)者收到超過(guò) 2f+1 個(gè) status 消息,將其組成狀態(tài)憑證(status certificate)S.(c).重提議(re-propose).新領(lǐng)導(dǎo)者將最高的h視為已承諾值,將排名最高的已接受值h′重新提議,經(jīng)過(guò)接受、承諾和公示步驟后,完成對(duì)h′的承諾,并開(kāi)始新的委員會(huì)內(nèi)分布式一致性算法.Solida 重配置的過(guò)程如圖10所示.

在Solida 中,重配置時(shí)采用新找到PoW 的礦工作為下個(gè)時(shí)期的領(lǐng)導(dǎo)者,此時(shí)的新領(lǐng)導(dǎo)者能夠打斷當(dāng)前委員會(huì)領(lǐng)導(dǎo)者,經(jīng)過(guò)委員會(huì)內(nèi)部共識(shí)后,新領(lǐng)導(dǎo)者正式接管委員會(huì),新領(lǐng)導(dǎo)者必須將之前被打斷的提議重新發(fā)起共識(shí).Solida 的敵手模型為n=3f+1,為了防止自私挖礦帶來(lái)鏈質(zhì)量的下降,Solida 在PoW中嵌入了新鮮的隨機(jī)數(shù),將每一輪提議最終得到的f+1 個(gè)簽名嵌入到PoW 中,保證誠(chéng)實(shí)用戶的鏈質(zhì)量,從而保證委員會(huì)中有超過(guò)2/3 的誠(chéng)實(shí)用戶.

圖10 Solida 重配置流程圖Figure 10 Reconfiguration process of Solida

(4)Hybrid consensus

混合共識(shí)hybrid consensus 由Pass和Shi[32]提出.Hybrid consensus 將經(jīng)典共識(shí)機(jī)制與非授權(quán)共識(shí)機(jī)制結(jié)合,利用工作量證明,提出混合共識(shí)機(jī)制,實(shí)現(xiàn)非授權(quán)環(huán)境中的狀態(tài)機(jī)復(fù)制.Pass和Shi 提出了交易的快速響應(yīng)特性(responsivenss),是指交易的確認(rèn)時(shí)間與網(wǎng)絡(luò)真實(shí)時(shí)延有關(guān),而與網(wǎng)絡(luò)時(shí)延上限無(wú)關(guān).Hybrid consensus 成功實(shí)現(xiàn)了交易的快速響應(yīng)特性.

在hybrid consensus 中,Pass和Shi 指出了ByzCoin 存在的問(wèn)題,ByzCoin 原本采用的敵手模型為n=3f+1,而由于自私挖礦攻擊導(dǎo)致誠(chéng)實(shí)節(jié)點(diǎn)維護(hù)的關(guān)鍵塊鏈質(zhì)量下降,只有當(dāng)敵手所占比例不超過(guò)1/4時(shí),誠(chéng)實(shí)節(jié)點(diǎn)產(chǎn)生的關(guān)鍵塊比例才能夠超過(guò)2/3,委員會(huì)內(nèi)誠(chéng)實(shí)用戶的數(shù)量占比才能得到確保.

Hybrid consensus 首次利用形式化的安全模型和模塊化的設(shè)計(jì)建?；旌瞎沧R(shí)機(jī)制,并證明了其能夠滿足一致性和活性等安全特性.

(5)Thunderella

Thunderella 由Pass和Shi[33]提出,敵手模型為n=4f+1/n=2f+1.Thunderella 的核心思想是在類似于比特幣的底層鏈之上,組成委員會(huì),實(shí)現(xiàn)交易快速響應(yīng).Thunderella 共識(shí)機(jī)制流程如圖11所示.

圖11 Thunderella 共識(shí)機(jī)制流程圖Figure 11 Consensus mechanism of Thunderella

Thunderella 共識(shí)機(jī)制的流程如下:

①委員會(huì)選舉.Thunderella 提供了兩種非授權(quán)網(wǎng)絡(luò)中委員會(huì)選舉的方式:第一種是利用PoW,通過(guò)底層鏈將最新找到PoW 的節(jié)點(diǎn)作為委員會(huì)成員,并按順序依次替換老節(jié)點(diǎn).為了實(shí)現(xiàn)公平性和防止自私挖礦攻擊,Thunderella 采用FruitChains 作為底層鏈; 第二種是利用PoS,隨機(jī)選取一定數(shù)量的權(quán)益持有者作為委員會(huì)成員.

②樂(lè)觀期(optimistic fast path period).需滿足條件:(a).領(lǐng)導(dǎo)者誠(chéng)實(shí);(b).委員會(huì)中誠(chéng)實(shí)節(jié)點(diǎn)數(shù)量超過(guò)3/4.設(shè)委員會(huì)成員數(shù)量共n個(gè),樂(lè)觀期交易確認(rèn)過(guò)程如下:(a).客戶端提交交易txi至委員會(huì)領(lǐng)導(dǎo)者;(b).領(lǐng)導(dǎo)者賦予交易序列號(hào)i,并將(i,txi)廣播給其他委員會(huì)成員;(c).委員會(huì)成員驗(yàn)證交易txi,通過(guò)驗(yàn)證則對(duì)其簽名并廣播;(d).網(wǎng)絡(luò)中任意節(jié)點(diǎn)收集對(duì)交易txi的簽名,如果有效簽名數(shù)量超過(guò)3n/4 個(gè),則認(rèn)為交易txi被最終確認(rèn).

連續(xù)的被確認(rèn)交易組成交易的“幸運(yùn)序列(lucky sequence)”,如tx1,tx2,tx3,tx5完成了確認(rèn),則組成的交易幸運(yùn)序列為:((1,tx1),(2,tx2),(3,tx3)),其中并不包括tx4和tx5.

③寬限期(grace period).寬限期是樂(lè)觀期向底層區(qū)塊鏈確認(rèn)期的過(guò)渡,當(dāng)未滿足樂(lè)觀期條件時(shí),進(jìn)入寬限期.寬限期具體的識(shí)別標(biāo)準(zhǔn)如下:如果節(jié)點(diǎn)發(fā)現(xiàn)其提交的交易txi長(zhǎng)時(shí)間未被確認(rèn),則將其發(fā)送到區(qū)塊鏈上.若經(jīng)過(guò)k個(gè)區(qū)塊(k為安全參數(shù),圖中假設(shè)k=2)之后,交易txi仍然未被添加到幸運(yùn)序列,則進(jìn)入寬限期.

寬限期包括k個(gè)區(qū)塊,寬限期未結(jié)束時(shí),節(jié)點(diǎn)輸出其認(rèn)同的最長(zhǎng)交易幸運(yùn)序列; 寬限期結(jié)束后,節(jié)點(diǎn)輸出所有已確認(rèn)和未確認(rèn)交易,進(jìn)入底層區(qū)塊鏈確認(rèn)期.

④底層區(qū)塊鏈確認(rèn)期(foundation Blockchain period).底層區(qū)塊鏈確認(rèn)期采用底層鏈共識(shí)機(jī)制,Thunderella 利用FruitChains 作為底層鏈,實(shí)現(xiàn)公平性,抵抗自私挖礦攻擊.在該時(shí)期,Thunderella能夠隨時(shí)重新進(jìn)入樂(lè)觀期,快速確認(rèn)交易.

Thunderella 樂(lè)觀期需要有超過(guò)3/4 的委員會(huì)成員投票,原因同樣是對(duì)于兩個(gè)不同的交易,如果其投票數(shù)量都滿足條件,則其中必然有超過(guò)1/2 的委員會(huì)成員對(duì)兩個(gè)交易都投票,而Thunderella 假設(shè)惡意節(jié)點(diǎn)不超過(guò)總節(jié)點(diǎn)個(gè)數(shù)的1/2,因此與假設(shè)矛盾.Thunderella 底層鏈采用FruitChains 能夠保證惡意節(jié)點(diǎn)算力不超過(guò)全網(wǎng)算力1/2 的條件下,惡意節(jié)點(diǎn)產(chǎn)生的區(qū)塊數(shù)量不超過(guò)區(qū)塊總數(shù)量的1/2,因此保證了委員會(huì)中惡意成員數(shù)量不超過(guò)1/2.Thunderella 同樣用形式化的方法證明了協(xié)議滿足一致性和活性.

(6)Algorand

Algorand 由Gilad 等人[34]提出.Algorand 是將PoS 與經(jīng)典分布式一致性算法結(jié)合的混合共識(shí)機(jī)制,其敵手模型為n=3f+1,網(wǎng)絡(luò)模型為同步網(wǎng)絡(luò).

在Algorand 中,區(qū)塊結(jié)構(gòu)如下:Br=(r,PAYr,SIG?r(Qr?1),H(Br?1)).其中r是指區(qū)塊的序列號(hào),即當(dāng)前的輪數(shù),PAYr是指當(dāng)前時(shí)間內(nèi)發(fā)生的交集集合,Qr?1是指上一輪產(chǎn)生的隨機(jī)種子,H(Br?1)是指上一個(gè)區(qū)塊的哈希值,?r是指當(dāng)前輪的領(lǐng)導(dǎo)者,SIG?r(Qr?1)是指?r利用自身私鑰對(duì)Qr?1計(jì)算的數(shù)字簽名.

Algorand 算法的流程如下:

①隨機(jī)數(shù)計(jì)算.在每一輪r中,節(jié)點(diǎn)獲取上個(gè)區(qū)塊的信息，計(jì)算本輪隨機(jī)數(shù),即上個(gè)區(qū)塊為Br?1=(r?1,PAYr?1,SIG?r?1(Qr?2),H(Br?2)).然后通過(guò)函數(shù)計(jì)算得到Qr?1=H(SIG?r?1(Qr?2),r?1).

②判斷是否被選中為本輪領(lǐng)導(dǎo)者/參與者.節(jié)點(diǎn)i私下判斷其是否被選中為本輪的領(lǐng)導(dǎo)者和本輪的委員會(huì)成員.若滿足則其被選中為本輪領(lǐng)導(dǎo)者; 若滿足pc,則其被選中為本輪委員會(huì)成員,此處p?和pc對(duì)應(yīng)不同的難度系數(shù).

③委員會(huì)內(nèi)分布式一致性算法.當(dāng)前輪被選中的節(jié)點(diǎn)運(yùn)行委員會(huì)內(nèi)分布式一致性算法.Algorand 提出了新的拜占庭一致算法BA,BA包括分級(jí)共識(shí)(graded consensus,GC)和二元拜占庭一致(binary Byzantine agreement,BBA)算法,在分級(jí)共識(shí)中,Algorand 將對(duì)整個(gè)區(qū)塊哈希值的共識(shí)轉(zhuǎn)化為對(duì)二元數(shù)值的共識(shí),并將二元數(shù)值放入到BBA 中,通過(guò)BBA 對(duì)二元數(shù)值達(dá)成一致從而確認(rèn)本輪區(qū)塊.

Algorand 的敵手模型為適應(yīng)性敵手.如果委員會(huì)內(nèi)分布式一致性算法采用類似于PBFT 的協(xié)議,委員會(huì)成員在一個(gè)提議過(guò)程中,需要至少三輪的投票,而敵手可以在成員第一輪投票之后辨認(rèn)出委員會(huì)成員,并對(duì)其實(shí)施腐化,從而控制整個(gè)委員會(huì).Algorand 采用了GC和BBA 結(jié)合的方式,每一輪投票采用全新選擇的委員會(huì),經(jīng)過(guò)一輪投票之后,雖然委員會(huì)身份暴露在敵手之下,但是其已經(jīng)失去了被腐化的意義,因?yàn)閷?shí)施下一輪投票的成員是利用PoS 重新選擇的節(jié)點(diǎn).PoS 在所有權(quán)益持有者中隨機(jī)選擇一定數(shù)量的委員會(huì)成員,相比于PoW,PoS 選擇成員的方式更加快速、高效,因此可以被Algorand 用于委員會(huì)的快速更新.Algorand 實(shí)現(xiàn)了仿真,當(dāng)50 k 個(gè)用戶時(shí),交易吞吐量大約為比特幣的125 倍.

7.3 綜合分析

混合共識(shí)機(jī)制將經(jīng)典分布式一致性算法與非授權(quán)共識(shí)相結(jié)合,具有強(qiáng)一致性特性,區(qū)塊鏈分叉概率很小,交易能夠得到較快速度的確認(rèn).但是,混合共識(shí)機(jī)制引入了一些新的問(wèn)題.

第一,協(xié)議啟動(dòng)問(wèn)題.在協(xié)議運(yùn)行的初始階段,如何安全的初始化,創(chuàng)建創(chuàng)世區(qū)塊; 如何不依賴可信啟動(dòng)來(lái)對(duì)協(xié)議運(yùn)行初始化配置[123,124],如利用安全多方計(jì)算等算法等;

第二,委員會(huì)重配置問(wèn)題.委員會(huì)重配置期間,如何確保新的委員會(huì)成員中誠(chéng)實(shí)用戶達(dá)到相應(yīng)比例; 如何確保新舊委員會(huì)成員交替時(shí),交易能夠持續(xù)處理; 如何確保敵手不能影響新節(jié)點(diǎn)加入委員會(huì)等;

第三,新節(jié)點(diǎn)加入問(wèn)題.在新節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí),如何實(shí)現(xiàn)快速自啟[125,126],避免下載海量的交易歷史和狀態(tài)等信息; 如何確保新節(jié)點(diǎn)加入時(shí)獲得的交易狀態(tài)信息真實(shí)有效,識(shí)別敵手產(chǎn)生的虛假信息等;

第四,委員會(huì)內(nèi)分布式一致性算法問(wèn)題.在委員會(huì)內(nèi)運(yùn)行分布式一致性算法期間,如何確?？蛻舳颂峤坏慕灰啄軌虮豢焖夙憫?yīng); 如何提高委員會(huì)內(nèi)分布式一致性算法的運(yùn)行效率,降低委員會(huì)成員間的通信復(fù)雜度和計(jì)算復(fù)雜度; 如何實(shí)現(xiàn)區(qū)塊的并行提議等.

8 采用多委員會(huì)的混合共識(shí)機(jī)制

8.1 概念

為了解決區(qū)塊鏈處理交易的可擴(kuò)展性,利用多個(gè)并行的委員會(huì)來(lái)處理網(wǎng)絡(luò)中不同分片的交易的混合共識(shí)機(jī)制被提出,也被稱為分片共識(shí)(sharding consensus)機(jī)制.

目前分片有以下幾種含義:

(1)通信分片(communication sharding)

通信分片是指將全網(wǎng)分為不同的片區(qū),每個(gè)片區(qū)由一個(gè)對(duì)應(yīng)的委員會(huì)處理,每個(gè)委員會(huì)內(nèi)部成員大部分時(shí)間只需內(nèi)部通信,每個(gè)片區(qū)內(nèi)部的其他客戶端、節(jié)點(diǎn)大部分時(shí)間可以通過(guò)與該分片內(nèi)委員會(huì)通信獲得目前區(qū)塊鏈的狀態(tài).

(2)計(jì)算分片(computation sharding)

計(jì)算分片是指每個(gè)分片委員會(huì)只負(fù)責(zé)處理其對(duì)應(yīng)的交易,如根據(jù)交易的ID 判斷其對(duì)應(yīng)的分片,交易ID 最末位數(shù)字如果是i,則由i號(hào)分片委員會(huì)處理該交易,對(duì)交易運(yùn)行委員會(huì)內(nèi)分布式一致性算法,驗(yàn)證該交易的合法性,決定該交易是否被添加到區(qū)塊鏈中.

計(jì)算分片使不同的交易以并行的形式被不同的委員會(huì)處理,當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量增多時(shí),可以增加更多的委員會(huì),這樣不同的交易能夠以并行的形式被不同的委員會(huì)同時(shí)處理,交易處理性能隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的增多而增加,進(jìn)而實(shí)現(xiàn)了交易處理的可擴(kuò)展性.

(3)存儲(chǔ)分片(storage sharding)

存儲(chǔ)分片是指不同分片委員會(huì)將處理后的交易分片存儲(chǔ),每個(gè)分片委員會(huì)只負(fù)責(zé)處理本分片對(duì)應(yīng)的交易,將交易放到本分片專屬的交易區(qū)塊鏈上.交易區(qū)塊鏈用于存儲(chǔ)本分片產(chǎn)生的交易歷史或當(dāng)前分片的未花費(fèi)交易池信息.存儲(chǔ)分片將整個(gè)區(qū)塊鏈系統(tǒng)的交易數(shù)據(jù)或未花費(fèi)的交易輸出(unspent transaction output,UTXO)數(shù)據(jù)分片存儲(chǔ),降低了節(jié)點(diǎn)的存儲(chǔ)負(fù)擔(dān).

多委員會(huì)混合共識(shí)機(jī)制流程如圖12所示,其包括選舉委員會(huì)成員、委員會(huì)成員分配、選舉委員會(huì)領(lǐng)導(dǎo)者、運(yùn)行委員會(huì)內(nèi)分布式一致性算法、廣播區(qū)塊和重配置委員會(huì)等步驟.以上步驟與單一委員會(huì)混合共識(shí)機(jī)制相類似,但是存在三個(gè)關(guān)鍵區(qū)別.第一,增添了委員會(huì)成員分配步驟,在選舉委員會(huì)成員后,需要將新選舉的委員會(huì)成員分配到不同委員會(huì)中,為了防止敵手在此過(guò)程中影響成員分配,需要設(shè)置合理的分配策略.第二,在運(yùn)行委員會(huì)內(nèi)分布式一致性算法步驟中,需要考慮到跨片交易的處理,即當(dāng)一個(gè)交易包含多個(gè)輸入且其屬于不同分片時(shí),需要多個(gè)分片協(xié)作完成對(duì)該交易的處理,防止交易雙花攻擊.第三,在廣播區(qū)塊的步驟中,如果采用存儲(chǔ)分片,那么可能每個(gè)分片各自生成和廣播其區(qū)塊鏈,不存在全局的區(qū)塊鏈.

8.2 典型方案分析

(1)ELASTICO

分片共識(shí)機(jī)制由Luu 等人[35]提出.ELASTICO 假設(shè)網(wǎng)絡(luò)模型為同步網(wǎng)絡(luò),敵手模型為n=4f+1,以保證委員會(huì)中誠(chéng)實(shí)節(jié)點(diǎn)數(shù)目達(dá)到2/3 以上.ELASTICO 將參與共識(shí)的n個(gè)節(jié)點(diǎn)分為k組,在一輪中,每一組輸出一個(gè)區(qū)塊協(xié)議輸出一個(gè)總區(qū)塊Br.其中r代表當(dāng)前輪數(shù),i代表委員會(huì)的序號(hào).ELASTICO的流程如下:

圖12 多委員會(huì)混合共識(shí)Figure 12 Multi-committee based hybrid consensus

①節(jié)點(diǎn)身份建立.想要參與共識(shí)的節(jié)點(diǎn)產(chǎn)生公鑰PK和其IP 地址ip,節(jié)點(diǎn)利用上個(gè)時(shí)期產(chǎn)生的隨機(jī)數(shù)ξr?1,尋找工作量證明其中nonce 是指節(jié)點(diǎn)選中的隨機(jī)數(shù),γ表示哈希函數(shù)的輸出一共有γ位,D表示挖礦難度,如D=10 表示w至少前10 位必須為0.滿足條件的nonce 即為工作量證明的解.找到滿足條件w的節(jié)點(diǎn)在全網(wǎng)廣播w.

②節(jié)點(diǎn)分片確認(rèn).ELASTICO 的委員會(huì)包括一個(gè)目錄委員會(huì)和多個(gè)普通委員會(huì),每個(gè)委員會(huì)包括c個(gè)成員.前c個(gè)找到工作量證明的節(jié)點(diǎn)廣播w,進(jìn)入目錄委員會(huì),為后續(xù)節(jié)點(diǎn)提供委員會(huì)分配和委員會(huì)成員身份列表服務(wù).目錄委員會(huì)人滿之后,后找到工作量證明的節(jié)點(diǎn)將工作量證明發(fā)送給目錄委員會(huì)成員,根據(jù)w的后s位進(jìn)入相應(yīng)委員會(huì).當(dāng)所有委員會(huì)成員到達(dá)c之后,目錄委員會(huì)將每個(gè)委員會(huì)成員列表發(fā)送給對(duì)應(yīng)委員會(huì)成員.每個(gè)普通委員會(huì)的成員只需跟本委員會(huì)內(nèi)部成員通信.

③委員會(huì)內(nèi)部共識(shí).每個(gè)委員會(huì)內(nèi)部運(yùn)行PBFT 算法,就本輪自身委員會(huì)內(nèi)部交易集合達(dá)成共識(shí),并將和對(duì)其確認(rèn)簽名發(fā)送至最終委員會(huì).

④廣播確認(rèn)區(qū)塊.最終委員會(huì)收集普通委員會(huì)本輪的區(qū)塊,每個(gè)成員驗(yàn)證區(qū)塊的有效性,驗(yàn)證通過(guò)后,組成本輪的總區(qū)塊Br,其中交易是所有之前收到的有效交易集的并集.然后,最終委員會(huì)內(nèi)運(yùn)行PBFT對(duì)Br達(dá)成共識(shí)，并在全網(wǎng)廣播Br.

⑤隨機(jī)數(shù)生成.最終委員會(huì)運(yùn)行隨機(jī)數(shù)生成協(xié)議,每個(gè)成員首先選擇隨機(jī)數(shù)Ri,并將其哈希值H(Ri)在委員會(huì)內(nèi)廣播,最終委員會(huì)運(yùn)行PBFT 確認(rèn)所有哈希值H(Ri)構(gòu)成的列表S,并在全網(wǎng)廣播S.最終委員會(huì)成員在全網(wǎng)公布自己選取的隨機(jī)數(shù)Ri,網(wǎng)絡(luò)中任意用戶獲得其中c/2+1 個(gè)隨機(jī)數(shù)Ri,并將其異或,便可得到本時(shí)期隨機(jī)數(shù)ξr,用于下個(gè)時(shí)期尋找PoW.每個(gè)用戶接收到的隨機(jī)數(shù)可能不一樣,因此規(guī)定任意c/2+1 個(gè)有效的隨機(jī)數(shù)Ri計(jì)算得到的ξr都是合法的.當(dāng)用戶在下個(gè)時(shí)期找到PoW 的解并上傳時(shí),需要將c/2+1 個(gè)有效的隨機(jī)數(shù)Ri同時(shí)上傳,以便驗(yàn)證其使用的ξr的合法性.

(2)Omniledger

Omniledger 由Kokoris-Kogias 等人[36]提出,其敵手模型為n=4f+1.它解決了ELASTICO 分片共識(shí)中存在的一些問(wèn)題,如當(dāng)惡意節(jié)點(diǎn)占比超過(guò)1/4時(shí),協(xié)議運(yùn)行失敗率高; 節(jié)點(diǎn)在尋找工作量證明時(shí),若通過(guò)工作量證明的后幾位決定進(jìn)入對(duì)應(yīng)的委員會(huì),抗偏置性較差,找到多個(gè)工作量證明的節(jié)點(diǎn)可以選擇進(jìn)入的分片; 跨片交易可能鎖死,導(dǎo)致系統(tǒng)不能正常工作等.

Omniledger 采用UTXO 模型,網(wǎng)絡(luò)中不同分片的節(jié)點(diǎn)只需處理和存儲(chǔ)該分片對(duì)應(yīng)的UTXO 數(shù)據(jù).與此同時(shí),Omniledger 提出了跨片交易防鎖死解決方案.在Omniledger 中,有兩種區(qū)塊鏈,身份區(qū)塊鏈和交易區(qū)塊鏈,身份區(qū)塊鏈用于記錄協(xié)議每個(gè)時(shí)期參與的節(jié)點(diǎn)和其對(duì)應(yīng)的分片信息,每個(gè)時(shí)期更新一次,而一個(gè)時(shí)期能夠產(chǎn)生多個(gè)交易區(qū)塊,每個(gè)分片負(fù)責(zé)產(chǎn)生和維護(hù)自己分片的交易區(qū)塊鏈.Omniledger 協(xié)議的具體過(guò)程如下:

①節(jié)點(diǎn)身份確認(rèn).與ELASTICO 類似,節(jié)點(diǎn)想要參加時(shí)期e的共識(shí),就必須在時(shí)期e?1 尋找工作量證明,找到工作量證明的節(jié)點(diǎn)將身份信息和相應(yīng)的工作量證明廣播,在e?1時(shí)期完成注冊(cè).時(shí)期e?1的領(lǐng)導(dǎo)者收集所有合法注冊(cè)者信息,運(yùn)行委員會(huì)內(nèi)分布式一致性算法,將合法注冊(cè)者信息寫入身份區(qū)塊鏈.

②委員會(huì)領(lǐng)導(dǎo)者選舉.在時(shí)期e開(kāi)始時(shí),通過(guò)密碼抽簽的方式選舉領(lǐng)導(dǎo)者,每個(gè)節(jié)點(diǎn)計(jì)算票據(jù)ticketi;e;v=VRFski(‘‘leader”|confige|v),其中VRFski(·)代表可驗(yàn)證隨機(jī)函數(shù),leader 為VRF 的附加輸入,表示此次計(jì)算的目的是選擇領(lǐng)導(dǎo)者,confige代表時(shí)期e的合法參與者,v代表當(dāng)前視圖編號(hào),i代表節(jié)點(diǎn)序號(hào).在一定的時(shí)間?內(nèi),用戶交換票據(jù)信息,選出數(shù)值最小的ticketi;e;v,將其對(duì)應(yīng)的節(jié)點(diǎn)作為領(lǐng)導(dǎo)者.然后領(lǐng)導(dǎo)者啟動(dòng)隨機(jī)數(shù)生成算法RandHound[127],如果在時(shí)間?內(nèi),RandHound 仍未被啟動(dòng),則視本輪領(lǐng)導(dǎo)者選舉失敗,令v=v+1,開(kāi)始新一輪的領(lǐng)導(dǎo)者選舉,直到RandHound 成功運(yùn)行為止.

③隨機(jī)數(shù)生成.領(lǐng)導(dǎo)者啟動(dòng)RandHound 算法,生成本輪隨機(jī)數(shù)ξr.領(lǐng)導(dǎo)者在全網(wǎng)廣播隨機(jī)數(shù)ξr和其證明.節(jié)點(diǎn)收到信息后驗(yàn)證隨機(jī)數(shù)ξr是否正確生成,若生成正確,則將其作為種子運(yùn)行偽隨機(jī)數(shù)生成器進(jìn)而生成隨機(jī)數(shù),產(chǎn)生隨機(jī)置換,并根據(jù)隨機(jī)置換確認(rèn)本輪所在的分片.

④委員會(huì)內(nèi)分布式一致性算法.每個(gè)委員會(huì)內(nèi)部按照ByzCoin 的方式處理分片內(nèi)部交易.

⑤委員會(huì)成員重配置.為了持續(xù)處理交易,Omniledger 設(shè)置合理挖礦難度,使得每次重配置,每個(gè)委員會(huì)只將部分節(jié)點(diǎn)替換,替換節(jié)點(diǎn)數(shù)量不超過(guò)總?cè)藬?shù)的1/3.在節(jié)點(diǎn)替換過(guò)程中,利用本輪隨機(jī)數(shù)決定現(xiàn)任委員會(huì)中被替換的節(jié)點(diǎn).

由于交易的分片存儲(chǔ),當(dāng)交易存在多個(gè)輸入且屬于不同分片時(shí),需要多個(gè)分片協(xié)作完成對(duì)交易的處理.Omniledger 提出跨片交易解決方案,利用原子性跨片交易防止跨片交易鎖死,主要流程如下:

①初始化.客戶端上傳交易,交易的輸入分片可能存在多個(gè),假設(shè)為IS1和IS2,輸出分片假設(shè)為OS.

②鎖定.每個(gè)分片的領(lǐng)導(dǎo)者驗(yàn)證交易輸入是否屬于當(dāng)前分片的UTXO,如果驗(yàn)證通過(guò),則提供交易的接受證明(proof of acceptance,PoA),即交易輸入在本分片UTXO 中的默克爾樹(shù)路徑,并將該交易輸入設(shè)置為鎖定狀態(tài),后續(xù)其他想要花費(fèi)該交易輸入的交易將被拒絕.如果驗(yàn)證未通過(guò),則提供交易的拒絕證明(proof of rejection,PoR).

③解鎖.解鎖分為以下兩種情況:第一種是解鎖至提交狀態(tài),如果所有輸入分片領(lǐng)導(dǎo)者都提供PoA,那么交易可以被提交,客戶端提交交易及其所有輸入的PoA.輸出分片OS 收到交易后,驗(yàn)證所有交易的合法性,驗(yàn)證通過(guò)后將該交易加入到輸出分片的下個(gè)區(qū)塊.第二種是解鎖至取消狀態(tài),如果有一個(gè)輸入分片領(lǐng)導(dǎo)者提供了PoR,那么客戶端創(chuàng)建“取消交易”,包含該交易對(duì)應(yīng)的PoR.所有輸入分片領(lǐng)導(dǎo)者收到“取消交易” 后,將原交易的輸入解鎖至可用狀態(tài).

Omniledger 解決了ELASTICO 存在的許多問(wèn)題,在分片數(shù)量為16 個(gè)且每個(gè)分片人數(shù)為70 人時(shí),能夠達(dá)到5000 tps 的交易吞吐率,且交易吞吐率隨網(wǎng)絡(luò)中節(jié)點(diǎn)增多而增加.文獻(xiàn)[128]對(duì)Omniledger 使用的隨機(jī)數(shù)生成算法改進(jìn),采用公開(kāi)可驗(yàn)證秘密分享,確保了隨機(jī)數(shù)的不可預(yù)測(cè)性、抗偏置性和公開(kāi)可驗(yàn)證性,并且保證了隨機(jī)數(shù)的持續(xù)生成.

(3)Chainspace

Chainspace 由Al-Bassam 等人[37]提出,其敵手模型為n=3f+1.Chainspace 在分片的基礎(chǔ)上,構(gòu)建了智能合約應(yīng)用平臺(tái).任何人能夠發(fā)布智能合約,智能合約的參與者可以是多個(gè)用戶.Chainspace中存在系統(tǒng)智能合約CSCoin,為整個(gè)協(xié)議的運(yùn)行設(shè)定一定的安全參數(shù).Chainspace 將智能合約的執(zhí)行和驗(yàn)證步驟分離開(kāi)來(lái),并且提出了跨片交易處理的原子承諾協(xié)議(sharded Byzantine atomic commit,SBAC).Chainspace 將智能合約和交易稱為“對(duì)象(objects)”,每個(gè)對(duì)象由不同的分片分別執(zhí)行、處理和驗(yàn)證.S-BAC 的實(shí)質(zhì)是BFT和原子承諾(atomic commit)的結(jié)合.Chainspace 中對(duì)交易或智能合約的處理過(guò)程如圖13所示.

圖13 Chainspace 共識(shí)流程圖Figure 13 Consensus mechanism of Chainspace

①準(zhǔn)備(prepare).用戶向輸入分片發(fā)送準(zhǔn)備消息prepare(tx),假設(shè)交易tx 有兩個(gè)輸入和一個(gè)輸出,其對(duì)應(yīng)的分片分別為分片1、分片2和分片3.

②處理準(zhǔn)備消息(process prepare).輸入分片1和分片2 的節(jié)點(diǎn)收到prepare(tx)消息后,鎖定交易tx 的輸入,在各自的委員會(huì)內(nèi)部通過(guò)運(yùn)行拜占庭算法處理準(zhǔn)備消息,如果交易tx 合法,即輸入未被花費(fèi)且沒(méi)有其他的交易使用該輸入,輸入分片向其他節(jié)點(diǎn)廣播承諾消息prepared(tx,commit).如果交易tx 不合法,未通過(guò)拜占庭算法,則廣播消息prepared(tx,abort).

③處理準(zhǔn)備完成的消息(process prepared).所有分片之間進(jìn)行交互,如果所有分片在上一步廣播的都是prepared(tx,commit)消息,則對(duì)交易tx 達(dá)成最終共識(shí),廣播accept(tx,commit)消息.如果分片中有大于等于一個(gè)分片提交了prepared(tx,abort)消息,則對(duì)交易tx 的共識(shí)失敗,廣播accept(tx,abort)消息.

④處理接受消息(process accept).當(dāng)上一步中有分片廣播accept(tx,commit)時(shí),交易tx 的輸出分片運(yùn)行委員會(huì)內(nèi)分布式一致性算法,將tx 添加到該分片中.當(dāng)分片廣播accept(tx,abort)時(shí),所有分片將交易tx 的輸入解鎖,放棄交易tx.

Chainspace 實(shí)現(xiàn)了交易和智能合約的通信分片和計(jì)算分片.在15 個(gè)委員會(huì),每個(gè)委員會(huì)4 個(gè)節(jié)點(diǎn)的情況下,其交易吞吐量為350 tps.

(4)RapidChain

RapidChain 由Zamani、Movahedi和Raykova[38]提出.RapidChain 實(shí)現(xiàn)了計(jì)算分片、通信分片和存儲(chǔ)分片,主要模塊包括啟動(dòng)(bootstrap)、共識(shí)和重配置.RapidChain 敵手模型為n=3f+1,網(wǎng)絡(luò)模型為部分同步網(wǎng)絡(luò).協(xié)議的具體流程如下:

①啟動(dòng).啟動(dòng)階段是指生成創(chuàng)世區(qū)塊和初始委員會(huì)的階段.在之前的區(qū)塊鏈中,如比特幣等,采用可信啟動(dòng)來(lái)實(shí)現(xiàn).RapidChain 無(wú)需可信啟動(dòng),首先在所有參與節(jié)點(diǎn)中,利用隨機(jī)圖(random graph)選舉出根群組(root group),然后利用根群組運(yùn)行分布式隨機(jī)數(shù)生成協(xié)議,生成參考委員會(huì).參考委員會(huì)負(fù)責(zé)生成其他k個(gè)普通委員會(huì).在RapidChain 中,啟動(dòng)階段只需運(yùn)行一次,不需要任何可信第三方和可信啟動(dòng)的存在,便能夠完成協(xié)議的初始化.

②時(shí)期內(nèi)共識(shí).協(xié)議分時(shí)期運(yùn)行,每個(gè)時(shí)期分為多個(gè)輪,每一輪中,委員會(huì)中運(yùn)行Ren 等人[129]提出的實(shí)用同步拜占庭容錯(cuò)協(xié)議,敵手模型為n=2f+1,此階段假設(shè)網(wǎng)絡(luò)模型為同步模型.

③重配置.時(shí)期之間需要運(yùn)行委員會(huì)重配置,節(jié)點(diǎn)通過(guò)尋找PoW 加入委員會(huì),為了抵抗自私挖礦攻擊,在PoW 中嵌入每一輪產(chǎn)生的隨機(jī)數(shù).重配置采用了有界布谷鳥(niǎo)規(guī)則(bounded Cuckoo rule),即新節(jié)點(diǎn)盡量替換掉原本委員會(huì)中不活躍的節(jié)點(diǎn).

RapidChain 在網(wǎng)絡(luò)層中,采用消息擴(kuò)散算法(information dispersal algorithms,IDA)代替?zhèn)鹘y(tǒng)區(qū)塊鏈網(wǎng)絡(luò)采用的八卦通信協(xié)議(gossip protocol).發(fā)送者利用糾錯(cuò)編碼,將區(qū)塊拆分為小區(qū)塊后傳播,接收者接收到一定數(shù)量的小區(qū)塊后可以恢復(fù)原始區(qū)塊.采用IDA 傳播方式能夠?qū)^(qū)塊傳播速度提升約5.3 倍.

RapidChain 對(duì)于跨片交易的處理如下:用戶將交易 tx 發(fā)送至網(wǎng)絡(luò)中任意節(jié)點(diǎn),收到 tx 的節(jié)點(diǎn)將其發(fā)送至 tx 對(duì)應(yīng)的輸出委員會(huì)Cout.Cout將交易 tx 拆分,假設(shè)交易 tx 包括 2 個(gè)輸入I1和I2,及 1 個(gè)輸出O,則將交易tx 拆分為3 個(gè)新交易:并且令和屬于Cout.Cout成員根據(jù)交易和輸入判斷所屬委員會(huì)Cin,將對(duì)應(yīng)交易發(fā)送至Cin.Cin驗(yàn)證和的合法性,通過(guò)后將對(duì)應(yīng)的tx1或tx2添加到其區(qū)塊,最后Cout將tx3收入自身區(qū)塊.

由于時(shí)期內(nèi)共識(shí)采用同步網(wǎng)絡(luò)模型,交易確認(rèn)時(shí)延與網(wǎng)絡(luò)真實(shí)時(shí)延無(wú)關(guān),導(dǎo)致交易確認(rèn)不能滿足快速響應(yīng)特性.但 RapidChain 協(xié)議其他部分采用部分同步網(wǎng)絡(luò)模型,均能滿足快速響應(yīng)特性.RapidChain采用一定措施,使得其時(shí)期內(nèi)共識(shí)也能夠接近快速響應(yīng)特性.

(5)其他分片共識(shí)機(jī)制

Manuskin、Mirkin和Eyal[130]提出了Ostraka.Ostraka 采用了節(jié)點(diǎn)差異化環(huán)境模型,即認(rèn)為每個(gè)節(jié)點(diǎn)處理交易的能力是不同的.在Ostraka 中,每個(gè)節(jié)點(diǎn)處理所有的交易.Ostraka 能夠抵抗拒絕服務(wù)攻擊,交易處理能力隨網(wǎng)絡(luò)規(guī)模的擴(kuò)大而線性增加.Dang 等人[131]采用數(shù)據(jù)庫(kù)分片的方式來(lái)實(shí)現(xiàn)區(qū)塊鏈的可擴(kuò)展性,并利用可信硬件Intel SGX 產(chǎn)生的可信隨機(jī)數(shù)將節(jié)點(diǎn)分配到不同分片中,確保了整個(gè)協(xié)議的活性和安全性.

8.3 綜合分析

分片共識(shí)在實(shí)現(xiàn)交易處理可擴(kuò)展性的同時(shí),引入了一些新的問(wèn)題,主要包括如下幾點(diǎn).

第一,跨片交易處理.包含多個(gè)輸入的交易,由于其輸入大概率分布在不同的分片中,因此需要多個(gè)分片共同協(xié)作安全和高效地處理交易.在處理過(guò)程中,需要防止雙花攻擊、重放攻擊[132]和交易鎖死,并且采用一定的方式提升交易的處理速度;

第二,委員會(huì)人數(shù)動(dòng)態(tài)管理.分片共識(shí)中,不同分片對(duì)應(yīng)的委員會(huì)人數(shù)可能存在一定的差異,當(dāng)兩個(gè)委員會(huì)之間交流過(guò)于頻繁時(shí),可以考慮將其合并為一個(gè)委員會(huì),提高交易處理速度等;

第三,惡意委員會(huì)檢測(cè)與恢復(fù).如果新加入成員分配到不同委員會(huì)的過(guò)程受到敵手的偏置,則可能造成某些委員會(huì)中惡意成員個(gè)數(shù)超過(guò)限制,敵手可能進(jìn)一步控制委員會(huì).如何檢測(cè)惡意委員會(huì)并建立恢復(fù)機(jī)制是未來(lái)需要研究的重要問(wèn)題.

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

(1)能力證明機(jī)制(proof of capacity)

能力證明是指根據(jù)參與者能夠使用的硬盤空間大小作為標(biāo)準(zhǔn),選出區(qū)塊的生產(chǎn)者.Miller 等人[133]提出了 Permacoin,要求參與者有能力存儲(chǔ)大文件的一部分.Park 等人[60]提出了 Spacecoin,采用非交互式空間證明(proof of space)達(dá)成共識(shí).

(2)消逝時(shí)間證明(proof of elapsed time)

消逝時(shí)間證明是基于硬件芯片執(zhí)行某個(gè)命令的等待時(shí)間來(lái)實(shí)現(xiàn)的,其實(shí)質(zhì)是利用可信硬件產(chǎn)生隨機(jī)數(shù)來(lái)決定下一個(gè)區(qū)塊生產(chǎn)者.Hyperledger 使用英特爾可信芯片 Intel SGX 中的 “飛地” 模塊,參與者在發(fā)布?jí)K之前都需要向飛地獲取一個(gè)隨機(jī)的等待時(shí)間,等待時(shí)間最短的節(jié)點(diǎn)被選為領(lǐng)導(dǎo)節(jié)點(diǎn).Zhang 等人[134]提出了資源高效利用挖礦(resource-efficient mining,REM),同樣采用可信硬件來(lái)計(jì)算PoW,用時(shí)最短節(jié)點(diǎn)將被選為領(lǐng)導(dǎo)節(jié)點(diǎn).

(3)融入知識(shí)證明的工作量證明(entangled proof of work and knowledge,EWoK)

Armknecht 等人[61]提出了 EWoK,主要將 PoW 與 PoK 結(jié)合,鼓勵(lì)節(jié)點(diǎn)對(duì)于區(qū)塊鏈系統(tǒng)歷史數(shù)據(jù)的存儲(chǔ).節(jié)點(diǎn)先通過(guò)工作量證明找到 PoW 的解,然后證明節(jié)點(diǎn)本地存儲(chǔ)了區(qū)塊鏈某個(gè)分片的完整數(shù)據(jù),完成證明的節(jié)點(diǎn)成為出塊者,EWoK 通過(guò)鼓勵(lì)節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)來(lái)增強(qiáng)系統(tǒng)的安全性.

10 未來(lái)研究方向

區(qū)塊鏈共識(shí)機(jī)制是區(qū)塊鏈技術(shù)的核心,未來(lái)的發(fā)展趨勢(shì)主要有以下幾點(diǎn):

第一,安全層面.設(shè)計(jì)并完善可證明安全的區(qū)塊鏈共識(shí)機(jī)制,如基于PoS 的共識(shí)機(jī)制,解決PoS 共識(shí)機(jī)制面臨的安全威脅; 將經(jīng)典分布式一致性算法與區(qū)塊鏈技術(shù)結(jié)合,利用委員會(huì)實(shí)現(xiàn)強(qiáng)一致性,解決委員會(huì)重配置的安全問(wèn)題;

第二,擴(kuò)容層面.利用分片技術(shù),通過(guò)計(jì)算分片、通信分片和存儲(chǔ)分片,實(shí)現(xiàn)交易處理的可擴(kuò)展性,解決跨片交易問(wèn)題; 利用DAG 技術(shù),采用并行區(qū)塊的架構(gòu),使得同一時(shí)間內(nèi)區(qū)塊鏈能夠容納更多的交易;

第三,啟動(dòng)層面.通過(guò)安全多方計(jì)算等密碼技術(shù)在非可信環(huán)境下完成協(xié)議自啟動(dòng),解決區(qū)塊鏈協(xié)議的初始化問(wèn)題; 通過(guò)對(duì)區(qū)塊鏈歷史數(shù)據(jù)的合理裁剪,使新加入節(jié)點(diǎn)能夠快速獲取當(dāng)前區(qū)塊鏈狀態(tài),參與共識(shí)運(yùn)行,解決新加入節(jié)點(diǎn)的啟動(dòng)問(wèn)題;

第四,激勵(lì)層面.設(shè)計(jì)合理可行的獎(jiǎng)勵(lì)和懲罰機(jī)制,以理性用戶作為出發(fā)點(diǎn),激勵(lì)用戶以誠(chéng)實(shí)行為參與共識(shí)機(jī)制的運(yùn)行和維護(hù); 合理懲罰惡意用戶,同時(shí)給予舉報(bào)者一定的獎(jiǎng)勵(lì).