PBFT 拜占庭協議安全性分析：不適合聯盟鏈或公鏈

作者：王永革教授，著名華裔密碼學家，北卡羅來納大學夏洛特分校 (UNC, Charlotte) 計算機系終身教授，德國海德堡大學獲得博士學位。

共識協議的設計一直是一個很具有挑戰性的課題。圖靈獎獲得者 Lamport 在 1989 年用古希臘帕克西島 (Paxos) 上的一羣業餘立法議員制定法律的過程描述了他所設計的可用於分佈式計算的 Paxos 共識協議。Lamport 將他的文章投給了 ACM TOCS。也許這個雜誌的編輯沒領會到該文章的重要性，所以一直沒同意發表。直到 Paxos 共識協議被學術界廣泛討論並被工業界廣泛應用，該雜誌纔在 1998 年發表了該文章：

Lamport,萊斯利。“兼職議會”。計算機系統上的ACM事務(TOCS) 16.2(1998): 133-169。

Lamport 自我調侃說這是他的所有文章中等待發表時間第二長的一篇文章。到目前爲止，Paxos 共識協議幾乎被使用於所有的分佈式系統。比如 Google 的 Bigtable 使用 Chubby lock service 系統來保證各個節點數據的一致性。而 Chubby lock service 就是基於 Paxos 協議的。此外，微軟，IBM，亞馬遜的雲服務系統都用 Paxos 協議爲其提供系統的一致性。粗略來講，Paxos 協議由一系列 ROUND 組成。ROUND 由 0 開始直到共識達成。每個 ROUND 分以下四步：

1. 主節點生成一個序列號，向所有節點廣播。希望大家參與該序列號的活動
2. 每個節點發給主節點以下信息：他所參與投過票的序列號和他投過的票
3. 主節點在收到第二步的大部分回覆後，選取一個不會違反 SAFETY 的數值 v。把這個值 v 廣播給所有的節點
4. 每個節點在收到主節點第三步的值 v 後，投票給 v 並向所有節點廣播他的投票

由於 Paxos 協議比較難於實現，斯坦福的研究者在 2014 年提出了模塊化的易於實現的 Paxos 協議，並將其命名爲 Raft 協議。Paxos/Raft 協議是在比較溫和的威脅模型裏工作的。換句話說，該協議只對異步網絡裏的非拜占庭錯誤具有魯棒性。在非拜占庭威脅模型裏，出錯的節點只能犯被動性的錯誤（比如停止工作）而不能展開具有主動進攻性的攻擊。具有 n 個節點的系統最多能容忍的非拜占庭錯誤節點數是（n-1）/2。Paxos/Raft 協議達到了這個最大的容錯節點數。

因爲 Paxos/Raft 協議對拜占庭錯誤不具有魯棒性，他們是無法在開放的網絡系統（比如區塊鏈系統）裏使用的。拜占庭錯誤是具有主動攻擊性的錯誤，比如：說謊，僞造消息，合謀攻擊，或者展開具有選擇性的 DoS 攻擊。我們在之前的文章中已經提到，去中心化的區塊鏈系統是基於開放的網絡系統的，所以我們必須使用拜占庭威脅模型。

目前市場上的區塊鏈裏使用最多的拜占庭協議是圖靈獎獲得者 Barbara Liskov 和她的學生 Castro 設計的實用拜占庭容錯系統 PBFT (practical BFT)。PBFT 被廣泛使用於聯盟鏈（比如 Hyperledger sawtooth 和趣鏈科技的 Hyperchain）和很多公鏈。PBFT 可以被看作是 Paxos 協議的拜占庭版本。其主要區別在於 PBFT 在 Paxos 協議中加入了一個驗證步驟來防止拜占庭錯誤。在分析其安全性之前，我們先給出其協議的形式化描述。

在 PBFT 協議中，我們假定有 n=3t+1 個節點 P1, …, Pn。其中最多 t 個節點被攻擊者所控制。PBFT 要求所有的節點共同維護一個狀態並採取一致的行動。PBFT 協議是通過一系列的視圖 (view) 來進行的。在每一個視圖裏，有一個節點被稱爲主節點 (leader)。PBFT 系統首先從視圖 (v=0) 開始，然後通過視圖更換協議進入視圖 v=1, v=2, …等等。只有在系統認爲主節點不能正常工作時，纔會啓動視圖更換協議進入下一個視圖。我們假定所有的節點都知道每一個視圖的主節點是誰。每當一個客戶提交一個任務給當前視圖的主節點後，PBFT 協議將進行三個階段的通信：序號分配（pre-prepare），相互交互（prepare），和 序號確認（commit）。序號分配（pre-prepare）階段對每個任務分配一個序列號，相互交互（prepare）和 序號確認（commit）階段對所有的任務提供一個全局的排序。假定我們現在在視圖 v，並且主節點是 Pi。那麼整個協議的過程如下：

1. 客戶端發送任務請求 m，激活主節點的服務操作。
2. 當主節點 Pi 接收任務請求 m 後，啓動三階段的協議：
a. 序號分配（pre-prepare）階段：主節點選擇一個唯一的序列號 seq 給任務請求 m。主節點然後向所有的節點廣播以下消息
m， <預準備，v, seq, H(m) >，簽名
其中 H 是一個哈希函數。一個節點 Pj 接受以上的消息，如果以下的條件都滿足
i. 數字簽名 SIGNATURE 有效
ii. Pj 尚未接受另一個含有相同 v, seq 的另一任務請求
iii. 序列號 seq 在合理的範圍內

b. 相互交互（prepare）階段：如果節點 Pj 接受接受了主節點的廣播消息，那麼 Pj 進入相互交互（prepare）階段並對所有的節點廣播以下消息

< 準備， V， seq， H （m）， Pj >， 簽名

c. 序號確認（commit）階段：對於節點 Pj 來說，一個數組<m, v, seq, Pj>是準備好了的當且僅當 Pj 收到了至少 2t 個有效的消息<PREPARE, v, seq, H(m), P>。當數組<m, v, seq, Pj>對 Pj 來說是準備好了後，Pj 對所有的節點廣播以下確認消息：

< 提交， V， seq， H （m）， Pj >， 簽名

當一個節點收到 2t+1 個確認消息後，該節點將執行任務請求 m 中所包含的任務，並將結果直接發送給客戶。
3. 客戶端等待來自不同節點的回覆，若有 t+1 個回覆相同，則該回復即爲運算的結果。

最近我們在如下文章中對 PBFT 的安全性進行了分析：

王Yongge。局部連接異步網絡中的拜占庭式容錯

該文章的分析結論是 PBFT 共識協議在異步網絡裏是不安全的。我們在本文，簡單的介紹我們設計的在異步網絡裏對 PBFT 協議的攻擊辦法。爲了簡化我們的描述，我們假定系統有 n=3+1=4 個節點 P1,P2, P3, P4。其中節點 P1 被攻擊者控制。另外我們假定視圖 v 的主節點是 P1。我們的攻擊在視圖 v 展開：

1. 在視圖 v 的序號分配（pre-prepare）階段，主節點 P1 把廣播消息「m, <PRE-PREPARE, v, seq, H(m) >，SIGNATURE」發送給 P1,P2, P3。但是不發給 P4。

2. 在相互交互（prepare）階段，P1 把廣播消息「<PREPARE, v, seq, H(m), P1>，SIGNATURE」發送給 P1,P2, P3。但是不發給 P4。在相互交互（prepare）階段，節點 P2, P3 會把廣播消息「<PREPARE, v, seq, H(m), P2>，SIGNATURE」和「<PREPARE, v, seq, H(m), P3>，SIGNATURE」發給所有的節點。當然了，如果可能，攻擊者也許會發起 DoS 攻擊，讓節點 P4 不會接受到節點 P2, P3 的廣播消息（這個 DoS 攻擊對我們的攻擊來講不是很重要）。到此時，數組<m, v, seq, Pj>對節點 P1,P2, P3 來說是準備好了。因爲 P4 最多收到了兩個相互交互消息，而我麼最少需要 2+1=3 個消息來準備好一個數組，所以對 P4 來說，該數組並沒有準備好。

3. 在序號確認（commit）階段，P1 把廣播消息「<COMMIT, v, seq, H(m), P1>，SIGNATURE」發送給 P1,P2。但是不發給 P4。在序號確認（commit）階段，節點 P2, P3 會把廣播消息「<COMMIT, v, seq, H(m), P2>，SIGNATURE」和「<PREPARE, v, seq, H(m), P3>，SIGNATURE」發給所有的節點。當然了，如果可能，攻擊者也許會發起 DoS 攻擊，讓節點 P4 不會接受到節點 P2, P3 的廣播消息（這個 DoS 攻擊對我們的攻擊來講不是很重要）。到此時，節點 P1,P2 收到了 3 個對任務 m 的確認消息。節點 P3 和 P4 最多收到 2 個對任務 m 的確認消息。所以節點 P2 將執行任務請求 m 中所包含的任務，並將結果直接發送給客戶。但是 P1,P3, P4 不會執行該任務。所以客戶收不到足夠的回覆。

在實行了以上的攻擊後，節點 P1 將不再回復任何視圖 v 的任何消息。所以系統將啓動視圖更換協議進入下一個視圖 v +1。在進入視圖 v +1 後，誠實節點的 P2,P3, P4 的內部數據狀態是不一樣的。所以系統進入了不協調的狀態。

在 PBFT 協議中，爲了解決有些節點可能會收不到某些消息（比如我們以上攻擊情景），PBFT 協議設計了 CHECKPOINT 狀態更新過程。特別的，每執行 100 個任務後，每個節點 Pj 會廣播其當前狀態的消息給所有的節點：

<檢查點，seq, H(狀態)，Pj >，簽名

如果一個節點 Pi 收到 2t+1 個如上的狀態更新消息，並且其狀態 state 的，那麼節點 Pi 將用如上消息裏的狀態 state 替換自己的當前狀態。在我們的如上攻擊中，如果不誠實的節點 P1 不發佈狀態更新消息，那麼 P2 發佈的狀態更新消息將不同於 P3 和 P4 發佈的狀態更新消息。因爲我們至少需要 2+1=3 個相同的狀態更新消息來更新一個節點的狀態，P2 的狀態是沒法更新到 P3 和 P4 的狀態的。所以系統將一直處於不協調狀態。

在以後的視圖裏，不誠實的節點 P1 可以和誠實的節點 P3，P4 合作共同執行客戶端的另一個任務請求。所以各個節點的狀態將進入不可恢復的不協調狀態。

在我們的前一篇文章裏，我們提到，在基於 Internet 的區塊鏈技術中，DoS 攻擊是很容易展開的。由於 Internet 是一個異步網絡，所以我們用以下模型來刻畫其網絡通信：

· 存在一個 Global Stabilization Time (GST)，在 GST 之前，任何消息可能丟失（比如 DoS 攻擊），或被重新排序。在 GST 之後，網絡變爲同步網絡。但是 GST 什麼時候開始，沒有人知道。

所以說，我們以上的攻擊在異步網絡的 GST 之前是可以展開的。那麼如果一個區塊鏈系統使用 PBFT 作爲其共識協議，我們以上的攻擊結果是什麼樣的？一般來說，在發起如上攻擊收，該區塊鏈系統首先會出現分叉，然後將進入死機狀態（也就是說，區塊鏈將沒有任何新的區塊可以生成）。特別的，加入在展開我們所描述的以上攻擊之前，大家達成共識的區塊鏈是：A→B→C→D。攻擊者用以上的攻擊方案，先讓 P2 決定下一個區塊是 E。也就是說在 P2 的記錄裏，當前區塊鏈是：A→B→C→D→E。但是 P3，P4 所記錄的當前區塊鏈仍然是 A→B→C→D。然後攻擊者 P1 讓節點 P3，P4 決定下一個節點爲 F。這樣在 P3，P4 的記錄裏，當前區塊鏈是：A→B→C→D→F。因爲區塊 E 不同於區塊 F。區塊鏈產生了分叉。由於下一個區塊必須有當前區塊鏈延伸出去。如果節點從現在開始不在參與任何活動，那麼系統沒發得到最小的投票數 2+1=3。所以沒有新的區塊可以生成。綜合起來，我們在本文的分析結論是：PBFT 共識協議沒法保證區塊鏈系統的安全性（safety）和活性（liveness）需求。所以我們建議，不論是聯盟鏈或公鏈，都不應該用 PBFT 做爲其共識協議。

歡迎加入律動 BlockBeats 官方社群：

Telegram 訂閱群：https://t.me/theblockbeats

Telegram 交流群：https://t.me/BlockBeats_App

Twitter 官方帳號：https://twitter.com/BlockBeatsAsia