GDF 研究院 | 解析 V 神的 99% 共識新算法

隨機

由 熱鏈中的人 於 8 月 30, 2018

GDF 數字金融研究院

是 GDF 數字金融生態基金旗下的研究機構

由 GDF 一線研究員

爲您剖析市場，揭祕區塊鏈技術

01 –

V 神的 99% 共識算法

今天我們來聊聊 V 神前不久剛發佈的 99% 算法，看看區塊鏈 3.0 和 2.0 兩代產品創造者如何看待該算法，或許能給大家更好地理解共識的進展。

BM 在 EOS 社區羣里發了這樣一段話：99% 算法是關於 Steem 和 Bitshare 的非 BFT 終結性的正式描述。

這句話怎麼理理解呢？

Steemit 使用的是 DPOS 算法，21 個節點進行打包完成出塊，達成共識；而 Bitshares 有見證人機制；簡單來說，二者結合從理論上來說就可以創建 V 神提出的 99% 算法所需的網絡環境。因此 BM 這句話似乎也可以這麼翻譯：Steem 和 Bitshare 的解決⽅方案都不是 BFT 的最終解決方案。

那什麼是最終解決方案呢？

自然能達成 99% 的作惡成本會是更好的解決方案，但目前網絡環境下，能有這樣的效率除非節點數量減少，通過弱中心化尋求折中方案。說白了，21 個節點的的 DPOS 算法，目前來說就是 BM 心中效率和去中心化權衡最好的設計。EOS 白皮書中也有提出，DAWN3.0 只需 0.25 秒即可達到 99.9% 的確認，1 秒即可達到 100% 不可逆，而且該算法保證 100% 生產者參與。也正因此，EOS 的 TPS 能擴展到百萬級別。（具體來說平均水平大約在 240 萬筆交易 / 秒）。其背後的創新之處是在傳統的 DPOS 機制中加入了 aBFT （異步拜占庭容錯）。

那麼，V 神提出的 99% 算法到底該如何理解，有沒有可能實現呢？

我們來分析一下

大家都知道的是，這個算法並不是 V 神創造的，正如 V 神 Twitter 所言，他只是把 1982 年拜占庭將軍解決方案的思想和算法加了限制條件，拓展到區塊鏈領域作爲一種理想化解決方案希望做技術改進。

說白了相當於將已有的解決方案本地化，放到區塊鏈領域進行使用。

那麼這次做爲何做這件事情，做他的意義又在哪裏呢？

在 1982 年的論文中，提出了 2 種方法解決拜占庭將軍問題，那麼 V 神試圖實現第二種，也即使用消息簽名的方式。該方式對比口頭敘述的方式有個好處，就是傳播過程中絕對安全。也就是說，使用這種方法我們只需要考慮（1）誠實節點忽略消息或者（2）作惡節點重新發簽名的問題。最終使用論文中提到的 choice 函數選擇出正確消息作爲共識標準即可。

第（1）種情況會導致忽略消息的節點傳遞的消息缺少一個簽名，進而造成上一輪的最終沒有被同意。第（2）種情況會導致或者哈希值偏高。觸犯了 choice 函數的條件，不會被作爲結果。

上述是原始論文對應的解決方案，那麼 V 神做了什麼改進使其適於本地化呢？第一個是引入 observer 機制，第二個是要求節點同步。可以看到這是一種理想狀態，因爲第二點就很難達成。不過第一點卻有現實意義，其一是該機制可以使得網絡更安全，其二是 observer 原本沒有任何激勵（例如 POW 中未成功打包的礦工），而 V 神改進之後，或許可以緩解這一問題，使得小礦工也有動力加入到網絡中共同維護。

參照下圖我們具體看一下算法過程：

假設有 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 時刻，節點停止偵聽，它們使用一些“選擇”功能從所有它們已經看到的有效消息中選擇一個值（比如，它們取最高的）。然後，它們決定這個值。

接下來，我們來探究一下這個爲什麼可行。我們需要證明的是，如果一個誠實節點已經看到一個特定值（有效的），然後，其他各個誠實節點也看到了該值（如果我們能證明這個，那麼我們就知道所有的誠實節點在運行同樣的選擇函數，因此它們會輸出相同的值）。假設任意一個誠實節點收到消息 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 個簽名的消息超時。

最後細心的同學可能還有個問題，爲什麼是 99%，而不是 98% 或者 99.99%？首先回到 1982 年的論文中我們不難發現，該問題的數學證明已經告訴我們，我們需要在 3m+1 的網絡中，不少於 1/3 的節點誠實，這樣纔能有一條信息在傳輸到每個端點之後能符合條件。於是當引入 observer 機制並且節點同步之後，用 1/(3m+1) 便可得出，在以太坊網絡存在情況下 (m>1)，我們只需要一個節點誠實便可以保證網絡安全。其實想表達的就是這個“1 個節點誠實”就能解決問題，以太坊目前的熱度和節點數目在數量上來說完全可以高於 99%，只不過不那麼精確計算罷了。

Casper 在朝着這個方向發展，可以期待的是，Casper 系統中會加入 observer 機制，並且 observer 能得到有效激勵，從而提高系統效率。而最終能否實現 V 神說的 99% 去中心化的作惡成本呢，其中一個很難逾越的技術門檻便是節點同步，這是未來可以期待的進一步技術革新，對於去中心化的效率是很值得期待的。

02 –

關於 GDF 數字金融生態基金及研究院

GDF 數字金融生態基金 ( Global Digital Finance Capital ) 是由 BKFUND、BFFUND 聯合組建的數字金融生態基金，總規模 1 億美元。數字金融生態基金（GDF）將專注於價值項目投資，瞄準數字金融生態領域的賽道，在一級市場和二級市場同時發力，幫助優秀的創業者與企業家成長，推動數字金融基礎設施建設，推動行業良性發展。

GDF 數字金融研究院是 GDF 數字金融生態基金旗下的研究機構，專注於區塊鏈前沿技術研究和數字金融行業動態，爲投資者提供專業、公正的市場剖析與技術解讀，更好的擁抱數字金融。

投資 | 觀點 | 數字金融

盡在 GDF 數字金融