Provably Fair Shuffling Through Cryptography

June 30, 2012

Allow me pose a question to you:

How can I shuffle a deck of cards, and prove to you that it was a fair shuffle?

To make it more complicated, assume you can't watch me shuffle. And, even more complicated, assume we have opposing interests in the outcome of this deck: it will be used to play a game in which we're playing against each other.

This is a question we posed to ourselves when designing bitZino. Our goal is to create a product that our users have ultimate trust in. As gamblers ourselves, we know this is incredibly important. Every time you suffer a bad beat or have a string of bad luck there's a lingering question in the back of your head: "Is this casino really fair?"

So, how can we prove to you that our shuffles are fair? How can we earn the ultimate trust of our users? We started our hunt for these answers by looking at the world around us:

In the physical world

It's common for one player to shuffle, and then offer to let another player cut the deck. This approach significantly helps curb the potential for cheating, because the shuffling is effectively done by two parties.

In the digital world

How can a server let a client cut the deck? It can't show the client the cards, otherwise it would be trivial for the client to cheat. And, if it doesn't show the client the cards, how can the client know that the server actually cut the deck as requested?

The answer: Hashing.

Cryptographic hash functions, such as the popular SHA256 algorithm, provide a means to create a fingerprint of a shuffled deck. Since the SHA256 hashing algorithm is one-way, I can let you look at the hash before the game starts, and know that there's no way you can use that hash to figure out what the shuffle of the deck actually is.

Cutting a deck in the digital world

To simulate cutting a deck the server shuffles the deck, computes a one-way hash of it, and then shows the client the hash before asking them to cut it. In this manner, the client can provably verify that the server actually cut the deck as asked.

Let's do an example. For this example we'll use a short 10-card deck. Each card will be represented as a single character between 0 and 9.

The server runs this code:

initial_shuffle = shuffle("0123456789")
=> "4830769125"
initial_shuffle_hash = SHA256(initial_shuffle)
=> "de2d8c0cd8b041612ab54dfde1f6cd362e5f93e697b47544357e4f65a9e9b521"

It then shows initial_shuffle_hash to the client, and asks for a random number between 0 and 9. Let's assume the client gives 4 as their random number.

// Show initial_shuffle_hash to client
cut_point = get_cut_point_from_client()
=> 4
final_shuffle =
    initial_shuffle.substring(cut_point) +
    initial_shuffle.substring(0, cut_point)
=> "7691254830"

The server then proceeds to deal for whatever game is being played.

After the game is over, the server shows the value of initial_shuffle to the client. The client can now confirm that the initial_shuffle, when hashed, matches the value they saw before the game. The client can also confirm that the cards they saw during the game matched the shuffle of "7691254830" - thereby confirming that the server actually cut the deck as requested.

This method forms the basis for the approach that bitZino takes when creating a Provably Fair shuffle. However, it gets more complicated:

Cutting the deck isn't enough

If a server has complete control of the deck, it's feasible that it could stack the deck such that a majority of possible cuts are in the server's favor. In order to demonstrate this, let's consider a game of high card, where the client is dealt the first card and the server is dealt the second card. Assume the deck is stacked as such:

initial_shuffle = "0123456789"

In this case, 9 out of 10 possible cuts will yield a win for the server:

cut(initial_shuffle, 0)
  => "0123456789"
deal()
  => client_hand = 0
  => server_hand = 1

cut(initial_shuffle, 1)
  => "1234567890"
deal()
  => client_hand = 1
  => server_hand = 2

cut(initial_shuffle, 2)
  => "2345678901"
deal()
  => client_hand = 2
  => server_hand = 3

...

cut(initial_shuffle, 9)
  => 9012345678
deal()
  => client_hand = 9
  => server_hand = 0

Only cut(9) results in a win for the client.

So, even if we used the above system to provably cut the deck - a corrupt casino could still cheat their users.

In order to remedy this, let's remember - we're not bound by simple deck manipulation operations in the digital world. We can apply any algorithm we want to the deck, as long as both the client and the server can verify the algorithm was applied correctly.

Let's just reshuffle the deck!

If we can apply any algorithm to the deck, let's shuffle it with a pseudorandom number generator! Let's reshuffle the deck using the Fisher-yates shuffle algorithm, with the random numbers generated from the Mersenne Twister algorithm.

The Mersenne Twister algorithm requires a seed to start its sequence. We can gather this seed from the client in the same way we would have gathered the cut_point.

So, now our server code looks like:

initial_shuffle = shuffle(<deck>)
initial_shuffle_hash = SHA256(initial_shuffle)
client_seed = get_seed_from_client()
rng = MersenneTwister19937(client_seed)
final_shuffle = FisherYatesShuffle(initial_shuffle, rng)

Adding just a little extra security

Just in case the Mersenne Twister algorithm has any unknown vulnerabilities, it's better to stay on the safe side, and not let the client directly provide the seed. Instead, we compute a seed by combining a server_seed (which is provided in hashed form to the client before the deal - in the same way as the initial_shuffle is) and a client_seed.

We compute the final seed by appending the server_seed to the client_seed, hashing the result, and applying a modulo, so that the seed is between 0 and 232.

In code form:

seed = SHA256(client_seed + server_seed) % 2 ^ 32

Quick Aside: Calculating a modulus of very large numbers in javascript

Our javascript hand verifier re-implements this entire algorithm in javascript. However, javascript represents all numbers as double-precision floating-point, which means it doesn't handle large numbers with enough precision to correctly do arithmetic to a SHA256 decimal. In order to get around this restriction, and still do a Modulo( 232 ) operation you can keep the SHA256 hash in hexadecimal string form, and just convert the last 8 characters to decimal, as such: var seedString = CryptoJS.SHA256(client_seed + server_seed).toString(); var seed = parseInt(seedString.substring(seedString.length - 8), 16);

Why the initial shuffle is necessary

Since the seed for the Mersenne Twister is generated from a combination of the server and the client, why even have an initial_shuffle? Why not just run a fresh deck through the Mersenne Twister once and be done with it?

The problem is that the MersenneTwister19937 algorithm only allows for 232 possible seeds. Whereas a single deck of 52 cards has 52! =~ 8 x 1067 =~ 2225 possible combinations. This means we'd only be able to arrive at a tiny tiny fraction of the astronomically large set of possible 52-card decks (the fraction gets even tinier when we're dealing with 416-card decks for blackjack).

In order to remedy this, the server should shuffle the deck first, using a random seed that has enough bits to represent the full deck.

The second round of shuffling only serves to ensure that neither the server nor client could possibly know the final deck before the game starts.

Putting it all together

The final pseudo-code for shuffling a deck of cards in a Provably Fair manner:

initial_shuffle = shuffle(<deck>)
server_seed = <random string>

hash_secret = SHA256(server_seed + initial_shuffle)
// Tell client the hash_secret

client_seed = get_seed_from_client()

seed = SHA256(client_seed + server_seed) % 2^32
rng = MersenneTwister19937(seed)
final_shuffle = FisherYatesShuffle(initial_shuffle, rng)

deal(final_shuffle)
// Tell client the initial_shuffle and the server_seed, so they can verify

Try it out for yourself!

This method is live in production on bitZino, for both real bitcoin and play money blackjack tables. No registration is required for play money. We also implemented a hand verifier in javascript, which implements the entire above algorithm in 100 lines of clean, well-commented, javascript.

- Libertaad