An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
复制标题
同步拜占庭协议的最优概率协议
DOI：
10.1137/s0097539790187084
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
S. Micali
中科院分区：
文献类型：
--
作者：
P. Feldman;S. Micali
广播保证了消息的接收者，其他人都收到了相同的消息。这种保证在所有通信都是个人对个人的情况下不再存在，并且其中一些人是不值得信任的：尽管他可能声称向每个人发送相同的消息，但不值得信任的发送者可能向不同的人发送不同的消息。在这种情况下，拜占庭式的协议提供了广播的“最佳选择”。然而，到目前为止，达成拜占庭式的协议需要许多轮的沟通（即，消息必须被来回发送多次，这随着网络的规模而增长）或者某些外部可信方的帮助。
在本文中，对于标准的通信模型的同步网络中，每对处理器是由一个私人的通信线路连接，我们展示了一个协议，在概率多项式时间，而不依赖于任何外部的可信方，达到拜占庭协议在预期的常数轮数和最坏的自然故障模型。事实上，我们的协议成功地容忍，多达1/3的处理器在网络中可以偏离其规定的指令以任意的方式，相互合作，并执行任意长的计算。
我们的协议有效地证明了随机化和零知识计算对错误的能力。事实上，它证明了“隐私”（我们的原语之一的基本成分），即使本身不是一个理想的目标（如拜占庭协议问题），也可以是实现正确性的关键工具。
我们的协议还引入了三个新的原语-分级广播，分级可验证的秘密共享，和不经意的共同硬币-是独立的利益，并可能有效地用于更实际的协议比我们。
Broadcasting guarantees the recipient of a message that everyone else has received the same message. This guarantee no longer exists in a setting in which all communication is person-to-person and some of the people involved are untrustworthy: though he may claim to send the same message to everyone, an untrustworthy sender may send different messages to different people. In such a setting, Byzantine agreement offers the "best alternative" to broadcasting. Thus far, however, reaching Byzantine agreement has required either many rounds of communication (i.e., messages had to be sent back and forth a number of times that grew with the size of the network) or the help of some external trusted party.
In this paper, for the standard communication model of synchronous networks in which each pair of processors is connected by a private communication line, we exhibit a protocol that, in probabilistic polynomial time and without relying on any external trusted party, reaches Byzantine agreement in an expected constant number of rounds and in the worst natural fault model. In fact, our protocol successfully tolerates that up to 1/3 of the processors in the network may deviate from their prescribed instructions in an arbitrary way, cooperate with each other, and perform arbitrarily long computations.
Our protocol effectively demonstrates the power of randomization and zero-knowledge computation against errors. Indeed, it proves that "privacy" (a fundamental ingredient of one of our primitives), even when is not a desired goal in itself (as for the Byzantine agreement problem), can be a crucial tool for achieving correctness.
Our protocol also introduces three new primitives---graded broadcast, graded verifiable secret sharing, and oblivious common coin---that are of independent interest, and may be effectively used in more practical protocols than ours.