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