AN OPTIMAL PROBABILISTIC PROTOCOL FOR SYNCHRONOUS BYZANTINE AGREEMENT

Broadcasting guarantees the recipient of a message that everyone else has received the same message. This guarantee no longer exists in a se tting in which all communication is person-to-person and some of the p eople involved are untrustworthy: though he may claim to send the same message to everyone, an untrustworthy sender may send different messa ges 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 g rew with the size of the network) or the help of some external trusted party. In this paper, for the standard communication model of synchro nous networks in which each pair of processors is connected by a priva te communication line, we exhibit a protocol that, in probabilistic po lynomial time and without relying on any external trusted party, reach es Byzantine agreement in an expected constant number of rounds and in the worst natural fault model. In fact, our protocol successfully tol erates that up to 1/3 of the processors in the network may deviate fro m their prescribed instructions in an arbitrary way, cooperate with ea ch other, and perform arbitrarily long computations. Our protocol effe ctively demonstrates the power of randomization and zero-knowledge com putation against errors. Indeed, it proves that ''privacy'' (a fundame ntal ingredient of one of our primitives), even when is not a desired goal in itself (as for the Byzantine agreement problem), can be a cruc ial tool for achieving correctness. Our protocol also introduces three new primitives-graded broadcast, graded verifiable secret sharing, an d oblivious common coin-that are of independent interest, and may be e ffectively used in more practical protocols than ours.