雪崩協議（Avalanche）共識機制3.0探究

文 | 袁浩

引言：

在上周美國舊金山舉行的 Blockchain Week 上，康奈爾教授埃米·岡·瑟勒（Emin Gun Sirer）對其領導的BloXroute及Avalanche項目進行宣講，BloXroute是一個Layer0的底層協議，致力於開發跨鏈的區塊支付網路。

而雪崩協議（Avalanche）則是一個新型的區塊鏈共識協議，分散式系統領域中，不是每天都有人告訴你「我有一個新的突破」。但，Avalanche可以說是一個公式共識演算法的重大突破和創新，這個演算法家族集成了經典的 Non-Byzanting 共識演算法和 Nakamoto 共識演算法（即 POW） 兩者的特點，做到簡單而又強大。

今年5月份，匿名團隊Team Rocket同Sirer教授合作，在IPFS上發表了題為「Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies」的論文。該論文關注於具體的細節和證明上，因此很難被非專業人士理解。而目前國內對這個共識協議還甚少了解，在此，我對它進行一個盡量簡化和可視化的分析。

兩類共識協議

當許多分散式計算機共享相同的任務和資源時，共識是最重要目標之一。

典型的例子是：在多個伺服器上維護金融系統中的帳戶餘額。金融機構不依靠單一資料庫來存儲數據，而是利用分布在全球不同地理位置的機器來處理這些交易。他們需要一種方法來讓所有這些機器數據是一致的，進而它們所反映的帳戶餘額也是一致的。

另一個例子是：保持對亞馬遜在線購物服務的一致性。為了在全球範圍內擴展服務，數據必須（在地理上）分布於不同的大型數據中心上。亞馬遜需要定期查看其庫存產品，否則可能會發生無法意料的事情。例如，庫存的最後一件商品肯能會重複出售給兩個不同的人。

共識機制一直是計算機科學中的一個重要問題。 為此，學者和工程師們在過去40年中一直在努力尋找有效的解決方案。在分散式系統領域，目前只存在兩組主要的共識協議族。我們接下來將會描述著兩組協議族。

經典共識協議BFT

第一類協議被稱為經典共識協議BFT，它是由兩位偉大的計算機科學家Leslie Lamport和Barbara Liskov在1982年共同開發的。他們兩人都是圖靈獎獲得者（相當於計算機科學家的諾貝爾獎）。我們熟知的國產公鏈代表小蟻NEO就是採用此共識機制。該協議採用「許可投票、少數服從多數」的記賬機制，允許33%的容錯，優點是可以快速結算和快速擔保交易。

然而，這也是有代價的：

• 它們無法擴展到1000個節點以上。這是因為它們通信成本正比於節點個數的二次方，即O(n?)。
• 他們要求網路中的每個人都知道所有其他參與者。

本質上，他們的安全性取決於法定數量的節點所作出的一致判斷，這些節點確認看到同樣的事情並進行認定。在構建私鏈時，這種方法是合理的，但是，當您處於不受信任的節點的動態環境中時，這種方法並不適用。

因此，公鏈可能需要基於另一種不同的共識協議，當然也有針對經典共識協議作出的一些改進（諸如動態調節節點，修改底層網路拓撲等），但比較適合聯盟鏈的應用場景。

中本聰共識協議POW

2009年，另一個類協議POW被提出來了。中本聰提出了他的新協議系列，並展示了它獨特的穩健性：

• 我們不需要知道參與網路的所有節點。任何節點都可以在任何時間點離開或加入，任何礦工都可以提出一個區塊並參與系統。
• 它可以擴展到分布在全世界的大量節點和參與者。

然而這些優點也是有代價的，特別是：

• 比特幣非常慢，平均而言，用戶必須等待大約10–60分鐘才能確認他們的交易被存儲在鏈上。
• 吞吐量也非常有限。比特幣每秒可處理大約3–7筆交易，當然，這處理速度距離成為世界貨幣的處理量還相差甚遠。
• 最後，比特幣消耗了大量的能量；大約相當於4個切爾諾貝利核電站的能量為比特幣供電。這些能量都花在了運算上了。

共識家族Consensus family

Emin教授在深入研究前述兩種主流共識機制後，受 Gossip 協議的啟發，提出了一組BFT協議（簡稱「共識家族」，Consensus family）。

「共識家族」對誠實節點（Correct nodes）和拜占庭節點（Byzanting nodes）的行為作了提前約定：誠實節點絕不會發出衝突交易，而拜占庭節點也不可能偽造一筆與誠實節點衝突的交易（也就是說，拜占庭節點發出的「偽造」交易，只會與自己以前發出過的交易衝突（比如雙花 double spending），但是不可能與誠實節點的交易衝突），拜占庭節點可以偽造許多彼此衝突的交易，但是誠實節點只會採用其中一筆交易。

最終，「共識家族協議」可以保證在存在拜占庭交易的情況下，共識的最終結果只會是接受一組互不衝突的交易集合，「共識家族」也採用了 UTXO 模型。

「協議家族」一共是由 4 個協議構成的，先從 Non-Byzantine 協議開始：Slush，在其基礎上逐漸構建?Snowflake，Snowball 和 Avalanche?這 3個 BFT 協議。

• Slush 協議：是「協議家族」的第一個協議，它是一個非拜占庭協議（Non-byzanting protocol，後續三個協議都是 BFT 協議）。Slush協議的特點是：簡單狀態（simple state），小樣本（small sample），反覆抽樣（repeated sampling），抽樣輪數或時間期限（用 m 表示），Slush 協議作為 BFT 協議的原始狀態，不能提供完整的 BFT 保證。
• Snowflake 協議：也叫 「BFT Snowflake」，它是「協議家族」的第二個協議，在 Slush 的基礎上擴展而來。Snowflake 為每個節點增加一個 counter， 用來記錄一個節點當前 color 的可信度。Snowflake 可以保證對最小的狀態做出很強的保證。
• Snowball 協議：Snowball 是共識家族中的第三個協議，它對 Snowflake 協議做了改進，添加一個更持久的可信度標誌，使得協議安全性更高，進一步增加了共識結果的可靠性（confidence）。Snowball 不僅比 Snowflake 更難攻擊，而且協議更加通用化了。
• Avalanche 協議（DAG）：Avalanche 是「共識家族」中的第四個協議，也是最核心協議，它在 Snowball 的基礎上添加一個動態的僅限追加（append-only）DAG 結構來記錄所有的交易。DAG 結構給雪崩協議Avalanche?帶來了兩大優勢：高效，安全。

共識家族的核心理念：Metastability

共識家族全都基於亞穩態模型（metastable mechenism）。雪崩協議的核心理念也是metastability。共識協議中最糟糕的事情是無法在兩個選擇之間做出決定，即你不希望它模糊地說兩個事件中有一個發生了，實際你期望它能確定兩個事件中到底哪個發生了哪個沒發生。雪崩協議的matastable協議旨在傾向於選擇於兩個選項中的一個。

運行中的雪崩協議 核心思想依賴於抽樣投票。

為了直觀解釋該過程的核心思想，讓我們看一個簡化的例子，如上圖所示。 考慮一個想要投票給藍色或紅色的去信任節點網路。

• 網路的單個節點從選擇少量隨機對等節點（例如五個）開始，並要求他們選擇顏色。
• 然後，每個對等節點以投票進行回應，發出請求節點使用該投票來形成所有投票的加權結果。在上圖中（在第一幀中），從發起請求的節點角度來看，整個網路基於第一投票傾向於紅色。
• 每個參與者都需要重複這一過程。

該協議類似於重複的二次抽樣投票過程。這裡發生的事情是，即使我們開始在紅色和藍色是一半一半的最糟糕的情況下，在一輪之後，很有可能結果不再是打平手了。此外，在兩輪甚至在三輪之打平手的概率將會非常小，打平手的幾率會以指數方式衰減。

該協議旨在於傾向某一結果而不是留在模稜兩可的中間選項。隨著它的傾向性越來越高，網路的感知的顏色將會轉移到其中一種顏色。我們向一個結果方向移動的速度（節點對一種顏色投票比另一種顏色更多）將會不斷加快，並且在某個時候我們達到不返回點，整個網路已就顏色達成一致。

Avalanche雪崩協議綜述

雪崩協議（Avalanche）結合了兩者的優點，特別是，

• 快速結算和低延遲：也就是說，在全球範圍內實現結算需要大約2-4秒鐘。這基本上意味著在4秒後，您的付款就已經處理和驗證完成了。（下圖Emin教授的ppt中指出：AVA的確認延遲時間只有4秒，相比比特幣、以太坊及Alogrand均有大幅提高）
• 更高的吞吐量：每秒可處理1000–10,000個交易。（下圖Emin教授的ppt中指出：AVA的TPS達到1300，相比比特幣、以太坊及Alogrand均有大幅提高）
• 穩健：網路無需就參與者是誰達成一致。
• 靜態協議：最重要的是，協議是綠色的。這意味著它是可持續的，它不會浪費任何能量，並且沒有特殊的礦工生態系統，其中礦工的利益與用戶的利益無關。

關於協議的一些補充說明：

• 高效的可擴展性：協議是輕量級的，因此提供可擴展性和低延遲。
• 拜占攻擊庭容忍度：它可以容忍大量的拜占庭參與者，而不對安全性產生影響。特別地，它可以容忍多達50％的節點作為拜占庭節點（即嘗試欺騙網路並保持整個網路不平衡的節點）。但是，它們無法讓兩個節點決定兩種不同顏色。
• 平等主義生態系統：雪崩協議產生了一個平等主義的生態系統，即網路中的所有節點都是相同的。 沒有礦工，也沒有特權。
• 衝突交易不受保護：如果攻擊者試圖在兩次不同的交易中花費相同的錢兩次（雙重支出），那麼雪崩協議將無法在這兩種交易之間做出選擇，導致這筆錢丟失。經典共識和中本聰協議將會選擇其中一個交易，但是雪崩協議不會。這是雪崩協議的一個非常有趣的屬性，它會隱式而又自然地懲罰壞的角色，而協議本身沒有增加任何額外的複雜讀。

結語：

共識機制是區塊鏈的靈魂，共識機制的演算法設計直接決定了區塊鏈的交易速度，交易吞吐量TPS。人們經常談論比特幣中使用的共識協議，就好像它是一種純粹的去中心化的方法，可以平等地對待所有網路參與者的意見。不幸的是，在比特幣中決策主要是由礦工做出的。

相比之下，雪崩協議將共識問題與管理問題分開。每個都是模塊化和獨立化地處理。通過gossip協議與循環採樣的智能組合形成共識。同時，通過抽樣和投注股份實現公賓士理，從而實現用戶與其決策之間的直接聯繫。

我們注意到一些熱門項目諸如Perlin已經開始搭建在雪崩協議Avalanche之上：https://medium.com/opentoken/perlins-implementation-of-avalanche-1cf7dceadd06

雪崩協議Avalanche目前尚未得到大規模應用，但考慮到其獨特創新之處，我們認為其可以比肩Algorand項目值得重點關注。

參考文獻：

-Cryptoconf 2018, Emin Gün Sirer talk?—?Snowflake to Avalanche

-Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies, Team Rocket, 2018

-SFBWofficial 2018,?Emin Gün Sirer talk: ?Ava protocol with new consensus family