PBFT論文完整重點筆記

d3centralizedPosted onin未分類
分享

內容目錄

1. 核心概念與目的

PBFT（Practical Byzantine Fault Tolerance）是一個能夠容忍拜占庭錯誤的實用共識演算法，由MIT的Miguel Castro和Barbara Liskov在1999年提出。這個演算法設計來解決分散式系統中節點可能出現任意錯誤（包括惡意攻擊或軟體錯誤）的問題，同時保證系統仍能正確運作。

想像一個班級要決定班遊地點，但班上可能有幾個同學會亂投票或說謊。PBFT就像是一套投票規則，確保即使有幾個搗蛋的同學，全班還是能做出正確的決定。

2. 系統模型與假設

2.1 拜占庭錯誤模型

論文採用拜占庭錯誤模型，意思是故障節點可能表現出任意行為——可能停止工作、發送錯誤訊息，甚至故意搗亂。這比一般只考慮節點當機的故障模型更嚴格，因為惡意節點會主動攻擊系統。

一般故障就像考試時有人睡著不寫；拜占庭錯誤則像有人故意在答案卷上亂寫，甚至偷看別人答案後故意寫錯，試圖讓老師無法判斷正確答案。

2.2 非同步網路環境

PBFT運作在非同步系統中，不依賴網路訊息傳遞時間的上限假設。這意味著演算法不會因為網路延遲就判斷節點故障，避免被攻擊者利用網路延遲來破壞系統。

2.3 最少節點數量要求

系統至少需要3f+1個副本節點才能容忍f個錯誤節點。

為什麼需要這麼多節點？

因為系統必須在 n－f 個節點回應後就能繼續運作（因為 f 個節點可能故障不回應）。但在 n－f 個回應中，可能有 f 個是來自故障節點的錯誤回應。所以正確節點的回應必須超過錯誤節點：n－2f > f，因此n > 3f。

如果班上有12個同學，最多能容忍3個搗蛋的（12=3×3+3）。當9個人投票時，即使其中3個是亂投的， 還有6個正確投票，仍能確保多數正確。

3. 演算法核心機制

3.1 視圖（View）與主節點（Primary）

系統運作在一系列稱為「視圖」的配置中，每個視圖有一個主節點（primary）和多個備份節點（backup）。視圖按順序編號，主節點透過公式p = v mod |R|決定，其中v是視圖編號。

視圖就像輪流當班長的制度。第0週0號同學當班長，第1週1號同學當班長，依此類推。如果發現班長不做事，就進行「視圖變更」換下一個班長。

3.2 三階段協議（Three-Phase Protocol）

這是PBFT最核心也最複雜的部分,包含預準備(pre-prepare)、準備(prepare)、提交(commit)三個階段。

3.2.1 預準備階段(Pre-prepare)

當主節點收到客戶端請求時,會分配一個序號 n 給這個請求,然後向所有備份節點廣播預準備訊息。預準備訊息包含視圖編號 v 、序號 n 和請求的摘要 d。

備份節點接受預準備訊息的條件:

  • 簽章正確且摘要與請求相符
  • 目前在視圖v中
  • 沒有接受過相同視圖v和序號n但不同摘要的預準備訊息
  • 序號在低水位 h 和高水位 H 之間

主節點(班長)收到「要不要訂飲料」的提案,給它編號5號,然後告訴大家「5號提案是訂飲料」。其他同學檢查:班長沒說謊(簽章正確)、確實是這一輪(視圖 v)、5號提案沒被用過、編號在合理範圍內。

3.2.2 準備階段(Prepare)

如果備份節點接受預準備訊息,就進入準備階段,向所有其他節點廣播準備訊息,內容包含視圖 v、序號 n、摘要 d 和節點編號 i。

當節點i的日誌中有請求 m、m 的預準備訊息(視圖 v 、序號 n )、以及2f個來自不同備份節點且符合預準備的準備訊息時,謂詞prepared(m,v,n,i)為真。

關鍵不變式:如果prepared(m,v,n,i)為真,則prepared(m’,v,n,j)對任何非故障節點j和任何m’≠m都為假。這確保了同一視圖中,不同非故障節點對相同序號的請求達成一致。

每個同學收到「5號提案是訂飲料」後,向全班廣播「我同意5號是訂飲料」。當某個同學收到至少2f個這樣的同意訊息時,他就知道「大家都認為5號是訂飲料」這件事已經準備好了。

為什麼需要 2f 個準備訊息:因為總共3f+1個節點,主節點發出預準備,需要2f個備份節點的準備訊息,加上主節點自己,共2f+1個節點確認。即使f個節點故障,至少還有f+1個正確節點確認。

3.2.3 提交階段(Commit)

當prepared(m,v,n,i)變為真時,節點i向其他節點廣播提交訊息。

當prepared(m,v,n,i)為真且節點i收到2f+1個符合預準備的提交訊息時,謂詞committed-local(m,v,n,i)為真。此時節點i可以執行請求m。

關鍵不變式:如果committed-local(m,v,n,i)對某非故障節點i為真,則committed(m,v,n)為真,意即至少f+1個非故障節點已經prepared。這確保了即使視圖變更,請求m仍會被執行。

當同學確認「5號是訂飲料」後,再廣播「我承諾執行5號提案」。收到2f+1個承諾後,就可以真正執行——去訂飲料了。

為什麼需要提交階段:預準備和準備階段確保同一視圖內的順序一致;提交階段確保跨視圖的順序一致。如果沒有提交階段,視圖變更時可能無法保證所有節點對已執行請求的共識。

3.3 客戶端操作流程

客戶端向主節點發送請求,然後等待收到f+1個來自不同節點、具有相同結果的回覆。因為最多f個節點可能故障,f+1個相同回覆保證至少有一個來自正確節點,因此結果正確。

如果客戶端沒有及時收到回覆,會向所有節點廣播請求;如果是主節點故障,最終會觸發視圖變更。

4. 視圖變更協議(View Change)

4.1 觸發條件

當備份節點等待執行請求超時時,會啟動視圖變更進入視圖v+1。節點停止接受訊息(除了檢查點、視圖變更和新視圖訊息),並向所有節點廣播視圖變更訊息。

如果班長遲遲不處理提案,其他同學等太久就會發起罷免,推選下一個班長。

4.2 視圖變更訊息內容

視圖變更訊息包含:

  • n: 最後穩定檢查點的序號
  • C: 證明檢查點正確性的2f+1個檢查點訊息
  • P: 所有在節點i上prepared且序號大於n的請求集合,每個請求包含預準備訊息和2f個準備訊息

4.3 新視圖訊息生成

新視圖v+1的主節點收到2f個有效的視圖變更訊息後,廣播新視圖訊息。新視圖訊息包含:

  • V: 收到的視圖變更訊息集合
  • O: 新生成的預準備訊息集合

主節點計算O的方式:

  1. 確定V中最新穩定檢查點的序號min-s和準備訊息中最高序號max-s
  2. 對min-s到max-s之間每個序號n,如果V中有請求在該序號prepared,則用該請求的摘要創建新預準備;否則創建空請求(null request)的預準備

詳細說明:空請求是一個特殊請求,執行時不做任何操作(no-op),用於填補序號空缺,確保序號連續性。

新班長收到大家的報告後,整理出「哪些提案已經有共識但還沒執行」。如果某個編號的提案大家有共識,就繼續執行;如果某個編號沒有提案,就插入一個「跳過」的空提案,保持編號連續。

4.4 活性保證

論文採用三個機制確保活性:

  1. 節點發出視圖變更訊息後等待時間T;如果超時未收到新視圖訊息或未執行新請求,則發起下一輪視圖變更,等待時間加倍為2T,呈指數增長
  2. 如果節點收到f+1個視圖更大的視圖變更訊息,即使自己的計時器未超時也發送視圖變更訊息
  3. 故障節點無法阻礙進展:因為主節點按v mod |R|輪流,故障主節點不會連續超過f個視圖

5. 垃圾回收與檢查點機制

5.1 檢查點生成

每當執行序號能被某常數(如100)整除的請求時,節點生成檢查點。節點廣播檢查點訊息,包含序號n和狀態摘要d。

當節點收集到2f+1個相同序號n和摘要d的檢查點訊息時,該檢查點變為穩定檢查點。

每處理100個提案就存檔一次遊戲進度。當至少2f+1個玩家都存到相同進度時,這個存檔就是「穩定的」,之前的紀錄可以清掉了。

5.2 水位標記(Water Marks)

低水位h等於最後穩定檢查點的序號;高水位H=h+k,其中k足夠大以避免節點停滯。節點只接受序號在h和H之間的訊息。

作用:防止故障主節點用極大的序號耗盡序號空間,也限制日誌大小。

6. 重要優化技術

6.1 訊息認證碼(MAC)取代數位簽章

正常運作時使用MAC進行訊息認證,僅在視圖變更時使用數位簽章。MAC計算速度比RSA簽章快三個數量級(約1000倍)。

技術細節:每個節點與其他節點共享16位元組的密鑰,使用MD5計算MAC,並取10位元組作為認證碼。訊息包含認證器(authenticator),為每個其他節點計算一個MAC形成向量。

6.2 降低通訊成本的優化

  1. 減少回覆大小:客戶端指定一個節點發送完整結果,其他節點只發送結果摘要
  2. 試探性執行(Tentative Execution):當prepared為真時就執行請求並發送試探性回覆,減少一輪訊息延遲(從5降到4)
  3. 唯讀操作優化:唯讀請求直接廣播給所有節點,節點在試探性狀態執行並回覆,客戶端等待2f+1個相同結果即可,只需一輪訊息

6.3 檢查點維護的寫時複製技術

使用512位元組區塊的寫時複製位元,當產生新檢查點時設定所有位元。修改區塊時,如果寫時複製位元為1,先保存舊內容到檢查點記錄,再寫入新值並清除位元。

效益:Andrew基準測試中,平均檢查點記錄只有182個區塊,最多500個,空間和時間開銷低。

6.4 增量雜湊(Incremental Hashing)

使用AdHash計算檢查點狀態摘要。將狀態分成固定大小區塊,每個區塊的雜湊值是區塊索引與區塊值的串接經MD5運算,狀態摘要是所有區塊雜湊值的和(模某大整數)。

維護一個表記錄每個區塊的雜湊值,產生檢查點時只需重新計算修改過的區塊雜湊值,更新總和即可。

7. 處理非確定性

狀態機副本必須是確定性的,但許多服務涉及非確定性(如NFS的時間戳記)。

解決方法:主節點選擇非確定性值,將值與請求串接後執行三階段協議,確保所有非故障節點對值和序號達成共識。副本必須能確定性地判斷值是否正確。

如果副本需要參與選值,可增加一個階段:主節點收集2f+1個備份提議的值,串接後執行三階段協議,副本用確定性計算(如取中位數)選擇最終值。

8. 實作與效能評估

8.1 BFS實作架構

論文實作了BFS(Byzantine-fault-tolerant File System),一個支援NFS V2協定的容錯檔案系統。使用記憶體映射檔案儲存檔案系統,作業系統管理快取並非同步寫入磁碟。

8.2 微基準測試結果

對於0位元組參數和結果的空操作:

– 讀寫操作延遲3.35毫秒,相較無複製版本0.82毫秒,額外開銷309%

– 唯讀操作延遲1.62毫秒,額外開銷98%

– 運算開銷約1.06毫秒(含0.55毫秒密碼學運算),通訊開銷1.47毫秒

8.3 Andrew基準測試結果

BFS相較標準NFS實作只慢3%,證明實用性。相較無複製版本(BFS-nr),完整基準測試額外開銷26%;若對lookup操作應用唯讀優化,開銷降至20%。

效能優勢來源:BFS透過複製達成穩定性,NFS標準實作需同步寫入磁碟;在有同步操作的階段(1、2、5),BFS反而比標準NFS快。

8.4 相較於前人工作的改進

相較Rampart,PBFT將延遲降低10倍以上(讀寫操作)和20倍以上(唯讀操作)。Rampart和SecureRing依賴同步假設,攻擊者可透過延遲正確節點來破壞安全性;PBFT不依賴同步假設保證安全性,更能抵抗攻擊。

9. 安全性與活性證明

9.1 安全性證明關鍵

論文證明如果prepared(m,v,n,i)為真,則prepared(m’,v,n,j)對任何非故障節點j和m’≠m為假。這基於|R|=3f+1和需要至少f+1個非故障節點prepared的事實。

視圖變更協議確保跨視圖的一致性:如果請求m在視圖v中committed,則視圖v’>v的新視圖訊息會包含至少一個非故障節點k的視圖變更訊息,該訊息確保m prepared的事實被傳播。

9.2 活性保證條件

演算法不依賴同步假設保證安全性,但依賴弱同步假設保證活性:delay(t)不會無限快於t增長。這避免了非同步系統無法實現共識的不可能結果。

10. 總結與貢獻

PBFT論文的重大貢獻包括:

  1. 首個在非同步網路中正確存活拜占庭錯誤的狀態機複製協議
  2. 多項重要優化使演算法效能足以實用
  3. 實作拜占庭容錯分散式檔案系統並提供效能量化數據

實際意義:PBFT能夠容忍軟體錯誤導致的故障,特別是非確定性錯誤,這些錯誤最難偵測且持續存在。論文甚至提到在執行系統時遇到軟體錯誤,演算法仍能正確運作。

未來展望:論文提出可用witness副本減少資源需求,以及可能將狀態副本數減少到f+1等改進方向。

11. Q&A

11.1 備份節點在接受訊息時，是怎麼驗證簽章？

論文使用兩種認證方式:​

1. 數位簽章(用於視圖變更訊息)

驗證方式:每個節點都知道其他所有節點的公鑰。當節點i收到聲稱來自節點j的訊息m時,會用節點j的公鑰驗證附在訊息上的簽章。如果簽章有效,就確認訊息確實來自節點j且未被篡改。​

論文使用RSA數位簽章:簽署時用私鑰加密訊息摘要(MD5),驗證時用公鑰解密並比對摘要。​

2. 訊息認證碼MAC(用於正常運作訊息)

驗證方式:每個節點與其他每個節點都共享一個16位元組的密鑰。訊息包含一個「認證器」,實際上是一個MAC向量,為每個其他節點計算一個MAC。​

接收節點用自己與發送者共享的密鑰,重新計算訊息的MAC,並與收到的MAC比對。如果相符,就確認訊息來自聲稱的發送者且未被篡改。​

數位簽章就像用你的私章蓋印,任何人都能用對應的「公章模板」驗證是不是你蓋的;MAC則像是你跟每個朋友約定一個暗號,只有你們兩人知道,收到訊息時用暗號確認是朋友發的。

11.2 「視圖內的順序一致」是指什麼順序？

「視圖內的順序一致」是指在同一個視圖中,所有非故障節點對於哪個請求被分配到哪個序號達成一致。​

詳細說明:
主節點為每個請求分配一個序號(sequence number),這個序號決定請求的執行順序。預準備和準備階段確保,即使主節點是惡意的,在同一視圖v中,不會有兩個不同的請求m和m’被分配到相同的序號n。​

論文的不變式說明:如果prepared(m,v,n,i)為真,則prepared(m’,v,n,j)對任何非故障節點j和任何m’≠m都為假。意思是,在視圖v中,所有正常節點都同意「序號n對應的是請求m」。​

想像班上要處理很多提案,每個提案給一個編號決定處理順序。「視圖內順序一致」就是確保所有正常同學都同意「5號是訂飲料提案,6號是訂便當提案」,不會有人認為5號是訂便當。

11.3 視圖變更訊息內容為什麼沒有包含committed與committed-local?

因為視圖變更只需要傳播「prepared」的資訊就足夠保證安全性。​

詳細解釋:

  • Prepared的定義:節點i有請求m的預準備、以及2f個匹配的準備訊息​
  • Committed的定義:至少f+1個非故障節點已經prepared​
  • Committed-local的定義:節點i已經prepared且收到2f+1個提交訊息​

視圖變更訊息包含P集合,其中包含所有在該節點prepared的請求及其證明(預準備+2f個準備訊息)。

為什麼prepared就夠了:
當新主節點收集2f個視圖變更訊息時,如果某個請求m在舊視圖v中committed(意即至少f+1個非故障節點prepared),則在這2f個視圖變更訊息中,至少有一個來自prepared了m的非故障節點。因為總共3f+1個節點,f+1個非故障節點prepared了m,2f個發送視圖變更的節點,兩者必定至少交集一個非故障節點。​

班長換人時,新班長只需要知道「哪些提案已經獲得足夠同意」(prepared),不需要知道「誰已經承諾執行」(committed)。因為只要有足夠同意,新班長就會讓大家繼續處理這個提案,最終一定會完成。

11.4 活性保證中提到「自己的計時器未超時」是指什麼計時器?

這是指備份節點等待請求執行的計時器。​

詳細機制:
當備份節點收到有效請求且尚未執行時,稱為「正在等待執行該請求」。節點在收到請求時啟動計時器(如果還沒在運行)。當請求執行完畢時停止計時器,但如果此時還有其他請求在等待,就重新啟動計時器。​

觸發視圖變更的兩種情況:​

  1. 計時器超時:如果計時器在視圖v中到期,備份節點會發起視圖變更進入視圖v+1​
  2. 收到f+1個更高視圖的視圖變更訊息:即使自己的計時器還沒到期,也會發送視圖變更訊息(針對收到訊息中最小的視圖)​

第二種機制確保節點不會「太晚」發起視圖變更——如果其他節點已經開始換視圖,自己也該跟上。​

計時器就像「等待班長處理提案的耐心」。如果等太久,就發起罷免換班長。但如果看到很多同學已經在發起罷免(收到f+1個視圖變更訊息),即使自己還有耐心,也會一起參與罷免,避免落後。

11.5 Copy-on-Write 的簡單比喻

Copy-on-Write(寫時複製)就像「拍照存檔前先做記號,修改時才備份」。​

運作方式:​

  1. 拍照時(產生檢查點):系統為所有512位元組的區塊設定一個「寫時複製位元」,並建立空的檢查點記錄​
  2. 修改資料時:要寫入某區塊前,先檢查寫時複製位元​
    • 如果位元是1(表示這區塊自上次檢查點後沒改過),就把舊內容複製到檢查點記錄中,然後寫入新值,並清除位元為0​
    • 如果位元是0(已經備份過),直接寫入新值​

想像你有一本筆記本(系統狀態),每天晚上要存檔。傳統方式是整本複印一份,很花時間。Copy-on-Write的做法是:晚上存檔時,只在每一頁夾一張標籤紙(寫時複製位元);隔天要修改某頁時,先檢查有沒有標籤紙,如果有,就先影印那一頁(放到檢查點記錄),然後拿掉標籤紙再修改。這樣只需要複印真正改過的頁面,省下大量時間和空間。​

效益: 論文實驗中,平均每次檢查點只需備份182個區塊,最多500個,相比整個檔案系統,空間和時間開銷非常低。

11.6 「視圖變更協議確保跨視圖一致性」的簡單比喻

這句話的意思:如果某個請求m在舊視圖v中已經committed,那麼在新視圖v’中,新主節點會從視圖變更訊息中得知這件事,並確保m繼續被處理,序號不變。​

想像班上換班長(視圖變更)。舊班長時期,「5號提案-訂飲料」已經有足夠多人同意(committed),但還沒執行就換班長了。

新班長上任時,會向大家收集工作報告(視圖變更訊息)。因為之前至少f+1個正常同學已經對「5號訂飲料」達成共識(prepared),而新班長收集2f個報告,這兩組人一定有至少一個正常同學重疊(因為總共3f+1個同學)。​

這個重疊的同學會在報告中告訴新班長「5號是訂飲料且已經有共識」。新班長看到後,會繼續讓大家處理「5號訂飲料」這個提案,保持序號5不變,確保不會換成別的提案。​

11.7 Witness副本是什麼?

Witness副本(見證副本)是一種輕量級副本,不儲存完整狀態,只在正常副本故障時參與協議。​

論文在結論中提到,未來可以用witness副本減少資源需求。正常情況下,只有完整副本參與協議並儲存狀態;當某個完整副本故障時,witness副本才被啟動參與協議。​

優勢:

  • 減少儲存成本:witness不需要儲存完整的服務狀態​
  • 維持容錯能力:仍然能提供相同的拜占庭容錯保證​

正常情況下,班上有4個同學(完整副本)處理提案並記錄所有資訊。另外有2個同學是「候補」(witness),平常不用記錄資訊,只在有正式同學缺席時頂替參與投票。這樣可以節省記憶負擔,又能維持容錯能力。​

注意: 論文只提出這個概念,並未實作或提供詳細設計。​

11.8 「狀態副本數減少到f+1」是指什麼?

「狀態副本數減少到f+1」是指只有f+1個節點儲存完整的服務狀態,而不是所有3f+1個節點都儲存。​

目前PBFT中,所有3f+1個節點都是完整副本,都儲存服務的完整狀態。但實際上,只要f+1個節點有完整狀態,就能保證至少有一個非故障節點擁有正確狀態(因為最多f個故障)。​

其餘2f個節點可能只儲存部分資訊或使用其他方式參與協議,減少儲存需求。這與witness副本的想法類似,但更激進——連參與協議的節點也不全部儲存狀態。​

論文提到「我們相信有可能做到,但細節還需要研究」。主要挑戰是如何設計協議,讓沒有完整狀態的節點仍能參與共識過程並驗證請求正確性。​

目前12個同學(假設3f+1=10,算錯了,應該是10個)每人都有完整的班級活動記錄本。「狀態副本數減少到f+1」的想法是:只有4個同學(f+1,f=3)保存完整記錄本,其他6個同學只保存重要摘要或索引,但仍然參與投票。這樣可以大幅減少儲存空間,又能維持決策能力。

11.9 備份節點何時會收到有效請求？

備份節點收到有效請求有兩個主要時機:​

時機一:主節點廣播預準備訊息時

正常情況下,客戶端首先向主節點發送請求訊息。主節點收到後,立即啟動三階段協議,向所有備份節點廣播預準備訊息(PRE-PREPARE),並將客戶端的原始請求m附帶在預準備訊息中。​

詳細流程:​

  1. 客戶端c發送請求訊息 ⟨REQUEST, o, t, c⟩ 給主節點p
  2. 主節點p分配序號n,廣播 ⟨PRE-PREPARE, v, n, d⟩_p, m 給所有備份節點,其中m是客戶端的請求訊息​
  3. 備份節點從預準備訊息中收到客戶端請求m​

驗證條件:備份節點接受預準備訊息(連同其中的請求m)需要滿足以下條件:​

  • 請求和預準備訊息的簽章或認證碼正確
  • 摘要d確實是請求m的摘要
  • 備份節點目前在視圖v中
  • 沒有接受過相同視圖v和序號n但不同摘要的預準備訊息
  • 序號n在低水位h和高水位H之間

時機二:客戶端超時後廣播請求時

異常情況下,如果客戶端在發送請求後沒有及時收到足夠回覆,會懷疑主節點可能故障,於是向所有副本節點(包括主節點和所有備份節點)廣播請求。​

詳細流程:​

  1. 客戶端等待f+1個相同結果的回覆超時
  2. 客戶端廣播請求給所有節點
  3. 備份節點直接收到客戶端的請求訊息

備份節點的處理方式:​

  • 如果請求已經處理過:備份節點直接重新發送之前的回覆(節點會記住發給每個客戶端的最後一個回覆)​
  • 如果請求還沒處理:備份節點將請求轉發(relay)給主節點​
  • 如果主節點不將請求廣播給群組:最終會有足夠多的備份節點懷疑主節點故障,觸發視圖變更​

何謂「有效」請求?

有效請求必須滿足:​

  • 請求的簽章或認證碼正確,確認來自合法客戶端
  • 客戶端有權限執行該操作(通過存取控制驗證)
  • 請求的時間戳t大於該客戶端上次執行請求的時間戳(避免重放攻擊)​

何時啟動計時器?

論文提到「備份節點在收到有效請求且尚未執行時,會等待執行該請求」。具體來說:​

  • 備份節點收到有效請求時啟動計時器(如果計時器還沒運行)​
  • 當請求執行完畢時停止計時器
  • 如果此時還有其他請求在等待執行,則重新啟動計時器​
  • 如果計時器在視圖v中到期,備份節點會發起視圖變更進入視圖v+1​

主節點就像班長,收到提案後應該告訴全班同學(預準備訊息)。但如果班長擺爛不通知,提案人(客戶端)等太久就會自己向全班廣播提案。其他同學收到後,如果發現確實沒處理過,就提醒班長該做事了;如果班長還是不做,大家就罷免他換人當。

11.10 為何視圖變更不需保存committed訊息，只基於R集合與R2集合必定有交集？

想像班級要換班長(視圖變更):

情境:舊班長時期,「5號提案-訂飲料」已經committed,意思是至少f+1=4個正常同學都準備好處理這個提案(prepared),但可能還沒全部執行完。​

新班長上任:新班長向全班收集工作報告(視圖變更訊息),收到2f=6份報告。​

交集保證:因為之前至少4個正常同學prepared了「5號訂飲料」,而現在6個同學交報告,全班只有7個正常同學(2f+1),所以這6個交報告的同學中,至少有一個正常同學(k同學)之前prepared了「5號訂飲料」。​

為什麼prepared就夠:k同學的報告會包含「5號是訂飲料」的完整證明(預準備+2f個準備訊息),新班長看到後就知道「5號必須是訂飲料,不能換成別的提案」。​

不需要committed訊息:新班長不需要知道「有多少人已經承諾執行」(committed)或「誰已經執行完」(committed-local),只需要知道「哪些提案有共識」(prepared)就足夠,因為有共識的提案必須繼續處理,最終一定會完成。