共識(shí)的奠基之作)
最近重新翻到 Pease、Shostak 和 Lamport 在 1980 年發(fā)表的這篇《Reaching Agreement in the Presence of Faults》越讀越覺得有意思。這幾年分布式系統(tǒng)、區(qū)塊鏈、共識(shí)算法的文章鋪天蓋地但很多人一上來就聊 PBFT、Raft、HotStuff卻很少有人回頭看看最底層的那個(gè)問題在節(jié)點(diǎn)可能撒謊的前提下我們到底能不能達(dá)成一致又需要多少輪通信、多少消息冗余才能做到這篇論文給出的答案就是 EIGExponential Information Gathering指數(shù)信息收集算法。我在工程里落地過類似的一致性協(xié)議也在模擬環(huán)境里寫過小規(guī)模的拜占庭場(chǎng)景測(cè)試所以這篇論文筆記不打算按摘要、引言、結(jié)論的順序平鋪直敘而是想從“為什么要設(shè)計(jì)成這樣”的角度把 EIG 的樹構(gòu)建、信息交叉驗(yàn)證、多數(shù)決策這三板斧拆開講清楚。如果你正準(zhǔn)備做分布式一致性相關(guān)的項(xiàng)目或者只是想搞明白拜占庭將軍問題為什么有這么多的衍生算法這篇筆記應(yīng)該能幫你跳過不少?gòu)澛贰?. 問題域在什么前提下“達(dá)成一致”才是一個(gè)可解的問題1.1 故障假設(shè)不只是進(jìn)程崩潰平時(shí)我們寫分布式系統(tǒng)默認(rèn)的故障模型是“崩潰故障”節(jié)點(diǎn)掛了就不回復(fù)消息丟了就重傳。這個(gè)模型友好得像一個(gè)說好要交作業(yè)但突然生病請(qǐng)假的同學(xué)你至少知道他會(huì)不會(huì)交、什么時(shí)候交。但如果換一個(gè)場(chǎng)景節(jié)點(diǎn)不一定是掛了而是被攻破、被惡意控制、或者干脆就是一個(gè)故障的傳感器在亂報(bào)數(shù)據(jù)問題就變成了“拜占庭故障”——進(jìn)程還會(huì)持續(xù)運(yùn)行但它的行為完全不可預(yù)測(cè)甚至可能對(duì)不同節(jié)點(diǎn)發(fā)送不同的消息。1980 年這篇論文處理的就是后一種情況。它把故障節(jié)點(diǎn)描述為“行為任意”比如可能發(fā)送沖突消息、可能選擇性沉默、可能偽造來源。這個(gè)假設(shè)放在今天來看非常實(shí)用區(qū)塊鏈里的惡意驗(yàn)證者、跨機(jī)房同步時(shí)的腦裂節(jié)點(diǎn)、物聯(lián)網(wǎng)中被劫持的終端本質(zhì)都是拜占庭故障。所以你可以把這篇論文看成一切非崩潰容錯(cuò)共識(shí)的理論起點(diǎn)。拜占庭故障帶來的核心困難在于你接收到一條消息無法判斷它是不是“真的”。一個(gè)誠(chéng)實(shí)節(jié)點(diǎn)報(bào)告“我看到的值是A”另一個(gè)節(jié)點(diǎn)報(bào)告“我聽到它說的是B”你沒有辦法直接確定哪一個(gè)才是事實(shí)只能靠節(jié)點(diǎn)之間的冗余信息相互驗(yàn)證。EIG 算法的整個(gè)設(shè)計(jì)都是圍繞這個(gè)“無法直接判斷真?zhèn)巍钡睦Ь痴归_的。1.2 同步網(wǎng)絡(luò)假設(shè)一切結(jié)論都有前提論文開篇實(shí)際上隱藏了一個(gè)很容易被忽略的前提通信是同步的。所謂同步指的是消息在一個(gè)有界延遲內(nèi)必然到達(dá)也就是說我們知道一輪消息最晚什么時(shí)候該到齊超過這個(gè)時(shí)間沒到就可以判定對(duì)方有問題。這個(gè)假設(shè)非常重要因?yàn)?EIG 算法的輪次結(jié)構(gòu)依賴“f1 輪之后所有誠(chéng)實(shí)節(jié)點(diǎn)的信息量一致”這個(gè)性質(zhì)。如果消息延遲無界你根本無法判斷“還沒收到”到底是對(duì)方故障還是網(wǎng)絡(luò)慢后續(xù)的多數(shù)決策也就失去了基準(zhǔn)。當(dāng)然今天的工程系統(tǒng)很少能給出嚴(yán)格的同步承諾。Raft 和 PBFT 實(shí)際上利用的是部分同步假設(shè)系統(tǒng)在某個(gè)未知的全局穩(wěn)定時(shí)間GST之后進(jìn)入同步狀態(tài)。但 EIG 的意義在于它在最嚴(yán)格的同步模型下給出了確定性的可解證明后來的異步 BFT 算法很多都是在這個(gè)結(jié)論之上放寬條件的結(jié)果。我建議初學(xué)者先把同步 EIG 吃透再去碰異步情況下的 FLP 不可能結(jié)論。1.3 一個(gè)反直覺結(jié)論3f1 個(gè)節(jié)點(diǎn)才能容忍 f 個(gè)拜占庭故障論文給出了一個(gè)看起來很反直覺的結(jié)論如果總節(jié)點(diǎn)數(shù)為 n拜占庭故障節(jié)點(diǎn)數(shù)為 f那么只有當(dāng) n 3f 時(shí)問題才可解。這個(gè)結(jié)論我最早看到的時(shí)候覺得過于保守畢竟在崩潰故障模型下 n 2f 就夠了。為什么多了一個(gè) f 的冗余用一個(gè)非常樸素的例子解釋。假設(shè) n3f1也就是三個(gè)節(jié)點(diǎn)中有一個(gè)是叛徒。誠(chéng)實(shí)節(jié)點(diǎn) A 和 B 各自匯報(bào)自己的值叛徒 C 對(duì) A 說“我的值是 0”對(duì) B 說“我的值是 1”。這時(shí)候 A 和 B 各自聽著兩個(gè)不同的版本沒人知道該信誰。表面上看如果 A 和 B 多交流一輪似乎可以交叉驗(yàn)證 C 的謊言。但問題是即使它們交流A 會(huì)對(duì) B 說“C 告訴我它是 0而我自己是 x”B 會(huì)對(duì) A 說“C 告訴我它是 1而我自己是 y”。由于 A 和 B 無法確認(rèn) C 到底對(duì)誰說了真話它們依然會(huì)陷入僵局。這個(gè)例子的本質(zhì)是在 n3, f1 時(shí)誠(chéng)實(shí)節(jié)點(diǎn)無法在信息上形成“交集”無法排除故障節(jié)點(diǎn)制造的矛盾。要打破僵局必須讓任何一個(gè)故障節(jié)點(diǎn)在任意一條信息路徑上出現(xiàn)次數(shù)不超過一次這樣多數(shù)投票才有意義。這直接引出了 n 3f 的約束。了解這個(gè)邊界很重要因?yàn)槲乙娺^不少項(xiàng)目在只有兩臺(tái)或三臺(tái)機(jī)器的情況下就去實(shí)現(xiàn)“拜占庭容錯(cuò)”最后發(fā)現(xiàn)只是在處理崩潰恢復(fù)根本沒有真正解決惡意節(jié)點(diǎn)問題因?yàn)樗麄儧]搞懂理論邊界。2. EIG 樹構(gòu)建指數(shù)信息收集Exponential Information Gathering到底在收集什么2.1 消息傳遞流程EIG 的核心思路非常直白讓每個(gè)節(jié)點(diǎn)不僅廣播自己的值還要廣播“它收到了誰的值”以及“它收到了誰轉(zhuǎn)述的誰的值”。這樣經(jīng)過多輪之后每個(gè)節(jié)點(diǎn)都會(huì)擁有一棵記錄傳播路徑的樹樹的每條路徑就代表一條完整的信息鏈。具體流程分輪進(jìn)行。第 1 輪每個(gè)節(jié)點(diǎn)把自己的初始值廣播給所有節(jié)點(diǎn)包括自己。節(jié)點(diǎn)收到后把發(fā)件人和收到的值記錄在樹的第一層。第 2 輪每個(gè)節(jié)點(diǎn)把第 1 輪收到的所有信息原樣轉(zhuǎn)播出去同時(shí)附帶上“這是誰發(fā)給我的”這個(gè)來源信息。節(jié)點(diǎn)再把這些轉(zhuǎn)發(fā)消息記錄在樹的第二層。依此類推經(jīng)過 f1 輪每個(gè)節(jié)點(diǎn)的樹上就會(huì)有從根到葉長(zhǎng)度為 f1 的完整路徑。我最初理解這個(gè)流程時(shí)有一個(gè)誤區(qū)以為每一輪大家廣播的是“自己的值”那只要 f1 輪之后所有人不就都知道所有人的值了嗎事實(shí)不是這樣。每一輪廣播的核心不是原始值而是“我看到的視圖”。也就是第 2 輪廣播的實(shí)際上是“節(jié)點(diǎn) A 告訴我了它的初始值節(jié)點(diǎn) B 告訴我了它的初始值……”這樣一條視圖消息接收者根據(jù)“誰在轉(zhuǎn)發(fā)”來區(qū)分這些視圖來自哪條路徑。正是因?yàn)橄⒗飻y帶了路徑信息樹結(jié)構(gòu)才能反映出某個(gè)節(jié)點(diǎn)在某條路徑上的“二次轉(zhuǎn)述”后續(xù)的決策階段才能針對(duì)性地剔除故障節(jié)點(diǎn)。2.2 路徑與“你自己告訴你”的區(qū)分EIG 樹的每個(gè)節(jié)點(diǎn)用一個(gè)序列號(hào)或者標(biāo)簽標(biāo)記這個(gè)標(biāo)簽其實(shí)就是消息傳播經(jīng)過的節(jié)點(diǎn)序列。比如根節(jié)點(diǎn)代表初始值標(biāo)號(hào)是空序列根的第 i 個(gè)子節(jié)點(diǎn)代表“節(jié)點(diǎn) i 在第 1 輪直接廣播給我的值”再往下路徑 (i, j) 代表“節(jié)點(diǎn) j 轉(zhuǎn)述了它從節(jié)點(diǎn) i 那里聽到的值”。這里有一個(gè)非常關(guān)鍵的細(xì)節(jié)路徑中不能出現(xiàn)重復(fù)節(jié)點(diǎn)。換句話說一條路徑不會(huì)出現(xiàn) (i, i)因?yàn)楣?jié)點(diǎn) i 沒有必要把“自己聽到的自己的值”再轉(zhuǎn)述一遍。所以樹的高度等于 f1但每一層可用的節(jié)點(diǎn)數(shù)在減少。更準(zhǔn)確地說整棵樹的節(jié)點(diǎn)總數(shù)是 n 加上 n(n-1)再加上 n(n-1)(n-2)直到 n 的階乘級(jí)別的路徑數(shù)。這正是“指數(shù)信息收集”這個(gè)名字的由來——系統(tǒng)的總消息量隨著輪數(shù)指數(shù)膨脹。理解這個(gè)路徑設(shè)計(jì)就能明白一條重要性質(zhì)任意兩條不同路徑的交集最多只有 f 個(gè)共同節(jié)點(diǎn)。換句話說如果一條路徑里混入了故障節(jié)點(diǎn)最多也只能跟另一條路徑在 f 個(gè)節(jié)點(diǎn)上產(chǎn)生交集這為后面“保留誠(chéng)實(shí)信息、排除故障信息”的多數(shù)決策提供了結(jié)構(gòu)保證。2.3 在最小案例 n4, f1 中構(gòu)建樹我們用最小的可解案例來走一遍完整流程。系統(tǒng)里有 A、B、C 三個(gè)誠(chéng)實(shí)節(jié)點(diǎn)分別持有初始值 x_A、x_B、x_C還有一個(gè)故障節(jié)點(diǎn) D。按照 n 3f4 個(gè)節(jié)點(diǎn)最多允許 1 個(gè)拜占庭節(jié)點(diǎn)所以 f1需要運(yùn)行 2 輪。第 1 輪結(jié)束后每個(gè)節(jié)點(diǎn)都會(huì)收到來自全部 4 個(gè)節(jié)點(diǎn)的初始值廣播。以誠(chéng)實(shí)節(jié)點(diǎn) A 為例它的樹第一層記錄了A 自己廣播的 x_AB 廣播的 x_BC 廣播的 x_CD 廣播的某個(gè)值 d_A注意 D 可能對(duì)每個(gè)節(jié)點(diǎn)都發(fā)送不同的值這里 d_A 表示 A 收到的版本。第 2 輪A 會(huì)把“我收到 x_B、我收到 x_C、我收到 d_A”這些信息打包然后廣播給 B、C、DB 和 C 也會(huì)做同樣的事情。這一輪結(jié)束后A 的樹第二層就會(huì)多出大量路徑。比如路徑 (B, C) 表示“C 轉(zhuǎn)述了它從 B 那里收到的值”路徑 (D, C) 表示“C 轉(zhuǎn)述了它從 D 那里收到的值”。注意A 本身不需要轉(zhuǎn)述自己收到的 D 消息因?yàn)樗约壕驼驹诼窂降哪┒说?A 可以通過比較“我直接從 D 收到的值”和“B 轉(zhuǎn)述的 D 給 B 的值”以及“C 轉(zhuǎn)述的 D 給 C 的值”來判斷 D 是不是在撒謊。現(xiàn)在有了完整的樹決策階段就可以開始。如果 D 是故障節(jié)點(diǎn)它可能在兩個(gè)誠(chéng)實(shí)節(jié)點(diǎn)面前表現(xiàn)得不一樣但 A、B、C 之間的兩輪信息交換必然會(huì)讓 D 的矛盾暴露出來。樹中某些路徑上的值會(huì)產(chǎn)生沖突這些沖突恰恰是識(shí)別故障節(jié)點(diǎn)的依據(jù)。3. 決策規(guī)則與正確性論證多數(shù)投票為什么在這里是真的可行3.1 從葉子上“修剪”故障節(jié)點(diǎn)拿到一棵完整的 EIG 樹之后怎么得出最終決定論文給出的規(guī)則可以拆成兩部分。第一部分是“一致性校驗(yàn)”。節(jié)點(diǎn) A 需要檢查樹中的每條路徑看看是否存在“同一節(jié)點(diǎn)在不同路徑上說了互相矛盾的話”。例如A 直接收到 D 的值是 d_A但 B 轉(zhuǎn)述說“D 告訴 B 的值是 d_B”而 d_A ≠ d_B那么 A 基本可以斷定 D 是一個(gè)故障節(jié)點(diǎn)。此時(shí) A 會(huì)丟棄所有包含節(jié)點(diǎn) D 的路徑也就是從第三層往下把它從樹里剪掉。關(guān)鍵是這一步并不是“判斷 D 是否故障”的絕對(duì)證明因?yàn)橐粋€(gè)故障節(jié)點(diǎn)可能在某些路徑上表現(xiàn)得完全一致也可能一個(gè)誠(chéng)實(shí)節(jié)點(diǎn)因?yàn)槟硞€(gè)異常流程被誤判。但 EIG 的巧妙之處在于它不要求每個(gè)節(jié)點(diǎn)對(duì)“誰故障”達(dá)成一致觀點(diǎn)它只是用這種剪枝操作把明顯沖突的信息從決策池中排除出去。第二部分是“多數(shù)決策”。剪枝之后每個(gè)節(jié)點(diǎn)對(duì)它樹中“頂層各分支”的值做多數(shù)投票。具體規(guī)則是從葉子往上遞歸計(jì)算如果一個(gè)節(jié)點(diǎn)的所有子樹都持有相同值這個(gè)值就向上傳導(dǎo)如果不一致就取子樹中的多數(shù)值如果沒有多數(shù)值則采用故障處理下的默認(rèn)值。遞歸到根節(jié)點(diǎn)時(shí)得出該節(jié)點(diǎn)認(rèn)為的系統(tǒng)一致性值。這里的多數(shù)投票跟普通的數(shù)據(jù)備份多數(shù)投票完全不同。普通投票只需要大多數(shù)節(jié)點(diǎn)在線即可EIG 的投票則是建立在“每一條路徑的獨(dú)立性”之上。因?yàn)楣收瞎?jié)點(diǎn)最多 f 個(gè)而任意兩條通往葉子的路徑交集不超過 f 個(gè)節(jié)點(diǎn)所以一旦某個(gè)值在葉子層形成了多數(shù)這個(gè)多數(shù)的結(jié)論就必然會(huì)傳遞到所有誠(chéng)實(shí)節(jié)點(diǎn)的根節(jié)點(diǎn)。換句話說這個(gè)多數(shù)不是統(tǒng)計(jì)意義上的“大多數(shù)而是信息冗余意義上的一種“不可能被偽造的利益聯(lián)合體”。3.2 正確性證明的關(guān)鍵引理教科書上通常用兩個(gè)引理來證明 EIG 算法的正確性我用大白話復(fù)述一下。引理一是兩個(gè)誠(chéng)實(shí)節(jié)點(diǎn)的樹在經(jīng)過了 f1 輪信息交換之后對(duì)于任意一條不包含故障節(jié)點(diǎn)的路徑它們記錄的值是相同的。原因很簡(jiǎn)單因?yàn)檫@條路徑上的每個(gè)節(jié)點(diǎn)都是誠(chéng)實(shí)的它們的轉(zhuǎn)述不會(huì)篡改信息所以無論從哪個(gè)誠(chéng)實(shí)節(jié)點(diǎn)去看這條路徑得到的結(jié)果都是一致的。引理二是如果故障節(jié)點(diǎn)試圖在兩條包含它的路徑上分別傳遞不同的值那么這兩條路徑必然會(huì)被某個(gè)誠(chéng)實(shí)節(jié)點(diǎn)的剪枝操作識(shí)別出來即使沒有識(shí)別出來多數(shù)投票也會(huì)把那個(gè)被篡改的分支淹掉。這個(gè)結(jié)論要?dú)w功于路徑交集的上限故障節(jié)點(diǎn)出現(xiàn)的次數(shù)有限它不可能同時(shí)壓過所有誠(chéng)實(shí)節(jié)點(diǎn)匯合而成的信息主流。這個(gè)證明思路對(duì)我最大的啟發(fā)是它不是去證明“每個(gè)節(jié)點(diǎn)都能準(zhǔn)確識(shí)別出故障節(jié)點(diǎn)”而是證明“即便某些故障節(jié)點(diǎn)沒有被識(shí)別出來多數(shù)決策的結(jié)果也完全一致”。這種從“結(jié)果一致性”出發(fā)的證明思路在工程上非常實(shí)用。因?yàn)楝F(xiàn)實(shí)項(xiàng)目中我們很少能精確定位哪臺(tái)機(jī)器出了故障很多時(shí)候只能確定“這群數(shù)據(jù)里混了臟數(shù)據(jù)”但只要我們能在輸出層面達(dá)成一致系統(tǒng)照樣可以對(duì)外提供正確服務(wù)。3.3 同步假設(shè)與 f1 輪的實(shí)際意義為什么恰好是 f1 輪而不是 f 輪或者 f2 輪可以從兩個(gè)方向理解。從信息傳播的角度看每一輪都讓每個(gè)節(jié)點(diǎn)的“視野”向外擴(kuò)展一層。要做到所有誠(chéng)實(shí)節(jié)點(diǎn)的視圖足夠交疊必須讓每條消息有足夠的時(shí)間穿過由誠(chéng)實(shí)節(jié)點(diǎn)組成的“信息骨干”。f 個(gè)故障節(jié)點(diǎn)最多可以沿路徑打斷 f 次所以需要 f1 次傳播才能確保至少存在一條完整的誠(chéng)實(shí)路徑把某個(gè)值從發(fā)起者傳到每個(gè)誠(chéng)實(shí)節(jié)點(diǎn)的視圖中。從異步邊界來看如果只看 f 輪故障節(jié)點(diǎn)有可能在最后一輪之前一直保持沉默讓所有誠(chéng)實(shí)節(jié)點(diǎn)都以為它不存在然后在最后一輪突然向部分節(jié)點(diǎn)發(fā)送不同的消息造成混亂。f1 輪就保證了一個(gè)故障節(jié)點(diǎn)制造的矛盾即使發(fā)生也有剩余輪次被誠(chéng)實(shí)節(jié)點(diǎn)的交叉驗(yàn)證暴露出來。工程上做超時(shí)設(shè)置的時(shí)候也可以參考這個(gè)概念如果容忍一次故障至少需要兩個(gè)有效的通信來回才能讓系統(tǒng)穩(wěn)定地達(dá)成一致。4. EIG 的代價(jià)與現(xiàn)實(shí)世界的取舍4.1 消息量是指數(shù)級(jí)的不是開玩笑EIG 的完整運(yùn)行需要多少消息粗略估算一下每輪每個(gè)節(jié)點(diǎn)都要向其余 n-1 個(gè)節(jié)點(diǎn)廣播自己當(dāng)前樹中的全部路徑信息而樹中的路徑數(shù)量隨著輪數(shù)指數(shù)增長(zhǎng)。在 f1 輪結(jié)束時(shí)總消息量大約在 O(n^(f1)) 級(jí)別確切說是指數(shù)級(jí)復(fù)雜度。對(duì)于 f1n4 的小案例這個(gè)數(shù)字還勉強(qiáng)能接受但如果系統(tǒng)有 100 個(gè)節(jié)點(diǎn)、需要容忍 10 個(gè)拜占庭故障消息量就會(huì)膨脹到天文數(shù)字這在實(shí)際網(wǎng)絡(luò)里完全不可行。這就是為什么 1980 年論文給出了一個(gè)理論上漂亮的算法但工程上很少直接實(shí)現(xiàn) EIG。現(xiàn)代 BFT 算法比如 PBFT會(huì)把通信復(fù)雜度降到多項(xiàng)式級(jí)別核心手段是引入“視圖”和“主節(jié)點(diǎn)”讓每一輪不再?gòu)V播整棵樹路徑而是廣播摘要和簽名。但 PBFT 的正確性論證里依然有 EIG 的影子——只不過它把“指數(shù)路徑冗余”換成了“多項(xiàng)式多輪交互 數(shù)字簽名”。如果你在做教學(xué)或者仿真實(shí)驗(yàn)我建議還是先實(shí)現(xiàn)一遍 EIG。它的代碼量不大但能很直觀地看到拜占庭故障對(duì)共識(shí)過程的攪動(dòng)作用。我在自己的測(cè)試環(huán)境里用 Python 寫過 n5、f1 的 EIG 模擬最后生成的樹結(jié)構(gòu)信息非常清晰比直接看 PBFT 的論文實(shí)現(xiàn)容易理解得多。4.2 EIG 與區(qū)塊鏈共識(shí)的關(guān)系很多人問既然 EIG 這么古老跟現(xiàn)在區(qū)塊鏈里的共識(shí)算法有什么關(guān)系其實(shí)關(guān)系非常大。中本聰共識(shí)工作量證明本質(zhì)上是通過算力投票來替代拜占庭節(jié)點(diǎn)之間的交互驗(yàn)證它能在開放網(wǎng)絡(luò)里工作是因?yàn)椤坝?jì)算資源”約束取代了“故障節(jié)點(diǎn)上限”約束。而在聯(lián)盟鏈或許可鏈里PBFT 類算法動(dòng)輒要求 n 3f這正是從這篇論文繼承下來的基礎(chǔ)結(jié)論。哪怕以太坊的 Casper FFG 這類基于權(quán)益證明的共識(shí)也無法繞開對(duì)拜占庭節(jié)點(diǎn)比例的嚴(yán)格假設(shè)。從另一個(gè)角度看EIG 的信息收集思想在“跨鏈驗(yàn)證”和“輕節(jié)點(diǎn)驗(yàn)證”中也有應(yīng)用。很多跨鏈協(xié)議要求中繼鏈對(duì)目標(biāo)鏈的狀態(tài)進(jìn)行多路采樣驗(yàn)證實(shí)際上就是不同路徑上的節(jié)點(diǎn)分別匯報(bào)自己看到的狀態(tài)摘要而合約根據(jù)多數(shù)一致的結(jié)果做出最終判斷。這和 EIG 樹中從多個(gè)路徑匯聚信息再多數(shù)投票的邏輯是相通的。4.3 什么時(shí)候 EIG 是“劃算”的雖然指數(shù)級(jí)消息復(fù)雜度很嚇人但 EIG 有個(gè)常被人忽略的優(yōu)勢(shì)它不需要數(shù)字簽名。該算法只依賴多輪交互和路徑交叉就解決了拜占庭問題這在 1980 年是一個(gè)非常大的貢獻(xiàn)因?yàn)楫?dāng)時(shí)的密碼學(xué)開銷被認(rèn)為非常昂貴。如果你的應(yīng)用場(chǎng)景滿足以下條件EIG 反而可能是一個(gè)值得考慮的方案節(jié)點(diǎn)數(shù)量很小比如 4 到 8 個(gè)故障輪次很少通常只需要容忍 1 個(gè)故障網(wǎng)絡(luò)是同步的通信延遲有界開發(fā)環(huán)境難以引入復(fù)雜的密碼學(xué)或者簽名庫(kù)。在這種極限場(chǎng)景下EIG 比 PBFT 更簡(jiǎn)單、更容易證明正確性也不需要維護(hù)視圖切換邏輯。我自己試過在一個(gè)低功耗嵌入式采集系統(tǒng)里模擬過類似流程節(jié)點(diǎn)之間用共享內(nèi)存通信最后的一致性效果非常穩(wěn)定代碼量也控制在幾百行以內(nèi)。5. 從 1980 年的論文到現(xiàn)代工程我讀 EIG 的四個(gè)實(shí)際收獲5.1 故障越“聰明”方案越要依賴結(jié)構(gòu)而不是技巧早期我也嘗試過用啟發(fā)式規(guī)則來識(shí)別拜占庭故障比如“如果某個(gè)節(jié)點(diǎn)的值連續(xù)多次與其他節(jié)點(diǎn)不同就標(biāo)記為故障”。這種思路在故障節(jié)點(diǎn)行為固定的時(shí)候有效但只要故障節(jié)點(diǎn)稍微聰明一點(diǎn)輪流對(duì) A 撒謊、對(duì) B 說實(shí)話、對(duì) C 沉默啟發(fā)式規(guī)則就會(huì)被繞過。EIG 給了一個(gè)徹底的方法論轉(zhuǎn)向不要試圖猜誰在撒謊而是通過讓信息沿著不相交的路徑匯聚使得撒謊行為在數(shù)學(xué)上不可能不被多數(shù)淹沒。這就像審計(jì)賬目時(shí)不靠肉眼辨別哪張發(fā)票是假的而是強(qiáng)制要求同一筆交易必須經(jīng)多個(gè)獨(dú)立渠道交叉驗(yàn)證假發(fā)票自然就被結(jié)構(gòu)隔離出來了。這個(gè)思路對(duì)架構(gòu)設(shè)計(jì)有很強(qiáng)的指導(dǎo)性——與其強(qiáng)化單點(diǎn)檢測(cè)不如設(shè)計(jì)信息冗余的結(jié)構(gòu)。5.2 同步假設(shè)不是理論家的玩具而是系統(tǒng)的兜底每次我跟團(tuán)隊(duì)討論系統(tǒng)設(shè)計(jì)時(shí)都會(huì)反復(fù)強(qiáng)調(diào)延遲上界timeout和輪次設(shè)計(jì)。在無界延遲的網(wǎng)絡(luò)里任何確定性共識(shí)算法都不可能同時(shí)滿足安全性和活性這是 FLP 定理的結(jié)論。EIG 雖然是 1980 年的論文但它已經(jīng)把“同步假設(shè)”作為整個(gè)協(xié)議運(yùn)行的前提你能在最原始的版本里看到一個(gè)概念的最純粹形態(tài)。現(xiàn)代工程中我們常用超時(shí)和重試來近似同步假設(shè)但要記住超時(shí)設(shè)置的背后就是 f1 輪思想的實(shí)踐。如果超時(shí)太短誠(chéng)實(shí)節(jié)點(diǎn)被誤判為故障節(jié)點(diǎn)如果超時(shí)太長(zhǎng)系統(tǒng)活性受損。理解了 EIG 對(duì)輪數(shù)的敏感性你在調(diào)參的時(shí)候至少能意識(shí)到這不是單純“拍腦袋定 10 秒”的問題。5.3 多數(shù)決策之前必須先有“可比較的信息視圖”很多人寫一致性協(xié)議時(shí)直接就對(duì)各節(jié)點(diǎn)的上報(bào)值做多數(shù)投票但別忘了投票的前提是大家投票的對(duì)象一致。EIG 樹的第一個(gè)作用其實(shí)是“對(duì)齊信息視圖”經(jīng)過 f1 輪交換之后每個(gè)誠(chéng)實(shí)節(jié)點(diǎn)都有了一棵結(jié)構(gòu)相同的樹差異只在于具體路徑上的值可能被故障節(jié)點(diǎn)污染。這為后面的多數(shù)投票建立了一個(gè)公共坐標(biāo)系。我在實(shí)際項(xiàng)目里踩過一個(gè)坑兩個(gè)數(shù)據(jù)中心各自維護(hù)一個(gè)本地狀態(tài)版本號(hào)然后試圖在它們之間做“多數(shù)投票”決定哪個(gè)版本應(yīng)該保留。結(jié)果發(fā)現(xiàn)兩個(gè)中心看到的節(jié)點(diǎn)列表都不一樣投票根本沒法進(jìn)行。后來我引入了一個(gè)虛擬的公共歷史結(jié)構(gòu)相當(dāng)于 EIG 樹的簡(jiǎn)化版先讓所有節(jié)點(diǎn)對(duì)齊自己的視圖再做多數(shù)判斷功能才穩(wěn)定下來。5.4 老論文的數(shù)學(xué)工具到今天依然可以用EIG 論文里用到的路徑、樹、交叉驗(yàn)證、多數(shù)合并這些工具本質(zhì)上是一套組合數(shù)學(xué)方法。今天你在實(shí)現(xiàn) Sharding 分片、數(shù)據(jù)副本修復(fù)、甚至多層聯(lián)邦學(xué)習(xí)聚合的時(shí)候都會(huì)遇到類似的“信息來自多個(gè)源頭需要融合確認(rèn)”的問題。一個(gè)人如果只懂得用最終一致性或者 Paxos 這類現(xiàn)成協(xié)議遇到新的場(chǎng)景大概率會(huì)抓瞎反過來如果掌握了 EIG 的這種樹狀信息收集和路徑?jīng)_突識(shí)別框架自研一個(gè)輕量級(jí)拜占庭容錯(cuò)協(xié)議并不是難事。我讀這篇論文的最大感受是它把“共識(shí)”這個(gè)看似抽象的問題轉(zhuǎn)化成了“樹的構(gòu)造與樹的修剪”這種非常具象的算法問題。如果你愿意動(dòng)手實(shí)現(xiàn)建議從 n4、f1 的無簽名版本開始把樹的層次打印出來逐步觀察故障節(jié)點(diǎn)在樹上制造的分歧。把這張圖看明白之后再去看 PBFT、Tendermint、HotStuff都會(huì)覺得順理成章。最后再分享一個(gè)小技巧做論文筆記時(shí)不要只摘抄結(jié)論盡量把每一輪的消息示例手動(dòng)走一遍。EIG 這種輪次型算法親手在紙上畫一遍樹勝過讀十遍證明。你一旦理解了“路徑”和“交集”這兩個(gè)概念整個(gè)分布式系統(tǒng)里的拜占庭問題就再也不會(huì)繞暈?zāi)懔恕? EIG算法詳解：拜占庭容錯(cuò)共識(shí)的奠基之作
最近重新翻到 Pease、Shostak 和 Lamport 在 1980 年發(fā)表的這篇《Reaching Agreement in the Presence of Faults》越讀越覺得有意思。這幾年分布式系統(tǒng)、區(qū)塊鏈、共識(shí)算法的文章鋪天蓋地但很多人一上來就聊 PBFT、Raft、HotStuff卻很少有人回頭看看最底層的那個(gè)問題在節(jié)點(diǎn)可能撒謊的前提下我們到底能不能達(dá)成一致又需要多少輪通信、多少消息冗余才能做到這篇論文給出的答案就是 EIGExponential Information Gathering指數(shù)信息收集算法。我在工程里落地過類似的一致性協(xié)議也在模擬環(huán)境里寫過小規(guī)模的拜占庭場(chǎng)景測(cè)試所以這篇論文筆記不打算按摘要、引言、結(jié)論的順序平鋪直敘而是想從“為什么要設(shè)計(jì)成這樣”的角度把 EIG 的樹構(gòu)建、信息交叉驗(yàn)證、多數(shù)決策這三板斧拆開講清楚。如果你正準(zhǔn)備做分布式一致性相關(guān)的項(xiàng)目或者只是想搞明白拜占庭將軍問題為什么有這么多的衍生算法這篇筆記應(yīng)該能幫你跳過不少?gòu)澛贰?. 問題域在什么前提下“達(dá)成一致”才是一個(gè)可解的問題1.1 故障假設(shè)不只是進(jìn)程崩潰平時(shí)我們寫分布式系統(tǒng)默認(rèn)的故障模型是“崩潰故障”節(jié)點(diǎn)掛了就不回復(fù)消息丟了就重傳。這個(gè)模型友好得像一個(gè)說好要交作業(yè)但突然生病請(qǐng)假的同學(xué)你至少知道他會(huì)不會(huì)交、什么時(shí)候交。但如果換一個(gè)場(chǎng)景節(jié)點(diǎn)不一定是掛了而是被攻破、被惡意控制、或者干脆就是一個(gè)故障的傳感器在亂報(bào)數(shù)據(jù)問題就變成了“拜占庭故障”——進(jìn)程還會(huì)持續(xù)運(yùn)行但它的行為完全不可預(yù)測(cè)甚至可能對(duì)不同節(jié)點(diǎn)發(fā)送不同的消息。1980 年這篇論文處理的就是后一種情況。它把故障節(jié)點(diǎn)描述為“行為任意”比如可能發(fā)送沖突消息、可能選擇性沉默、可能偽造來源。這個(gè)假設(shè)放在今天來看非常實(shí)用區(qū)塊鏈里的惡意驗(yàn)證者、跨機(jī)房同步時(shí)的腦裂節(jié)點(diǎn)、物聯(lián)網(wǎng)中被劫持的終端本質(zhì)都是拜占庭故障。所以你可以把這篇論文看成一切非崩潰容錯(cuò)共識(shí)的理論起點(diǎn)。拜占庭故障帶來的核心困難在于你接收到一條消息無法判斷它是不是“真的”。一個(gè)誠(chéng)實(shí)節(jié)點(diǎn)報(bào)告“我看到的值是A”另一個(gè)節(jié)點(diǎn)報(bào)告“我聽到它說的是B”你沒有辦法直接確定哪一個(gè)才是事實(shí)只能靠節(jié)點(diǎn)之間的冗余信息相互驗(yàn)證。EIG 算法的整個(gè)設(shè)計(jì)都是圍繞這個(gè)“無法直接判斷真?zhèn)巍钡睦Ь痴归_的。1.2 同步網(wǎng)絡(luò)假設(shè)一切結(jié)論都有前提論文開篇實(shí)際上隱藏了一個(gè)很容易被忽略的前提通信是同步的。所謂同步指的是消息在一個(gè)有界延遲內(nèi)必然到達(dá)也就是說我們知道一輪消息最晚什么時(shí)候該到齊超過這個(gè)時(shí)間沒到就可以判定對(duì)方有問題。這個(gè)假設(shè)非常重要因?yàn)?EIG 算法的輪次結(jié)構(gòu)依賴“f1 輪之后所有誠(chéng)實(shí)節(jié)點(diǎn)的信息量一致”這個(gè)性質(zhì)。如果消息延遲無界你根本無法判斷“還沒收到”到底是對(duì)方故障還是網(wǎng)絡(luò)慢后續(xù)的多數(shù)決策也就失去了基準(zhǔn)。當(dāng)然今天的工程系統(tǒng)很少能給出嚴(yán)格的同步承諾。Raft 和 PBFT 實(shí)際上利用的是部分同步假設(shè)系統(tǒng)在某個(gè)未知的全局穩(wěn)定時(shí)間GST之后進(jìn)入同步狀態(tài)。但 EIG 的意義在于它在最嚴(yán)格的同步模型下給出了確定性的可解證明后來的異步 BFT 算法很多都是在這個(gè)結(jié)論之上放寬條件的結(jié)果。我建議初學(xué)者先把同步 EIG 吃透再去碰異步情況下的 FLP 不可能結(jié)論。1.3 一個(gè)反直覺結(jié)論3f1 個(gè)節(jié)點(diǎn)才能容忍 f 個(gè)拜占庭故障論文給出了一個(gè)看起來很反直覺的結(jié)論如果總節(jié)點(diǎn)數(shù)為 n拜占庭故障節(jié)點(diǎn)數(shù)為 f那么只有當(dāng) n 3f 時(shí)問題才可解。這個(gè)結(jié)論我最早看到的時(shí)候覺得過于保守畢竟在崩潰故障模型下 n 2f 就夠了。為什么多了一個(gè) f 的冗余用一個(gè)非常樸素的例子解釋。假設(shè) n3f1也就是三個(gè)節(jié)點(diǎn)中有一個(gè)是叛徒。誠(chéng)實(shí)節(jié)點(diǎn) A 和 B 各自匯報(bào)自己的值叛徒 C 對(duì) A 說“我的值是 0”對(duì) B 說“我的值是 1”。這時(shí)候 A 和 B 各自聽著兩個(gè)不同的版本沒人知道該信誰。表面上看如果 A 和 B 多交流一輪似乎可以交叉驗(yàn)證 C 的謊言。但問題是即使它們交流A 會(huì)對(duì) B 說“C 告訴我它是 0而我自己是 x”B 會(huì)對(duì) A 說“C 告訴我它是 1而我自己是 y”。由于 A 和 B 無法確認(rèn) C 到底對(duì)誰說了真話它們依然會(huì)陷入僵局。這個(gè)例子的本質(zhì)是在 n3, f1 時(shí)誠(chéng)實(shí)節(jié)點(diǎn)無法在信息上形成“交集”無法排除故障節(jié)點(diǎn)制造的矛盾。要打破僵局必須讓任何一個(gè)故障節(jié)點(diǎn)在任意一條信息路徑上出現(xiàn)次數(shù)不超過一次這樣多數(shù)投票才有意義。這直接引出了 n 3f 的約束。了解這個(gè)邊界很重要因?yàn)槲乙娺^不少項(xiàng)目在只有兩臺(tái)或三臺(tái)機(jī)器的情況下就去實(shí)現(xiàn)“拜占庭容錯(cuò)”最后發(fā)現(xiàn)只是在處理崩潰恢復(fù)根本沒有真正解決惡意節(jié)點(diǎn)問題因?yàn)樗麄儧]搞懂理論邊界。2. EIG 樹構(gòu)建指數(shù)信息收集Exponential Information Gathering到底在收集什么2.1 消息傳遞流程EIG 的核心思路非常直白讓每個(gè)節(jié)點(diǎn)不僅廣播自己的值還要廣播“它收到了誰的值”以及“它收到了誰轉(zhuǎn)述的誰的值”。這樣經(jīng)過多輪之后每個(gè)節(jié)點(diǎn)都會(huì)擁有一棵記錄傳播路徑的樹樹的每條路徑就代表一條完整的信息鏈。具體流程分輪進(jìn)行。第 1 輪每個(gè)節(jié)點(diǎn)把自己的初始值廣播給所有節(jié)點(diǎn)包括自己。節(jié)點(diǎn)收到后把發(fā)件人和收到的值記錄在樹的第一層。第 2 輪每個(gè)節(jié)點(diǎn)把第 1 輪收到的所有信息原樣轉(zhuǎn)播出去同時(shí)附帶上“這是誰發(fā)給我的”這個(gè)來源信息。節(jié)點(diǎn)再把這些轉(zhuǎn)發(fā)消息記錄在樹的第二層。依此類推經(jīng)過 f1 輪每個(gè)節(jié)點(diǎn)的樹上就會(huì)有從根到葉長(zhǎng)度為 f1 的完整路徑。我最初理解這個(gè)流程時(shí)有一個(gè)誤區(qū)以為每一輪大家廣播的是“自己的值”那只要 f1 輪之后所有人不就都知道所有人的值了嗎事實(shí)不是這樣。每一輪廣播的核心不是原始值而是“我看到的視圖”。也就是第 2 輪廣播的實(shí)際上是“節(jié)點(diǎn) A 告訴我了它的初始值節(jié)點(diǎn) B 告訴我了它的初始值……”這樣一條視圖消息接收者根據(jù)“誰在轉(zhuǎn)發(fā)”來區(qū)分這些視圖來自哪條路徑。正是因?yàn)橄⒗飻y帶了路徑信息樹結(jié)構(gòu)才能反映出某個(gè)節(jié)點(diǎn)在某條路徑上的“二次轉(zhuǎn)述”后續(xù)的決策階段才能針對(duì)性地剔除故障節(jié)點(diǎn)。2.2 路徑與“你自己告訴你”的區(qū)分EIG 樹的每個(gè)節(jié)點(diǎn)用一個(gè)序列號(hào)或者標(biāo)簽標(biāo)記這個(gè)標(biāo)簽其實(shí)就是消息傳播經(jīng)過的節(jié)點(diǎn)序列。比如根節(jié)點(diǎn)代表初始值標(biāo)號(hào)是空序列根的第 i 個(gè)子節(jié)點(diǎn)代表“節(jié)點(diǎn) i 在第 1 輪直接廣播給我的值”再往下路徑 (i, j) 代表“節(jié)點(diǎn) j 轉(zhuǎn)述了它從節(jié)點(diǎn) i 那里聽到的值”。這里有一個(gè)非常關(guān)鍵的細(xì)節(jié)路徑中不能出現(xiàn)重復(fù)節(jié)點(diǎn)。換句話說一條路徑不會(huì)出現(xiàn) (i, i)因?yàn)楣?jié)點(diǎn) i 沒有必要把“自己聽到的自己的值”再轉(zhuǎn)述一遍。所以樹的高度等于 f1但每一層可用的節(jié)點(diǎn)數(shù)在減少。更準(zhǔn)確地說整棵樹的節(jié)點(diǎn)總數(shù)是 n 加上 n(n-1)再加上 n(n-1)(n-2)直到 n 的階乘級(jí)別的路徑數(shù)。這正是“指數(shù)信息收集”這個(gè)名字的由來——系統(tǒng)的總消息量隨著輪數(shù)指數(shù)膨脹。理解這個(gè)路徑設(shè)計(jì)就能明白一條重要性質(zhì)任意兩條不同路徑的交集最多只有 f 個(gè)共同節(jié)點(diǎn)。換句話說如果一條路徑里混入了故障節(jié)點(diǎn)最多也只能跟另一條路徑在 f 個(gè)節(jié)點(diǎn)上產(chǎn)生交集這為后面“保留誠(chéng)實(shí)信息、排除故障信息”的多數(shù)決策提供了結(jié)構(gòu)保證。2.3 在最小案例 n4, f1 中構(gòu)建樹我們用最小的可解案例來走一遍完整流程。系統(tǒng)里有 A、B、C 三個(gè)誠(chéng)實(shí)節(jié)點(diǎn)分別持有初始值 x_A、x_B、x_C還有一個(gè)故障節(jié)點(diǎn) D。按照 n 3f4 個(gè)節(jié)點(diǎn)最多允許 1 個(gè)拜占庭節(jié)點(diǎn)所以 f1需要運(yùn)行 2 輪。第 1 輪結(jié)束后每個(gè)節(jié)點(diǎn)都會(huì)收到來自全部 4 個(gè)節(jié)點(diǎn)的初始值廣播。以誠(chéng)實(shí)節(jié)點(diǎn) A 為例它的樹第一層記錄了A 自己廣播的 x_AB 廣播的 x_BC 廣播的 x_CD 廣播的某個(gè)值 d_A注意 D 可能對(duì)每個(gè)節(jié)點(diǎn)都發(fā)送不同的值這里 d_A 表示 A 收到的版本。第 2 輪A 會(huì)把“我收到 x_B、我收到 x_C、我收到 d_A”這些信息打包然后廣播給 B、C、DB 和 C 也會(huì)做同樣的事情。這一輪結(jié)束后A 的樹第二層就會(huì)多出大量路徑。比如路徑 (B, C) 表示“C 轉(zhuǎn)述了它從 B 那里收到的值”路徑 (D, C) 表示“C 轉(zhuǎn)述了它從 D 那里收到的值”。注意A 本身不需要轉(zhuǎn)述自己收到的 D 消息因?yàn)樗约壕驼驹诼窂降哪┒说?A 可以通過比較“我直接從 D 收到的值”和“B 轉(zhuǎn)述的 D 給 B 的值”以及“C 轉(zhuǎn)述的 D 給 C 的值”來判斷 D 是不是在撒謊。現(xiàn)在有了完整的樹決策階段就可以開始。如果 D 是故障節(jié)點(diǎn)它可能在兩個(gè)誠(chéng)實(shí)節(jié)點(diǎn)面前表現(xiàn)得不一樣但 A、B、C 之間的兩輪信息交換必然會(huì)讓 D 的矛盾暴露出來。樹中某些路徑上的值會(huì)產(chǎn)生沖突這些沖突恰恰是識(shí)別故障節(jié)點(diǎn)的依據(jù)。3. 決策規(guī)則與正確性論證多數(shù)投票為什么在這里是真的可行3.1 從葉子上“修剪”故障節(jié)點(diǎn)拿到一棵完整的 EIG 樹之后怎么得出最終決定論文給出的規(guī)則可以拆成兩部分。第一部分是“一致性校驗(yàn)”。節(jié)點(diǎn) A 需要檢查樹中的每條路徑看看是否存在“同一節(jié)點(diǎn)在不同路徑上說了互相矛盾的話”。例如A 直接收到 D 的值是 d_A但 B 轉(zhuǎn)述說“D 告訴 B 的值是 d_B”而 d_A ≠ d_B那么 A 基本可以斷定 D 是一個(gè)故障節(jié)點(diǎn)。此時(shí) A 會(huì)丟棄所有包含節(jié)點(diǎn) D 的路徑也就是從第三層往下把它從樹里剪掉。關(guān)鍵是這一步并不是“判斷 D 是否故障”的絕對(duì)證明因?yàn)橐粋€(gè)故障節(jié)點(diǎn)可能在某些路徑上表現(xiàn)得完全一致也可能一個(gè)誠(chéng)實(shí)節(jié)點(diǎn)因?yàn)槟硞€(gè)異常流程被誤判。但 EIG 的巧妙之處在于它不要求每個(gè)節(jié)點(diǎn)對(duì)“誰故障”達(dá)成一致觀點(diǎn)它只是用這種剪枝操作把明顯沖突的信息從決策池中排除出去。第二部分是“多數(shù)決策”。剪枝之后每個(gè)節(jié)點(diǎn)對(duì)它樹中“頂層各分支”的值做多數(shù)投票。具體規(guī)則是從葉子往上遞歸計(jì)算如果一個(gè)節(jié)點(diǎn)的所有子樹都持有相同值這個(gè)值就向上傳導(dǎo)如果不一致就取子樹中的多數(shù)值如果沒有多數(shù)值則采用故障處理下的默認(rèn)值。遞歸到根節(jié)點(diǎn)時(shí)得出該節(jié)點(diǎn)認(rèn)為的系統(tǒng)一致性值。這里的多數(shù)投票跟普通的數(shù)據(jù)備份多數(shù)投票完全不同。普通投票只需要大多數(shù)節(jié)點(diǎn)在線即可EIG 的投票則是建立在“每一條路徑的獨(dú)立性”之上。因?yàn)楣收瞎?jié)點(diǎn)最多 f 個(gè)而任意兩條通往葉子的路徑交集不超過 f 個(gè)節(jié)點(diǎn)所以一旦某個(gè)值在葉子層形成了多數(shù)這個(gè)多數(shù)的結(jié)論就必然會(huì)傳遞到所有誠(chéng)實(shí)節(jié)點(diǎn)的根節(jié)點(diǎn)。換句話說這個(gè)多數(shù)不是統(tǒng)計(jì)意義上的“大多數(shù)而是信息冗余意義上的一種“不可能被偽造的利益聯(lián)合體”。3.2 正確性證明的關(guān)鍵引理教科書上通常用兩個(gè)引理來證明 EIG 算法的正確性我用大白話復(fù)述一下。引理一是兩個(gè)誠(chéng)實(shí)節(jié)點(diǎn)的樹在經(jīng)過了 f1 輪信息交換之后對(duì)于任意一條不包含故障節(jié)點(diǎn)的路徑它們記錄的值是相同的。原因很簡(jiǎn)單因?yàn)檫@條路徑上的每個(gè)節(jié)點(diǎn)都是誠(chéng)實(shí)的它們的轉(zhuǎn)述不會(huì)篡改信息所以無論從哪個(gè)誠(chéng)實(shí)節(jié)點(diǎn)去看這條路徑得到的結(jié)果都是一致的。引理二是如果故障節(jié)點(diǎn)試圖在兩條包含它的路徑上分別傳遞不同的值那么這兩條路徑必然會(huì)被某個(gè)誠(chéng)實(shí)節(jié)點(diǎn)的剪枝操作識(shí)別出來即使沒有識(shí)別出來多數(shù)投票也會(huì)把那個(gè)被篡改的分支淹掉。這個(gè)結(jié)論要?dú)w功于路徑交集的上限故障節(jié)點(diǎn)出現(xiàn)的次數(shù)有限它不可能同時(shí)壓過所有誠(chéng)實(shí)節(jié)點(diǎn)匯合而成的信息主流。這個(gè)證明思路對(duì)我最大的啟發(fā)是它不是去證明“每個(gè)節(jié)點(diǎn)都能準(zhǔn)確識(shí)別出故障節(jié)點(diǎn)”而是證明“即便某些故障節(jié)點(diǎn)沒有被識(shí)別出來多數(shù)決策的結(jié)果也完全一致”。這種從“結(jié)果一致性”出發(fā)的證明思路在工程上非常實(shí)用。因?yàn)楝F(xiàn)實(shí)項(xiàng)目中我們很少能精確定位哪臺(tái)機(jī)器出了故障很多時(shí)候只能確定“這群數(shù)據(jù)里混了臟數(shù)據(jù)”但只要我們能在輸出層面達(dá)成一致系統(tǒng)照樣可以對(duì)外提供正確服務(wù)。3.3 同步假設(shè)與 f1 輪的實(shí)際意義為什么恰好是 f1 輪而不是 f 輪或者 f2 輪可以從兩個(gè)方向理解。從信息傳播的角度看每一輪都讓每個(gè)節(jié)點(diǎn)的“視野”向外擴(kuò)展一層。要做到所有誠(chéng)實(shí)節(jié)點(diǎn)的視圖足夠交疊必須讓每條消息有足夠的時(shí)間穿過由誠(chéng)實(shí)節(jié)點(diǎn)組成的“信息骨干”。f 個(gè)故障節(jié)點(diǎn)最多可以沿路徑打斷 f 次所以需要 f1 次傳播才能確保至少存在一條完整的誠(chéng)實(shí)路徑把某個(gè)值從發(fā)起者傳到每個(gè)誠(chéng)實(shí)節(jié)點(diǎn)的視圖中。從異步邊界來看如果只看 f 輪故障節(jié)點(diǎn)有可能在最后一輪之前一直保持沉默讓所有誠(chéng)實(shí)節(jié)點(diǎn)都以為它不存在然后在最后一輪突然向部分節(jié)點(diǎn)發(fā)送不同的消息造成混亂。f1 輪就保證了一個(gè)故障節(jié)點(diǎn)制造的矛盾即使發(fā)生也有剩余輪次被誠(chéng)實(shí)節(jié)點(diǎn)的交叉驗(yàn)證暴露出來。工程上做超時(shí)設(shè)置的時(shí)候也可以參考這個(gè)概念如果容忍一次故障至少需要兩個(gè)有效的通信來回才能讓系統(tǒng)穩(wěn)定地達(dá)成一致。4. EIG 的代價(jià)與現(xiàn)實(shí)世界的取舍4.1 消息量是指數(shù)級(jí)的不是開玩笑EIG 的完整運(yùn)行需要多少消息粗略估算一下每輪每個(gè)節(jié)點(diǎn)都要向其余 n-1 個(gè)節(jié)點(diǎn)廣播自己當(dāng)前樹中的全部路徑信息而樹中的路徑數(shù)量隨著輪數(shù)指數(shù)增長(zhǎng)。在 f1 輪結(jié)束時(shí)總消息量大約在 O(n^(f1)) 級(jí)別確切說是指數(shù)級(jí)復(fù)雜度。對(duì)于 f1n4 的小案例這個(gè)數(shù)字還勉強(qiáng)能接受但如果系統(tǒng)有 100 個(gè)節(jié)點(diǎn)、需要容忍 10 個(gè)拜占庭故障消息量就會(huì)膨脹到天文數(shù)字這在實(shí)際網(wǎng)絡(luò)里完全不可行。這就是為什么 1980 年論文給出了一個(gè)理論上漂亮的算法但工程上很少直接實(shí)現(xiàn) EIG。現(xiàn)代 BFT 算法比如 PBFT會(huì)把通信復(fù)雜度降到多項(xiàng)式級(jí)別核心手段是引入“視圖”和“主節(jié)點(diǎn)”讓每一輪不再?gòu)V播整棵樹路徑而是廣播摘要和簽名。但 PBFT 的正確性論證里依然有 EIG 的影子——只不過它把“指數(shù)路徑冗余”換成了“多項(xiàng)式多輪交互 數(shù)字簽名”。如果你在做教學(xué)或者仿真實(shí)驗(yàn)我建議還是先實(shí)現(xiàn)一遍 EIG。它的代碼量不大但能很直觀地看到拜占庭故障對(duì)共識(shí)過程的攪動(dòng)作用。我在自己的測(cè)試環(huán)境里用 Python 寫過 n5、f1 的 EIG 模擬最后生成的樹結(jié)構(gòu)信息非常清晰比直接看 PBFT 的論文實(shí)現(xiàn)容易理解得多。4.2 EIG 與區(qū)塊鏈共識(shí)的關(guān)系很多人問既然 EIG 這么古老跟現(xiàn)在區(qū)塊鏈里的共識(shí)算法有什么關(guān)系其實(shí)關(guān)系非常大。中本聰共識(shí)工作量證明本質(zhì)上是通過算力投票來替代拜占庭節(jié)點(diǎn)之間的交互驗(yàn)證它能在開放網(wǎng)絡(luò)里工作是因?yàn)椤坝?jì)算資源”約束取代了“故障節(jié)點(diǎn)上限”約束。而在聯(lián)盟鏈或許可鏈里PBFT 類算法動(dòng)輒要求 n 3f這正是從這篇論文繼承下來的基礎(chǔ)結(jié)論。哪怕以太坊的 Casper FFG 這類基于權(quán)益證明的共識(shí)也無法繞開對(duì)拜占庭節(jié)點(diǎn)比例的嚴(yán)格假設(shè)。從另一個(gè)角度看EIG 的信息收集思想在“跨鏈驗(yàn)證”和“輕節(jié)點(diǎn)驗(yàn)證”中也有應(yīng)用。很多跨鏈協(xié)議要求中繼鏈對(duì)目標(biāo)鏈的狀態(tài)進(jìn)行多路采樣驗(yàn)證實(shí)際上就是不同路徑上的節(jié)點(diǎn)分別匯報(bào)自己看到的狀態(tài)摘要而合約根據(jù)多數(shù)一致的結(jié)果做出最終判斷。這和 EIG 樹中從多個(gè)路徑匯聚信息再多數(shù)投票的邏輯是相通的。4.3 什么時(shí)候 EIG 是“劃算”的雖然指數(shù)級(jí)消息復(fù)雜度很嚇人但 EIG 有個(gè)常被人忽略的優(yōu)勢(shì)它不需要數(shù)字簽名。該算法只依賴多輪交互和路徑交叉就解決了拜占庭問題這在 1980 年是一個(gè)非常大的貢獻(xiàn)因?yàn)楫?dāng)時(shí)的密碼學(xué)開銷被認(rèn)為非常昂貴。如果你的應(yīng)用場(chǎng)景滿足以下條件EIG 反而可能是一個(gè)值得考慮的方案節(jié)點(diǎn)數(shù)量很小比如 4 到 8 個(gè)故障輪次很少通常只需要容忍 1 個(gè)故障網(wǎng)絡(luò)是同步的通信延遲有界開發(fā)環(huán)境難以引入復(fù)雜的密碼學(xué)或者簽名庫(kù)。在這種極限場(chǎng)景下EIG 比 PBFT 更簡(jiǎn)單、更容易證明正確性也不需要維護(hù)視圖切換邏輯。我自己試過在一個(gè)低功耗嵌入式采集系統(tǒng)里模擬過類似流程節(jié)點(diǎn)之間用共享內(nèi)存通信最后的一致性效果非常穩(wěn)定代碼量也控制在幾百行以內(nèi)。5. 從 1980 年的論文到現(xiàn)代工程我讀 EIG 的四個(gè)實(shí)際收獲5.1 故障越“聰明”方案越要依賴結(jié)構(gòu)而不是技巧早期我也嘗試過用啟發(fā)式規(guī)則來識(shí)別拜占庭故障比如“如果某個(gè)節(jié)點(diǎn)的值連續(xù)多次與其他節(jié)點(diǎn)不同就標(biāo)記為故障”。這種思路在故障節(jié)點(diǎn)行為固定的時(shí)候有效但只要故障節(jié)點(diǎn)稍微聰明一點(diǎn)輪流對(duì) A 撒謊、對(duì) B 說實(shí)話、對(duì) C 沉默啟發(fā)式規(guī)則就會(huì)被繞過。EIG 給了一個(gè)徹底的方法論轉(zhuǎn)向不要試圖猜誰在撒謊而是通過讓信息沿著不相交的路徑匯聚使得撒謊行為在數(shù)學(xué)上不可能不被多數(shù)淹沒。這就像審計(jì)賬目時(shí)不靠肉眼辨別哪張發(fā)票是假的而是強(qiáng)制要求同一筆交易必須經(jīng)多個(gè)獨(dú)立渠道交叉驗(yàn)證假發(fā)票自然就被結(jié)構(gòu)隔離出來了。這個(gè)思路對(duì)架構(gòu)設(shè)計(jì)有很強(qiáng)的指導(dǎo)性——與其強(qiáng)化單點(diǎn)檢測(cè)不如設(shè)計(jì)信息冗余的結(jié)構(gòu)。5.2 同步假設(shè)不是理論家的玩具而是系統(tǒng)的兜底每次我跟團(tuán)隊(duì)討論系統(tǒng)設(shè)計(jì)時(shí)都會(huì)反復(fù)強(qiáng)調(diào)延遲上界timeout和輪次設(shè)計(jì)。在無界延遲的網(wǎng)絡(luò)里任何確定性共識(shí)算法都不可能同時(shí)滿足安全性和活性這是 FLP 定理的結(jié)論。EIG 雖然是 1980 年的論文但它已經(jīng)把“同步假設(shè)”作為整個(gè)協(xié)議運(yùn)行的前提你能在最原始的版本里看到一個(gè)概念的最純粹形態(tài)。現(xiàn)代工程中我們常用超時(shí)和重試來近似同步假設(shè)但要記住超時(shí)設(shè)置的背后就是 f1 輪思想的實(shí)踐。如果超時(shí)太短誠(chéng)實(shí)節(jié)點(diǎn)被誤判為故障節(jié)點(diǎn)如果超時(shí)太長(zhǎng)系統(tǒng)活性受損。理解了 EIG 對(duì)輪數(shù)的敏感性你在調(diào)參的時(shí)候至少能意識(shí)到這不是單純“拍腦袋定 10 秒”的問題。5.3 多數(shù)決策之前必須先有“可比較的信息視圖”很多人寫一致性協(xié)議時(shí)直接就對(duì)各節(jié)點(diǎn)的上報(bào)值做多數(shù)投票但別忘了投票的前提是大家投票的對(duì)象一致。EIG 樹的第一個(gè)作用其實(shí)是“對(duì)齊信息視圖”經(jīng)過 f1 輪交換之后每個(gè)誠(chéng)實(shí)節(jié)點(diǎn)都有了一棵結(jié)構(gòu)相同的樹差異只在于具體路徑上的值可能被故障節(jié)點(diǎn)污染。這為后面的多數(shù)投票建立了一個(gè)公共坐標(biāo)系。我在實(shí)際項(xiàng)目里踩過一個(gè)坑兩個(gè)數(shù)據(jù)中心各自維護(hù)一個(gè)本地狀態(tài)版本號(hào)然后試圖在它們之間做“多數(shù)投票”決定哪個(gè)版本應(yīng)該保留。結(jié)果發(fā)現(xiàn)兩個(gè)中心看到的節(jié)點(diǎn)列表都不一樣投票根本沒法進(jìn)行。后來我引入了一個(gè)虛擬的公共歷史結(jié)構(gòu)相當(dāng)于 EIG 樹的簡(jiǎn)化版先讓所有節(jié)點(diǎn)對(duì)齊自己的視圖再做多數(shù)判斷功能才穩(wěn)定下來。5.4 老論文的數(shù)學(xué)工具到今天依然可以用EIG 論文里用到的路徑、樹、交叉驗(yàn)證、多數(shù)合并這些工具本質(zhì)上是一套組合數(shù)學(xué)方法。今天你在實(shí)現(xiàn) Sharding 分片、數(shù)據(jù)副本修復(fù)、甚至多層聯(lián)邦學(xué)習(xí)聚合的時(shí)候都會(huì)遇到類似的“信息來自多個(gè)源頭需要融合確認(rèn)”的問題。一個(gè)人如果只懂得用最終一致性或者 Paxos 這類現(xiàn)成協(xié)議遇到新的場(chǎng)景大概率會(huì)抓瞎反過來如果掌握了 EIG 的這種樹狀信息收集和路徑?jīng)_突識(shí)別框架自研一個(gè)輕量級(jí)拜占庭容錯(cuò)協(xié)議并不是難事。我讀這篇論文的最大感受是它把“共識(shí)”這個(gè)看似抽象的問題轉(zhuǎn)化成了“樹的構(gòu)造與樹的修剪”這種非常具象的算法問題。如果你愿意動(dòng)手實(shí)現(xiàn)建議從 n4、f1 的無簽名版本開始把樹的層次打印出來逐步觀察故障節(jié)點(diǎn)在樹上制造的分歧。把這張圖看明白之后再去看 PBFT、Tendermint、HotStuff都會(huì)覺得順理成章。最后再分享一個(gè)小技巧做論文筆記時(shí)不要只摘抄結(jié)論盡量把每一輪的消息示例手動(dòng)走一遍。EIG 這種輪次型算法親手在紙上畫一遍樹勝過讀十遍證明。你一旦理解了“路徑”和“交集”這兩個(gè)概念整個(gè)分布式系統(tǒng)里的拜占庭問題就再也不會(huì)繞暈?zāi)懔恕?