IOTA Tangle 网络中的共识协议 — FPC(快速随机共识)

​​这是用来解释IOTA Coordicide中描述的FPC协议的系列文章中的第一篇。


本系列的主要目的是让社区了解最新的研究结果,并对有机会获得Coordicide专项资助的有趣的研究问题做出解释。正如您将看到的,这个主题非常广泛,并与Coordicide项目的其他部分的有许多联系和依赖。

针对这么复杂的问题,我们将尝试一次只解释几个要点,并将重点放在目前正在研究的问题上。尽管如此,我们已经意识到IOTA已经具备了有效和安全地解决Coordicide问题的所有关键条件。

余下的问题是找出解决方案的最优解,例如:

  1. 增加安全
  2. 增加可持续性(例如降低消息复杂度、降低PoW)
  3. 增加TPS
  4. 缩短完成的时间
  5. 增加实施的灵活性,以应对未来的挑战

现在,让我们来认真研究和了解一下这种“共识”到底是什么?

为什么需要共识?

分布式(去中心化)系统的共识,能让网络系统在分散决策非常困难甚至不可能的情况下,就所需的状态或意见达成一致。


分布式计算本质上是不可靠的。共识的达成能使分布式系统作为一个整体进行工作。这一挑战的重要性来自它的普遍存在,而容错是其中最基本的要求之一。

常见的例子包括:多副本的文件系统、时钟同步、资源分配、任务调度以及最后但也很重要的分布式账本。


分布式系统构成了计算机科学中一个巨大而经典的主题,相关的共识也是如此:有关此主题的简洁介绍,请参见《分布式共识是如何工作的?》。

现存的共识协议本质上是经典协议——例如基于PAXOS的协议——以及最近的游戏规则改变者:中本聪共识。这两种协议都有严重的限制。


传统的协议具有二次方消息复杂度,需要精确的隶属关系识别,而且易受干扰。另一方面,中本聪提出的协议虽然是健壮的,不需要精确的成员关系,但它依赖于PoW,这导致了众所周知的问题,如矿工算力竞争和不可扩容。

那么,如何在IOTA Tangle中达成共识呢?

让我们首先回顾一下中本聪共识。中本聪共识的一个绝妙想法是使共识具有不确定性或概率性。不同于(分布式)系统的所有节点都必须同意一个值的正确性,他们对该值正确的概率达成共识。

在这个共识协议中,领导者的角色由解决给定计算难题最快的节点承担;这个赢家向区块链添加了一个新块。通过这种方式,(分布式)网络正在构建不断增长的区块链,并就最长链或累积难度最大的链的有效性达成一致。

那么,为什么这种共识是概率性的呢?为了知道某个事务将被认为是有效的,比如在100天内,我们必须知道100天内最长的链将包含这个给定的事务。

换句话说,我们感兴趣的是100天内最长的链包含这个事务的概率。当包含该事务的块“更深入”地沉入链中时,事务将不会被“回滚(篡改)”的概率会增加。

例如,在比特币区块链中,建议等到交易被区块链上的6个区块收录了再进行。在此深度之后,事务被回滚的概率非常低。


这种效果也适用于Tangle 网络。一项交易越“深”——或者说被这种混乱“包围”得越“深”——它就会变得越不可变更。在下面的图中,深绿色事务被所有浅绿色事务验证。随着浅绿色事务数量的增加,深绿色事务在未来网络中不会变更的概率收敛到 1 。

但等一下,Tangle 与区块链不同!虽然区块链不允许包含两个冲突的事务,但是Tangle会可能暂时包含这样的事务。因此,恶意玩家可能会在Tangle 的不同部分附加了两个冲突的事务,如上图中的深绿色和橙色方块。

这些事务可能在混乱中“存活”一段时间,直到诚实的节点检测到冲突为止。一旦检测到这样的冲突,节点将决定选择哪个事务。在上面的例子中,深绿色的事务被混乱“包围得更紧”,最终应该得到所有节点的批准。

为了使Tangle成为一个真正的共识协议,我们必须对相互冲突的交易做出选择。而这一选择就是基于共识协议做出的。

我们是在原地打转吗?幸运的是没有:Coordicide提出了另外两个共识协议:快速概率共识(FPC)元胞自动机共识共识(CC)

本文的其余部分将专门介绍FPC,并解释如何在决定单个交易是否有效时达成共识。

在以后的一篇博客文章中,我们将讨论为什么这是可行的,以便在Tangle的级别上达成共识,并且我们将讨论在混乱中事务的最终结果。

什么是FPC?

通过阅读Serguei Popov和Bill Buchanan的最初的论文我们可以得知:FPC是一种低通信复杂度的无领导的概率二进制共识协议,它在拜占庭处境的架构中是健壮的。

而当我们继续深究所有这些术语的真正含义时,一个更轻的版本的FPC开始浮现出来,它很容易被实现,并且已经包含了大多数重要的功能。

我们假设网络有n个节点,分别以1、2、…、n进行标记。每个节点都有一个意见或状态。表示节点 i 在 t 时刻的意见表示为 s_i(t),意见取值为{0,1};这就是我们所说的二元共识的原因。

基本的思路是让多数节点进行投票。在每一轮中,每个节点都查询 k 个随机节点,然后根据多数节点的意见来设置自己的意见。就这么简单!然而,这种简单的多数投票结果对于错误节点和恶意攻击者来说是脆弱的。它需要一个额外的机制,事实上是一个额外的随机性,来保证它的健壮。

更准确地说,在每个步骤中,每个节点选择 k 个随机节点 C_i ,查询它们的意见并计算它们的平均意见 η 。

我们 用 𝝉∊[0,1] 表示第一轮的阈值,这能产生协议的一些非对称性(这是我们不久以后要讨论的另一个话题)。此外,我们引入了“附加的随机性”;我们让U_ {t},i=1,2,.....,为符合均匀分布规则Unif(𝜷, 1- 𝜷),的独立恒等分布随机变量,其中𝜷 ∊ [0,1/2]。

每一轮,每个节点 i 使用 k 个随机节点的意见来更新自己的意见;

然后开始循环,直到 t 不再大于0:

重要的是,在每一轮中,节点查询不同的随机节点集,并且在每一轮中更新随机变量 U_t 。


为了降低协议的通信复杂度,我们引入了一个局部终止规则。每个节点都有一个计数器变量 cnt ,如果该节点的观点没有变化,它的值就会增加 1 ;如果观点发生了变化,它的值就会被重置为 0 。

一旦计数器达到某个阈值 l ,即 cnt≥1 时,节点认为当前状态为最终状态。因此,节点将不再发送任何查询,但仍将回答传入的查询。下面的图表显示了变量 cnt 在 l=5、k=10 的每个节点上的典型演化,初始值为90%的 1 和10%的 0 。


在左边的图中,协议没有受到干扰,但是在右边的图中,20%的节点恶意地试图转到大多数诚实节点。在这两种情况下,最终所有诚实的节点都同意最初的多数。

我们想重点强调FPC中的普遍的随机阈值这一特性,并仔细参考FPC的模拟结果,以便为FPC中各种参数设置和攻击策略进行首次分析。

随机阈值的作用

Carl von Clausewitz在《战争论》中指出了战争中不确定性的重要性:

战争是不确定的领域;战争行动所依据的因素中,有四分之三笼罩在或大或小的不确定性的迷雾中。首先要有敏锐的智力,以便通过准确而迅速的判断来辨明真相。- Carl von Clausewitz, 1873

这与FPC中的随机阈值有什么关系?在简单多数情况下,投票这些阈值将等于0.5。卓有成效的攻击策略可以一直保持诚实节点的 η 约为 0.5,来防止协议的收敛(稍后我们会看到这样一个成功的攻击)。Popov 和Buchanan 的想法是在系统中添加“噪声”或“迷雾”,以增加潜在攻击者的情报的不确定性。

为什么这些措施很重要?在一个没有恶意节点的情况,η 的分布接近正态分布:

在一个不进行干预的情况下,诚实节点的意见可以保持接近 50:50 的情况。然而,随机投票产生的随机效应会最终导致协议的收敛。这一点与拜占庭式的框架是完全不同的。

让我们考虑一个攻击者的策略:将诚实节点分成两个同样大小的组,其不同的意见将导致诚实节点 η 值的分布如下:

那么攻击者如何才能做到这一点呢?

攻击者一直等待,直到所有诚实节点从所有其他诚实节点接收到意见。攻击者然后计算这些中间的中值 η 。现在,攻击者通过最大化这些 η 值的差异来试图保持 η 的中值接近 0.5 。

FPC如何防止这样的攻击?我们将确定性阈值(红色,虚线)替换为随机阈值(蓝色,虚线)。在下面的图中,每条蓝线代表一个特定的回合的随机阈值。由于这些阈值是随机的,对手无法预见如何分割诚实节点以保持50:50的情况。最好的方法还是把它们除以0.5。

然而,一旦蓝线(下图中r3中的蓝线)离红线足够远,对手就会失去对诚实节点的控制,协议就赢了。

在下面的动画中,您可以看到在没有随机性(阈值=0.5)的情况下应用这种对抗性策略以及添加随机性之后,协议的行为和结果。正如您所看到的,对手设法将节点保持在中间状态很长一段时间。但更糟糕的是,网络开始出现意见分歧,并导致共识无法达成。然而,在引入额外的随机性之后,共识很快就达成了。

当前的进展和后续工作

最后但同样重要的,让我们回到IOTA目前正在研究的一些工作,并举出一些将来协作的案例:

  1. 目前,我们正在进行全面的仿真,以研究不同类型网络拓扑下的各种攻击策略。其结果将使我们能够确定最优的随机性数量和选择协议参数。我们也在研究FPC对故障和随机阈值干扰的鲁棒性。
  2. 仿真结果表明,所得到的FPC收敛边界远优于Popov和Buchanan的理论收敛边界。各种参数设置仿真表明,存在所谓的“截止现象”。非正式地说,这本质上意味着协议只需要 m 个步骤,就具有很高的达成共识的可能性,而且协议需要 m 个以上步骤的可能性非常小。在这个方向上的理论结果将会非常受欢迎。
  3. FPC的实际应用效果还取决于节点的声望。由于节点的声望或法力在Coordicide项目的其他部分中也起着重要的作用,我们将在以后的博客文章中对此进行更多的讨论。无论如何,这个附加特性将使协议能更安全地抵御各种攻击。
  4. 上述在FPC中研究的参数在协议开始时就已确定。然而,为了提高安全性,同时降低消息复杂度(这听起来像是一个奇迹),我们正在研究FPC的改造版本。例如,如果一个节点的 η 接近0.5,节点可能决定增加查询的数量,如果是接近1,它可以决定减少下一步的查询数量或立即停止查询。
  5. 目前,机器学习被广泛地应用于各个领域,显示出它相对于传统基于规则的算法的优越性。我们计划使用机器学习,不仅用于错误和恶意节点的侦测,而且使用强化学习来识别出最有害的攻击策略。

我们期待着通过研究部门的眼睛,带您一起踏上令人兴奋的Coordicide之旅,希望您能像我们一样享受这个项目的发展。


一如既往,我们欢迎你的评论和问题,无论是在这里的评论或是在Discord上的#tanglemath频道。您也可以与我们进行更紧密的科学合作,并申请资助

作者不是IOTA基金会的成员。本文由他与IOTA研究小组的成员合作撰写。

原文链接:https://blog.iota.org/consensus-in-the-iota-tangle-fpc-b98e0f1e8fa​​​​

大熊

专栏作者:大熊

个人简介:我共发表了 29 篇文章,总计被阅读了8,584 次,共获得了 353 个赞。

作者邮箱 作者主页 Ta的文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注