若想搞懂區塊鏈就不能忽視的經典:PBFT

在這篇文章中,筆者將介紹一個歷久不衰的經典:PBFT。它的全名為Practical Byzantine Fault Tolerance,誕生至今已逾20年。它的發明源於分散式系統中一個著名的共識難題:拜占庭將軍問題(Byzantine Generals Problem)。PBFT並不是一個針對全開放環境的共識協定 — 事實上在區塊鏈出現之前,並未出現任何一個針對開放環境的拜占庭容錯共識。區塊鏈的橫空出世啟發了研究人員再度審視PBFT這個經典。PBFT具有一些與區塊鏈截然不同的特性,這提供了改進區塊鏈一些有用的思路,例如以PBFT為基礎建立的權益證明(Proof-of-stake)模型。接下來的篇幅中,筆者將簡介PBFT的起源背景、共識運作、正確性證明,以及PBFT與區塊鏈不同的特性。

為什麼要發明PBFT?

人類自古以來便不斷追求可以永續運作的系統。一個永續的系統,首先要能夠容錯以避免因單一故障而停擺。一個實現容錯的直覺作法就是讓系統具有一定程度的冗余 — 讓有多個具有相同組成與狀態的個體同時運作,如此當故障發生時只需替換故障的個體便能保證系統繼續運作。在分散式系統中,我們稱這樣的設計為狀態機複製( State Machine Replication )。

什麼是狀態機?

狀態機是一個抽象的黑盒子,它具有初始狀態,並且在收到輸入後,能依據相應的轉換函數而轉換至新的狀態,且轉換的過程是決定性的( Deterministic ) — 只要給定相同的初始狀態及輸入,必定會得到相同的輸出。而由數個具有相同轉換函數的狀態機組成的系統即為狀態機複製。

為什麼需要共識?

由於狀態機具有決定性,為了使這些冗余的狀態機具有一致的狀態,每個狀態機都必須依相同的順序進行狀態轉換,因此每個狀態機必須達成對轉換順序的共識。這些狀態機組成一個網路,每個狀態機都是網路中的節點,節點與節點間僅能透過通訊交換訊息以達成共識。

為什麼共識這麼難?

在只依賴通訊便想達成共識的情境下,會碰到一個難解的問題,這也是在共識協定中一個著名問題:拜占庭將軍問題。

一群拜占庭將軍圍攻一座城市,他們必須達成同時進攻或同時撤退的共識,且各將軍只能透過信使將自己的決定通知其他人。然而,這群將軍中有叛徒,可能會發出相反的訊息干擾,或者只通知一部分的將軍。在已知有叛徒存在的情況下,該如何達成正確的共識?

顯然,狀態機複製的共識問題可以被化約成拜占庭將軍問題:

  • 節點就是將軍
  • 通訊就是信使
  • 進攻/撤退的決策就是需達成共識的內容
  • 將軍/狀態機的隨機行為稱為拜占庭錯誤( Byzantine Fault )
  • 叛徒/敵對狀態機存在的情形下仍能達成共識的特性便稱為拜占庭容錯( Byzantine Fault Tolerance )。

正確的共識:安全性( Safety )與活躍性( Liveness )

一個正確、可用的共識協定必須確保拜占庭將軍們一定會達成唯一的共識(安全性),且共識一定會形成(活躍性),關於安全性與活躍性筆者將於下文詳述。

共識一定可以達成嗎?

具備安全性與活躍性的共識一定可以達成嗎?答案是不一定。根據 FLP原理:在非同步的網路通訊及決定性的程序( Process )下,若出現任一個毀壞故障( Crash Fault ),則共識不可能同時具備安全性與活躍性。

那怎麼辦?有兩種方法可以繞過FLP原理的限制:第一種方法是假設網路通訊是同步的 — 這就是PBFT所採用的方式;第二種方法是在共識協定中引入一些隨機的因子,使整個協定變為非決定性的( Non-deterministic ),這樣做的優點是協定更強健,就算在非同步的網路通訊下依然可以運作,例如 Honey Badger BFT 就是一個非同步且非決定性的共識。

效能如何?

在 PBFT 出現前,曾出現許多不同的共識協定,但是效能都不夠好,直到 PBFT 的出現改變了一切,由其命名中的 P ( Practical ) 便能看出端倪。

PBFT如何運作?

PBFT 是一個具有拜占庭容錯的狀態機複製。欲解決拜占庭將軍問題,一個直覺的想法就是利用一輪或多輪的投票以獲得多數共識。然而,要由誰來發起投票?要投幾次票才能確保共識具有安全性與活躍性? PBFT 的創新在於三階段投票的設計,分為「就位」( Pre-prepare )、「預備」( Prepare )、「執行」( Commit )三個階段。

為了簡化問題,我們先做以下的假設:

假設

  • 只有4個將軍,最多能容忍1個叛徒(4 = 3f+1,f為能容忍叛徒數量,關於3f+1的意義,筆者將於下文的安全性分析詳述)。
  • 每個將軍都有編號(0~3)。
  • 每個將軍都能辨識彼此的簽名。
  • 每次行動都有一個序號( Sequence Number )
  • 進攻/撤退會組成一連串按序號排列的序列,例如:進攻 — 進攻 — 防守 — 進攻 — …。
  • 有一個主導者( Primary )和數個驗證者( Validator )。
  • 主導者分成不同代,主導者的代數稱為視域( View )。
  • 將軍們遵照循環制( Round-robin )輪流擔任主導者,例如:第1代主導者由編號1的將軍擔任,第2代主導者由編號2的將軍擔任,以此類推;第4代主導者由編號0的將軍再度擔任。
  • 有將軍主動發起輪替的提議時才會輪替主導者,該輪替機制稱為視域變換( View-change )。

第一階段:就位(Pre-prepare)

  • 主導者負責接收拜占庭君主( Client )的進攻/撤退命令( Request )
  • 由主導者負責發起提議,內容包含進攻或撤退( Message )、第幾代( View )、第幾次進攻( Sequence Number )。
  • 主導者透過信使發送附有自己簽名的「就位」訊息給其他驗證者。

PBFT Pre-prepare Phase

第二階段:預備(Prepare)

  • 各驗證者收到「就位」 訊息後需決定是否接受主導者的提議,若贊成提議則發送附有自己簽名的「預備」訊息給所有將軍;若不贊成則不發送任何訊息。
  • 發出「預備」訊息的驗證者開始「預備」階段。
  • 各將軍若收到3則以上「預備」訊息,則該將軍進入「已預備」( Prepared )狀態,這些「預備」訊息的集合統稱為「已預備證明」( Prepared Certificate )

PBFT Prepare Phase

第三階段:執行(Commit)

  • 「已預備」的將軍若決定執行,則發送附有簽名的「執行」訊息給所有將軍;若決定不執行則不發送任何訊息。
  • 發出「執行」訊息的將軍開始「執行」階段。
  • 各將軍若收到3則以上「執行」訊息,則執行訊息內容,這也代表該提議取得了共識。
  • 執行訊息後的將軍進入「已執行」狀態並將執行結果回報( Reply )給拜占庭君主。
  • 回報後的將軍結束這回合,靜待下一個提議的到來。

PBFT Commit Phase

可能有些讀者比較熟悉下面這個精簡版的流程圖:

PBFT Process

替換不適任的主導者:視域變換(View-change)

以上的共識形成的過程非常依賴忠誠的主導者,萬一主導者是叛徒呢?為了避免不提案的主導者癱瘓所有行動,將軍們需要一個輪替機制,也就是視域變換

  • 每個將軍從收到「預備」訊息後開始計時,轉為「已執行」狀態後結束計時。
  • 如果在計時後 T 時間內未執行訊息,則該將軍可以發送「變換」( View-change )訊息,訊息內容包含新的代數(目前代數+1 )以及其他重要訊息。
  • 如果主導者未提案,則每個誠實的驗證者最終都會因為超時而發出變換訊息。

 

  • 新主導者若收到3則以上「變換」訊息,則新主導者可以發送「新域」( New-view )訊息,訊息內容包含新代數、所有具有「已預備證明」且尚未被執行的「就位」訊息,以及其他重要訊息。
  • 各驗證者收到「新域」訊息後,逐一針對尚未執行的「就位」訊息進行投票流程。
  • 接下來由新主導者負責接收拜占庭君主的命令。

PBFT New-view

如何保證安全性與活躍性?

安全性

保證安全性即是保證每個將軍的對同樣的行動序號都有一致的行動。例如,假設序號 3 的內容是「進攻」,安全性保證:不會有任何將軍的序號 3 內容為「撤退」。

安全性與安全門檻 f 有關,若將軍總數為 3f+1,則最多能夠容許 f 個叛徒,因此所有預備/執行都必須取得 2f+1個將軍同意。如此若要使同一個序號產生兩個分歧的行動,則至少需要有 1 個好將軍同時同意兩個分歧的內容,這與好將軍的假設矛盾。

三階段流程也與安全性有關。為什麼不是兩階段而是三階段?設想一個只有兩階段投票的情境:假設將軍 2 於收集到「已預備證明」後便直接執行序號 6 的行動「進攻」,但將軍 3、將軍 4 由於信使延誤的關係而發起視域變換,因此將軍 2 也被迫跟著進行變換,由於將軍 3、將軍 4 並未收到序號 6 的行動,也因此序號 6 的內容不會被重新執行,新主導者會將序號 6 指派給下一個行動「撤退」,結果將軍 2 將會執行同為序號 6「進攻」與「撤退」,違反了安全性。因此第三階段 — 「執行階段」( Commit Phase )是必要的,唯有在將軍 2 確保將軍 3、將軍 4 都收集了序號 6 的「已預備證明」並回傳「執行」訊息的情況下才能執行序號 6 的內容。如此就算發生視域變換,也能保證序號 6 不再被重複指派不同內容,安全性因此獲得保證。

活躍性

保證活躍性即是保證行動不會因為停頓的主導者而中斷,而這仰賴於視域變換的運作。為了避開 FLP 原理的限制,PBFT 使用弱同步假設( Weak Synchrony ),即假設網路延遲的增長速度慢於每次超時增加的緩衝時間。如果在視域變換的過程中超時,則各將軍再發起一次變換,並延長等待時間至 2T/3T/4T…以此類推,直到等待時間可以容忍信使的延遲。在最壞的情況下,就算碰到連續 f 個叛徒,也能保證其活躍性。

PBFT的特性

PBFT 是一個許可制的、基於領袖的、基於通訊的、安全性重於活躍性的共識協定。這些特點跟我們知道的區塊鏈截然不同:

  • 許可制的( Permissioned ):PBFT 並非完全開放的,這是由於 PBFT 需要讓節點能夠驗證彼此的訊息以及精準掌握節點的數量,基於中本共識( Nakamoto Consensus )的區塊鏈則是屬於對任何人都開放的非許可制( Permissionless )。基於 PBFT 的權益證明( Proof-of-stake )模型則讓參與者可以依據自己的資產進行註冊,兼顧對所有人開放的特性又能善用註冊掌握驗證所需的資訊與節點總數。
  • 基於領袖的( Leader-based ):也就是先決定領袖( Leader ),再由領袖送出提議,這樣做最直接的好處就是不需要浪費自己的運算資源去爭取當領袖的機會,然而缺點就是只有在視域變換時才輪替領袖,成為領袖的機會並不公平,缺乏加入網路的誘因;區塊鏈則是在多個提案中選擇工作證明難度最高的區塊作為共識,雖然這樣會造成運算資源的浪費,但是成為出塊者的機率大致是公平的,其與算力成正比。近來的研究顯示:可以透過公平的亂數決定領袖,這樣既能保證成為領袖的機會公平,也能節省運算資源。然而怎麼保證亂數產生器是公平的?這是下一個大問題。
  • 基於通訊的( Communication-based ):PBFT 的安全性奠基於 3 階段投票,雖然不必如工作證明般消耗大量計算資源,但數量龐大的通訊也造成可擴展性的瓶頸 — 就算是號稱最實用的 PBFT ,也無法擴展到 1000 個以上個節點。不僅如此,PBFT 使用訊息驗證碼( MAC ),每投一輪票就需要每一個節點驗證一次訊息,大量的簽名/驗證也是另一個潛在的瓶頸。另一個潛在的問題是,基於通訊的模型是主觀的( Subjective ),對於遠程攻擊( Long-range Attack )沒有抵抗能力,新參與者無從分辨哪一個才是由誠實節點維護的狀態。相對地,區塊鏈是基於計算的( Computation-based ),它的安全性奠基於可驗證的計算證明,雖然在效率上不如基於通訊的作法,然而這樣模型卻是客觀的( Objective ),欲加入的新節點只需要根據中本共識( Nakamoto Consensus )選擇困難度最高的鏈加入即可。
  • 安全性重於活躍性的( Safety over Liveness ):PBFT 不論在何種網路假設下(同步/非同步)都能確保安全性,幾乎不可能出現分岔,因此具有即時敲定( Instant Finality )的特性;相對地,區塊鏈則是活躍性重於安全性,其安全性有賴於同步的網路,而具有複數個共識(及分岔)的情況也相當常見,需要經過一定數量的區塊「確認」才能保證其不再分岔的機率足夠大。

PBFT上可以發行密碼貨幣嗎?

綜合 PBFT 上述的特性:許可制、缺乏參與誘因、缺乏遠程攻擊的抗性、過高的通訊成本,我們無法在 PBFT 上建立一個完全去中心化而實用的密碼貨幣。然而,PBFT 可以作為權益證明的共識模型,而權益證明可以是非許可制的,並且能提供經濟激勵 — 例如 Ethereum Casper 就是一個結合基於計算與基於通訊模型的混合式模型,它由工作證明決定領袖,再由存入押金的驗證者( Validator )進行單輪投票以敲定共識。儘管目前有許多難題,但非常值得期待。

結語

儘管在區塊鏈蓬勃發展的今日,PBFT 這個經典仍然蘊含許多值得研究人員反覆推敲的巧思,其後續也衍生出非常多新協定,例如 Tendermint / HotStuff / Harmony FBFT 等等。看懂 PBFT 之後再回頭看其他貌似高深的協定,讀者肯定會覺得豁然開朗。


立即加入獲得最完整的金融科技資訊、區塊鏈新知、業界實例!