康奈爾大學Sleepy Model PoS共識機制詳解：「互聯網規模」共識如何實現？

雷鋒網AI金融科技按：共識機制是區塊鏈和分散式計算的基礎。如比特幣採用的PoW（工作量證明）就是一種是讓計算工作完成最出色的節點獲得系統的數字貨幣獎勵的競爭機制，近年來，PoW共識機制逐步暴露出資源消耗大、運行成本高的問題，一些替代性的方案如PoS也被提出並引起了學術界的極大興趣。例如康奈爾大學IC3（Initiative for Cryptocurrency and Contracts，虛擬貨幣及合同倡議）項目的Co-Director 石潤婷教授(Elaine Shi)等在2017年提出了基於Sleepy Model的PoS共識，並對其進行了形式化描述和安全性分析。

與我們熟悉的各種加密貨幣的共識機制不同，Sleepy Model的提出旨在解決今天的互聯網規模、數百萬計甚至更多節點的情況下，如何保持系統的魯棒性同時又保持系統效率的問題。石潤婷教授認為，雖然區塊鏈技術在虛擬貨幣得到了成功的應用，目前通用的共識機制不適合於推廣到互聯網級別規模，互聯網規模的分散式系統需要新的理論框架，也需要可驗證的安全協議以及實施方案，這也是讓區塊鏈技術從虛擬貨幣走向更廣闊應用的一個關鍵點。

背景

在計算機科學中，為了解決計算機單機性能不足，某些應用中需要更大的存儲、更強的計算能力的需求，有研究者將一組電腦連接起來，彼此進行交互以實現一個共同的目標，通過網路相互連接傳遞消息與通信後並協調它們的行為，這也是「分散式計算」的由來。

隨著摩爾定律碰到瓶頸，越來越多的系統要依靠分散式集群架構來實現海量數據處理和可擴展計算能力。而區塊鏈正是為了解決各個節點互不信任，又需要協同工作而產生的，與一般的分散式系統不同的是，一般的分散式系統通過一個共同的中心來實現相互信任，而區塊鏈中的各節點是通過共識機制而實現相互信任，可以說，共識機制是區塊鏈與分散式計算的基礎。

關於分散式計算的文獻以及密碼學文獻通常會考慮兩種類型的參與者：誠實的和非誠實的。然後會分析上述彈性屬性，假設對誠實參與者的比例下限。對於通常部署共識協議的傳統環境如Google Wallet等應用程序，其中節點的數量大約是十幾個，而在大規模的共識協議（雷鋒網註：例如區塊鏈協議）中，不僅用戶數量大幅增加，同時達成共識也更為複雜，已有的共識機制不能很好的符合魯棒性的要求。

在Real World Crypto 2017安全大會上，石潤婷教授首次對基於Sleepy Model的PoS共識機制進行了解釋，雷鋒網結合論文進行了節略改編：

「互聯網規模」的共識機制

我在這裡想和大家討論互聯網規模的共識機制。你們有人可能會記得，去年八月有一天，達美航空的系統完全癱瘓，你無法預訂機票，所有航班也被取消，這是因為達美的計算基礎設施出現了鼓掌。類似的情況也出現在國家科學基金上，去年七月的時候也發生了系統宕機，你不得不繼續等待。好吧，如果我不能飛這我還能忍受，但如果不能做科研，那我要說這就太讓我傷心了。

我們關注兩點：可複製性、魯棒性。在計算機科學中，這被稱為分散式系統，這一領域已經有了近30年的研究。在分散式系統中有一個非常重要的抽象概念，我們稱之為「狀態機複製」，這也被稱之為「線性」或者「共識機制」。

那麼什麼是狀態機複製呢？這裡有一個應用場景：拿Google Wallet來講，Google可能考慮將其伺服器進行備份。你自然不會希望你放在Google那裡的錢遭受損失，所以備份是一個好主意。當某個伺服器出現問題，在所有這些伺服器上會存有線性排序的日誌，我們會關注兩個安全屬性：一致性、活躍度。一致性指的是所有誠實的伺服器節點都同意這些交易日誌，活躍度指的是，如果一個客戶提交了一筆交易，那麼這筆交易需要很快被記錄在所有伺服器中。

問他是：如果某些伺服器安全受到了威脅呢？有問題的伺服器會背叛其他伺服器，這個問題非常重要。當我們討論共識問題，通常來講，這些伺服器從屬於一個團體，我們可以認為這些伺服器是相互信任的。今天我們為什麼認為比特幣令人激動，是因為比特幣開啟了分散式計算的新的篇章，其提出的分散式共識令人驚嘆，也使得互聯網規模的共識存在可能。

然而我們知道，互聯網存在著數百萬計甚至更多的節點，這些節點節點可能不一定在線，有的在線，有的不在線，要形成共識有很多不可預測的情況。同時每個節點都是自私的，因此互相不信任，這也給「互聯網規模」的共識機制提出了新的挑戰。

我和虛擬貨幣圈的很多人有過交流，他們或多或少認為目前的共識機制或多或少地無法適應互聯網級別規模，原因在於這些共識機制在互聯網級別的大規模、複雜狀態下魯棒性並不好。關於互聯網規模共識的魯棒性，這是一個非常大的話題，我在此處不再展開，但我們會從一些基本的問題入手，來解釋什麼是魯棒性。

我們剛剛經歷了美國總統大選。總共有三億人（節點），1.6億人亮相（並進行了投票），如果我們希望，如果這些亮相（投票的人）當中有51%是誠實的，否則我們就不能正確預測選舉的結果，這就是一個共識的例子。

這裡我們假設一些節點是在線的，一些節點是睡眠的。在線意味著這些節點會主動參與共識協議，而睡眠節點可能會從睡眠中恢復，並繼續加入共識協議，這就是一個「Sleepy Model」，關於這一模型我們有這樣的額外假設：

作惡節點無法任意行動（無法偏離基本協議規則）；

作惡節點可以延遲和修改消息；

在線誠實的節點可以快速接收消息，否則將被視為睡眠節點；

在這一環境中，我們提出的一個非常自然的問題是：

當僅有51%的在線節點誠實，我們能否達成共識？

這當中的3個難點在於：

1）協議沒有任何在線節點比例的先驗知識。在線節點可能是30%，也可能是1%；

2）而且你無法進行假設，有可能你假設30%在線節點參與協議，但實際只有1%參與協議，而這99%的沉睡節點不會影響1%的在線節點的共識結果；

3）另一種情況是，而在此過程中，會有「沉睡」節點醒來，他們將受到所有之前待處理的信息，參與到共識投票中，隨之而來的安全問題。

經典共識協議的失效

我們研究的結論可能令你吃驚：甚至在99%的在線節點誠實的情況下，目前所有的經典共識協議都無法在這樣的場景中順利運行。我來簡單解釋一下，經典共識協議可以分為兩類，即同步共識協議和非同步共識協議，在同步協議中可以立即接收信息，而非同步協議中，作惡者可以隨意的修改信息和延遲發出。為什麼在同步協議中會失效呢？原因很簡單，因為一直在線的節點按順序接收信息，而在「Sleep Model」中，我們允許睡眠節點在蘇醒後接收信息。而信息的延遲存在著不確定性。

那麼，為什麼非同步協議也會失效呢？原因在於在非同步協議中，睡眠節點將會被視為作惡節點。假設某個協議可以在已知數量情況下允許1/3作惡者存在，但如果有99%節點為沉睡節點，那麼這些節點被視為作惡節點，這樣你無法得到足夠選票達成共識。

我們說比特幣的中本聰區塊鏈（PoW模式）具有魯棒性，這有兩方面含義：好處是，中本聰區塊鏈在大多數在線節點誠實時可以達成共識；但缺點是：能耗太高。今日用於比特幣挖礦的電力高達1.5GW，比美國最大的核電站發電量或者美國10%的太陽能發電量都要大。

我們是否可以在達到中本聰區塊鏈的魯棒性的同時，又免於支付高額代價？辦法是：保留中本聰的區塊鏈結構，但去除PoW共識；其中的挑戰在於，在達到這一點的同時保證安全性？

我來簡單解釋區塊鏈的機制。中本聰區塊鏈將前一個塊數據和交易，進行hash，為什麼PoW耗費資源？因為哈希函數具有隨機性，為了找到適合的解，必須嘗試各種隨機數求解，而誠實節點只相信「最長的鏈」，如果某個作惡節點想要否定某筆交易雙花，他需要獲得大部分哈希算力來保證其提交的塊結果被接受。

我們可以將PoW視為「領導人選舉」，如果你提出一個正確的解，你就是具備下一個塊的出塊權並提交交易。我們的想法是：是否可以限定解法的範圍，從而達到降低資源浪費的效果？

基於Sleepy Model的PoS共識機制

讓我們考慮一個簡單的「允許協議」，這意味著我們知道哪些節點參與協議、每個節點都知道其他節點的公鑰，稍後我會講，如何在PoS下無需允許達成共識。假設所有節點有一個一周的同步期，在每一個時間周期，Dan將他的名字、當前時間結果一同計算哈希值，如果小於難度係數，那麼Dan將會被選為出塊者，並收集信息出塊，其他人可以檢查Dan是否是正確的出塊者，以及通過公鑰驗證這一區塊是否由Dan簽署。

問題在於：這個協議是否足夠安全？在這一模式下，作惡者的收益更大：當誠實的節點當選，他會出一個塊，當作惡者當選，他會出很多塊，以及挖未來的塊。因此我們做了進一步修正：

1.）每個塊的時間戳是嚴格遞增的；

2）誠實節點會拒絕「未來時間區塊」。

這樣，不誠實節點就不能為所欲為出塊了。某種意義上這一協議的安全性得到了保證，但實際上通常不是這樣，因為非誠實節點仍然可以使用已經選舉的節點和他們的塊製造出分叉。

為了證明我們的「休眠共識」機制有效，我們仍需要更多的證明。由於時間關係在此我不再展開，詳細內容可以閱讀我們的最新論文，在論文中我們介紹了：1）更詳細的證明；2）更弱的假設；3）更強大的安全模型結果。我認為這一研究對於銀行等聯盟鏈非常有吸引力，每個銀行成為一個節點，以去中心化的方式來管理他們的票據，從而實現更快的銀行間結算；至於魯棒性，銀行可以隨時重啟機器進行檢修，而無需與其他銀行進行協調。

關於互聯網級別的共識機制，我們意識到有太多的問題比我們所理解的東西更難以理解，我們需要一個新的理論框架對於這些協議進行分析和推理，同時我們也可能需要安全的協議設計和實現，這對於加密社區來說也非常重要，無論從新的加密協議、或是分散式計算都是如此。另一方面，從理論研究到產生實際影響，這也需要可驗證的安全協議以及實施方案。謝謝。

相關論文：The Sleepy Model of Consensus 摘要

分散式計算及相關密碼學文獻通常考慮兩種類型的參與者：誠實的玩家和作弊的玩家，然後會分析彈性屬性以假設誠實玩家的比例下限。

按照假設，誠實的玩家不僅被假定遵循規定的協議，而且在整個協議執行過程中被假定為在線。而在實際場景中，可能會出現數百萬玩家的「大規模」共識協議（例如區塊鏈協議），這種假設是不切實際的。在本研究中我們研究分散式協議，玩家的狀態可以是在線（警戒）或離線（睡著），他們的在線狀態可能在協議期間的任何時候改變。我們希望解決的主要問題是：

我們能否設計出在僅有零星用戶參與下仍然保持彈性的共識協議？即，在任何給定的點上，都只有極少一部分用戶實際在線參與？

據我們所知，即使我們假設，99％的在線玩家都是誠實的，目前的共識協議在這種零星參與的狀態下都會崩潰。

本研究則發現了上述零星參與情況下仍然可以形成共識的可能性。我們提出了一個基於「Sleepy Mode」（沉睡模式）的共識協議，該模式彈性假設只有大多數在線玩家是誠實的。我們的協議依賴於公鑰基礎設施（PKI），一種通用隨機字元串（CRS），並且在Dwork-Naor-Sahai（STOC"98）的時序模型中被證明是安全的。在該模型中，所有玩家被假定為具有弱同步時鐘（所有時鐘與實時時間的偏差在Δ之內），並且在網路上發送的所有消息都在Δ時間內傳送，並且假設存在次指數安全的抗碰撞哈希函數和增強的陷門排列。

一個令人驚訝的發現是，我們的協議明顯偏離了分散式共識的標準方法，而我們卻依賴中本聰區塊鏈協議背後的關鍵思路（同時不需要POW工作證明）。最後我們最終觀察到，如果大多數在線玩家不誠實，「沉睡共識」是無法實現的。

點此下載閱讀論文全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！