Error-free Multi-valued Broadcast and Byzantine Agreement with Optimal Communication Complexity
Error-free Multi-valued Broadcast and Byzantine Agreement with Optimal Communication Complexity
复制标题
具有最佳通信复杂性的无差错多值广播和拜占庭协议
DOI：
10.1007/978-3-642-25873-2_4
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Patra
中科院分区：
文献类型：
--
作者：
A. Patra
在本文中，我们首次提出了具有最佳通信复杂度和容错性的无错误、异步广播（称为A-cast）和拜占庭协议（称为ABA）协议。我们的协议是多值的，这意味着它们处理l位输入，并且对于n≥3t+1个参与方的集合来说，如果l足够大，通信复杂度为${\mathcal O}(n\ell)$位，其中最多t可以被拜占庭式损坏。此前，Patra和Rangan （Latincrypt'10， ICITS'11）报道了多值、通信优化的A-cast和ABA协议仅在概率上正确。
遵循之前关于多值协议的所有工作，我们也遵循基于约简的协议方法，这意味着我们的协议是根据现有的小消息（可能是单位）的A-cast和ABA协议设计的。与Patra和Rangan的缩减相比，我们的缩减调用了更少或相同数量的单比特协议实例。此外，与Patra和Rangan （ICITS'11）的${\mathcal O}(n)$相比，我们的缩减在恒定的预期时间内运行。而且，我们的减排比他们的减排更简单、更优雅。
通过从异步设置中调整我们的技术，我们提出了新的无错误的、通信最优的基于约简的广播（BC）和拜占庭协议（BA）协议，这些协议在同步设置中是恒定的轮询，并且只调用$\mathcal O(n^2)$单比特协议实例。在此之前，Fitzi和Hirt （PODC'06）已经实现了通信最优性，他们提出了概率正确的多值BC和BA协议，使用恒定轮询和${\mathcal O}(n(n+\kappa))$ （κ是错误参数）调用单比特协议。最近，Liang和Vaidya （PODC'11）实现了相同的无误差概率。然而，它们的缩减需要整数复杂度和实例数，它们分别是消息大小的函数${\mathcal O}(\sqrt{\ell} + n^2)$和${\mathcal O}(n^2\sqrt{\ell} + n^4)$，其中l=Ω（n6）。
In this paper we present first ever error-free, asynchronous broadcast (called as A-cast) and Byzantine Agreement (called as ABA) protocols with optimal communication complexity and fault tolerance. Our protocols are multi-valued, meaning that they deal with l bit input and achieve communication complexity of ${\mathcal O}(n\ell)$ bits for large enough l for a set of n≥3t+1 parties in which at most t can be Byzantine corrupted. Previously, Patra and Rangan (Latincrypt'10, ICITS'11) reported multi-valued, communication optimal A-cast and ABA protocols that are only probabilistically correct.
Following all the previous works on multi-valued protocols, we too follow reduction-based approach for our protocols, meaning that our protocols are designed given existing A-cast and ABA protocols for small message (possibly for single bit). Our reductions invoke less or equal number of instances of protocols for single bit in comparison to the reductions of Patra and Rangan. Furthermore, our reductions run in constant expected time, in contrast to ${\mathcal O}(n)$ of Patra and Rangan (ICITS'11). Also our reductions are much simpler and more elegant than their reductions.
By adapting our techniques from asynchronous settings, we present new error-free, communication optimal reduction-based protocols for broadcast (BC) and Byzantine Agreement (BA) in synchronous settings that are constant-round and call for only $\mathcal O(n^2)$ instances of protocols for single bit. Prior to this, communication optimality has been achieved by Fitzi and Hirt (PODC'06) who proposed probabilistically correct multi-valued BC and BA protocols with constant-round and ${\mathcal O}(n(n+\kappa))$ (κ is the error parameter) invocations to the single bit protocols. Recently, Liang and Vaidya (PODC'11) achieved the same without error probability. However, their reduction calls for round complexity and number of instances that are function of the message size, ${\mathcal O}(\sqrt{\ell} + n^2)$ and ${\mathcal O}(n^2\sqrt{\ell} + n^4)$ , respectively where l=Ω(n6).