Synopsis of Our Solution. Following the time-tested notion of reducing randomized Byzantine Agreement to the problem of flipping a global bounded-bias coin, we concentrate our attention to designing such a protocol. As pointed out earlier, standard techniques (due to Xxxxx [21] and Dwork et al. [11]) show how to get a BA protocol with a constant-round overhead, given a common-coin protocol. The “immediately obvious” approach is to use the collective coin-flipping protocols of Feige [12] or Xxxxxxx and Xxxxxxxxx [22]. However, we cannot use these protocols as such, because they work under the assumption that there exists a broadcast channel, which we cannot assume. log n Nevertheless, our protocol borrows ideas from the collective coin-flipping protocol of Feige [12]. Feige’s protocol for collective coin-flipping works as follows: All the players are alive in the beginning of the protocol. In the first round, the players throw a ball each at random into one of O( n ) bins. The players who threw their balls into the lightest bin survive for the next round. The protocol is then recursively invoked on the O(log n) players in the lightest bin. The crucial idea is that, assuming that the good players throw their balls randomly, their balls are almost uniformly distributed among the bins. Thus, the lightest bin contains approximately the right fraction of good players. Therefore, this protocol can be viewed as a way of electing a small subset (a “committee”) of the n players, that contains a “large enough” fraction of good players. After log∗ n recursive invocations of this process, a leader is elected. We let the leader flip a coin, and broadcast it. Note that each step of this protocol assumes that the players broadcast their choices of the bins to all the players. Since we do not have a broadcast channel, we have to implement it, and that requires Byzantine Agreement. It looks like we are back to the same problem. The trick to avoid this circularity is to use a certain weak version of broadcast (called graded broadcast) to implement the first stage of Feige’s protocol. We then proceed to show that this reduces BA among n players to BA among O(log n) players. Thus, assuming that we can implement graded broadcast in O(1) rounds, we get an O(log n) round BA protocol. Notations. Letters such as P, S denote protocols. We usually denote subprotocols of a protocol P by subscripts, such as Pi, and subprotocols of Pi by superscripts, such as Pj . Players are denoted by the letter P , possibly w...
