论文标题
打破$ o（\ sqrt n）$ - 位障碍：拜占庭人与每个聚会的polygog位协议
Breaking the $O(\sqrt n)$-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party
论文作者
论文摘要
拜占庭协议（BA）是面对恶意代理商的一项投入部分的$ n $ entary的任务，是一个强大的原始原始性，是广泛的分布式协议的核心。有趣的是，在具有最佳整体沟通的协议中，各方的需求是高度不平衡的：摊销成本为$ \ tilde o（1）$ lits $ lits $ lits，但有些当事方必须发送$ω（n）$位。在最著名的平衡协议中，总体通信是次优的，每一方通信$ \ tilde o（\ sqrt {n}）$。在这项工作中，我们询问不对称是否是优化总通信的固有的。我们在这一行中的贡献如下： 1）我们定义了一个密码原始的，简洁的分布式签名（SRDS），这足以构建$ \ tilde o（1）$平衡BA。我们提供了来自不同密码和公钥基础架构（PKI）假设的SRD的两种构造。 2）基于SRDS的BA遵循从“几乎每个地方”协议到完全协议的提升范式，并在一轮中进行。我们证明，对于每个方发送$ o（n）$消息的协议，PKI设置和加密假设是必需的。 3）我们进一步探讨了一种自然方法达到SRD的自然方法与特定类型的NP完整问题（概括子集和子集产物）的自然方法与平均简洁的非相互作用参数系统（SNARGS）之间的联系。 我们的结果提供了新的方法，以及最大程度地减少BA的每人交流的局限性和障碍。特别是，我们使用$ \ tilde o（1）$平衡的通信构建了前两个BA协议，在设置和加密假设之间提供了权衡，并回答了King和Saia（Disc'09）提出的一个空旷的问题。
Byzantine agreement (BA), the task of $n$ parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of a vast range of distributed protocols. Interestingly, in protocols with the best overall communication, the demands of the parties are highly unbalanced: the amortized cost is $\tilde O(1)$ bits per party, but some parties must send $Ω(n)$ bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating $\tilde O(\sqrt{n})$. In this work, we ask whether asymmetry is inherent for optimizing total communication. Our contributions in this line are as follows: 1) We define a cryptographic primitive, succinctly reconstructed distributed signatures (SRDS), that suffices for constructing $\tilde O(1)$ balanced BA. We provide two constructions of SRDS from different cryptographic and Public-Key Infrastructure (PKI) assumptions. 2) The SRDS-based BA follows a paradigm of boosting from "almost-everywhere" agreement to full agreement, and does so in a single round. We prove that PKI setup and cryptographic assumptions are necessary for such protocols in which every party sends $o(n)$ messages. 3) We further explore connections between a natural approach toward attaining SRDS and average-case succinct non-interactive argument systems (SNARGs) for a particular type of NP-Complete problems (generalizing Subset-Sum and Subset-Product). Our results provide new approaches forward, as well as limitations and barriers, towards minimizing per-party communication of BA. In particular, we construct the first two BA protocols with $\tilde O(1)$ balanced communication, offering a tradeoff between setup and cryptographic assumptions, and answering an open question presented by King and Saia (DISC'09).
