论文标题
拜占庭在多项式时间内具有近乎最佳的弹性
Byzantine Agreement in Polynomial Time with Near-Optimal Resilience
论文作者
论文摘要
自1980年代初以来，人们就知道，拜占庭在全部信息中达成协议，异步模型也无法确定性地解决即使是一个崩溃的故障[FLP85]，但是它可以用概率1 [BEN83]解决，即使对所有消息的安排和损坏所有消息的对手，也可以损坏所有/3 $ 3 $ 3 $ 3 $ 3 $ 3 $ [BRA] [BRA] [BRA] [BRA] [BRA] [BRA]。 [BEN83，BRA87]的主要缺点是，每当$ f =θ（n）$时，它们以$ 2^{θ（n）} $ rounds终止。 KING和SAIA [KS16，KS18（ARXIV：1812.10169）]开发了一种多项式协议（多项式弹，多项式计算），该协议对$ f <（1.14 \ times 10^{ - 9}）均具有弹性。协议中的新想法是通过分析这些玩家在许多回合中产生的随机变量的偏差来检测可能BAD参与者的联盟。 在这项工作中，我们设计了一个简单的集体投币协议，以便如果任何有缺陷的参与者的联盟不遵循协议，那么最终将通过两个简单的统计测试之一来检测它们。使用此额外的投资协议，我们在多项式数量的巡回赛中解决了拜占庭一致，即使在最高$ f <n/4 $ byzantine故障的情况下也是如此。这接近$ f <n/3 $上限，最大故障数[BT85，FLM86，LSP82]。
It has been known since the early 1980s that Byzantine Agreement in the full information, asynchronous model is impossible to solve deterministically against even one crash fault [FLP85], but that it can be solved with probability 1 [Ben83], even against an adversary that controls the scheduling of all messages and corrupts up to $f<n/3$ players [Bra87]. The main downside of [Ben83, Bra87] is that they terminate in $2^{Θ(n)}$ rounds in expectation whenever $f=Θ(n)$. King and Saia [KS16, KS18(arXiv:1812.10169)] developed a polynomial protocol (polynomial rounds, polynomial computation) that is resilient to $f < (1.14\times 10^{-9})n$ Byzantine faults. The new idea in their protocol is to detect -- and blacklist -- coalitions of likely-bad players by analyzing the deviations of random variables generated by those players over many rounds. In this work we design a simple collective coin-flipping protocol such that if any coalition of faulty players repeatedly does not follow protocol, then they will eventually be detected by one of two simple statistical tests. Using this coin-flipping protocol, we solve Byzantine Agreement in a polynomial number of rounds, even in the presence of up to $f<n/4$ Byzantine faults. This comes close to the $f<n/3$ upper bound on the maximum number of faults [BT85,FLM86,LSP82].
