HotStuff和Tendermint,SBFT有什么区别?

  HotStuff和Tendermint,SBFT有什么区别?在这篇文章中,我将尝试比较我最喜欢的四种拜占庭式容错(BFT)状态机复制(SMR)协议:

  HotStuff。提供了线性和响应性的新BFT协议。最近的LibraBFT基于HotStuff。有关更多信息,请参见后面的文章。

  PBFT。BFTSMR的金标准。强烈建议您观看2001年的BarbaraLiskov的视频。这是PBFT项目页面。

  嫩薄荷。一种现代的BFT算法,在节点之间也使用对等八卦协议。这是github仓库。

  SBFT。一个基于PBFT的BFT系统,具有更好的可伸缩性和最佳情况下的延迟。这是一个实现SBFT协议的github存储库。

  这篇文章从分布式计算理论的角度在协议级别进行了比较。特别是,这不是系统或软件的比较。它是比较基本措施的基础,人们应该通过这些基本措施来研究这些不同的协议。可以在此表中总结很多比较结果,该表实质上表明,没有一种协议会主导所有其他协议。

  念上的区别:轮换领导者与稳定领导者

  如上所述,所有这些协议都具有通过视图更改协议替换领导者的能力。{PBFT,SBFT}与{Tendermint,HotStuff}之间的一个关键概念差异是{PBFT,SBFT}基于稳定的领导者范式,其中仅当检测到问题时才更改领导者,因此领导者可能会停留在许多命令上/块。{Tendermint和HotStuff}基于旋转的领导者范式。一次尝试提交命令/块后,旋转领导者。在此范式中,领导者轮换(视图更改)是系统正常操作的一部分。

  请注意,{PBFT,SBFT}可以很容易地修改以在旋转的领导者范式中运行,而类似的{Tendermint,HotStuff}可以很容易地修改以在稳定的领导者范式中运行。

  在许多情况下,这是一个折衷。一方面,保持稳定的领导者意味着更少的开销和更好的性能,这要归功于领导者诚实可信时的稳定性。另一方面,稳定的恶意领导者可能导致无法检测到的恶意行为。例如,这样一种难以检测到的恶意行为就是以有偏见的方式按块设置命令的内部顺序。不断旋转引线可提供更强的公平性保证。

  正常情况下领导提交阶段的技术差异

  PBFT使用所有创建O(n2)通常情况下的领导者提交阶段的通信复杂性。长期以来一直观察到,该阶段可以转换为线性通信模式,从而产生O(n)通信复杂性。SBFT和HotStuff都使用这种方法来获得领导者提交阶段的线性成本。Tendermint使用八卦所有机制,因此O(nlogn)消息和O(n2)话。由于这对于协议而言并非必需,因此在上表中,我考虑了Tendermint的一个变体,该变体执行O(n)正常情况下的领导者提交阶段的沟通也是如此。

  变更视图阶段的技术差异

  PBFT中的视图更改机制并未针对关键路径进行优化。从算法上讲,至少需要O(n2)要发送的单词(某些不使用公共密钥签名的PBFT变体使用更多)。SBFT也有类似的O(n2)单词视图变化的复杂性。

  在Tendermint和HotStuff中,领导者轮换(视图更改)是关键路径的一部分。领导者轮换基本上每3轮完成一次,因此要花更多的精力来优化此部分。从算法上讲,Tendermint的主要创新是仅需O(n)的视图改变协议消息(和单词)。HotStuff具有类似的O(n)单词视图变化的复杂性。

  有人可能会问,Tendermint的视角变化改进是否使其严格优于PBFT。答案是,Tendermint并非在所有方面都主导PBFT。在响应性和延迟方面进行了微妙的权衡(不足为奇)。

  延迟和响应能力方面的技术差异

  延迟的衡量标准是在诚实的领导者和GST之后进行交易所需的往返次数。确切地说,我们将从交易到达领导者到任何参与者(领导者/副本/客户)第一次获悉交易已完成的时间进行度量。请注意,从客户端的角度来看,可能有额外的延迟,并且/或者可能是由于学习和检查点要求所致。这些额外的延迟垂直于共识协议。

  PBFT的往返延迟为2,而Tendermint也是如此。但是,Tendermint视图更改无响应,而PBFT视图更改无响应。如果协议以网络的速度进步而无需等待与部分同步模型相关联的预定义超时,则它是响应式的。PBFT和SBFT都响应,而Tendermint没有响应。

  特别是,可以证明,即使在GST之后,如果Tendermint协议在其视图更改阶段没有等待时间(超时),那么恶意攻击者也可能导致其失去全部生命,并且没有任何进展。超时后,Tendermint不会出现活动问题(在GST之后),但这意味着它会导致在关键路径上发生超时。因此,即使网络延迟大大小于固定超时,它也无法更快地进行。

  重要的是要注意,在许多应用程序中,不响应可能是一个合理的设计选择。响应的重要性取决于使用情况,吞吐量的重要性以及稳定期间网络延迟的可变性。

  然而,有人可能会问:我们能否获得一种也具有响应性的线性视点变化?

  这正是HotStuff进入图片的地方。HotStuff扩展了Tendermint的视图更改方法,并提供了复杂度线性且响应迅速的协议!那么,HotStuff是否在所有维度上都严格控制Tendermint?不,这是一个权衡。HotStuff提交路径导致PBFT和Tendermint的延迟为3次往返,而不是2次往返。

  很自然地问,2次往返和3次往返的延迟之间的区别重要吗?同样,答案是延迟的重要性取决于用例。许多应用程序可能不关心延迟是否是平均的,例如10次往返,而其他应用程序可能希望尽可能减少延迟。

  最小化延迟

  实际上,如果您确实希望最大程度地减少延迟,那么在最佳情况下甚至可能只有一轮延迟!这正是SBFT实现的目标。这并不像看起来那么容易。

  SBFT获得最佳情况的一轮延迟。那是最优的吗?您现在知道答案了,这是一个权衡。尽管SBFT具有最佳的最佳情况延迟,但它具有的视图更改协议具有O(n2)最坏情况下的复杂性。

  吞吐量:流水线和并发

  PBFT实现与ChainedHotStuff变体之间还有另一个重要区别,这与提高吞吐量的不同方法有关。

  在PBFT中,领导者维护着一个开放时隙的窗口,并被允许在其活动窗口中同时提交所有开放时隙的工作。从概念上讲,这就像TCP,其中发送方不必等待数据包i的ACK发送消息之前我+1。修改窗口大小的实验已通过经验验证,该窗口可以通过允许领导者同时协调广告位承诺的多个操作来显着提高吞吐量。SBFT使用类似的机制。

  基本的HotStuff协议按顺序工作以提交每个块。因此,吞吐量限制为每3轮1个区块。通过使用流水线技术,ChainedHotStuff协议将其显着提高到了每轮摊销1块。基本上,发送的每个消息都是某个广告位i的第一轮消息,时隙i−1的第二轮消息以及时隙i−2的第三轮消息。因此,虽然仍按顺序工作,但ChainedHotStuff提供了每轮1块的摊销吞吐量。链接的想法来自减少消息类型的数量。在Casper中,提出了一种类似的方法来减少消息类型。减少消息的类型和链接也可以使协议更简单。这允许更简单,更干净的软件实现。从协议基础上看,CasperFFG本质上是ChainedTendermint。

  从理论上讲,并发方法还可以获得流水线方法获得的每轮最佳摊销1块。但是,流水线方法还减少了发送的位数(通过将多个消息聚合为一个),这是并发方法当前不做的事情。

  请注意,流水线和并发是提高BFTSMR吞吐量的技术。它们与任何特定的BFT协议都不紧密相关。例如,可以提出一种使用流水线的ChainedPBFT(或SBFT)变体,或者可以切换到稳定的领导者模式的WindowedHotStuff变体,该模式允许同时在未完成的插槽窗口上取得进展。

  在标准的BFTSMR体系结构中,提交块与执行块可以分开。通常,执行必须是顺序执行的,并且通常在优化提交吞吐量(通过管道或并发)之后,顺序执行成为吞吐量的性能瓶颈。如果执行确实是瓶颈,那么这就是需要优化的地方。有关更多信息,请参见后面的文章。