區(qū)塊鏈共識機制研究綜述*

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

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

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

1 引言

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

1.1 區(qū)塊鏈概述

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

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

1.2 共識概述

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

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

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

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

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

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

對于區(qū)塊鏈共識,主要的評價標準有如下幾點.

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

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

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

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

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

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

1.3 本文貢獻

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

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

(2)總結(jié)了共識機制的評判標準,包括安全性、交易吞吐率、可擴展性、交易確認時間、去中心化和資源占用等內(nèi)容.

(3)分類研究了共識機制的系統(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)有共識機制,分析了各類共識機制的基本原理、典型方案和優(yōu)缺點.

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

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

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

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

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

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

(5)分析了未來共識機制的研究熱點和發(fā)展方向.

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

1.4 相關(guān)工作

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

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

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

2 模型和定義

2.1 定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相比于弱一致性,強一致性具有以下優(yōu)點:

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

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

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

2.2 模型分類

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

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

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

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

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

2.2.2 腐化模型

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

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

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

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

2.2.3 敵手模型

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

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

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

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

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

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

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

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

3.1 概念

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

3.2 典型方案分析

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

(1)Paxos

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

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

(2)PBFT

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

PBFT 的分布式共識達成過程如下:

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

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

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

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

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

PBFT 的分布式共識過程如圖1 所示:

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

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

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

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

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

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

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

(3)Hot-Stuff

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

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

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

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

對于每個消息,如對提議a(1),PBFT 中使用完整的2f+1 個簽名作為其準備憑證CC(a(1)),而Hot-Stuff 中使用門限簽名技術(shù),將一個門限簽名作為準備憑證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é)議,實現(xiàn)了快速響應(yīng)特性.交易確認時延為2?+O(δ),?表示網(wǎng)絡(luò)時延上限,δ表示網(wǎng)絡(luò)真實時延.

(4)SBFT

可擴展拜占庭容錯協(xié)議(scalable Byzantine fault tolerance,SBFT)由Golan-Gueta 等人[12]提出.SBFT 主要解決拜占庭容錯協(xié)議在應(yīng)用到區(qū)塊鏈中的去中心化和擴容問題,SBFT 的敵手模型n=3f+1,能夠允許200 多個節(jié)點同時完成共識.SBFT 利用領(lǐng)導(dǎo)者作為信息、簽名的收集者,采用門限簽名降低通信復(fù)雜度.在PBFT 中,每一輪的投票,節(jié)點需要向網(wǎng)絡(luò)中其他節(jié)點廣播投票,并且收集其他節(jié)點的投票,而SBFT 利用領(lǐng)導(dǎo)者收集每一輪投票,收集到的簽名數(shù)量達到門限要求以后,領(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é)點失效的最小化異步模型系統(tǒng)中，不存在一個可以解決一致性問題的確定性共識機制.Rabin[66]和Ben-Or[67]利用所有節(jié)點可見的隨機數(shù)發(fā)生器實現(xiàn)了異步網(wǎng)絡(luò)中的分布式一致性協(xié)議,敵手對于隨機數(shù)發(fā)生器生成的隨機數(shù)是不可預(yù)知的,隨機數(shù)發(fā)生器成為了異步網(wǎng)絡(luò)共識中常用的工具.

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

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

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

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

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

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

驗證的異步拜占庭一致算法(validated asynchronous Byzantine agreement,VABA)由Abraham、Malkhi和Spiegelman[52]提出.在異步網(wǎng)絡(luò)環(huán)境下,VABA 實現(xiàn)了多值拜占庭一致算法,敵手模型為n=3f+1.VABA 基于隨機預(yù)言模型,在每次共識過程中,采用多個并行的領(lǐng)導(dǎo)者提議,從中隨機選取一個作為最終結(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é)議中敵手數(shù)量為f,在一輪中就某個數(shù)值v運行分布式共識達成算法,敵手為了擾亂協(xié)議執(zhí)行,可能對數(shù)值v′投票.此時協(xié)議需要規(guī)定對某個數(shù)值的投票數(shù)必須達到某個法定人數(shù),如2f+1(假設(shè)敵手模型為n=3f+1),才能確保一輪共識運行完畢后最多對一個特定值達成共識.因為假設(shè)v′=v,且v′跟v同樣獲得了2f+1 的投票,此時對于二者的投票必然存在交集,其人數(shù)至少為f+1,即這f+1 個節(jié)點同時對v′和v投票.由于敵手個數(shù)最多為f,所以此f+1 個節(jié)點至少包含一個誠實節(jié)點,這與誠實節(jié)點不能模棱兩可的假設(shè)相矛盾.拜占庭法定人數(shù)系統(tǒng)在同步網(wǎng)絡(luò)環(huán)境中達成了共識.

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

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

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

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

3.3 綜合分析

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

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

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

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

4 授權(quán)共識機制

4.1 概念

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

4.2 典型方案

(1)Hyperledger

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

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

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

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

(2)DFINITY

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

DFINITY 共識機制具體運行流程如下:

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

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

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

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

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

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

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

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

(3)PaLa

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

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

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

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

4.3 綜合分析

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

5 基于工作量證明的共識機制

5.1 概念

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

5.2 典型方案分析

(1)比特幣

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

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

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

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

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

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

(2)以太坊

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

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

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

以太坊中,區(qū)塊出塊間隔大約為15 秒,短暫的區(qū)塊間隔時間造成了以太坊區(qū)塊鏈容易產(chǎn)生分叉.如果某個礦池算力較大,且由于節(jié)點數(shù)量多導(dǎo)致其與網(wǎng)絡(luò)中其他節(jié)點的連接數(shù)量更多,那么其產(chǎn)生的區(qū)塊在網(wǎng)絡(luò)中傳播速度較快.當(dāng)出現(xiàn)分叉時,其他算力較小的礦池或單一節(jié)點只能淪為被裁剪掉的分叉,導(dǎo)致這些節(jié)點失去了挖礦的動力,進而影響到整個以太坊系統(tǒng)的安全.為了解決上述問題,以太坊調(diào)整了區(qū)塊結(jié)構(gòu).在比特幣中,只有在主鏈上挖礦得到區(qū)塊的礦工才會得到酬金,也只有主鏈的區(qū)塊能夠被接下來的區(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

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

(3)Bitcoin-NG

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

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

圖5 Bitcoin-NG 共識機制Figure 5 Consensus mechanism of Bitcoin-NG

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

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

(4)FruitChains

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

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

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

在FruitChains 中,交易是與水果綁定的,新挖到的水果被放入到有效水果集(fruit set)F中,有效水果集隨著水果的挖出和使用不斷更新,新挖到的區(qū)塊負責(zé)將F中的水果放入到區(qū)塊中,此時敵手如果針對底層區(qū)塊采取自私挖礦或是扣塊攻擊,便毫無意義,因為包含交易的水果會被其他誠實節(jié)點產(chǎn)生的區(qū)塊收錄.因此FruitChains 防止了自私挖礦攻擊,實現(xiàn)了公平性.

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

圖6 FruitChains 共識機制Figure 6 Consensus mechanism of FruitChains

(5)GHOST

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

(6)Spectre

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

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

5.3 綜合分析

采用工作量證明的共識機制主要面臨以下幾個問題:

(1)巨大的能源消耗

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

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

(2)存在安全隱患

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

1)日蝕攻擊(eclipse attack)

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

2)雙花攻擊(double spending)

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

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

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

3)自私挖礦(selfish mining)

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

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

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

6.1 概念

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

6.2 典型方案分析

(1)PPCoin

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

(2)Casper FFG

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

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

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

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

(3)Ouroboros 系列

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

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

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

圖8 Ouroboros 共識機制流程圖Figure 8 Consensus mechanism of Ouroboros

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

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

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

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

(4)Snow White

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

Snow White 采用的網(wǎng)絡(luò)模型為睡眠模型(sleepy model)[116],即節(jié)點不會保持永久在線,可能在某段時間內(nèi)在線,也可能在某段時間內(nèi)離線,間斷參與共識.該模型中節(jié)點的狀態(tài)更加符合現(xiàn)實網(wǎng)絡(luò)中節(jié)點的狀態(tài).Snow White 采用與FruitChains 類似的激勵制度,并且同樣采用區(qū)塊和水果同時生成的挖礦機制,交易放在水果中,水果放在區(qū)塊中,將連續(xù)幾個區(qū)塊的獎勵和其中包含的交易費平均分給區(qū)塊對應(yīng)的出塊者,實現(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ū)塊,該委托人將會被除名,所有權(quán)益持有者選出新的超級節(jié)點將其替代.比特股(Bitshares)以DPoS 為原理實現(xiàn).DPoS 以選舉委托人的形式實現(xiàn)共識,帶來了嚴重的中心化問題.

6.3 綜合分析

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

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

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

(2)打磨攻擊(grinding attack)

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

(3)長程攻擊(long range attack)

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

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

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

7 采用單一委員會的混合共識機制

7.1 概念

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

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

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

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

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

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

采用單一委員會的混合共識機制流程如圖9所示.

圖9 單一委員會混合共識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é)點,對其完成身份認證后通過鏈一致(chain agreement,CA)算法,來完成最終區(qū)塊的生成,鏈一致算法通常采用PBFT 來實現(xiàn).PeerCensus 允許加入新節(jié)點,新節(jié)點需要通過委員會的共識決定才能加入到委員會中.PeerCensus 的委員會管理存在一定問題,它采用離開檢測機制來判斷節(jié)點是否離開.正常節(jié)點通過發(fā)送ping 消息,如果未收到相應(yīng)節(jié)點的回復(fù),則判斷其離線,然后正常節(jié)點發(fā)起對該離線節(jié)點的“ 離開” 提議,提議通過委員會共識后,委員會才完成重配置.這樣一來,惡意用戶能夠通過不斷制造離開提議的方式降低整個系統(tǒng)的運行效率.

(2)ByzCoin

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

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

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

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

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

(3)Solida

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

Solida 共識機制的流程如下:

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

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

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

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

(4)Hybrid consensus

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

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

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

(5)Thunderella

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

圖11 Thunderella 共識機制流程圖Figure 11 Consensus mechanism of Thunderella

Thunderella 共識機制的流程如下:

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

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

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

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

寬限期包括k個區(qū)塊,寬限期未結(jié)束時,節(jié)點輸出其認同的最長交易幸運序列; 寬限期結(jié)束后,節(jié)點輸出所有已確認和未確認交易,進入底層區(qū)塊鏈確認期.

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

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

(6)Algorand

Algorand 由Gilad 等人[34]提出.Algorand 是將PoS 與經(jīng)典分布式一致性算法結(jié)合的混合共識機制,其敵手模型為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ū)塊的序列號,即當(dāng)前的輪數(shù),PAYr是指當(dāng)前時間內(nèi)發(fā)生的交集集合,Qr?1是指上一輪產(chǎn)生的隨機種子,H(Br?1)是指上一個區(qū)塊的哈希值,?r是指當(dāng)前輪的領(lǐng)導(dǎo)者,SIG?r(Qr?1)是指?r利用自身私鑰對Qr?1計算的數(shù)字簽名.

Algorand 算法的流程如下:

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

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

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

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

7.3 綜合分析

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

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

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

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

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

8 采用多委員會的混合共識機制

8.1 概念

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

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

(1)通信分片(communication sharding)

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

(2)計算分片(computation sharding)

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

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

(3)存儲分片(storage sharding)

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

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

8.2 典型方案分析

(1)ELASTICO

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

圖12 多委員會混合共識Figure 12 Multi-committee based hybrid consensus

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

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

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

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

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

(2)Omniledger

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

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

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

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

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

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

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

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

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

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

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

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

(3)Chainspace

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

圖13 Chainspace 共識流程圖Figure 13 Consensus mechanism of Chainspace

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

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

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

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

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

(4)RapidChain

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

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

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

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

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

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

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

(5)其他分片共識機制

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

8.3 綜合分析

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

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

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

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

9 其他共識機制

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

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

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

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

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

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

10 未來研究方向

區(qū)塊鏈共識機制是區(qū)塊鏈技術(shù)的核心,未來的發(fā)展趨勢主要有以下幾點:

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

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

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

第四,激勵層面.設(shè)計合理可行的獎勵和懲罰機制,以理性用戶作為出發(fā)點,激勵用戶以誠實行為參與共識機制的運行和維護; 合理懲罰惡意用戶,同時給予舉報者一定的獎勵.