V神推薦99%容錯共識算法，也可改造其他共識算法區塊鏈
Vitalik最近在他的博客上發布了一篇名為《99%容錯共識算法指南》，并表示該算法由計算機科學家LeslieLamport發明。Vitalik對該共識進行了解釋，并對其調整以適用于區塊鏈環境中。
通常，所有區塊鏈共識算法，關心的是鏈的驗證者（即礦工）所做的事情。 Vitalik 建議，如果網絡流量的獨立觀察者（即只是用戶正在運行的區塊鏈客戶端，而不是礦工 / 驗證者）實時監視正在發生的事情，并注意消息何時出現，那么他們可以檢測到由礦工發起的 51％ 攻擊這種“犯規游戲”，這就可以提供額外的安全保障，來防范此類攻擊。
正如 Vitalik 自己所說，這一共識算法仍是經典拜占庭將軍問題。如果真的實現這種 1％一致性算法的方法，那么現在的 51% 攻擊將不會存在。Vitalik 在文中表示在此基礎上把各類經典分布式算法和加密算法改造應用于區塊鏈領域內，也將有可能獲得不錯的效果。
我們將 Vitalik Buterin 博客原文翻譯如下：
很長時間以來，我們都聽說過在同步網絡中有可能實現 50% 容錯共識，其中通過任何誠實節點廣播的消息保證能夠在某個已知時段內被所有其他誠實節點收到（如果攻擊者擁有超過 50% 的節點，他們能夠實施“51% 攻擊”，對于任何此類的算法來說，都有類似的情況）。
我們也一直聽說，如果您希望放寬同步假設，并有個“在異步下安全”的算法，那么最大可實現的容錯率下降到 33%（PBFT，Casper FFG 等都屬于這一類）。但是，如果增加更多的假設（具體來說，需要觀察者也積極地觀察共識，并且不只是事后才下載它的輸出），就能夠將容錯率一直提高到 99%。
事實上，這早已為人所知，Leslie Lamport 寫于 1982 年的著名論文《拜占庭將軍問題》描述了該算法。下面是我嘗試用簡化的形式描述和重構該算法。
假設有 N 個節點，我們分別用 0，……，N-1 來標識，并且在網絡延遲加上時鐘差異有個已知的界限 D（比如，D = 8 秒）。每個節點具有在時間 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[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 既沒有準時到達節點 0，也沒有準時到達節點 2。在 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)*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 個隨機節點參與到該算法。一個有效的提議是由閾值相關算法最終確定的任何有效鏈的值。如果一個節點在 T k * D (D = 8 秒) 時刻前看到一些最終確定具有 k 個簽名的值，它就把該鏈放到其已知鏈集合，并在添加了它自己的簽名后重新廣播它，觀察者像以前一樣使用 T (k – 0.5) * D 的閾值。
最后用到的“選擇”函數很簡單：
最終確定的值，如果不是那些在上一輪中已經同意成為最終確定的值的后代，將被忽略。
最終確定的無效值被忽略。
要在兩個最終確定的值之間做出選擇，就選擇具有更低哈希值的那個。
如果 5% 的驗證器是誠實的，那么只有大約一萬億分之一的概率隨機選到的 512 個節點沒有一個是誠實節點，并且只要網絡延遲加上時鐘差異小于 D/2，上述算法就有用，就算因為延時相關算法的缺省容錯率被破壞而呈現多個沖突的最終確定的值，也能正確地協調在某些單獨最終確定的值上的節點。
如果滿足閾值相關共識算法的默認容錯率（通常是 50%，或是 67% 誠實），那么閾值相關共識算法將不會最終確定任何新的檢查點，或者，它將最終確定那些相互兼容的新檢查點（即，一系列把前一個點作為父節點的檢查點），因此，即使網絡延遲超過 D/2（或 D），作為結果，參與延遲相關算法的節點不同意它們接受的值，它們接受的的值仍然被保證是同一個鏈上的一部分，因此，沒有實際的分歧。一旦在未來某一輪，延遲恢復正常，那么，延遲相關共識將回到“同步”狀態。
如果閾值相關和延遲相關共識算法的假設同時（或在連續的輪次中）被破壞，那么該算法可以崩潰。比如，假設在某一輪次，閾值相關共識算法最終確定 Z -> Y -> X，并且延遲相關共識算法在 Y 和 X 之間不一致，那么在下一輪次中，該閾值相關共識算法最終確定 X 的后代 W，其中 X 不是 Y 的后代；在該延遲相關共識算法中，那些跟 Y 一致的節點將不接受 W，但是，跟 X 一致的節點會接受 W。無論如何，這是不可避免的，在拜占庭容錯理論中，不存在超過 1/3 容錯率的安全同步共識，這是一個眾所周知的結果，因為即使允許同步假設，但是假設離線觀察者不可能超過 1/2 缺省容錯率。
1.TMT觀察網遵循行業規范，任何轉載的稿件都會明確標注作者和來源；
2.TMT觀察網的原創文章，請轉載時務必注明文章作者和"來源：TMT觀察網"，不尊重原創的行為TMT觀察網或將追究責任；
3.作者投稿可能會經TMT觀察網編輯修改或補充。
