在我们系列博文的最近一期,我们介绍了一个新的账本模型,它允许节点理解冲突之间的因果关系。
在这一部分中,我们将用一个新的基元–广义投票协议–来扩展用于描述分布式系统的理论模型,然后为这个基元的一个实例提供规范,该实例使用新获得的自由度来实现最佳协议性能。
理论模型
在试图为分布式系统中使用的组件建立理论模型的过程中,分布式计算研究领域已经确定了基本构件的集合。
这些分布式计算基元是对协议的一般化、高层次的抽象,与它们的实际设计和实施完全无关。
这种抽象不仅允许研究人员比较和研究解决类似问题的不同解决方案的性能,而且还允许创建模块化软件,当新的和更好的解决方案出现时,系统的各个元素可以被交换。
原子性广播
与共识领域相关的最突出的分布式计算原语之一是原子性广播。
它描述了一个协议,确保分布式网络中的所有节点以完全相同的顺序收到相同的信息集–因此是广播。它之所以被称为原子性,是因为该协议要么在所有参与者中成功,要么对所有参与者停止。
注:有几个不同的协议实现了这一基本原则,但最突出的可能是Hashgraph和HoneyBadger。
广义的投票
我们已经讨论了建立总秩序是如何直接导致当代DLT的局限性的,因此我们想提出一个不依赖于总秩序的不同的、更通用的原始方法。
我们称这个基元为广义投票,它描述了一个协议,确保分布式网络中的所有参与者最终收到相同的消息集,并且在这些消息存在冲突的情况下,最终决定一个单一版本的真相(truth)。
这个基元是通用的,足以涵盖所有形式的共识(包括中本聪最初的区块链设计),这是一个很好的指标,表明它是一个真正的基元。
注:原子广播协议原来是通用投票协议的一个专门版本,因此“实际上”不是一个真正的原语,因为它对底层设计做出了假设(即通过建立一个总顺序来解决冲突)。
在介绍了我们新的投票协议的理论基础之后,我们现在将继续提供规范中缺少的部分。
我们将以自下而上的方式逐步介绍这些概念,从网络层开始,然后将这些概念扩展到包括共识。
网络层
与其他DLT类似,我们使用一个点对点的网络,节点与固定数量的邻居通信。
绿色节点有5个邻居
邻居的选择可以通过手动的相互对等,通过使用自动的对等发现或两者的组合来实现。
注意:IOTA提供了一个默认的对等策略,允许节点自动寻找邻居,无需用户干预。
八卦协议(Gossip)
由于我们的协议是基于四重记账法的原则,向账本写账就像向网络广播一笔交易一样简单。
因此,一个想要发布交易的节点向其所有的邻居发送一条带有交易的消息,这些邻居将更新他们的账本并递归地传递该消息。
节点交换包含交易的消息
这种通信形式被称为八卦协议,由于它是基于只与固定数量的邻居交换信息,它可以扩展到任意数量的参与者。
崩溃容错
到目前为止,我们的协议是可扩展的,但它还不可靠,因为有几种情况可能会阻止一个节点接收所有的信息(例如,离线或故障)。
为了解决这个问题,我们将使用中本聪的想法,使信息形成一个DAG(有向无环图),后来的信息参考先前的信息。与每个区块只引用一个区块的区块链相比,IOTA中的一个消息引用了两个父区块,这使我们能够摆脱建立总排序的需要。
每条消息都参考了之前的两条消息
一个节点如果收到引用未知父块的消息,可以向它的邻居请求丢失的消息。这个简单的机制保证了,即使是已经离线一段时间的节点,只要他们重新上线并收到最近的消息,就能够递归请求他们错过的消息。
递归请求缺失消息的行为被称为固化,而在其直接或间接祖先中没有空白的消息被称为固体。
分布式系统处理不可靠的参与者通过不可靠的媒介进行通信的能力被称为崩溃容错。
Tangle
由于产生的DAG看起来与区块链有点不同,我们想花点时间,介绍一些额外的术语。
引导网络的第一个消息被称为创世消息,当没有其他消息可以参考时,节点会参考它。默认情况下,它被标记为固体。
还没有被其他消息引用的消息,被称为Tip,在发布消息时设置这些参考的过程被称为Tip选择。
紫色的消息是DAG的顶端
所有被一条消息直接或间接引用的消息被称为它的过去锥体。
紫色的消息形成了蓝色消息的过去锥体
相应地,所有直接或间接引用某条消息的消息被称为它的未来锥体。
紫色信息构成了蓝色信息的未来锥体
只有极少数节点看到的消息被后来的消息引用的机会较低,在罕见的边缘情况下,可能发生消息根本不被引用的情况。
我们称这些消息为 “孤儿”,一旦发现没有人再引用它们,它们就会被清理掉。
红色的消息没有被其他人接收,也不会有任何影响–它是孤儿。
结论
我们已经指定了一个非常简单的广播协议,确保每个节点最终都会对网络已经处理过的消息有一个类似的认知(孤儿被忽略)。
我们没有像原子广播协议那样,不断监控每个参与者,并在太多节点出现问题时停止网络,而是给节点以追赶的能力。
注:这个非常简单的想法,即给予节点追赶的能力是中本聪最大的突破之一。
它不仅允许节点可靠地弥合次优网络条件的时间,而且还允许任何人随时离开或加入网络–它是真正的开放和无许可。
共识层
到目前为止,我们的协议是非常简单的,只需要在每笔交易中发送两个额外的哈希值,但我们也没有真正解决共识这个难题。
虽然达成共识通常被认为是一个非常复杂的话题,但我们将看到,我们的协议实际上已经完成了,只是需要一些小的调整来提供共识。
了解中本聪
为了理解下面的章节,我们首先需要改变我们看待区块链的方式。
与其把它们看成一条最长的链,不如把它们看成一棵树,所有被放弃的分叉仍然可见,关于哪个分叉应该占上风的投票结果被计入竞争链的长度。
现实中最长的链只是竞争分叉树上的一个分支。
中本聪的区块链不仅仅是一个包含状态变化的消息序列,它也是一个投票机制,每个区块都为一个特定的分叉投票。
这个小小的视角转变导致了一个真正重要的观察。
中本聪的区块链中的每个引用都会对潜在的无限制数量的分叉进行投票,其大小不变的哈希值使得消息传递的复杂性完全不变,并且不受诸如网络规模等因素的影响。
这种形式的虚拟投票–节点通过复制的数据结构中的引用来表达他们的意见,而不是交换额外的消息–是如此高效,甚至不再使用中本聪的共识的项目仍在使用这些原则来通知网络的其他部分关于状态的变化,我们很可能会找到一种更有效的方式来压缩意见。
注:赋予连接信息的哈希值以意义,并让节点有办法理解这种意义,是中本聪的第二大革命。
虚拟投票
由于我们的分类账模型可能会产生大量的冲突,而投票通常是一个昂贵的操作,我们决定复制中本聪的想法,把每条信息变成投票。
为了能够让我们的消息在我们的四重记账本的分支上投票,我们首先需要把信息从账本投射到纠结中,然后给我们的参考信息一个含义。
因此,我们对我们的协议做了如下调整。
- 一个发出包含交易信息的节点,为这个交易所属的分支投票。
- 消息之间的引用意味着认可,因此每个消息都会递归地投票给它直接或间接引用的消息的分支(投票沿着纠结中的边继承)。
- 为两个成对冲突的分支投票的消息被认为是无效的。
一个消息所投的分支是通过连接其父辈和所包含的事务的分支来确定的。
一个消息继承其父辈和所包含的事务的分支
例子
理解所有这些工作的最简单方法是看一个例子。
让我们假设我们有一个没有冲突的纠结,所有的消息都包含诚实的交易,并相应地投票给我们的四合一会计分类账的主分支。
在没有冲突的情况下,信息只是见证了其他信息并为主分支投票
现在让我们假设,一个攻击者发布了一个双重消费–一个包含交易的消息,与之前发布的其他消息之一相冲突。
现在发生的事情是,两个冲突的事务将被记录到它们对应的分支中,这些新引入的分支将根据我们刚刚定义的规则自动传播到Tangle中的消息中。
所有的消息在一个冲突的消息的未来锥,投票为相应的分支被网络接受。
分支DAG:绿色分支比红色分支获得了更多的批准和投票
共识规则非常简单:得到最多认可的分支获胜。如果出现平局,节点将选择哈希值较低的分支。
类似于区块链,后面的块通过附加到获胜链来强化之前的决策,我们协议中的节点也继续引用获胜分支的消息——这使得推翻之前的决策变得越来越难。
与区块链(每个块只发布一个验证器语句)不同,IOTA中的节点不断地与每个已发出的事务分享它们的意见。
这解决了中本聪的原始区块链设计的最大问题之一,因为它允许网络在异步网络模型中运行,并并行收集大量的确认,以尽可能快地达到最终结果。
事实上,交易越多,我们能够收集的票数就越多,达到最终结果的速度就越快–用户越多,网络就越快。
去中心化的身份
到目前为止,我们的协议是非常通用的,对所使用的sybil保护没有任何假设,但由于我们想建立一个基于身份的共识机制,不同的节点在共识过程中有加权的影响,我们需要对我们的协议做另一个调整。
为了能够将每个信息与它的发布者的权重联系起来,我们让每个节点对他们的信息进行签名。
在两个哈希值的基础上,我们在每个消息中加入发布者节点的身份和签名
这样一来,每条消息就可以客观地与在共识过程中具有一定影响力的特定发行者联系起来。
注意:在采用率低的时候,最有影响力的节点会定期发布空消息以保证网络安全。
消息有效载荷和层
为了实现以数据为中心的用例,我们允许消息不仅携带交易,而且携带任意的数据有效载荷。
每个有效负载的第一个字节对其类型进行编码,该类型可用于动态更改其解析和转换为内存中表示的方式。
与TCP/IP允许在其通用数据段之上定义额外的协议一样,这允许我们创建更高层次的协议。
注意:非交易有效载荷将始终与主分支相关联,因为它们在第1层没有固有和共享的冲突概念。
去中心化的应用程序和虚拟机
节点可以安装插件,定义一个特定于有效载荷的虚拟机,解析和处理不同的有效载荷类型,创建一个分散的应用程序,在所有安装了相同插件的其他节点中复制其状态。
插件使用事件驱动架构来监听包含相应有效载荷类型的消息。
由于任何DLT使用在节点之间复制的消息来达成共识,它甚至有可能在这些虚拟机内运行具有特定用例共识算法的额外DLT。
节点可以单独决定处理哪些有效载荷,但为了达到良好的去中心化水平,去中心化的应用需要有合理数量的参与者。
含有某个节点不感兴趣的有效载荷的消息仍然被八卦,但需要很少的计算开销,因为它们被当作通用数据片段处理。
注:我们在GitHub资源库中提供了一个去中心化和抗审查的聊天应用程序的概念证明。
父级类型
由于即使是虚拟投票机制仍然是一种投票机制,其结果在前期并不明确,可能而且会发生诚实的节点将他们的消息附加到DAG的某个部分,而该部分被证明不是获胜的部分,这些消息的有效载荷将不得不在之后被重新附加。
喜欢红色或绿色分支的节点永远不会同时批准红色和绿色分支,但是会批准蓝色分支
这就产生了一个博弈论上的问题,即节点会被激励将他们的信息附加到已经决定的旧信息上。
如果所有的节点都是理性的,并且会相应地修改他们的tip选择,我们将无法在投票中取得任何进展,因为没有新的消息会到达,从而批准冲突并推动系统得出结论。
含有有效载荷的诚实消息如果引用了DAG的错误部分就不能被批准,原因是批准总是针对消息的整个过去锥体,而批准两个双花的消息被认为是无效的。
为了解决这个问题,我们引入了不同类型的父引用,它们意味着不同的事情。
强父级:投票给被引用的消息和它过去的锥体中的一切。
Message4继承被引用消息的所有分支(包括它们过去的锥体)
弱父级:投票给被引用的信息和其过去的锥体中的所有内容。投票给被引用的信息和其过去的圆锥体中的任何内容。
Message4引用具有弱父级的Message3,并忽略其过去锥体中的分支(蓝色)
认同(Like)父类:投票给被引用的消息和它过去锥体中的所有内容(如果在另一个父节点中存在冲突的分支,那么以这个父节点中指定的分支为准)。
Message4忽略蓝色分支,因为它与绿色相冲突,我们更认同绿色(与我们的特定的认同父类)
这些新的引用类型现在允许节点独立引用其他诚实消息。
结论
我们已经为一个新的底层投票协议提供了高水平的规范,该协议完全基于中本聪的想法,并允许节点完全异步和实时地处理交易。
所产生的协议不仅在概念上非常简单,而且还具有其他一些理想的特性。
- 该协议是可扩展的(支持任意数量的节点和验证器)。
- 该协议是稳健的(即使验证者突然消失,它也能继续运行–我们唯一需要的是对重量的相对感知,以便做出决定)。
- 该协议是快速的(确认时间接近实时)。
- 该协议是安全的(对旁门左道的攻击者有弹性)。
- 该协议提供崩溃容错性(发生故障的节点有办法赶上)。
- 该协议提供了不变性(由于消息是通过哈希值连接在一起的,如果我们假设节点可以就正确的提示集达成一致,那么过去的决定就不能被改变)。
- 该协议是高效的(它在协议的任何地方都没有不必要的开销–它甚至不发送投票)。
- 该协议具有最大程度的抗审查性(没有任何实体控制对账本的写入权限–甚至是矿工)。
- 该协议是灵活的(与任何类型的Sybil保护兼容–例如PoW、PoS、dPoS、VDFs、许可委员会等等)。
虽然从概念的角度来看,这些概念非常简单,但它仍然是一个巨大的工程挑战,因为你有许多相互依赖的层次和水平,必须全部携手合作。
我们不得不发明了几个新的数据结构和索引类型,使我们能够有效地管理所有这些,并在或多或少的O(1)中运行,而且我们仍在优化代码库的一部分。
我相信可以合理地假设,这里介绍的概念构成了你可能会建立的最简单和最有效的投票协议。我们不可能比在每个交易中加入两个哈希值更好(如果你能用一个哈希值就能做到,我真的会很惊讶)。
但是,最有效的投票机制还不是最有效的共识机制,我们将在本系列的后续部分继续改进和扩展我们的协议。
简而言之
我们设计了一个协议,允许节点直接写入分布式账本,没有任何中间人,只需与他们的邻居分享交易。
每笔交易都带有几个字节的小标签,节点只需看一下标签就能达成共识,无需交换额外的信息。
该协议与中本聪式区块链同样强大和安全,即使有非常多的节点下线,也能继续运作。
本文原文非中文版本,由BruceX进行翻译,如若转载,请注明出处:https://www.iota.love/202110/the-trust-machine-part4-the-tangle-a-generalized-voting-protocol/