我們已經聽過很長一段時間了，在同步網絡中可以達到50％容錯的共識，其中任何誠實節點廣播的消息都保證在某個已知時間段內被所有其他誠實節點接收（如果攻擊者有 超過50％，它們可以執行“51％攻擊”，并且對于任何此類算法都有類似的功能）。 我們也聽說很長一段時間，如果你想放寬同步假設，并且有一個“異步安全”的算法，最大可實現的容錯率下降到33％（PBFT，Casper FFG等都屬于這個 類別）。 但是你知道嗎，如果你添加更多的假設（具體來說，你需要觀察者也積極地觀察共識，而不僅僅是事后才下載它的輸出），你可以將容錯率一直提高到99％？
事實上，這一點早已為人所知；萊斯利·蘭波特1982年的著名論文“拜占庭將軍問題”包含算法的描述。以下是我試圖以簡化的形式描述和重新表述該算法的嘗試。
假設有N個節點，我們將其標記為0....N-1，有一個已知的界限D關于網絡延遲加上時鐘差異(例如。D=8秒)。每個節點都有能力在T時刻同時發布一個值。 (惡意節點當然可以早于或晚于T)所有節點等待(N-1) * D秒，運行以下進程。定義x : i作為“價值”x節點簽名i”, x : i : j作為“價值”x由i，這個值和簽名一起由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）。
現在，讓我們探索一下為什么會這樣。我們需要證明的是，如果一個誠實節點已經看到了一個特定的值(有效地)，那么每個其他誠實節點也看到了這個值(如果我們證明了這一點，那么我們就知道所有誠實節點都運行著相同的選擇函數，因此它們將輸出相同的值)。假設任何誠實的節點接收到消息v：i [1]：...：i [k]他們認為有效（即，它在T + k * D時刻之前到達）。 假設x是單個其他誠實節點的索引。 x是{i [1] ... i [k]}的一部分，或者不是。
●在第一種情況下（比如說這個消息的x = i [j]），我們知道誠實節點x已經廣播了該消息，并且他們這樣做是為了響應他們在時刻T之前收到的帶有j-1簽名的消息。因此他們在T+（j-1）* D時廣播他們的消息，因此在時刻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之前將其廣播到一個誠實的節點，并且誠實節點將發出附有其簽名的消息，該具有k + 1個簽名的消息的超時的消息將在時刻T +（k + 0.5）* D之前到達所有其他觀察者。
對其他協商一致算法的改進
假設我們有一些其他的一致性算法（例如，PBFT，Casper FFG，基于鏈的PoS），其輸出可以偶爾在線觀察者看到（我們稱之為閾值相關的一致性算法，與上面的算法相反） ，我們將其稱為延遲相關的一致性算法。假設依賴于閾值的一致性算法連續運行，其模式是不斷地將新塊“最終化”到鏈上（即，每個最終值指向一些先前的最終值作為“父”;如果存在一系列指針 A - > ... - > B，我們稱A為B的后代。我們可以將依賴于延遲的算法改造到這個結構上，讓總是在線的觀察者能夠在檢查點上獲得一種“強大的終結性”，容錯率達到95％（你可以通過增加更多的驗證器和任意方式將其任意接近100％） 要求這個過程需要更長的時間）。
每次時間達到4096秒的倍數時，我們運行與延遲相關的算法，選擇512個隨機節點參與該算法。有效方案是由閾值相關算法最終確定的任何有效的值鏈。如果節點在具有k個簽名的時間T + k * D（D = 8秒）之前看到一些最終值，則它將鏈接到其已知鏈的集合中并且重新廣播它并添加其自己的簽名; 觀察者像以前一樣使用T +（k-0.5）* D的閾值。
結尾處使用的“選擇”函數很簡單：
●最后確定的最終值，如果不是上一輪中已商定的最終值的后代，就會被忽略。
●無效的最終值將被忽略。
●若要在兩個有效的最終值之間進行選擇，選擇一個哈希值較低的值。
如果5％的驗證器是誠實的，那么只有大約1/1萬億的機會512個隨機選擇的節點中沒有一個是誠實的，因此只要網絡延遲加上時鐘差異小于D / 2，上述算法 即使由于閾值相關算法的容錯被破壞而呈現多個沖突的最終值，也將工作，正確地協調某些單個最終值的節點。
如果滿足閾值相關一致性算法的容錯（通常為50％或67％誠實），那么依賴于閾值的一致性算法將不會最終確定任何新檢查點，或者它將最終確定彼此兼容的新檢查點 （例如，一系列檢查點，其中每個檢查點指向前一個作為父項），因此即使網絡延遲超過D / 2（或甚至D），因此參與延遲相關算法的節點也不同意它們的值 接受，他們接受的價值仍然保證是同一個鏈的一部分，因此沒有實際的分歧。 一旦延遲在未來一輪恢復正常，延遲相關的共識將恢復“同步”。
如果閾值相關和延遲相關的共識算法的假設同時（或在連續輪次中）被破壞，則算法可以分解。 例如，假設在一輪中，閾值依賴共識最終確定Z - > Y - > X并且延遲依賴共識在Y和X之間不一致，并且在下一輪中，閾值依賴共識最終確定X的后代W，其中 不是Y的后代; 在延遲相關的共識中，同意Y的節點將不接受W，但是同意X的節點將接受。 但是，這是不可避免的; 超過1/3容錯的安全欠不同步共識的不可能性是拜占庭容錯理論中眾所周知的結果，即使允許同步假設但假設離線觀察者也不可能超過1/2容錯。
