我們已經聽過很長一段時間了，在同步網絡中可以達到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容錯。
內容來源：區塊鏈兄弟
作者：V神
