What are effective and secure ways of shuffling a deck of cards in a contract?

Question

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?

Answer 1

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. E_K(X) is X encrypted with key K
2. D_K[ E_K(X) ] = X for all K and X
3. E_K[ E_J(X) ] = E_J[ E_K(X) ]
   • i.e. E(X) is commutative
4. Given X and E_K(X) it is computationally impossible to derive K
5. Given X and Y, J and K such that E_J(X) = E_K(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 E_A[ E_B(X) ], which is equivalent to E_B[ E_A(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.

Answer 2

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.

Answer 3

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