[LK83]

I got lost on the line "If the final answer is odd, the flip is TAILS." For example: Alice flips 1 for tails. Barb/Charlie/Danika flip 0. Why is the answer tails when most of the people flipped 0 for heads? Why use XOR instead of just taking the most common answer?

[malgorithms]

Perhaps an even simpler analogy is a light switch. Each person decides randomly either to flip the light switch or leave it where it is. This is basically what random XOR'ing is.

If you're one of 10 people doing this to the light switch, then as long as you choose randomly, it doesn't matter what the other 9 people do. It has a 50% chance of ending up on and a 50% chance of ending up off. Even if the other 9 people are cheating together.

Of course this has the problem that whoever goes last wins, which is why the commitment ceremony is necessary.

[laszlokorte]

So you only have to trust one person to play fair. If you used most common vote, then if 10 people play, 6 could conspire to always achieve tails.

But when using XOR even if 9 people conspire they can not know if the 10th votes 1 or 0.

[rtkwe]

Think of it this way. If everyone is cheating and fixes their answers to be tails one fair coin flip will still randomly determine the outcome because their fair flip will swap between heads and tails for the whole group.