論文: Practical Byzantine Fault Tolerance

PBFT及其變種在區(qū)塊鏈共識算法中有很廣泛的應(yīng)用, 所以搞清楚PBFT是很有必要的. 這正是那篇最初的PBFT文章.

1. 引言

前提: n個節(jié)點中 至多 向下取整(n-1)/3 的節(jié)點是惡意節(jié)點.

結(jié)果: 能夠確保Liveness (網(wǎng)絡(luò)持續(xù)運行, 不會卡死) 和 Safety (安全性, 不會被惡意節(jié)點主導(dǎo))

之前的BFT算法的缺陷:

1. 假設(shè)消息是同步的 (危險, 因為相比于控制你的節(jié)點, DDOS讓你的節(jié)點反應(yīng)變慢更加簡單, 輕松破壞"同步"假設(shè))

2. 效率低

只讀操作只需要一個round trip.

讀寫操作只需要兩個round trip.

使用基于消息驗證代碼(Message Authentication Code)來進行高效的驗證. public-key cryptography是Rampart的主要吞吐量瓶頸, 在 PBFT中只有當出現(xiàn)錯誤的時候才會使用.

2. 系統(tǒng)模型

異步分布式系統(tǒng). 節(jié)點可能會讓消息發(fā)送失敗, 延遲, 重放或者亂序.

假設(shè): 失效節(jié)點獨立性. 即通過每個節(jié)點不同密碼等各種手段, 確保一個節(jié)點失效不會引發(fā)別的節(jié)點失效, 相互獨立.

目標: 防止/檢測出信息造假, 重放, 損壞

手段:

1. public-key authentication

2. message authentication codes

3. message digests produced by collision-resistant hash functions.

什么是message digests

https://www.techopedia.com/definition/4024/message-digest

可以理解為checksum, 對文件內(nèi)容進行hash, 如果文件內(nèi)容被修改則hash改變, 用以驗證文件是否損壞/被修改. MD5, SHA等算法都可以用作生成message digest的算法)

Cryptographic hash function

密碼學(xué)中將輸入數(shù)據(jù)作為message, 輸出數(shù)據(jù), 即hash value, 記做message digest = 消息摘要.

僅對message digest進行簽名, 而不是對整個message進行簽名.

什么是簽名

非對稱加密中使用私鑰對消息+自己的身份進行加密, 外部節(jié)點使用公鑰進行解密, 可以看到加密方的身份, 即為簽名.

3. 服務(wù)屬性

服務(wù) = 狀態(tài) + 操作

PBFT不依賴于同步性來提供安全性, 但依賴于同步性來實現(xiàn)Liveness. (異步系統(tǒng)的共識是無法實現(xiàn)的, 即使只有一個壞節(jié)點, 也會導(dǎo)致整個系統(tǒng)無法達成共識).

保證Liveness的前提:

1. 至多 向下取整 (n-1)/3個節(jié)點是壞節(jié)點

2. delay(t)增長得比t快.delay(t)為消息發(fā)出時間t與消息被接收的時間之間的延遲.

結(jié)論

當f個節(jié)點為惡意節(jié)點, 全網(wǎng)需要至少3f+1個節(jié)點來確保安全性和liveness.

推理

由于有f個壞節(jié)點, 它們可能完全不回復(fù)消息, 所以我們要確泵匝客戶端只要接收到n-f個消息就足以做出判斷. 不能依賴于更多的信息, 否則等待永不回復(fù)壞節(jié)點就意味著liveness被破壞.

考慮一個最差的情況: 那f個還未回復(fù)的節(jié)點是好節(jié)點, 收到的n-f個消息中有f個壞節(jié)點消息. 那么接到的好節(jié)點的消息實際上是 n-2f個, 壞節(jié)點消息是f個. 根據(jù)少數(shù)服從多數(shù), 需要n-2f>f, 即n>3f.

綜上, 全網(wǎng)總節(jié)點數(shù)n至少是3f+1才能確保安全性和Liveness.

4. 算法

一個應(yīng)用于分布式系統(tǒng), 在不同節(jié)點上運行狀態(tài)完全一致的狀態(tài)機. 每一個狀態(tài)機維護當前的狀態(tài), 同時對外暴露一些操作. 客戶端可以調(diào)用這些操作來修改整個網(wǎng)絡(luò)的狀態(tài).

限制條件:

1. 狀態(tài)機必須是確定性的, 即給定狀態(tài)下的輸出必須一致

2. 所有節(jié)點必須從同一個狀態(tài)開始運行.

這兩個條件用以確保: 所有節(jié)點能夠?qū)蛻舳苏埱蟮恼w順序(全序, 即所有信息的序號都是有序的)達成共識.

n=3f+1是下限. 如果n>3f+1, 并不會讓系統(tǒng)更加健壯, 反而只會降低性能, 因為需要交換更多的信息)

重要概念: View.

節(jié)點運行過程中, 全網(wǎng)絡(luò)的配置(configuration)是在不斷變化的. 比方說現(xiàn)在的配置是A節(jié)點是主節(jié)點, 其余節(jié)點都是從節(jié)點, 那么一段時間后, 這個配置可能改變?yōu)锽節(jié)點為主節(jié)點, 其余從節(jié)點.

我們將每一次的配置狀態(tài)稱為一個View. 整個網(wǎng)絡(luò)就是不斷在不同的View之間切換的.

記當前View的編號為v, 編號為p = v % n的節(jié)點就作為主節(jié)點, 其余作為從節(jié)點. 當主節(jié)點失效時, 進行View的切換.

算法流程:

1. 客戶端發(fā)送請求到主節(jié)點, 調(diào)用"操作"

2. 主節(jié)點向從節(jié)點廣播請求.

3. 所有節(jié)點(包含主節(jié)點?)都將自己的處理結(jié)果發(fā)送給客戶端.

4. 客戶端接收到f+1個來自不同節(jié)點的相同回復(fù)后, 就可以將這個相同回復(fù)作為操作的結(jié)果.

為什么是f+1個? 壞節(jié)點可以無限重放壞消息, 但是無法仿造別人的簽名. 所以f個壞節(jié)點能產(chǎn)生的帶不同簽名的壞回復(fù)至多f個. 那么f+1個相同的消息就必然是好節(jié)點發(fā)出的.

4.1 客戶端

客戶端c將操作o發(fā)送到主節(jié)點, 消息記做 <REQUEST, o, t, c>sigma_c 其中, o是操作, t是時間戳, c是客戶端編號.

節(jié)點直接將操作結(jié)果發(fā)送給客戶端, 記做<REPLY, v, t, c, i, r>sigma_i. 其中, v是View編號, t是請求的時間戳, c是客戶端編號, i是節(jié)點編號, r是操作結(jié)果.

客戶端接收到f+1個, 帶有相同t和r, 但是不同節(jié)點編號的消息后, 就將r作為操作結(jié)果.

如果客戶端在一段時間內(nèi)沒有接收到足夠的回復(fù)(可能因為主節(jié)點沒能廣播成功等原因), 它就自己廣播請求到所有節(jié)點.

如果節(jié)點已經(jīng)處理過這個請求, 直接重發(fā)上一次的回復(fù). 否則, 如果是從節(jié)點, 它要將這個消息轉(zhuǎn)發(fā)給主節(jié)點. 如果從節(jié)點發(fā)現(xiàn)主節(jié)點還不廣播消息, 從節(jié)點就會懷疑主節(jié)點壞了. 這樣的從節(jié)點一旦達到一定數(shù)目, 就進行View變更, 換掉主節(jié)點.

4.2 操作

每一個節(jié)點的狀態(tài), 包含:

1. 整個服務(wù)的狀態(tài).

2. 消息日志(messagelog)

3. 一個代表節(jié)點當前view的整數(shù)

主節(jié)點p接收到客戶端請求m后, 使用一個具有三階段的協(xié)議進行原子性的廣播操作. 如果請求太多, 主節(jié)點會將請求buffer起來稍后再處理.

三階段分別為

1. pre-prepare

2. prepare

3. commit

其中,

pre-prepare和prepare是用來確保同一個View中的請求是全排序的, 即使主節(jié)點是壞的.

prepare和commit是用來確保所有View中的請求整體都是全排序的.

pre-prepare階段, 主節(jié)點對請求m編號為n, 將消息廣播到所有從節(jié)點, 同時加入自己的message log. 消息為<<PRE_PREPARE, v, n, d>sigma_p, m>, 其中v是View編號, m是請求信息, d是m的digest.

(那m的請求信息是啥????)

此pre-prepare消息用作消息m在View v中被編號為n的證明.

注意, 請求的內(nèi)容并沒有放在pre-prepare消息中, 這樣pre-prepare消息就非常小, 如此一來:

1. 將排序的協(xié)議和廣播請求的協(xié)議解耦合

2. 我們可以用適合短消息的協(xié)議來發(fā)送pre-prepare消息, 而用適合長消息的協(xié)議來發(fā)送真正的請求.

滿足以下條件時, 從節(jié)點會接受pre-prepare消息:

1. 請求和pre-prepare消息的簽名都正確, d是m的digest

2. 從節(jié)點在View v中.

3. 它沒接收過同在View v中且編號同為n, 但是digest不一樣的pre-prepare消息

4. 編號n在下限h和上限H之間. (這是為了避免壞的主節(jié)點通過設(shè)置一個超大的n來窮盡編號)

從節(jié)點若不同意接受pre-prepare消息就什么都不做.

若同意接受pre-prepare消息<<PRE_PREPARE, v, n, d>sigma_p, m>, 則進入"prepare"階段:

廣播<PREPARE, v, n, d, i>sigma_i到所有節(jié)點; 將pre-prepare和prepare消息都加入到message log.

節(jié)點(包含主節(jié)點)接收到prepare消息后, 進行驗證: 簽名正確; View編號和節(jié)點當前View編號一致; 編號n在h和H之間. 驗證通過就將prepare消息加到message log.

當且僅當節(jié)點i將如下消息插入到message log后, 我們才認為節(jié)點進入準備完畢狀態(tài), 記做prepared(m, v, n, i).

1. 請求m

2. 針對m, v, n的pre-prepare消息

3. 2f個來自不同從節(jié)點的對應(yīng)于pre-prepare的prepare消息(算上自己的那個prepare消息). 如何驗證對應(yīng)關(guān)系? 通過v, n和digest.

**為什么是2f個****? **

因為prepare消息主節(jié)點不參與發(fā)送, 這樣全網(wǎng)3f+1個節(jié)點刨去主節(jié)點和惡意節(jié)點(f+1)個, 剩下的是2f個好節(jié)點.

[prepared謂詞]

進入準備完畢狀態(tài)后, 節(jié)點i進入commit階段, 廣播消息<COMMIT, v, n, D(m), i>sigma_i到所有節(jié)點.

節(jié)點接收到commit消息后, 進行驗證: 簽名正確; View編號和節(jié)點當前View編號一致; 編號n在h和H之間. 驗證通過就將commit消息加到message log.

[committed, committed-local謂詞]

如果有f+1個好節(jié)點進入到prepared(m, v, n, i)狀態(tài), 則記為commited(m, v, n)狀態(tài)

如果節(jié)點i在prepared(m, v, n, i)狀態(tài)下接收到了2f+1個來自不同節(jié)點(包含自身)的commit消息, 則進入committed_local(m, v, n, i)狀態(tài). 驗證commit和pre-prepare的關(guān)聯(lián)性通過View v, 編號n和digest.

結(jié)論: 一旦有一個節(jié)點進入committed-local(m, v, n, i)狀態(tài), 則全網(wǎng)進入committed(m, v, n)狀態(tài).

PBFT

流程圖解釋:

編號0是主節(jié)點, 3是壞節(jié)點. 1和2是從節(jié)點.

1. 客戶端發(fā)送request給主節(jié)點

2. pre-prepare. 主節(jié)點廣播pre-prepare消息給從節(jié)點.

3. prepare

4. 從節(jié)點廣播prepare消息給所有節(jié)點.

5. 節(jié)點接收到2f個prepare消息(算上自己)后進入commit狀態(tài).

6. commit

7. 所有節(jié)點廣播commit消息

8. 節(jié)點接收到2f+1個commits(算上自己)后, 進入committed-local狀態(tài), 開始執(zhí)行操作并將結(jié)果回復(fù)給client.

4.3 垃圾回收

本章核心概念, checkpoint.

節(jié)點必須保持消息保存在message log中, 直到它知道這個消息已經(jīng)被f+1個節(jié)點執(zhí)行, 而且它可以在view-change的時候向其他節(jié)點證明這一點(被f+1節(jié)點執(zhí)行).

每次操作都生成proof太耗費資源. 節(jié)點只有在一定請求數(shù)目之后才會生成proof. 將運行這一系列操作后得到的狀態(tài), 命名為 checkpoint. 一個有proof的checkpoint被稱為stable checkpoint.

記checkpoint的編號 = 該checkpoint的最后一個請求的編號

節(jié)點保存多個狀態(tài):

1. 最近一個stable checkpoint

2. 若干個不stable的checkpoint

3. 目前節(jié)點自身的狀態(tài).

checkpoint的正確性驗證方法如下:

1. 節(jié)點i創(chuàng)建checkpoint之后, 向其他節(jié)點廣播<CHECKPOINT, n, d, i>_sigma_i. 其中: n是此checkpoint的編號, d是該checkpoint的digest.

2. 每個節(jié)點將收到的checkpoint消息保存到message log中.

3. 當節(jié)點收到2f+1個對應(yīng)于同一個n和d的, 不同的節(jié)點發(fā)出的checkpoint消息后, 這2f+1個消息就可以作為checkpoint的proof.

新的編號為n的stable checkpoin產(chǎn)生后, 節(jié)點就可以將自己保存的所有編號≤n的pre-prepare, prepare, commit消息從log中丟棄.

checkpoint協(xié)議還會修改前文提到的編號的上下界h和H. 新的下界h等于最近一個stable checkpoint的編號 (即該checkpoint的最后一個請求編號);上界H=h+k, 其中k要足夠大, 以避免節(jié)點等待checkpoint變成stable的. 舉例來說, 如果每100個請求一個checkpoint, 那k可以是200.

4.4 View-change

view-change存在的意義: 主節(jié)點壞掉了, 更換view(即更換主節(jié)點), 以此來保證全網(wǎng)的liveness.

從節(jié)點觸發(fā)View Change

從節(jié)點會通過timeout來決定是否進行view-change. 從節(jié)點接收到請求后就會開啟timer, 如果timeout時間內(nèi)處理完請求則停止timer, 否則就會進行view-change, 從v到v+1.

從節(jié)點廣播View Change

此時從節(jié)點將不再接受消息, 廣播<VIEW-CHANGE, v+1, n, C, P, i>_sigma_i消息到所有節(jié)點.

其中:

n是節(jié)點i的最近一次stable checkpoint "s"的編號.

C是用來證明s合法的那2f+1個checkpoint消息.

P是一個包含若干個Pm的集合. 其中Pm的定義: 對于編號大于n且已經(jīng)在節(jié)點i prepared的消息m, Pm包含一個合法的pre-prepare消息(不帶對應(yīng)的client消息)和2f個對應(yīng)的, 由不同節(jié)點簽名的prepare消息(v, n, D(m)要一樣)

新的主節(jié)點上位

View v+1的主節(jié)點p接收到2f個來自不同其他節(jié)點的view-change消息后, 就廣播<NEW-VIEW, v+1, V, O>_sigma_p到所有節(jié)點.

其中:

V: 集合{p接收到的view-change消息, p發(fā)送(或者應(yīng)該發(fā)送)的對于v+1的view-change消息} 后者不就是本消息么?

O: 一個包含若干pre-prepare消息的集合(不順帶請求), 包含如下內(nèi)容:

1. 主節(jié)點從V中找到

2. min-s, 即最近一次stable checkpoint的編號.

3. V中所有prepare消息的最大的編號max-s.

4. 對min-s和max-s之間的每個編號n, 主節(jié)點創(chuàng)建一個新的pre-prepare消息, 用于View v+1. 兩種情況:

5. V中的某個編號為n的view-change消息, 其P集合不為空. 這種情況下, 主節(jié)點創(chuàng)建一個新的pre-prepare消息<PRE-PREPARE, v+1, n, d>_sigma_p, 其中d是V中pre-prepare message????

6. 其P集合為空. 主節(jié)點創(chuàng)建一個新的pre-prepare消息<PRE-PREPARE, v+1, n, d^null>_sigma_p, 其中d^null是一個特殊的null請求的digest. 該操作什么都不做.

然后, 主節(jié)點將O中的信息插入到log中. 如果min-s大于它最近一個checkpoint的編號, 主節(jié)點要計算編號為min-s的checkpoint的proof, 并將其插入到log中, 然后按照4.3中所講進行垃圾回收.

至此, 主節(jié)點正式進入View v+1, 可以接受關(guān)于v+1的消息.

從節(jié)點接受新的主節(jié)點

如果從節(jié)點接受的new-view消息滿足如下條件

1. 簽名合法

2. V中的view-change消息合法.

3. O合法 (算法類似于主節(jié)點創(chuàng)建O的算法)

從節(jié)點會將這些消息加入到log中(跟上一段的主節(jié)點操作一樣), 然后對于O中的每一個pre-prepare消息, 廣播對應(yīng)的prepare消息到所有節(jié)點并插入log, 正是進入View v+1.