Probabilistic Byzantine Fault Tolerance (Extended Version)

共识是构建可靠和容错的分布式服务的基本构建块。许多为部分同步系统设计的拜占庭容错共识协议在处理对手时采用悲观的方法，即使在对手可能制造的最坏情况下也能以确定性的方式确保安全。按照这种方法通常会导致消息复杂度的增加（例如PBFT）或通信步骤数量的增加（例如HotStuff）。然而，在实践中，对手的能力并不像这些协议所假设的那样强大。此外，只需以高概率确保安全性和活性特性即可满足要求。为了适应更现实和乐观的对手，并提高BFT共识的可扩展性，我们提出了ProBFT（概率拜占庭容错）。ProBFT是一种基于领导者的概率共识协议，具有消息复杂度为$O(n\sqrt{n})$和容忍许可部分同步系统中的拜占庭错误的最优通信步骤数量。它建立在众所周知的基元之上，如概率拜占庭法定人数和可验证随机函数。ProBFT即使在领导者错误的情况下，只要大多数副本正确，并且仅使用PBFT中使用的一小部分消息（例如$20\%$），就可以以高概率保证安全性和活性。我们提供了ProBFT协议及其分析的详细描述。

提高分布式系统中拜占庭容错共识协议的可扩展性和适应性，解决了现有协议在处理敌对行为时过于悲观和复杂的问题。

提出了一种基于概率的拜占庭容错共识协议ProBFT，采用领导者模式，利用概率拜占庭仲裁和可验证随机函数等基础算法，实现了在有限的消息数和通信步数下保证安全性和活性的共识。

ProBFT协议具有较高的可扩展性和适应性，能够应对更加现实和乐观的敌对行为，并且在处理故障领导者时仍能保证安全性和活性；实验结果表明，ProBFT协议在消息数和通信步数方面都优于现有协议，例如PBFT，仅使用了PBFT消息数的20%。

在拜占庭容错共识协议领域，与ProBFT相关的研究包括：Practical Byzantine Fault Tolerance (PBFT)，HotStuff，Tendermint等。