作者：Vitalik Buterin（V神）
翻譯 | Katie,責編 | 晉兆雨
出品 | 區塊鏈大本營
頭圖 |付費下載於視覺中國
很長一段時間以來，我們一直聽說在同步網路中,實現50%容錯的共識是有可能的。在同步網路中，任何可信節點廣播的訊息都可以保證在某個已知時間段內被所有其它可信節點接收。
如果攻擊者超過50%，他們就可以執行“51%攻擊”，對於區塊鏈上同型別的任何演算法都有可能出現類似的情況。
我們也一直聽過這樣的說法：如果你想放鬆同步假設，並且擁有一種“非同步下安全”的演算法，最大可達到的容錯率可下降到33% (PBFT、Casper FFG等都屬於此類)。
然而，如果新增更多假設(具體來說，你不僅需要觀察者來關注那些不積極參與共識但關心其輸出的使用者，也要積極地關注共識，而不僅僅是在結果出現後下載其輸出)，這樣可以把容錯率一路提高到99%嗎?
事實上，這一點 早已人盡皆知。萊斯利·蘭伯特（Leslie Lamport）1982年在著名的談及“拜占庭一般問題”的論文中包含了對演算法的描述。下面我將嘗試用簡化的形式重新來描述和表述這個演算法。
假設有N個參與共識的節點，每個人都提前同意這些節點代表誰(根據上下文，它們可以由可信方選擇，或者如果需要更強的去中心化程度，可以透過一些工作證明或利害關係進行證明)。
我們把這些節點標記為0…N-1。另外，還假設網路延遲和時鐘差異上有一個已知的限制D。（例如，D = 8秒)。每個節點都有能力在T時刻釋出值(惡意節點當然可以早於T或晚於T地釋出值)。
所有節點等待(N - 1)∙D秒，執行如下程序。定義x: i為“節點i簽名的值x”，x: i: j為“節點i簽名的值x，並且x與j一起簽名”，等等。在第一階段發表的提案將採用v的形式: i的形式為一些v和i，其中包括提出該提案的節點的簽名。
如果一個驗證器i收到一些訊息v: i[1]:…: i[k]， 其中i[1]:…:i[k]是已經按順序對訊息進行了簽名的索引列表（只是v本身會算作k = 0,而v:i則為k = 1),那麼驗證程式檢查(i)的時間將小於T + k∙D,同時他們尚未看到包含以下內容的有效訊息;如果兩項檢查均透過了，則會發布v: i[1]:…: i[k]: i。
在T + (N - 1)∙D時，節點停止監聽。此時，就可以保證所有的可信節點都“有效地看到了”相同的一組值。
如果問題要求選擇一個值，則可以使用一些“選擇”函式從他們看到的值中選擇一個值（例如採用雜湊值最低的值）。然後節點可以就該值達成共識。
現在，讓我們來探究一下為什麼這種方式有效。我們需要證明的是,如果一個誠實節點（有效地）看到了特定的值,然後其它的誠實節點也看到該值(如果我們證明了這一點,那麼我們知道所有誠實節點都看到了同一組值,因此如果所有誠實節點都執行相同的選擇功能,他們會選擇相同的值)。
假設任何誠實節點收到一條訊息v: i[1]:…i[k]，他們認為是有效的。在時間T + k∙D之前到達)，假設x是另一個誠實節點的索引。x要麼是i[1]的一部分:…要麼不是。
在第一種情況下(對於此訊息，x=i[j]),我們知道誠實節點x已經廣播該訊息,他們這樣做是為了響應他們在時間T+（j - 1）·D之前收到的帶有j-1簽名的訊息。此時他們廣播了他們的訊息,那麼所有誠實節點一定都會在時間T + j∙D前收到訊息。
在第二種情況下，由於誠實節點在時間T + k∙D之前看到訊息，那麼它們就會用自己的簽名傳播訊息，並保證包括x在內的所有人都會在時間T + (k + 1)∙D之前看到它。
注意，該演算法使用新增自己簽名的行為作為訊息超時的一種“碰撞”。正是這種能力保證了一個誠實的節點如果及時看到了訊息，那它們也可以確保其它所有節點也能及時看到訊息，因為“準時”的定義增加的時間超過了每新增一個簽名的網路延遲。
在一個節點是誠實的情況下，我們能否保證被動的觀察者(比如關心結果的非共識參與節點)也可以看到結果。
按照計劃，存在一個問題。假設一個指揮官和k(惡意)驗證器的某個子集生成一條訊息v: i[1]:…i[k]，並且在T + k∙D前廣播給一些受害者，受害者認為訊息是“準時”,但當他們轉發時,訊息只會在T + k∙D之後達到所有的已經協商一致的誠實節點,而所有協商一致的誠實節點將會拒絕它。
但我們可以堵住這個洞，提出一個新的約束：要求D在兩倍的網路延遲加上時間差。然後我們給觀察者一個不同的超時:觀察者接受v: i[1]:…i[k]必須在 T + (k - 0.5)∙D之前。
現在，假設觀察者看到一條訊息並接受了它。他們能夠在時間T + k∙D之前將其廣播到一個誠實節點,並且誠實節點將釋出帶有簽名的訊息,該訊息將在T + D (k + 0.5)之前到達所有其它觀察者，同時帶有k + 1個簽名的訊息將會超時。
改進其它共識演算法
理論上講，上述演算法可以作為獨立的共識演算法使用，甚至可以用於執行權益證明的區塊鏈。
第N + 1輪共識的驗證器集合本身可以在第N輪共識中被決定(例如，每輪共識也可以接受“存款”和“取款”交易，如果接受並正確簽名，將新增或刪除驗證器後進入下一輪)。
需要新增的主要額外成分是另一種機制，用於決定允許提議區塊的提名者(例如。每輪可以有一個指定的提名者)。它也可以被修改為用作工作證明的區塊鏈，允許參與共識的節點透過公鑰釋出工作解決方案的證明，同時透過簽名實時地“宣告自己”。
然而，同步假設是非常強大的，所以我們希望在不需要超過33%或50%容錯的情況下，無需同步假設也能工作。有一種方法可以做到這一點。
假設我們有一些其它的共識演算法(例如，PBFT, Casper FFG，基於鏈的PoS)，其輸出可以被偶爾線上的觀察者看到(我們稱之為閾值依賴的共識演算法，而上文所述的演算法我們稱之為延遲依賴的共識演算法)。
假設閾值依賴的共識演算法持續執行，在一種模式下，它將不斷地“確定”新的區塊到鏈上。例如:每一個最終值都將指向一個“父”;如果有一個指標序列a→…→B，我們稱A為B的後裔。
我們可以在這種結構上改進依賴於延遲的演算法，讓總是線上的觀察者能夠訪問檢查點上的一種“有可能結果”，容錯性約為95%（也可以透過新增更多的驗證器和要求使用花費更長時間的過程來將容錯性推進至100%）。
每當時間達到4096秒的倍數時，我們就執行依賴於延遲的演算法，選擇512個隨機節點來參與演算法。
一個有效的建議是由閾值相關演算法最終確定的任何有效的值鏈。如果一個節點在時間T + k∙D (D = 8秒)之前看到有k個簽名的某個最終值，則接受該鏈進入它的已知鏈集中，並新增自己的簽名進行重新廣播它;觀察者像以前一樣使用T + (k - 0.5)∙D的閾值。
最後使用的“選擇”函式很簡單:
忽略不是在前一輪中已經商定的最終確定值的後代的值
忽略最終的無效值
在兩個有效的最終值中進行選擇時，選擇雜湊值較低的那個
如果5%的驗證器是誠實的,那麼隨機選擇的 512 個節點中，只有大約 1 萬億分之一的機會是誠實的，因此當上述演算法工作，將會協調得出單一最終值的節點。
如果閾值依賴的共識演算法的容錯性被滿足(通常50%或67%的節點是誠實的)，那麼閾值依賴的共識演算法將不會確定任何新的檢查點，或者它將確定最終彼此相容的新檢查點(例如，每個檢查點都指向前一個檢查點作為父檢查點)。
因此，參與依賴於延遲的演算法的節點不會同意它們接受的值，它們接受的值仍然保持為同一鏈的一部分，不存在沒有實際的分歧。一旦延遲在未來的某個回合恢復正常，依賴於延遲的共識將恢復“同步”。
如果依賴閾值和依賴延遲的共識演算法的假設同時被打破(或在連續的兩輪中被打破)，那麼演算法就會分解。例如,假設在一輪中,閾值依賴共識最終確定Z→X→Y，而延遲以來共識在X,Y之間意見不一，那麼共識將會在不達成協議情況下結束。下一輪閾值依賴共識將會在最終確定W不源於 X，且X不源於Y的情況下結束;在依賴延遲的共識中，同意Y的節點不會接受W，而同意X的節點會。然而，這是不可避免的;非同步下的安全共識是不可能的。
容錯是拜占庭容錯理論中一個眾所周知的結論，就像很多的不可能事件一樣，容錯甚至在觀察器離線情況下允許同步假設。
*本文僅代表作者個人觀點，不構成任何投資建議，不代表CSDN任何立場。
原文連結：
https://hackernoon.com/how-to-achieve-99percent-fault-tolerant-consensus-n25b31mr
本文由CSDN翻譯，轉載請註明出處
