Overview of the Protocol. − To simplify the description of the coin-flipping problem, in Section 2.1 we originally stated the adversary chooses σ(t) = v∗, and has the goal to convince one player to believe the output of Coin-Flip is σ(t). This is too conservative, and in fact makes the coin-flipping problem needlessly difficult. Consider the sizes of the sets Akeep and Aflip. There are two relevant cases to consider: Case |Akeep| ∈ [0, f]. When Akeep /= ∅, σ(t) = −v∗ is defined, and it would be bad for the adversary if everyone agreed the output of Coin-Flip were v∗, i.e., sgn(Σ(p)) = v∗ for all p ∈ [n]. In fact, it would be equally bad for the adversary if sgn(Σ(p)) = −v∗ for all p. Since Aflip ≥ n − f, the next iteration of Bracha-Agreement would end in agreement since now a supermajority of n − f ≥ (n + f + 1)/2 holds 9When sgn(ΣG(t)) = −σ(t), the adversary is forced to set σ(t)ΣB (t) ≥ −σ(t)ΣG(t), increasing the aggregate σ-correlation of bad players and increasing the aggregate negative good-bad correlation. When sgn(ΣG(t)) = σ(t), the adversary can choose to reverse either of these trends and exacerbate the other, i.e., reduce good-bad negative correlations but increase bad σ-correlations, or reduce bad σ-correlations but increase good-bad negative correlations. 10One player p will be allowed to set vp = v∗ in Line 3, and p will execute Line 4 slowly, either validating its own message among the first n − f or not, at the discretion of the scheduler. In this way the scheduler decides if Akeep = {p} or ∅. − | | ≤ the value v∗. To summarize, when Akeep f, it is critical for the adversary to create disagreement on the outcome of the global coin flip. ∈ − | | ≥ Case Akeep f + 1. If this is the case, then some kind of “finger on the scale” strategy should force the outcome of the coin flip to be v∗. Any player that validates the state of n f players must necessarily validate the state of some p Akeep, and hence learn the value of v∗. If any player that knows v∗ writes only v∗ to its entries in the blackboard, this will surely be the outcome of the global coin flip.
