前言

近日比原鏈（BYTOM）技術(shù)團(tuán)隊(duì)發(fā)布了Bystack區(qū)塊鏈BaaS平臺(tái)，其中包括側(cè)鏈的共識(shí)算法BBFT（Bystack Byzantine Fault Tolerance）。筆者將在這篇文章中闡述比原鏈BBFT嘗試解決的問(wèn)題以及分析BBFT與其他各家共識(shí)協(xié)議的主要差異。

BBFT是一個(gè)PBFT的變形，它的原理與PBFT一脈相承。若想深刻理解BBFT的巧思，則必須進(jìn)入PBFT的脈絡(luò)推敲。早在區(qū)塊鏈藉由比特幣的大紅大紫之前，PBFT就作為共識(shí)協(xié)議存在于世界上了。由Castro和Liskov于1999年發(fā)明，它是一個(gè)具有20年歷史的經(jīng)典設(shè)計(jì)，它的發(fā)明是為了解決分布式系統(tǒng)中的一個(gè)經(jīng)典問(wèn)題：拜占庭將軍問(wèn)題。直到今日，PBFT仍蘊(yùn)含許多值得反復(fù)推敲的巧思，不斷啟發(fā)后世發(fā)明出更好的協(xié)定。

PBFT基本的運(yùn)作流程

PBFT是一個(gè)具有二輪投票的三階段協(xié)議，每個(gè)視域（View）都會(huì)有一個(gè)特定的節(jié)點(diǎn)作為領(lǐng)導(dǎo)節(jié)點(diǎn)（Primary/Leader），負(fù)責(zé)通知所有節(jié)點(diǎn)進(jìn)入投票流程。各節(jié)點(diǎn)則會(huì)經(jīng)歷Pre-prepare/Prepare/Commit這三個(gè)階段，并依據(jù)接收的訊息決定是否投票/進(jìn)入下一階段，每個(gè)節(jié)點(diǎn)投完票后將訊息發(fā)給所有其他的節(jié)點(diǎn)。

若個(gè)節(jié)點(diǎn)在兩階段投票之后取得多數(shù)共識(shí)，則各節(jié)點(diǎn)可以更新本機(jī)的狀態(tài)，結(jié)束這一回合。視域變換（View-change）僅當(dāng)多數(shù)節(jié)點(diǎn)發(fā)起時(shí)執(zhí)行，當(dāng)目前的領(lǐng)導(dǎo)節(jié)點(diǎn)并未正常執(zhí)行任務(wù)時(shí)，這可以替換當(dāng)前的領(lǐng)導(dǎo)節(jié)點(diǎn)，保證協(xié)議正常運(yùn)作。

PBFT的特性

PBFT與中本聰共識(shí)（區(qū)塊鏈）有相當(dāng)不同的特性：PBFT是一個(gè)許可制的、基于領(lǐng)導(dǎo)節(jié)點(diǎn)的、基于通訊的、安全性重于活躍性的共識(shí)協(xié)定。

許可制的（Permissioned）：PBFT并非完全開(kāi)放的，這是由于PBFT需要讓節(jié)點(diǎn)能夠驗(yàn)證彼此的訊息以及精準(zhǔn)掌握節(jié)點(diǎn)的數(shù)量，區(qū)塊鏈則是屬于對(duì)任何人都開(kāi)放的非許可制（Permissionless）。

基于領(lǐng)導(dǎo)節(jié)點(diǎn)的（Leader-based）：也就是先決定領(lǐng)導(dǎo)節(jié)點(diǎn)（Leader），再由領(lǐng)導(dǎo)節(jié)點(diǎn)送出提議，這樣做最直接的好處就是不需要浪費(fèi)自己的運(yùn)算資源去爭(zhēng)取當(dāng)領(lǐng)導(dǎo)節(jié)點(diǎn)的機(jī)會(huì)，然而缺點(diǎn)就是只有在視域變換時(shí)才輪替領(lǐng)導(dǎo)節(jié)點(diǎn)，成為領(lǐng)導(dǎo)節(jié)點(diǎn)的機(jī)會(huì)并不公平，缺乏加入網(wǎng)絡(luò)的誘因；區(qū)塊鏈則是在多個(gè)提案中選擇工作證明難度最高的區(qū)塊作為共識(shí)，雖然這樣會(huì)造成運(yùn)算資源的浪費(fèi)，但是成為出塊者的機(jī)率大致是公平的，其與算力成正比。

基于通訊的（Communication-based）：PBFT的安全性奠基于3階段投票，雖然不必如工作證明般消耗大量計(jì)算資源，但數(shù)量龐大的通訊也造成可擴(kuò)展性的瓶頸——就算是號(hào)稱最實(shí)用的PBFT，也無(wú)法擴(kuò)展到1000個(gè)以上個(gè)節(jié)點(diǎn)。不僅如此，PBFT使用消息驗(yàn)證代碼（MAC），每投一輪票就需要每一個(gè)節(jié)點(diǎn)驗(yàn)證一次訊息，大量的簽名/驗(yàn)證也是另一個(gè)潛在的瓶頸。

安全性重于活躍性的（Safety over Liveness）：PBFT不論在何種網(wǎng)絡(luò)假設(shè)下（同步/異步）都能確保安全性，幾乎不可能出現(xiàn)分岔，因此具有實(shí)時(shí)敲定（Instant Finality）的特性；相對(duì)地，區(qū)塊鏈則是活躍性重于安全性，其安全性有賴于同步的網(wǎng)絡(luò)，而具有復(fù)數(shù)個(gè)共識(shí)（及分岔）的情況也相當(dāng)常見(jiàn)，需要經(jīng)過(guò)一定數(shù)量的區(qū)塊「確認(rèn)」才能保證其不再分岔的機(jī)率足夠大。

PBFT的問(wèn)題

首先，PBFT中的每個(gè)節(jié)點(diǎn)都需于每一輪投票中做n-n的通訊，假設(shè)n為1000，則每一次的共識(shí)都需要至少100，000次的通訊，盡管PBFT已經(jīng)是BFT家族當(dāng)中最實(shí)用的協(xié)議，這么巨量的通訊需求仍是擴(kuò)展的瓶頸。

如何提升效率？

· 聚合簽名

為了提升效率，一個(gè)直覺(jué)的思路是：避免n-n的通訊。我們可以指定網(wǎng)絡(luò)中的某節(jié)點(diǎn)作為協(xié)調(diào)者來(lái)發(fā)送/接收每個(gè)節(jié)點(diǎn)的投票，這樣每個(gè)節(jié)點(diǎn)都只需要向協(xié)調(diào)者發(fā)送訊息即可，從而避免了n-n的通訊。然而，在這樣的情境下，協(xié)調(diào)者有作惡的可能，因?yàn)閰f(xié)調(diào)者可以在未確實(shí)接收到指定數(shù)量的訊息前便執(zhí)行下一輪投票或者進(jìn)行狀態(tài)更新。

因此，我們可以使用門坎簽章（Threshold Signature）來(lái)保證協(xié)調(diào)者的正當(dāng)行為，門坎簽章的可以保證：需集合超過(guò)門坎數(shù)量（t-of-n）的簽章才有效。也就是說(shuō)，我們可以指定：唯有當(dāng)協(xié)調(diào)者集合 2f+1 個(gè)門坎簽章后，協(xié)調(diào)者才能帶著合法的簽名繼續(xù)推進(jìn)共識(shí)。Harmony FBFT便是一個(gè)使用聚合簽名以提升效率的BFT家族協(xié)議。

· 管線設(shè)計(jì)

每個(gè)內(nèi)容都必須經(jīng)過(guò)二輪投票/三個(gè)階段才能達(dá)成共識(shí)，如果有m個(gè)內(nèi)容就需要執(zhí)行2m次投票。管線設(shè)計(jì)（Pipelining）可以減少投票的次數(shù)，它的基本思路如下：讓每個(gè)節(jié)點(diǎn)在投第 i 輪的prepare階段時(shí)，同時(shí)也是對(duì)其前一個(gè)內(nèi)容 i-1 的commit階段投票。這樣做便可以節(jié)省對(duì)同一個(gè)內(nèi)容重復(fù)投票的冗余，大幅提升效率。這樣的思路首見(jiàn)于2018年發(fā)表的HotStuff協(xié)議。

· 只讓部分節(jié)點(diǎn)參與共識(shí)：最小生成樹(shù)

另外一種提高效率的方法，就是避免使所有的節(jié)點(diǎn)參與共識(shí)，這也正是比原鏈BBFT采取的作法。在BBFT中，節(jié)點(diǎn)分為三種：Consensus Node/Gateway Node/Leader Node，這些節(jié)點(diǎn)形成樹(shù)的結(jié)構(gòu)，樹(shù)為網(wǎng)絡(luò)中節(jié)點(diǎn)的最小生成樹(shù)（Minimal Spanning Tree），可能由分布式算法得出，或是由外部服務(wù)提供。樹(shù)葉的節(jié)點(diǎn)即為Consensus Node；樹(shù)根為L(zhǎng)eader Node；其他部分為Gateway Node。每種節(jié)點(diǎn)都有分別的任務(wù)：Consensus Node負(fù)責(zé)進(jìn)行投票；Gateway Node則不需參與投票，但必須負(fù)責(zé)聚合由Consensus Node送來(lái)的簽章；Leader Node負(fù)責(zé)與其他Leader Node交換訊息。BBFT的運(yùn)作流程如下圖所示，BBFT的共識(shí)過(guò)程，便是訊息由樹(shù)根向樹(shù)葉傳播再回到樹(shù)根的過(guò)程。

如何確保正確性（Safety and Liveness）？

在為PBFT帶入新技術(shù)以提升效率的同時(shí)，也必須確保協(xié)議本身的安全性與活躍性。接下來(lái)我們來(lái)看看，上述的協(xié)議是如何確保這兩者。

· 視域變換（View-change）

FBFT沿用了PBFT的視域變換，即在正常情況下并不更換領(lǐng)導(dǎo)節(jié)點(diǎn)，僅有當(dāng)超過(guò)2f+1個(gè)節(jié)點(diǎn)發(fā)起視域變換才會(huì)更迭領(lǐng)導(dǎo)節(jié)點(diǎn)。視域變換雖然本身是一個(gè)能夠替換作惡領(lǐng)導(dǎo)節(jié)點(diǎn)的機(jī)制，但它同時(shí)要求協(xié)議必須具有3個(gè)階段，才能保證協(xié)議的安全性（即不分岔）。

· 領(lǐng)導(dǎo)節(jié)點(diǎn)輪替（Rotating Leader）

HotStuff另一方面則引入了領(lǐng)導(dǎo)節(jié)點(diǎn)輪替的機(jī)制，在每個(gè)回合都更換領(lǐng)導(dǎo)節(jié)點(diǎn)，如此來(lái)回避視域變換高額的通訊成本。領(lǐng)導(dǎo)節(jié)點(diǎn)輪替也常見(jiàn)于許多BFT家族的協(xié)議，算是目前保障安全性機(jī)制的主流。

· 混合式（Hybrid）

比原鏈BBFT則取各家所長(zhǎng)，同時(shí)應(yīng)用了視域變換與領(lǐng)導(dǎo)節(jié)點(diǎn)輪替，等于是上了雙重保險(xiǎn)。

不過(guò)值得注意的是，目前的BBFT技術(shù)白皮書(shū)僅有一輪投票的模型，并未提出兩輪投票/三階段共識(shí)的模型。另外，領(lǐng)導(dǎo)節(jié)點(diǎn)輪替的順序也將基于各節(jié)點(diǎn)的權(quán)益（Stake），若節(jié)點(diǎn)出現(xiàn)違反協(xié)議的行為則該節(jié)點(diǎn)會(huì)遭受懲罰。

BBFT的挑戰(zhàn)

綜合以上的分析與比較，BBFT目前有幾個(gè)顯著的挑戰(zhàn)。首先，是最小生成樹(shù)的產(chǎn)生方式，如何同時(shí)兼顧去中心化與效率？其次是BBFT僅采取單輪投票作為共識(shí)，在引入視域變換的情況之下，可能會(huì)發(fā)生分岔，這樣的網(wǎng)絡(luò)也會(huì)遭受日蝕攻擊的威脅。最后，引入門坎簽章的前提下，勢(shì)必需要引入分布式私鑰生產(chǎn)協(xié)議（Distributed Key Generation）以共同生成私鑰，這部分于技術(shù)白皮書(shū)中尚未提及，卻是可能造成瓶頸的潛在因子。

結(jié)語(yǔ)

本篇文章簡(jiǎn)介了PBFT的特性及其效能問(wèn)題，并比較了FBFT/HotStuff/BBFT等協(xié)議針對(duì)效能問(wèn)題的解決思路，最后歸納出比原鏈BBFT的未來(lái)挑戰(zhàn)，希望能幫助讀者更理解BBFT的精髓。

作者：Juin Chiu，Unitychain 研究員 & Taipei Ethereum Meetup共同組織者，目前的研究領(lǐng)域?yàn)楣沧R(shí)協(xié)議/分片技術(shù)/自主身份等。