正文

正文

Lamport, Leslie. "The part-time parliament." ACM Transactions on Computer Systems (TOCS) 16.2 (1998): 133-169.

正文

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

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，激活主節點的服務操作。

m,，SIGNATURE

2. 當主節點Pi 接收任務請求m 後，啟動三階段的協議：

a. 序號分配（pre-prepare）階段：主節點選擇一個唯一的序列號seq 給任務請求m。主節點然後向所有的節點廣播以下消息

其中H 是一個哈希函數。一個節點Pj 接受以上的消息，如果以下的條件都滿足

i. 數字簽名SIGNATURE 有效

ii. Pj 尚未接受另一個含有相同v, seq 的另一任務請求

，SIGNATURE

iii. 序列號seq 在合理的範圍內b. 相互交互（prepare）階段：如果節點Pj 接受接受了主節點的廣播消息，那麼Pj 進入相互交互（prepare）階段並對所有的節點廣播以下消息c. 序號確認（commit）階段：對於節點Pj 來說，一個數組是準備好了的當且僅當Pj 收到了至少2t 個有效的消息

，SIGNATURE

。當數組

對Pj 來說是準備好了後，Pj 對所有的節點廣播以下確認消息：

當一個節點收到2t+1 個確認消息後，該節點將執行任務請求m 中所包含的任務，並將結果直接發送給客戶。

Yongge Wang. Byzantine Fault Tolerance in Partially Connected Asynchronous Networks

3. 客戶端等待來自不同節點的回复，若有t+1 個回復相同，則該回复即為運算的結果。

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

1. 在視圖v 的序號分配（pre-prepare）階段，主節點P1 把廣播消息「m,，SIGNATURE」發送給P1,P2, P3。但是不發給P4。，SIGNATURE」發送給P1,P2, P3。但是不發給P4。在相互交互（prepare）階段，節點P2, P3 會把廣播消息「，SIGNATURE」和「，SIGNATURE」和「

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

，SIGNATURE」和「

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

，SIGNATURE

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

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

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

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

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