作者：Sebastian Müller, Andreas Penzkofer,Nikita Polyanskii, Jonas Theis, William Sanders, Hans Moog, Aix Marseille Université, CNRS, Centrale Marseille, I2M-UMR 7373, 13453 Marseille, France IOTA Foundation, Berlin, Germany
出品：LD Capital
摘要
我們介紹Tangle 2.0 的理論基礎，這是一種基於有向無環圖（DAG）的概率性無領導共識協議，稱為Tangle。 Tangle 自然而然地繼區塊鏈之後出現，是其下一個進化階段，因為它所提供的功能適合創建更高效和更具擴展性分佈式賬本解決方案。
共識不再出現在最長鏈上，而是見於最重DAG 上，其中工作量證明（PoW）被基於權益或聲譽的權重函數所取代。 DAG 結構和底層基於現實的未花費交易輸出（UTXO）賬本允許並行驗證交易，而無需全排序。同時，它支持刪除礦機和驗證器這些中間環節，實現了純兩步式流程，該流程在節點層面，而非驗證器層面遵循「提案- 投票」範式。
我們提出一個框架來分析不同通信和對手模型下的活性和安全性。這樣可以在一些邊界案例和異步通信模型中提供不可能的結果。我們提供協議安全性形式證明，該證明假定公共隨機幣種。
關鍵詞：共識協議；無領導；異步；容錯；有向無環圖；安全
1. 引言
在分佈式系統中，不同事件可能同時發生，但參與者感知它們的順序有所不同。相比之下，像比特幣[1]這樣的分佈式賬本技術（DLT）常常用完全有序的數據結構——區塊鏈來記錄交易，這些交易闡明了賬本狀態。這種設計會造成挖礦機或驗證器等瓶頸，而每筆交易都必須通過它們進行。區塊創建也可能同時發生在網絡不同部分，導致區塊鏈分叉，需要解決。這是往往通過最長鏈規則[1]或某個最重子樹變體[2]來完成的。為了確保系統的安全性，我們人為抑制系統吞吐量，這樣在下個區塊創建前，每個區塊都能充分傳播，而極少數「孤塊」會自發分裂區塊鏈。限制可擴展性另一個的影響是交易是分批處理的。挖礦機創建這些交易的批次或區塊，區塊鏈可視為三步式過程。在第一步，客戶端向區塊生產者發送某項交易，然後某個區塊生產者提出包含一批交易的區塊，而在最後一步，驗證器驗證該區塊。
IOTA 採用一種更新穎方法來處理分佈式系統的異步設置[3]。該方法不需要集群交易，而採用有向無環圖（DAG）（作為底層數據結構）來表示同時發生的事件。在該模型中，單次交易被添加到賬本中，而每次交易都引用至少兩次先前交易。這種特性將賬本更新簡化成兩個步驟：一個節點向賬本提出交易，並等待其他節點驗證該交易。去除礦機或驗證器中間環節來解決（或至少減輕）與之有關的幾個問題，如挖礦比賽[4]、集中化[5]、礦機可提取價值[6]和負外部效應[ 7] ，從而實現免費用架構。但是，向賬本添加新交易的並行性意味著，共識必須見於「更廣」子圖，而非僅僅最長鍊或最重子樹。
通常而言，共識協議（特別是DLT）是非常大的研究領域，我們必須參照一些綜述文章來獲得更詳細介紹，如文獻[8]-[10]。雖然共識協議取決於許多不同方面，但在引言其他部分，我們將側重於與所提出協議的設計選型關係最密切的方面。
賬本模型。分佈式賬本（DL）通常以兩種方式實現收支平衡：一種是基於賬戶的模型，其中資金直接和用戶賬戶關聯，如以太坊[11]；而另一種則是未花費交易輸出（ UTXO）模型，在該模型中，令牌鏈接到所謂輸出，而用戶擁有輸出密鑰，如比特幣[1]及其諸多衍生品，以及艾達幣[12]、AVAX 幣[13]和IOTA幣[14]。後一種情況的重要觀察結果是，UTXO 本身形成DAG。對於許多用例和情況來說，對交易進行全排序是非必要的，因為它們中大多數是可並行處理的。但如果有衝突交易，UTXO 賬本的只添加屬性會妨礙這種並行處理優勢。在文獻[15]中，我們提出樂觀更新賬本的增強UTXO 賬本模型，來跟踪可能有衝突的依賴關係。我們構建共識協議，並利用此賬本模型快速並行地解決衝突。
Tangle 與局部秩序。 Tangle 是儲存分佈式賬本（DL）所有交易的DAG。每個DAG 歸納了頂點集（頂點集是我們設定中的交易集合）的偏序。這種特性與建立交易全序的區塊鏈形成對比。因為在故障崩潰系統中，原子廣播和共識是等價問題，見文獻[16]，DAG 的偏序在共識協議中造成其他「困難」。更確切地說，基於DAG 的DLT 在安全性方面存在嚴重限制。在Tangle 最初提案中，文獻[3]用「最重子圖」替換最長鏈規則，即包含最多交易的子DAG。但事實證明，這該設計容易受到各種類型攻擊，而且過多依賴發出交易所需的工作量證明（工作量），如文獻[17]。與許多其他基於DAG 提案的共同之處是，該設計的另一個關鍵元素是有存活性問題。如果誠實交易涉及某個將來被證明是惡意的交易，無法添加到賬本狀態。本文提出的協議依靠權重函數和基於現實的賬本狀態來解決安全性問題[15]。通過將交易與其容器（即區塊1）分隔開來，利用新區塊引用方案來處理存活性問題，特別是這種無批處理架構支持面向流過程的DLT 設計。 （1 與許多區塊鏈協議不同，我們要求每個區塊都剛好包含一項交易。但原則上，該協議可改編為區塊包含不止一項交易。）
Sybil 保護。在人人都能參與的「無需許可環境」中，Sybil 保護起到至關重要的作用。比特幣中本聰共識是第一個在如此開放環境中利用工作量證明（PoW），實現共識的共識。
由於PoW 會導致巨大能源浪費和許多負面外部效應，許多人努力提出更可持續性的替代方案。其中最突出的是權益證明（PoS），其中驗證器投票權與其在系統中的權益（按照基礎加密貨幣計算）成正比。本文所用Sybil 保護是以節點身份為基礎的。我們一般將其描述為稀缺資源函數或抽象聲譽函數。該函數稱為權重，為每個節點身份分配一個正數。比如，此權重可對應於賭注令牌、授權令牌或文獻[14]所述的「MANA 幣」金額。我們需要注意的是，權重不一定要連接到底層令牌，但可被任何其他「權重」所取代，從而很好實現Sybil 保護。尤其是我們框架也可用於需許可環境，在該環境中只有預定義驗證器有正權重，而且可用於具有動態委員會篩選的情形。
中本聰共識。分佈式共識使參與者可以就不斷增長的交易日誌達成一致。數十年來，這一直是重要研究課題，在計算機科學中的重要性從未有過爭議。對共識協議進行分的方法有許多種。比如，在PAXOS 和BFT 方面有經典里程碑式結果和新穎的中本聰式共識機制。
我們將中本聰共識理解為選擇最長子鏈的原則，比如見文獻[10]，或權重最重子鏈（作為一種變體）。我們將此概念擴展到最重子DAG。更確切地說，我們認為，中本聰區塊鏈共識遵循的是提議- 投票範式，該範式概述如下。
時間被劃分成時期（epoch），每個時期都有「民選」領導。該領導將交易批處理到某個新的區塊，然後提出該區塊。接著，其他參與者對提出的區塊進行投票，比如通過將區塊鏈擴展到所提區塊所在區塊鏈。一旦投票數達到一定閾值，所提出區塊就被認為構成賬本一部分。上述各要素具體定義可能有所不同，相應地「中本聰共識」有不同變體。在某種程度上，上述範式簡化為每個時期必須約定一位唯一領導。一旦參與者就領導達成共識，區塊鏈的線性意味著就賬本狀態達成共識，而只有領導才能推進賬本狀態，這一事實明顯造成瓶頸和公認性能限制。我們提案完全刪除了「領導」的角色，允許參與者同時提出區塊和它包含的交易。一旦區塊提出，所有參與者都可以投票並參與共識發現。投票權重和上文所述節點的權重成正比，這樣協議就能適應不同權重分佈。該協議也被歸類為非二元共識協議，因為可同時決定多項交易，是一個不斷進行的投票過程，形成遞進成長史。同時，它也涉及一種概率共識，即某筆交易積累的輔助節點越多，該筆交易最終被確認並添加到賬本的可能性就越大。
投票。在我們無區塊架構中，每個新區塊均引用至少兩個現有區塊，從而形成上述DAG 結構。和區塊鏈一樣，新區塊不僅就直接引用進行投票，而且就其過去錐體進行投票。雖然這是一種有效投票方案，但也存在孤塊或存活性問題。如果一個區塊在其過去錐體中包含一個無效區塊，那麼它將不再是投票對象，所包含的交易也不能被納入賬本。我們通過引入兩種不同參照來解決該問題。第一個參照是Tangle 結構，而第二個參照是源自UTXO 賬本的DAG 結構。最後一個參照允許我們對最初孤立交易進行投票，改變先前發布的投票。最終，這兩種投票都被累積到一個投票權重，我們將其稱為贊成權重（AW）。該AW 越高，交易最終納入賬本的概率越高。我們參照圖1 來了解投票機制例子。
圖1：Tangle 被用作節點投票層，可就衝突結果達成共識。節點利用無領導協議在衝突交易x 和y 之間約定獲勝者。不同顏色代表不同節點特徵。對於交易y，輔助節點數量（如右側所示）隨時間推移而增加。虛線引用是所謂的交易引用，可以「挽救」投給「失敗方」的交易。
通常，投票機制可用於任何基於DAG 的數據結構，該結構帶有能夠引用前一個區塊的添加程序。它需要三個主要組成部分：第一個基本成分是有效投票和傳播選票的參考方案。
第二個必要成分是構建允許衝突共存的廣義數據不變式結構，見文獻[15]。該功能使我們能夠「樂觀」地對待交易；每筆新交易都被認為是「誠實的」，除非與其他交易衝突。因此，節點可能開始構建於每筆新交易之上，即使該筆交易被證明存在衝突。第三個成分是被稱為On Tangle voting （OTV）的投票機制它，可以同時有效地對無限交易進行投票。該效率是通過保持較低區塊開銷來實現的，因為其他節點投票均可通過隱式投票機制綁定。此外，與經典拜占庭容錯相比，我們無需監視節點活動，因為交易的發出（將選票投出）是功能正常的明顯標誌。
安全性。自共識協議研究開始以來，安全性概念一直是業界關注的焦點。任何共識協議都是為了就數據達成共識。有些參與者可能出錯，甚至積極阻止達成共識，而有人則關心達成共識所需要的條件。
提議- 投票共識協議的安全性通常分為兩點：存活性和安全性。存活性指的是任何正確交易最終被所有誠實參與者接受，而安全性指的是所有參與者最終就同一組交易達成一致。某個共識協議是否滿足這些屬性在很大程度上取決於模型假設。模型大致可分為通信模型和攻擊者模型。
在最具限制性通信模型（同步模型）中，自里程碑式結果出現以來[18]，人們已知曉許多不同解決方案[18]。異步模型對區塊傳輸延遲不設置任何限制，通常以A 表示。但在最通用通信模型——異步模型下，情況並非如此，關於共識協議最著名結果之一是FLP 不可能性結果[19]，它表明在異步通信模型中，單個出錯參與者可能阻礙共識的發現。
由於FLP 不可能性結果依賴區塊延遲的特定配置，許多從業者認為其不適合在現實世界中實現，因為這些特殊情況不太可能發生。人們在這兩個極端通信模型之間，提出了幾個中介模型，並在較強網絡延時假設下取得許多積極結果，比如部分同步模型[20]、定時異步模型[21]和帶故障檢測異步模型[16]。
除通信模型外，對手模型在中本聰協議中起重要作用，特別是安全性分析。協議安全性通常以稀缺資源數量來表示，如PoW，這是攻擊協議，是恢復已確認交易所必需的。中本聰[1]通過考慮某種特定攻擊，即所謂私有雙花攻擊，分析了該特性。注意，這裡經典通信模型屬於部分同步模型。在過去十年裡，一個相關研究問題是搜索最壞情況下攻擊策略，識別在對手權重方面的安全閾值。近幾年文獻[22]和[23]給出幾種最長鏈協議的嚴格一致性限制，但這些安全閾值在部分同步情況下有效，在異步情況（如[24]）下無效。
還有一項研究調查如何通過對通信層面施加更大影響來彌補其較低權重。這種攻擊中最突出特點是均衡攻擊[25]，包括具有均衡挖礦能力的多個節點子組之間的網絡通信。
我們對這一討論特別感興趣，因為我們提出了同時在通信層面和對手層面建模的框架。我們在異步通信模型中獲得了不可能性結果，這點不足為奇。儘管如此，在進一步同步性假設下，我們證實如果對手權重不超出特定閾值的話，那麼協議可以保證存活性和安全性（以非常高概率）。所得安全限制是為任何可能攻擊策略設定的，可根據協議進行配置。
在異步模型中導致不可能性結果的情形通常被認為與實際目的無關，如文獻[26]和[27]。這麼做的理由是，在實際應用程序中，區塊延遲隨機性如此之大，以至於不可能發生特定情況。雖然我們在一定程度上同意這種OTV 推理，但我們在核心投票協議中添加了第二個共時性級別，以此獲得嚴謹安全閾值。我們將共識協議視為兩層解決方案。第一層按異步設置工作，在正常網絡條件下可快速安全地確認。第二層以節點的可選同步性為基礎，可在最壞情況下找到共識。同步水平取決於分散隨機信標或公共貨幣，使協議對類似上述均衡攻擊的攻擊具有魯棒性。自文獻[28]發表以來，人們就知道利用共識協議的隨機化來規避不可能性結果，這樣便引入了局部隨機性。該文獻介紹一種常見幣種[29]，並將其運用於幾種方法。
性能。為共識協議效率界定指標並非易事，因為它依賴許多不同方面。自然選擇是參與者之間發送的區塊數量，對於同步模型則是通信步驟數量。在DLT 中，常用指標是每秒交易數量和確認時間。由於我們協議採用的是隱式投票，節點之間不交換直接區塊，其區塊複雜度達到最佳（如果選票是通過無論如何都會發送的區塊投出）。我們估算了確認時間，並顯示其對權重分佈的依賴關係。在本研究中，我們並未評估定量性能指標，如吞吐量和能源消耗。此類研究將在後續研究中進行。
一個常見誤解是，異步共識協議並不適合時間緊迫的應用程序[26]，其謬論是同步協議提出很強的同步性假設，而一旦這些假設得不到滿足的話，安全性就會受損。我們認為恰好相反，異步協議可能更適合時間緊迫的應用程序。在通信良好情況下，以具有基本安全裕度的網絡延時估算的同步模型為基礎，交易審批速度要快得多。
基於領導的區塊鏈架構的一個主要缺點是缺乏可拓展性。為了更加精確，我們設為網絡延時， 為區塊發布率，q 為對手權重，那麼在文獻[2]和[22]之後，協議安全性條件表示為：
為了設計能夠應對最大對手權重q 的彈性系統，此方程給出安全發佈區塊的最大速率限制。比如，如果在近期領導方面有分歧，可能出現安全違規。這些分歧可能是並行[30]生成區塊或某些攻擊場景[31][32]造成的。為此，區塊鏈可能會重組，特別對於區塊生產率很高的DLT[33]。
在我們的案例中，本文在協議吞吐量方面無理論上限；但我們協議在可拓展性方面局限性仍需在未來工作中進行研究。
1.1 基於DAG協議的相關工作
我們在總論中提到許多相關工作。在本節中，我們將重點介紹通用架構，提到以往使用DAG 作為底層數據結構提案。
基於區塊鏈協議是以區塊鏈條化或「線性化」為基礎，這種鏈條化或「線性化」構建起交易的全序。這通常是通過選擇領導來實現的。其中一個主要問題是，如果區塊創建速度高於其傳播時間，可能會造成許多競爭甚至衝突區塊，從而嚴重影響性能。因此，為了保證系統在安全參數範圍內，低區塊創建率限制了交易確認率和系統吞吐量。
性能。業界已經提出了幾種方法規避上文提出的線性化並提高性能。它們大多都有一個共同點，即區塊不僅可以引用前一個區塊，而且可以引用多個區塊，將底層數據結構從鏈條變為有向無環圖。的確，使用DAG 的想法在近十年來變得非常流行，如文獻[3]、[34] -[39]和總結性論文[10]。
DAG 結構的應用使對賬本並行寫入訪問成為可能，可以有效通過多個領導實現更快區塊時間。事實上，上述研究證實DAG 結構（而非鏈條）能夠減少確認時間，並提高協議總體安全性。
排序。不同DAG 協議在達成共識方式上可能有所不同。尤其DAG 數據結構的使用可以（但不要求）規避交易完全排序。例如在文獻[3]中，節點遵循並附加到最重DAG，而在多數其他提出的協議（如文獻[39]和[37]）中，共識仍然是通過創建全序實現。另一種通過交易排序來實現共識的方法是藉助原子廣播協議。此類協議使網絡參與者能夠就接收的交易（總）排序達成共識，而這種線性化輸出形成賬本。最可靠協議在異步環境中實現拜占庭容錯，並達到最佳通信複雜度，見文獻[40]和[41]。如文獻[42]和[43]以「通信史」編碼為基礎，以DAG 為形式，提出了改進措施。我們協議與上述方法有所不同，因為在我們設置中只需要偏序。
無領導。 DAG 也能促進無領導共識發現。比如，DAG 數據結構可以用來記錄直接投票機制結果，該機制在參與者之間進行直接查詢，如文獻[13]和[44]。但我們注意到，文獻[13]作者並未正確分析其提出的協議，該協議是否具有所需屬性尚不明確，如文獻[45，第2.3 節]。直接投票法可以視為與我們的ansatz 正交。在ansatz 中，我們跟踪現有依賴關係，並藉助DAG 隱式投票方案來解決衝突。文獻[43]也採用隱式投票方案，但最終需要對DAG 進行線性化。
1.2 結果
中本聰「最長鏈規則」的兩個主要問題是可擴展性嚴重受限，缺乏並行性。缺乏並行性導致底層通信網絡需要強同步性假設。我們所提出的共識協議，在異步模型中高效快速運行，並具有高度並行性，這點是通過以「最重DAG 規則」代替「最長鏈規則」實現的。由於所產生共識並非基於交易全序，這樣可以對交易進行流處理。對於智能合約更新和可選共享解決方案驗證而言，優化變得越來越重要。
區塊鏈另一個不太為人所知的缺點是需要礦機或驗證器這類這些中間媒介。我們通過啟用賬本無領導寫入權限，將系統簡化為資金擁有者和節點二分結構，來消除這種依賴性。節點額外承擔類似驗證器的角色。節點提出新的區塊，而這些區塊包含來自資金擁有者的交易，並將其添加到Tangle，節點利用添加程序對前面區塊進行驗證和投票，從而形成一種高效的隱式投票方案。
我們提出了一種以廣義權重函數為形式的節點投票權的泛化。這種泛化使我們協議有較高可配置性，適應需要實現該投票權的系統的需求和安全要求，比如無需許可或需許可。我們引入一種異步無領導協議，該協議在Tangle 中採用基於權重投票方案。通過隱式投票跟踪交易支持者（即節點）。交易確認狀態可通過閾值標準加以確定。我們提供各種核心組件算法。更準確地說，闡述如何通過隱式投票方案來更新支持者列表，以及節點如何將其區塊附加到Tangle。我們提供了系統收斂性、存活性和安全性定理。首先，給定一個隨機的、不可預測區塊流，定理7.1 保證，如果對手權重小於50%，系統將最終收斂至共識狀態，但在這種情況下，系統不給出安全保證。其次，我們通過擴展協議，借助某個常見幣種，引入以特定時間間隔同步節點的能力，並提供安全性和存活性保證。定理10.1 給出該擴展協議安全保證。
1.3 論文結構
本論文結構如下。第1.4 節概述所用符號、首字母縮略語和術語。第2 節概述本文所用一些圖表理論的初步研究。第3 節提供基本網絡環境，所提出的Sybil 保護機制在該環境中運行。第4 節描述Tangle 數據結構功能，以及如何用其確認區塊。第5 節概述基於現實的UTXO 賬本，該賬本構成我們方法的中心組件，有助於跟踪誠實節點對沖突交易的看法。第6 節介紹投票協議和交易的確認。第7 節定義通信模型和對手模型，並在第8 節和第9 節中探討系統存活性和安全性，特別演示了某些試圖創造「亞穩態」的攻擊，在特定情況和較強對手假設下，可能會造成問題。第10 節提供解決方案，引入以更大時間間隔同步節點的能力。最後，第11 節對未來研究方向做出展望。
我們以若干圖表結構作為共識協議基礎。表1 概述了所用圖表。
點擊此處可下載並閱讀全文。
免責聲明
本研究報告內的信息均來自公開披露資料，且本文中的觀點僅作為研究目的，並不代表任何投資意見。報告中出具的觀點和預測僅為出具日的分析和判斷，不具備永久有效性。此外，在任何情況下，本機構及作者不對任何人因使用本報告中的任何內容所引致的任何損失負任何責任。
