[ivoikwee] Verifiable randomness

Casinos have many games that rely on randomness.  It's surprising that they haven't deployed technologies that allow players to verify that the randomness is actually random: players might enjoy having proof that the house isn't cheating them (at least, not cheating by sampling from a probability distribution different from what the player is expecting).  We propose a cryptographic scheme to do this: the house proves to the player that the house would have had to do an exorbitant amount of work to choose a random seed that favors the house.

House secretly chooses a nonce NH and announces Hash(NH), the cryptographic hash of NH.  It is in the house's best interest to choose NH so that it is different every time and hard to guess by the players, e.g., 256 bits of true randomness.

Players then each publicly announce their own nonce strings in two stages.  First, each player announces Hash(NP) of their nonce string NP.  The strings NP should be different every time and hard for an adversary to guess, e.g, 256 bits of true randomness.

In the second stage, all players then publicly announce their NP.  Everyone can verify that the hashes match what was announced in stage 1.  We do player nonce announcement in two stages to thwart the house planting a confederate among the players.  If the players were to announce their nonces directly, the confederate, announcing last (somehow), also having access to the house's secret NH, could choose a NP that cancels out the other players' nonces and manipulates the pseudo random number generator.  Players' nonces must have a lot of entropy to prevent a house confederate from inverting hashes via brute force.  Hash function needs to be collision resistant so that a house confederate among the players cannot construct two nonces with the same hash, then strategically reveal one of them in stage 2.

Still need to think carefully whether the house bribing some players might be a problem.  In general, collusion between players in multiplayer games is tricky.

Instead of 256 bits of true randomness, it might be possible to substitute less randomness and a computationally expensive hashing function like Argon2i.

House secretly combines NH and all the players' NPs in a specified deterministic way to seed a specified cryptographically secure pseudo random number generator.  The nonce-combining operation needs to use a cryptographic hash so that neither the house nor the players can manipulate or predict the PRNG by carefully selecting their nonces.

Then, play the game, sampling in a specified way from the PRNG when randomness is needed.

After the game, house reveals NH.  Players can verify that its hash matches the Hash(NH) announced earlier.  Now that they know NH and all the previously publicly announced player NPs, each player can recreate and verify all random sampling that occurred during the game.

For a game like poker, this means players can, after a hand, determine what everyone's cards were, so learn who was bluffing.

All this is easy to do for online gaming.  Physical casinos would have to stop using classic physical randomizing devices like cards, dice, and roulette wheels.  Those classic randomizing devices have served to convince players that the house is not generating skewed randomness; this proposal represents improved technology to that end.  (Slot machines are already controlled by computers; it's basically online gaming.)  Perhaps the classic devices can be kept as tools to help players generate their nonces, like adding entropy to /dev/random.  (Previously, a speed cube might be a good compact entropy generating device.)  However, they are not ideal because the classic devices are designed to generate their randomness publicly; in contrast, a player must keep secret his or her random player nonce during stage 1.

If the house's announced NH does not hash to the previously announced hash, or if the samples from the PRNG do not match what the seed should have produced, then the player has the option to invalidate the preceding play.  Presumably the player will only exercise the option if the player lost.  If there are many players, then any player can exercise the option.  However, if the house plants a confederate among the players, they might be able to conspire to invalidate games in which the house, or players colluding with the house, lose.  Such behavior might be obvious, and the house regularly failing to behave correctly will contribute to a bad reputation.  However, this general problem still needs more attention.  Maybe the house pays all players the maximum payout if the house behaves incorrectly.

Possible methods for nonce generation and transmission: mobile phone app, QR code.

Perhaps this kind of multi-party initialization of a random number generator could be done for drawing lottery numbers, nowadays done with transparent ball machines that serve to try to convince players that the balls are being picked uniformly randomly.  The two-stage procedure described above for players submitting nonces requires more work by the players, more than just buying a lottery ticket.