【Author】
Abraham, Ittai; Chan, T. -H. Hubert; Dolev, Danny; Nayak, Kartik; Pass, Rafael; Ren, Ling; Shi, Elaine
【Source】DISTRIBUTED COMPUTING
【Abstract】As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquadratic BA under an adaptive adversary. Intriguingly, they all make a common relaxation about the adaptivity of the attacker, that is, if an honest node sends a message and then gets corrupted in some round, the adversary cannot erase the message that was already sent-henceforth we say that such an adversary cannot perform "after-the-fact removal". By contrast, many (super-)quadratic BA protocols in the literature can tolerate after-the-fact removal. In this paper, we first prove that disallowing after-the-fact removal is necessary for achieving subquadratic-communication BA. Next, we show new subquadratic binary BA constructions (of course, assuming no after-the-fact removal) that achieve near-optimal resilience and expected constant rounds under standard cryptographic assumptions and a public-key infrastructure (PKI) in both synchronous and partially synchronous settings. In comparison, all known subquadratic protocols make additional strong assumptions such as random oracles or the ability of honest nodes to erase secrets from memory, and even with these strong assumptions, no prior work can achieve the above properties. Lastly, we show that some setup assumption is necessary for achieving subquadratic multicast-based BA.
【Keywords】Byzantine agreement; Communication complexity; Subquadratic; Lower bounds
【摘要】随着拜占庭协议 (BA) 协议在大规模去中心化加密货币中得到应用，一个越来越重要的问题是设计具有改进通信复杂性的 BA 协议。一些现有的工作已经展示了如何在自适应对手下实现次二次 BA。有趣的是，他们都对攻击者的适应性做出了共同的放松，即如果一个诚实的节点发送了一条消息，然后在某一轮中被破坏，那么攻击者就无法删除已经发送的消息——因此我们说这样一个对手无法执行“事后删除”。相比之下，文献中的许多（超）二次 BA 协议可以容忍事后删除。在本文中，我们首先证明不允许事后删除对于实现次二次通信 BA 是必要的。接下来，我们展示了新的次二次二进制 BA 结构（当然，假设没有事后删除），在标准密码假设和同步和部分公钥基础设施 (PKI) 下实现近乎最佳的弹性和预期的恒定轮次同步设置。相比之下，所有已知的二次协议都做出了额外的强假设，例如随机预言或诚实节点从内存中擦除秘密的能力，即使有这些强假设，之前的工作也无法实现上述特性。最后，我们展示了一些设置假设对于实现基于次二次组播的 BA 是必要的。
【文献类型】Article; Early Access
评论