Provably fair Heads or Tails: attacks on the seed parts

Let's recall our provably faire Heads or Tails protocol:

• Assume an agreed upon seedable random generator and bet amount.
• The casino selects a random seed part \(s_C\), and sends its signed hash to Alice, along with a proof that twice the bet amount has been put in escrow. This is the commitment.
• Alice concatenates a random seed part \(s_A\) to the commitment, signs the result, and sends it back to the casino, along with her bet money.
• The casino seeds the random generator with \(s_A \oplus s_C\), tosses the coin and either pays Alice or keeps her bet money.
• The casino reveals \(s_C\) to prove the fairness of the toss.

Let us spell out here how an weakness on \(s_C\) can let Alice cheat the Casino: If the distribution of \(s_C\) is not uniform, and Alice knows where the most probable values are, she can look for values of \(s_A\) that will skew the toss towards a greater-that-half chance of winning.

A weakness in the one-wayness of the hash function can allow Alice to deduce things about \(s_C\) as well, facilitating the same attack.

Here is some Python code for a brute-force search of an \(s_A\) (alice_seed, in the code) that will allow Alice to cheat the casino:

def win(seed):
    """Return True if the given seed would let alice win her bet, False if the
    casino wins"""
    pass  # The protocol is agnostic to the actual implementation

best_seed = None
best_winning_prob = None
alice_seed = -1
while True:
    alice_seed += 1
    winning_prob = np.mean([win(alice_seed * casino_seed)
                            for casino_seed in most_probable_casino_seeds()])
    if best_winning_prob is None or winning_prob > best_winning_prob:
        print(f"{alice_seed=}, {winning_prob=}")
        best_winning_prob = winning_prob
        best_seed=alice_seed

This code assumes that there is a handful of values that are more probable that others, and that Alice can enumerate them, or at least get a representative sample.

More subtle forms of non uniformity in the Casino's choice of seed will require finer work from Alice, but the basic principle is there.

The reverse is true, and if Alice's choice of \(s_A\) is not truly random, then the casino can skew its choice of \(s_C\) in a direction that would make it win more often than chance.

Note that this attack is harder to pull off from the casino's side, as it must, chronologically, commit to its \(s_C\) before Alice chose her \(s_A\).

Let's work through an example:

• The casino notices, over multiple games, that Alice always choses her lucky number 42 as \(s_A\).
• The casino choses an \(s_C\) that, when combined with \(s_A=42\), yields a victory for the casino.
• Bob notices this, and in turn, knowing that the casino's \(s_C\) is not random, runs the above program to play against the casino's \(s_C\).
• The casino can't protect itself from Bob, as it had to commit to \(s_C\) when setting up the game, before either Alice or Bob can play.