论文标题
不是偶然的：亚条件异步拜占庭协议WHP
Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP
论文作者
论文摘要
King和Saia是第一个打破同步系统中拜占庭同步的二次词复杂性与适应性对手的一致性，而Algorand则以近乎最佳的弹性打破了这一界限（首先是同步模型，然后是最终的同步性）。然而，异步次级拜占庭协议的问题仍然开放。据我们所知，我们是第一个以肯定的方式回答这个问题的人。解决方案的关键组成部分是基于VRF的共享硬币算法。第二个基本要素是基于VRF的委员会抽样，我们首次将其正式化并在异步模型中使用。我们的算法与延迟的自适应对手有关，该算法无法执行事后的去除，但可以完全控制拜占庭的过程和有关早期交流的完整信息。使用委员会的抽样和我们的共享硬币，我们以很高的可能性解决了拜占庭协议，其单词复杂性为$ \ widetilde {o}（n）$和$ o（1）$（1）$预期的时间，打破了$ O（n^2）$ BIT障碍，用于异常拜占庭协议。
King and Saia were the first to break the quadratic word complexity bound for Byzantine Agreement in synchronous systems against an adaptive adversary, and Algorand broke this bound with near-optimal resilience (first in the synchronous model and then with eventual-synchrony). Yet the question of asynchronous sub-quadratic Byzantine Agreement remained open. To the best of our knowledge, we are the first to answer this question in the affirmative. A key component of our solution is a shared coin algorithm based on a VRF. A second essential ingredient is VRF-based committee sampling, which we formalize and utilize in the asynchronous model for the first time. Our algorithms work against a delayed-adaptive adversary, which cannot perform after-the-fact removals but has full control of Byzantine processes and full information about communication in earlier rounds. Using committee sampling and our shared coin, we solve Byzantine Agreement with high probability, with a word complexity of $\widetilde{O}(n)$ and $O(1)$ expected time, breaking the $O(n^2)$ bit barrier for asynchronous Byzantine Agreement.
