2018 年 10 月 5 日-12 日，在美國舊金山舉行的 Blockchain Week 上，就職於康奈爾大學的 Emin Gun Sirer 教授對其領導的 BloXroute 及雪崩協議（Avalanche）項目進行了宣講。

BloXroute 是一個 Layer 0 的底層協議，致力於開發跨鏈的區塊支付網絡。而雪崩協議則是一個新型的區塊鏈共識協議。

雖然在分佈式系統領域中，不是每天都有新的突破。但雪崩協議是當之無愧的關於共識算法的重大創新。這個算法家族集成了經典的非拜占庭共識算法和中本聰共識算法的優勢，堪稱簡單而強大。

今年 5 月，匿名團隊 Team Rocket 同 Sirer 教授合作，在 IPFS 上發表了題爲「Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies」的論文。該論文專注於細節證明，很難被非專業人士理解。

目前國內對雪崩協議的介紹和解讀還非常少，因此，資深投資人 Howard Yuan 對其進行了可視化的深入分析，以饗讀者。

共識協議的重要性

共識機制是計算機科學領域最重要的問題之一。在過去 40 年，學者和工程師們一直在努力尋找關於共識的有效解決方案。

當許多分佈式計算機共享相同的任務和資源時，共識的重要性就凸顯出來了。

舉例來說，在多個服務器上維護金融系統中的帳戶餘額。現代的金融機構不能依靠單一數據庫來存儲數據，而是利用分佈在全球的機器來處理這些交易。他們需要一種方法，確保在任一時刻，所有機器上的數據保持一致。顯性層面來看，就是確保它們所反映的帳戶餘額一致。

再比如，確保亞馬遜等大型在線購物平臺的數據保持一致。爲了在全球範圍內開展服務，這類平臺的數據必須在地理上分佈於不同的數據中心。亞馬遜需要定期查看其庫存情況，避免意外發生。否則，緊俏的商品就可能同時出售給兩個客戶，引發權益糾紛。

目前，在分佈式系統領域，主要存在兩組共識協議。接下來，我們將會對其進行分析。

拜占庭容錯共識協議

共識機制 3.0 雪崩協議研究

第一類經典的共識協議被稱之爲：拜占庭容錯（BFT）類共識協議，是由兩位偉大的計算機科學家 Leslie Lamport 和 Barbara Liskov 在 1982 年共同開發的。他們兩人都是計算機科學的桂冠——圖靈獎的獲得者。

我們熟知的國產公鏈代表小蟻（NEO）就採用了此共識機制。

該協議採用「許可投票、少數服從多數」的記賬原則，允許 33% 的容錯率。其優點顯而易見，可以快速結算和快速進行擔保交易。

然而，其弊端也很明顯：

  • 無法擴展到 1000 個節點以上。這是因爲，該協議的通信成本與節點個數的二次方（即：O(n²)）成正比；
  • 該協議要求網絡中的每個人都知道所有的其他參與者。

本質上，該協議的安全性取決於特定數量的節點作出的一致判斷，即：所有節點確認看到了同樣的事情，進行了認定。

在構建私鏈時，這種方法是可行的。但當你處於動態環境中，出現不受信任的節點時，這種方法就不再適用。因此，公鏈需要另一種共識協議。

當然，也有針對經典共識協議作出一些改進的方法，比如：對節點進行動態調整或修改底層網絡的拓撲結構等，但只適合聯盟鏈的應用場景。

中本聰共識協議

2009 年，中本聰共識協議（也稱爲：「工作量證明」，POW）出現了。中本聰提出了新的協議，並展示了它獨特的穩健性。

在該共識協議下，我們不需要知道參與網絡的所有節點。在任何時間，任一節點都可以離開或加入，任何礦工都可以提出一個區塊，並參與到系統中來。

由此，它可以擴展到遍佈全球的大量節點上，吸引了爲數衆多的參與者。BTC 交易得以成立。

然而，迅速擴展之餘，它也存在天然的短板，特別是：

  • 交易處理速度緩慢。平均而言，用戶必須等待大約 10–60 分鐘才能確認他們的交易記錄被存儲到了鏈上；
  • 吞吐量非常有限。BTC 每秒只能處理大約 3–7 筆交易，這在很大程度上制約了其世界貨幣的目標實現。
  • 最後，能耗巨大。BTC 網絡的耗電量大約相當於 4 個切爾諾貝利核電站的能量，這些能量都花在了運算上了。

共識家族的提出

在對上述兩種主流的共識機制進行深入研究的基礎上，Emin Gun Sirer 提出了一組 BFT 協議，即：「共識家族」。

「共識家族」對誠實節點（Correct nodes）和拜占庭節點（Byzanting nodes）的行爲作了提前約定：

  • 誠實節點絕不會發出衝突交易；
  • 拜占庭節點也不可能僞造一筆與誠實節點衝突的交易；

也就是說，拜占庭節點發出的「僞造」交易，只會與其曾經發出的交易衝突（意即：「雙花」，double spending），但不可能與誠實節點的交易衝突。

拜占庭節點可以僞造許多彼此衝突的交易，但誠實節點只會採用其中一筆交易。

「共識家族」也採用了 UTXO （未使用餘額，Unspent Transaction Output）模型。

「共識家族」保證了，在拜占庭交易的情況下，共識的最終結果只會是接受一組互不衝突的交易集合。

「共識家族」由四個協議構成。從非拜占庭協議開始，先是 Slush，在其基礎上建構了 Snowflake、Snowball 和 Avalanche 這 3 個
BFT 協議。

  • Slush 協議：「共識家族」的第一個協議，屬非拜占庭協議。後面三個都是 BFT 協議。

Slush 協議的特點是：簡單狀態（simple state），小樣本（small sample），反覆抽樣（repeated
sampling），有抽樣輪數或時間期限（用 m 表示）。Slush 協議作爲 BFT 協議的原始狀態，不能提供完整的 BFT 保證。

  • Snowflake 協議：又稱爲「BFT Snowflake」，是「共識家族」的第二個協議，在 Slush 的基礎上擴展而來。Snowflake 爲每個節點增加了一個 counter， 用來記錄該節點當前的可信度。Snowflake 可以保證對最小的狀態做出很強的保證。
  • Snowball 協議：「共識家族」的第三個協議，對 Snowflake 協議做了進一步改進，添加了一個更持久的可信度標誌，提高了協議安全性和共識結果的可靠性。相較於 Snowflake ，Snowball 更難被攻擊，更爲通用化。
  • 雪崩協議：「共識家族」的第四個協議，也是核心所在。它在 Snowball 的基礎上添加了一個動態的、僅限追加的 DAG 結構來進行交易記錄。

DAG 結構給雪崩協議（Avalanche） 帶來了兩大優勢：高效，安全。

共識家族的核心理念

亞穩態模型

共識家族全部基於亞穩態模型（metastable mechenism）。 雪崩協議也不例外。

共識協議中最糟糕的事情是，無法在兩個選擇之間做出決定，即：你不希望它模糊地說，兩個事件中有一個發生了。實際上，你的期望是，它能確切地告訴你，兩個事件中，到底哪個發生了，哪個沒發生。

雪崩協議的亞穩態模型旨在做出這種選擇。

共識機制 3.0 雪崩協議研究圖：運行中的雪崩協議

核心思想來自於抽樣選票

爲了直觀解釋該過程，讓我們看一個簡化的例子，如上圖所示。假設一個想要投票給藍色或紅色的去信任節點網絡。

  • 首先，選擇少量隨機對等的節點（以五個爲例），要求網絡的單個節點對顏色做出選擇。
  • 每個對等節點以投票形式進行迴應，發出請求的節點利用投票數據形成加權結果。以上圖的第一幀數據爲例，從發起請求的節點來看，整個網絡傾向於給紅色投票。
  • 每個參與者都需要重複這一過程。

該協議類似於重複的二次抽樣投票過程。

顯而易見，即使在紅、藍各佔一半的最極端情況下，經過一輪重複，結果就會發生變化，不再保持對等狀態。

此外，在兩輪或三輪之後，對等狀態的出現概率將會變得非常小，出現機率將以指數形式衰減。

該協議旨在明示結果，而不是停留在模棱兩可的中間狀態。

隨着傾向性越來越明顯，網絡節點感知到的顏色將會集中。並且，向特定方向移動的速度將會不斷加快，在某個時間點上，整個網絡已就顏色達成一致。

雪崩協議概述

共識機制 3.0 雪崩協議研究

雪崩協議結合了非拜占庭共識算法和中本聰共識算法的特徵，優勢明顯：

  • 快速結算、低延遲：在全球範圍內實現交易結算，僅需大約 2-4 秒鐘。這意味着，在發起結算指令 4 秒後，就已經完成了付款驗證。相較當前較爲主流的區塊鏈網絡，比如 BTC、以太坊和 Algorand，確認延遲時間大爲縮短；
  • 更高的吞吐量： TPS 可達 1300，每秒可處理 1000-10000 筆交易，相較 BTC、以太坊和 Algorand，吞吐量大幅提高；
  • 穩健：網絡無需就參與者的身份達成一致。
  • 靜態協議：更重要的是，該協議是「綠色」的。這意味着，它可持續，不會浪費能量，不存在特殊的礦工生態系統，礦工利益與用戶利益不交叉。

此外，還有一些關於雪崩協議的補充說明：

  • 可擴展性高：輕量級協議保證了較高的可擴展性和低延遲。
  • 拜占庭攻擊容忍度高：它允許大量的拜占庭參與者存在，但不會對網絡安全性產生實質性影響。它對拜占庭節點（即：嘗試欺騙網絡並保持整個網絡不平衡的節點）的容忍度上限可達 50%。
  • 平等主義：雪崩協議造就了一個平等的生態系統，網絡中所有的節點權益都是相同的。
  • 衝突交易不受保護：如果攻擊者試圖在兩次不同的交易中花費同一筆錢，雪崩協議將無法做出選擇，這筆錢就會丟失。經典共識和中本聰共識會選擇其中一個交易，但雪崩協議不會。這個有趣的屬性會隱祕、自然地懲罰壞角色，而協議本身並未增加任何額外的讀取成本。

共識與管理分離，公平治理

共識機制 3.0 雪崩協議研究

共識機制是區塊鏈的靈魂，共識機制的算法設計直接決定了區塊鏈的交易速度和交易吞吐量。

人們經常談論 BTC 網絡的共識協議，就好像它是一種純粹的、完美的方法，真的能夠平等地對待所有參與者的意見。但實際上，BTC 網絡中的決策主要是由礦工做出的。

相比之下，雪崩協議做到了共識問題與管理問題的分離。針對每個問題，採用了模塊化、獨立化的處理手段。通過 gossip 協議與循環採樣的智能組合，形成了共識。

同時，通過抽樣和投注股份，實現了公平治理，達成了用戶與其決策之間的直接聯繫。

雖然雪崩協議尚未得到大規模應用，但有一些熱門項目諸如 Perlin 已經搭建在其上。其獨特的創新之處，值得重點關注，深入探究。

參考文獻：

  • 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_