引言：V神近日發佈了名為“99%容錯共識”的新共識算法，該算法只要求1%的節點保持誠實，即使99%的節點全部選擇作惡，區塊鏈網絡也能正常運轉。
原文翻譯：
一直以來我們就知道，在一個同步的網絡中能夠達到50％容錯的共識，在這個網絡中的任何誠實節點廣播的消息都保證在某個已知時間段內被所有其他誠實節點接收（如果攻擊者有超過50％，它們可以執行“51％攻擊”，並且對於任何此類算法都有類似的功能）。並且我們也很久就聽說過，如果你想放寬同步假設，並且有一個“異步安全”的算法，最大可實現的容錯率會下降到33％（PBFT，Casper FFG等都屬於這個類別）。但是你知道嗎，如果你添加更多的假設（具體來說，你需要假設觀察者也積極地觀察共識，而不僅僅是事後才下載其輸出），是否可以將容錯率一直提高到99％呢？
事實上，這很久之前就已經被認識到了:Leslie Lamport1982年那篇著名的論文“The Byzantine Generals Problem”（鏈接https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf）裡就有對這種算法的描述。下面我將嘗試簡述並重構這種算法。
假設存在N個節點，我們將其標記為0……N-1，並且網絡延遲加時間差（例如，D=8秒）的值存在一個已知的界限D。每個節點都能夠在時間T（惡意節點當然可以提前或早於T的值）發佈值。所有節點等待（N-1）*D秒並運行以下過程：將x：i定義為“由節點i簽名的值x”，將x：i：j定義為“由i簽署的值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；（ii）它們還沒有看到一條包含v的有效消息。如果兩個檢查都通過，他們就會發布v：i[1]：…：i[k]：i。
在時間T+（N-1）*D，節點停止收聽，並且他們使用一些“選擇”函數從他們看到的有效消息的所有值中選擇一個值（例如，它們通常取最高值）。然後他們決定這個值。
節點1（紅色）是惡意的，節點0和2（灰色）是誠實的。一開始，兩個誠實的節點提出他們的建議y和x，攻擊者建議w和z遲到。w按時到達節點0但不到達節點2，並且z沒有按時到達兩個中的任何一個節點。在時間T+D，節點0和2重新廣播他們已經看到但還尚未廣播的所有值，但是卻在（x和w表示節點0，y表示節點2）上添加它們的簽名。兩個誠實的節點都看到{x，y，w}；然後他們可以使用一些標準選擇函數（例如按字母順序最高的y）。
現在，讓我們來探討一下為什麼會這樣。我們需要證明的是，如果一個誠實的節點已經看到一個特定的值（有效），那麼每個其他誠實的節點也看到了這個值（如果我們證明這一點，那麼我們知道所有誠實的節點都在運行相同的選擇函數，所以他們會輸出相同的值）。假設任何誠實的節點接收到它們認為有效（比如，它在時間T+k*D之前到達）的消息v：i[1]：…：i[k]。假設x是其他單個誠實節點的索引。x是{i[1]…i[k]}的一部分，或者不是。
- 在第一種情況下（比如說這個消息的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接受兩倍的網絡延遲加上時鐘差異的約束。然後我們對觀察者施加不同的超時：一個觀察者在時間T+（k-0.5）*D之前接受v：i[1]：….：i[k]。現在，假設觀察者看到一條消息並且接受。他們將能夠在時間T+k*D之前將其廣播到一個誠實的節點，並且誠實節點將會發出附有其簽名的消息，該消息將在時間T+（k+0.5）*D（具有k+1個簽名的消息超時）之前到達所有其他觀察者。
改造其他共識算法
假設我們有一些其他的一致性算法（例如，PBFT，Casper FFG，基於鏈的PoS），其輸出可以偶爾地被在線觀察者看到（我們稱之為閾值相關的一致性算法，與上面的算法相反），我們將其稱為延遲相關的一致性算法。假設依賴於閾值的一致性算法連續運行，其模式是不斷地將新塊“最終化”到鏈上（即，每個最終值指向一些先前的最終值作為“父”；如果存在一系列指針A->…->B，我們稱A為B的後代。我們可以將依賴延遲的算法改造到這個結構上，讓總是在線的觀察者能夠在檢查點上獲得一種“強大的終結性”，容錯率達到95％（你可以不斷地通過增加更多的驗證器或者要求這個過程使用更長時間的方式使其接近100％）。
每次當時間達到4096秒的倍數時，我們將運行依賴於延遲的算法，選擇512個隨機節點參與算法。有效提議是由閾值相關算法最終確定的任何有效值鏈。如果一個節點在具有k個簽名的時間T+k*D（D=8秒）之前看到一些最終值，則它會將鏈收納到其已知鏈的集合中並且重新廣播它並添加其自己的簽名；觀察者會像以前一樣使用T +（k-0.5）*D的閾值。
在結尾所使用的“選擇”函數很簡單：
- 不是已經同意在上一輪中作為最終值後代的最終值，將被忽略
- 無效的最終值將被忽略
- 要在兩個有效的最終值之間進行選擇，請選擇具有較低哈希值的值
如果5％的驗證器是誠實的，那麼512個隨機選擇的節點中沒有一個是誠實的概率只有大約1/1萬億，因此只要網絡延遲加上時鐘差異小於D/2，即使由於閾值相關算法的容錯被破壞而呈現多個衝突的最終值，上述算法也將依然有效運作，並正確地協調某些單個最終值的節點。
如果碰到滿足“閾值依賴”一致性算法的容錯（通常為50％或67％誠實），那麼依賴於閾值的一致性算法將不會最終確定任何新檢查點，或者它將最終確定彼此兼容的新檢查點（例如，一系列檢查點，它們中的每個檢查點都將前一個作為父項），因此即使網絡延遲超過D/2（或甚至D），並且當參與延遲相關算法的節點也不同意它們所接受的值，那麼他們接受的值仍然被保證是同一個鏈的一部分，因此沒有實際的分歧。一旦延遲在未來的某一輪中恢復正常，延遲相關的共識將恢復“同步”。
如果閾值依賴和延遲依賴共識算法的假設同時（或在連續輪次中）被破壞，則算法可能被破壞。例如，假設在同一輪中，閾值依賴共識最終確定Z→Y→X並且延遲依賴共識在Y和X之間不一致，並且在下一輪中，閾值依賴共識最終確定W是X的後代，而不是Y的後代；在延遲相關的共識中，同意Y的節點將不會接受W，但是同意X的節點將會接受W。然而這是不可避免的；超過1/3容錯的異步安全共識的不可能性是拜占庭容錯理論中的一個眾所周知的結果，就像大於1/2容錯的不可能性，即使允許假定設想也不會允許假定離線觀察者。
閱讀更多 幣和 的文章
