區塊鏈共識算法及應用研究

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

1.江蘇警官學院 計算機信息與網絡安全系，南京 210031

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

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

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

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

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

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

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

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

1 共識算法概述

在計算機學科領域，算法是為了實現某一目的而設計的一系列解決具體問題的清晰指令，協議是為了使通信雙方或多方達到某一目的而規定的一組規則。協議用于解決具體問題，而算法是對協議的具體實現，體系結構和協議奠定了網絡的主體架構。為此，本文在討論共識算法時將其置于具體的網絡環境和應用場景中。

1.1 區塊鏈共識模型

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

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

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

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

（3）交易廣播。將簽名后的交易數據通過調用本地應用程序接口（application programming interface，API）或以P2P 節點方式廣播到網絡中。

（4）挖礦。挖礦即對交易數據的打包和確認。首先根據區塊的數據結構，將交易打包進區塊，再采用Merkle Tree 算法生成區塊體中所有交易的Merkle Roo（t哈希值），然后根據區塊頭部的元數據，采用相應的共識算法（如PoW、PoS等）獲取新區塊的記賬權。

（5）全網節點寫入。礦工將生成的新區塊廣播到區塊鏈網絡中，任意一個節點在接收到新區塊后，對其進行驗證，驗證通過后將該區塊鏈接到本地區塊鏈上。同時，不同的區塊鏈系統還將采用相應的算法防止分叉的產生，維護主鏈的唯一性和穩定性。

圖1 區塊鏈共識基礎模型Fig.1 Blockchain consensus base model

1.2 共識算法中的基本定義

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

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

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

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

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

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

（共識（consensus））就某種狀態或數據達成一致性的過程。

一致性一般是指分布式系統中數據及其副本對外呈現的狀態，描述的是多個節點對數據狀態的維護能力，而共識描述的是分布式系統中多個節點間彼此對某個狀態達成一致結果的過程。一致性描述的是狀態的結果，而共識則是一種手段，達成某種共識并不意味著取得了完全一致。

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

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

（宕機缺陷（fail-stop fault））因系統進程停止運行導致的缺陷。

（宕機恢復故障（fail-recovery failure））因系統進程停止運行導致的故障，該故障在重啟進程后恢復。

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

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

通信模型在很大程度上決定著共識算法的設計與實現。在同步網絡中，在一個消息到達節點之前，已經確認前一條消息成功接收；在異步網絡中，由于消息的傳輸可能會產生延時、亂序等現象，無法保障消息會按照發送時的順序有序到達；而在部分同步網絡中，消息能夠在系統限定的時間內到達所有非拜占庭節點，但前后順序無法得到保障。

2 經典分布式共識算法

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

2.1 兩軍問題

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

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

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

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

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

兩軍問題是研究分布式系統一致性的一個重要理論，對現代計算機網絡技術的發展產生了重要影響，對區塊鏈共識算法的研究具有重要意義。例如，在TCP/IP 體系中，TCP 協議為了解決兩個節點之間通信的可靠性問題，就采用了基于“三次握手”建立連接和“四次握手”斷開連接的機制，為解決兩軍問題不存在理論提供了一個簡易可行的應用范式。

2.2 拜占庭將軍問題

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

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

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

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

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

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

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

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

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

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

所有非拜占庭服務器（沒有出現故障的服務器）使用完全相同的輸入信息，產生完全一致的輸出結果。

當輸入的信息正確時，所有非拜占庭服務器都要接受該信息，并計算相應的結果。

與此同時，對于一個已投入運行的拜占庭容錯系統來說，所有拜占庭服務器（出現缺陷或故障的服務器）需要滿足安全性和活性兩個指標：

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

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

根據節點（服務器或客戶端）的容錯類型，可以將分布式系統的共識機制分為拜占庭容錯和非拜占庭容錯兩類，其中非拜占庭容錯（如Paxos、viewstamped replication、Raft等算法）主要用于聯盟鏈和私有鏈，而公有鏈主要使用拜占庭容錯共識算法。

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

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

因為本小節研究的主要內容是分布式系統的共識問題，所以在這里更關注PBFT 的一致性協議。一致性協議約定來自客戶端（client）的每一個請求按照確定的順序在每個服務器上執行，每個服務器在相同的配置信息下工作（該配置信息稱為“視圖”），服務器分為主節點（primary）和副本節點（replica）兩類，其中主節點僅有一個，它負責對客戶端的請求進行排序，副本節點按照主節點提供的順序執行請求。

一致性協議至少包括請求（propose）、預準備（pre-prepare）、準備（prepare）、確認（commit）和回復（reply）5 個階段。圖4 是一個簡化的PBFT 協議運行示意圖，其中副本節點replica 3 為故障節點（標×），箭頭表示消息的發送過程。整個協議的執行過程如下：

（1）請求（propose）?？蛻舳讼蛑鞴濣c發送請求，該請求消息=[op,t,-id,-sig]，其中op 代表執行的操作，為時間戳，-id 為客戶端標識，-sig 為客戶端數字簽名。簽名的目的是對客戶端進行認證和授權，以適應聯盟鏈或私有鏈對接入節點的管理要求。

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

圖4 PBFT 協議運行示意圖Fig.4 PBFT protocol communication pattern

（3）準備（prepare）。所有副本節點在接收到preprepare 消息后，構成一個準備消息prepare=[p,vn,sn,(),-id,-sig]，然后將其發送給其他服務器節點，其中p 表示prepare 消息，-id 為副本節點的標識，-sig為副本節點的數字簽名。

（4）確認（commit）。服務器節點在收到2+1 個prepare 消息（系統中總共有3+1 個服務器節點，其中故障節點有個）后，對視圖內的請求和執行順序進行驗證，驗證通過后執行客戶端請求，并構成一個確認消息commit=[,vn,sn,(),-id,-sig]后發送給其他服務器節點，其中表示commit消息。

（5）回復（reply）。當服務器節點收到2+1 個commit 消息，構成一個回復消息reply=[,vn,t,-sig]后發送給客戶端，其中表示回復消息?？蛻舳说却蟹掌鞴濣c的回復消息，如果接收到2+1 個相同的回復，則該回復即為運算結果。

在異步系統中，PBFT 算法能夠在拜占庭節點數少于1/3 的情況下達成最終的一致性。同時，在PBFT 中，消息發送者的身份都以數字簽名方式經過了認證，確保了節點的可信性和消息來源的可追溯能力。另外，PBFT 提供了超時機制，從而保證了安全性和活性。

2.3 FLP 不可能性定理

1985 年，Fischer、Lynch 和Paterson 三位科學家在文獻[31]中提出：在一個多進程異步系統中，只要存在一個不可靠的進程，就不存在在有限時間內使所有進行達成一致的協議。按照三位科學家姓氏的首字母，該定理被稱為FLP 不可能性定理。

任何一個分布式算法都需要對系統場景進行假設或設置條件，從而形成系統模型，FLP 不可能性定理建立在以下4個條件（條件8至條件11）的基礎上：

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

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

失敗-停止模型。進程失敗后不再處理任何消息。

失敗進程數限制。系統中最多只能有一個進程失敗。

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

FLP 不可能性定理是眾多共識算法中一個非常經典的基礎性定理。對于FLP 不可能性定理的理解和應用需要建立在相應假設及限制條件的系統模型上，在FLP 不可能性定理假設條件中，因為沒有對進程接收消息、處理消息和回復消息的時間進行限制，也就是說進程處理速度不確定，消息的延遲也可能很大，因此在判斷一個進程問題時不知道是因宕機引起的進程故障還是因消息的處理時間太長而造成的延時所致。同時，FLP 不可能性定理中所指的故障并不是拜占庭故障，而僅僅是導致進程停止運行的宕機故障。

在異步系統中，當一個進程出現故障或響應時間延遲時，不存在一個分布式算法能夠讓所有的非故障進程達成一致性共識。為規避FLP 不可能性定理，只能通過對某些條件進行必要的取舍或調整來優化問題模型。例如，因為存在FLP 不可能性定理的限制，許多區塊鏈項目的共識算法一般都認為大部分節點是誠實的，并且滿足一定的同步性，其中PoW算法認為至少51%的節點是誠實的，并且有一定的同步性，PoS 和PBFT 算法也認為2/3 及以上的節點是誠實的。

2.4 CAP 定理

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

CAP 定理是分布式系統設計中最基礎和最關鍵的理論之一。CAP 定理提出：在一個分布式數據存儲系統中，最多只能同時滿足一致性、可用性和分區容錯性3個屬性中的2個屬性（每個屬性即一個條件）。

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

（2）可用性：每個非故障節點在收到請求消息后必須給予回復。

（3）分區容錯性：能夠容忍網絡丟失從一個節點發送給另一節點的任意數量的消息。

CAP 定理在應用于分布系統時，需要根據不同的場景對3 個屬性進行相應的取舍，如圖5 所示。在網絡環境中，由于分區容錯是一個常態，在設計一個具體的分布式系統時需要在一致性與可用性之間進行權衡。例如，Amazon DynamoDB 為了確保可用性而只能舍棄一致性，而谷歌文件系統（Google file system，GFS）在實現一致性的前提下只有舍棄可用性。

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

雖然CAP 定理和FLP 不可能性定理都是研究分布式系統中的一些無解問題，但兩個定理成立的條件不同：FLP 不可能性定理假設的異步通信鏈路是可靠的，只是消息存在延遲，但不會丟失，而CAP 定理中的網絡分區容錯性會導致消息丟失；由于FLP 不可能性定理中的故障節點會從系統中完全隔離，不會對任意請求進行響應，但CAP 定理中的可用性要求系統能夠響應請示。但不管是FLP 不可能性定理還是CAP 定理，因為分布式系統都會對一致性、可用性和可終止性有要求，所以在具體的共識算法設計時都需要考慮兩個定理的條件限制，通過合理取舍CAP 定理的相關屬性來規避FLP 不可能性。

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

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

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

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

2.5 Paxos算法

Paxos 算法是Lamport 早在1990 年提出的一種在分布式系統中基于消息傳遞的一致性算法，為后續各類典型一致性算法研究提供了理論基礎和參照。不過，由于Paxos 算法的描述過于晦澀難懂，在工程應用中很難實現。

概括地講，Paxos 算法具體解決的是在一個隨時可能出現節點故障或網絡異常（如分組延時、丟失、重傳、亂序等）的分布式系統中，在某一集群內快速實現數據或網絡狀態的一致性。Paxos 算法建立在以下3個假設條件（條件12至條件14）成立的基礎上：

部分同步網絡環境。

能夠容忍一半以下數量的宕機恢復（非拜占庭故障）節點，即少數服從多數的“過半”規則。

不存在拜占庭將軍問題，即信道是安全可靠的，且節點發送出去的信息可能會出現丟失或重復，但不會被篡改。

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

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

圖6 Paxos算法運行過程描述Fig.6 Description of running process of Paxos algorithm

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

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

在以上兩個階段中，每個階段對應的請求和應答（響應）內容各不相同。

作為分布式共識設計時參考的一個重要算法，Paxos 算法已經應用到Google Chubby、Microsoft Autopilot、微信PaxoStore等重要的分布式服務中。另外，在Paxos 算法的基礎上，相繼設計出了應用于不同場景且易于理解和實現的共識算法，如Raft、Zookeeper、etcd等。

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

表1 經典共識算法Table 1 Classical consensus algorithm

3 區塊鏈共識算法

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

3.1 PoW 共識算法

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

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

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

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

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

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

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

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

如圖7 所示的是比特幣系統中PoW 共識算法的執行流程，其主要實現過程如下：

（1）根據區塊數據結構，將鑄幣（coinbase）交易和節點緩存中已簽名的交易打包進區塊形成完整的區塊體，通過默克爾樹（Merkle tree）算法生成默克爾根（Merkle-root）。

（2）判斷距上次難度值調整時是否已經產生了2 016 個區塊，如果是，馬上進行難度值的調整，以獲得新的難度位（Bits）；否則使用原來的難度值繼續進行挖礦。

圖7 比特幣系統中PoW 共識算法的實現流程Fig.7 Realization process of Po Wconsensus algorithm in bitcoin system

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

（4）礦工將新挖出的區塊向全網廣播，希望獲得新區塊的記賬權從而獲得比特幣發行獎勵。節點對接收到的新區塊進行驗證，如果驗證無誤就將該區塊添加到主鏈上，并以此區塊為基礎繼續下一個區塊的挖礦工作。

通過以上過程，交易信息將被寫入各記賬節點的區塊中，形成一個分布式的一致性賬本。

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

（1）比特幣PoW 共識算法

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

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

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

（2）以太坊Ethash 共識算法

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

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

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

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

圖8 以太坊Ethash 共識算法的實現流程Fig.8 Realization process of Ethash consensus algorithm in Ethereum system

②生成緩存（cache）。根據seed計算出一個16 MB的用于輔助校驗區塊和生成數據集（dataset）的偽隨機cache，由輕客戶端存儲。

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

④挖礦。礦工根據區塊頭遞歸長度（recursive length prefix，RLP）、從dataset 中隨機取出的數據和Nonce 進行數據混合運算得到混合摘要值。當對混合摘要的哈希計算結果符合區塊難度要求時挖礦成功；否則，繼續Nonce++運算，直到符合條件。

⑤驗證。節點收到新區塊時，根據存儲在本地的cache 重新生成dataset 中所需要的數據，再結合區塊頭中的信息來驗證難度值。

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

圖9 Ethash 算法中區塊、種子、緩存和數據集之間的關系Fig.9 Relationship among block,seed,cache,and dataset in Ethash algorithm

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

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

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

（3）Bitcoin-NG

限制比特幣系統效率的主要因素有區塊大?。總€區塊約1 MB）和出塊速度（約10 min）。如果單純地增加區塊大小也可以增加單個區塊容納的交易數量，進而提高系統的效率，但是隨著區塊大小的增大，網絡的延時也會隨之增大，效率反而會降低；如果單純縮短出塊速度，可以縮短交易的確認時間，但將會導致頻繁發生分叉，系統的安全性大大降低。為了解決比特幣的效率問題，以提高區塊鏈的吞吐量，Eyal等人提出了Bitcoin-NG擴容算法。

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

如圖10所示，與比特幣的區塊頭部相比，Bitcoin-NG 的主塊多了一個用于存放當前領導者公鑰（PK）的字段，因為交易被打包進微塊后，為了實現對微塊所屬領導者的驗證，需要用領導者自己的私鑰對生成的微塊進行簽名（sig）；為了激勵礦工按照約定規則挖礦并打包交易，在Bitcoin-NG 算法中，挖到主塊的礦工獲得類似于比特幣中的挖礦獎勵，而對于當前窗口期內生成微塊的所有交易費中，40%歸當前領導者所有，60%歸下一個領導者所有，這樣做的目的主要是防止貪心礦工進行自私挖礦（selfish mining）。

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

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

Eyal等人在約1 000 個節點組成的比特幣系統上對Bitcoin-NG 算法進行了模擬實驗，對其良好的可擴展性、有效提升吞吐量和明顯降低延遲等特性進行了有效驗證，成為區塊鏈擴容方案中具有代表性的共識算法。

（4）其他典型PoW 共識改進算法

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

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

表2 列出了針對PoW 共識算法及其主要改進算法的相關信息。

表2 PoW 及其改進算法Table 2 PoW and its improved algorithms

3.2 PoS 共識算法

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

PoW 共識算法是通過消耗現實生產生活中的價值（算力）來維護區塊鏈的價值體系，而PoS 共識算法則是在一套規則的支持下，利用已有的價值（權益）來達成共識從而不斷衍生出新的價值，進而在一個“自治系統”（不需要像PoW 那樣從外界輸入算力）中維護區塊鏈的價值體系。

2011 年，Quantum Mechanic 首次提出了PoS 共識算法，算法中規定了用節點擁有的比特幣數量來替代PoW 共識算法中基于算力求解哈希值的過程，即礦工擁有的比特幣數量越多挖到礦的可能性就越大。2012 年，King 等人設計了點點幣（PPCoin 或PeerCoin）并在系統中首次實現了PoS 共識算法。

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

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

（PoS 共識算法）給定一個全網統一的難度值，以及新打包進區塊的元數據，尋找滿足條件的記數器，使得：

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

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

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

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

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

需要說明的是：PoS 共識算法最早運行在PPCoin系統，但PPCoin 系統中使用的是PoS+PoW 混合共識算法。

（1）DPoS 共識算法

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

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

目前，使用DPoS 共識算法的區塊鏈應用系統主要 有Bitshares（比特股）、Steem、EOS，其中Steem 和EOS 中委托人的數量都為21。

（2）Ouroboros共識算法

為了能夠在運行PoS 共識算法的區塊鏈系統中實現類似PoW 共識算法中的安全機制，Kiayias 等人提出了Ouroboros 共識算法。Ouroboros 共識算法因其在學術領域產生的影響力，很快成為學術界認可和產業界采用的可證明是安全和健壯的PoS 共識算法。目前，Cardano（ADA，艾達幣）就使用了Ouroboros共識算法。

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

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

②每個時隙最多只能產生一個區塊，如果當時隙到來時對應的節點離線或生成的區塊未得到大多數節點的確認，則該時隙不會生成有效區塊。

③由多個連續的時隙組成一個窗口（epoch），在一個窗口中，權益的計算是以該窗口開始時的歷史值為基準，期間權益的變化不會影響當前窗口中出塊者的選擇。

④每個窗口開始時，在礦工節點的計算機內存中會生成一個genesis block，該特殊區塊僅記錄本窗口中可能參與出塊的權益持有者的候選人信息以及隨機數種子，并不會最終上鏈。

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

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

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

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

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

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

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

（3）Ouroboros Praos共識算法

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

（4）Ouroboros Genesis共識算法

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

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

（5）Snow White共識算法

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

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

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

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

3.3 PoW+PoS 混合共識算法

PoW+PoS 共識算法結合了PoW 和PoS 的特點，節點在競爭記賬權的過程中按算法要求生成PoW 或PoS 區塊，有效解決了原來單一共識算法在安全風險、能源消耗、效率等方面存在的問題。

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

Reddcoin 是一種加密貨幣，其前期使用PoW 算法實現代幣的分發，而后期使用PoSV 以提高P2P 網絡的安全性。

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

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

（2）當某一礦工成功挖到一個空區塊頭后，將其立即向全網廣播。

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

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

（5）所有活躍節點在收到第個幸運股權持有者的廣播區塊后，對其進行驗證，如果驗證通過則確認該區塊并連接到主鏈，然后繼續下一個區塊的挖礦過程。否則，丟棄該區塊。

在以上過程中，要求所有的個幸運股權持有者都在線，其中任意一個不在線都會導致生成的區塊驗證失敗。PoA 算法會周期性地通過計算丟棄區塊的數量來調整值，當某一周期內丟棄區塊的數量增大時，則值會減??；否則，值會增大。PoA 算法中，打包進區塊的交易費由挖出該空區塊頭的礦工和個幸運股權持有者共享。

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

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

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

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

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

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

圖13 2-hop 區塊鏈結構Fig.13 2-hop blockchain structure

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

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

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

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

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

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

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

（2）重配置過程。系統設定一個具有一定難度的哈希函數求解問題，求得PoW 解的節點將其結果廣播給委員會成員；委員會成員對PoW 解進行驗證，驗證通過后將求得解的節點作為新的領導者；當新領導者產生后，所有節點將在“交易確認過程”階段已確認的交易哈希值等相關狀態消息發送給新領導者，當新領導者接收到2+1 個狀態消息后，將其組合成一個狀態證明（status certificate）消息，然后進行廣播。接收到狀態證明的節點確認已打包的交易信息，并進入由新委員會成員組成的新一輪一致性共識過程。

在Solida 混合共識算法中，通過PoW 共識算法實現新領導者的選舉，完成新委員會成員的重新配置；利用BFT 算法完成委員會內部成員之間的一致性共識，確保委員會內部有超過2/3 誠實成員的前提下便能夠取得一致性共識。

另外，在由Pass 等人提出的Hybrid consensus混合共識算法中，通過結合低效的PoW 共識算法和快速的BFT 授權共識算法，實現在非授權環境下達成快速共識。

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

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

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

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

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

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

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

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

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

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

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

另一個基于PoW 和PBFT 混合共識的典型算法是ByzCoin。該算法采用PoW 選舉分片節點（委員會成員），分片內部采用改進的PBFT 算法完成共識。當區塊大小為32 MB、分片中的節點數為144時，算法每秒的交易量可以達到974。

2016年，Luu等人提出了ELASTICO混合算法，最先將多分片技術應用到區塊鏈中。ELASTICO 首先通過PoW 共識競爭選舉網絡中的記賬節點，然后按照預先確定的規則，將選舉得到的記賬節點分配到不同的分片委員會中。每個分片委員會內部執行PBFT 算法打包生成交易集合。該交易集合經簽名后被提交給共識委員會。共識委員會在驗證簽名后，最終將所有的交易集合打包成區塊并記錄在區塊鏈上。

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

（1）節點注冊。在當前窗口期內，節點參與PoW共識，將計算得到的難度值和節點身份信息進行廣播。領導者在當前分片內運行PBFT 共識算法，將收集到的所有合法節點信息注冊到身份鏈。

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

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

（4）分片中節點的重配置。為了提高系統的穩定性，分片中節點的更換不能太頻繁，具體可通過設置合理的PoW 難度值，使得每次重新配置時，更換掉的節點數不超過總節點數的1/3。

圖16 OmniLedger共識算法總體架構Fig.16 Overall architecture of OmniLedger consensus algorithm

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

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

Algorand是由Gilad 等人提出的PoS+BFT 單一分片共識算法中具有代表性的混合算法。Algorand 算法的共識過程主要分為委員會成員選舉和形成共識兩個階段：委員會成員選舉階段利用基于VRF 協議的PoS 共識選舉出委員會領導者和成員（驗證者），其中領導者負責創建區塊，而驗證者負責對創建的區塊進行共識；共識階段通過運行稱為“BA★”的新的BFT 協議對區塊達成共識。BA★是Algorand 算法的核心。

（1）選擇隨機數。在VRF 協議的每一輪，節點首先獲取上個區塊的信息B=(-1,PAY,(Q),(B))，然 后通過計算Q=((Q),-1) 得到本輪的隨機數。

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

Algorand 在由1 000 臺虛擬機組成的實驗環境中模擬了多達500 000 個用戶，結果表明交易在不到1 min 的時間內得到了確認，實現了125 倍于比特幣的吞吐量。

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

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

4 總結與展望

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

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

本文重點從區塊鏈產生之前的經典分布式共識和區塊鏈共識兩方面著手，就單一共識算法和混合共識算法進行了系統性的分析和梳理，并選擇了部分典型算法進行了較為系統的介紹。基于目前的研究現狀，針對區塊鏈共識算法的發展，重點需要研究和解決性能與可擴展性、激勵機制、安全與隱私、并行處理等方面的問題。

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

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

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

最后，隨著區塊鏈應用領域的不斷拓展，傳統的單一鏈式數據結構因其效率低下而無法適應大規模高吞吐量應用場景的需求，以DAG 為代表的“圖型”數據結構和存儲結構通過并行處理來替代鏈式處理有效彌補了區塊鏈的原生缺陷。這些新型區塊鏈數據結構帶來的共識算法研究成為當前和未來研究的趨勢之一。例如，如何將DAG 結構和分區技術進行結合，以此來改變區塊鏈系統的數據結構和存儲結構，進而可彌補分布式賬本在可擴展性、吞吐率、交易確認時間等方面的原生缺陷；再如，隨著區塊鏈技術在物聯網中應用的不斷深入，區塊鏈為解決物聯網數據存儲和共享的安全性提供了技術保障，但海量的物聯網數據對區塊鏈共識性能提出了挑戰。為此，如何將區塊鏈中的分片機制與物聯網環境中的云計算/邊緣計算等架構有機結合，從而提高數據處理的效率，將是一個迫切需要解決的熱點問題等。