15

We want to write a card game in Ethereum. What are effective and secure ways of shuffling a deck of cards in a contract, and dealing them to players? It needs to be done in a way so that no one can determine each other's cards and what the shuffled deck is, by examining the open source contract code and shuffling transactions which are all on the public Ethereum blockchain.

If this isn't possible in a contract, what approaches are possible?

  • 4
    Please see this question on how to create a random number ethereum.stackexchange.com/questions/191/… – hcvst Jan 22 '16 at 11:32
  • 3
    I think this is significantly different enough to warrant a separate question. Shuffling cards is much more difficult than simple RNG. See mental poker – Tjaden Hess Jan 24 '16 at 4:16
  • The comment pointing you to the Wikipedia article regarding Mental Poker really does answer your question. I was going to provide a brief overview how we are shuffling, but to be honest, it is exactly what is described in that article - and my description was less clearly written. – jimkberry Jan 26 '16 at 4:48
  • @jimkberry, It would still be helpful to have a good answer to this question, even if it is just a summary of wikipedia. Maybe add in some things you've learned from experience, or some solidity code. – Tjaden Hess Jan 29 '16 at 21:14
  • yes, I'm hoping for what @TjadenHess suggests – eth Jan 29 '16 at 21:28
9

Shuffling a deck


Commutative encryption:

Alice and Bob want to shuffle a deck of cards, such that neither knows what the other's hand contains, but the hands are disjoint (i.e. only one may have a particular card).

Protocol:

Alice and Bob decide on an encryption protocol with the following features

  1. EK(X) is X encrypted with key K
  2. DK[ EK(X) ] = X for all K and X
  3. EK[ EJ(X) ] = EJ[ EK(X) ]
    • i.e. E(X) is commutative
  4. Given X and EK(X) it is computationally impossible to derive K
  5. Given X and Y, J and K such that EJ(X) = EK(Y) cannot be found
    • i.e. E(x) is collision-resistant

Now that Alice and Bob have an encryption scheme:

  1. Bob takes the fifty-two cards ("2C","3C",...,"AS") and encrypts each with key B
  2. Bob shuffles the encrypted cards in random order, and sends the deck to Alice
    • Alice can't see the cards, since she doesn't know B
  3. Alice selects five cards, and sends them back to Bob
    • This is Bob's hand. Bob can see these cards, since he knows B
  4. Alice sends five more cards back to Bob, but first she encrypts them using key A
    • Each card is now encrypted as EA[ EB(X) ], which is equivalent to EB[ EA(X) ] by property #4.
  5. Bob decrypts these cards and sends them back
    • Bob cannot see the cards, since he does not know A. Alice, however can see them and these are her hand.

More cards can be drawn using a similar procedure. After the game, Alice and Bob reveal A and B so that they can verify that neither player cheated.

Encryption schemes with the properties listed do in fact exist, including a method similar to RSA. See my Source for more details.


Use in contracts:

Contracts can be used to manage the messaging between players, and to distribute rewards. The contract does not need to execute any logic unless the players do not agree on the results. In the case of a disagreement, the challenger must put up enough Ether to cover the gas costs of verifying the game. Then the other player must execute the call to verify the game result. Gas is refunded to the truthful player, and the round is canceled or forfeit by the cheater.

9

Since Ethereum contracts can have their source code verified then this should be as simple as making use of an RNG to pick cards randomly from a deck. Anyone who wishes to verify that the deck is adequately shuffled can verify the contract source code.

Since generation of good randomness is addressed elsewhere this answer assumes that the card shuffling contract has access to good random numbers.

Using on-demand randomness

Producing a well shuffled deck can be done by randomly selecting cards from an unshuffled deck and building a new deck until the unshuffled deck has been depleted.

contract Deck {
   uint8[52] deck;

   function getRandomNumber() returns (uint) {
       ...;
   }

   function shuffle() {
      uint8[52] memory unshuffled;

      for (uint8 i=0; i < 52; i++) {
          unshuffled[i] = i;
      }

      uint cardIndex;

      for (i=0; i < 52; i++) {
          cardIndex = getRandomNumber() % (52 - i);
          deck[i] = unshuffled[cardIndex];
          unshuffled[cardIndex] = unshuffled[52 - i - 1]
      }
   }
}

This contract represents each of the 52 cards as an integer between 0-51 inclusive. A call to the shuffle function will populate the deck storage variable with a 52 card deck with random ordering.

Responding to random input.

This assumes that randomness can be safely requested which is not necessarily feasible. If this is not the case and randomness must instead be sent into the contract then the following general concept should work equally well.

contract Deck {
   uint8[52] deck;

   function shuffle(bytes randomBytes) {
      if (randomBytes.length < 52) throw;

      uint8[52] memory unshuffled;

      for (uint8 i=0; i < 52; i++) {
          unshuffled[i] = i;
      }

      uint8 cardIndex;

      for (i=0; i < 52; i++) {
          cardIndex = uint8(randomBytes[i]) % (52 - i);
          deck[i] = unshuffled[cardIndex];
          unshuffled[cardIndex] = unshuffled[52 - i - 1];
      }
   }
}

This version of the contract requires at least 52 bytes of randomness to be included with the call to shuffle.

  • 1
    This answers the question as stated, but I think the implication was that the cards would be secretly shuffled and dealt, such that the players can't see the other players' hands. I think the question is poorly worded. – Tjaden Hess Jan 29 '16 at 21:11
  • 1
    Thanks for feedback @TjadenHess. Hope I clarified the question better with italics. – eth Jan 29 '16 at 21:46
  • @eth : I don't think your current italics clarify anything, it's not clear whether people have to be able to secretively draw cards without the other players knowing. – Christian Jan 30 '16 at 12:04
  • "needs to be done in a way so that no one can determine [each other's cards and] what the shuffled deck is" ok I added the part in [] (it does clarify but not sure if it's really needed) – eth Jan 30 '16 at 12:16
  • In the light of the new requirements I'm inclined to change my answer to "This cannot be done on Ethereum since it is impossible for contracts to keep secrets.". This sort of app is sufficiently complex that I'm doubtful that it's a useful question since the solution is likely to require coordination through other networks like whisper. Anyone else want to weigh in on this? – Piper Merriam Jan 30 '16 at 22:34
1

If you want cards to be non repeating, then it's actually a pretty hard problem. A simpler problem is if we don't care if the same card is dealt multiple times (for example you have an Ace of spades and I have an Ace of spades).

Let's consider a simple game with 2 players. Each player will be dealt 1 card and it's ok, that both players may get the same card. It can be thought of as the two cards are dealt from two different decks. To implement this, we can think of each card as an index between 0 and 51 (inclusive). Here's how to fairly generate player 1's card, so that only he knows what it is.

  1. Player 2 generates a random number in range 0..51 called p2_offset. Next he generates a random string called p2_secret (for example "pcjshjfgn"). Next, he submits sha3(p2_offset, p2_secret) to the blockchain.
  2. Player 1 generates a random number in range 0..51 called p1_offset and a random string p1_secret and submits sha3(p1_offset, p1_secret) to the blockchain.
  3. Player 2 reveals p2_offset and p2_secret to the Ethereum contract, which verifies that sha3 of those values matches what he submitted earlier.
  4. Player 1 can now figure out what his card is by doing (p2_offset + p1_offset) mod 52. Notice that player 2 does not know what the cards is because p1_offset is unknown to him.
  5. Player 1 can reveal his card by submitting p1_offset and p1_secret to the contract. Again, the contract will verify that sha3 of those values matches what player 1 submitted before.

The same approach can be used for generating player 2's card.

Making sure that each card appears only once I think is pretty challenging. We could say that once

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.