论文标题
身份验证的拜占庭协议的最佳沟通复杂性
Optimal Communication Complexity of Authenticated Byzantine Agreement
论文作者
论文摘要
拜占庭协议（BA）是分布式计算中最根本的问题之一，其通信复杂性是重要的效率指标。众所周知，由于Dolev和Reischuk的下限，在最坏情况下，BA是必要的。 Berman等人的$ f <n/3 $，已证明该下限对未经身份验证的设置很紧。但是，对于经过验证的设置，$ n/3 \ le f <n/2 $仍然存在相当大的差距。 本文为缩小这一差距提供了两个结果。这两个方案都具有二次通信的复杂性，并且在弹性和假设方面具有不同的权衡。第一个协议实现了$ f <n/2 $的最佳弹性，但需要一个值得信赖的阈值签名设置。第二个协议在标准PKI模型中实现了接近最佳的弹性$ f \ le（1/2 - \ varepsilon）n $。
Byzantine Agreement (BA) is one of the most fundamental problems in distributed computing, and its communication complexity is an important efficiency metric. It is well known that quadratic communication is necessary for BA in the worst case due to a lower bound by Dolev and Reischuk. This lower bound has been shown to be tight for the unauthenticated setting with $f < n/3$ by Berman et al. but a considerable gap remains for the authenticated setting with $n/3 \le f < n/2$. This paper provides two results towards closing this gap. Both protocols have a quadratic communication complexity and have different trade-offs in resilience and assumptions. The first protocol achieves the optimal resilience of $f < n/2$ but requires a trusted setup for threshold signature. The second protocol achieves near optimal resilience $f \le (1/2 - \varepsilon)n$ in the standard PKI model.
