作者：文檔 / 來源：PlatON

概述

PlatON提出了一種基于部分同步假設情形下的并行拜占庭容錯協議CBFT(Concurrent Byzantine Fault Tolerance)，解決區塊鏈共識效率的問題。本文分析了PBFT，Tendermint，Hotstuff等共識協議，CBFT綜合了其優點，通過pipeline的方式完成區塊生成和確認的并行，在一個視圖窗口內可以出多個塊，并可以在O(n2)O(n2)內完成視圖窗口切換，從而提高共識效率。

分布式網絡模型

按照分布式系統理論，分布式系統的網絡模型分為三類：

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

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

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

同步網絡模型是十分理想的情況，異步網絡模型是更為貼近實際的模型，但據FLP不可能[1]原理，在異步網絡模型假定下，共識算法不可能同時滿足安全性（safety）和活躍性（liveness），目前的BFT類共識算法多是基于部分同步網絡模型假定。我們也是基于部分同步網絡模型假定來進行討論。

BFT共識協議

概述

一個分布式系統是由多個節點組成，節點之間需要網絡發送消息通信，根據它們遵循的協議在某個任務消息達成共識并一致執行。這個過程中會出現很多類型的錯誤，但它們基本上可以分為兩大類。

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

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

考慮到這兩種錯誤，我們希望系統始終能夠保持兩個屬性：安全性(safety)和活躍性(liveness)。

• 安全性：在以上兩類錯誤發生時，共識系統不能產生錯誤的結果。在區塊鏈的語義下，指的是不會產生雙重花費和分叉。
• 活躍性：系統一直能持續產生提交，在區塊鏈的語義下，指的是共識會持續進行，不會卡住。假如一個區塊鏈系統的共識卡在了某個高度，那么新的交易是沒有回應的，也就是不滿足liveness。

BFT(拜占庭容錯協議)是一種即使系統中存在惡意節點也能保證分布式系統的安全性和活躍性的協議。根據Lamport[2]的經典論文，所有BFT協議都有一個基本假設：節點總數大于 3f 時，惡意節點最大為 f ，誠實節點可以達成一致的正確結果。

PBFT

實用拜占庭容錯算法（PBFT[3]）是現實世界里首批能夠同時處理第一類和第二類錯誤的拜占庭容錯協議之一，基于部分同步模型，解決了之前BFT類算法效率不高的問題，將算法復雜度由節點數的指數級降低到節點數的平方級，使得拜占庭容錯算法在實際系統應用中變得可行。

目前區塊鏈中使用的BFT類共識協議都可以認為是PBFT的變形，與PBFT一脈相承。

正常流程

PBFT正常流程如下所示（圖1中C為客戶端，系統中有編號分別為0～3的四個節點，且節點3為拜占庭節點）:

 

圖1 PBFT正常流程

 

PBFT 正常流程為3階段協議：

• pre-prepare：主節點（Primary）廣播預準備消息（Preprepare）到各副本節點（Replica)
• prepare：該階段是各個節點告訴其他節點我已經知道了這個消息，一旦某個節點收到了 包含n-f 個prepare消息（我們將使用QC也就是Quorum Certificate來指代，下同）則進入prepared狀態
• commit：該階段是各個節點以及知道其他節點知道了這個消息，一旦某個節點收到了n-f 個commit消息（QC）則進入committed狀態

視圖切換流程

視圖切換（viewchange）是PBFT最為關鍵的設計，當主節點掛了（超時無響應）或者副本節點集體認為主節點是問題節點時，就會觸發ViewChange事件，開始viewchange階段。此時，系統中的節點會廣播視圖切換請求，當某個節點收到足夠多的視圖切換請求后會發送視圖切換確認給新的主節點。當新的主節點收到足夠多的視圖切換確認后開始下一視圖，每個視圖切換請求都要包含該節點達到prepared狀態序號的消息。

在視圖切換過程中，我們需要確保提交的消息序號在整個視圖更改中也是一致的。簡單來說，當一個消息定序為n，且收到2f+1個prepare 消息之后，在下個視圖中，依然會被分配序號為n，并重新開始正常流程。

 

圖2 PBFT視圖切換流程 如圖2所示，viewchange會有三個階段，分別是view-change，view-change-ack和new-view階段。從節點認為主節點有問題時，會向其它節點發送view-change消息，當前存活的節點編號最小的節點將成為新的主節點。當新的主節點收到2f個其它節點的view-change消息，則證明有足夠多人的節點認為主節點有問題，于是就會向其它節點廣播。

 

通信復雜度問題

PBFT 是基于三階段投票即可達成共識的協議。prepare和commit階段中，都需要每個節點廣播自己的prepare或commit消息，因此通信復雜度是O(n2)O(n2)。

view change過程中，需要所有的副本節點先time out，然后對于view change這件事達成共識，然后，他們把這個共識（以及已經達成了共識這件事）告訴新的主節點，新的主節點還要把這個消息廣播出去宣布view change，因此，view change的通信復雜度是O(n3)O(n3)。

高達 O(n3)O(n3) 的通信復雜度無疑給PBFT 的共識效率帶來了嚴重的影響，極大地制約了PBFT的可擴展性。

BFT協議的優化

如何把O(n3)O(n3)的通信復雜度降到O(n)O(n)，提高共識效率，是BFT共識協議在區塊鏈場景中面臨的挑戰。針對BFT共識效率的優化方法，具有以下幾類：

聚合簽名

E.Kokoris-Kogias等在其論文中提出了在共識機制中使用聚合簽名的方法。論文中提到的ByzCoin[4]以數字簽名方式替代原有PBFT使用的MAC將通信延遲從O(n2)O(n2)降低至O(n)O(n)，使用聚合簽名方式將通信復雜度進一步降低至O(logn)O(logn)。但ByzCoin在主節點作惡或33%容錯等方面仍有局限。

之后一些公鏈項目，例如Zilliqa[5]等基于這種思想，采用EC-Schnorr多簽算法提高PBFT過程中Prepare和Commit階段的消息傳遞效率。

通信機制優化

PBFT使用多對多(all-to-all)的消息模式，因此需要 O(n)O(n) 的通信復雜度。

SBFT(Scale optimized PBFT)[6]提出了一個使用收集器(collector)的線性通信模式。這種模式下不再將消息發給每一個副本節點，而是發給收集器，然后再由收集器廣播給所有副本節點，同時通過使用門限簽名(threshold signatures)可以將消息長度從線性降低到常數，從而總的開銷降低到O(n)O(n)。

Tendermint[7]使用gossip通信機制，樂觀情況下可以將通信復雜度降低到O(nlogn)O(nlogn)。

view-change流程優化

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

Tendermint 將roundchange(和viewchange類似)合入正常流程中，因此roundchange和正常的區塊消息commit流程一樣，不像PBFT一樣有單獨的viewchange流程，因此通信復雜度也就降為O(n2)O(n2)。

HotStuff參考Tendermint，也將視圖切換流程和正常流程進行合并，即不再有單獨的視圖切換流程。通過引入二階段投票鎖定區塊，并采用leader節點集合BLS聚合簽名的方式，將視圖切換的通信復雜度降低到了O(n)O(n)。

鏈式BFT

傳統BFT需要對每個區塊進行兩輪共識，O(n)O(n)的通信復雜度可以讓區塊達到prepareQC，但是必須要O(n2)O(n2) 的通信復雜度才能讓區塊達到commitQC。

Hotstuff將傳統BFT的兩輪的同步BFT改為三輪的鏈式BFT，沒有明確的prepare，commit共識階段，每個區塊只需要進行一輪QC，后一個區塊的 prepare 階段為前一個區塊的 pre-commit 階段，后一個區塊的 pre-commit 階段為前一個區塊的 commit 階段。每次出塊的時候都只需要O(n)O(n)的通信復雜度，通過兩輪的O(n)O(n)通信復雜度，達到了之前O(n2)O(n2)的效果。

流水線（Pipelining）和并行處理（Concurrency）

PBFT、Tendermint等協議具有即時確定(Instant Finality)的特性，幾乎不可能出現分叉。在PBFT中，每個區塊被確認后才能出下一個區塊，Tendermint還提出區塊鎖定的概念，進一步確保了區塊的即時確定性，即在某個round階段，節點對區塊消息投了pre-commit票，則在下一個round中，該節點也只能給該區塊消息投pre-commit票，除非收到新proposer的針對某個區塊消息的解鎖證明。

這類BFT共識協議本質上是一個同步系統，將區塊的生產和確認緊密耦合，一個區塊確認后才能生產下一個區塊，需要在塊與塊間等待最大的可能網絡延遲，共識效率受到很大的限制。

HotStuff的Pipelining方法將區塊的生產和確認分離，每個區塊的最終確認需要后兩個區塊達到QC，也就意味著上一個區塊沒有完全確認（需要滿足Three-Chain）的情況下可以生產下一個區塊。這種方式實際上還是一個半同步系統，每個區塊的產生還是需要等上一個區塊達到QC。

EOS[9]的BFT-DPoS共識協議可認為是一種完全并行的Pipelining方案：每個區塊生產后立即全網廣播，區塊生產者一邊等待 0.5 秒生產下一個區塊，一邊接收其他見證人對于上一個區塊的確認結果，使用BFT協議達成共識，新區塊的生產和舊區塊確認的接收同時進行，這極大地優化了出塊效率。

CBFT 共識協議

為什么設計CBFT

前面的內容中，我們分析了BFT共識協議的問題，以及幾種主流的優化BFT共識協議，這些BFT共識協議在降低通信復雜度和出塊效率方面都取得了不錯的研究成果，但仍存在一些改進空間。

• PBFT 較之于之前的 BFT 算法雖更實用，但因受制于O(n3)O(n3)的視圖切換開銷，在擴展性方面存在很大的問題。

• Tendermint將round change和正常流程合并，簡化了視圖切換邏輯，將視圖切換的通信復雜度降低為O(n2)O(n2)，但需要等待一個比較大的網絡時延來保證活躍性。同時 Tendermint 仍然是串行出塊和確認，一個區塊的投票需要等上一個區塊 commit 完成才能開始。

• EOS的BFT-DPOS 共識協議中，區塊生產者可以連續產生若干區塊，同時區塊采用并行確認，提高了出塊速度。使用 BFT 協議確認出塊，但僅適用于強同步的通信模型。

• HotStuff 創新地提出了基于leader節點的、三階段提交的 BFT 共識協議，吸收了 Tendermint 的優點，將viewchange 和正常流程合并，并將 viewchange 的通信復雜度降至線性。同時通過簡化消息類型，可以 pipeline 的方式確認區塊。但引入了新的投票階段也會增加通信復雜度，同時一個視圖窗口只確認一個區塊，這無疑需要耗費較多的通信復雜度在視圖切換上。此外，基于Leader節點收集投票的星狀拓撲結構，比較適合于 Libra 這種網絡環境良好的聯盟鏈，在弱網環境中比較容易受單點故障影響，造成較大的 leader 節點切換開銷。

因此，我們提出了 CBFT 共識協議，在以上共識協議的基礎上進行進一步的優化，可以極大地降低通信復雜度 ，并且提高出塊效率。

CBFT概述

CBFT基于部分同步網狀通信模型，提出了一個三階段共識的并行拜占庭容錯協議。網狀的通信模型更適合公網的弱網環境，在PlatON上已經使用了該協議作為共識算法。

CBFT 的正常流程和 Hotstuff 類似，分為 prepare，pre-comit，commit 和 decide幾個階段。但 CBFT 還作了關鍵的改進：在一個視圖窗口內可以連續提議多個區塊，下一個區塊的產生不用等上一個區塊達到QC；而且各個節點可以在接收上一個區塊投票的同時，并行執行下個區塊的交易，以 pipeline 的方式對區塊進行投票確認， 從而極大提高了出塊速度。

CBFT 有自適配的視圖切換機制：在一個視圖窗口內，節點接收到足夠多的區塊以及贊成票（超過2/3的節點投票，也就是 QC）時，會自動進行窗口切換，切換到下一個窗口，無需進行 viewchange 投票。除此之外，節點才會啟動 viewchange 流程，并且在 viewchange 階段引入了和 Hotstuff 一樣的二階段鎖定投票規則，同時使用 BLS 聚合簽名，可以在O(n2)O(n2)的通信復雜度內完成視圖窗口切換。

根據上面的討論，CBFT 只在正常流程之外才會進行 viewchange，因此相比 HotStuff 會有更少的視圖切換開銷。

接下來先給出 CBFT 共識中涉及的相關概念及其含義說明，便于之后對 CBFT 進行詳細介紹。

CBFT相關術語

• 提議人(Proposer)： CBFT共識中負責出塊的節點
• T： 時間窗口，每個提議人只能在自己的時間窗口進行出塊
• N： 共識節點總數
• f： 拜占庭節點最大數量
• 足夠多贊成票： 表示為至少收到N-f張贊成票
• 驗證人(Validator)： 共識節點中非提議人節點
• 視圖(View)： 當前提議人的時間窗口可以產生區塊的時間范圍
• ViewNumber： 每個時間窗口的序號，隨著時間窗口遞增
• HighestQCBlock： 本地最高的N-f PrepareVote區塊
• ProposalIndex： 提議人的索引號
• ValidatorIndex： 驗證人的索引號
• PrepareBlock： 提議的區塊消息，主要包含區塊（Block)，提議人索引號
• PrepareVote： 驗證人對提議區塊的Prepare投票，每個驗證人需要執行區塊后才發送PrepareVote。主要包含ViewNumber, 區塊hash, 區塊高度，驗證人索引號(ValidatorIndex)
• ViewChange： 當時間窗口超時，提議人的區塊沒有都收集到N-f PrepareVote，則會向下一個提議人發送ViewChange。ViewChange包含 提議人索引號（ValidatorIndex），最高確認區塊(HighestQCBlock)
• 鎖(Lock)： 對指定塊高進行鎖定
• Timeout： 超時（時間窗口到期可以看作提議人的超時時間）
• 法定： 最大被允許
• 同一個View： 兩個View的ViewNumber相等，可以成為同一個View

BLS簽名

目前業界采用的聚合簽名方案主要是BLS聚合簽名。BLS聚合簽名是在BLS簽名方案基礎上的擴展方案。Boneh-Lynn-Shacham（BLS）簽名方案是Dan Boneh，Ben Lynn, Hovav Shacham[10]于2001年提出的。BLS簽名目前在許多區塊鏈項目如Dfifinity、fifilecoin、 Libra中都得到了運用。 BLS聚合簽名可以把多個簽名簡化為1個聚合簽名，對于提高BFT共識協議中的通信效率至關重要。

值得注意的是，BLS聚合簽名的方法是有漏洞的。一種稱為rogue public key的攻擊可以使得攻擊者有機會在獲得其他簽名者的公鑰和標準BLS簽名信息之后，能夠操縱聚合簽名的輸出結果。

對這個攻擊的一種最直接的防御措施是，參與BLS聚合簽名的人都需要先證明各自確實掌握了BLS私鑰信息，并事先注冊。這一過程可以通過使用一種簡單高效的零知識證明技術(Schnorr非交互式零知識證明協議)完成。參與者在進行聚合簽名之前，需要給出零知識證明，證明其持有公鑰信息的同時，確實掌握了該公鑰對應的私鑰信息。

CBFT協議流程

正常流程

 

圖3 CBFT正常流程

 

1. 提議人在成功進入到新的 View 后，會連續產生多個區塊，將消息PrepareBlock<ViewNumber, ProposalIndex, Block>廣播給驗證人。

2. 逐個驗證區塊：驗證人校驗簽名和時間窗口，執行區塊，成功后產生PrepareVote<ViewNumber,BlockHash, BlockNumber>。當PrepareVote對應的父區塊收集到N-f個PrepareVote時，使用BLS 將N-f 個PrepareVote的個體簽名聚合成一個聚合簽名，并將當前PrepareVote進行廣播。我們將N-f個PrepareVote 簡化為prepareQC(quorum certificate) 。

3. 當節點在當前view內最后一個區塊收到prepareQC，則會進入新的view開始下一輪投票。

為了更安全的投票，投票必須符合以下規則：

• 區塊執行后才能進行投票

• 誠實的節點只能對當前View提議的區塊進行投票

• 誠實的節點當View超時后不能再進行投票，也不接收當前View的投票

• 在同一個View內，相同高度的兩個區塊只能投其中一個

• 當對Block(n+1)進行投票時，Block(n)需達到prepareQC

ViewChange流程

 

圖4 時間窗口出塊完成時切換窗口

 

 

圖5 時間窗口出塊未完成但過期時切換窗口

 

 

圖6 viewchange投票流程 假設每個時間窗口最多允許產生n個區塊，viewchange 流程如下：

 

• 如果在時間窗口內，收到第n塊的prepareQC，則更新本地view+1，進入新的正常流程，這種情況下如果是新提議人達成n的QC，則開始廣播第一個區塊，如圖4所示，高度為BlockNumber(n)+1 ，并會攜帶n 區塊的prepareQC。
• 如果時間窗口過期，節點首先會拒絕對當前提議人的區塊產生新的投票，同時沒有收到第n塊的prepareQC，則發送ViewChange<ViewNumber, HighestQCBlock>消息，如圖5所示。
• 下一個時間窗口的提議人收到 N-f 個ViewChange 消息（我們將N-f 個ViewChange 消息簡稱為 viewchangeQC )之后，使用BLS簽名聚合成一個QC簽名，然后更新本地ViewNumber+1，由于采用兩輪投票鎖定區塊的規則，新提議人可以簡單地從收到的 N-f 個viewchange 消息中選擇 HighestQCBlock，將新的區塊序號定為 HighestQCBlock+1，如圖6所示，然后廣播第一個區塊給各驗證人節點，并攜帶HighestQCBlock的QC簽名和viewchange的QC簽名。
• 各驗證人節點會根據收到的 HighestQCBlock+1 序號開始新一輪共識。

區塊確認

Pipelining流程

在傳統BFT(PBFT, Tendermint)中，每個區塊通常都需要經歷明確的Pre-Commit 和 Commit階段才最終確認：

• Pre-Commit： 當節點收到N-f個Prepare投票時會廣播Pre-Commit, Pre-Commit 可以看作對Prepare階段的確認。
• Commit： 當收到N-f個Pre-Commit投票時，表明所有節點對指定消息達成一致，提交到本地磁盤。

根據上面的介紹，CBFT中也有類似的 Prepare 和 ViewChange 兩個階段，每個區塊只有Prepare投票，沒有明確的Pre-Commit 和 Commit階段，那么如何達到區塊的確認呢？CBFT可看作Pipeline版本的 BFT，每個prepareQC 都是對前面區塊更高階段的確認。

 

圖7 CBFT確認流程 如圖7所示prepareQC(2)作為Block(1)的Pre-Commit階段，prepareQC(3)作為Block(1)的Commit階段，Block(2)的Pre-Commit階段。

 

因此在CBFT中，只有兩種消息類型：prepare消息和view-change消息，每個消息的QC均采用聚合簽名方式驗證。

區塊重組

假設每個view允許產生n個區塊，當前view ViVi 時間窗口超時，view切換到Vi+1Vi+1，此時ViVi產生的區塊只有部分得到QC，部分區塊會進行重組，重組規則如下：

• Pre-Commit狀態的區塊被鎖定，不能被重組，即如果當前節點在高度h上有Pre-Commit狀態的區塊，當前節點不能在高度h產生新的區塊，也不能在高度h對其他區塊投票
• Prepare狀態的區塊可以被重組，即如果當前節點在高度h上有Prepare狀態的區塊，當前節點可以在高度h產生新的區塊，或者在高度h對其他區塊投票（只允許對更高viewnumber的區塊投票）

驗證人替換機制

CBFT共識中，每430個區塊（稱為一個 Epoch）就會更新驗證人集合，更新規則如下：

• 新驗證人可能由于網絡連接或區塊不同步等原因不能參與共識，因此我們每次替換不超過14個節點，如果候選驗證人不足14個，替換的數量為候選驗證人的總數。
• 使用VRF從候選驗證人中隨機選出新驗證人。

容錯恢復（WAL）機制

CBFT 共識提供了容錯恢復機制，也就是 WAL 模塊。該模塊不屬于嚴格意義上的預寫日志系統，但是借鑒了相關思想，在驗證人共識過程中將還未落鏈區塊的共識狀態和當前View的共識消息從內存分別持久化到本地數據庫和本地文件。在系統 crash 或者機器掉電重啟之后通過磁盤日志數據迅速恢復共識狀態。

這里簡要介紹一下主要的原理：

• 區塊、viewChange 在各驗證人間達成共識需要經歷驗證、投票等階段，某個區塊最終落鏈前與該區塊相關的共識狀態、消息都記錄在內存中。節點重啟也只是需要恢復這部分還未落鏈區塊的內存數據，因此 checkpoint 恢復點也就是當前 blockchain 的 currentBlock
• 鏈式投票可得，每一區塊的投票都是對前一區塊的確認，達到第三級，即達到區塊的 Commit 階段，因此 3-chain 區塊的 prepareQC 狀態在共識中至關重要，必須保證在重啟后恢復，這部分數據存儲至 db
• 共識消息只保留最近一輪 view 相關的，這部分數據存儲至文件

區塊同步機制

由于 CBFT 共識的異步并行性，導致最新的區塊存儲在內存中，并且區塊高度有3種高度：最高邏輯區塊高度、最高確認區塊高度和寫入磁盤區塊高度，并且三種高度依次遞減。因此 CBFT 中的區塊同步機制也在已有的PlatON-P2P的基礎上作了適配，調整了區塊高度的獲取方式。 這里概要介紹區塊同步機制如下：

• 新加入節點通過PlatON-P2P 利用快速同步或全同步更新至主網高度
• 共識節點利用CBFT-P2P的心跳機制與其它節點保持塊高一致
• 共識節點區塊落后時，會主動減少通信量，全力處理區塊同步
• 同步機制使用BLS簽名來減少網絡同步消息量

CBFT分析

基本規則定義

為方便對CBFT的安全性和活躍性進行分析 ，我們定義CBFT的幾條基本規則。

K-Chain 規則

對于一條鏈，滿足以下條件：

B(0)<-C(0)<-...<-B(k-1)<-C(k-1)

我們將其定義為K-Chain, 其中B為Block, C為B的prepareQC。我們可以看到當達到3-Chain時如：B0<-C0<-B1<-C1<-B2<-C2, B0達到Commit狀態。

Lock-Block規則

節點a中, 當區塊n收到區塊n之后的2次prepareQC，則區塊n定義為Lock-Block(a)。可以觀察到，當Lock-Block(a) = B0時，B0達到2-Chain, 如B0<-C0<-B1<-C1。

Unlock-Block規則

假設Lock-Block(a)為n，當n的子區塊n+1達到2次prepareQC,則Lock-Block(a)為n+1。可以觀察到，當Lock-Block(a) = B0時，B0達到2-Chain， 如B0<-C0<-B1<-C1-B2,當B0 Unlock-Block時，B0達到3-Chain，如B0<-C0<-B1<-C1<-B2<-C2。

Previous-Block規則

形如 Block(B)<-prepareQC(B)<-Block(B')，我們將Block(B)定義為Block(B')的Previous-Block， 則可表示為Previous-Block(B') = Block(B)。

由Lock-Block與Previous-Block規則可知:

在節點a中，形如B<-C<-B'<-C'<-B'' , Previous-Block(B'') > Lock-Block(a)

Commit 規則

當區塊n, 收到區塊n之后的3次prepareQC，則區塊n被Commit。可以觀察到，當B0被Commit時，B0達到3-Chain，如B0<-C0<-B1<-C1<-B2<-C2。

安全性（safety）證明

1） 不存在同一個View中有兩個相同高度區塊都能收到足夠多投票

證明： 假設N=3f+1為節點總數，f為拜占庭節點最大數量，那么當收到2f+1投票為足夠多投票。因兩個區塊都收到至少2f+1,投票總量至少為 2(2f+1) = N+f+1, 可以看到至少有f+1對兩個區塊投了票，與f個拜占庭節點假設矛盾。

2） 對于3-Chain來說，B0<-C0<-B1<-C1<-B2<-C2, ViewNumber(B2) >= ViewNumber(B0)。那么存在Block(B)，當ViewNumber(B) > ViewNumber(B2)，則Previous_Block(B) > B0。

證明： 對于正常誠實節點（給區塊B2，B投過票）來說， 那么節點至少可以看到B0<-C0<-B1<-C1<-B2, 也就是Lock-Block最小為Lock-Block(B0)。因為ViewNumber(B) > ViewNumber(B2)，則根據ViewChange確認規則，ViewNumber(B)的第一個區塊不小于B1，則Previous_Block(B) > B0

3） 假設節點n的Lock-Block(n) = B，節點m的Lock-Block(m) = B'，如果Number(B) = Number(B'), 則Hash(B) = Hash(B')

證明： 由上面Lock-Block規則可知，存在2種Lock-Block場景，第一種情況兩個QC在同一View內，則由1可知不存在B'和B同時收到足夠多投票。第二種情況，出現B與B'分屬不同View，且都收到prepareQC(B), prepareQC(B')。假設ViewNumber(B') > ViewNumber(B), 那么根據結論2，Previous_Block(B') > B，與假設矛盾。

4） 在Commit階段不會有兩個相同高度不同塊Hash被Commit

證明： 由3可知，如果Number(B) = Number(B'),不存在B，B''同時被Lock-Block。則可推不存在Commit(B),Commit(B')都被提交。

活躍性（liveness）證明

假設節點間網絡最大延時為T，執行區塊為S

1） 不存在時間窗口永遠小于time(prepareQC)*2時間

證明： 根據實際網絡狀況，合理調整實際窗口大小，可以保證時間窗口內至少達成2次QC，則時間窗口至少為 2S+4T

2） ViewNumber可以達成一致，并且遞增

證明： ViewChange達成一致最少需要T，由結論1可以保證ViewChange可以達成一致，為那么ViewNumber可以進行遞增切換

3） Lock-Block高度永遠遞增

證明： 假設ViewNumber為n, n+1, 由安全證明（2），可以保證ViewNumber(n+1)的第一個區塊Previous-Block至少為Lock-Block(View(n))，又由于活證明（1), 至少有兩次prepareQC，可以得到兩個View鎖定高度的關系，Lock-Block(View(n+1)) >= Lock-Block(View(n))+1

通信復雜度分析

• PBFT: 網狀網絡拓撲，采用二階段投票協議，消息達到prepared狀態即鎖定，有單獨的視圖切換流程，正常流程通信復雜度為O(n2)O(n2)，視圖切換流程通信復雜度為O(n3)O(n3)。
• Tendermint: 網狀網絡拓撲，采用二階段投票協議， 消息達到prepared狀態即鎖定，視圖切換流程和正常流程合并，通信復雜度為O(n2)O(n2)。
• Hotstuff 星狀網絡拓撲，采用三階段投票協議，消息達到pre-commited狀態即鎖定，視圖切換流程和正常流程合并， 通信復雜度為O(n)O(n)。
• CBFT: 網狀網絡拓撲，采用三階段投票協議， 消息達到pre-commited狀態即鎖定, 自適配視圖切換流程， 通信復雜度為O(n2)O(n2)。

回顧與總結

本文討論了目前常見的BFT類共識算法，提出了一種可以更適合公網環境的CBFT協議，可以在滿足安全性和活躍性的前提下，大大提高區塊出塊確認速度，滿足區塊鏈當下越來越高的共識速度需求。

參考文獻

[1] M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,”J. ACM, 1985.

[2] L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3), 1982.

[3] M. Castro and B. Liskov. Practical byzantine fault tolerance. In OSDI,1999.

[4] E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford, “Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing,” 2016.

[5] TEAM T Z. Zilliqa TechnicalWhitepaper[J]. Zilliqa, 2017: 1–8.

[6] Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, Alin Tomescu，“a Scalable and Decentralized Trust Infrastructure”，2018.

[7] C. Unchained, “Tendermint Explained — Bringing BFT-based PoS to the Public Blockchain Domain.” [Online]. Available: https://blog.cosmos.network/tendermint-explained-bringing-bft-based-pos-to-the-public-blockchain-domain-f22e274a0fdb.

[8] M. Yin, D. Malkhi, M. K. Reiterand, G. G. Gueta, and I. Abraham, “HotStuff: BFT consensus in the lens of blockchain,” 2019.

[9] “EOS.IO Technical White Paper v2.” [Online]. Available: https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.

[10] Dan Boneh, Manu Drijvers, Gregory Neven. "BLS Multi-Signatures With Public-Key Aggregation", 2018.