作者：資訊 / 來源：PlatON

PlatON 的 Giskard 共識協議由概率性權益證明 PPoS( PlatON proof of stake ) 和 Giskard 拜占庭容錯協議-Giskard BFT( Giskard Byzantine Fault Tolerance ) 組成。PPoS 使用質押、委托、隨機選取的形式選出參與共識的驗證節點，Giskard BFT 使用類 BFT 算法實現區塊的生產和驗證。

本文我們將簡單介紹 PPoS 共識和 BFT 理論，并分析 PBFT 算法特性及 PBFT 存在的問題，其后重點分析 Giskard BFT 借鑒 PBFT、Tendermint、Hotstuff 等共識協議的演進之路。

區塊鏈技術本質脫離不開傳統分布式系統。分布式一致性算法是傳統分布式系統的一大難題，經過長期的研究和應用，誕生了如 paxos、raft、zab 等成熟安全的算法。

相比于傳統的分布式系統，公共區塊鏈中沒有中心化的假設，任何節點都可以加入并自由訪問所有的數據，因此公鏈中不可避免會存在惡意節點。所以，區塊鏈系統中的共識機制不僅需要支持 CFT( Crash fault tolerance ) 還需要支持 BFT(Byzantine Fault Tolerance) 。BFT 是一個已經被研究得比較透徹的理論，PBFT 是其中最為著名的實現算法，目前廣泛應用于各大區塊鏈系統中。

PlatON 的 Giskard 共識協議由概率性權益證明 PPoS(PlatON proof of stake) 和 Giskard 拜占庭容錯協議-Giskard BFT(Giskard Byzantine Fault Tolerance) 組成。PPoS 使用質押、委托、隨機選取的形式選出參與共識的驗證節點，Giskard BFT 使用類 BFT 算法實現區塊的生產和驗證。

PPOS——驗證節點選取

在介紹 PPoS 之前，我們先科普一下 PoS，目前 PoS 共識方案可以分為四類：

PoS 共識概述

** Chain-Based**

這是早期的一代 PoS。根據持有 token 的數量偽隨機地選擇驗證人進行區塊生產。其中還有 PoS+PoW 方案，一般是 PoW 出塊，通過 PoS 選擇驗證人進行驗證，以太坊的 Casper1.0 也是一種混合 PoS/PoW 的方案，作為其從 PoW 轉換到 PoS 的中間方案。

** DPoS (Delegated Proof of Stake)**

委托權益證明。每個 token 持有人可以把權利委托給部分代表，由代表參與區塊的生產和驗證。

** VRF (Verifiable Random Function)**

可驗證隨機函數用于驗證節點的隨機選取。目前，Dfinity、Cardano 和 Algorand 等采用了這種方案。

** BFT (Byzantine Fault Tolerance)**

拜占庭容錯。選出驗證節點后通過運行 BFT 協議經過多輪投票確認區塊完成共識。目前 Tendermint、Stellar、Ontology、Zilliqa、NEO 等都是采用這類共識算法。

PlatON 的共識方案 PPoS，也就是我們常說的概率性權益證明，它本質是一種 PoS 共識方案，根據節點的權益繪制成二項分布累積分布曲線，并使用 VRF 隨機選取驗證節點。

PPoS 解決的關鍵核心點在于驗證人的選取不僅與節點權益的大小有關，還兼具隨機性，也就是說選出的驗證節點不一定是權益最高的節點，權益較低的節點也有一定的選中概率。隨機性算法可以保證選取的結果不可預測、不可操控且公平可靠。PPoS 本質上是 PoS+VRF 方案的結合。

簡單總結就是： PPoS 提供了一種盡可能公平、隨機地從眾多參與節點中選取出若干驗證節點的方案。

針對驗證人選取的隨機性問題，我們也做了專題研究，請參看《PoS 共識中的驗證人選取》一文：

【技術云圖】PoS 共識中驗證人選舉的隨機方案（上）

【技術云圖】PoS 共識中驗證人選舉的隨機方案（下）

BFT——區塊共識

驗證節點被選舉出來之后，運行共識協議進行區塊生產和驗證，整個過程需要節點之間相互協作，對區塊進行相互確認，得出一致結論，達成區塊共識。

上文中提到，區塊鏈中的共識算法不僅需要考慮 Crash 節點，還需要考慮 Byzantine 節點。什么是拜占庭節點？我們從一個故事說起。

拜占庭將軍問題

拜占庭羅馬帝國國土遼闊，為了達到防御目的，每塊封地都駐扎一支由將軍統領的軍隊，每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳遞消息。

在戰爭的時候，拜占庭軍隊內所有將軍必須達成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。但是，在軍隊內有可能存有叛徒和敵軍的間諜，左右將軍們的決定影響將軍們達成一致共識。在已知有將軍是叛徒的情況下，其余忠誠的將軍如何達成一致協議的問題，這就是拜占庭將軍問題。

拜占庭將軍問題所描述的是好的將軍不知道其他將軍是好的，還是壞的，但所有好的將軍的目的是：行動一致，共同進退。所以，他們需要在策略上達成一致。

看到這里，相信大家對拜占庭節點也有了初步的理解。簡單地說，在區塊鏈系統中存在以下兩類錯誤：

• 第一類錯誤是節點崩潰、網絡故障、丟包等，這種錯誤類型的節點是沒有惡意的，屬于非拜占庭錯誤。

• 第二類錯誤是節點可能是惡意的，不遵守協議規則。例如驗證者節點可以延遲或拒絕網絡中的消息、領導者可以提出無效塊或者節點可以向不同的對等體發送不同的消息。在最壞的情況下，惡意節點可能會相互協作。這些被統稱為拜占庭錯誤。

要讓這個問題有解，還需要先引入一個概念—— 分布式網絡模型 ，按照分布式系統理論，分布式系統的網絡模型分為三類：

• 同步網絡模型 ：節點所發出的消息，在一個確定的時間內，肯定會到達目標節點

• 異步網絡模型 ：節點所發出的消息，不能確定一定會到達目標節點

• 部分同步網絡模型 ：節點發出的消息，雖然會有延遲，但是最終會到達目標節點

拜占庭將軍問題的解決，有一個十分重要的前提，那就是通信信道必須是可靠的。如果信道不能保證可靠，那么拜占庭問題無解。這也就是 FLP 不可能原理，即在異步網絡模型假定下，共識算法不可能同時滿足安全性（safety）和活躍性（liveness），也就是說，在一個不可靠的通信鏈路上試圖通過通信以達成一致是基本不可能或者十分困難的。至于什么是安全性和活躍性，我們后面再說。

其實，拜占庭將軍問題最早是由 Leslie Lamport 在 1982 年發表的論文《The Byzantine Generals Problem》提出的，他證明了在將軍總數大于 3f，背叛者為 f 或者更少時，忠誠的將軍可以達成命令上的一致，即 3f+1<=n。而 Miguel Castro 和 Barbara Liskov 在 1999 年發表的論文《Practical Byzantine Fault Tolerance》中首次提出 PBFT 算法，該算法容錯數量也滿足 3f+1<=n。

BFT 是一個已經被研究得比較透徹的理論，它告訴我們，基于部分同步網絡模型的假定，在不超過三分之一的故障節點和作惡節點情況下，非拜占庭節點之間可達到最終一致性。PBFT 是其中最為著名的實現算法，意為實用拜占庭容錯算法。目前，區塊鏈的共識算法大多都是基于 BFT 的實現。Giskard BFT 也是由 PBFT 演進而來。

PBFT 算法在區塊鏈共識的應用

PBFT 算法被廣泛應用于各類區塊鏈共識，它不僅解決了共識過程中可能發生的拜占庭節點問題，同時也使系統始終能夠保持兩個屬性：安全性（safety）和活躍性（liveness）。

• 安全性 ：在 Crash 節點和 Byzantine 節點兩類錯誤發生時，共識系統不能產生錯誤的結果。在區塊鏈中，指的是不會產生雙重花費和分叉。

• 活躍性 ：系統一直能持續產生提交，在區塊鏈中，指的是共識會持續進行，不會卡住。假如一個區塊鏈系統的共識不可持續，那么系統無法響應客戶端新的交易請求，也就是不滿足 liveness。

我們直接以 PBFT 算法在區塊鏈共識的應用為例，總結算法的核心流程：

PBFT 的共識過程

由上圖可知，PBFT 是一個典型的三階段提交算法：

• pre-prepare （預備階段） ：各節點負責接收區塊、執行區塊，產生區塊投票簽名，開始廣播簽名給所有共識節點

• prepare （準備階段） ：各節點負責收集簽名，某節點收集滿 2*f 的簽名后，表明自身達到可以提交區塊的狀態，開始廣播 Commit 包

• Commit （提交階段） ：各節點負責收集 Commit 包，某節點收集滿 2*f+1 的 Commit 包后，直接將本地緩存的最新區塊提交到數據庫

看到這里，也許你會有以下疑問：

為什么不同階段所需要的簽名個數不同

對于 prepare 和 commit 階段來說，考慮最壞的情況：我們假設收到 f 個是正常節點發過來的簽名，也有 f 個是惡意節點發過來的，那么，第 2f+1 個簽名只可能是正常節點發過來的（因為我們限制了最多只有 f 個惡意節點）。由此可知，「大多數」正常的節點還是可以讓系統工作下去的。所以 2f+1 這個參數和 n>=3f+1 的要求是邏輯自洽的。而在 prepare 階段，節點 0 發出消息即可認為確認消息，所以 prepare 階段只需收集 2*f 個簽名。

為什么只有兩階段消息不能達成一致性

只有 pre-prepare 和 prepare 兩個階段消息是無法達成一致的。舉例說明，假設沒有 commit 階段，節點 1 在 prepare 階段收集滿 2*f 的簽名后，達到 Prepared 狀態，然而這個 Prepared 僅是節點 1 的一個局部視角，不是全局一致，此時節點 1 不能保證其余節點都達到 Prepared 狀態，如果少于 f 個非拜占庭節點成為 Prepared 狀態，節點 1 又確認了該消息，那么系統就出現了不一致。

為什么三階段消息可以達成一致性

說到這里，其實就很好理解為什么三階段消息可以達成一致性，某節點收集滿 2*f+1 的 Commit 包意味著有 f+1 個非拜占庭節點達成了 Prepared 狀態，也就意味著「多數」節點已經認同了消息。

下面，我們再介紹 PBFT 的視圖和視圖切換流程。

PBFT 共識算法使用視圖 view 記錄每個節點的共識狀態，相同視圖節點維護相同的 Leader 和 Replicas 節點列表。當 Leader 出現故障，為了保證協議活躍性（liveness），會發生視圖切換，若視圖切換成功 (至少 2*f+1 個節點達到相同視圖)，則根據新的視圖選出新 leader 。

話不多說，直接上視圖切換流程圖：

PBFT 的視圖切換流程

PBFT 的視圖切換流程也分為三個階段：

• view-change ：各副本節點（Replica) 認為主節點（Primary）有問題時，會向其它節點發送 view-change 消息

• view-change-ack ：各節點接收到 2*f+1 個 view-change 消息后，選舉當前存活的節點編號最小的節點成為新的主節點，并向該節點發送 view-change-ack 消息

• new-view ：當新的主節點收到 2*f+1 個其它節點的 view-change-ack 消息后，向其它節點廣播 new-view 消息。注意：從節點不會發起 new-view 事件

通過對共識流程的分析，相信大家對 view 切換流程都能夠很好地理解，這里我們不再贅述。接下來我們著重分析 PBFT 算法存在的問題，以及 Giskard BFT 改進優化。

PBFT 存在的問題

通過對 PBFT 共識流程三階段的詳細分析，可以看到消息傳輸的開銷很大。系統在嘗試達成狀態共識時，涉及到 n 個節點都需要廣播消息到 n-1 個其它節點，因此算法通信復雜度達到 O(n²)，在節點數目為 1000 的情況下所需要交換的通信量為 1,000,000。有實驗得出當節點數量超過 20 時，算法的性能會急劇下降。

另外，在 PBFT 選舉 Leader 的過程中，有可能經過多輪交互，選舉出的 Leader 一直長時間運行，直到 Leader 節點出現故障才發起視圖切換流程。但在區塊鏈系統中，視圖 view 表示一個共識單元，共識過程由一個接一個的 view 組成，每個 view 中由一個確定的提議人來主導共識協議，產生區塊，其余驗證人對區塊進行投票簽名達成共識。因為節點產生區塊與利益相關（如記賬權，區塊獎勵等），因此需要頻繁地更換出塊節點，也就是需要頻繁地切換視圖 view，這勢必會帶來巨大的網絡資源消耗。

Giskard BFT 共識優化

所以我們基于 BFT 協議，結合區塊鏈的特性，主要圍繞著以下幾點進行協議優化，設計了 Giskard BFT 。

_ view-change 流程優化_

所有的 BFT 協議都通過 view-change 來更換主節點。PBFT，SBFT 等協議具有獨立的 view-change 流程，當主節點出問題后才觸發。而在 Tendermint、HotStuff 等協議中沒有顯式的 view-change 流程、view-change 流程合入正常流程中，因此提高了 view-change 的效率，將 view-change 的通信復雜度降低。

Giskard BFT 也是基于 view 的的共識協議，為降低通訊復雜度，Giskard BFT 也沒有顯式的 view change 流程，而是把這個流程和正常出塊流程結合。Giskard BFT 約定每個提議節點在本視圖內連續產生 10 個區塊，并且每個區塊都達成 QC （Quorum Certificate，表示節點收到針對該區塊的 2*f+1 個簽名）狀態后，則自動切換到下一個 view ，不需要單獨的 view-change 投票流程。

下圖是顯式的 ViewChange 流程，可以看到它并沒有類似 PBFT 中的 view-change-ack 和 new-view 階段，這兩個流程被后續的 prepareQC(n) 進行代替。

Giskard BFT viewchange 投票流程

總結一下，view-change 流程優化的兩個重點：

• 不需要顯式的 view change 流程，減少投票動作。

• 沒有 view-change-ack 和 new-view 階段，而是結合區塊鏈特性，由后續的 prepareQC(n) 對新的 view 進行「間接」確認。

_ 應用 BLS 聚合簽名_

為了進一步減少消息通訊量，我們采用了聚合簽名技術。業界主流的聚合簽名方案是 BLS 聚合簽名。BLS 聚合簽名是在 BLS 簽名方案基礎上的擴展方案。

在 Giskard BFT 中，我們把針對 block 和 view-change 消息的多個節點簽名聚合成一個簽名，可以簡單地理解為：把多個節點的一段很長的簽名「壓縮」為一個簽名。這種做法極大地降低了通訊量，對提高協議的通信效率也起到了很大的作用。

_ 區塊生產和驗證并行化_

此處優化是 Giskard BFT 的獨到創新之處。這里的并行指的是：區塊生產和區塊驗證的并行化。

上文提到，Giskard BFT 是基于視圖 view 的共識協議，每個提議節點在本視圖內連續產生 10 個區塊，并行流程如下：

• 提議節點在一個 view 內可以連續提議多個區塊，下一個區塊的產生不用等上一個區塊達到 QC 狀態。

• 驗證人在接收上一個區塊投票的同時，可以并行執行下個區塊的交易。

這種做法極大提高出塊速度，也提高了系統的共識性能。

引進 pipeline 方式對區塊進行確認

在傳統 BFT 主導的區塊鏈系統中，每個區塊的共識通常都需要經歷明確的 Pre-Commit 和 Commit 階段才最終確認：

• Pre-Commit ：當節點收到 2*f+1 個 Prepare 投票時會廣播 Pre-Commit，Pre-Commit 可以看作對 Prepare 階段的確認。

• Commit ：當收到 2*f+1 個 Pre-Commit 投票時，表明所有節點對指定消息達成一致，提交到本地磁盤。

Giskard BFT 中的每個區塊只有 Prepare 投票，沒有明確的 Pre-Commit 和 Commit 階段，那么區塊如何達到最終的確認呢？Giskard BFT 可看作 Pipeline 版本的 BFT ，每個 prepareQC 都是對前面區塊更高階段的確認。

Giskard BFT 的區塊確認流程

如圖所示 prepareQC(2) 作為 Block(1) 的 Pre-Commit 階段 prepareQC(3) 作為 Block(1) 的 Commit 階段，Block(2) 的 Pre-Commit 階段。

簡單來說，就是「省略」了 PBFT 的 Commit 階段，這里讀者可能有疑慮：前文不是明確給出結論，必須通過三階段消息才能達成一致性？其實 Giskard BFT 不是真的沒有 Commit 階段，而是結合區塊鏈特性，將下一個區塊的 QC 狀態作為上一個區塊的 Commit 間接確認。

Giskard BFT 結合區塊鏈的鏈式結構，引進 pipeline 方式對區塊進行確認，使得協議變得簡潔而優美，能夠很好地進行流程化作業，提高了協議的性能，另外也對協議的可擴展性留足了設計空間。

結語

目前，應用了 Giskard 共識協議的 PlatON 測試網、主網和 Alaya 網絡都已經長時間穩定、高效運行，它的安全性（safety）和活躍性（liveness）得到了充分的驗證，同時 Giskard 共識對解決系統過于中心化，降低網絡通信復雜度、消息復雜度，提升共識效率以及整個區塊鏈的交易處理性能所起到的作用毋庸置疑。

在后期的協議版本中，我們將繼續深入優化：驗證人的選取不僅采用 VRF，還計劃結合可驗證秘密分享 PVSS、BLS 等密碼算法進一步增加隨機性；引入分組共識再次提升算法的可擴展性，以高效支持更多的驗證節點加入，增加網絡的安全性和容錯性。