PlatON提出了一種基於部分同步假設情形下的並行拜占庭容錯協議CBFT(Concurrent Byzantine Fault Tolerance)，解決區塊鏈共識效率的問題。本文分析了PBFT，Tendermint，Hotstuff等共識協議，CBFT綜合了其優點，透過pipeline的方式完成區塊生成和確認的並行，在一個檢視視窗內可以出多個塊，並可以在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)。view change過程中，需要所有的副本節點先time out，然後對於view change這件事達成共識，然後，他們把這個共識（以及已經達成了共識這件事）告訴新的主節點，新的主節點還要把這個訊息廣播出去宣佈view change，因此，view change的通訊複雜度是O(n3) 。
高達O(n3) 的通訊複雜度無疑給PBFT的共識效率帶來了嚴重的影響，極大地制約了PBFT的可擴充套件性。
BFT協議的最佳化
如何把O(n3) 的通訊複雜度降到O(n)，提高共識效率，是BFT共識協議在區塊鏈場景中面臨的挑戰。針對BFT共識效率的最佳化方法，具有以下幾類：
聚合簽名
E.Kokoris-Kogias等在其論文中提出了在共識機制中使用聚合簽名的方法。論文中提到的ByzCoin[4]以數字簽名方式替代原有PBFT使用的MAC將通訊延遲從O(n2)降低至O(n)，使用聚合簽名方式將通訊複雜度進一步降低至O(logn)。但ByzCoin在主節點作惡或33%容錯等方面仍有侷限。
之後一些公鏈專案，例如Zilliqa[5]等基於這種思想，採用EC-Schnorr多籤演算法提高PBFT過程中Prepare和Commit階段的訊息傳遞效率。
通訊機制最佳化
PBFT使用多對多(all-to-all)的訊息模式，因此需要O(n2)的通訊複雜度。
SBFT(Scale optimized PBFT)[6]提出了一個使用收集器(collector)的線性通訊模式。這種模式下不再將訊息發給每一個副本節點，而是發給收集器，然後再由收集器廣播給所有副本節點，同時透過使用門限簽名(threshold signatures)可以將訊息長度從線性降低到常數，從而總的開銷降低到O(n2)。
Tendermint[7]使用gossip通訊機制，樂觀情況下可以將通訊複雜度降低到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)。
HotStuff參考Tendermint，也將檢視切換流程和正常流程進行合併，即不再有單獨的檢視切換流程。透過引入二階段投票鎖定區塊，並採用leader節點集合BLS聚合簽名的方式，將檢視切換的通訊複雜度降低到了O(n)。
鏈式BFT
傳統BFT需要對每個區塊進行兩輪共識，O(n)的通訊複雜度可以讓區塊達到prepareQC，但是必須要O(n2)的通訊複雜度才能讓區塊達到commitQC。
Hotstuff將傳統BFT的兩輪的同步BFT改為三輪的鏈式BFT，沒有明確的prepare，commit共識階段，每個區塊只需要進行一輪QC，後一個區塊的prepare階段為前一個區塊的pre-commit階段，後一個區塊的pre-commit階段為前一個區塊的commit階段。每次出塊的時候都只需要O(n)的通訊複雜度，透過兩輪的O(n)通訊複雜度，達到了之前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(n^(3))的檢視切換開銷，在擴充套件性方面存在很大的問題。
Tendermint將round change和正常流程合併，簡化了檢視切換邏輯，將檢視切換的通訊複雜度降低為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)的通訊複雜度內完成檢視視窗切換。
根據上面的討論，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廣播給驗證人。
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流程如下：
1. 如果在時間視窗內，收到第n塊的prepareQC，則更新本地view+1，進入新的正常流程，這種情況下如果是新提議人達成n的QC，則開始廣播第一個區塊，如圖4所示，高度為BlockNumber(n)+1 ，並會攜帶n 區塊的prepareQC。
2. 如果時間視窗過期，節點首先會拒絕對當前提議人的區塊產生新的投票，同時沒有收到第n塊的prepareQC，則傳送ViewChange<ViewNumber, HighestQCBlock>訊息，如圖5所示。
3. 下一個時間視窗的提議人收到 N-f 個ViewChange訊息（我們將N-f 個ViewChange 訊息簡稱為 viewchangeQC )之後，使用BLS簽名聚合成一個QC簽名，然後更新本地ViewNumber+1，由於採用兩輪投票鎖定區塊的規則，新提議人可以簡單地從收到的N-f個viewchange訊息中選擇HighestQCBlock，將新的區塊序號定為 HighestQCBlock+1，如圖6所示，然後廣播第一個區塊給各驗證人節點，並攜帶HighestQCBlock的QC簽名和viewchange的QC簽名。
4. 各驗證人節點會根據收到的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個區塊，當前viewVi時間視窗超時，view切換到Vi+1，此時Vi產生的區塊只有部分得到QC，部分割槽塊進行重組，重組規則如下：
Pre-Commit狀態的區塊被鎖定，不能被重組，即如果當前節點在高度h上有Pre-Commit狀態的區塊，當前節點不能在高度h產生新的區塊，也不能在高度h對其他區塊投票
Prepare狀態的區塊可以被重組，即如果當前節點在高度h上有Prepare狀態的區塊，當前節點可以在高度h產生新的區塊，或者在高度h對其他區塊投票（只允許對更高viewnumber的區塊投票）
驗證人替換機制
CBFT共識中，每250個區塊（稱為一個 Epoch）就會更新驗證人集合，更新規則如下：
新驗證人可能由於網路連線或區塊不同步等原因不能參與共識，因此我們每次替換不超過8個節點，如果候選驗證人不足8個，替換的數量為候選驗證人的總數。
使用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(n3)。
Tendermint：網狀網路拓撲，採用二階段投票協議， 訊息達到prepared狀態即鎖定，檢視切換流程和正常流程合併，通訊複雜度為O(n2)。
Hotstuff：星狀網路拓撲，採用三階段投票協議，訊息達到pre-commited狀態即鎖定，檢視切換流程和正常流程合併， 通訊複雜度為O(n)。
CBFT：網狀網路拓撲，採用三階段投票協議，訊息達到pre-commited狀態即鎖定，自適配檢視切換流程，通訊複雜度為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.
原文連結：
https://platonnetwork.github.io/Docs/#/zh-cn/Introduction/[Chinese-Simplified]-PlatON共識方案
