我們已經聽過很長一段時間了，在同步網路中可以達到50％容錯的共識，其中任何誠實節點廣播的訊息都保證在某個已知時間段內被所有其他誠實節點接收（如果攻擊者有更超過50％，就可以執行“51％的攻擊”，而有這種用於這種型別的任何演算法）的類似物。我們也聽說很長一段時間，如果你想放寬同步假設，並且有一個“非同步安全”的演算法，最大可實現的容錯率下降到33％（PBFT，Casper FFG等都屬於這個類別）。但是你知道嗎，如果你新增更多的假設（具體來說，你需要觀察者，即。如果使用者沒有積極參與共識但關心其輸出，也要積極觀察共識，而不僅僅是事後下載其輸出），您可以將容錯率一直提高到99％？
事實上，這已經知道了很長時間; Leslie Lamport著名的1982年論文“The Byzantine Generals Problem”（連結在這裡）包含了演算法的描述。以下是我嘗試以簡化形式描述和重新構造演算法。
假設存在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:ik = 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但不z到達節點2，並且沒有按時到達節點。在時間T + D，節點0和2重播他們已經看到了，他們還沒有廣播的所有值，但增加了他們的簽名上（x與w節點0，y節點2）。這兩個節點誠實看到{x, y, w}。
如果問題需要選擇一個值，他們可以使用一些“選擇”函式從他們看到的值中選擇一個值（例如，他們採用具有最低雜湊的值）。然後節點可以就此值達成一致。
現在，讓我們來探討一下為什麼會這樣。我們需要證明的是，如果一個誠實的節點已經看到了一個特定的值（有效地），那麼每個其他誠實的節點也看到了這個值（如果我們證明了這一點，那麼我們知道所有誠實的節點都看到了相同的一組值，所以如果所有誠實節點都執行相同的選擇函式，它們將選擇相同的值）。假設任何誠實節點接收v : i[1] : ... : i[k]到他們認為有效的訊息（即，它在時間之前到達T + k * D）。假設x是單個其他誠實節點的索引。要麼x是其中的一部分，{i[1] ... i[k]}要麼不是。
在第一種情況下（比如說x = i[j]這個訊息），我們知道誠實節點x已經廣播了該訊息，並且他們這樣做是為了響應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，並且誠實的節點將發出帶有其簽名的訊息，該訊息將在時間之前到達所有其他觀察者T + (k + 0.5) * D，具有k+1簽名的訊息的超時。
改造其他共識演算法
理論上，上述內容可以用作獨立的一致性演算法，甚至可以用於執行股權證明區塊鏈。共識的第N + 1輪驗證器本身可以在共識的第N輪中決定（例如，每輪共識也可以接受“存款”和“撤銷”交易，如果接受並正確簽署將會增加或刪除驗證器進入下一輪）。需要新增的主要附加成分是用於決定允許誰提出阻止的機制（例如，每輪可以有一個指定的提議者）。它還可以被修改為可用作工作證明區塊鏈，允許參與共識的節點透過在簽名的同時在其公鑰之上釋出工作證明解決方案來實時“宣告自己”。用它的訊息。
但是，同步假設非常強，因此我們希望能夠在沒有超過33％或50％容錯的情況下在沒有它的情況下工作。有一種方法可以實現這一目標。假設我們有一些其他的一致性演算法（例如，PBFT，Casper FFG，基於鏈的PoS），其輸出可以偶爾線上觀察者看到（我們稱之為閾值相關的一致性演算法，與上面的演算法相反） ，我們稱之為延遲依賴共識演算法）。假設依賴於閾值的一致性演算法連續執行，其模式是不斷地將新塊“最終化”到鏈上（即，每個最終值指向一些先前的最終值作為“父”;如果存在一系列指標A -> ... -> B，我們稱A 為B 的後代。
我們可以將依賴於延遲的演算法改造到這個結構上，讓總是線上的觀察者能夠在檢查點上獲得一種“強大的終結性”，容錯率達到95％（你可以透過增加更多的驗證器和任意方式將其任意接近100％）要求這個過程需要更長的時間）。
每次時間達到4096秒的倍數時，我們執行與延遲相關的演算法，選擇512個隨機節點參與演算法。有效提議是由閾值相關演算法最終確定的任何有效值鏈。如果一個節點在T + k * D帶有k簽名的時間（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。但是，這是不可避免的; 具有超過1/3容錯性的安全欠不同步共識的不可能性是a眾所周知拜占庭容錯理論的結果，即使允許同步假設，但假設離線觀察者不可能超過1/2容錯。
