本文介绍 Tangle 2.0 的理论基础，这是一种基于有向无环图（DAG）的概率性无领导共识协议，称为 Tangle。
撰文：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 概述了所用图表。
可点击下载并阅读全文。
