快速概率共识协议(FPC)的模拟

风使蜡烛熄灭,但助火燃烧。同样地,随机性、不确定性、混沌:你可以利用它们,而不是躲起来。你想成为火,渴望风来。

Nassim Nicholas Taleb

TL, DR

Serguei Popov最近引入的快速概率共识(FPC)(论文)在大多数时间内以最少的步骤得到共识,并且比Popov给出的理论上限要快得多。 论文声称在有附加随机性时,可以允许协议在其他协议失败的关键情况下仍然有效。 这些模拟表明FPC在各种攻击场景下确实非常强大。

介绍和设置

我们对Serguei Popov提出的快速概率共识(论文)进行了第一次基于模拟的研究。 由于该协议在非关键情况下非常安全和快速,因此本研究主要是针对试图达成对诚实节点的分歧,并主要考虑关键情况下的攻击策略。 这个帖子并非旨在对FPC进行彻底的科学研究; 它只是收集各种观察数据,以说明其功能。

问题

分布式网络如何才能就某个一位变量找到共识?

以前的答案

直到2018年,已知的共识协议基本上都是经典协议,即每个节点与每个节点进行通讯,以及Nakamoto(中本聪)共识协议。后者因其位于区块链技术的核心而闻名。但是,这两种协议都有严格的限制。为了理解新方法的重要性,我们列举了这些模型的一些不太方便的属性。经典协议具有二次消息复杂性,需要精确的成员资格知识并获得许可。 Nakamoto协议非常强大,不需要精确的成员资格。但是,它具有高延迟,低吞吐量且不可持续等缺点。而且,这两种协议都没有可扩展性。最近,加密社区提出了其他的一些方法,例如, 雪崩协议和NKN提出的元胞自动机方法。但是,我们想在此强调,在加密社区之外,这个主题早已有研究,可以参考文献:扰动网络中的分布式二项共识,以获得摘要和进一步的了解。关于没有拜占庭干扰的多数投票方面的文献很多; 我们仅提供最新的参考资料之一,内存有限的节点共识的通信成本,和最常见的维基百科

所有这些协议(Nakamoto协议除外)主要依赖于多数规则,并遵循可能最自然的直觉。 节点向其他节点查询其意见并采纳多数人的意见。 该模型的若干变体也被提出来了,以便保证最终所有节点收敛具有相同意见达成共识。 另一个困难是共识协议应该对网络故障和恶意攻击者具有鲁棒性。

新的方案是什么?

FPC引入了分布式的随机变量,允许协议在收敛速度和安全性方面获得理论结果。

根据研究论文的假设,该协议被证明是安全的! 然而,理论结果似乎远非最优,即使对于具有良好数学背景的人来说,论文中的公式甚至可能看起来都很可怕。

模型

我们假设n个节点想要就某一位变量的值达成一致,并且每个节点都可以访问网络中的任何其他节点。 部分节点是拜占庭式的,即它们由对手控制,他们要么推迟达成共识,要么打破共识(即至少让几个诚实的节点得出不同的结论),或者改变 诚实节点的最初意见。对抗节点数量所占比例用q表示。

共识协议的目标如下:

如果,最初绝大多数节点不是更喜欢1,那么最终的共识,很大概率,应该是0;
如果,最初绝大多数节点更喜欢1,那么最终的共识,很大概率应该是1 。

在这里,绝大多数超级多数仍然是一些松散定义的概念。 但是,您可以将绝大多数视为与50:50情况有统计差异的情形; 例如,对于某些固定的 \alpha> 0.5,1值意见的比例大于 \alpha。 超级多数则是已经接近共识,例如超过90%的节点都有相同的意见。

协议

协议取决于各种参数:

  • 0.5 < a \leq b <1:第一轮的阈值限制;
  • \beta \ in(0,0.5):后续轮次的阈值限制;
  • \m_0: 冷静期;
  • \l: 确定的时间长度; 连续轮次的数量(当冷静期结束时)具有相同的意见,之后它成为一个节点的最终结果。

重要的是,每个节点在局部决定何时固定它的意见。 一旦意见固定不变后,节点就会停止询问,但会继续回答查询。

现在该协议解释如下:

  • 每个节点根据一些合理的(本地)规则决定这个一位变量的初始值。
  • 在第一轮中,每个节点 j 随机查询 k 个节点并获得他们的初始意见。 每个节点 j 计算这k个节点中1值意见的比例 \eta_j;
  • 向所有节点揭示服从均匀分布Uni f [a,b]的随机变量 X_1。 这是中心化的随机变量出现的地方。
  • 每个节点 j 使用以下决策规则:如果 \eta_i 大于等于 X_1,则这个节点采用1值意见,否则采用0值意见. 这就是第一轮。

在随后的查询轮次中,动态规则非常相似:

  • 在大于等于2的 m 轮次中,每个诚实节点 j 随机查询 k 个节点,并记录它收到的1值意见的比例 \eta_j。
  • Unif [\beta,1- \beta] - 分布式随机变量X_m被揭示给所有节点。
  • 尚未拥有最终意见的每个节点 j 使用以下决策规则:如果 \eta_j 大于等于 X_m,则采用1值意见,否则采用0值意见。
  • 如果节点在冷却期后连续的 l 轮中都有相同的意见,那么这个节点会最终确定其意见。

协议是如何失败的?

共识协议可能失败的方式主要有三种:

  • 意见分歧失败 - 协议终止但诚实节点的最终意见不一致;
  • 终止失败 - 在很长一段时间后未达成共识;
  • 完整性失败 - 协议的结果并不反映诚实节点的初始意见。

对手策略

原始论文区分了两种不同类型的对手。

  • 谨慎的对手:任何对抗性节点必须在同一轮中保持相同的意见,即对该回合中收到的所有查询回应相同的值。
  • Berserk对手:对手节点可能会在同一轮中对不同的查询做出不同的响应。

所获得的理论界限适用于对手的任何可能策略。然而,为了进行模拟,我们必须考虑具体的对手策略。

在本研究中,我们假设最初在诚实节点中存在大多数1值意见,并且我们考虑以下不同的对手策略:

  • 始终响应0值意见; 对手试图将最初多数的1值意见转变。换句话说,对手试图达到完整性失败。
  • 传递n-1轮次中诚实节点的少数意见; 在这种策略中,对手试图改变最初的多数并延迟协议。对手仍然持谨慎态度,因为它在同一回合中传达了相同的意见。
  • 第三种策略是Berserk型的。 对手节点等待所有诚实节点收到来自所有其他诚实节点的意见。然后攻击者计算这些节点 \eta的中位数,并将给那些 \ eta 大于所有诚实节点\η中位数的节点响应 1值 意见,而给其他节点响应0值意见。这种策略试图将诚实的节点细分为两个大小不同的意见组。它不是最佳的,但它的实现简单快捷。
  • 第四种策略是谨慎的,但它更复杂。它试图将中位数稳定在0.5左右,使得\η的方差变为最大。
  • 第五个也是最后一个策略可能是最糟糕的情况。它是第四种战略的Berserk版本。

对手可能无法适应最后两种策略,因为所涉及的优化可能需要太长时间,并且似乎很难提出一种明显更好的策略来打破协议的安全性。 我们在此指出,我们的主要关注点是试图达成分歧的对抗性策略。 出于这个原因,策略5在这里被认为是最坏的情况。 由于我们认为分歧失败是最严重的失败,因此我们不会在此处提供有关终止失败的对抗策略的结果。

有时我们谈到协议的安全性,意思是最后所有诚实的节点都同意相同的观点。

参数选择

在本研究中,我们为所有模拟固定以下参数:

  • n = 1000:节点数
  • a = 0.55, b = 0.65 :(这些参数的选择将在很大程度上取决于“多数”的精确定义。)m_0 = 2:预热阶段的长度
  • l = 3:“确定阶段”的长度

以下参数列表将根据模拟而变化

  • k:每个节点发送的查询数
  • max_it: 共识协议停止前的最大迭代次数
  • \beta:从第2步开始对阈值变量的支持
  • adv_strategy: 对抗策略
  • q:对手节点的比例

对于每一组参数设置,执行1000个模拟。

模拟

我们考虑上述第2种对抗策略,并设置 k = 20,\beta = 0.3和\q = 0.1。 在下文中,我们呈现共识协议运行迭代次数的直方图。其中给出了p_0 三种初始比例的情况。 在每种情况下,对手节点的比例选择为 q = 0.1。

在这些参数选择下,共识协议非常快。

我们还发现p_0 = 0.7的情况下收敛是最慢的。 这并不令人惊讶,因为在这种情况下,初始的总比例(在诚实和恶意节点中)是0.63,这位于区间[a,b]中。

但总是达成共识,并最终做出哪些决定呢?

我们首先看一下安全案例的百分比,即所有诚实的节点最终都有相同的意见:

对于p_0 接近区间[a,b]的时候,这看起来可能不太令人信服? 然而,有必要检查没有获得共识的情况。 为了做到这一点,我们调查了执行协议之后诚实节点之间的平均意见。 如果我们将此值舍入到第一个小数,我们将获得以下直方图。

这表明协议(在上述参数选择情况下)对于所有初始意见的选择都不适用。

让我们检查一下参数 k 的调整是否可能会改善这种情况。 这里给出了在p_0 = 0.7,四中不同k值情况下,所需迭代次数的直方图。

我们看到查询数量的增加导致协议的加速。 更好的是,安全性也在增加:

查询次数一致率
200.952
350.989
500.996
1000.999

打破协议

让我们从失败中学习,并对协议增加更大压力,将对手节点的比例增加到 q = 0.3。 我们设置 k = 50。

在这些参数选择下,共识协议仍然在所有三种初始意见的情况下终止,但收敛速度要慢得多。

较慢的收敛不是这里唯一的问题。 事实上,我们还有一个安全问题:

Initial mean opinion p_0Agreement rate
0.50.727
0.70.724
0.90.738

修复失败

增加查询数量是解决上述问题的关键。我们设置 p_0 = 0.7,q = 0.3,\beta = 0.3并考虑对手策略1到3:

增加查询数似乎可以控制30%的对手节点。 但是,查询超过四分之一的节点不是可扩展的方法。 另一个解决方案是调整参数 l。 我们将在帖子末尾更详细地看到这一点。

共识协议的演化

那么在共识协议期间究竟会发生什么? 给定节点意见固定的速度有多快?

在下图中,每一行显示了诚实节点之间平均意见的演变。 其中参数如下: p_0 = 0.7,q = 0.1,k = 50,\beta = 0.3,我们考虑的是第二种对抗策略。

我们看到,在几乎所有情况下,平均意见达到0或1相当快。

下图显示了具有固定意见的诚实节点的百分比; 每条路径再次表示共识协议的实现:

分散随机化的好处

Popov提出的协议和其他协议的一个本质区别在于阈值是随机的,并且这种随机性是去中心化的。 我们研究了这种随机性给对手策略4和5的影响:让我们改变随机阈值\beta。 其他参数 p_0 = 0.7,q = 0.1,k = 20。 我们首先研究第四种对抗策略。

请注意 \beta = 0.5表示m 大于等于 2的轮次中阈值始终为0.5,因此不具有随机性。 一个更大的 \beta 意味着更少的随机性。

这清楚地说明随机性的增加会降低协议的速度,并且非随机设置对这种攻击并不健壮!

Choice of betaAgreement rate
0.10.973
0.30.966
0.50.538

对抗BERSERK

我们现在考虑第五种对抗策略。

让我们来看看协议中会发生什么。 我们看到对手如何设法将观点保持在0.5左右,而越来越多的诚实节点确定他们的意见。 我们研究的参数是:q = 0.1,k = 20,p_0 = 0.7和 \beta = 0.5。

我们比较了攻击策略4和5下协议的安全性。

同样,在第五种攻击策略中,查询数量的增加可以增加协议的安全性。我们所设置的参数为:p_0 = 0.7,q = 0.1,l = 3,和 \beta = 0.3。

Number of queriesAgreement rate
200.886
500.980
1000.994
1500.998

另一种可能性是在保持 k = 50 的情况下,改变确定长度 l

Determination length lAgreement rate
30.980
50.994
101.000

让我们最后看一下固定协议是如何“路径化”:p_0 = 0.7,q = 0.1,l = 10,\beta = 0.3。

随机性的成本?

一切都有它的成本; 额外的随机性也是如此。 在 p_0 = 0.7的情况下,额外的随机性保证了在危急情况下的安全性。 但是,此功能需要权衡。 例如,在初始意见\ p_0 = 0.8的情况下,额外的随机性会降低协议收敛速度并降低其安全性。 然而,至少在这种情况下,附加随机性的优点似乎超过了性能和安全性的微小损失。

Choice of betaAgreement rate
0.10.995
0.31.000
0.51.000

讨论和展望

通过分布式随机生成器引入的附加随机层,可以在没有这种特性时协议会失效的情况下,使得系统达成共识,这似乎是有效的。 一定程度的随机性,例如在\beta的选择编码中,似乎取决于具体情况。

在这些模拟中获得的收敛速度远远好于Popov获得的理论上限。 此外,在非危急情况下,几乎总是以最少的步骤实现共识。 但是,FPC取决于许多不同参数的选择。 在上述研究中,我们只考虑了其中的一些,并且它们对协议结果的影响尚未进行更详细的研究。

原文链接:http://datatreker.com/simulations-of-the-fast-probabilistic-consensus-protocol-fpc

Jimmy Xiong

专栏作者:Jimmy Xiong

个人简介:研究者,布道者,投资人,IEN成员,IOTAChina创办人。

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

发表评论

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