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​​​​