區塊鏈共識機制研究綜述*

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

1.北京航空航天大學 網絡空間安全學院,北京100191

2.北京航空航天大學 合肥創新研究院,合肥230012

1 引言

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

1.1 區塊鏈概述

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

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

1.2 共識概述

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

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

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

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

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

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

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

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

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

(3)可擴展性.可擴展性是指網絡處理交易的性能是否能夠隨著節點的增多而增強,其關注的是網絡處理能力的可增長性.可擴展性一般通過對網絡實施分片(sharding)來實現,將整個網絡節點分為不同的分片,每個分片并行處理分片內部的數據.

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

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

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

1.3 本文貢獻

本文主要研究了以下內容:

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

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

(3)分類研究了共識機制的系統模型,將網絡模型分為同步網絡、部分同步網絡和異步網絡,將腐化模型分為靜態敵手、溫和敵手和適應性敵手,將敵手模型分為n=2f+1、n=3f+1和n=4f+1,指出了各類模型之間的區別.

(4)分類研究了現有共識機制,分析了各類共識機制的基本原理、典型方案和優缺點.

經典分布式共識主要在節點之間完成狀態機復制,實現一致性和活性.典型方案包括Paxos、PBFT、Hot-Stuff[11]、SBFT[12]、MinBFT[13]和Honey Badger BFT[14]等;

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

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

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

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

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

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

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

1.4 相關工作

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

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

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

2 模型和定義

2.1 定義

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

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

另外,Pass和Shi[32]提出了狀態機復制的快速響應特性.

定義2(快速響應特性)快速響應特性(responsiveness)是指交易確認時間與網絡真實時延δ有關,與網絡時延上限?無關.

狀態機復制過去經常被用于大型數據庫的同步,如Google和Facebook 將狀態機復制用于其數據庫核心部分的同步.

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

定義4(非授權共識)非授權共識(permissionless consensus)是指在非授權網絡中,節點不需要經過身份認證,網絡中節點數量隨時變化,節點無法獲知所有參與者節點數量和身份等信息.所有節點通過一定的共識機制實現非授權網絡中的狀態機復制.非授權共識同樣需要滿足一致性和活性.

非授權網絡與授權網絡的區別主要有以下兩點:第一,任何節點在任意時間都能隨時加入或退出非授權網絡,不需要完成身份認證; 第二,參與非授權共識的節點數目隨時變化,不可預知.

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

公共賬本的概念是對狀態機復制的延伸,狀態機復制在過去僅僅被用在授權網絡中完成數據的同步,而公共賬本意味著在非授權網絡中,實現公開透明、任何節點能夠隨時訪問、添加信息的公共的賬本.

公共賬本應當滿足以下兩個安全特性[51].

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

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

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

表1 共識機制總結Table 1 Summary of consensus mechanisms

共同前綴特性可以這樣理解,誠實節點產生的鏈最終會彼此一致,且誠實節點已經確定的鏈不會被改寫.

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

鏈質量屬性是指連續的區塊中必定有足夠比例的區塊由誠實用戶產生.

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

此外,區塊鏈特性還包括公平性.

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

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

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

相比于弱一致性,強一致性具有以下優點:

(1)區塊鏈無分叉,通過運行分布式一致性算法,實現狀態機復制,節點不需要浪費大量算力;

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

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

2.2 模型分類

以下分別介紹共識機制的網絡模型、腐化模型和敵手模型.

2.2.1 網絡模型

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

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

定義16(異步網絡)異步網絡(asynchronous network)是指敵手能夠任意拖延誠實用戶的消息或將其打亂順序,只要保證最終誠實用戶的消息能夠到達彼此.

2.2.2 腐化模型

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

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

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

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

2.2.3 敵手模型

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

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

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

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

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

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

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

3 經典分布式共識機制

3.1 概念

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

3.2 典型方案分析

3.2.1 部分同步網絡分布式一致算法

(1)Paxos

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

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

(2)PBFT

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

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

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

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

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

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

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

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

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

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

當主節點(主節點)超時無響應或其他節點大多數認為其存在問題時,會進入視圖轉換過程.PBFT的視圖轉換過程如下:

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

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

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

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

(3)Hot-Stuff

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

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

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

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

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

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

(4)SBFT

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

3.2.2 異步網絡分布式一致性算法

Fischer、Lynch和Paterson[65]提出了FLP 不可能定理,在網絡可靠，但允許節點失效的最小化異步模型系統中，不存在一個可以解決一致性問題的確定性共識機制.Rabin[66]和Ben-Or[67]利用所有節點可見的隨機數發生器實現了異步網絡中的分布式一致性協議,敵手對于隨機數發生器生成的隨機數是不可預知的,隨機數發生器成為了異步網絡共識中常用的工具.

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

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

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

假設網絡中共n個節點,每一輪共識就大小為B的數據運行共識機制.Honey Badger BFT 算法的主要過程如下:

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

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

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

3.2.3 同步網絡分布性一致算法

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

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

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

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

Malkhi、Nayak和Ren 等人[71]提出了Flexible BFT,在同步網絡中實現了狀態機復制.Flexible BFT 只有在承諾步驟要求網絡是同步的,即只在承諾步驟中使用網絡延時參數,在其他步驟不需要網絡同步的假設.

3.3 綜合分析

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

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

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

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

4 授權共識機制

4.1 概念

授權共識機制是指在授權網絡中,節點首先經過身份認證加入網絡中,然后在節點之間運行某種分布式一致性算法,實現狀態機復制,對數據達成共識,進而生成和維護授權網絡內部的區塊鏈.授權共識機制產生的區塊鏈不同于比特幣之類的“公鏈”,節點只有在獲得身份認可之后才能加入授權網絡中,進入到授權網絡內部,從而完成共識過程.

4.2 典型方案

(1)Hyperledger

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

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

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

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

(2)DFINITY

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

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

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

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

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

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

⑤區塊最終確認.區塊最終確認是指網絡中的所有節點在觀察到已公示區塊達到一定的深度時,將其確定為最終確認區塊,其中的交易也完成最終確認.

⑥下一任委員會工作.在當前時期結束后,根據本時期隨機數ξr隨機選取下一任委員會.

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

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

(3)PaLa

PaLa 由Chan、Pass和Shi[18]提出,PaLa 實現了授權網絡中的快速共識.PaLa 的網絡模型為部分同步網絡,敵手模型是n=3f+1.

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

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

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

4.3 綜合分析

授權共識機制中的所有節點在參與共識前,必須要經過身份注冊.授權共識主要適用于企業、組織之間的聯盟等,在聯盟節點參與共識的情況下,能夠實現較高的交易吞吐率.授權共識中,網絡處理交易的性能受到參與節點計算能力的影響較大.目前,由于授權共識的應用場景大多為聯盟之間的數據處理和存儲,授權共識需要考慮智能合約的處理問題,因此授權網絡中節點分工的明確化和數據處理的模塊化顯得越來越重要.

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

5.1 概念

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

5.2 典型方案分析

(1)比特幣

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

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

①節點獲取挖礦難度、交易信息.比特幣中,節點能夠自由加入、退出網絡,不需要完成身份注冊.節點在挖礦前,首先獲取當前工作量證明難度D,并且收集本時期內網絡中產生的交易,將交易排列成默克爾樹形式,并計算交易構成的默克爾樹樹根Merkle.與此同時,根據比特幣的最長鏈原則,選取合適的區塊鏈,獲取其最末端區塊哈希值Ar?1.

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

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

Garay、Kiayias和Leonardos[51]提出了比特幣區塊鏈骨干協議,分析了其基本安全特性.Pass、Seeman和Shelat[83]分析了區塊鏈在部分同步網絡環境下的安全性.根據上述文獻定義,區塊鏈具有共同前綴、鏈質量、鏈增長、公平性、強一致性和弱一致性等特性.

(2)以太坊

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

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

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

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

圖4 以太坊區塊鏈結構Figure 4 Structure of Blockchain in Ethereum

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

(3)Bitcoin-NG

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

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

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

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

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

(4)FruitChains

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

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

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

FruitChains 中,區塊被定義為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是指要被包含到區塊中的有效水果集合.當哈希值h的前128 位小于區塊挖礦難度DB時,表示節點成功挖到了區塊,此時的隨機數η便是工作量證明的解.

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

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

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

(5)GHOST

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

(6)Spectre

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

IOTA[55]、Byteball[90]]和Hashgraph[91]同樣采用DAG 結構處理數據.Conflux[92]在DAG 結構的基礎上,引入區塊排序算法,將所有區塊確定性排列為單鏈結構,不產生分叉,充分利用每個區塊,將交易吞吐率提升到每秒鐘數千次.

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

5.3 綜合分析

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

(1)巨大的能源消耗

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

圖7 DAG 結構示例圖Figure 7 Structure of block using DAG

(2)存在安全隱患

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

1)日蝕攻擊(eclipse attack)

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

2)雙花攻擊(double spending)

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

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

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

3)自私挖礦(selfish mining)

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

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

6 基于權益證明的共識機制

6.1 概念

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

6.2 典型方案分析

(1)PPCoin

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

(2)Casper FFG

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

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

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

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

(3)Ouroboros 系列

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

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

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

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

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

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

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

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

(4)Snow White

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

Snow White 采用的網絡模型為睡眠模型(sleepy model)[116],即節點不會保持永久在線,可能在某段時間內在線,也可能在某段時間內離線,間斷參與共識.該模型中節點的狀態更加符合現實網絡中節點的狀態.Snow White 采用與FruitChains 類似的激勵制度,并且同樣采用區塊和水果同時生成的挖礦機制,交易放在水果中,水果放在區塊中,將連續幾個區塊的獎勵和其中包含的交易費平均分給區塊對應的出塊者,實現了公平性.

(5)DPoS

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

6.3 綜合分析

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

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

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

(2)打磨攻擊(grinding attack)

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

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

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

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

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

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

7.1 概念

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

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

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

(3)運行委員會內分布式一致性算法.委員會領導者在委員會內部對區塊發起共識請求,一般可以運行類似PBFT 或其改進協議,實現委員會內部的拜占庭容錯,達成分布式一致性共識,進而生成和維護區塊鏈.

(4)廣播區塊.委員會成員將生成的區塊廣播至全網,使得網絡中非委員會的節點和客戶端收到新產生的區塊,更新交易和區塊鏈.

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

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

圖9 單一委員會混合共識Figure 9 Single-committee based hybrid consensus

7.2 典型方案分析

(1)PeerCensus

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

(2)ByzCoin

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

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

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

③委員會重配置.ByzCoin 的委員會重配置采用“滑窗” 的形式,即新找到關鍵塊的節點進入委員會,并成為當前委員會的領導者,將委員會中“最久遠” 的區塊的出塊者踢出委員會.

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

(3)Solida

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

Solida 共識機制的流程如下:

①委員會內分布式一致性算法.Solida 改進了PBFT 算法,刪除了預準備階段,增加了公示階段,包括(a).提議(propose).領導者將交易打包并廣播 tx和(propose,c,e,v,s,h),其中h是交易的哈希值.(b).準備(prepare).收到上述信息的成員檢查交易和領導者身份的合法性,驗證通過后廣播消息(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).節點完成對h的承諾之后,在全網廣播公示消息((notify,c,e,v,s,h),C),收到該消息的用戶驗證其合法性,通過后完成交易的確認.

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

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

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

(4)Hybrid consensus

混合共識hybrid consensus 由Pass和Shi[32]提出.Hybrid consensus 將經典共識機制與非授權共識機制結合,利用工作量證明,提出混合共識機制,實現非授權環境中的狀態機復制.Pass和Shi 提出了交易的快速響應特性(responsivenss),是指交易的確認時間與網絡真實時延有關,而與網絡時延上限無關.Hybrid consensus 成功實現了交易的快速響應特性.

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

Hybrid consensus 首次利用形式化的安全模型和模塊化的設計建模混合共識機制,并證明了其能夠滿足一致性和活性等安全特性.

(5)Thunderella

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

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

Thunderella 共識機制的流程如下:

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

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

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

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

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

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

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

(6)Algorand

Algorand 由Gilad 等人[34]提出.Algorand 是將PoS 與經典分布式一致性算法結合的混合共識機制,其敵手模型為n=3f+1,網絡模型為同步網絡.

在Algorand 中,區塊結構如下:Br=(r,PAYr,SIG?r(Qr?1),H(Br?1)).其中r是指區塊的序列號,即當前的輪數,PAYr是指當前時間內發生的交集集合,Qr?1是指上一輪產生的隨機種子,H(Br?1)是指上一個區塊的哈希值,?r是指當前輪的領導者,SIG?r(Qr?1)是指?r利用自身私鑰對Qr?1計算的數字簽名.

Algorand 算法的流程如下:

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

②判斷是否被選中為本輪領導者/參與者.節點i私下判斷其是否被選中為本輪的領導者和本輪的委員會成員.若滿足則其被選中為本輪領導者; 若滿足pc,則其被選中為本輪委員會成員,此處p?和pc對應不同的難度系數.

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

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

7.3 綜合分析

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

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

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

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

第四,委員會內分布式一致性算法問題.在委員會內運行分布式一致性算法期間,如何確保客戶端提交的交易能夠被快速響應; 如何提高委員會內分布式一致性算法的運行效率,降低委員會成員間的通信復雜度和計算復雜度; 如何實現區塊的并行提議等.

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

8.1 概念

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

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

(1)通信分片(communication sharding)

通信分片是指將全網分為不同的片區,每個片區由一個對應的委員會處理,每個委員會內部成員大部分時間只需內部通信,每個片區內部的其他客戶端、節點大部分時間可以通過與該分片內委員會通信獲得目前區塊鏈的狀態.

(2)計算分片(computation sharding)

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

計算分片使不同的交易以并行的形式被不同的委員會處理,當網絡中節點數量增多時,可以增加更多的委員會,這樣不同的交易能夠以并行的形式被不同的委員會同時處理,交易處理性能隨著網絡中節點數量的增多而增加,進而實現了交易處理的可擴展性.

(3)存儲分片(storage sharding)

存儲分片是指不同分片委員會將處理后的交易分片存儲,每個分片委員會只負責處理本分片對應的交易,將交易放到本分片專屬的交易區塊鏈上.交易區塊鏈用于存儲本分片產生的交易歷史或當前分片的未花費交易池信息.存儲分片將整個區塊鏈系統的交易數據或未花費的交易輸出(unspent transaction output,UTXO)數據分片存儲,降低了節點的存儲負擔.

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

8.2 典型方案分析

(1)ELASTICO

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

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

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

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

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

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

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

(2)Omniledger

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

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

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

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

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

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

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

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

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

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

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

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

(3)Chainspace

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

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

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

②處理準備消息(process prepare).輸入分片1和分片2 的節點收到prepare(tx)消息后,鎖定交易tx 的輸入,在各自的委員會內部通過運行拜占庭算法處理準備消息,如果交易tx 合法,即輸入未被花費且沒有其他的交易使用該輸入,輸入分片向其他節點廣播承諾消息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).當上一步中有分片廣播accept(tx,commit)時,交易tx 的輸出分片運行委員會內分布式一致性算法,將tx 添加到該分片中.當分片廣播accept(tx,abort)時,所有分片將交易tx 的輸入解鎖,放棄交易tx.

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

(4)RapidChain

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

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

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

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

RapidChain 在網絡層中,采用消息擴散算法(information dispersal algorithms,IDA)代替傳統區塊鏈網絡采用的八卦通信協議(gossip protocol).發送者利用糾錯編碼,將區塊拆分為小區塊后傳播,接收者接收到一定數量的小區塊后可以恢復原始區塊.采用IDA 傳播方式能夠將區塊傳播速度提升約5.3 倍.

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

由于時期內共識采用同步網絡模型,交易確認時延與網絡真實時延無關,導致交易確認不能滿足快速響應特性.但 RapidChain 協議其他部分采用部分同步網絡模型,均能滿足快速響應特性.RapidChain采用一定措施,使得其時期內共識也能夠接近快速響應特性.

(5)其他分片共識機制

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

8.3 綜合分析

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

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

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

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

9 其他共識機制

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

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

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

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

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

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

10 未來研究方向

區塊鏈共識機制是區塊鏈技術的核心,未來的發展趨勢主要有以下幾點:

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

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

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

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