王 群，李馥娟，倪雪莉，夏玲玲，王振力，梁廣俊

1.江蘇警官學(xué)院 計(jì)算機(jī)信息與網(wǎng)絡(luò)安全系，南京 210031

2.江蘇省電子數(shù)據(jù)取證分析工程研究中心，南京 210031

共識是一個選擇或意見集中與統(tǒng)一的問題，涉及社會生活、管理及計(jì)算機(jī)應(yīng)用等眾多領(lǐng)域。通俗地講，共識過程類似于日常生活中的投票或舉手表決，只是這里的表決環(huán)境變成了分布式系統(tǒng)，而“投票”或“舉手”過程則是通過相應(yīng)的算法隱性地進(jìn)行。

分布式系統(tǒng)出現(xiàn)后，首先需要解決的一個根本問題就是如何實(shí)現(xiàn)集群內(nèi)部不同節(jié)點(diǎn)上數(shù)據(jù)的統(tǒng)一性和不同節(jié)點(diǎn)間針對特定操作狀態(tài)（如“提交”或“回滾”）的一致性，即通過共識機(jī)制使分布式節(jié)點(diǎn)達(dá)成一致性或取得穩(wěn)定的狀態(tài)。由于早期的分布式系統(tǒng)應(yīng)用主要集中于節(jié)點(diǎn)數(shù)量有限、運(yùn)行環(huán)境相對可信的分布式數(shù)據(jù)庫系統(tǒng)，系統(tǒng)中不存在惡意篡改或偽造數(shù)據(jù)的攻擊節(jié)點(diǎn)，因此針對傳統(tǒng)分布式系統(tǒng)中共識算法的研究一般不考慮拜占庭容錯問題。與之不同，區(qū)塊鏈系統(tǒng)在一個復(fù)雜和缺乏信任機(jī)制的開放互聯(lián)網(wǎng)環(huán)境（尤其是公有鏈）中通過共識算法建立了節(jié)點(diǎn)之間的信任，最終實(shí)現(xiàn)了不同節(jié)點(diǎn)上賬本的一致性和數(shù)據(jù)的安全性，因此，區(qū)塊鏈被稱為“信任機(jī)器”。由此可見，共識算法是區(qū)塊鏈技術(shù)中需要重點(diǎn)研究和掌握的關(guān)鍵技術(shù)。

通常情況下，區(qū)塊鏈系統(tǒng)中的節(jié)點(diǎn)首先是一個互聯(lián)網(wǎng)接入節(jié)點(diǎn)，其接入配置與普通聯(lián)網(wǎng)計(jì)算機(jī)沒有區(qū)別。但作為一個構(gòu)建在互聯(lián)網(wǎng)架構(gòu)和平臺上的自治系統(tǒng)，區(qū)塊鏈系統(tǒng)在繼承了傳統(tǒng)互聯(lián)網(wǎng)開放性、匿名性以及節(jié)點(diǎn)之間松耦合關(guān)系等基本特性的同時，其內(nèi)部采用點(diǎn)對點(diǎn)（peer-to-peer，P2P）方式組織節(jié)點(diǎn)之間的區(qū)塊傳輸、驗(yàn)證與記賬。P2P 網(wǎng)絡(luò)中，所有節(jié)點(diǎn)均處于相同的邏輯位置，每個節(jié)點(diǎn)在從其他節(jié)點(diǎn)獲取服務(wù)的同時，也為其他節(jié)點(diǎn)提供路由選擇與維護(hù)、區(qū)塊傳輸與驗(yàn)證、新節(jié)點(diǎn)發(fā)現(xiàn)等服務(wù)。在P2P網(wǎng)絡(luò)中，每個節(jié)點(diǎn)都維護(hù)著一個存放區(qū)塊鏈賬本數(shù)據(jù)的共享文件夾，共識算法的主要功能便是維護(hù)不同節(jié)點(diǎn)共享文件夾中賬本數(shù)據(jù)的一致性和正確性。

在傳統(tǒng)網(wǎng)絡(luò)中，像微信、支付寶等在線支付平臺的可靠性都由業(yè)務(wù)系統(tǒng)的提供者決定，個人身份信息、交易記錄等信息的安全性也取決于第三方機(jī)構(gòu)的信譽(yù)和安全技術(shù)服務(wù)能力。這種中心化的業(yè)務(wù)處理和管理模式在區(qū)塊鏈系統(tǒng)中被打破。隨著2008 年11 月1 日中本聰在其論文“Bitcoin：a peer-to-peer electronic cash system”中對比特幣原理的簡要闡述，以及2009 年1 月3 日比特幣系統(tǒng)的正式上線及創(chuàng)世區(qū)塊（genesis block）的問世，比特幣系統(tǒng)在隨之不溫不火地發(fā)展了將近10 年后，人們才發(fā)現(xiàn)通過區(qū)塊鏈這一底層技術(shù)，可以在一個完全去中心化的分布式環(huán)境中實(shí)現(xiàn)與傳統(tǒng)中心化環(huán)境下相同的業(yè)務(wù)功能，而完成該功能的關(guān)鍵便是共識算法。與傳統(tǒng)的業(yè)務(wù)處理系統(tǒng)相比，區(qū)塊鏈具有去中心化、數(shù)據(jù)不可篡改、集體維護(hù)、高度透明、安全可信等特點(diǎn)，區(qū)塊鏈技術(shù)以密碼學(xué)和P2P 網(wǎng)絡(luò)為基礎(chǔ)，將特定結(jié)構(gòu)的交易數(shù)據(jù)（如比特幣）或業(yè)務(wù)數(shù)據(jù)按照約定方式組織成區(qū)塊，然后通過選定的共識算法將新區(qū)塊添加到主鏈上，并利用密碼學(xué)技術(shù)保證數(shù)據(jù)的安全性和不可偽造性。因此，從本質(zhì)上講，區(qū)塊鏈就是一種不可篡改的分布式記賬方法，在整個網(wǎng)絡(luò)中共識算法每個節(jié)點(diǎn)都在維護(hù)著唯一的賬本。為此，共識算法是區(qū)塊鏈系統(tǒng)架構(gòu)的核心。

根據(jù)是否嚴(yán)格維護(hù)去中心化這一機(jī)制的不同，可將區(qū)塊鏈分為完全去中心化的“公有鏈”（public blockchain）和中心化的“私有鏈”（private blockchain）兩類，另外在公有鏈和私有鏈之間還存在著部分去中心化的“聯(lián)盟鏈”（consortium blockchain）；如果按照準(zhǔn)入機(jī)制的不同，可以將區(qū)塊鏈系統(tǒng)分為無需對節(jié)點(diǎn)身份進(jìn)行認(rèn)證的非許可鏈（permissionless blockchain）和需要對節(jié)點(diǎn)的準(zhǔn)入身份進(jìn)行認(rèn)證的許可鏈（permissioned blockchain）。通常情況下，公有鏈屬于非許可鏈，而私有鏈和聯(lián)盟鏈屬于許可鏈。聯(lián)盟鏈未來的發(fā)展更趨向于私有鏈，因此在部署架構(gòu)中一般可將聯(lián)盟鏈作為私有鏈的一種類型。共識算法因區(qū)塊鏈應(yīng)用場景的不同而有所不同，公有鏈環(huán)境中的共識算法一般需要支持良好的可擴(kuò)展性，需要在參與共識的節(jié)點(diǎn)隨時變化（“加入”或“離開”）的情況下達(dá)成最終的共識，而且還要防止可能存在的拜占庭節(jié)點(diǎn)對系統(tǒng)的攻擊。同時，受限于FLP（Michael Fisher、Nancy Lynch and Michael Paterson）定理、CAP（consistency、availability and partition-tolerant）定理和Paxos 算法等分布式一致性算法對運(yùn)行條件的嚴(yán)格限定，私有鏈中的共識算法一般很難保證強(qiáng)一致性；在私有鏈環(huán)境中，由于對接入節(jié)點(diǎn)的身份有嚴(yán)格的驗(yàn)證和控制機(jī)制（如目前廣泛使用的基于公鑰基礎(chǔ)設(shè)施（public key infrastructure，PKI）機(jī)制的數(shù)字證書技術(shù)實(shí)現(xiàn)節(jié)點(diǎn)認(rèn)證等），有效保證了節(jié)點(diǎn)的可信性，私有鏈中的共識算法一般是一種高效的強(qiáng)一致性算法，但算法的可擴(kuò)展性和有效防范拜占庭節(jié)點(diǎn)攻擊的能力有所減弱。

隨著區(qū)塊鏈應(yīng)用領(lǐng)域的不斷擴(kuò)展和對區(qū)塊鏈技術(shù)研究的不斷推進(jìn)，國內(nèi)外研究者分別對共識算法從不同角度進(jìn)行了梳理。在國內(nèi)研究方面，文獻(xiàn)[5]較為系統(tǒng)地整理了傳統(tǒng)分布式系統(tǒng)和區(qū)塊鏈系統(tǒng)中的共識算法，并選擇不同的發(fā)展主線分析了共識算法的新進(jìn)展；文獻(xiàn)[6]在對區(qū)塊鏈共識算法進(jìn)行總結(jié)的基礎(chǔ)上，根據(jù)不同的共識機(jī)制就算法實(shí)現(xiàn)、應(yīng)用和發(fā)展進(jìn)行了較為系統(tǒng)的介紹；文獻(xiàn)[7]重點(diǎn)從出塊節(jié)點(diǎn)選舉和主鏈共識兩方面系統(tǒng)分析了共識協(xié)議的實(shí)現(xiàn)，并提出了存在的問題及解決方案；文獻(xiàn)[8]在調(diào)研并分析了代表性共識算法及其演進(jìn)歷程的基礎(chǔ)上，提出了共識算法的分類模型，并對部分重要的共識算法進(jìn)行了分析。在國外研究方面，文獻(xiàn)[9]重點(diǎn)對區(qū)塊鏈中基于證明的共識協(xié)議進(jìn)行了討論，并對工作量證明和權(quán)益證明進(jìn)行了對比分析；文獻(xiàn)[10]從應(yīng)用開發(fā)的角度，重點(diǎn)對區(qū)塊鏈分叉和一致性算法進(jìn)行了討論；文獻(xiàn)[11]在介紹了分布式賬本技術(shù)（distributed ledger technology，DLT）及其變種基本原理的基礎(chǔ)上，對130 種共識算法進(jìn)行了對比分析，然后對分布式賬本技術(shù)的發(fā)展前景進(jìn)行了展望。

本文在廣泛收集國內(nèi)外各類文獻(xiàn)資料以及對區(qū)塊鏈技術(shù)及其主要應(yīng)用進(jìn)行深入分析的基礎(chǔ)上，歸納整理了共識算法中涉及到的主要概念。同時，以比特幣的出現(xiàn)和應(yīng)用作為一個大體的分界點(diǎn)，將共識算法分為分布式系統(tǒng)經(jīng)典共識算法和區(qū)塊鏈共識算法兩類，其中對經(jīng)典共識算法的介紹主要針對傳統(tǒng)分布式系統(tǒng)工作原理和特點(diǎn)來展開，而對區(qū)塊鏈共識算法的分析是在對現(xiàn)有共識算法和系統(tǒng)進(jìn)行了梳理的基礎(chǔ)上，認(rèn)為拜占庭容錯（Byzantine fault tolerance，BFT）、實(shí)用拜占庭容錯（practical Byzantine fault tolerance，PBFT）、工作量證明（proof of work，PoW）和權(quán)益證明（proof of stake，PoS）是各類區(qū)塊鏈共識算法的核心，而其他大量的共識算法是其功能擴(kuò)展和組合?；谶@一事實(shí)和基本思想，本文將主流區(qū)塊鏈共識算法分為PoW、PoS、PoW+PoS、PoW/PoS+BFT/PBFT 共四類進(jìn)行討論。

1 共識算法概述

在計(jì)算機(jī)學(xué)科領(lǐng)域，算法是為了實(shí)現(xiàn)某一目的而設(shè)計(jì)的一系列解決具體問題的清晰指令，協(xié)議是為了使通信雙方或多方達(dá)到某一目的而規(guī)定的一組規(guī)則。協(xié)議用于解決具體問題，而算法是對協(xié)議的具體實(shí)現(xiàn)，體系結(jié)構(gòu)和協(xié)議奠定了網(wǎng)絡(luò)的主體架構(gòu)。為此，本文在討論共識算法時將其置于具體的網(wǎng)絡(luò)環(huán)境和應(yīng)用場景中。

1.1 區(qū)塊鏈共識模型

早期的共識算法主要是在大多不考慮拜占庭容錯問題的分布式系統(tǒng)中研究數(shù)據(jù)庫操作的一致性。在這類分布式系統(tǒng)中，一般不考慮節(jié)點(diǎn)故意偽造、篡改數(shù)據(jù)等問題，認(rèn)為系統(tǒng)節(jié)點(diǎn)只會出現(xiàn)宕機(jī)或網(wǎng)絡(luò)故障等非人為攻擊現(xiàn)象。與傳統(tǒng)分布式環(huán)境相比，區(qū)塊鏈共識算法是在網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜、體系架構(gòu)各異以及節(jié)點(diǎn)之間缺乏信任的開放網(wǎng)絡(luò)環(huán)境中實(shí)現(xiàn)操作和數(shù)據(jù)的一致性和正確性，在共識算法的實(shí)現(xiàn)過程中，多數(shù)情況下參與節(jié)點(diǎn)較多，而且存在惡意的拜占庭節(jié)點(diǎn)。另外，傳統(tǒng)的分布式系統(tǒng)一般工作在同步環(huán)境，節(jié)點(diǎn)之間達(dá)成一致性的難度較小，算法實(shí)現(xiàn)也相對簡單，算法運(yùn)行的效率較高。而區(qū)塊鏈共識算法主要運(yùn)行在基于分組交換的互聯(lián)網(wǎng)環(huán)境中，不但要解決分組傳輸?shù)难訒r、重復(fù)、丟失和出錯等復(fù)雜問題，還要能夠根據(jù)大多數(shù)應(yīng)用場景的要求，在效率、可靠性和安全性等方面得到保障。因此，區(qū)塊鏈共識算法設(shè)計(jì)時需要面對的環(huán)境更為復(fù)雜，需要面對的困難和解決的問題更多。

區(qū)塊鏈技術(shù)的核心內(nèi)容主要包括分布式數(shù)據(jù)庫、密碼學(xué)、共識算法和P2P 網(wǎng)絡(luò)，其中分布式數(shù)據(jù)庫負(fù)責(zé)數(shù)據(jù)的寫入、讀取與存儲，密碼學(xué)中的非對稱密鑰加密機(jī)制和哈希（Hash）算法實(shí)現(xiàn)用戶身份認(rèn)證、地址標(biāo)識、完整性驗(yàn)證等功能，共識算法實(shí)現(xiàn)交易信息在分布式賬本中的一致性和安全性，P2P 網(wǎng)絡(luò)提供了區(qū)塊鏈不同節(jié)點(diǎn)間的通信保障。在圖1 所示的區(qū)塊鏈共識模型中，以比特幣系統(tǒng)為例，結(jié)合區(qū)塊鏈核心技術(shù)的應(yīng)用，描述了一個交易從生成到最后被打包確認(rèn)的5 個過程：

（1）生成交易。交易信息由客戶端（完整客戶端、輕量級客戶端或在線交易平臺）生成，包括交易的輸入金額、輸入賬戶及輸出賬戶的地址等信息。未經(jīng)簽名的“原始交易”（raw transaction）無法被礦機(jī)接收，只有在進(jìn)行了用戶簽名后，該交易才會被礦機(jī)通過共識機(jī)制打包進(jìn)新區(qū)塊。

（2）交易簽名。用戶在客戶端用自己的私鑰對交易進(jìn)行簽名，形成合法的交易數(shù)據(jù)。

（3）交易廣播。將簽名后的交易數(shù)據(jù)通過調(diào)用本地應(yīng)用程序接口（application programming interface，API）或以P2P 節(jié)點(diǎn)方式廣播到網(wǎng)絡(luò)中。

（4）挖礦。挖礦即對交易數(shù)據(jù)的打包和確認(rèn)。首先根據(jù)區(qū)塊的數(shù)據(jù)結(jié)構(gòu)，將交易打包進(jìn)區(qū)塊，再采用Merkle Tree 算法生成區(qū)塊體中所有交易的Merkle Roo（t哈希值），然后根據(jù)區(qū)塊頭部的元數(shù)據(jù)，采用相應(yīng)的共識算法（如PoW、PoS等）獲取新區(qū)塊的記賬權(quán)。

（5）全網(wǎng)節(jié)點(diǎn)寫入。礦工將生成的新區(qū)塊廣播到區(qū)塊鏈網(wǎng)絡(luò)中，任意一個節(jié)點(diǎn)在接收到新區(qū)塊后，對其進(jìn)行驗(yàn)證，驗(yàn)證通過后將該區(qū)塊鏈接到本地區(qū)塊鏈上。同時，不同的區(qū)塊鏈系統(tǒng)還將采用相應(yīng)的算法防止分叉的產(chǎn)生，維護(hù)主鏈的唯一性和穩(wěn)定性。

圖1 區(qū)塊鏈共識基礎(chǔ)模型Fig.1 Blockchain consensus base model

1.2 共識算法中的基本定義

針對區(qū)塊鏈共識算法的研究涉及大量技術(shù)、經(jīng)濟(jì)和社會等眾多層面的問題，為便于對區(qū)塊鏈共識算法的理解，下面給出一些基本定義。

（一致性（agreement））所有的非缺陷進(jìn)程都必須同意接受某一個值。

在區(qū)塊鏈網(wǎng)絡(luò)中，一致性存在強(qiáng)一致性（strict consistency）和弱一致性（weak consistency）兩種類型。其中，強(qiáng)一致性是指任意時刻所有節(jié)點(diǎn)中的數(shù)據(jù)是相同的，而弱一致性（也稱為最終一致性）是指不保證任意時刻任意節(jié)點(diǎn)上的同一份數(shù)據(jù)都是相同的，但最終會趨于相同。在弱一致性區(qū)塊鏈系統(tǒng)中，并不是每一個合法挖礦者挖出的區(qū)塊最終都會連接到主鏈，因此不可避免會存在分叉現(xiàn)象（如比特幣（bitcoin）、以太坊（ethereum）等），而在強(qiáng)一致性區(qū)塊鏈系統(tǒng)中，由于區(qū)塊的生成由每一輪指定的節(jié)點(diǎn)負(fù)責(zé)（如Hyperledger、Solida等），不會出現(xiàn)分叉現(xiàn)象。

（正確性（validity））針對所有的非缺陷進(jìn)程，其同意接受的值必須是非故障進(jìn)程提議的值。

（可終止性（termination））對于每一個非缺陷進(jìn)程來說，必須都有一個最終確定的值。

一致性、正確性和可終止性稱為共識問題的三個屬性，同時滿足一致性和正確性時稱為安全性（safety），滿足可終止性時稱為活性（liveness）。

（共識（consensus））就某種狀態(tài)或數(shù)據(jù)達(dá)成一致性的過程。

一致性一般是指分布式系統(tǒng)中數(shù)據(jù)及其副本對外呈現(xiàn)的狀態(tài)，描述的是多個節(jié)點(diǎn)對數(shù)據(jù)狀態(tài)的維護(hù)能力，而共識描述的是分布式系統(tǒng)中多個節(jié)點(diǎn)間彼此對某個狀態(tài)達(dá)成一致結(jié)果的過程。一致性描述的是狀態(tài)的結(jié)果，而共識則是一種手段，達(dá)成某種共識并不意味著取得了完全一致。

（拜占庭缺陷（Byzantine fault））從不同多角度表現(xiàn)出不同現(xiàn)象的缺陷。

（拜占庭故障（Byzantine failure））由拜占庭缺陷引起的故障。

（宕機(jī)缺陷（fail-stop fault））因系統(tǒng)進(jìn)程停止運(yùn)行導(dǎo)致的缺陷。

（宕機(jī)恢復(fù)故障（fail-recovery failure））因系統(tǒng)進(jìn)程停止運(yùn)行導(dǎo)致的故障，該故障在重啟進(jìn)程后恢復(fù)。

由定義5 至定義8 可知，并不是所有的缺陷或故障都是拜占庭的，像宕機(jī)缺陷或故障為非拜占庭缺陷或故障，而由人為破壞、惡意代碼攻擊等不可預(yù)測的行為引起的缺陷或故障是拜占庭的。

（通信模型（communication model））分組通信網(wǎng)絡(luò)是一類串行通信網(wǎng)絡(luò)，根據(jù)節(jié)點(diǎn)之間消息（分組）傳輸方式的不同，可以將區(qū)塊鏈網(wǎng)絡(luò)分為同步網(wǎng)絡(luò)、異步網(wǎng)絡(luò)和部分同步網(wǎng)絡(luò)三種類型。其中，同步網(wǎng)絡(luò)是指非拜占庭收發(fā)節(jié)點(diǎn)在時鐘頻率上保持一致，異步網(wǎng)絡(luò)是指非拜占庭收發(fā)節(jié)點(diǎn)在時鐘頻率上不需要保持一致，而部分同步網(wǎng)絡(luò)是指網(wǎng)絡(luò)中的部分（而非全部）非拜占庭節(jié)點(diǎn)在時鐘頻率上保持相對一致。

通信模型在很大程度上決定著共識算法的設(shè)計(jì)與實(shí)現(xiàn)。在同步網(wǎng)絡(luò)中，在一個消息到達(dá)節(jié)點(diǎn)之前，已經(jīng)確認(rèn)前一條消息成功接收；在異步網(wǎng)絡(luò)中，由于消息的傳輸可能會產(chǎn)生延時、亂序等現(xiàn)象，無法保障消息會按照發(fā)送時的順序有序到達(dá)；而在部分同步網(wǎng)絡(luò)中，消息能夠在系統(tǒng)限定的時間內(nèi)到達(dá)所有非拜占庭節(jié)點(diǎn)，但前后順序無法得到保障。

2 經(jīng)典分布式共識算法

共識算法的發(fā)展是隨著計(jì)算機(jī)應(yīng)用技術(shù)及應(yīng)用環(huán)境的變化而同步演進(jìn)的。與目前復(fù)雜網(wǎng)絡(luò)環(huán)境下的主流區(qū)塊鏈共識算法相比，早期的共識算法一般不考慮作惡節(jié)點(diǎn)的存在，認(rèn)為系統(tǒng)中只會存在服務(wù)器宕機(jī)或網(wǎng)絡(luò)故障等非人為攻擊現(xiàn)象，即大多數(shù)情況下不考慮拜占庭容錯問題，因此，早期的共識算法也稱為分布式一致性算法。但需要說明的是，回顧經(jīng)典的分布式一致性算法并不是說這些算法已經(jīng)成為束之高閣的歷史，而是通過系統(tǒng)的梳理和研究，為現(xiàn)代區(qū)塊鏈共識算法的設(shè)計(jì)思想理清思路，為區(qū)塊鏈共識算法的發(fā)展趨勢把準(zhǔn)方向。另外，像目前聯(lián)盟鏈中使用的實(shí)用拜占庭容錯（PBFT）和比特幣的工作量證明（PoW）等典型共識算法均出現(xiàn)在區(qū)塊鏈概念提出之前，最初也是為了解決分布式系統(tǒng)的一致問題而提出，“新瓶裝舊酒”也是一種應(yīng)用創(chuàng)新。

2.1 兩軍問題

1975 年，Akkoyunlu 等人首次提出了網(wǎng)絡(luò)通信領(lǐng)域的“兩軍問題”（也有學(xué)者稱之為“兩軍悖論”或“協(xié)同攻擊問題”），指出在一條不可靠的通信鏈路上試圖通過通信方式達(dá)成一致性是不可能的，成為計(jì)算機(jī)通信領(lǐng)域首個被證明無解的問題。研究兩軍問題，需要同時建立在以下兩個條件的基礎(chǔ)上：

通信信道是不可靠的（與拜占庭將軍問題不同）。

不存在叛徒問題，即信使是可靠的。

兩軍問題是一個在信道存在干擾條件下的兩節(jié)點(diǎn)通信問題，也是一個日常生活問題。如圖2 所示，分隔在“白軍”兩側(cè)的總數(shù)大于白軍人數(shù)的兩支“藍(lán)軍”如果要獲勝，必須同時對白軍發(fā)起攻擊。那么，是否存在一種方式（協(xié)議）能夠使藍(lán)軍獲勝呢？顯然這是一個無解的問題。

圖2 兩軍問題示意圖Fig.2 Two-army problem pattern

兩軍問題是研究分布式系統(tǒng)一致性的一個重要理論，對現(xiàn)代計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展產(chǎn)生了重要影響，對區(qū)塊鏈共識算法的研究具有重要意義。例如，在TCP/IP 體系中，TCP 協(xié)議為了解決兩個節(jié)點(diǎn)之間通信的可靠性問題，就采用了基于“三次握手”建立連接和“四次握手”斷開連接的機(jī)制，為解決兩軍問題不存在理論提供了一個簡易可行的應(yīng)用范式。

2.2 拜占庭將軍問題

1982 年，由Lamport 等人提出了拜占庭將軍問題（Byzantine generals problem），其核心思想是在明知軍中存在叛徒的情況下，要保證行動（進(jìn)攻或撤退）的一致性。隨著區(qū)塊鏈技術(shù)的出現(xiàn)和興起，這一問題作為研究分布式系統(tǒng)中一致性機(jī)制的經(jīng)典理論開始重入大眾視野，并直接影響著區(qū)塊鏈共識算法的設(shè)計(jì)與實(shí)現(xiàn)。

拜占庭將軍問題的提出，建立在同時滿足以下3個條件（條件3 至條件5）的基礎(chǔ)上。

通信信道的可靠性。拜占庭將軍問題的研究建立在信使不會被敵方捕獲這一前提下，即信使肯定會將消息傳遞給盟軍中的其他將軍（即信使是可靠的），但傳遞的消息是否真實(shí)并無限制。用在分布式系統(tǒng)中，拜占庭將軍問題認(rèn)為傳遞消息的網(wǎng)絡(luò)信道是絕對可靠的，在此前提下再進(jìn)行一致性和容錯性的研究。

條件3 可通過口頭協(xié)議來實(shí)現(xiàn)：（1）每條發(fā)送的消息都能夠被正確傳遞；（2）消息的接收方能夠知道該條消息的發(fā)送方；（3）當(dāng)消息沒有發(fā)送時可以被檢測到。

圖3 三個將軍中一個是叛徒Fig.3 One of three generals is a traitor

如果條件4 成立，還需要滿足另兩個條件：每個忠誠的將軍必須收到相同的命令值(1),(2),…,()，其中()(1 ≤≤)表示第個將軍傳遞給其他將軍的消息，即所有忠誠的將軍在收到消息后會遵守相同的命令；如果發(fā)送消息的第個將軍是忠誠的，那么所有忠誠的將軍接收到的()值是相同的。

少數(shù)的叛徒無法使忠誠的將軍做出錯誤的決定。假設(shè)()是第個將軍發(fā)送給其他將軍的消息，每個將軍會根據(jù)收到的所有消息(1),(2),…,()做出決定。這一條件在分布式系統(tǒng)中可以描述為每個節(jié)點(diǎn)在接收到消息后都會傳遞給其他節(jié)點(diǎn)，通過遞歸方式，直到最后每個節(jié)點(diǎn)中都存在其他所有節(jié)點(diǎn)發(fā)送的消息。最后，所有節(jié)點(diǎn)按照少數(shù)服從多數(shù)的原則達(dá)成行動上的一致。

需要說明的是，通過條件5 雖然可以最終實(shí)現(xiàn)運(yùn)行上的一致性，卻無法知道誰是叛徒，即無法進(jìn)行溯源。為了解決這一問題，在分布式系統(tǒng)中可以采用群簽名、環(huán)簽名、盲簽名等數(shù)字簽名技術(shù)，通過非安全通道實(shí)現(xiàn)對消息或文檔真實(shí)性的認(rèn)證。

共識算法是區(qū)塊鏈技術(shù)的核心，拜占庭容錯是研究區(qū)塊鏈共識算法的關(guān)鍵。傳統(tǒng)的獨(dú)立磁盤冗余陣列（redundant arrays of independent disks，RAID）、幀檢驗(yàn)和超時重傳等分布式系統(tǒng)中使用的容錯機(jī)制，一般只能解決局部或特定條件下的單一問題，無法適應(yīng)分布式系統(tǒng)中可能存在的因人為攻擊、安全漏洞、軟件缺陷等綜合問題引起的復(fù)雜錯誤。因此，工程實(shí)踐中需要一種能夠容忍多種形式的軟件錯誤和安全漏洞的機(jī)制，這一機(jī)制或方案稱為拜占庭容錯（BFT）技術(shù)。

拜占庭將軍問題類似于分布式系統(tǒng)。其中，服務(wù)器類比為將軍，服務(wù)器之間的消息傳遞類比為在將軍之間傳遞消息的信使。服務(wù)器可能會受到攻擊而向其他服務(wù)器發(fā)送錯誤信息，發(fā)送錯誤信息的服務(wù)器扮演著叛徒的角色。因此，可以將拜占庭容錯系統(tǒng)理解為在一個由多臺服務(wù)器組成的分布式系統(tǒng)中，對于每一個請求必須滿足以下兩個條件（條件6和條件7）的系統(tǒng)：

所有非拜占庭服務(wù)器（沒有出現(xiàn)故障的服務(wù)器）使用完全相同的輸入信息，產(chǎn)生完全一致的輸出結(jié)果。

當(dāng)輸入的信息正確時，所有非拜占庭服務(wù)器都要接受該信息，并計(jì)算相應(yīng)的結(jié)果。

與此同時，對于一個已投入運(yùn)行的拜占庭容錯系統(tǒng)來說，所有拜占庭服務(wù)器（出現(xiàn)缺陷或故障的服務(wù)器）需要滿足安全性和活性兩個指標(biāo)：

（1）安全性：對于任何已經(jīng)完成的請求都不允許更改，而且對之后的請求是可見的。

（2）活性：對于非拜占庭客戶端發(fā)出的請求，能夠無條件地接受并執(zhí)行。

根據(jù)節(jié)點(diǎn)（服務(wù)器或客戶端）的容錯類型，可以將分布式系統(tǒng)的共識機(jī)制分為拜占庭容錯和非拜占庭容錯兩類，其中非拜占庭容錯（如Paxos、viewstamped replication、Raft等算法）主要用于聯(lián)盟鏈和私有鏈，而公有鏈主要使用拜占庭容錯共識算法。

拜占庭容錯系統(tǒng)能夠容忍幾乎所有形式的錯誤類型，已經(jīng)成為解決分布式系統(tǒng)容錯問題的一種通用方案。但早期的拜占庭容錯協(xié)議在實(shí)現(xiàn)時過于強(qiáng)調(diào)算法的理論性而忽視了實(shí)用性，并且算法的復(fù)雜度隨著系統(tǒng)中節(jié)點(diǎn)數(shù)的增加而呈指數(shù)級上升，另外還需要配置時鐘同步機(jī)制，限制了其應(yīng)用。實(shí)用拜占庭容錯（PBFT）共識算法能夠?qū)崿F(xiàn)對一定數(shù)量的拜占庭節(jié)點(diǎn)進(jìn)行容錯，在異步分布式系統(tǒng)中提供安全性和活性，并通過對BFT 算法的改進(jìn)，將系統(tǒng)的復(fù)雜度從指數(shù)級降到了多項(xiàng)式級別，使得算法在實(shí)際應(yīng)用中變得可行。在區(qū)塊鏈應(yīng)用場景中，PBFT 共識算法適合于對一致性要求較高的私有鏈和聯(lián)盟鏈。例如，在IBM 主導(dǎo)的超級賬本（hyperledger）項(xiàng)目中，PBFT 便是一個可選的共識協(xié)議。

根據(jù)協(xié)議實(shí)現(xiàn)時關(guān)注點(diǎn)的不同，目前的拜占庭系統(tǒng)主要分為狀態(tài)機(jī)拜占庭系統(tǒng)和Quorum 拜占庭系統(tǒng)兩類。前者強(qiáng)調(diào)系統(tǒng)中同一時刻只允許有一個請求被執(zhí)行，這就使得服務(wù)器之間執(zhí)行請求的順序要求完全一致；后者對請求的執(zhí)行順序沒有嚴(yán)格要求，但對響應(yīng)時間極為敏感。PBFT 屬于狀態(tài)機(jī)拜占庭系統(tǒng)，即整個系統(tǒng)維護(hù)同一個狀態(tài)，所有服務(wù)器采取的運(yùn)行完全一致，具體通過一致性（agreement）、檢查點(diǎn)（check point）和視圖更換（view change）3 個協(xié)議來實(shí)現(xiàn)。其中，一致性協(xié)議的功能是實(shí)現(xiàn)客戶端發(fā)出的請求在每個服務(wù)器上都能夠按照確定的順序執(zhí)行；檢查點(diǎn)協(xié)議的功能是定期清理日志以節(jié)約資源，同時將系統(tǒng)中的服務(wù)器同步到某一個相同的狀態(tài)；視圖更換協(xié)議的作用是在節(jié)點(diǎn)出錯時進(jìn)行替換，并確保被非拜占庭服務(wù)器執(zhí)行的請求不會受到影響。系統(tǒng)在正常運(yùn)行時一般只執(zhí)行一致性和檢查點(diǎn)兩個協(xié)議，只有在系統(tǒng)出現(xiàn)錯誤（如節(jié)點(diǎn)宕機(jī)或運(yùn)行緩慢）時視圖更換協(xié)議才開始啟用。

因?yàn)楸拘」?jié)研究的主要內(nèi)容是分布式系統(tǒng)的共識問題，所以在這里更關(guān)注PBFT 的一致性協(xié)議。一致性協(xié)議約定來自客戶端（client）的每一個請求按照確定的順序在每個服務(wù)器上執(zhí)行，每個服務(wù)器在相同的配置信息下工作（該配置信息稱為“視圖”），服務(wù)器分為主節(jié)點(diǎn)（primary）和副本節(jié)點(diǎn)（replica）兩類，其中主節(jié)點(diǎn)僅有一個，它負(fù)責(zé)對客戶端的請求進(jìn)行排序，副本節(jié)點(diǎn)按照主節(jié)點(diǎn)提供的順序執(zhí)行請求。

一致性協(xié)議至少包括請求（propose）、預(yù)準(zhǔn)備（pre-prepare）、準(zhǔn)備（prepare）、確認(rèn)（commit）和回復(fù)（reply）5 個階段。圖4 是一個簡化的PBFT 協(xié)議運(yùn)行示意圖，其中副本節(jié)點(diǎn)replica 3 為故障節(jié)點(diǎn)（標(biāo)×），箭頭表示消息的發(fā)送過程。整個協(xié)議的執(zhí)行過程如下：

（1）請求（propose）?？蛻舳讼蛑鞴?jié)點(diǎn)發(fā)送請求，該請求消息=[op,t,-id,-sig]，其中op 代表執(zhí)行的操作，為時間戳，-id 為客戶端標(biāo)識，-sig 為客戶端數(shù)字簽名。簽名的目的是對客戶端進(jìn)行認(rèn)證和授權(quán)，以適應(yīng)聯(lián)盟鏈或私有鏈對接入節(jié)點(diǎn)的管理要求。

（2）預(yù)準(zhǔn)備（pre-prepare）。當(dāng)主節(jié)點(diǎn)接收到請求消息后，給該請求分配一個序列號sn，并構(gòu)造一個預(yù)準(zhǔn)備消息pre-prepare=[p-p,vn,sn,(),-sig,]，之后將該消息發(fā)送給系統(tǒng)中的所有副本節(jié)點(diǎn)，其中p-p 代表pre-prepare 消息，vn 為視圖號，()是客戶端消息的摘要值（Hash 值），-sig 為主節(jié)點(diǎn)的簽名。序號規(guī)定了服務(wù)器執(zhí)行命令的順序，視圖號使副本節(jié)點(diǎn)知道當(dāng)前視圖，主節(jié)點(diǎn)簽名是使副本節(jié)點(diǎn)知道誰是當(dāng)前系統(tǒng)中唯一的主節(jié)點(diǎn)，消息摘要值防止消息在傳輸過程中被篡改。

圖4 PBFT 協(xié)議運(yùn)行示意圖Fig.4 PBFT protocol communication pattern

（3）準(zhǔn)備（prepare）。所有副本節(jié)點(diǎn)在接收到preprepare 消息后，構(gòu)成一個準(zhǔn)備消息prepare=[p,vn,sn,(),-id,-sig]，然后將其發(fā)送給其他服務(wù)器節(jié)點(diǎn)，其中p 表示prepare 消息，-id 為副本節(jié)點(diǎn)的標(biāo)識，-sig為副本節(jié)點(diǎn)的數(shù)字簽名。

（4）確認(rèn)（commit）。服務(wù)器節(jié)點(diǎn)在收到2+1 個prepare 消息（系統(tǒng)中總共有3+1 個服務(wù)器節(jié)點(diǎn)，其中故障節(jié)點(diǎn)有個）后，對視圖內(nèi)的請求和執(zhí)行順序進(jìn)行驗(yàn)證，驗(yàn)證通過后執(zhí)行客戶端請求，并構(gòu)成一個確認(rèn)消息commit=[,vn,sn,(),-id,-sig]后發(fā)送給其他服務(wù)器節(jié)點(diǎn)，其中表示commit消息。

（5）回復(fù)（reply）。當(dāng)服務(wù)器節(jié)點(diǎn)收到2+1 個commit 消息，構(gòu)成一個回復(fù)消息reply=[,vn,t,-sig]后發(fā)送給客戶端，其中表示回復(fù)消息?？蛻舳说却蟹?wù)器節(jié)點(diǎn)的回復(fù)消息，如果接收到2+1 個相同的回復(fù)，則該回復(fù)即為運(yùn)算結(jié)果。

在異步系統(tǒng)中，PBFT 算法能夠在拜占庭節(jié)點(diǎn)數(shù)少于1/3 的情況下達(dá)成最終的一致性。同時，在PBFT 中，消息發(fā)送者的身份都以數(shù)字簽名方式經(jīng)過了認(rèn)證，確保了節(jié)點(diǎn)的可信性和消息來源的可追溯能力。另外，PBFT 提供了超時機(jī)制，從而保證了安全性和活性。

2.3 FLP 不可能性定理

1985 年，F(xiàn)ischer、Lynch 和Paterson 三位科學(xué)家在文獻(xiàn)[31]中提出：在一個多進(jìn)程異步系統(tǒng)中，只要存在一個不可靠的進(jìn)程，就不存在在有限時間內(nèi)使所有進(jìn)行達(dá)成一致的協(xié)議。按照三位科學(xué)家姓氏的首字母，該定理被稱為FLP 不可能性定理。

任何一個分布式算法都需要對系統(tǒng)場景進(jìn)行假設(shè)或設(shè)置條件，從而形成系統(tǒng)模型，F(xiàn)LP 不可能性定理建立在以下4個條件（條件8至條件11）的基礎(chǔ)上：

異步通信。與相對可靠的同步通信相比，異步通信的最大區(qū)別是沒有時鐘，無法實(shí)現(xiàn)時間同步，未使用超時機(jī)制，無法回溯失敗原因，信息的延遲可能非常大，并且消息可能存在亂序。

通信健壯。只要進(jìn)程沒有失敗，消息雖然會被無限延遲，但最終會到達(dá)接收端，并且消息只會被送達(dá)一次（不能重復(fù)）。

失敗-停止模型。進(jìn)程失敗后不再處理任何消息。

失敗進(jìn)程數(shù)限制。系統(tǒng)中最多只能有一個進(jìn)程失敗。

根據(jù)FLP 不可能性定理的定義，一個共識協(xié)議針對一個具有(≥2)個進(jìn)程的異步通信系統(tǒng)，不同進(jìn)程之間的通信通過相互發(fā)送消息進(jìn)行；共識系統(tǒng)的配置（configuration）由進(jìn)程的內(nèi)部狀態(tài)與消息緩存組成，如果在系統(tǒng)操作之后，沒有進(jìn)程做出決定（“提交”或“回滾”），則稱為不確定的配置；相反，如果某個配置能夠精確地做出決定，則稱為確定性的配置。如果某個配置是確定的，則認(rèn)為一致性可以達(dá)成。在此過程中，把從一個配置狀態(tài)轉(zhuǎn)換到另一個配置狀態(tài)的過程稱為一個步驟（step），每個步驟由單一進(jìn)程的一次執(zhí)行完成。對于FLP 不確定性定理的理解，關(guān)鍵在于“確定性”（deterministic）和“不確定性”（un-deterministic）兩個詞應(yīng)用場景的理解，即在共識協(xié)議中，盡管每個進(jìn)程的狀態(tài)轉(zhuǎn)換函數(shù)是確定性的，但觸發(fā)狀態(tài)轉(zhuǎn)換函數(shù)的消息接收和處理過程是不確定性的，因此，在一個存在故障進(jìn)程的異步通信系統(tǒng)中，不可能在有限時間內(nèi)達(dá)成共識狀態(tài)。

FLP 不可能性定理是眾多共識算法中一個非常經(jīng)典的基礎(chǔ)性定理。對于FLP 不可能性定理的理解和應(yīng)用需要建立在相應(yīng)假設(shè)及限制條件的系統(tǒng)模型上，在FLP 不可能性定理假設(shè)條件中，因?yàn)闆]有對進(jìn)程接收消息、處理消息和回復(fù)消息的時間進(jìn)行限制，也就是說進(jìn)程處理速度不確定，消息的延遲也可能很大，因此在判斷一個進(jìn)程問題時不知道是因宕機(jī)引起的進(jìn)程故障還是因消息的處理時間太長而造成的延時所致。同時，F(xiàn)LP 不可能性定理中所指的故障并不是拜占庭故障，而僅僅是導(dǎo)致進(jìn)程停止運(yùn)行的宕機(jī)故障。

在異步系統(tǒng)中，當(dāng)一個進(jìn)程出現(xiàn)故障或響應(yīng)時間延遲時，不存在一個分布式算法能夠讓所有的非故障進(jìn)程達(dá)成一致性共識。為規(guī)避FLP 不可能性定理，只能通過對某些條件進(jìn)行必要的取舍或調(diào)整來優(yōu)化問題模型。例如，因?yàn)榇嬖贔LP 不可能性定理的限制，許多區(qū)塊鏈項(xiàng)目的共識算法一般都認(rèn)為大部分節(jié)點(diǎn)是誠實(shí)的，并且滿足一定的同步性，其中PoW算法認(rèn)為至少51%的節(jié)點(diǎn)是誠實(shí)的，并且有一定的同步性，PoS 和PBFT 算法也認(rèn)為2/3 及以上的節(jié)點(diǎn)是誠實(shí)的。

2.4 CAP 定理

在2000 年的分布式計(jì)算原則大會（Symposium on Principles of Distributed Computing 2000）上，計(jì)算機(jī)科學(xué)家Brewer 在主旨演講中針對分布式環(huán)境下數(shù)據(jù)庫的一致性（consistency）、可用性（availability）和分區(qū)容錯性（partition-tolerant）提出了猜想。2002 年，該猜想得到了來自麻省理工學(xué)院的兩位教授Lynch和Gilbert的證明，被稱為CAP 定理。

CAP 定理是分布式系統(tǒng)設(shè)計(jì)中最基礎(chǔ)和最關(guān)鍵的理論之一。CAP 定理提出：在一個分布式數(shù)據(jù)存儲系統(tǒng)中，最多只能同時滿足一致性、可用性和分區(qū)容錯性3個屬性中的2個屬性（每個屬性即一個條件）。

（1）一致性：數(shù)據(jù)對象的原子性，即在所有操作（“讀”或“寫”）中，必須存在一個完整、確定的順序，使得所有操作就像在單個實(shí)體上完成一樣。

（2）可用性：每個非故障節(jié)點(diǎn)在收到請求消息后必須給予回復(fù)。

（3）分區(qū)容錯性：能夠容忍網(wǎng)絡(luò)丟失從一個節(jié)點(diǎn)發(fā)送給另一節(jié)點(diǎn)的任意數(shù)量的消息。

CAP 定理在應(yīng)用于分布系統(tǒng)時，需要根據(jù)不同的場景對3 個屬性進(jìn)行相應(yīng)的取舍，如圖5 所示。在網(wǎng)絡(luò)環(huán)境中，由于分區(qū)容錯是一個常態(tài)，在設(shè)計(jì)一個具體的分布式系統(tǒng)時需要在一致性與可用性之間進(jìn)行權(quán)衡。例如，Amazon DynamoDB 為了確?？捎眯远荒苌釛壱恢滦?，而谷歌文件系統(tǒng)（Google file system，GFS）在實(shí)現(xiàn)一致性的前提下只有舍棄可用性。

圖5 CAP 定理的屬性取舍Fig.5 Attribute trade-off of CAP theorem

雖然CAP 定理和FLP 不可能性定理都是研究分布式系統(tǒng)中的一些無解問題，但兩個定理成立的條件不同：FLP 不可能性定理假設(shè)的異步通信鏈路是可靠的，只是消息存在延遲，但不會丟失，而CAP 定理中的網(wǎng)絡(luò)分區(qū)容錯性會導(dǎo)致消息丟失；由于FLP 不可能性定理中的故障節(jié)點(diǎn)會從系統(tǒng)中完全隔離，不會對任意請求進(jìn)行響應(yīng)，但CAP 定理中的可用性要求系統(tǒng)能夠響應(yīng)請示。但不管是FLP 不可能性定理還是CAP 定理，因?yàn)榉植际较到y(tǒng)都會對一致性、可用性和可終止性有要求，所以在具體的共識算法設(shè)計(jì)時都需要考慮兩個定理的條件限制，通過合理取舍CAP 定理的相關(guān)屬性來規(guī)避FLP 不可能性。

CAP 定理指出，分布式系統(tǒng)不可能同時提供一致性、可用性和分區(qū)容錯性。同樣，在區(qū)塊鏈系統(tǒng)中也存在一個名為SHD 完整性的問題（也有研究者稱為“不可能三角”問題），即必須在安全性（security)、高性能（high-performance）和去中心化（decentralization）之間進(jìn)行權(quán)衡。

在比特幣區(qū)塊鏈系統(tǒng)中，在確保了安全性和去中心化的同時，需要以犧牲效率為代價(jià)（每秒只能處理7 筆交易，每10 min 只能產(chǎn)生一個區(qū)塊）。比特幣系統(tǒng)的缺陷不止一個，例如高性能ASIC 礦機(jī)和礦池的出現(xiàn)破壞了去中心化（當(dāng)ASIC 礦機(jī)獲得超線性回報(bào)時，普通CPU 挖礦的概率幾乎為0）。還有，隨著礦池計(jì)算能力的逐漸增強(qiáng)，有人壟斷網(wǎng)絡(luò)總計(jì)算資源的51%似乎只是時間問題，因此系統(tǒng)的安全性也岌岌可危。因此，比特幣區(qū)塊鏈已經(jīng)失去了SHD 完整性。

為了避免ASIC礦機(jī)帶來的影響，以太坊采用Ethash算法實(shí)現(xiàn)了安全性和去中心化。與此同時，作為以太坊第一個大規(guī)模智能合約應(yīng)用的CyptoKitties 算法卻暴露出了效率低下的問題。另外，從PoW 向PoS 和DPoS 的轉(zhuǎn)變極大地提高了以太坊的性能，卻嚴(yán)重影響了去中心化。

為此，如果要實(shí)現(xiàn)去中心化又要保證安全，那么在性能上需要做出犧牲（如比特幣系統(tǒng)）；如果在安全前提下實(shí)現(xiàn)高性能，就需要在去中心化上作出讓步（如私有鏈和聯(lián)盟鏈）；如果要同時實(shí)現(xiàn)去中心化和高性能，那么其安全性將無法得到保障。因此，在當(dāng)前區(qū)塊鏈系統(tǒng)中如果要實(shí)現(xiàn)SHD 完整性還需要在理論和實(shí)踐上不斷探索。

2.5 Paxos算法

Paxos 算法是Lamport 早在1990 年提出的一種在分布式系統(tǒng)中基于消息傳遞的一致性算法，為后續(xù)各類典型一致性算法研究提供了理論基礎(chǔ)和參照。不過，由于Paxos 算法的描述過于晦澀難懂，在工程應(yīng)用中很難實(shí)現(xiàn)。

概括地講，Paxos 算法具體解決的是在一個隨時可能出現(xiàn)節(jié)點(diǎn)故障或網(wǎng)絡(luò)異常（如分組延時、丟失、重傳、亂序等）的分布式系統(tǒng)中，在某一集群內(nèi)快速實(shí)現(xiàn)數(shù)據(jù)或網(wǎng)絡(luò)狀態(tài)的一致性。Paxos 算法建立在以下3個假設(shè)條件（條件12至條件14）成立的基礎(chǔ)上：

部分同步網(wǎng)絡(luò)環(huán)境。

能夠容忍一半以下數(shù)量的宕機(jī)恢復(fù)（非拜占庭故障）節(jié)點(diǎn)，即少數(shù)服從多數(shù)的“過半”規(guī)則。

不存在拜占庭將軍問題，即信道是安全可靠的，且節(jié)點(diǎn)發(fā)送出去的信息可能會出現(xiàn)丟失或重復(fù)，但不會被篡改。

由于Lamport 在文獻(xiàn)[24]中對Paxos 算法的描述很難理解，為使更多的研究者能夠掌握Paxos 算法的精髓并推動該算法的應(yīng)用，后來作者在文獻(xiàn)[39]中對該算法描述進(jìn)行了簡化，在該精簡版本的Paxos 算法中，分布式系統(tǒng)中的節(jié)點(diǎn)被分成proposer（提議者）、acceptor（接受者）和learner（學(xué)習(xí)者）共3 種角色，而且一個節(jié)點(diǎn)可以同時扮演多種角色。其中，提議者向接受者提交提案（proposal），提案中包含有決議（value）；接受者在接收到提案后對該提案進(jìn)行審批；學(xué)習(xí)者在獲取了通過審批的提案后，執(zhí)行提案中包含的決議。在此過程中，如果同時滿足只有提議者的決議才能被授受者審批、每次只能批準(zhǔn)一個決議以及決議只有被批準(zhǔn)后才能被學(xué)習(xí)者獲取并執(zhí)行這3 個條件，就可以保證數(shù)據(jù)的一致性。

如圖6 所示，Paxos 算法的執(zhí)行分為兩個階段，每個階段又分為兩個子過程。

圖6 Paxos算法運(yùn)行過程描述Fig.6 Description of running process of Paxos algorithm

第一階段（準(zhǔn)確階段）：（1）提議者選擇一個提案編號，然后向一半以上的接受者發(fā)送該編號的準(zhǔn)備請求。（2）接受者在收到該準(zhǔn)備請求后，如果其中的編號大于其已經(jīng)響應(yīng)過的所有準(zhǔn)備請求的編號，則對該請求做出響應(yīng)，并將其已經(jīng)接受過的最大編號的提案（如果有的話）回復(fù)給提議者，同時接受者承諾不再授受任何編號小于的提案；如果還沒有接受過提案，則返回當(dāng)前的編號。

第二階段（提議階段）：（1）如果某個提議者收到半數(shù)以上授受者對其編號為的準(zhǔn)備請求的應(yīng)答，那么該提議者就會向這些接受者返回一個針對[,]提案的授受請求，其中是應(yīng)答中編號最大的提案的值；如果應(yīng)答中沒有任何提案，那么就由提議者任意設(shè)置。（2）如果接受者收到針對編號的接受請求，只要該接受者尚未對編號大于的準(zhǔn)備請求做出過響應(yīng)，便接受該提案，并返回接受應(yīng)答。

在以上兩個階段中，每個階段對應(yīng)的請求和應(yīng)答（響應(yīng)）內(nèi)容各不相同。

作為分布式共識設(shè)計(jì)時參考的一個重要算法，Paxos 算法已經(jīng)應(yīng)用到Google Chubby、Microsoft Autopilot、微信PaxoStore等重要的分布式服務(wù)中。另外，在Paxos 算法的基礎(chǔ)上，相繼設(shè)計(jì)出了應(yīng)用于不同場景且易于理解和實(shí)現(xiàn)的共識算法，如Raft、Zookeeper、etcd等。

表1 對經(jīng)典分布式共識算法進(jìn)行了匯總，并對各算法涉及到的主要特性進(jìn)行了說明。

表1 經(jīng)典共識算法Table 1 Classical consensus algorithm

3 區(qū)塊鏈共識算法

當(dāng)中本聰在其那篇經(jīng)典的論文“Bitcoin：a peerto-peer electronic cash system”中描述了一個在不需要第三方機(jī)構(gòu)就可以實(shí)現(xiàn)點(diǎn)對點(diǎn)在線支付的比特幣系統(tǒng)后，支撐這一“神奇”應(yīng)用場景且對傳統(tǒng)中心化系統(tǒng)產(chǎn)生顛覆作用的區(qū)塊鏈技術(shù)得到全球范圍的關(guān)注，也引發(fā)了區(qū)塊鏈共識算法的研究熱潮，同時產(chǎn)生了大量創(chuàng)新性的應(yīng)用。雖然各類共識算法伴隨著區(qū)塊鏈產(chǎn)品及應(yīng)用的迭代不斷推陳出新，但就其算法的核心仍然是BFT、PBFT、PoW 和PoS 共識算法，其他大量算法幾乎都是以上4 類基本算法的性能優(yōu)化、功能擴(kuò)展和應(yīng)用組合。

3.1 PoW 共識算法

雖然比特幣系統(tǒng)首次使用了工作量證明（proof of work，PoW）算法實(shí)現(xiàn)挖礦過程，但工作量證明的概念早在1999 年就已經(jīng)提出，并在防范垃圾郵件和拒絕服務(wù)（denial of service，DoS）攻擊等功能中得到了應(yīng)用。

比特幣區(qū)塊鏈的PoW 共識機(jī)制借鑒了哈?，F(xiàn)金（HashCash）的思想。哈?，F(xiàn)金最早用來處理垃圾郵件，發(fā)件人發(fā)送的郵件正文中必須包含一段由收件人地址、發(fā)送時間和計(jì)數(shù)器（counter）組成的郵件簽名，其中計(jì)數(shù)器功能需要使郵件簽名滿足條件：利用SHA-1 算法對郵件簽名生成一個160 bit 長度的哈希值，該哈希值的前20 位全為0。于是，郵件發(fā)送方在發(fā)送郵件前需要不斷調(diào)整計(jì)數(shù)器的值（counter++），生成滿足條件的郵件簽名。對于郵件服務(wù)器來說，只需要進(jìn)行一次SHA-1 計(jì)算并判斷簽名是否滿足條件即可。SHA-1 的碰撞概率和散列算法的不可預(yù)測性，決定了HashCash 系統(tǒng)的安全性。

定義10（比特幣PoW 共識算法）在比特幣網(wǎng)絡(luò)中，給定一個難度值，存在一個區(qū)塊中容納的所有交易數(shù)據(jù)，計(jì)算滿足條件的（number only used once）值，使得兩次SHA-256 計(jì)算得到的值小于：

其中，在確定（新區(qū)塊中“區(qū)塊體”中的交易信息已確定）的情況下，不斷重復(fù)選取隨機(jī)數(shù)，直至找到滿足條件的為止。

由定義10 可見，在PoW 共識算法中，礦工只有不斷改變輸入的值，才能在競爭中獲勝，而競爭力的大小由礦工節(jié)點(diǎn)的算力大小決定，因此算法的競爭最后轉(zhuǎn)變到比特幣網(wǎng)絡(luò)中哈希算力的競爭上。另外，難度值的大小用于控制比特幣的出塊時間在系統(tǒng)約定的10 min 左右，新難度值與舊難度值之間的關(guān)系為：

其中，代表產(chǎn)生前面2 016 個區(qū)塊所用的時間。雖然在PoW 共識機(jī)制中引入了大小為32 Byte的難度值，但在比特幣區(qū)塊頭部中卻只用4 Byte 的“Bits”（難度位）字段來設(shè)置難度大小，因此在PoW 共識算法的具體實(shí)現(xiàn)中使用了與難度值對應(yīng)的“目標(biāo)值”（用表示）概念，目標(biāo)值與難度值之間的關(guān)系為：

其中，表示最大目標(biāo)值，即比特幣創(chuàng)世區(qū)塊（genesis block）的“Bits”字段值0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFFFFFF，是一個64 位的16 進(jìn)制固定值，該值用小端法（little-endian）表示為0x1d00FFFF。

在PoW 共識系統(tǒng)中，一定會存在在計(jì)算上嚴(yán)重不對稱的兩個角色：工作者和驗(yàn)證者。其中，工作者需要進(jìn)行一定難度的哈希計(jì)算得出一個結(jié)果，而驗(yàn)證者通過簡單的計(jì)算就可以判斷工作者是否做了相應(yīng)難度的工作。

如圖7 所示的是比特幣系統(tǒng)中PoW 共識算法的執(zhí)行流程，其主要實(shí)現(xiàn)過程如下：

（1）根據(jù)區(qū)塊數(shù)據(jù)結(jié)構(gòu)，將鑄幣（coinbase）交易和節(jié)點(diǎn)緩存中已簽名的交易打包進(jìn)區(qū)塊形成完整的區(qū)塊體，通過默克爾樹（Merkle tree）算法生成默克爾根（Merkle-root）。

（2）判斷距上次難度值調(diào)整時是否已經(jīng)產(chǎn)生了2 016 個區(qū)塊，如果是，馬上進(jìn)行難度值的調(diào)整，以獲得新的難度位（Bits）；否則使用原來的難度值繼續(xù)進(jìn)行挖礦。

圖7 比特幣系統(tǒng)中PoW 共識算法的實(shí)現(xiàn)流程Fig.7 Realization process of Po Wconsensus algorithm in bitcoin system

（3）將區(qū)塊頭部當(dāng)前版本號（version）、前一區(qū)塊哈希（prev-block Hash）、當(dāng)前難度值（Bits）、隨機(jī)數(shù)（nonce）、Merkle 根（Merkle-root）以及時間戳（times tamp）6 個字段共80 Byte 數(shù)據(jù)作為工作量證明的輸入值，不斷調(diào)整隨機(jī)數(shù)，并對每次調(diào)整后的區(qū)塊頭進(jìn)行雙SHA-256 運(yùn)算，將運(yùn)算值與當(dāng)前的難度值進(jìn)行比較，如果小于難度值則挖礦成功。

（4）礦工將新挖出的區(qū)塊向全網(wǎng)廣播，希望獲得新區(qū)塊的記賬權(quán)從而獲得比特幣發(fā)行獎勵。節(jié)點(diǎn)對接收到的新區(qū)塊進(jìn)行驗(yàn)證，如果驗(yàn)證無誤就將該區(qū)塊添加到主鏈上，并以此區(qū)塊為基礎(chǔ)繼續(xù)下一個區(qū)塊的挖礦工作。

通過以上過程，交易信息將被寫入各記賬節(jié)點(diǎn)的區(qū)塊中，形成一個分布式的一致性賬本。

由于比特幣在加密貨幣領(lǐng)域取得巨大成功，PoW共識算法也引起了區(qū)塊鏈研究者的廣泛關(guān)注，隨即在原生PoW 共識算法的基礎(chǔ)上推出了一批具有影響力的算法。

（1）比特幣PoW 共識算法

PoW 共識算法最典型和成功的應(yīng)用場景是比特幣（Bitcon），后來針對工作量證明的共識算法基本上都是針對比特幣系統(tǒng)存在的缺陷和不足衍生出來的，因此可以將比特幣系統(tǒng)中的PoW 共識算法稱為“原生”PoW 共識算法。

比特幣系統(tǒng)是一個基于互聯(lián)網(wǎng)的分布式賬本，節(jié)點(diǎn)緩存中的交易打包進(jìn)礦工的區(qū)塊，并通過算力競爭和P2P 網(wǎng)絡(luò)同步最終獲得對區(qū)塊的記賬權(quán)。作為第一個成功的加密貨幣，挖礦過程扮演著貨幣發(fā)行的角色，礦工在成功獲得區(qū)塊的記賬權(quán)后，系統(tǒng)會以一定數(shù)量的比特幣（BTC）給礦工以獎勵，該獎勵以鑄幣交易（coinbase transaction）形式作為下一個區(qū)塊的第一個交易打包進(jìn)區(qū)塊，從而實(shí)現(xiàn)了貨幣的發(fā)行過程。在比特幣系統(tǒng)中，鑄幣交易只有一個輸出，該輸出地址即為礦工的比特幣地址，其他交易的實(shí)質(zhì)是賬戶間比特幣的轉(zhuǎn)移，根據(jù)具體的支付要求，一筆交易可能存在多個輸入和多個輸出，每一個輸入或輸出都代表著參與本筆交易各方的比特幣地址。

比特幣系統(tǒng)規(guī)定每個區(qū)塊大小為1 MB，每筆交易限制在250 Byte 左右，區(qū)塊的出塊時間限制在約10 min，因此比特幣的交易量只有每秒約7筆（1×1 024×1 024/250 ≈7）；另外，在比特幣系統(tǒng)中，一個區(qū)塊在主鏈上的深度只有達(dá)到6 個時才能被最終確認(rèn)，因此一筆交易從發(fā)生到最后確認(rèn)需要約1 h，如此小的交易量和超長的確認(rèn)時間限制了PoW 共識算法的應(yīng)用推廣；還有，中本聰為了解決拜占庭將軍問題，在比特幣系統(tǒng)中引入了競爭挖礦機(jī)制，所采用的PoW 共識算法在最大可能實(shí)現(xiàn)公平性的同時，支持哈希運(yùn)算挖礦所需的巨大算力唯一的價(jià)值是保障了比特幣的安全性，除此之外對于現(xiàn)實(shí)社會沒有任何意義。

（2）以太坊Ethash 共識算法

雖然比特幣和以太坊都使用了PoW 共識算法，但兩者分屬于區(qū)塊鏈技術(shù)發(fā)展的不同階段。以比特幣為代表的加密貨幣是區(qū)塊鏈1.0時代的典型代表，比特幣系統(tǒng)存在著非圖靈完備、腳本簡單、缺少狀態(tài)控制機(jī)制、擴(kuò)展性差等不足，而以太坊由于對智能合約的完美支持而被稱為“全球計(jì)算機(jī)”，成為區(qū)塊鏈2.0 時代的典型應(yīng)用場景。相對于比特幣，以太坊提供了賬戶模式（沒有使用比特幣的UTXO 模式）、圖靈完備、更好的隱私保護(hù)、更優(yōu)的共識機(jī)制等功能。

由于比特幣PoW 共識算法中的哈希運(yùn)算采用雙SHA-256，只消耗CPU 資源，而對內(nèi)存要求不高，這樣很容易設(shè)計(jì)和制造專用于算法需求的ASIC 芯片進(jìn)行挖礦。為了克服比特幣存在的不足，以太坊中的PoW 共識算法采用“內(nèi)存困難”機(jī)制，主要思想是增加PoW 算法的復(fù)雜性，使其在運(yùn)算中需要大量內(nèi)存的支持，以此來抵制ASIC 專用芯片挖礦，其中以太坊中使用的方案便是利用大內(nèi)存基于有向無環(huán)圖（directed acyclic graph，DAG）機(jī)制的Ethash共識算法。

Ethash 共識算法是目前以太坊基于PoW 的挖礦算法，它的前身是Dagger Hashimoto 算法。Dagger Hashimoto 算法的設(shè)計(jì)目的是抵制ASIC 專用芯片挖礦、輕客戶端驗(yàn)證和全鏈數(shù)據(jù)存儲。圖8 所示的是Ethash 共識算法的實(shí)現(xiàn)流程。與比特幣中的原生PoW 共識算法相比較，Ethash 共識算法不僅需要尋找值，同時還填入一項(xiàng)在挖礦過程中計(jì)算出來的混合摘要（）值，值不僅作為礦工消耗內(nèi)存挖礦的工作量證明，而且驗(yàn)證者在驗(yàn)證區(qū)塊的有效性時也需要使用到該值。Ethash 共識算法的實(shí)現(xiàn)過程主要分為以下幾個步驟：

①生成種子（seed）。一個窗口期（epoch length）等于30 000（以太坊約15 s 產(chǎn)生一個新區(qū)塊，因此窗口期約為15 h），即每30 000 個區(qū)塊形成一個窗口（epoch），每個窗口更新一次數(shù)據(jù)集（dataset）。Seed的初始值為0，每經(jīng)過一個窗口期會取前一個seed 的哈希值作為下一個窗口的seed。

圖8 以太坊Ethash 共識算法的實(shí)現(xiàn)流程Fig.8 Realization process of Ethash consensus algorithm in Ethereum system

②生成緩存（cache）。根據(jù)seed計(jì)算出一個16 MB的用于輔助校驗(yàn)區(qū)塊和生成數(shù)據(jù)集（dataset）的偽隨機(jī)cache，由輕客戶端存儲。

③生成數(shù)據(jù)集（dataset）。根據(jù)cache 由特定算法生成一個1 GB 的DAG 數(shù)據(jù)集（dataset），其中dataset中的每一項(xiàng)數(shù)據(jù)都是通過cache 中的256 項(xiàng)數(shù)據(jù)計(jì)算而來。cache 和dataset的大小每經(jīng)過一個窗口期會重新計(jì)算一次，由全節(jié)點(diǎn)（如礦工）存儲，而輕客戶端只存儲cache。

④挖礦。礦工根據(jù)區(qū)塊頭遞歸長度（recursive length prefix，RLP）、從dataset 中隨機(jī)取出的數(shù)據(jù)和Nonce 進(jìn)行數(shù)據(jù)混合運(yùn)算得到混合摘要值。當(dāng)對混合摘要的哈希計(jì)算結(jié)果符合區(qū)塊難度要求時挖礦成功；否則，繼續(xù)Nonce++運(yùn)算，直到符合條件。

⑤驗(yàn)證。節(jié)點(diǎn)收到新區(qū)塊時，根據(jù)存儲在本地的cache 重新生成dataset 中所需要的數(shù)據(jù)，再結(jié)合區(qū)塊頭中的信息來驗(yàn)證難度值。

以太坊中Ethash 共識算法的主要功能可以分為生成和管理數(shù)據(jù)集以及挖礦兩個階段，其中區(qū)塊、種子、緩存和數(shù)據(jù)集之間的關(guān)系如圖9 所示。

圖9 Ethash 算法中區(qū)塊、種子、緩存和數(shù)據(jù)集之間的關(guān)系Fig.9 Relationship among block,seed,cache,and dataset in Ethash algorithm

除Ethash 共識算法外，萊特幣（Litecoin,LTC）通過剛性內(nèi)存哈希函數(shù)Scrypt 取代原生PoW 中的SHA-256，達(dá)世幣（DASH）通過11 種哈希函數(shù)的混合運(yùn)算來提高算法的復(fù)雜性。目前，以太坊正在從基于PoW 的Ethash 共識算法向著PoW/PoS 混合過渡，最后將完全運(yùn)行在PoS 共識算法下。

另外，由于智能合約的引入，使得以太坊應(yīng)用場景不再限于加密貨幣，而是延伸到了更廣泛的應(yīng)用，因此在以太坊平臺只有提供手續(xù)費(fèi)（gas）的交易才能最終被打包到區(qū)塊中，以太坊手續(xù)費(fèi)的基本標(biāo)準(zhǔn)為×，其中是系統(tǒng)根據(jù)交易難度設(shè)定的手續(xù)費(fèi)，而是交易者實(shí)際設(shè)置的手續(xù)費(fèi)，當(dāng)實(shí)際提供的手續(xù)費(fèi)低于標(biāo)準(zhǔn)手續(xù)費(fèi)時，礦工一般不會接受這筆交易，某筆交易如果需要盡快被打包確認(rèn)便會提高交易的手續(xù)費(fèi)。

還有，由于以太坊的出塊速度約為15 s，相對較短的出塊間隔在交易數(shù)量增多的情況下容易產(chǎn)生分叉。為了維護(hù)最長鏈規(guī)則，以太坊使用了貪婪最重可見子樹協(xié)議（greedy heaviest observed subtree，GHOST），也稱為“幽靈”協(xié)議算法，使沒有被打包到主鏈上的區(qū)塊（稱為“叔塊”，uncle block）的創(chuàng)建者以及對叔塊的引用者都能夠拿到一定的以太幣（ETH）補(bǔ)償。一方面，使原來打包進(jìn)叔塊的交易被確認(rèn)，提高交易的效率；另一方面，將創(chuàng)建叔塊的誠實(shí)節(jié)點(diǎn)的算力納入到整個區(qū)塊鏈的算力中，提高了系統(tǒng)的安全性。

（3）Bitcoin-NG

限制比特幣系統(tǒng)效率的主要因素有區(qū)塊大小（每個區(qū)塊約1 MB）和出塊速度（約10 min）。如果單純地增加區(qū)塊大小也可以增加單個區(qū)塊容納的交易數(shù)量，進(jìn)而提高系統(tǒng)的效率，但是隨著區(qū)塊大小的增大，網(wǎng)絡(luò)的延時也會隨之增大，效率反而會降低；如果單純縮短出塊速度，可以縮短交易的確認(rèn)時間，但將會導(dǎo)致頻繁發(fā)生分叉，系統(tǒng)的安全性大大降低。為了解決比特幣的效率問題，以提高區(qū)塊鏈的吞吐量，Eyal等人提出了Bitcoin-NG擴(kuò)容算法。

在Bitcoin-NG 算法中，每個窗口（epoch）仍然是10 min，但在每個窗口期內(nèi)系統(tǒng)會進(jìn)行兩步操作：選擇一位“領(lǐng)導(dǎo)者”（leader）和交易序列化（transaction serialization）。相應(yīng)的存在兩類區(qū)塊：主塊（key block）和微塊（micro block）。其中，選擇領(lǐng)導(dǎo)者的過程與比特幣挖礦相同，由領(lǐng)導(dǎo)者挖出的區(qū)塊為主塊，但主塊中不包含交易信息。領(lǐng)導(dǎo)者選出后，負(fù)責(zé)在窗口期內(nèi)（下一個新領(lǐng)導(dǎo)者出現(xiàn)之前）收集交易信息，并將其打包進(jìn)一個個微塊，每個微塊的大小不能超過預(yù)設(shè)值的上限，微塊的形成時間約為10 s，生成微塊的過程不需要工作量證明，即不需要消耗算力。由于微塊的生成速度遠(yuǎn)遠(yuǎn)大于主塊，如果簡單地采用比特幣的最長鏈原則將無法實(shí)現(xiàn)領(lǐng)導(dǎo)者的選擇，因此Bitcoin-NG 算法中引入了區(qū)塊權(quán)重的原則，且規(guī)定微塊是沒有權(quán)重的，在Bitcoin-NG 算法中礦工維護(hù)的是一條最長且權(quán)重最大的鏈。

如圖10所示，與比特幣的區(qū)塊頭部相比，Bitcoin-NG 的主塊多了一個用于存放當(dāng)前領(lǐng)導(dǎo)者公鑰（PK）的字段，因?yàn)榻灰妆淮虬M(jìn)微塊后，為了實(shí)現(xiàn)對微塊所屬領(lǐng)導(dǎo)者的驗(yàn)證，需要用領(lǐng)導(dǎo)者自己的私鑰對生成的微塊進(jìn)行簽名（sig）；為了激勵礦工按照約定規(guī)則挖礦并打包交易，在Bitcoin-NG 算法中，挖到主塊的礦工獲得類似于比特幣中的挖礦獎勵，而對于當(dāng)前窗口期內(nèi)生成微塊的所有交易費(fèi)中，40%歸當(dāng)前領(lǐng)導(dǎo)者所有，60%歸下一個領(lǐng)導(dǎo)者所有，這樣做的目的主要是防止貪心礦工進(jìn)行自私挖礦（selfish mining）。

圖10 Bitcoin-NG 共識算法示意圖Fig.10 Schematic diagram of Bitcoin-NG consensus algorithm

在Bitcoin-NG 算法中，微塊不需要進(jìn)行挖礦競爭就可以輕松生成并發(fā)布，這樣作惡領(lǐng)導(dǎo)者便可以構(gòu)造不同的微塊并發(fā)送給不同節(jié)點(diǎn)實(shí)現(xiàn)對系統(tǒng)的雙花攻擊。為了防止雙花攻擊，Bitcoin-NG 算法采用了一種稱為“毒藥交易”（poison transaction）的特殊交易。當(dāng)領(lǐng)導(dǎo)者發(fā)現(xiàn)前面的某個領(lǐng)導(dǎo)者是作惡領(lǐng)導(dǎo)者時，他將作惡領(lǐng)導(dǎo)者的信息打包到自己的微塊中并發(fā)布，這樣作惡領(lǐng)導(dǎo)者原來獲得的獎勵將全部被收回，同時進(jìn)行“舉報(bào)”的領(lǐng)導(dǎo)者將獲得作惡領(lǐng)導(dǎo)者總獎勵5%的獎勵。另外，為了防止區(qū)塊鏈產(chǎn)生分叉，Bitcoin-NG 算法還引入了“報(bào)酬審核期”的概念，規(guī)定交易費(fèi)在100 個主塊后才能使用。

Eyal等人在約1 000 個節(jié)點(diǎn)組成的比特幣系統(tǒng)上對Bitcoin-NG 算法進(jìn)行了模擬實(shí)驗(yàn)，對其良好的可擴(kuò)展性、有效提升吞吐量和明顯降低延遲等特性進(jìn)行了有效驗(yàn)證，成為區(qū)塊鏈擴(kuò)容方案中具有代表性的共識算法。

（4）其他典型PoW 共識改進(jìn)算法

由于PoW 共識算法在區(qū)塊鏈技術(shù)中的奠基石作用，研究者通過算法優(yōu)化與改進(jìn)，在原生PoW 算法基礎(chǔ)上提出了大量有代表性的算法：2016 年Kokoris-Kogias 等人提出了ByzCoin共識算法，該算法采用了與Bitcoin-NG 同樣的思路，將區(qū)塊分為主塊（key block）和微塊（micro block）。只是在ByzCoin 算法中，一旦發(fā)現(xiàn)有作惡領(lǐng)導(dǎo)者，礦工將通過投票方式，在票數(shù)超過67%閾值時便取消該作惡領(lǐng)導(dǎo)者的資格，并取消所有的獎勵。ByzCoin 算法可以有效防止Bitcoin-NG 算法中可能存在的作惡領(lǐng)導(dǎo)者；2017 年，Kokoris-Kogias 等人在借鑒ELASTICO 共識算法并行跨分片處理功能的基礎(chǔ)上，對ByzCoin 共識算法進(jìn)行了優(yōu)化，提出了ByzCoinX 共識算法，使區(qū)塊鏈系統(tǒng)的可擴(kuò)展性和安全性都有了較大提高；2017 年，Pass 和Shi 提出了FruitChains 共識算 法。該算法 提出了Frui（t水果）的概念，其中一個Fruit 中可能包括多個交易，而一個區(qū)塊中也可能包含多個Fruit，F(xiàn)ruit和區(qū)塊利用同一個哈希尋找工作量證明，從而提高比特幣系統(tǒng)中挖礦的公平性；2018 年，來自清華大學(xué)的Li 等人提出了Conflux 共識算法。該算法先用DAG 圖來算出區(qū)塊順序，再決定要保留的交易數(shù)據(jù)，然后生成沒有分叉的單鏈結(jié)構(gòu)，使交易的吞吐率提升到每秒6 000 次以上。

除此之外，針對PoW 共識算法主要在能耗和51%攻擊方面存在的問題，研究人員提出了一些改進(jìn)算法：為了有效緩解PoW 算法的能耗問題，Lasla 等人提出了Green-PoW 共識算法，通過對挖掘過程中所消耗能量的再利用，可以將挖礦的能耗降低到50%左右；為了解決PoW 共識算法高能耗和51%攻擊問題，Kara 等人提出了CW-PoW 算法，該算法通過引入多輪證明的方式在能耗和對51%攻擊及Sybil 攻擊的魯棒性方面取得了明顯成效；針對PoW 共識算法存在的不足，Qu 等人提出了聯(lián)合學(xué)習(xí)證明算法（proof of federated learning，PoFL），該算法將聯(lián)邦學(xué)習(xí)理論用于區(qū)塊鏈工作證明，加強(qiáng)了對用戶隱私信息的保護(hù)等。

表2 列出了針對PoW 共識算法及其主要改進(jìn)算法的相關(guān)信息。

表2 PoW 及其改進(jìn)算法Table 2 PoW and its improved algorithms

3.2 PoS 共識算法

對于比特幣來說，成也PoW，敗也PoW。PoW 共識算法通過所有參與節(jié)點(diǎn)之間的算力競爭，提交一個計(jì)算困難但驗(yàn)證容易的計(jì)算結(jié)果，任何節(jié)點(diǎn)都可以通過簡單的運(yùn)算來驗(yàn)證結(jié)果的正確性進(jìn)而承認(rèn)被驗(yàn)證者的工作量，這一機(jī)制有效維護(hù)了比特幣系統(tǒng)的安全性和穩(wěn)定性。然而，PoW 算法存在的算力不公平、資源浪費(fèi)、效率低下等問題，嚴(yán)重限制了比特幣區(qū)塊鏈技術(shù)向加密貨幣領(lǐng)域之外的延伸和拓展。鑒于此，研究者提出了針對工作量證明機(jī)制的替代算法，權(quán)益證明（PoS）便是其中的一種。

PoW 共識算法是通過消耗現(xiàn)實(shí)生產(chǎn)生活中的價(jià)值（算力）來維護(hù)區(qū)塊鏈的價(jià)值體系，而PoS 共識算法則是在一套規(guī)則的支持下，利用已有的價(jià)值（權(quán)益）來達(dá)成共識從而不斷衍生出新的價(jià)值，進(jìn)而在一個“自治系統(tǒng)”（不需要像PoW 那樣從外界輸入算力）中維護(hù)區(qū)塊鏈的價(jià)值體系。

2011 年，Quantum Mechanic 首次提出了PoS 共識算法，算法中規(guī)定了用節(jié)點(diǎn)擁有的比特幣數(shù)量來替代PoW 共識算法中基于算力求解哈希值的過程，即礦工擁有的比特幣數(shù)量越多挖到礦的可能性就越大。2012 年，King 等人設(shè)計(jì)了點(diǎn)點(diǎn)幣（PPCoin 或PeerCoin）并在系統(tǒng)中首次實(shí)現(xiàn)了PoS 共識算法。

參照PoW 共識機(jī)制的定義，將PPCoin 中的PoS共識算法稱為原生PoS 共識算法。原生PoS 共識算法中引入了“幣齡”的概念，相關(guān)定義如下：

（幣齡）幣齡（）是指持幣數(shù)量（）與持幣時間（）的乘積：

（PoS 共識算法）給定一個全網(wǎng)統(tǒng)一的難度值，以及新打包進(jìn)區(qū)塊的元數(shù)據(jù)，尋找滿足條件的記數(shù)器，使得：

PoS 共識算法的記賬規(guī)則與PoW 共識算法基本相似，但PoS 共識算法不需要礦工枚舉所有的隨機(jī)數(shù)，而是在1 s 內(nèi)只允許一次哈希值，大大減輕了計(jì)算工作量，從而減緩了算力競爭帶來的資源消耗。

由于PoS 共識算法的提出主要是為了解決PoW共識算法的缺陷，通過與PoW 共識算法的比較便可以體現(xiàn)PoS 共識算法的優(yōu)勢：

（1）PoS 是通過權(quán)益大小來尋找哈希值，不存在因算力競爭浪費(fèi)能源的問題。誕生于2013 年11 月24 日的Nextcoin（未來幣）是一個全新的使用PoS共識算法的第二代虛擬貨幣。

（2）由于PoS 共識算法采用類似“幣齡”的權(quán)益值，并對成功挖礦者采用了幣齡“清零”機(jī)制，PoS 共識算法更加公平。

（3）為了防止節(jié)點(diǎn)離線積累幣齡，2014 年Vasin提出了PoS2.0并應(yīng)用到黑幣（BlackCoin）中，從而使黑幣從當(dāng)時的PoW+PoS 共識模式發(fā)展到了純PoS共識模式。PoS2.0 共識算法中的權(quán)益大小與用戶在線時間成正比，這種激勵機(jī)制有效增強(qiáng)了區(qū)塊鏈P2P網(wǎng)絡(luò)的健壯性，防止了PoW 共識算法中“公地悲劇”（tragedy of the commons）的發(fā)生，而且使得攻擊者實(shí)現(xiàn)“51%攻擊”的難度大大增加等。但PoS 共識算法容易產(chǎn)生分叉，且區(qū)塊鏈的去中心化特點(diǎn)被弱化。

需要說明的是：PoS 共識算法最早運(yùn)行在PPCoin系統(tǒng)，但PPCoin 系統(tǒng)中使用的是PoS+PoW 混合共識算法。

（1）DPoS 共識算法

針對PoS 共識算法主要存在離線節(jié)點(diǎn)積累幣齡和某些擁有權(quán)益的節(jié)點(diǎn)無意挖礦等缺陷，2014 年4月，Larimer 在PoS 共識算法的基礎(chǔ)上提出了委托權(quán)益證明（delegated proof of stake，DPoS）共識算法。DPoS 共識算法引入了類似企業(yè)董事會的管理機(jī)制，權(quán)益持有者通過投票方式選擇能夠代表自己利益的委托人（票數(shù)與持有代幣的多少成正比），被選出的受信任的委托人需要交納一定數(shù)量的保證金，最后形成一個由101 個委托人組成的集合。該集合中的委托人將以平等的權(quán)利按規(guī)則輪流作為出塊者生成區(qū)塊，并從每筆交易的手續(xù)費(fèi)中獲得收益。在此期間，如果某個委托人違反了出塊規(guī)則，其委托人身份將被新選出的委托人替代，而且其保證金也被系統(tǒng)沒收。

DPoS 共識算法通過選舉委托人的方式來確定區(qū)塊的生成者，縮短了交易的確認(rèn)時間，提高了系統(tǒng)的效率，但由于被選舉出的負(fù)責(zé)挖礦的委任人數(shù)量僅為101 個，DPoS 共識算法是一個去中心化（針對權(quán)益持有者）和中心化（委托人）相結(jié)合的共識算法。另外，DPoS 共識算法可能會存在委托人通過聯(lián)合操縱區(qū)塊鏈網(wǎng)絡(luò)來損害普通節(jié)點(diǎn)利益，以及通過選出不符合要求的委托人從而迫使網(wǎng)絡(luò)的性能下降等現(xiàn)象。

目前，使用DPoS 共識算法的區(qū)塊鏈應(yīng)用系統(tǒng)主要 有Bitshares（比特股）、Steem、EOS，其中Steem 和EOS 中委托人的數(shù)量都為21。

（2）Ouroboros共識算法

為了能夠在運(yùn)行PoS 共識算法的區(qū)塊鏈系統(tǒng)中實(shí)現(xiàn)類似PoW 共識算法中的安全機(jī)制，Kiayias 等人提出了Ouroboros 共識算法。Ouroboros 共識算法因其在學(xué)術(shù)領(lǐng)域產(chǎn)生的影響力，很快成為學(xué)術(shù)界認(rèn)可和產(chǎn)業(yè)界采用的可證明是安全和健壯的PoS 共識算法。目前，Cardano（ADA，艾達(dá)幣）就使用了Ouroboros共識算法。

Ouroboros 共識算法的核心是根據(jù)權(quán)益的多少來隨機(jī)選出一個出塊者，而且這個隨機(jī)過程是無法預(yù)測的。Ouroboros共識算法的運(yùn)行過程為：

①共識過程的時間被劃分為間隔相同的時隙（slot），每個被選舉出的出塊者（類似于DPoS 中的委托者）對應(yīng)一個時隙。

②每個時隙最多只能產(chǎn)生一個區(qū)塊，如果當(dāng)時隙到來時對應(yīng)的節(jié)點(diǎn)離線或生成的區(qū)塊未得到大多數(shù)節(jié)點(diǎn)的確認(rèn)，則該時隙不會生成有效區(qū)塊。

③由多個連續(xù)的時隙組成一個窗口（epoch），在一個窗口中，權(quán)益的計(jì)算是以該窗口開始時的歷史值為基準(zhǔn)，期間權(quán)益的變化不會影響當(dāng)前窗口中出塊者的選擇。

④每個窗口開始時，在礦工節(jié)點(diǎn)的計(jì)算機(jī)內(nèi)存中會生成一個genesis block，該特殊區(qū)塊僅記錄本窗口中可能參與出塊的權(quán)益持有者的候選人信息以及隨機(jī)數(shù)種子，并不會最終上鏈。

⑤在每個窗口中，以genesis block 中的每個候選人所持有權(quán)益的占比為概率，選擇每個時隙對應(yīng)的出塊者，具體的選擇函數(shù)（Cardano 中使用了followthe-Satoshi 算法）為U=(S,ρ,r)，其中U為窗口中第個時隙對應(yīng)的出塊者，S為在窗口中由所有出塊候選人組成的集合(,,…,U)，ρ為窗口中使用的隨機(jī)數(shù)種子，該隨機(jī)數(shù)種子與當(dāng)前窗口中每位候選人持有的權(quán)益（,,…,s）有關(guān)，r為第個時隙對應(yīng)的索引（index）信息。根據(jù)隨機(jī)數(shù)種子ρ，函數(shù)()從候選人集合S中隨機(jī)選出第個時隙對應(yīng)的出塊者U。

⑥由連續(xù)的窗口銜接生成的鏈便是Ouroboros共識算法形成的鏈，形成鏈的每個區(qū)塊之間的關(guān)系與比特幣相同，即當(dāng)前區(qū)塊通過上一個區(qū)塊的哈希函數(shù)來連接。

在Ouroboros 共識算法中，每一個窗口的隨機(jī)數(shù)由安全多方計(jì)算（secure multiparty computation，MPC）協(xié)議產(chǎn)生，該協(xié)議使用可公開驗(yàn)證秘密共享（publicly verifiable secret sharing，PVSS）方案。該方案基于非交互式零知識證明（non-interactive zeroknowledge，NIZK）確保了任何出塊候選人都可以在參與人數(shù)達(dá)到閾值的情況下重構(gòu)密鑰，并驗(yàn)證其有效性。

Ouroboros 共識算法的執(zhí)行流程如圖11 所示。從鏈的創(chuàng)世區(qū)塊（非每個窗口中的genesis block）開始，硬編碼了與用戶身份相關(guān)聯(lián)的公鑰密鑰對（其中公鑰pub公開，私鑰priv由用戶保存）、權(quán)益s以及初始的隨機(jī)數(shù)種子。之后，后續(xù)的每個窗口會基于前一個窗口的這些基本數(shù)據(jù)運(yùn)行，其中每個節(jié)點(diǎn)以當(dāng)前窗口的隨機(jī)數(shù)種子ρ以及genesis block 中的權(quán)益(,,…,s) 和時隙對應(yīng)的索引信息r為輸入值，獨(dú)立運(yùn)行函數(shù)U=(S,ρ,r)，根據(jù)概率獲得當(dāng)前時隙對應(yīng)的出塊者U；對于某個出塊候選人來說，如果正好自己被選擇為本時隙對應(yīng)的出塊者，則執(zhí)行交易打包和分發(fā)等操作，否則對接收到的區(qū)塊進(jìn)行驗(yàn)證操作（此過程與比特幣的挖礦過程相同）；如果被選擇的出塊者正好處于離線狀態(tài)或出現(xiàn)運(yùn)行故障，則在該時隙內(nèi)不會產(chǎn)生新區(qū)塊或生成的區(qū)塊被廢棄；在當(dāng)前窗口中，根據(jù)時隙劃分不斷執(zhí)行選擇出塊者、出塊、驗(yàn)證等操作，直到最后一個時隙結(jié)束。在整個窗口操作結(jié)束后，會在每個節(jié)點(diǎn)的內(nèi)存中生成下一個窗口的隨機(jī)數(shù)種子ρ以及出塊候選人集合，隨后進(jìn)入下一個窗口的操作流程。

圖11 Ouroboros共識算法的執(zhí)行流程Fig.11 Implementation process of Ouroboros consensus algorithm

Ouroboros 共識算法的最大特點(diǎn)是通過安全、多方執(zhí)行的協(xié)議來實(shí)現(xiàn)每個時隙出塊者選擇的隨機(jī)性，以確保出塊者的選擇不會被攻擊者操縱。但該算法不適合完全去中心化的應(yīng)用場景。

Ouroboros 共識算法中，在選擇每個時隙對應(yīng)的出塊者時隨機(jī)數(shù)種子發(fā)揮著十分重要的作用，但由于該隨機(jī)數(shù)種子生成函數(shù)是公開的，即在每個窗口（epoch）開始的時候，所有節(jié)點(diǎn)已經(jīng)知道整個窗口中所有的候選人，作惡節(jié)點(diǎn)可以利用這一缺陷有針對性地進(jìn)行賄賂攻擊或DDoS 攻擊；另外，對于MPC來說，隨著參與節(jié)點(diǎn)數(shù)量的增加，其性能則會降低；還有，Ouroboros 共識算法的攻擊模型=2+1 建立在同步網(wǎng)絡(luò)模型中，對通信環(huán)境提出了較高要求。

（3）Ouroboros Praos共識算法

針對Ouroboros 共識算法存在的不足，David 等人在Ouroboros 基礎(chǔ)上提出了改進(jìn)的Ouroboros Praos 共識算法。該算法的主要改進(jìn)是在選擇出塊候選人時，用可驗(yàn)證隨機(jī)函數(shù)（verifiable random function，VRF）替代公開偽隨機(jī)函數(shù)，從而使每個節(jié)點(diǎn)可以使用不同的隨機(jī)函數(shù)判斷自己是否是出塊候選人。當(dāng)某個節(jié)點(diǎn)被確定為某個時隙對應(yīng)的出塊候選人時直接出塊，該塊中同時包含有區(qū)塊驗(yàn)證時所需要的證明信息。其他節(jié)點(diǎn)只有在收到區(qū)塊時才知道誰是出塊者，這樣系統(tǒng)的安全性和出塊速度都得到了大幅度提升。另外，在Ouroboros Praos 共識算法的基礎(chǔ)上，Ganesh 等人提出了匿名可驗(yàn)證隨機(jī)函數(shù)（anonymous VRF）概念，通過構(gòu)造一類通用的私有PoS（private PoS）協(xié)議，實(shí)現(xiàn)了對節(jié)點(diǎn)隱私的有效保護(hù)。

（4）Ouroboros Genesis共識算法

Ouroboros Genesis 是Ouroboros 協(xié)議的第3 個版本，由Badertscher 等人在Ouroboros Praos 基礎(chǔ)上提出。Ouroboros Genesis 主要解決的是在一個部分同步網(wǎng)絡(luò)環(huán)境中，當(dāng)一個全新節(jié)點(diǎn)或長時間離線節(jié)點(diǎn)加入網(wǎng)絡(luò)時，如何利用其他節(jié)點(diǎn)中的賬本信息來建立自己的區(qū)塊鏈賬本，即如何解決新節(jié)點(diǎn)的自舉（bootstrap）問題。PoW 共識算法使用最長鏈規(guī)則來確定本地賬本，而PoS使用替代的檢查點(diǎn)（check point）協(xié)議或拜占庭容錯機(jī)制來建立本地賬本，但這些算法的實(shí)現(xiàn)都要求節(jié)點(diǎn)在始終在線的同步網(wǎng)絡(luò)環(huán)境中。

為了解決自舉問題，Ouroboros Genesis 算法中提出了一種稱為豐富規(guī)劃（plenitude rule）的主鏈選擇機(jī)制，將從不同節(jié)點(diǎn)復(fù)制的賬本進(jìn)行比較，從中選出具有相同前綴且最長的鏈作為本地賬本。Ouroboros Genesis 算法在沒有采用檢查點(diǎn)的前提下，有效防范了攻擊者通過偽造一個符合系統(tǒng)規(guī)則的最長區(qū)塊鏈，為新節(jié)點(diǎn)或離線節(jié)點(diǎn)加入網(wǎng)絡(luò)時提供虛假賬本信息服務(wù)的長程攻擊（long range attack），并且在通用可組合（universal composable，UC）模型下形式化驗(yàn)證了算法的安全性。

（5）Snow White共識算法

Snow White 共識算法是由康奈爾大學(xué)Elaine Shi教授等人在2016 年提出的一個運(yùn)行在去中心化的異構(gòu)網(wǎng)絡(luò)環(huán)境中、提供端到端PoS的共識算法。Snow White 采用了睡眠執(zhí)行模型（sleepy execution model）實(shí)現(xiàn)了新加入節(jié)點(diǎn)或離線節(jié)點(diǎn)重新加入后實(shí)現(xiàn)共識時的具體要求。該模型中的節(jié)點(diǎn)狀態(tài)與互聯(lián)網(wǎng)中的節(jié)點(diǎn)狀態(tài)高度契合。Snow White 使用委員會重組機(jī)制，每次重組過程都以節(jié)點(diǎn)最近擁有權(quán)益的多少為依據(jù)確定委員會成員，然后通過成員權(quán)益的多少隨機(jī)選擇出塊者。Snow White 使用委員會重組機(jī)制的目的是根據(jù)系統(tǒng)中可能發(fā)生的節(jié)點(diǎn)權(quán)益變化，動態(tài)選擇委員會成員和出塊者，以防止后來破壞（posterior corruption）攻擊的發(fā)生，以提高系統(tǒng)的抗攻擊能力。同時，該機(jī)制設(shè)置了較小的委員會重組時間間隔，適應(yīng)了互聯(lián)網(wǎng)環(huán)境中節(jié)點(diǎn)頻繁加入和離開的連接特征。

Snow White雖然設(shè)置了較小的委員會重組時間，但算法中規(guī)定的節(jié)點(diǎn)權(quán)益變化不能太頻繁，以確保節(jié)點(diǎn)的投票權(quán)與其擁有權(quán)益成正比。另外，Snow White 采用了與FruitChains 算法相擬的挖礦激勵機(jī)制，交易信息放在水果中，水果放在區(qū)塊中，將出塊獎勵和區(qū)塊中包含的所有交易費(fèi)分配給相應(yīng)的出塊者。

為便于加強(qiáng)對不同算法的理解，表3 對幾個典型的PoS 共識算法的性能進(jìn)行了分類比較。

表3 典型PoS 共識算法的性能比較Table 3 Preformance comparison of typical PoS consensus algorithms

3.3 PoW+PoS 混合共識算法

PoW+PoS 共識算法結(jié)合了PoW 和PoS 的特點(diǎn)，節(jié)點(diǎn)在競爭記賬權(quán)的過程中按算法要求生成PoW 或PoS 區(qū)塊，有效解決了原來單一共識算法在安全風(fēng)險(xiǎn)、能源消耗、效率等方面存在的問題。

權(quán)益速度證明（proof of stake velocity，PoSV）共識算法由Ren 在2014 年4 月提出，并應(yīng)用到Reddcoin（蝸牛幣）中。針對PoS 中基于時間線性函數(shù)屯積幣齡的問題，PoSV 將其函數(shù)修改為指數(shù)式衰減函數(shù)，從而使幣齡的增長率隨時間呈下降趨勢，直到最后趨于0。這樣一來，新幣的幣齡增長要比老幣快，直到達(dá)到上限閾值時趨于相同。

Reddcoin 是一種加密貨幣，其前期使用PoW 算法實(shí)現(xiàn)代幣的分發(fā)，而后期使用PoSV 以提高P2P 網(wǎng)絡(luò)的安全性。

出塊獎勵和收取交易費(fèi)是區(qū)塊鏈挖礦收入的主要來源。當(dāng)出塊獎勵隨著系統(tǒng)運(yùn)行時間不斷減少時（如比特幣），挖礦者則將注意力集中到交易費(fèi)的收取，這有可能導(dǎo)致“公地悲劇”的發(fā)生，從而對系統(tǒng)安全性造成威脅。另外，當(dāng)交易費(fèi)不足以吸引挖礦者時，要么部分挖礦者可能會因?yàn)闊o利可圖而選擇離開，要么只有通過收取更高的交易費(fèi)來維持系統(tǒng)的運(yùn)行。不管選擇哪種方式，都會導(dǎo)致系統(tǒng)的安全性降低直至區(qū)塊鏈網(wǎng)絡(luò)無法正常運(yùn)行。為了解決以上問題，Bentov 等人提出了活躍證明（proof of activity，PoA）共識算法，其基本思想是盡可能激勵持幣者參與挖礦過程，在保持?jǐn)?shù)字貨幣保值甚至增值的前提下，解決維護(hù)網(wǎng)絡(luò)安全性對交易費(fèi)過度依賴的問題。PoA 共識算法的挖礦過程如下：

（1）每個礦工不斷進(jìn)行Hash 運(yùn)算，生成一個符合難度值的空區(qū)塊頭。該空區(qū)塊頭是一個特殊的區(qū)塊，其中區(qū)塊中不包含交易信息，只包含由前一區(qū)塊Hash 值、本節(jié)點(diǎn)的公鑰地址、區(qū)塊序號和Nonce 值等字段組成的區(qū)塊頭。

（2）當(dāng)某一礦工成功挖到一個空區(qū)塊頭后，將其立即向全網(wǎng)廣播。

（3）所有活躍節(jié)點(diǎn)在收到空區(qū)塊頭后對其進(jìn)行驗(yàn)證，驗(yàn)證通過后，便以組成區(qū)塊頭的字段信息作為數(shù)據(jù)源，隨機(jī)選取個股權(quán)持有者。具體選擇過程為：首先將本區(qū)塊頭的Hash 值與前一區(qū)塊頭的Hash值進(jìn)行串聯(lián)，再與一個固定值串聯(lián)，然后計(jì)算串聯(lián)后數(shù)據(jù)的Hash 值；對計(jì)算得到的Hash 值利用跟隨聰（follow-the-Satoshi）算法進(jìn)行次隨機(jī)運(yùn)算，依次生成個幸運(yùn)股權(quán)持有者。

（4）所有活躍節(jié)點(diǎn)判斷自己是否是幸運(yùn)股權(quán)持有者。如果自己是前-1 個幸運(yùn)股權(quán)持有者，則用自己的私鑰對區(qū)塊頭簽名后向全網(wǎng)廣播；如果自己是第個幸運(yùn)股權(quán)持有者，則在空區(qū)塊頭的基礎(chǔ)上通過添加區(qū)塊體內(nèi)容來構(gòu)建一個新區(qū)塊，其中區(qū)塊體中主要包括盡可能多的交易、前-1 個幸運(yùn)股權(quán)持有者分別對Hash 值的簽名以及自己對完整區(qū)塊Hash 值的簽名。然后，將生成的區(qū)塊向全網(wǎng)廣播。

（5）所有活躍節(jié)點(diǎn)在收到第個幸運(yùn)股權(quán)持有者的廣播區(qū)塊后，對其進(jìn)行驗(yàn)證，如果驗(yàn)證通過則確認(rèn)該區(qū)塊并連接到主鏈，然后繼續(xù)下一個區(qū)塊的挖礦過程。否則，丟棄該區(qū)塊。

在以上過程中，要求所有的個幸運(yùn)股權(quán)持有者都在線，其中任意一個不在線都會導(dǎo)致生成的區(qū)塊驗(yàn)證失敗。PoA 算法會周期性地通過計(jì)算丟棄區(qū)塊的數(shù)量來調(diào)整值，當(dāng)某一周期內(nèi)丟棄區(qū)塊的數(shù)量增大時，則值會減?。环駝t，值會增大。PoA 算法中，打包進(jìn)區(qū)塊的交易費(fèi)由挖出該空區(qū)塊頭的礦工和個幸運(yùn)股權(quán)持有者共享。

以太坊共識算法共有Frontier（前沿）、Homestead（家園）、Metropolis（大都會）和Serenity（寧靜）4 個階段，前3 個階段采用PoW 共識算法，第4 個階段將引入PoS 算法，即Casper投注共識算法。該共識算法增加了懲罰機(jī)制，并基于PoS 思想在記賬節(jié)點(diǎn)中選取驗(yàn)證者。

Casper 存在多個版本，其中Casper FFG（friendly finality gadget）是PoW 和PoS 的結(jié)合，用于Ethereum2.0。Casper FFG 在初始階段會發(fā)布一個Casper合約，每個用戶在向該合約存入以太幣的同時，要求寫入一個“驗(yàn)證代碼”從而成為一個可以參與對PoW產(chǎn)生的區(qū)塊進(jìn)行PoS 共識的驗(yàn)證者。驗(yàn)證者的權(quán)益大小與存入的以太幣數(shù)量多少有關(guān)。Casper FFG 并非對每一個區(qū)塊都要進(jìn)行共識，而是從創(chuàng)世區(qū)塊開始，每100 個區(qū)塊設(shè)置一個檢查點(diǎn)，僅對檢查點(diǎn)區(qū)塊進(jìn)行PoS 共識。如圖12 所示的是Casper FFG 共識算法的流程示意圖，從根（root）開始，由檢查點(diǎn),,…,B形成檢查點(diǎn)樹（checkpoint tree），從創(chuàng)世區(qū)塊開始每經(jīng)過100 個PoW 區(qū)塊便形成一個PoS 檢查點(diǎn)，從創(chuàng)世區(qū)塊開始主鏈上檢查點(diǎn)的數(shù)量即為檢查點(diǎn)的高度。每個驗(yàn)證者都要對檢查點(diǎn)進(jìn)行投票，投票的內(nèi)容是由多個高度不同的檢查點(diǎn)組成的連接，如果投票給某個連接的票數(shù)超過2/3，則該連接被稱為絕對多數(shù)連接，該連接上的所有區(qū)塊將被最終確認(rèn)并永久無法更改。

圖12 Casper FFG 共識算法流程示意圖Fig.12 Flow diagram of Casper FFG consensus algorithm

Casper FFG 的投票過程為：驗(yàn)證者生成投票消息，然后用自己的私鑰進(jìn)行簽名后向全網(wǎng)廣播。該消息主要由4 條信息組成，如表4 所示；Casper合約在接收到投票消息后進(jìn)行“苛刻條件”（slashing conditions）規(guī)則驗(yàn)證，以防范無利害關(guān)系（nothing at stake）攻擊和長程攻擊。其中，針對無利害關(guān)系攻擊，當(dāng)驗(yàn)證者同時發(fā)送了＜,,(),()＞和＜,,(),()＞兩條不同的投票消息時，要求()≠()，即一個礦工不能同時在兩條鏈上挖礦，如果Casper 合約檢查到此類現(xiàn)象的發(fā)生，將沒收該礦工（驗(yàn)證者）的以太幣押金；針對長程攻擊威脅，Ethereum2.0中引入了LMD GHOST分叉選擇規(guī)則，如果區(qū)塊鏈出現(xiàn)分叉，則選擇當(dāng)前檢查點(diǎn)中驗(yàn)證者投票最多的鏈作為主鏈。

表4 組成投票消息的4 條信息Table 4 Four pieces of information that makes up voting message

如圖13 所示，2-hop（二跳）共識算法以輪為單位，每輪分為PoW 共識和PoS 共識兩個階段，在PoW共識階段生成PoW 區(qū)塊，而在PoS 共識階段對生成的PoW 區(qū)塊進(jìn)行驗(yàn)證和確認(rèn)。通過交替進(jìn)行PoW共識和PoS 共識，增加了攻擊者的難度，有效防范了針對區(qū)塊鏈PoW 或PoS 的51%攻擊。

圖13 2-hop 區(qū)塊鏈結(jié)構(gòu)Fig.13 2-hop blockchain structure

在燃燒證明（proof of burn，PoB）共識算法中，礦工通過燃燒自己的代幣來競爭新區(qū)塊的記賬權(quán)，燃燒的代幣越多獲得記賬權(quán)的概率就越大。在此過程中，燃燒是指礦工將持有的代幣轉(zhuǎn)入到一個無法退回但可驗(yàn)證的特定地址的過程，礦工持有的代幣可能是比特幣、以太幣或其他任何一個具有PoB 協(xié)議的幣種。

表5 列出了典型的幾類PoW+PoS 共識算法主要解決的問題和典型應(yīng)用場景。

表5 典型PoW+PoS 共識算法的性能比較Table 5 Performance comparison of typical PoW+PoS consensus algorithms

3.4 PoW/PoS+BFT/PBFT 混合共識算法

為解決非拜占庭容錯的傳統(tǒng)分布式共識算法難以適應(yīng)大部分區(qū)塊鏈應(yīng)用場景的不足，提出PoW/PoS+BFT/PBFT 系列混合共識算法。該類算法將典型區(qū)塊鏈共識算法PoW/PoS 與經(jīng)典分布式共識算法BFT/PBFT 結(jié)合，通常利用PoW/PoS 選擇產(chǎn)生一個或多個分片（shard），然后在分片內(nèi)部使用BFT/PBFT 生成區(qū)塊。這里的分片也稱為委員會，它是由負(fù)責(zé)對全網(wǎng)交易信息進(jìn)行處理的節(jié)點(diǎn)組成的集合，如果所有交易在同一個集合中完成，則稱為單一分片，如果在不同集合內(nèi)部分別處理不同的交易信息，則稱為多分片。

PoW 共識算法在比特幣系統(tǒng)中取得了巨大成功，但在確認(rèn)時間和激勵機(jī)制方面遇到了挑戰(zhàn)。為此，Abraham 等人提出了Solida混合共識算法，該算法是一種基于可重構(gòu)BFT 共識的去中心化區(qū)塊鏈協(xié)議。它通過借鑒Paxos 共識算法中的領(lǐng)導(dǎo)者選舉機(jī)制，有效解決了委員會重配置問題，并在惡意節(jié)點(diǎn)數(shù)小于節(jié)點(diǎn)總數(shù)1/3 的情況下提供安全性和活性。Solida共識算法主要包括以下兩個過程：

（1）交易確認(rèn)過程。①領(lǐng)導(dǎo)者對接收到的交易計(jì)算哈希值后打包進(jìn)區(qū)塊，并將區(qū)塊和對應(yīng)交易的哈希值向全網(wǎng)廣播；②接收到領(lǐng)導(dǎo)者廣播消息的成員驗(yàn)證交易的正確性和領(lǐng)導(dǎo)者身份的合法性，驗(yàn)證通過后將該消息繼續(xù)向全網(wǎng)廣播；③如果其中一個成員接收到2+1 個其他成員針對同一區(qū)塊消息的廣播，就接受該區(qū)塊消息，并將該2+1 個消息組成一個接受證明（accept certificate）消息后向全網(wǎng)廣播；④其他成員在接收到該接受證明后，經(jīng)驗(yàn)證無誤后向全網(wǎng)廣播；⑤如果一個成員接收到了2+1 個合法的接受證明消息，便對該區(qū)塊信息進(jìn)行最終確認(rèn)，并將接收到的2+1 個成員的消息組成一個承諾證明（commit certificate）后向全網(wǎng)廣播；⑥網(wǎng)絡(luò)中的用戶在接收到該承諾證明后驗(yàn)證其消息的合法性，通過驗(yàn)證后最終完成交易的確認(rèn)。

（2）重配置過程。系統(tǒng)設(shè)定一個具有一定難度的哈希函數(shù)求解問題，求得PoW 解的節(jié)點(diǎn)將其結(jié)果廣播給委員會成員；委員會成員對PoW 解進(jìn)行驗(yàn)證，驗(yàn)證通過后將求得解的節(jié)點(diǎn)作為新的領(lǐng)導(dǎo)者；當(dāng)新領(lǐng)導(dǎo)者產(chǎn)生后，所有節(jié)點(diǎn)將在“交易確認(rèn)過程”階段已確認(rèn)的交易哈希值等相關(guān)狀態(tài)消息發(fā)送給新領(lǐng)導(dǎo)者，當(dāng)新領(lǐng)導(dǎo)者接收到2+1 個狀態(tài)消息后，將其組合成一個狀態(tài)證明（status certificate）消息，然后進(jìn)行廣播。接收到狀態(tài)證明的節(jié)點(diǎn)確認(rèn)已打包的交易信息，并進(jìn)入由新委員會成員組成的新一輪一致性共識過程。

在Solida 混合共識算法中，通過PoW 共識算法實(shí)現(xiàn)新領(lǐng)導(dǎo)者的選舉，完成新委員會成員的重新配置；利用BFT 算法完成委員會內(nèi)部成員之間的一致性共識，確保委員會內(nèi)部有超過2/3 誠實(shí)成員的前提下便能夠取得一致性共識。

另外，在由Pass 等人提出的Hybrid consensus混合共識算法中，通過結(jié)合低效的PoW 共識算法和快速的BFT 授權(quán)共識算法，實(shí)現(xiàn)在非授權(quán)環(huán)境下達(dá)成快速共識。

Chainspace 共識算法是由AI-Bassam 等人提出的一個支持多用戶自定義智能合約的分布式賬本平臺。Chainspace 提出了一種稱為分片拜占庭原子提交（sharded Byzantine atomic commit，S-BAC）的可跨多個拜占庭節(jié)點(diǎn)分片（委員會）處理通用智能合約交易的協(xié)議，B-BAC 協(xié)議結(jié)合了BFT 和原子提交，實(shí)現(xiàn)了拜占庭和異步環(huán)境下交易處理的分片內(nèi)共識。在Chainspace 中，智能合約的執(zhí)行和驗(yàn)證過程分開執(zhí)行，其對象（交易或智能合約）的執(zhí)行過程如下（如圖14 所示，其中用戶提交了一個帶有2 個輸入和1 個輸出的對象）：

圖14 Chainspace 共識算法流程示意圖Fig.14 Flow diagram of Chainspace consensus algorithm

（1）準(zhǔn)備（prepare）。用戶執(zhí)行交易啟動程序，并發(fā)送交易消息prepare(T)給至少一個誠實(shí)節(jié)點(diǎn)，確保至少有一個誠實(shí)節(jié)點(diǎn)接收到該交易。本例中，交易有分片1 和分片2 兩個輸入和分片3 一個輸出；節(jié)點(diǎn)在接收到prepare(T)消息后，每個分片中的節(jié)點(diǎn)將跨分片執(zhí)行兩階段提交協(xié)議，prepare(T)消息在分片內(nèi)部通過BFT 達(dá)成共識。

（2）過程準(zhǔn)備（process prepare）。分片1 和分片2中的節(jié)點(diǎn)在接收到prepare(T)消息后，在各委員會內(nèi)部通過BFT 共識算法來處理交易信息：如果交易有效，則提交該交易，并向委員會內(nèi)部所有節(jié)點(diǎn)廣播prepared(T,commit)承諾消息；如果交易無效，則終止該交易，并向委員會內(nèi)部所有節(jié)點(diǎn)廣播prepared(T,abort)取消消息。

（3）過程準(zhǔn)備完成（process prepared）。通過原子提交協(xié)議在不同分片之間進(jìn)行prepare(T)消息交互，如果不同分片之間交互的全部都是parpared(T,commit）消息，則交易最終達(dá)成共識，并廣播accept(T,commit)消息；如果其中有一個分片提交的是prepared(T,abort)消息，則交易共識失敗，并廣播accept(T,abort)消息。

（4）過程接受（process accept）。當(dāng)某一分片中存在accept(T,commit)廣播消息時，將在輸入分片的委員會內(nèi)部運(yùn)行BFT 共識算法，將交易交給分片進(jìn)行管理；當(dāng)某一分片中存在accept(T,abort)廣播消息時，所有分片對交易的輸入狀態(tài)進(jìn)行解鎖后，將其丟棄。

本文在一個真實(shí)的基于云環(huán)境的測試平臺上對Chainspace 算法進(jìn)行了評估，其交易吞吐量隨分片數(shù)量的增加而線性增長，每增加一個分片，每秒可提升22 個交易的處理能力。Chainspace 為集中式的授權(quán)系統(tǒng)提供了一個高效的解決方案。

2018 年，Zamani 等人提出的RapidChain混合共識算法是一個基于分片的公有鏈協(xié)議，它采用了委員會內(nèi)共識算法，在拜占庭節(jié)點(diǎn)不超過1/3 總節(jié)點(diǎn)數(shù)的非許可網(wǎng)絡(luò)環(huán)境下能夠最終取得共識的一致性，并實(shí)現(xiàn)處理交易的通信、計(jì)算和存儲開銷的完整分片。本文通過實(shí)驗(yàn)表明，在一個由4 000個節(jié)點(diǎn)組成的網(wǎng)絡(luò)中，RapidChain 算法的吞吐量超過7 300 TPS，而預(yù)期確認(rèn)延遲約為8.7 s。

雖然比特幣取得了巨大成功，但過長的交易確認(rèn)時間嚴(yán)重影響了PoW 共識協(xié)議的應(yīng)用拓展，Decker 等人提出的PeerCensus 算法被認(rèn)為是最早成功地將PBFT 與比特幣區(qū)塊鏈技術(shù)相結(jié)合形成的一種在確保安全的前提下達(dá)成快速一致性的混合共識算法。如圖15 所示，PeerCensus 算法主要由底層的區(qū)塊鏈和位于中間層的鏈協(xié)議（chain agreement，CA）兩部分組成。其中，底層的比特幣區(qū)塊鏈運(yùn)行PoW 共識選出一定數(shù)量的節(jié)點(diǎn)，對這些節(jié)點(diǎn)完成身份認(rèn)證后提交給CA；CA 通過PBFT 算法來實(shí)現(xiàn)具體功能。CA 主要有兩項(xiàng)任務(wù)：一是跟蹤系統(tǒng)中的成員，即當(dāng)前有哪些節(jié)點(diǎn)在線并參與共識，以確保PBFT 能夠發(fā)揮其作用；二是解決區(qū)塊鏈分叉問題，來實(shí)現(xiàn)最終的強(qiáng)一致性。

圖15 PeerCensus共識算法組成示意圖Fig.15 Schematic diagram of PeerCensus consensus algorithm

為了演示PeerCensus 的應(yīng)用效果，作者在論文中引入了一種名為Discoin 的新型加密貨幣。在Discoin 中，交易提交給主服務(wù)器，由主服務(wù)器給每一個交易分配序列號，并將其保存在交易的歷史記錄中。由于交易是完全有序的，這樣有效解決了雙重花費(fèi)問題，并且在提交時，所有節(jié)點(diǎn)都會認(rèn)可一個共同的交易歷史記錄，提升了安全性。

另一個基于PoW 和PBFT 混合共識的典型算法是ByzCoin。該算法采用PoW 選舉分片節(jié)點(diǎn)（委員會成員），分片內(nèi)部采用改進(jìn)的PBFT 算法完成共識。當(dāng)區(qū)塊大小為32 MB、分片中的節(jié)點(diǎn)數(shù)為144時，算法每秒的交易量可以達(dá)到974。

2016年，Luu等人提出了ELASTICO混合算法，最先將多分片技術(shù)應(yīng)用到區(qū)塊鏈中。ELASTICO 首先通過PoW 共識競爭選舉網(wǎng)絡(luò)中的記賬節(jié)點(diǎn)，然后按照預(yù)先確定的規(guī)則，將選舉得到的記賬節(jié)點(diǎn)分配到不同的分片委員會中。每個分片委員會內(nèi)部執(zhí)行PBFT 算法打包生成交易集合。該交易集合經(jīng)簽名后被提交給共識委員會。共識委員會在驗(yàn)證簽名后，最終將所有的交易集合打包成區(qū)塊并記錄在區(qū)塊鏈上。

2018 年，Kokoris-Kogias 等人在ELASTICO 算法的基礎(chǔ)上提出了基于分片的區(qū)塊鏈共識算法Omni-Ledger。該算法使用RandHound和VRF 協(xié)議將節(jié)點(diǎn)隨機(jī)分配到不同的分片上，每個分片內(nèi)部的共識采用PBFT 算法（具體為ByzCoinX 共識算法）。OmniLedger 的總體結(jié)構(gòu)如圖16 所示，由一條用于記錄不同窗口期（epoch length）分片及其包含的節(jié)點(diǎn)信息的身份鏈（identity blockchain）和多條負(fù)責(zé)產(chǎn)生和維護(hù)本分片內(nèi)部交易信息的分片鏈（shard blockchain）組成。OmniLedger共識算法的執(zhí)行過程如下：

（1）節(jié)點(diǎn)注冊。在當(dāng)前窗口期內(nèi)，節(jié)點(diǎn)參與PoW共識，將計(jì)算得到的難度值和節(jié)點(diǎn)身份信息進(jìn)行廣播。領(lǐng)導(dǎo)者在當(dāng)前分片內(nèi)運(yùn)行PBFT 共識算法，將收集到的所有合法節(jié)點(diǎn)信息注冊到身份鏈。

（2）節(jié)點(diǎn)分配。首先，每個已注冊的節(jié)點(diǎn)通過ticket=VRF(“”||config||)計(jì)算自己的票據(jù)值，其中VRF(·)代表VRF 函數(shù)，表示本次VRF 計(jì)算目的是選擇領(lǐng)導(dǎo)者，config是注冊在身份鏈上的所有的節(jié)點(diǎn)信息，是當(dāng)前計(jì)算的輪數(shù)（同一深度的區(qū)塊，可能需要多輪共識才能確定），為節(jié)點(diǎn)序號，為當(dāng)前窗口期。在一定時間內(nèi)，所有節(jié)點(diǎn)交換自己的ticket，然后將ticket值最小的節(jié)點(diǎn)選舉為當(dāng)前的領(lǐng)導(dǎo)者；在確定了領(lǐng)導(dǎo)者后，新的領(lǐng)導(dǎo)者啟動無偏差隨機(jī)數(shù)生成協(xié)議RandHound，將個合法節(jié)點(diǎn)分配到個分片中。

（3）跨分片操作。為了支持分片間的交易，Omni-Ledger 使用了UTXO 賬戶模型。假設(shè)用戶分別從Shard 1 和Shard 2 向Shard 3 轉(zhuǎn)賬，主要操作階段為：①初始化。用戶（client）上傳交易，交易的輸入分片為Shard 1 和Shard 2，輸出分片為Shard 3。②鎖定。Shard 1 和Shard 2 中的領(lǐng)導(dǎo)者在接收到交易輸入后，鎖定請求并驗(yàn)證交易的合法性，然后記錄鎖定狀態(tài)以及合法交易在本分片UTXO 中的Merkle 樹路徑。③解鎖。分兩種情況：一是提交跨分片確認(rèn)請求。如果Shard 1 和Shard 2 中的交易輸入都合法，那么用戶將向Shard 3 提交確認(rèn)信息。Shard 3 在接收到交易后，驗(yàn)證所有交易的合法性，通過驗(yàn)證后將交易打包進(jìn)當(dāng)前區(qū)塊。另一種情況是交易不合法后的回滾。如果在“鎖定”階段發(fā)現(xiàn)某個分片中的交易不合法，那么客戶端將創(chuàng)建一個“取消交易”消息，并廣播給所有參與該交易的分片，所有輸入分片中的領(lǐng)導(dǎo)者在接收到該消息后，將原交易的輸入狀態(tài)解鎖到可用狀態(tài)，實(shí)現(xiàn)跨分片交易的回滾。

（4）分片中節(jié)點(diǎn)的重配置。為了提高系統(tǒng)的穩(wěn)定性，分片中節(jié)點(diǎn)的更換不能太頻繁，具體可通過設(shè)置合理的PoW 難度值，使得每次重新配置時，更換掉的節(jié)點(diǎn)數(shù)不超過總節(jié)點(diǎn)數(shù)的1/3。

圖16 OmniLedger共識算法總體架構(gòu)Fig.16 Overall architecture of OmniLedger consensus algorithm

OmniLedger 采用了在出塊速度和安全性之間進(jìn)行平衡的“先信任后驗(yàn)證”（trust-but-verify）分層處理機(jī)制，分片共識可采用較少的節(jié)點(diǎn)，以加快分片共識以及區(qū)塊確認(rèn)速度，分片形成的區(qū)塊再被更多的節(jié)點(diǎn)進(jìn)行再次驗(yàn)證。另外，OmniLedger 還采用了區(qū)塊鏡像（snapshot）和區(qū)塊并行處理技術(shù)，以減小對內(nèi)存資源的占用，并提高共識效率。OmniLedger 在25 個分片的情況下，交易量可以達(dá)到13 000 TPS。

2019 年，Wang 等人提出了Monoxide 算法，該算法將分片技術(shù)和傳統(tǒng)PoW 共識有機(jī)結(jié)合，并借助提出的“Chu-ko-nu mining”算法，實(shí)現(xiàn)了每個礦工可以同時在不同的分片進(jìn)行探礦，在解決了因分片造成的算法分散這一缺陷的同時，還提高了系統(tǒng)抗攻擊能力和出塊速度。

Algorand是由Gilad 等人提出的PoS+BFT 單一分片共識算法中具有代表性的混合算法。Algorand 算法的共識過程主要分為委員會成員選舉和形成共識兩個階段：委員會成員選舉階段利用基于VRF 協(xié)議的PoS 共識選舉出委員會領(lǐng)導(dǎo)者和成員（驗(yàn)證者），其中領(lǐng)導(dǎo)者負(fù)責(zé)創(chuàng)建區(qū)塊，而驗(yàn)證者負(fù)責(zé)對創(chuàng)建的區(qū)塊進(jìn)行共識；共識階段通過運(yùn)行稱為“BA★”的新的BFT 協(xié)議對區(qū)塊達(dá)成共識。BA★是Algorand 算法的核心。

（1）選擇隨機(jī)數(shù)。在VRF 協(xié)議的每一輪，節(jié)點(diǎn)首先獲取上個區(qū)塊的信息B=(-1,PAY,(Q),(B))，然 后通過計(jì)算Q=((Q),-1) 得到本輪的隨機(jī)數(shù)。

（2）選擇委員會領(lǐng)導(dǎo)者（出塊節(jié)點(diǎn)）和成員（驗(yàn)證者節(jié)點(diǎn)）。每個節(jié)點(diǎn)運(yùn)行VRF 函數(shù)，根據(jù)函數(shù)值來判斷自己的身份：如果滿足(SIG(,1,Q))≤，則該節(jié)點(diǎn)被選舉為本輪的領(lǐng)導(dǎo)者；如果滿足(SIG(,1,Q))≤′，則該節(jié)點(diǎn)被選舉為本輪委員會的成員。其中，和′表示概率。

Algorand 在由1 000 臺虛擬機(jī)組成的實(shí)驗(yàn)環(huán)境中模擬了多達(dá)500 000 個用戶，結(jié)果表明交易在不到1 min 的時間內(nèi)得到了確認(rèn)，實(shí)現(xiàn)了125 倍于比特幣的吞吐量。

2017 年，被稱為“中國以太坊”的NEO（小蟻）區(qū)塊鏈中采用了授權(quán)拜占庭容錯（delegated Byzantine fault tolerance，dBFT）算法。該算法是一種通過代理投票來實(shí)現(xiàn)大規(guī)模節(jié)點(diǎn)參與共識的BFT 算法。在NEO 中，管理代幣的持有者通過PoS 共識投票選出其所支持的記賬人，然后被選出的記賬人之間通過BFT 算法達(dá)成共識并生成區(qū)塊。在公有鏈中，NEO在dBFT 的支持下每15～20 s 可以生成一個區(qū)塊，交易吞吐量達(dá)到1 000 TPS。

區(qū)塊鏈混合共識算法充分吸收了原來單一共識算法的優(yōu)勢，并經(jīng)相互結(jié)合后克服了原來單一共識在出塊速度、吞吐量、安全性等方面存在的不足，使得區(qū)塊鏈能夠適應(yīng)更多的應(yīng)用場景。表6 給出了幾類典型混合共識算法在核心算法、分片類型、通信模型和應(yīng)用場景等方面的主要性能比較。

4 總結(jié)與展望

區(qū)塊鏈技術(shù)在與實(shí)體產(chǎn)業(yè)的融合過程中正在加速數(shù)字經(jīng)濟(jì)的發(fā)展。作為區(qū)塊鏈核心技術(shù)的共識算法，能夠在節(jié)點(diǎn)高度分散且不存在彼此間信任機(jī)制的網(wǎng)絡(luò)環(huán)境中就某一具體事務(wù)達(dá)成結(jié)果的一致性，且對過程和結(jié)果都不存在分歧。嚴(yán)格地講，除能源消耗外，共識算法不存在絕對的誰最適合誰的問題。通常情況下，共識算法的選擇是在針對具體應(yīng)用場景的前提下，在效率、安全性、穩(wěn)定性之間的折衷和平衡。

表6 典型PoW/PoS+BFT/PBFT 共識算法的性能比較Table 6 Performance comparison of typical PoW/PoS+BFT/PBFT consensus algorithms

本文重點(diǎn)從區(qū)塊鏈產(chǎn)生之前的經(jīng)典分布式共識和區(qū)塊鏈共識兩方面著手，就單一共識算法和混合共識算法進(jìn)行了系統(tǒng)性的分析和梳理，并選擇了部分典型算法進(jìn)行了較為系統(tǒng)的介紹?；谀壳暗难芯楷F(xiàn)狀，針對區(qū)塊鏈共識算法的發(fā)展，重點(diǎn)需要研究和解決性能與可擴(kuò)展性、激勵機(jī)制、安全與隱私、并行處理等方面的問題。

首先，區(qū)塊鏈的性能和可擴(kuò)展性是影響當(dāng)前區(qū)塊鏈共識算法的關(guān)鍵因素，分片技術(shù)通過將節(jié)點(diǎn)分組后分割處理交易，多個分片并行交易，以最大限度地提高性能，同時大大減少每個節(jié)點(diǎn)的通信、計(jì)算和存儲開銷，從而使系統(tǒng)能夠擴(kuò)展到大型網(wǎng)絡(luò)環(huán)境。然而，現(xiàn)有的單一共識和混合共識算法大多沒有更好地發(fā)揮分片的更多優(yōu)勢，吞吐量和延遲仍然是主要的瓶頸。同時這些協(xié)議實(shí)現(xiàn)的安全保障很弱且故障率較高，許多性能的實(shí)現(xiàn)還依賴于大量的假設(shè)（如可信、同步網(wǎng)絡(luò)環(huán)境等），限制了對主流系統(tǒng)的適用性。下一步還需要重點(diǎn)在算法優(yōu)化和工程應(yīng)用中進(jìn)一步研究。其中，如何將經(jīng)典的傳統(tǒng)一致性算法更好地“移植”到區(qū)塊鏈應(yīng)用環(huán)境，在發(fā)揮傳統(tǒng)算法已形成的特定性能優(yōu)勢的同時，解決某些區(qū)塊鏈應(yīng)用場景下對共識算法的具體要求，還需要在算法實(shí)現(xiàn)的理論研究和工程實(shí)踐上進(jìn)行深入探討。

其次，激勵機(jī)制是區(qū)塊鏈共識算法的重要組成要素，是決定具體算法能否滿足特定應(yīng)用場景要求的關(guān)鍵，比特幣取得今天的成功有力地證明了這一點(diǎn)。受比特幣的影響，早期的激勵機(jī)制主要來源于經(jīng)濟(jì)刺激，礦工積極、忠誠、高效地參與挖礦主要是為了獲得經(jīng)濟(jì)利益。然而隨著區(qū)塊鏈應(yīng)用場景的多元化，在單一經(jīng)濟(jì)激勵機(jī)制發(fā)揮的功能逐漸被弱化的情況下，如何實(shí)現(xiàn)共識算法的安全性、一致性和活性，還需要針對具體應(yīng)用場景對算法進(jìn)行優(yōu)化，在共識與激勵二元耦合過程中尋得平衡。試想一下，如果一個區(qū)塊鏈系統(tǒng)的共識算法中不再存在激勵機(jī)制，那么區(qū)塊鏈的安全性、去中心化、開放自治等功能將如何實(shí)現(xiàn)。沒有這些功能特征的系統(tǒng)已不再是一個區(qū)塊鏈系統(tǒng)。但如果過于強(qiáng)調(diào)經(jīng)濟(jì)激勵機(jī)制在共識算法中的作用，則勢必在安全性、效率、過擴(kuò)展性等方面帶來新的挑戰(zhàn)。因此，從某種程度上講，區(qū)塊鏈共識提供的是一種解決問題的思路，而不是一個固定的范式。

還有，在區(qū)塊鏈共識算法中，隱私與安全相互依存，但各有側(cè)重。安全更關(guān)注于系統(tǒng)的抗攻擊能力，而隱私則聚焦于對個人及相關(guān)范圍信息的管控。共識過程是一個多節(jié)點(diǎn)通過頻繁交換信息以達(dá)成最終一致性的過程，期間不但會受到傳統(tǒng)網(wǎng)絡(luò)攻擊（如DDoS 攻擊、女巫攻擊等）的威脅，攻擊者更會利用具體算法存在的缺陷進(jìn)行有針對性的攻擊破壞（如針對特定共識算法的雙花攻擊、自私挖礦攻擊、賄賂攻擊等）。因此，針對區(qū)塊鏈共識算法安全性的研究需要在綜合各類復(fù)雜網(wǎng)絡(luò)環(huán)境的前提下，再就具體的算法實(shí)現(xiàn)進(jìn)行研究。同時，還要綜合安全、去中心化和可擴(kuò)展性之間的平衡；區(qū)塊鏈共識過程中涉及到的隱私主要包括節(jié)點(diǎn)交易隱私、賬戶地址隱私、用戶身份隱私和智能合約隱私等方面，攻擊者基于算法設(shè)計(jì)和實(shí)現(xiàn)過程中存在的缺陷，分析賬本內(nèi)容和合約執(zhí)行代碼，從中獲得與用戶身份相關(guān)的信息，導(dǎo)致隱私泄露。針對共識環(huán)節(jié)的隱私保護(hù)，目前的研究主要集中在信息混淆、信息加密、通道隔離和訪問與授權(quán)管理等領(lǐng)域。

最后，隨著區(qū)塊鏈應(yīng)用領(lǐng)域的不斷拓展，傳統(tǒng)的單一鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)因其效率低下而無法適應(yīng)大規(guī)模高吞吐量應(yīng)用場景的需求，以DAG 為代表的“圖型”數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)通過并行處理來替代鏈?zhǔn)教幚碛行浹a(bǔ)了區(qū)塊鏈的原生缺陷。這些新型區(qū)塊鏈數(shù)據(jù)結(jié)構(gòu)帶來的共識算法研究成為當(dāng)前和未來研究的趨勢之一。例如，如何將DAG 結(jié)構(gòu)和分區(qū)技術(shù)進(jìn)行結(jié)合，以此來改變區(qū)塊鏈系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)，進(jìn)而可彌補(bǔ)分布式賬本在可擴(kuò)展性、吞吐率、交易確認(rèn)時間等方面的原生缺陷；再如，隨著區(qū)塊鏈技術(shù)在物聯(lián)網(wǎng)中應(yīng)用的不斷深入，區(qū)塊鏈為解決物聯(lián)網(wǎng)數(shù)據(jù)存儲和共享的安全性提供了技術(shù)保障，但海量的物聯(lián)網(wǎng)數(shù)據(jù)對區(qū)塊鏈共識性能提出了挑戰(zhàn)。為此，如何將區(qū)塊鏈中的分片機(jī)制與物聯(lián)網(wǎng)環(huán)境中的云計(jì)算/邊緣計(jì)算等架構(gòu)有機(jī)結(jié)合，從而提高數(shù)據(jù)處理的效率，將是一個迫切需要解決的熱點(diǎn)問題等。