# Another Fair BitCoin Toss

Using Blum’s Protocol

Previously, we implemented a fair coin toss on Bitcoin using XOR. We introduce an alternative way of implementing it using Blum’s original coin tossing protocol¹.

It consists of the following steps:

- Alice chooses prime numbers
and*p*. He tells Bob*q*. Alice chooses*N = p * q*and*p*to be extremely large so that Bob cannot feasibly find them from*q*.*N* - Bob chooses
between 0 and*x*. He calculates*N*. He tells Alice*b = x² mod N*. This step is similar to*b**calling*the outcome before a coin toss; you pick an outcome and commit to it.² - Alice calculates the four square roots of
modulo*b*. These are*N*and*x, y, -x*. He chooses one of the pairs*-y*or*{x,-x}*, and tells it to Bob. This step corresponds to the physical flipping of the coin.*{y,-y}* - If Alice chooses
, Bob wins, and he proves it easily by telling Alice*{x,-x}***x**, which he would not have been able to find unless he chose it in step 2, since he does not knowand*p*.*q* - If Alice chooses
, then she wins. Bob cannot find*{y,-y}***y**, so he cannot trick Alice by telling her**y**.

[1] Coin Flipping by Telephone: A Protocol for Solving Impossible Problems. Blum (CRYPTO 1981).

[2] ** x** and

**N**have to be coprime to ensure 4 square roots.