麻豆国内精品欧美在线-麻豆国内精品久久久久久-麻豆国产在线观看一区二区-麻豆国产在线观看免费-麻豆国产原创-麻豆国产一区二区在线观看

正如 Vitalik 自己所說，這一共識(shí)算法仍是經(jīng)典拜占庭將軍問題。如果真的實(shí)現(xiàn)這種 1％一致性算法的方法，那么現(xiàn)在的 51% 攻擊將不會(huì)存在。Vitalik 在文中表示在此基礎(chǔ)上把各類經(jīng)典分布式算法和加密算法改造應(yīng)用于區(qū)塊鏈領(lǐng)域內(nèi)，也將有可能獲得不錯(cuò)的效果。

我們將 Vitalik Buterin 博客原文翻譯如下：

很長時(shí)間以來，我們都聽說過在同步網(wǎng)絡(luò)中有可能實(shí)現(xiàn) 50% 容錯(cuò)共識(shí)，其中通過任何誠實(shí)節(jié)點(diǎn)廣播的消息保證能夠在某個(gè)已知時(shí)段內(nèi)被所有其他誠實(shí)節(jié)點(diǎn)收到（如果攻擊者擁有超過 50% 的節(jié)點(diǎn)，他們能夠?qū)嵤?1% 攻擊”，對(duì)于任何此類的算法來說，都有類似的情況）。

我們也一直聽說，如果您希望放寬同步假設(shè)，并有個(gè)“在異步下安全”的算法，那么最大可實(shí)現(xiàn)的容錯(cuò)率下降到 33%（PBFT，Casper FFG 等都屬于這一類）。但是，如果增加更多的假設(shè)（具體來說，需要觀察者也積極地觀察共識(shí)，并且不只是事后才下載它的輸出），就能夠?qū)⑷蒎e(cuò)率一直提高到 99%。

事實(shí)上，這早已為人所知，Leslie Lamport 寫于 1982 年的著名論文《拜占庭將軍問題》描述了該算法。下面是我嘗試用簡(jiǎn)化的形式描述和重構(gòu)該算法。

假設(shè)有 N 個(gè)節(jié)點(diǎn)，我們分別用 0，……，N-1 來標(biāo)識(shí)，并且在網(wǎng)絡(luò)延遲加上時(shí)鐘差異有個(gè)已知的界限 D（比如，D = 8 秒）。每個(gè)節(jié)點(diǎn)具有在時(shí)間 T（惡意節(jié)點(diǎn)當(dāng)然能夠早于或晚于時(shí)間 T）發(fā)布一個(gè)值的能力。所有節(jié)點(diǎn)等待 (N - 1) * D 秒，運(yùn)行以下過程。定義 x : i 是“節(jié)點(diǎn) i 簽署的值 x”，x : i : j 是“節(jié)點(diǎn) i 簽署的值 x，并且由節(jié)點(diǎn) j 簽署該值和簽名”，等等。在第一個(gè)階段發(fā)布的提議以 v : i 的形式出現(xiàn)，代表某些 v 和 i，包含提出它的節(jié)點(diǎn)的簽名。

如果驗(yàn)證節(jié)點(diǎn) i 收到一些消息 v : i[1] : … : i[k]，其中 i[k] 是一個(gè)索引列表，這些索引已經(jīng)（順序）簽署了消息（只是 v 本身將計(jì)為 k = 0，并且 v:i 計(jì)為 k = 1），然后，驗(yàn)證器檢查（i）時(shí)間是否小于 T K * D，以及（ii）它們是否還沒看到一個(gè)有效的包含 v 的消息。如果這兩個(gè)驗(yàn)證都通過，那么，它們就發(fā)布 v : i[1] : … : i[k] : i。

在 T (N-1) * D 時(shí)刻，節(jié)點(diǎn)停止偵聽，它們使用一些“選擇”功能從所有它們已經(jīng)看到的有效消息中選擇一個(gè)值（比如，它們?nèi)∽罡叩模Ｈ缓螅鼈儧Q定這個(gè)值。

現(xiàn)在，我們來探究一下這個(gè)為什么可行。我們需要證明的是，如果一個(gè)誠實(shí)節(jié)點(diǎn)已經(jīng)看到一個(gè)特定值（有效的），然后，其他各個(gè)誠實(shí)節(jié)點(diǎn)也看到了該值（如果我們能證明這個(gè)，那么我們就知道所有的誠實(shí)節(jié)點(diǎn)在運(yùn)行同樣的選擇函數(shù)，因此它們會(huì)輸出相同的值）。假設(shè)任意一個(gè)誠實(shí)節(jié)點(diǎn)收到消息 v : i[1] : … : i[k]，它們認(rèn)為有效（即，它在 T k * D 時(shí)刻前到達(dá)）。 假設(shè) x 是單個(gè)其他誠實(shí)節(jié)點(diǎn)的索引。那么，x 要么是{i[1] … i[k]}的一部分，要么不是。

在第一種情況下（設(shè) x = i[j] 是這個(gè)消息），我們知道，誠實(shí)節(jié)點(diǎn) x 已經(jīng)廣播了該消息，并且它們這么做是為了響應(yīng)用在 T (j - 1)*D 時(shí)刻前收到的帶有 j – 1 個(gè)簽名的消息，于是，它們?cè)谀莻€(gè)時(shí)刻廣播了它們的消息，因此，在 T j * D 時(shí)刻前，所有誠實(shí)節(jié)點(diǎn)應(yīng)該收到了該消息。

在第二種情況下，由于誠實(shí)節(jié)點(diǎn)在 T k * D 時(shí)刻前看到了該消息，然后，它們將廣播帶著它們簽名的數(shù)據(jù)，并保證包括 x 在內(nèi)的每個(gè)節(jié)點(diǎn)都會(huì)在 T (k 1) * D 時(shí)刻前看到該消息。

注意，該算法使用添加自己簽名的操作，作為一種在超時(shí)消息上的“撞擊”，并且這種能力保證，如果一個(gè)誠實(shí)節(jié)點(diǎn)看到準(zhǔn)時(shí)的消息，它們可以確保其他任何節(jié)點(diǎn)也能準(zhǔn)時(shí)看到該消息，因?yàn)椤皽?zhǔn)時(shí)”的定義隨著每個(gè)增加的簽名而增加更多的網(wǎng)絡(luò)延時(shí)。

在這種情況下，如果一個(gè)節(jié)點(diǎn)是誠實(shí)的，我們能否保證被動(dòng)觀察者也能夠看到輸出，就算我們要求它們一直觀察過程？按照所寫的計(jì)劃，存在一個(gè)問題。假設(shè)命令者和一些 k（惡意）驗(yàn)證器子集產(chǎn)生了一個(gè)消息 v : i[1] : … : i[k]，并且在 T k * D 時(shí)刻前，直接把它廣播給了一些“受害者”。這些受害者認(rèn)為該消息是準(zhǔn)時(shí)的，但是，當(dāng)它們重新廣播該消息時(shí)，它只在 T k * D 時(shí)刻后到達(dá)所有誠實(shí)參與共識(shí)的節(jié)點(diǎn)，因此，所有誠實(shí)參與共識(shí)的節(jié)點(diǎn)都會(huì)拒絕該消息。

但是，我們可以補(bǔ)上這個(gè)漏洞。我們要求 D 受兩倍網(wǎng)絡(luò)時(shí)延加上時(shí)鐘差異的約束。然后，我們對(duì)觀察者施加不同的超時(shí)：觀察者在 T (k – 0.5) * D 時(shí)刻前收到 v : i[1] : … : i[k]。現(xiàn)在，假設(shè)觀察者看到一個(gè)消息并接收它。它們將能夠在 T k * D 時(shí)刻前廣播給一個(gè)誠實(shí)節(jié)點(diǎn)，并且誠實(shí)節(jié)點(diǎn)會(huì)發(fā)出附有其簽名的消息，該消息將在 T (k 0.5) * D 時(shí)刻前達(dá)到所有其他觀察者，那么，具有 k 1 個(gè)簽名的消息超時(shí)。

假設(shè)我們有一些其他共識(shí)算法（例如，PBFT，Casper FFG，基于鏈的 PoS），這些算法的輸出可以被偶爾上線的觀察者看到（我們稱之為閾值相關(guān)共識(shí)算法，而不是上面提到的算法，那些被我們稱為延遲相關(guān)共識(shí)算法）。假設(shè)閾值相關(guān)共識(shí)算法持續(xù)運(yùn)行，其模式是不斷地“最終化”新塊到區(qū)塊鏈上（即，每個(gè)最終化的值指向一些作為“父節(jié)點(diǎn)”的之前最終化的值，如果有個(gè)指針順序 A -> … -> B，我們稱 A 是 B 的后代）。我們可以把延時(shí)相關(guān)算法改造到這個(gè)結(jié)構(gòu)上，讓總是在線的觀察者能夠在檢查點(diǎn)上獲得一種“強(qiáng)大的終結(jié)性”，具有大約 95% 的容錯(cuò)率（通過添加更多驗(yàn)證器和要求該過程花費(fèi)更長的時(shí)間，您可以任意地推動(dòng)這個(gè)值接近 100%）。

每當(dāng)時(shí)間到達(dá) 4096 秒的倍數(shù)時(shí)，我們運(yùn)行延遲相關(guān)算法，選擇 512 個(gè)隨機(jī)節(jié)點(diǎn)參與到該算法。一個(gè)有效的提議是由閾值相關(guān)算法最終確定的任何有效鏈的值。如果一個(gè)節(jié)點(diǎn)在 T k * D (D = 8 秒) 時(shí)刻前看到一些最終確定具有 k 個(gè)簽名的值，它就把該鏈放到其已知鏈集合，并在添加了它自己的簽名后重新廣播它，觀察者像以前一樣使用 T (k – 0.5) * D 的閾值。

最后用到的“選擇”函數(shù)很簡(jiǎn)單：

最終確定的值，如果不是那些在上一輪中已經(jīng)同意成為最終確定的值的后代，將被忽略。

最終確定的無效值被忽略。

要在兩個(gè)最終確定的值之間做出選擇，就選擇具有更低哈希值的那個(gè)。

如果 5% 的驗(yàn)證器是誠實(shí)的，那么只有大約一萬億分之一的概率隨機(jī)選到的 512 個(gè)節(jié)點(diǎn)沒有一個(gè)是誠實(shí)節(jié)點(diǎn)，并且只要網(wǎng)絡(luò)延遲加上時(shí)鐘差異小于 D/2，上述算法就有用，就算因?yàn)檠訒r(shí)相關(guān)算法的缺省容錯(cuò)率被破壞而呈現(xiàn)多個(gè)沖突的最終確定的值，也能正確地協(xié)調(diào)在某些單獨(dú)最終確定的值上的節(jié)點(diǎn)。

如果滿足閾值相關(guān)共識(shí)算法的默認(rèn)容錯(cuò)率（通常是 50%，或是 67% 誠實(shí)），那么閾值相關(guān)共識(shí)算法將不會(huì)最終確定任何新的檢查點(diǎn)，或者，它將最終確定那些相互兼容的新檢查點(diǎn)（即，一系列把前一個(gè)點(diǎn)作為父節(jié)點(diǎn)的檢查點(diǎn)），因此，即使網(wǎng)絡(luò)延遲超過 D/2（或 D），作為結(jié)果，參與延遲相關(guān)算法的節(jié)點(diǎn)不同意它們接受的值，它們接受的的值仍然被保證是同一個(gè)鏈上的一部分，因此，沒有實(shí)際的分歧。一旦在未來某一輪，延遲恢復(fù)正常，那么，延遲相關(guān)共識(shí)將回到“同步”狀態(tài)。

如果閾值相關(guān)和延遲相關(guān)共識(shí)算法的假設(shè)同時(shí)（或在連續(xù)的輪次中）被破壞，那么該算法可以崩潰。比如，假設(shè)在某一輪次，閾值相關(guān)共識(shí)算法最終確定 Z -> Y -> X，并且延遲相關(guān)共識(shí)算法在 Y 和 X 之間不一致，那么在下一輪次中，該閾值相關(guān)共識(shí)算法最終確定 X 的后代 W，其中 X 不是 Y 的后代；在該延遲相關(guān)共識(shí)算法中，那些跟 Y 一致的節(jié)點(diǎn)將不接受 W，但是，跟 X 一致的節(jié)點(diǎn)會(huì)接受 W。無論如何，這是不可避免的，在拜占庭容錯(cuò)理論中，不存在超過 1/3 容錯(cuò)率的安全同步共識(shí)，這是一個(gè)眾所周知的結(jié)果，因?yàn)榧词乖试S同步假設(shè)，但是假設(shè)離線觀察者不可能超過 1/2 缺省容錯(cuò)率。