论文标题
通过统计欺诈检测，拜占庭与最佳弹性达成协议
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
论文作者
论文摘要
自1980年代中期以来，众所周知，拜占庭协议可以通过概率1的概率解决，即使是针对无所不知的计算无限的对手，该对手可以适应性地\ emph {roffere}，最高$ f <n/3 $ parties。此外，问题不溶于$ f \ geq n/3 $损坏。但是，布拉查（Bracha）的1984年协议以$ f <n/3 $的弹性实现了指数预期的延迟$ 2^{θ（n）} $，该限制在此模型中从未改善，$ f = \ lfloor（n-1）/3 \ rfloor $腐败。 在本文中，我们证明，在异步，完整信息模型中，拜占庭协议可以用概率1来解决，而概率1与可能损坏$ f <n/3 $ party的自适应对手，而仅产生高概率的多项式延迟。我们的协议遵循国王，赛亚和黄，佩蒂和朱的早期多项式延迟协议，这些协议分别为$ f \ f \ n/10^9 $和$ f <n/4 $。 弹性$ f =（n-1）/3 $非常困难，因为这是拜占庭和诚实球员的影响力大致相同的点。我们解决的核心技术问题是设计一种集体额外的额外挑战协议，该协议最终使我们以明确的结果翻转硬币。一开始，拜占庭球员的影响力太强大而无法克服，他们可以随意确定硬币的行为。我们保证，仅在多项式执行硬币的执行之后，（a）（a）拜占庭玩家无法修复硬币的行为（从而结束游戏），或者（b）我们可以``黑名单''玩家，以至于拜占庭人的黑名单率至少与良好的球员的黑名单相比至少与拜访者一样大。黑名单标准基于对欺诈检测的简单统计检验。
Since the mid-1980s it has been known that Byzantine Agreement can be solved with probability 1 asynchronously, even against an omniscient, computationally unbounded adversary that can adaptively \emph{corrupt} up to $f<n/3$ parties. Moreover, the problem is insoluble with $f\geq n/3$ corruptions. However, Bracha's 1984 protocol achieved $f<n/3$ resilience at the cost of exponential expected latency $2^{Θ(n)}$, a bound that has never been improved in this model with $f=\lfloor (n-1)/3 \rfloor$ corruptions. In this paper we prove that Byzantine Agreement in the asynchronous, full information model can be solved with probability 1 against an adaptive adversary that can corrupt $f<n/3$ parties, while incurring only polynomial latency with high probability. Our protocol follows earlier polynomial latency protocols of King and Saia and Huang, Pettie, and Zhu, which had suboptimal resilience, namely $f \approx n/10^9$ and $f<n/4$, respectively. Resilience $f=(n-1)/3$ is uniquely difficult as this is the point at which the influence of the Byzantine and honest players are of roughly equal strength. The core technical problem we solve is to design a collective coin-flipping protocol that eventually lets us flip a coin with an unambiguous outcome. In the beginning the influence of the Byzantine players is too powerful to overcome and they can essentially fix the coin's behavior at will. We guarantee that after just a polynomial number of executions of the coin-flipping protocol, either (a) the Byzantine players fail to fix the behavior of the coin (thereby ending the game) or (b) we can ``blacklist'' players such that the blacklisting rate for Byzantine players is at least as large as the blacklisting rate for good players. The blacklisting criterion is based on a simple statistical test of fraud detection.
