科普 | 回收协议：DAG的分布式共识

DAG，叫做有向无环图，这是一种计算机学上面常用到的拓扑数据结构。他要求每一个交易都必须验证前面两条旧的交易，这样就形成了层层确认的结构，使每一次交易形成了一个链条。

近年来，看到了越来越多的基于DAG的新型加密货币。它最初（最有可能）在2015年开始使用DAGCoin，随后是许多其他项目，如IOTA，Hashgraph，Chainspace，PARSEC，Fantom，当然还有Aleph。

在本文中，将首先分享一下对DAG在空间中受到更多关注的原因的看法，但主要关注点将是核心共识层。通常，这些协议的部署方式是在选定的委员会（IOTA除外）之间建立核心共识，并且任何希望执行交易的用户必须联系委员会成员（或成员）以便包括交易代表用户在共识中考虑。委员会可以预先定义，如Hedera Hashgraph等许可解决方案，或者由社区选举和随后重新选举，如Aleph或Lisk的情况。

回顾

早在90年代，就引入了一系列新的共识协议，称为PAXOS。PAXOS允许多个服务器就共同决策达成一致，并允许实现状态机复制（SMR）系统，即协调客户端与服务交互的容错服务。主要思想是协调多台机器上的数据存储，从用户的角度来看，与系统的交互与单个服务器的通信无法区分。换句话说，用户在线拥有他/她的“驱动器”并且甚至不知道该“驱动器”托管在多个服务器上，因为内部工作被隐藏在友好的用户界面下。

这如何与区块链连接？如何看待它的方式，所有分布式账本技术（DLT）的主要目标是重新实现传统上以分布式和无信任方式依赖可信第三方（通常是公司或政府）的服务。听起来有点像SMR的扭曲。

那么为什么没有25年历史的基于PAXOS的加密货币呢？一个重要的技术原因浮现在脑海中。在无权限的开放世界场景中构建可靠的系统 - 用户可以主动尝试破坏整个系统 - 与在拥有所有服务器的权限设置中构建系统完全不同，可能发生的最糟糕的事情是简单服务器故障。

名称

使用传统术语，构建现代类似加密货币的系统所需要的是原子广播（ABC）或总订单广播，其中所有过程都同意所有消息/事务的共同排序。请注意，正确实施的原子广播足以阻止双重攻击。考虑用户尝试提交多个冲突事务的情况。在这种情况下，交易根据既定订单进行核算，确保相同的资金不会花费两次。这个问题通常用于构建一个公共时钟，用于显示每个事务的时间，该时钟基于所有进程的内部时钟（对于错误进程可能会出现偏差）。

区块链中的“链”恰恰代表了这种排序。虽然Nakamoto共识为这个问题提供了革命性的无法解决方案，但现在可以看到它存在速度和可扩展性的固有问题。

在尝试解决双重支出问题时，订购所有交易实际上是过度的。在美国购买冰茶的人不应该等待根据在中国购买咖啡的人的交易订购此交易，即使它同时发生。通过使用牢记其独立性的数据结构，可以独立处理这两个事务并更快地进行验证。

在为货币设计的分布式系统中要解决的更容易的问题是可靠的广播（RBC）。这允许所有进程在有限时间内就给定事务的有效性达成一致（不排序所有事务），并且通常比总订单广播快得多。加密货币的申请非常简单：给定用户的交易使用连续的自然数进行索引，并且只要协议及其所有前任被认为有效，就会处理任何交易。最后，所有这些用户的交易都按照与其索引相对应的顺序进行计算，从而防止任何冲突的交易。

虽然RBC无法在所有应用程序中取代ABC，但它是一个有价值的附加组件，因为它提供了一种执行加速交易的安全方式。关于RBC最重要的是利用一个小技巧，可以在实施ABC的同时获得RBC而无需在进程之间进行任何额外的通信。

前程回顾

1978年，莱斯利·兰波特（Leslie Lamport）定义了一个概念，它大大简化了对分布式系统中事件排序的思考，即之前发生过的关系。然后可以将解释定义以更好地符合说明的目的：

这种关系保证了不同进程的时钟在它们之间发生的通信方面是同步的。这是一个相当弱的关系，但在某些应用中它就足够了，而在其他应用中它可以用作具有更强属性的时钟的基础。

在现实生活中，流程可以欺骗并伪造他们的时间戳。这使得时间戳单独不适合作为构建共同总排序的决定因素。通常，需要一个复杂的算法，但有一点需要注意：如果事件以“合理”的方式完全排序，那么在一个过程中执行的事件，以及发送/接收事务的事件应该与发生的事件一致 - 在关系之前。

回到DAG

此时明确一点：DAG和偏序（posets）是（基本上）描述同一个对象的两种不同方式。每DAG可以通过添加传递性（即，寻找被变换成偏序传递闭包），和每一个偏序可以通过仅着重于直接之前是元件/后彼此被解释为一个DAG。稍微滥用符号，然后会考虑一个偏序为DAG结构，因为将永远不会有兴趣在一个交易是否是直接高于另一个，所以的设定部分的一些关系有序的概念>是一个更自然的描述。

新波协议的常见思想是使用偏序作为查找总秩序的过程中的中间步骤。通常，通过引用一些先前事务的哈希值将新事务（或事务容器）附加到结构，类似于Merkle树。出于本文的目的，将引用诸如Merkle posets之类的结构。因此，各种协议使用不同的规则集来将中间结构转换成所选择的最终排序。以下注释显示了这与之前发生的关系如何联系：

证明：由于T_2> T_1，在它们的创建之间，T_1的发行者（例如，过程A）需要将关于它的信息（直接或间接）传递给T_2的发行者（过程B）。因此，根据定义，T_2发生在T_1之前。

共识层

因此，由一个新波协议构建的每个Merkle poset都需要是之前发生的poset 的子post（不一定是诱导的）。然后，每个进程保留其Merkle poset的版本并定期与其他进程同步。使用这种数据结构的基本原理是，它允许协议将它们可以操作的两个层分开：

1. 在第一层中，进程向Merkle posets添加元素（例如，事务）。然后，一种更简单的方法 - 例如，一个八卦协议 - 用于同步他们的信息。这一层非常简单：进程随机连接和交换有关新事务的信息。诀窍在于交易结构为“Merkle posets”，因此它们保留了有关该层流程之间通信的一些信息。在这个级别上不需要针对双重攻击的保护措施，并且很容易通过小额费用来抵制交易垃圾邮件。
2. 第二层是协议独特魔法发生的地方。一旦拥有一个本地存储的Merkle poset，进程就可以计算总排序。该计算的规则因协议而异，协议可以安全运行的假设也是如此。一个共同特征是该层上的所有计算都是在本地完成的，因此进程不需要交换任何其他信息。
   虽然这种划分对于许多加密爱好者来说可能并不令人惊讶，因为它在该领域已经相当普遍，但在经典的共识算法中并不常见。尽管在加密中感觉非常自然，但是在Hashgraph开始将这个概念作为他们的“八卦八卦”技术推销之前，它有点被忽视了。

共识是在旁观者眼中

为什么这很重要？主要是，它降低了通信成本，因此每个事务只需要发送一次到每个进程。仅使用结构性poset信息，可以通过新事务可用于验证和订购旧事务的想法来实现共识。

在传统协议中，当流程就特定交易的有效性达成一致时，需要进行多轮通信（取决于底层网络的特定假设），在此期间，他们仅就相关交易通知对方他们的意见。Merkle posets的关键创新是，创建交易时流程所拥有的信息可以从交易中的位置推断出来。有了这些信息，就不必询问一个过程，因为我们可以预测答案。因此，可以说实际的共识是在Merkle poset中“模拟”的，或者“共识在眼中”在旁观者中，“正如Danezis和Hrycyszyn的诗意所说。

降低

在Aleph中，将原子广播（总订单广播）问题简化为二进制协议（BA）。顾名思义，实现二元协议是一个相当简单的概念。要达成二进制协议，进程需要就单个二进制值达成一致。但是将ABC减少到BA的过程是什么？

首先， Merkle poset是由作为交易容器和可能的其他数据的单元构建的。单位被分成连续批次，然后每个批次以确定的方式单独订购，然后批次按其指数完全排序。这背后的基本原理是，在同意特定批次的组成之后，所有过程都很容易计算相同的排序 - 例如，将订单基于涉及单元散列的函数。

为了把所有单位成批，协议选择其中的几个作为计时单位，以作为通用的时间戳。在选择定时单元之后，批次的构造以下列方式进行：对于给定单元U，其批量索引等于最低索引k，使得U在第k个定时单元之下。这个定义具有有限性的好处，即一旦选择了索引高达k的所有定时单元，就不能将新单元添加到索引高达k的批次中。这源于这样一个事实，即新单位只能添加到旧单位而不是下单位。

该如何选择计时单位？当构造poset时，我们将单元的级别定义为大致与创始单元的距离（省略技术细节），并将每个级别上生成的每个过程的第一个单元称为主要单元。然后，对于每个过程，我们基于这个问题运行二元决策：“这个过程是否在k级产生了主要单位众所周知？”但BA的执行方式保证了所有主要单位中至少三分之二的正面结果。当从BA中获得肯定结果的所有可能候选者中选择一个主要单位时，我们使用所有过程的预先计算的排序，每个级别的不同的一个，并根据此排序选择第一个。

警惕的读者现在可能会问自己这些问题：是否需要这些麻烦？为什么不使用poset级别将单位分成批次？推理很简单，因为级别永远不会是最终的，因为任何进程都可以将单元添加到任何现有级别，即使poset中已经有更高级别。

总而言之，一共减少包括三个步骤：

1.  将原子广播问题减少到“普通批处理部门”。
2. 进一步将其减少到公共子集问题（选择时序单位）。
3. 将其简化为简单的二进制协议。

重用

这些减少的一个重要特征是除了Merkle集合的同步之外它们不需要任何额外的通信，Merkle集合是协议的组成部分，因为这些结构的同步是事务在进程之间传播的方式。最后一步是设计适当的BA算法。我们使用经过修改和改编的ABBA（异步拜占庭二元协议）版本，因为它很容易将其纳入到poset结构中，并且在网络假设方面具有最佳性能（异步性和对高达⅓N-1拜占庭故障的弹性）。由于减少是在Merkle poset上完成的，没有任何额外的假设，我们只是继承了这些属性，因此自动将这些放在少量的协议中，这些协议可以做出这种声明，并通过证明来证明它。

回收

总之，通过使用多个减少和本地模拟ABBA协议，这次获得了用于原子广播的完全异步和BFT安全协议。这可以在没有整个Merkle posets技巧的情况下完成，因为像Honey Badger BFT这样的协议已经做到了这一点。为什么要打扰DAG，所有这些都是废话？

Merkle posets的主要优势在于它们能够在本地模拟一致性算法，因为它们可以通过“回收协议”无需任何额外数据来运行该算法的任意多个实例。

仅此一项就是一个巨大的带宽节省，它允许部署SNAP（简化的非安排协议协议），这是我们自制的可靠广播协议，允许快速安全的令牌交易。

还有一种无法预料的好处。在传统的异步协议中，总是存在一个机会，即给定的合法事务广播太慢，并且协议以否定的决定终止，即它不被处理。在这种情况下，此交易和所有相关的通信成本基本上都被浪费了。如果要验证事务，则需要重新发送，并且需要再次运行达成协议的基础协议。实质上，这种重复使用了昂贵的资源并降低了效率。

相反，当使用Merkle posets时，如果将事务添加到poset，则永远不需要再次添加。即使给定协议的第一个实例未能验证它（即，在我们的示例中，它未能包含在给定批次中），它可以在以后再次重新运行而不带任何带宽成本。因此，对于使用Merkle posets的协议，没有任何东西丢失，一切都被回收。

结论

很明显，传统区块链的吞吐量不足以维持将在某些DLT系统之上构建的大量未来应用程序。因此，预计在未来几年，将可以看到更多的解决方案，专注于克服这一缺陷。目前关于加密空间的研究正处于发展阶段，主要认为避免重新发明轮子的唯一方法是将其置于经典作品中。此外，完全理解使用经典协议对Merkle网络的影响的探索才刚刚开始。

（作者：区块链安全档案，内容来自链得得内容开放平台“得得号”；本文仅代表作者观点，不代表链得得官方立场）