Tangle 2.0 理論基礎“無領導中本聰共識”：最重 DAG

摘要

我們介紹 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 概述了所用圖表。