区块链共识分析的简单框架

高产 Jan

共识机制的设计出发点

正如Jan大佬开篇提出的,区块链的共识出于使用场景的不同,和传统的数据库、分布式系统的共识设计和实现上面,有不小的差异。

顺着这个思路,一起回顾现在已知的区块链最初在白皮书提出的使用场景:

  • 比特币:一种点对点的电子现金系统
  • 以太坊:下一代智能合约和去中心化应用平台
  • EOS: 为满足去中心化应用的纵向和横向扩展需求而设计的区块链软件架构
  • Nervos:A Common Knowledge Base for Crypto-Economy
  • 其他:…

从上述的区块链项目中,可以看到,区块链的设计至少要满足下面的要求:

  • 去中心化
  • 价值存储和流转

至此,我们可以明白区块链的共识机制是作为维护去中心化、价值存储和流转的核心引擎而出现的。

共识机制、去中心化、价值

区块链网络里里外外存在各种各样身份的参与者:矿工、用户、开发者、作恶者、外界未知者。

这些参与者的身份或有交叠、或有动态变化、但是,不管是哪种,区块链网络里面内在的发展引力是:壮大的“诚实者”集体。

在区块链网络里面,想要达到“诚实者”集体的壮大,需要通过共识机制进行调节:

  • 矿工:提供友好的,发展合理的奖励机制,吸引矿工给网络注入价值支撑;
  • 开发者:以技术的形式,支起网络的安全防火墙,并有一定的技术优势化身矿工;
  • 用户:通过自有资金,给网络带去活力,构建生态的多样性;
  • 作恶者:增加作恶成本、促使作恶者转变为“诚实者”
  • 其他:…

当面对这些参与者,不同的平衡机制,将会导致不同的共识框架。
例如:

  • 现有Permissionless的PoW区块链项目,主要考虑的是成为矿工的门槛,毕竟矿工直接参与和维护网络整个价值体系,通过引导大家成为或保持具有矿工功能的角色,可以大大提高区块链网络的去中心化程度。
  • 对于追求高性能的PoS类项目,要实现的是在保证价值正确存储和流转下,开发者的便利和用户的友好使用体验。

为了服务价值的存储和流转,区块链的共识机制是在去中心化的基础上面,以网络认可的信任模型,与各种参与者的价值进出和存储进行交互,从而,促使网络的发展和健壮。

综上,探讨区块链网络的共识框架,或者说实现流程,基本会着重于矿工、用户、开发者、作恶者的角度,并主要从Jan大佬提出的下面流程进行分析:
进入方式、出块方式、共识方式、退出方式、一致性、活性、延迟、带宽效率、节点数量

最后,谢谢这些干货,可能探讨的有点混乱啦

6 Likes

很好的话题。首先,我可以多提供一点学术界方面的资料,这些资料我仅仅罗列作为参考,不代表我认同其中的部分或者全部观点(甚至有些内容写的也并不是很清楚)。

[1] Garay, Juan, and Aggelos Kiayias. Sok: A consensus taxonomy in the blockchain era . Cryptology ePrint Archive, Report 2018/754, 2018.
[2] Bano, Shehar, et al. “Consensus in the age of blockchains.” arXiv preprint arXiv:1711.03936 (2017).
[3] MetaAnalysis of Alternative Consensus Protocols

其次,文章中有两处我比较在意。

  1. 在“最小的信任模型”部分中,

这个实际上,前者 Byzantine Broadcast 问题,后者是 Byzantine Agreement 问题,两个问题在文献中都有着形式化的定义并且分别有着不同的安全下限(可以容忍多少拜占庭节点)。

而这个情况,在我的理解中,只存在于 Byzantine Broadcast 问题当中,并且在该问题里,发起节点一般不被包含在共识的主要问题里研究(也就是不被包含在 N \geqslant 3f + 1 当中的 N 里面)。因此原文的叙述中

这一点我认为也是不成立的。在 Byzantine Agreement 问题中,所有共识节点都是要验证每一轮的消息的合法性的。如果说文章想表达的是区块链中,节点需要验证交易是否合法(金额,签名等),那么这样的比较是无效的。因为共识模型实际上是剔除了上层应用的抽象模型,比特币属于分类账,而分类账模型属于共识模型上层的应用。正如文章前面所说,共识模型关注一致性和活性,因此共识模型应当只保证诚实节点之间不会就不同的消息达成一致并且诚实节点总是可以就新的消息达成共识,而不应该考虑任何和消息的内容有关的合法性。

而后面这一段

中论述的 SPV 节点,其功能在于验证某交易在链上的哪个位置,并不参与验证新的区块,但是可以发起新的交易请求。因此如果只考虑 SPV 节点和矿工之间的互动的话,应当将其与 Byzantine Broadcast 问题下的传统共识模型相比较。

  1. 在“一个简单的分析框架”中,

我想知道“链上伪随机”和“VRF随机选择”有什么区别。

最后,对框架做一点小补充。简单比较上述性质有一定的参考性,但是却无法得出准确的结论。不同的假设会对上述性质产生显著的影响。比如就时间模型假设而言,很多协议在同步模型下或者半同步模型下可以保持一致性和活性,但是在异步条件下无法保证活性。因此,要么在同样的假设下比较上述性质,要么将假设也作为一部分放在比较的维度当中。前者看起来更直观也更合理。但实际上,首先很多协议设计的目的之一就是在于这样的假设;其次,哪种时间模型的假设更合理(既不会太强也不会太弱)是依据应用场景的不同而变化的。因此,如果将协议都拉平在同一个假设下,有失公允并且可能也会变得没有意义。在明确应用场景之前,更建议将假设作为评估的一部分(事实上很多密码学的文献都会这样做)。

4 Likes

这里是想到哪儿就写到哪儿了,把交易验证放在“共识框架”的名字下讨论确实不合适。

这里“链上伪随机”指的是利用区块链本身的信息来作为随机性来源,例如用前一个区块的hash.

我考虑过要不要把网络假设包含进来,最后省略掉了,主要是担心加进来会让这个框架变得太复杂,反而会让读者难以比较,因为这里更希望提出一个侧重于区块链的框架,突出在区块链场景中共识最重要的那些特点。我甚至想把一致性和活性删掉,或者合并成一个“偏好一致性还是活性“。

做一个标准表格和一个扩展表格也许是个办法,把更细节一些的东西放到扩展表格里面去。

1 Like

我觉得这个思路很好,加进来确实会让它变得难以理解,时间模型实际上不是个易于理解的概念。扩展表格已经有人做了,标准表格虽然有人做,但是却并没有限定假设。或许我们可以规定一种应用场景,根据这种场景确定我们的各种假设,在这样的假设下我们可以对一致性活性进行比较,甚至还能排个序出来。

另外激励机制这个维度我觉得很好,不知道有没有文章系统地比较过不同区块链的激励机制的均衡以及它对共识安全性的影响(我的上一个回复的第三篇引文提到过,但是分析太简单了)。

2 Likes

就像军迷们喜欢看武器装备的各种参数一样,jan 的这篇文章无疑提供了非常友好的“性能参数”。我也尝试着给这个分析框架做一点添砖加瓦的小事,根据这个框架分析一下 algorand。

algorand 是 Micali 提出的一种结合 VRF 和 BFT 的共识算法

  • 从进入方式上看,参与者持有一定比例的代币就能获得相应概率的参与共识的机会。
  • 从出块选择上看,algorand 是一种 PoS 算法,通过 VRF 算法为每一轮共识随机选择一组共识节点。
  • 从共识方式上看,algorand 在每一轮共识中实际上运行的是 BFT 算法,需要 1 到多轮共识过程完成给定区块的共识。
  • 从退出方式上看,参与者离线或者不再持有任何代币即会失去参与共识的机会。
  • 从一致性和活性上看,algorand 对恶意节点的容忍比例与共识委员会的期望大小有关,委员会期望大小越大,对恶意节点的容忍比例就越高,按照论文的计算,在委员会期望大小为 2000 的时候,能容忍恶意节点持有不超过 20% 的代币。
  • 从延迟上看,algorand 的延迟为中,实际情况甚至可能是高。由于 algorand 实际上是在公网环境运行 BFT 算法,共识节点众多(委员会期望大小甚至设定为 2000,而对应的实际物理节点数量在初期可能并不多,但是随着代币的分散度增加,物理节点数量可能也会非常多),由于对节点在线要求高且公网的网络情况复杂很可能导致区块普遍需要多轮共识过程。
  • 从带宽效率上看,algorand 的带宽效率为中甚至低。因为 algorand 需要额外传输共识过程中必要的投票,而这些投票消息的复杂度与共识物理节点的数量成平方的关系。
  • 从节点数量上看,algorand 的节点数量为中。algorand 虽然在共识委员会的期望大小为 2000, 但是实际上掌握大量代币的物理节点可以同时扮演多个共识节点,以至于实际上真正参与共识的物理节点并不会非常多。而且,由于 BFT 的消息复杂度和物理节点数量成平方的关系,实际上 BFT 能够支持的物理节点不会特别多。
5 Likes

补充两点,一是与比特币相对,Algorand 是侧重一致性的共识算法,如果我们要套用

的话。二是 Algorand 的 BFT 是经过简化了的,是一种二元拜占庭共识,所以为了不造成不了解 Algorand 的读者的直观上的误解,特意补充说明一下它的“一轮”和“PBFT”的“一轮”不一样。

1 Like

今天应用共识分析框架分析一下 EOS

  • 从进入方式上看,参与者需要竞选超级节点,进入超级节点名单才有机会参与共识,其中获得用户投票值最高的 21 个超级节点是区块生产者,其他超级节点作为候选。
  • 从出块选择上看,EOS 采用 DPoS 算法,出块顺序做过多次变更,从最早的轮询到后来提出随机选择,最近为了适应 0.5 秒的出块间隔,采用区块生产者协商的方式确定出块顺序,以最大程度上减少网络延迟。
  • 从共识方式上看,EOS 摒弃了原先的见证人机制,转而采用 BFT 算法,使得区块确认时间从至少 45 秒(3 秒出块)缩短到了大部分情况下 1 秒左右(0.5 秒出块)。
  • 从退出方式上看,区块生产者的投票值跌出前 21 名,将转入候选名单,如果超级节点在 24 小时内均未产生区块,将跌出候选名单。
  • 从一致性和活性上看,EOS 能容忍不超过 33% 的区块生产者作恶。
  • 从延迟上看,EOS 的延迟为低,多数情况下仅需 1 秒即可完成交易的确认,这得益于其相对中心化的设计和超级节点强大的配置。
  • 从带宽效率上看,EOS 的带宽效率为高。EOS 的带宽有一部分用于传输 BFT 的共识消息(如提案和投票),但是一方面 EOS 的区块生产者不多,另一方面这些区块生产者的带宽资源非常丰富,因此共识消息在带宽消耗中的占比非常有限,所以 EOS 的带宽效率还是很高的。
  • 从节点数量上看,EOS 的节点数量是低。EOS 的区块生产者数量固定,只有 21 个。
2 Likes

继续分析 Ouroboros,Ouroboros 是最早有形式化安全证明的 PoS 算法之一。

  • 从进入方式上看,Ouroboros 是 PoS 算法,参与者持有代币即获得了参与共识的机会。
  • 从出块选择上看,在 Ouroboros 里,持有超过一定比例代币的用户组成选举人团,通过多方计算(MPC) 生成一个随机种子,该随机种子作为 FTS 算法的输入,确定下一轮的 N 个出块节点。FTS 算法即 Follow The Satoshi 算法,根据用户持有的代币数量按比例确定性随机选择。
  • 从共识方式上看,Ouroboros 是基于链的概率性 PoS 算法,其分叉选择规则相对复杂。
  • 从退出方式上看,用户不再持有代币即失去了参与共识的机会。
  • 从安全偏好上看,Ouroboros 偏好活性,其可以容忍恶意节点持有不超过 51% 的代币。
  • 从延迟上看,Ouroboros 的延迟为中。Ouroboros 是概率性共识算法,需要多个区块的确认,具体数量取决于设定的安全参数。
  • 从带宽效率上看,Ouroboros 的带宽效率为中。Ouroboros 额外消耗的带宽主要是在选举人团通过 MPC 计算随机数上。
  • 从节点数量上看,Ouroboros 的节点数量为高。任何持有代币的用户都有机会成为共识节点。
2 Likes

有意思的是,我觉得 EOS 的 33% 和 Algorand 的 20% 不一样。相比于 EOS,直觉上我觉得 Algorand 的 20% 更安全一点。更具体地说,Algorand 的 20% 是抵抗 Adaptive adversary 的,EOS 的 33% 我不知道它的 adversary 模型是什么。

完全赞同,评估安全性需要结合进入方式,出块选择,共识方式以及安全假设等进行综合考虑,所以完全不能把这里的数字和安全划上等号。

1 Like

已经整理到表格中去了。我对进入和退出方式有些疑问,印象中参与共识需要先成为Delegator,所以在表格里面留了问号。

我再查询了一遍,没有看到这样的表述,所以不太确定。

如果你看的是 Ouroboros 的论文的话,肯定没有这样的表述的。大部分讲共识机制的论文的 focus 都不在进入退出这里。具体 Cardano 是怎么使用 Ouroboros 的,还需要看他们网站的 Documentation 或者代码。

浏览了一些官方文档,Cardano的随机数应该是由delegators根据PVSS产生,由这个随机数从所有stake holder里面选择合适的出块人出块。

谢谢 @wancencen ~

我去年看的资料说的是不只是 PVSS,Cardano 采用的是 commit-reveal + PVSS 的混合方式。或者它更新了?

Casper 的发展历程是一个冗长且充满戏剧性的故事,今天简单分析下 Vlad 主导的 Casper-CBC 和 Vitalik 主导的 Casper-FFG。

  • 从进入方式上看, CBC 和 FFG 都要求验证者抵押代币。
  • 从出块选择上看,Casper 是覆盖在 PoW/PoS 上的确认层,并不出块。验证者对链上的区块投票,通过共识达成链上区块的确认。
  • 从共识方式上看,因为 Vlad 排斥 BFT 算法,因此设计了 GHOST 的变种 LMD GHOST (Latest message-driven GHOST) 作为 CBC 的共识机制。Vitalik 最初采用的是简化的 BFT 算法,后来也转向了 GhOST 算法,设计了 IMD GHOST (Immediate message-driven GHOST) 作为 FFG 的共识机制。
  • 从退出方式上看,验证者解除抵押就无法参与验证。
  • 从安全偏好上看,Casper 偏好一致性(感觉用一致性和活性来描述安全偏好似乎不是很合适,用概率性或确定性描述也许更好一些)。
  • 从延迟上看,Casper 的延迟更多地取决于底层的 PoW/PoS 的设置,比如是每 50 个块确认一次,还是每 100 个块,以及每个块的平均出块时间。
  • 从带宽效率上看,Casper 的带宽效率为中。Casper 需要为验证者的投票消耗额外的带宽。
  • 从节点数量上看,Casper 的节点数量为中。
1 Like

Ethereum 2.0 Beacon Chain把出块和共识分开,用VDF产生随机数来选择出块人,用Casper保证共识。在通常情况下系统可以同时保证一致性和活性,在共识无法达成的时候只保证活性。因此Casper是偏好一致性的,但是整体上我觉得偏好活性。

Ethereum 2.0 是 RANDAO + VDF 我记得?VDF 单独是无法工作的,必须指定输入,不同的输入其实会影响实际效果。

指定输入是指什么?详细说说?