Bill P. Godfrey et al


Monday, June 26, 2006

Stacking the deck

So I was reading this website, it had an article talking about how an on-line casino is publishing the mathematical "hash" of the virtual deck of cards before the game but without revealing everyone's state of play.

An anonymous commenter wrote...
"The integrity of the deck doesn't matter worth *anything*. The hash insures (or is supposed to) that they haven't changed the cards middeck. There is NO protection against stacking the deck."

Now this got me thinking, and I think I've worked out a way to have a dealer which everyone could be sure is fair. I stress that I think I've worked out a way. If I've made an error, (or dare I say, you think it's perfect) please leave a comment and tell me.

A deck of 52 cards has 52! (or approx 8×1067) possible shuffles. This is comfortably within the realm of 256 bits. The dealer's shuffler code will need 256 bits to perform its task.
  1. Dealer selects 256 bits, his contribution to the shuffle function, k0.
  2. Dealer selects another 256 bits for the secret salt value (salt).
  3. Dealer calculates the dealer's hash. SHA256(k0 + salt) and transmits it to all players.
  4. Each player selects their own contribution to the shuffle function, kn.
  5. Each player calculates and publishes the result of SHA256(kn).
  6. Once everyone has the player's hashes from step 5, each players publishes their kn value from step 4.
  7. Each player and dealer may audit the other player's hash by repeating the SHA256 calculation.
  8. Dealer calculates SHA256(k0 + k1 ... kn + salt) and shuffles the virtual deck with the result. (The shuffle function should be published in advance and be deterministic only on the seed value.)
  9. Dealer and players play with shuffled deck until the winner is decided.
  10. Once the game is over, dealer publishes k0 and salt, allowing everyone to audit the dealer's actions.
Note that player's kn values can be any length, within reason, depending on how difficult that player wants to make it for others to cheat. If a player trusts all other parties, that player could just use no bits at all as thier kn value.

Here's my own attempt at attacking this algorithm. Stop me if I've missed anything.
  • Neither dealer nor players can "stack the deck" by choosing a favourable kn, because all parties contribute into the final hash that seeds the shuffler.
  • The dealer can't choose a favourable k0 or salt after the each player's kn has been revealed, as the dealer will already have revealed the dealer's hash which the player's can check afterwards.
  • The last player in line can't choose favourable kn material with knowledge of all the other k inputs - even if he colludes with the dealer - as the other players don't have to reveal their actual kn value until all the players have revealed their hash.
  • Players can't change thier chosen kn value after step 5, as they will have already revealed the SHA256 of their kn value and the other players can check it.
  • Players can't collude against the dealer or other players, as salt will not be revealed until the game is over.
  • The dealer can't use different shuffled deck, as all of the dealer's actions may be repeated once the game is over and all hidden values are revelead.
Any comments please?

Its possible I'm talking rubbish. Its also possible I'm the millionth person to think of this.

UPDATE: Looking over it again, I don't think the salt value adds anything and I can't remember why I added it in the first place. Without the salt, the algorithm is the same for dealers and players, except the dealer's reveal of k0 comes after the game has completed.

7 Comments:

  • You got the salt - which enhances the flavour, but I'm annoyed that you forgot the pepper

    Condimentally correct,
    Coventry.

    By Anonymous Anonymous, At 1:08 PM, June 27, 2006  

  • Last time I was in Coventry, they didn't have any mustard.

    By Blogger Bill P. Godfrey, At 4:57 PM, June 27, 2006  

  • They had, and always have had, plenty of mustard - they just had trouble cutting it

    [the blooming runny stuff kept slipping through their scissors and making a nasty stain on the counter... what a shambles!]

    Codnimentally correct,
    Coventry

    By Anonymous Anonymous, At 9:13 PM, June 27, 2006  

  • Darn mustard. Always cutting and running.

    -- Bill P. Codfrey.

    By Blogger Bill P. Godfrey, At 11:20 PM, June 27, 2006  

  • Interesting site! I read down to your "Conversation with an Athiest".

    Have you ever tho't that something CONTROLS you, that makes you SAY, FEEL, and ACT the way you do? Is Destiny CONTROLLED by CODES?

    You have hidden DNA and RNA CODES in you, plus other CODES that switch things ON and OFF in your body, ALL to CONTROL you!

    WHO PUT THE HIDDEN CODES INTO YOU?

    Likewise, YOU CAN READ CODES RIGHT OUT OF YOUR OWN BIBLE, that CONTROL your Destiny!

    See the "Chosen"Code and "Color" Code; VISIT: http://quadcode.blogspot.com ! Save or Print it to study.

    HAVE A BRILLIANT DAY!

    By Blogger Rudy Wellsand, At 7:57 PM, June 28, 2006  

  • Can't the dealer collude with a player (e.g., a planted player) by secretely revealing k0 (and the salt, if present) to that player?

    By Anonymous Ed Davies, At 11:55 AM, August 03, 2006  

  • Ed Davies...

    Yes, the dealer could reveal k0 to a placed player, but I don't think they could organise deck-stacking that way, as all players and dealer have to reveal the hash of their own contribution to the shuffle function beforehand.

    You are correct in that this protocol could not stop a corrupt dealer revealing to a colluding player what everyone has been dealt. Even if it stops stacking the deck.

    Is there a way to play card games over the internet without trusting anyone at all? I don't know, but I'll think about it. Its a nice intellectual challenge.

    By Blogger Bill P. Godfrey, At 10:35 PM, August 06, 2006  

Post a Comment



<< Home