在已經大規模投入使用中的分散式資料庫系統環境中，有可能存在很多的宕機錯誤。根據 CAP 原理[2]，Paxos 和 Raft 協議被設計為在犧牲一定可用性的情況下，解決在節點伺服器可能宕機問題的協議[3]。
然而這些協議在區塊鏈領域內還不能直接使用，因為還有其他更多在區塊鏈領域內可能出現的錯誤。在表 1 中這種任意型別錯誤都可能發生的場景中，伺服器有可能產生原本不應該輸出的內容，系統要做好最壞情況的準備。例如，當一個伺服器向不同的伺服器傳送截然相反的訊息時，那麼僅可處理宕機錯誤 Paxos 協議就無能為力了。
這種型別錯誤，也被稱為拜占庭錯誤，最早由 Pease 和 Lamport 在上世紀80 年代透過拜占庭將軍問題進行描述和分析[4][5]。
因此相較於分散式資料庫，區塊鏈的對於一致性問題的設計和實現要更為複雜，這也是為什麼區塊鏈不只是一個簡單的分散式資料庫的原因之一。
3.2.BFT 共識原理及流程簡介
Lamport 等人在其經典論文[4]中除了提出拜占庭將軍問題外，也提供了兩種解決辦法[6][7]。
第一種為“口頭訊息”的 OM(m)協議，即除了鏈路上可使用加密安全保障外，不允許使用任何的加密演算法。該協議需要兩兩之間遞迴的傳遞大量訊息，因此訊息複雜度很高，為指數級，不太具有可實際操作性。但這一演算法仍有其很高的價值，首先是為“實用拜占庭容錯”（Practical Byzantine Fault Tolerance）這一多項式級別複雜度協議的誕生做了一個鋪墊；另外，其 1/3 容錯節點數量也被證明為是該類演算法的理論上限。
而第二種為“加密訊息”的 SM(m)協議。該演算法與第一種不同之處在於使用簽名演算法。每個節點都能產生一個不可偽造的簽名，並可由其他節點進行驗證。當收到訊息後，節點會透過簽名來判斷及驗證該訊息是否已收到過。最終不再收到訊息後，訊息共識結束。它同樣假設是在一個同步網路內進行；另外，簽名身份體系資訊需要在網路執行前確定，較難實現擴充套件。Vitalik 近期在其部落格上釋出了一篇名為《一個 99%容錯共識的指南》[8]就是根據這一協議在區塊鏈實際場景中所作的適應性改造探索[9]。
3.3.技術思路分析
與從比特幣系統中衍生出的中本聰共識不同，BFT 類協議基於節點間傳遞訊息對網路中提案達成共識。因此一般來說訊息複雜度較高，而且節點的加入和退出過程需要進行特別處理，但一旦達成共識則形成確定性結果，而不是中本聰共識的概率上的最終一致。
因此基於以上特性，BFT 類共識目前在金融場景以及聯盟鏈場景中應用的更多。不過隨著研究的探索推進，一些可在公有鏈場景下使用的 BFT 共識也正在不斷研發出來。
4. BFT 類共識概覽
我們在已有 BFT 類共識分類[10][11]的基礎上，繼續對目前 BFT 協議進行了梳理。因為 BFT 協議中的無論是口頭協議還是書面協議都不夠“實用”，很難在實際場景中直接運用。因此後來學術界和業界對 BFT 協議有了大量的改
進。按照改進思路的不同，這些協議主要可分為以下 3 大類方向：
·針對無拜占庭錯誤場景進行最佳化
·針對拜占庭錯誤場景進行最佳化
·為公鏈應用而做的最佳化
4.1.針對無拜占庭錯誤場景進行最佳化
此場景假設大部分情況下，網路中的節點執行都正常，拜占庭錯誤並不經常出現，因此可對這種節點均正常情況下的共識機制進行簡化或最佳化。
下面我們根據不同的最佳化方法，對這些協議進行分項介紹。
4.1.1.基於協約的方法
對 BFT 協議最為經典的改進主要是以 PBFT 為代表的基於節點協約一致（Agreement）的方法。該類協議通常會有一個主節點作為網路中的樞軸。比其他節點相比，主節點在共識過程中會發出最主要的作用，但通常也會成為系統效能的瓶頸。因為主節點需要將客戶端發來的請求排序後傳送給所有的備節點。所有節點透過互相通訊後達成一致，實現安全性（Safety）；大多數協議中所有節點也會向客戶端回覆響應，實現活性（Liveness）。該類協議通常需要 3f+1 個節點來實現對 f 個拜占庭節點的容錯。
實用拜占庭容錯（Practical Byzantine Fault Tolerance. 簡稱 PBFT）[12]是早期對其進行的改進，將 BFT 的訊息複雜度從指數級降低為O(n2)級別，即具備了可實際使用的條件。
PBFT 協議將共識過程分為了 5 個階段（如果不算與客戶端互動的階段，則可視為 3 個階段）：
·Request 階段是客戶端傳送資訊；
·在 Pre-prepare 階段，主節點接到訊息對其簽名並分配一個唯一的序號n 並將該訊息傳送給其他節點；
·Prepare 階段：所有備份節點收到主節點發來的 PRE-PREPARE 訊息後，將一個包含當前檢視號 v、訊息序號 n、訊息摘要的 PREPARE 資訊發給所有其他節點。如果節點收到了 2f 個以上的 PREPARE 訊息後則進入到下一階段並且該訊息處於 Prepared 狀態。
·Commit 階段：每個節點廣播一個保護當前檢視號 v、訊息序號 n 的 COMMIT 訊息。當節點收到 2f 個相同的 COMMIT 訊息並且小於序號 n的訊息都已被執行，那麼當前訊息會被執行並被標記為 Committed 狀態。
·Reply 階段：所有節點將執行結果返回給客戶端。
除了以上階段流程外，協議執行過程中還涉及到幾個重要概念：
·水位：每個節點在執行協議時會設定一個處理訊息的視窗，訊息序號在這個區間內的時候才會被處理，例如最小序號設為 h、最大序號為 H。
·檢查點（Checkpoint）：在執行提交過程中所有已處於已準備好（Prepared）和已提交狀態（Committed）的資訊會被記錄在記憶體中。節點會定期（每執行 k 個請求後）記錄一個穩定的檢查點並截斷記錄，即每執行 k 個請求後，會將水位 h 和 H 提高 k 個單位。
·檢視切換（View Change）：但是當節點發現對某個訊息的等待超過一定時間後，則認為是主節點失效，會傳送檢視切換（VIEW-CHANGE）訊息並開始檢視切換的過程。
·批次（Batch）:實際執行中會採用的一些最佳化改進技術，例如批次方式，即實際程式並不是對單個提交來每次執行協議，而是會在以集合形式同時在網路中處理，並透過設定批次大小（Batch Size）的方式來控制處理訊息的數量。
在設定了以上執行機制後，儘管訊息複雜度仍然較高，PBFT 已具備了實際執行的可行性。之後的許多 BFT 類協議均在 PBFT 協議基礎上進行改進，並將 PBFT 作為研究對比的基準物件。
Chain 協議。Chain 協議[13]採用了一個和其名稱很相似的鏈條式傳播路徑[14]。從主節點開始，每一次傳播時即加入該節點的摘要資訊。當客戶端較多時，Chain 通常會比 PBFT、Zyzzyva 等吞吐量更高。
Ring 協議。Ring 協議[15]使用環形拓撲方式來傳遞訊息，即每個節點都有訊息的上一個傳送者和下一個接收者，以此方式來降低對部分節點分配更多工作而形成的效能瓶頸問題。對有無錯誤的不同場景，Ring 分別採用兩種執行模式：快速模式（Fast Mode）和彈性模式（Resilient Mode），並採用 ABSTRACT 框架進行切換[14]。
BFT-SMaRt 協議。BFT-SMaRt[16]與 PBFT、UpRight[17]類似，但增強了可靠性、模組化程度、同時還提供了靈活的程式設計介面。
4.1.2.基於 Quorum 的方法
Quorum 機制是一種分散式系統中常用的機制，用來保證資料冗餘和最終一致性的投票演算法。其主要思想來源於抽屜原理，常用於分散式系統的讀寫訪問控制[18]。
該類共識協議不需要節點間相互通訊，而是由節點直接執行並響應客戶端發來的請求。當受到足夠數量的響應後，客戶端才會將結果最終提交。但是當出現拜占庭錯誤場景時，通常會花費較大的代價來解決。另外，由於缺少對請求的排序機制，Quorum 方法無法處理有競爭（contention）的情況。
Q/U 協議。Q/U 協議（Query/Update）[19]是一個典型的基於 Quorum的協議。Q/U 沒有主節點來為請求排序，而是由客戶端直接向節點傳送請求並由節點反饋結果。它需要 5f+1 個節點來對 f 個拜占庭節點容錯。
HQ 協議（Hybrid Quorum）[20]是另一個較為早期和著名的共識協議。正如其名稱，HQ 綜合參考並最佳化了 Q/U 協議和 PBFT 協議：只需要 3f+1個節點進行容錯，並針對沒有競爭的情況簡化了 PBFT 節點間通訊。當沒有競爭情況下，共識主要分為兩個階段：第一階段是客戶端傳送請求並收集節點的狀態資訊；當收到結果表明 2f+1 個節點狀態相同且可以執行請求後，開始第二階段資訊傳送、由節點執行請求。而如果發現有競爭，則採用類似PBFT 的解決過程，效能也退化為和 PBFT 類似。
Quorum 協議也是基於 Quorum 機制的一個共識協議[14]，主要沒有客戶端競爭的非非同步網路而進行設計，只需要 3f+1 個節點進行拜占庭容錯。當沒有錯誤產生時，Quorum 協議的傳播路徑和 Q/U 類似，節點獨立執行請求並自己維護一個執行歷史記錄。當客戶端數量較少時，其吞吐量和延遲等效能指標均比其他 BFT 類共識更好。但其缺點也和 Q/U 類似，無法處理客戶端有競爭的情況[10]。
4.1.3.基於 Speculation 的方法
在這類協議中，節點不需要透過需要消耗大量系統代價的 3 階段提交過程即可響應客戶端的請求。採用了更樂觀的策略，節點同意由主節點發出的排序請求並給客戶端返回結果。由客戶端而不是節點來負責考慮一致性問題。如果發現不一致問題，由客戶端負責通知節點回滾至一致狀態。
Zyzzyva 協議。Zyzzyva 是該類中最典型的一個協議[21]。它需要 3f+1 個節點進行拜占庭容錯。與基於 Agreement 的協議類似，Zyzzyva 中的主節點也是將客戶端發來的請求排序後轉發其他節點。每個節點根據自身歷史記錄來執行請求並將結果反饋給客戶端。客戶端根據節點返回的一致性結果數量分別執行不同的動作。
在沒有錯誤的場景下，Zyzzyva 表現比 PBFT 和 Q/U 等協議要好；但是當有錯誤時，因為要涉及到和 PBFT 類似的 view change 過程，其效能也會急劇下降。
Zeno 協議。Zeno 協議[22]在 Zyzzyva 基礎上進行修改，將原有的強一致性替換為一個較弱的最終一致性保證。它允許客戶端偶爾忽略其他更新，但是當網路不穩定時，所有節點的狀態需要進行合併以達成一致。
ZZ 協議。ZZ 協議[23]同樣基於 Speculation 機制。因其還採用了分離處理的機制，也可將其歸為“分離處理一致性與執行請求的階段”的類別，我們將在後續章節繼續介紹。
4.1.4.基於客戶端的方法
基於客戶端的方法透過避免節點間通訊的方式，來避免異常節點對正常節點的攻擊、誤導或延遲。協議完全依賴於這些客戶端的正確性，假設客戶端都沒有異常、是誠實且在宕機時會被外部所感知的。
OBFT（Obfuscated BFT）協議[24]是這一類協議的典型代表。它需要 3f+1 個節點進行容錯，但與其他很多 BFT 協議涉及到節點間通訊不同，OBFT協議中的節點完全不需要關注其他節點並只與客戶端聯絡，因此避免了惡意節點干擾其他正常從而影響系統效能的問題，不過這也帶來了一個較強的假設：必須完全信任客戶端不會作惡。因此該類協議都存在著較難在實際場景中進行應用的問題。
4.1.5.基於可信元件的方法
因為 FLP 不可能性原理（即使網路通訊可靠也無法在任何場景下都能達到共識[25]），一些協議並不使用傳統的超時等機制而是基於外部的可信元件進行設計。這些元件也需要被認為是無拜占庭錯誤的，但允許存在宕機等臨時性無法提供服務的情況[11]。基於以上條件，該類協議可以將容錯節點數量從 3f+1 將為 2f+1。
例如，CheapBFT 協議[26]。需要基於一個叫做 CASH 的 FPGA 可信裝置，從而降低正常情況下協議對於資源的使用。
4.1.6.基於拜占庭鎖的方法
拜占庭鎖是拜占庭協議的擴充套件，透過利用 IO 絕大多數時間裡不會出現競爭的特性來達到降低伺服器響應時間、提高吞吐量與擴充套件性的效果。
這種方法最早由 Zzyzx 協議[27]提出，包括加鎖和解鎖兩個部分。加解鎖過程均基於現有拜占庭協議達成對客戶端授權的一致。當授權完成，則獲得鎖的客戶端可直接進行操作，從而去掉了主節點排序、節點間通訊等操作，從而大幅度提高吞吐量。但當有多個客戶端需要頻繁切換時，其效能也會大幅下降，因此該協議較為適用於客戶端不會頻繁發生變化的情況下。
4.1.7.基於分離一致性與執行請求的方法
還有一類改進方法是將共識與執行提交的過程分開，因為執行客戶端請求只需要 f+1 個（當沒有拜占庭節點或者客戶端可驗證結果正確性時）或 2f+1個節點（當有可能存在拜占庭節點且客戶端不可驗證正確性時），因此可將協議的執行分為 2 個部分，一部分節點負責一致性共識協議，而另一部分負責執行提交，從而提高吞吐量。
ZZ 協議，透過虛擬化技術[23]把節點均正常場景下的執行所需節點數量從 2f+1 降為 f+1 個。在沒有錯誤場景時，只透過 f+1 個節點來執行請求，其餘伺服器在休息狀態；而當執行請求的節點發生錯誤時，客戶端透過虛擬化技
術快速啟動更多的節點來執行[11]。
ODRC 協議也是將執行節點數量將為了 f+1，但與 ZZ 協議不同，它並沒有採用額外的虛擬化等技術，而是在 BFT 協議過程中的節點達成一致後、執行請求前增加了一個選擇執行節點的階段。該階段根據當前系統狀態，選擇指定數量的節點執行請求[11]。
4.2.針對拜占庭錯誤場景進行最佳化
上面介紹的一類協議均是針對沒有錯誤的場景對 BFT 協議進行簡化而設計，因此當遇到拜占庭錯誤時，這類協議的效能一般都會下降比較多，甚至很難保證系統活性。而另一類協議的改進目的是為了有效對拜占庭行為（甚至是一些罕見的行為）進行容錯，降低系統在有無拜占庭錯誤這兩種場景下的表現差異。主要有以下幾個比較典型的協議。
Aardvark 協議。Aardvark 協議[28]的通訊過程與 PBFT 類似，但對許多可能的錯誤場景設計了適應性機制以保證系統的安全性和活性。這些適應性機制包括：對客戶端採用混合簽名等機制來防止客戶端作惡；更為積極主動的觸發 view change 過程以避免主節點有拜占庭行為；為每個節點設計 3f+1 個網路介面（其中 1 個用於其與客戶端通訊，其餘 3f 個用於節點間通訊），以此隔離網路通道來防止流量攻擊。
Prime 協議。因為 PBFT 協議中當主節點作惡的 view change 過程對效能的影響較大，即便主節點不進行任何主動作惡，只要在處理排序過程中刻意增加延遲就可以降低系統整體效能表現。Prime 協議[29]針對此情況進行了改進，在 PBFT 過程前增加了一個預排序的階段，包括 PO Request、PO ACK、PO ARU 等階段。透過這種分析主節點排序時間的方式，使得所有節點來監控網路表現。因此主節點必須及時將訊息傳送給其他節點以避免被替換掉。因為引入了額外的階段，Prime 在正常場景中的效能要比 PBFT 等協議要低；但在存在錯誤場景中其表現要比其他協議要好。
Spinning 協議。Spinning 協議[30]在 PBFT 協議的基礎上，設計用來減輕更換主節點的代價。在正常場景中的，Spinning 通訊過程與 PBFT 相同。不過它沒有 view change 過程，而是透過合併操作的方式來收集不同節點資訊來決定之前檢視中的操作是否應在新檢視中執行。
RBFT 協議。Redundant-BFT 協議[31]利用目前所流行的多核技術來保障魯棒性。該協議採用與 PBFT 類似的通訊過程，但在 Pre-prepare 階段前增加了一個 Propagate 階段。客戶端首先將訊息傳送給 f+1 個節點，這些節點在 Propagate 階段相互傳遞訊息以此來保證客戶端請求會被所有正常節點接收到。RBFT 執行 f+1 個同一個協議的多個例項，其中每個例項都對應一個在不同物理機器上執行的主節點，不過只有被主例項所排序的請求才會被有效執行。備份例項執行的意義主要在於監測執行效能：當發現主例項執行緩慢時，備份例項將觸發 view change 過程選擇出一個新的主例項。
4.3.為公鏈應用最佳化
傳統 PBFT 及類似協議，其自身的特性導致應用場景有較多限制，例如訊息複雜度隨節點數成平方級別上升、主節點容易成為系統效能瓶頸、節點列表需要提前固定且節點間相互已知。所以在分散式賬本系統中，更多應用於聯盟鏈或私有鏈場景中。
為了適應公有鏈場景中的大規模擴充套件需求，有不少專案進行了有益嘗試，具體方式可主要包括與公鏈共識結合以及基於密碼學機制等兩大類方式。
4.3.1.與中本聰共識結合
為了在公有鏈中利用 BFT 類共識的結果可快速得到最終確認等優點，一類做法是將 BFT 類協議與中本聰協議進行結合，以此來取長補短，將 BFT 類共識引入應用到公有鏈的業務場景中。
例如，Elaine Shi 等在 2017 年提出將 BFT 類共識與中本聰共識結合的辦法[32]：透過 PoW 先選出負責共識的委員會（Commitee）；由委員會再進行 PBFT 過程達成共識並出塊[33]。
DPoS+BFT 協議也是類似的思路。該協議是 BFT 類協議與中本聰協議結合的一個典型代表，被用於 BM 開發的石墨烯[34]“全家桶”平臺，包括 BitShares[35]、Steemit[36]、EOS[37]等。通證持有者以投票等方式選出自己支援的“代表”，並由這些代表組成的見證人網路透過 BFT 的方式進行共識。例如 EOS 中，使用者投票產生 21 個可出塊的“超級節點”，以 BFT 方式共識後輪流出塊，對 1/3 以下的“超級節點”可以容錯。基於該類共識協議的平臺效能較高，且不需要競爭挖礦等，但缺點是略微中心化。
DBFT 協議是 NEO 提出的授權拜占庭容錯協議[38]，和 DPoS+BFT 思路有些類似，是一種透過代理投票實現大規模參與的共識協議。通證持有者可透過投票選出他所支援的“代理”，然後代理再透過 BFT 達成共識。因此它也和DPoS+BFT 類似，具有快速、擴充套件性好等特點，但也同樣受到共識節點數量有限、中心化程度太高等質疑。
Tendermint BFT 協議。Cosmos 專案提出了名為 Tendermint BFT 的一種基於 BFT 的 PoS 共識協議[39]。它以加權輪詢的方式產生驗證者集合，由選出的驗證者產生共識提議並進行 BFT 過程。因此它也是一種在半同步網路中使用的確定性演算法[40]。
FBA 協議。Stellar 使用的恆星共識協議（Stellar Consensus Protocol）的背後是一種聯邦拜占庭協議（Federated Byzantine Agreement）。該協議並不是直接把 BFT 和某一箇中本聰共識結合，而是參考了中本聰對比特幣的設計理念。該協議實現一個開放式的節點成員列表，任何人都可以加入。網路中的每個節點可自行選擇其 Quorum，降低對非理性行為的容忍程度，所以其效能和可擴充套件性都較為突出，但一些拜占庭行為也可能導致分
叉等情況發生，因此節點需要花費不少代價去設定其所信任的節點列表。
還有一些專案在嘗試探索把 BFT 協議引入當前公鏈平臺中，例如 Istanbul BFT（IBFT）[41]就是透過引入驗證者（validator）並基於 Quorum 機制執行，並被探索用於當前以太坊平臺。
除了狹義的“區塊鏈”方式外，Hashgraph[42]也可認為是一種 BFT 類共識與 DAG 結合的協議。它透過 gossip about gossip 降低通訊量，並且也是非同步的 BFT 協議。
4.3.2.基於密碼學最佳化
另一種可運用於公鏈的思路是利用密碼學的方法，包括聚合簽名、可驗證隨機函式、門限簽名等，以達到降低 BFT 類共識的通訊代價、提高共識效率的目的。
聚合簽名
E.Kokoris-Kogias 等在其論文中提出了在共識機制中使用聚合簽名的方法。論文中提到的 ByzCoin[43]以數字簽名方式替代原有 PBFT 使用的 MAC 將通訊延遲從O(n2)降低至o(logn)；使用聚合簽名方式將通訊複雜度進一步降低
至O(logn)。但 ByzCoin 在主節點作惡或 33%容錯等方面仍有侷限。之後一些公鏈專案，例如 Zilliqa[44]等基於這種思想，採用 EC-Schnorr 多籤演算法提高 PBFT 過程中 Prepare 和 Commit 階段的訊息傳遞效率，並結合分片等最佳化技術以希望突出改進公有鏈平臺 TPS。
Gosig[45]也使用該方法，同時還結合了 Algorand 以 VRF 方式選擇“Leader”和多輪投票等方法來儘量降低 Leader 作惡可能性。
可驗證隨機函式
Algorand 的 BA★協議[46]使用了另一種密碼學方法——可驗證隨機函（VRF），以加密抽籤的形式隨機決定“驗證者”，並以帶有權重的方式來全網共識，可認為是 BFT 類共識+PoS 或 PoWeight 的架構。投票過程分為兩個階段：第一階段透過一個分級共識選出“驗證者”共識最多的候選區塊；
第二階段執行一個二元拜占庭協議（接受出塊或產生空塊）。執行速度很快，不太容易產生分叉且交易確認時間雖使用者數增加變化不大[33]。另外，Algorand 透過加密方式隱藏了“領導者”的真實身份，提高了針對 Leader 攻擊的安全性。
VBFT 協議也是使用 VRF 的一個共識協議[47]，由 Ontology 提出，可認為是 PoS+VRF+BFT：在共識協議的各個階段，分別使用 VRF 從網路中選出該階段所需要的節點，例如提案節點、驗證節點、確認節點等並完成最終的共識。其中的選擇引數是根據 PoS 來確定。
門限簽名
以上介紹的協議大部分都需要假設基於一個同步或半同步的網路環境，而 HoneyBadger BFT 是第一個知名的非同步 BFT 類協議[48]，可在訊息延遲沒有明確上限的非同步網路中執行。它首先將交易拆分為多份，各個節點間相互，減輕發起節點的訊息傳送瓶頸問題。而因為其非同步網路環境，節點間收到交易是非同步的、隨機順序的。節點以二元拜占庭協議剔除無效交易和重複交易等後，得到一個非同步公共交易子集（Asynchronous Common Subset）[49]。
而門限加密使得只有 f+1 個誠實節點共同合作才能解密出訊息原文，防止惡意節點對於最終交易集的攻擊。HoneyBadger BFT 協議的主要限制是其在非同步網路下為一個非確定性共識演算法（FLP 不可能性原理[25]）。
5. 實測對比
除了進行理論上的歸納總結與分析外，我們選用 PBFT、Zyzzyva、Zilliqa 協議，編寫共識協議的程式進行實測模擬。透過橫向與縱向的測試比較，以期得出以上共識協議的技術建議。
5.1.測試方案介紹
由於共識協議都需要基於一個實際的應用場景，我們在程式中將節點處理計算的過程設定為一個固定的延時；訊息傳輸採用訊息佇列方式來實現。程式基於 Java 8 編寫實現。
因為 PBFT、Zilliqa 等共識協議在一些實現細節上缺少明確描述，我們在實現程式時進行了以下設定：
·節點之間的網路時延在 5-10 毫秒內
·網路頻寬設定為 100MB（假設每條請求訊息平均 100B 大小）
5.2.場景 1：節點均正常的橫向比較
首先在所有節點均為誠實節點的情況下，我們進行多組實測，橫向比較 PBFT、Zyzzyva、Zilliqa 共識協議在不同情況下的協議吞吐量、網路中平均訊息量、達成共識總時長等效能指標。
本場景的第 1 組測試條件為：
·批次大小= 10
·水位大小=30
·檢查點週期=10
·客戶端數量=1，訊息傳送間隔=1ms
橫向比較的結果（其中吞吐量和網路平均訊息量單位均為訊息筆數，下同）如下：
整體來看，BFT 類協議的吞吐量確實均會隨著節點數增加而下降（效能降低），當節點數量過多時，很難完成處理。
對於 PBFT 協議，可看到其訊息量和節點數量確實有平方級的關係（本例中約為6*n2）；
而 Zyzzyva 和 Zilliqa 的訊息量為線性關係，即以上協議的方法確實會降低PBFT 訊息量大的問題。
由於批次大小會影響網路中處理訊息的數量，因此我們在第 2 組觀察批次大小對效能的影響。測試條件為：
·節點數=22
·水位大小=30
·檢查點週期=10
·客戶端數量=1，訊息傳送間隔=1ms
從結果可以看出，增加批次大小對吞吐量均有較為明顯的提升，但也會增加網路中的訊息量。其中，Zilliqa 的吞吐量提升最為明顯，因為該演算法可以在一個單位時間內進行聚合簽名並且可以批次驗證，即批次大小相當於打包區塊的大小。所以當總頻寬允許的情況下，Zilliqa 演算法可以透過增加批次而獲取極大的吞吐量。
PBFT 和 Zyzzyva 提升到一定階段後在實測中會遇到瓶頸（批次數>30 後，吞吐量始終接近 1000），原因是本次測試客戶端訊息間隔導致。如果降低傳送間隔或者增加客戶端數量均可提高吞吐量。例如，當假設訊息可並行處理且沒有到達網路頻寬瓶頸，增加客戶端可得到如下 PBFT 的效能結果為：
5.3.場景 2：節點異常時的橫向比較
BFT 類協議的一個複雜之處在於部分節點存在拜占庭行為情況下的處理，各個協議對不同數量的異常節點，該情況下的效率可能也不一樣。
在本場景中我們設定節點數固定為 22 個。
本場景第 1 組測試設定條件為：
·批次大小=10
·水位大小=30
·檢查點週期=10
·客戶端數量=1
經過測試 PBFT、Zyzzyva、Zilliqa 的吞吐量分別為：
其中，可看到 PBFT 吞吐量和共識時間都優於 Zyzzyva 和 Zilliqa，是因為本次測試暫忽略了網路訊息量增大對訊息傳播延遲的影響。
從結果也可看到網路平均訊息量會減小，尤其是 PBFT 的訊息量會隨著節點增多而降低較快。其原因是當出現拜占庭節點時，作惡節點的訊息會被忽略掉；而同時，訊息傳播和達成共識的時間會相應延長。
5.4.場景 3：PBFT 測試研究
下面的幾個場景我們對比 PBFT 的批次、檢查點週期與吞吐量、網路中平均訊息量以及達成共識時間等效能表現之間的關係。
·節點數=22
·水位大小=50
可以看到，對於 PBFT 來說，檢查點週期調整對效能的影響並沒有太大；而調整批次大小則會較大程度上提高吞吐量指標、縮短共識時間，不過同時也會加大訊息量對網路造成壓力。
5.5.場景 4：Zyzzyva 測試研究
從上述場景已可看到，調整批次大小會對共識效能產生影響；而 Zyzzyva的主節點負責接收各客戶端發來的請求，因此在客戶端數量不同的情況下，表現可能也會不一樣。因此我們針對不同的批次大小和客戶端數量進行分析研究。
從結果可以看到，當批次數較小時，增加客戶端數量後，Zyzzyva 整體效能並沒有太大改觀。
當增大批次後，Zyzzyva 的吞吐量提高較為明顯；在增加客戶端數量後，吞吐量和共識時間均有改觀，但在增加一定程度後其表現並不會繼續提升。
另外和 PBFT 類似，增加客戶端數量或增大批次後，Zyzzyva 的網路訊息也會隨之增加。
5.6.場景 5：Zilliqa 測試研究
從場景 1 的測試中可看出，Zilliqa 的 Batch 可以設定的遠比 PBFT 大從而獲得極大的吞吐量，因此與前兩個縱向對比測試略有不同，本場景測試著眼點在網路頻寬消耗上。在不同 Batch 下，我們測試研究 Zilliqa 的消耗情況（以 PBFT 作為一個基準對比）。
測試條件為：
·節點數=22
·檢查點週期=10
·訊息大小=100B
可以看到，儘管可設定較大的批次數來獲得更高的吞吐量，但 Zilliqa 的最大頻寬消耗也會隨著批次數而線性增長。作為對比，PBFT 在批次數到達一定數量後，最大消耗頻寬會趨於穩定。因此在實際應用共識協議時，應充分考慮好選用的共識協議以及實際網路頻寬情況。
6. 參考資料
[1] M. van Steen and A. S. Tanenbaum, Distributed Systems, 3.01. 2017.
[2] S. Gilbert and N. Lynch, “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services,” ACM SIGACT News, 2002.
[3] S. Gilbert and N. Lynch, “Perspectives on the CAP Theorem,” Computer (Long. Beach. Calif)., vol. 45, no. 2, pp. 30–36, 2012.
[4] L. Lamport, R. Shostak, and M. Pease, “The Byzantine Generals Problem,”ACM Trans. Program. Lang. Syst., 1982.
[5] LoomNetwork, “瞭解區塊鏈的基本（第一部分）：拜占庭容錯(Byzantine Fault Tolerance),” 2018. [Online]. Available: https://segmentfault.com/a/1190000014009235.
[6] bangerlee, “[上篇] 大話分散式系統理論基礎.” [Online]. Available: https://mp.weixin.qq.com/s/p4PEZPjxJyYXKpkCCdShbw.
[7] 初夏虎, “拜占庭將軍問題深入探討,” 2015. [Online]. Available: https://www.8btc.com/article/70370.
[8] V. Buterin, “A Guide to 99% Fault Tolerant Consensus,” 2018. [Online]. Available: https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html.
[9] 袁煜明 and 胡智威, “【火線視點10】Vitalik的‘99%容錯共識演算法’解析.”
[10] D. Gupta, L. Perronne, and S. Bouchenak, “BFT-Bench: Towards a practical evaluation of robustness and effectiveness of BFT protocols,” in LectureNotes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2016.
[11] J. FAN, L.-T. YI, and J.-W. SHU, “Research on the Technologies of Byzantine System,” J. Softw., vol. 24, no. 6, pp. 1346–1360, 2014.
[12] M. Castro and B. Liskov, “Practical byzantine fault tolerance and proactive recovery,” ACM Trans. Comput. Syst., 2002.
[13] R. van Renesse and F. B. Schneider, “Chain Replication for Supporting High Throughput and Availability,” Proc. 6th Conf. Symp. Opearting Syst. Des. Implement. - Vol. 6, 2004.
[14] P.-L. Aublin, R. Guerraoui, N. Kne?evi?, V. Quéma, and M. Vukoli?, “The Next 700 BFT Protocols,” ACM Trans. Comput. Syst., vol. 32, no. 4, pp. 1–45, 2015.
[15] R. Guerraoui, N. Knezevic, V. Quema, and M. Vukolic, “Stretching BFT,” 2
010.
[16] A. Bessani, J. Sousa, and E. E. P. Alchieri, “State machine replication for the masses with BFT-SMART,” in Proceedings - 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2014, 2014.
[17] A. Clement et al., “Upright cluster services,” in Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles - SOSP ’09, 2009.
[18] Wikipedia, “Quorum (distributed computing).” [Online]. Available: https://en.wikipedia.org/wiki/Quorum_(distributed_computing).
[19] M. Abd-El-Malek, G. R. Ganger, G. R. Goodson, M. K. Reiter, and J. J. Wylie, “Fault-scalable Byzantine fault-tolerant services,” in Proceedings of thetwentieth ACM symposium on Operating systems principles - SOSP ’05, 2005.
[20] B. Bershad, D. ACM Digital Library., B. ACM Special Interest Group in Operating Systems., R. Rodrigues, and L. Shrira, “HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance,” Proc. 7th Symp. Oper. Syst. Des. Implement., p. 407, 2006.
[21] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong, “Zyzzyva: Speculative Byzantine Fault Tolerance,” Proc. Symp. Oper. Syst. Princ., pp. 45–58, 2007.
[22] A. Singh, P. Fonseca, and P. Kuznetsov, “Zeno: Eventually Consistent Byzantine-Fault Tolerance.,” Nsdi, pp. 169–184, 2009.
[23] T. Wood, R. Singh, A. Venkataramani, P. Shenoy, and E. Cecchet, “ZZ and the art of practical BFT execution,” in Proceedings of the sixth conference on Computer systems - EuroSys ’11, 2011.
[24] A. Shoker, J. P. Bahsoun, and M. Yabandeh, “Improving independence offailures in BFT,” in Proceedings - IEEE 12th International Symposium on Network Computing and Applications, NCA 2013, 2013.
[25] M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,” J. ACM, 1985.
[26] R. Kapitza et al., “CheapBFT: Resource-efficient Byzantine Fault Tolerance,” Proc. 7th ACM Eur. Conf. Comput. Syst., 2012.
[27] J. Hendricks, S. Sinnamohideen, G. R. Ganger, and M. K. Reiter, “Zzyzx: Scalable fault tolerance through Byzantine locking,” in Proceedings of the International Conference on Dependable Systems and Networks, 2010.
[28] A. Clement, E. Wong, L. Alvisi, M. Dahlin, and M. Marchetti, “Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults,” Symp. A Q. J. Mod. Foreign Lit., 2009.
[29] Y. Amir, B. Coan, J. Kirsch, and J. Lane, “Prime: Byzantine replication under attack,” IEEE Trans. Dependable Secur. Comput., 2011.
[30] G. S. Veronese, M. Correia, A. N. Bessani, and L. C. Lung, “Spin one’s wheels? Byzantine fault tolerance with a spinning primary,” in Proceedings of the IEEE Symposium on Reliable Distributed Systems, 2009.
[31] P. L. Aublin, S. Ben Mokhtar, and V. Quema, “RBFT: Redundant byzantine fault tolerance,” in Proceedings - International Conference on Distributed
[32] R. Pass and E. Shi, “Hybrid consensus: {Efficient} consensus in the permissionless model,” Leibniz {Int}. {Proc}. {Informatics}, {LIPIcs}, 2017.
[33] 姚前, 數字貨幣初探. 中國金融出版社, 2018.
[34] “Graphene Technical Documentation.” [Online]. Available: http://docs.bitshares.org/.
[35] “BitShares Whitepapers.” [Online]. Available: http://docs.bitshares.org/bitshares/papers/.
[36] “Steem Whitepaper.” [Online]. Available: https://steem.io/steem-whitepaper.pdf.
[37] “EOS.IO Technical White Paper v2.” [Online]. Available: https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.
[38] NEO, “A Byzantine Fault Tolerance Algorithm for Blockchain.” [Online]. Available: http://docs.neo.org/en-us/basic/consensus/whitepaper.html.
[39] “Cosmos Whitepaper.” [Online]. Available: https://github.com/cosmos/cosmos/blob/master/WHITEPAPER.md.
[40] 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.
[41] Z.-C. Lin, “Istanbul BFT (IBFT).” [Online]. Available: https://medium.com/getamis/istanbul-bft-ibft-c2758b7fe6ff.
[42] H. Hashgraph, “Hedera: A Governing Council & Public Hashgraph Network.” [Online]. Available: https://s3.amazonaws.com/hedera-hashgraph/hh-whitepaper-v1.1-180518.pdf.
[43] 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.
[44] T. Z. Team, “Zilliqa Technical Whitepaper,” Zilliqa, pp. 1–8, 2017.
[45] P. Li, G. Wang, X. Chen, and W. Xu, “Gosig: Scalable Byzantine Consensus on Adversarial Wide Area Network for Blockchains,” 2018.
[46] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich, “Algorand: Scaling byzantine agreements for cryptocurrencies,” Proc. 26th Symp. Oper. Syst. Princ., 2017.
[47] “VBFT演算法介紹.” [Online]. Available: https://github.com/ontio/documentation/blob/master/vbft-intro/vbft-intro-CN.md.
[48] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song, “The Honey Badger of BFT Protocols,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security - CCS’16, 2016.
[49] Juniway, “Honey Badger of BFT 協議詳解.” [Online]. Available: https://www.jianshu.com/p/15d5b6f968d9.
