Provably Fair Slots With Factoradics

March 13, 2013

We just launched Slots on bitZino, and like all our games, it is provably fair.

Earlier on this blog, we discussed in technical depth just how we go about shuffling a deck in a provably fair manner. This technique doesn't work out of the box with slots though.

When we launched Roulette and Craps, we worked around this issue by simply using a deck of cards anyway: each card in the deck corresponded to a distinct outcome of the game, and we just used the top card as the result for each round. This hack doesn't work for Slots though, because there are thousands of possible outcomes for each game.

One possible solution is to use multiple decks of cards, one for each slots reel. This isn't ideal though, because it doesn't work the same for various games of slots - if the game happens to have 5 reels, it needs more decks being shuffled. It also breaks our standard hand verifier, and potentially requires a longer client_seed depending on what game is being played.

Another possible solution is to use a longer deck, and have each card represent a unique slots outcome (similar to the Craps and Roulette solutions). However, once you start dealing with 5-reel slots, this deck would need to be hundreds of thousands (if not millions) of cards long. This would mean we would need to transfer megabytes of data between our servers and the client for every spin! Clearly that wouldn't fly.

Ideally, we'd simply use a short, standard deck of cards, and convert that shuffled deck into a unique Slots outcome.

Enter Factoradics

Fortunately, there is already an established mathematical concept that is used for converting permutations (e.g., shuffled decks of cards) into numbers. That concept is called Factorial Number Systems, or factoradics.

An example

For example, if we had a 3 card deck, then the following table would represent how we would convert a shuffle of this deck into a base-10 number.

Deck Decimal
0,1,2 0
0,2,1 1
1,0,2 2
1,2,0 3
2,0,1 4
2,1,0 5

Converting a deck into a number

In order to programatically create the above table, we must first convert the deck into a factoradic. We represent our factoradic as an array.

function getFactoradic(deck_numbers) {
  var value, count, factoradic = [], inserted_values = [];
  for(var i = 0; i < deck_numbers.length; i++) {
    value = deck_numbers[i];
    count = 0;
    for(var j = 0; j < inserted_values.length; j++) {
      if (inserted_values[j] < value) {
        count++;
      }
    }
    factoradic.push(value - count);
    inserted_values.push(value);
  }
  return factoradic;
}

Once we have the factoradic, we can compute the decimal value that corresponds to this factoradic:

function getDecimalFromFactoradic(factoradic, max_number) {
  var total = 0, size = factoradic.length;
  for(var i = size - 1; i > 0; i--) {
    total = (total + factoradic[size - 1 - i]) * i;
    if (total > max_number) {
      total = total % max_number;
    }
  }
  return total;
}

Note that the max_value is simply used to do a modulus operation as we go. This prevents the number from getting too large, which would cause it to start losing precision in javascript.

Choosing a large enough deck size

The number of possible permutations for a deck with n unique cards is n!.

If your slots game has R reels, each with I icons on the reel, then there are IR possible outcomes for that game. A more concrete example: if your slots game has 3 reels, each with 32 icons, then there are 323 == 32768 possible outcomes.

Unfortunately, a deck of cards can't be converted directly into a number between 1 and 32768, because there is no n, such that n! will equal 32768. The good news though, is that when you use a large enough n, the number n! produces is divisible by almost any "small" number, like 32768.

So, we chose specifically to use a 32 card deck. This produces 32! possible outcomes, which equals:

263130836933693530167218012160000000

This number is divisible by all numbers for slots games we would consider making, including 3 reels with 32 icons each (32768 possible outcomes), all the way up to 5 reels with 128 icons each (34359738368 possible outcomes).

Converting a number to a Slots outcome

The final step is converting the number computed above into a slots outcome. We do this by simply performing a series of modulus and division operations, as such:

function getSlotsNumbers(number, num_reels, num_icons_per_reel) {
  var slots_numbers = [];
  for(var i = 0; i < num_reels; i++) {
    slots_numbers.push(
        parseInt(number / Math.pow(num_icons_per_reel, i), 10) % num_icons_per_reel);
  }
  return slots_numbers;
}

Finally, we use the slots_numbers to represent the middle icon in each reel. If the number is at the edge (e.g., 0 or 31), then the icon directly above or beneath it simply wraps around.

Try it out yourself!

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

- Libertaad

Keep bitcoind Running With God-rb

December 21, 2012

If you're running a bitcoin related service, chances are you rely on bitcoind to handle sending and receiving bitcoins. Therefore, keeping bitcoind up and running is vitally important to keeping your service fully operational.

This is the position we're in. If our backend bitcoind process dies, we can't process our players' withdrawals and deposits. It is critical to the success of bitZino that we keep bitcoind up and running at all times.

In the beginning

When we first started bitZino, we just ran bitcoind directly. This typically worked well, but once every few weeks or so we'd find that bitcoind was utilizing 100% CPU, and was unresponsive to JSON-RPC commands. Even though the process hadn't died, it was effectively useless until it was restarted.

Then we found god

God is a process monitoring framework, written in ruby. With god you can automatically monitor processes: keep them running, and also restart them if they begin using too much CPU or memory. It is very easy to configure and get up and running.

To start using god yourself, you must be running bitcoind on a posix-compatible system. To install god make sure you have ruby installed, then just run:

[sudo] gem install god

(I recommend using sudo to install god at the system level)

Our god config

Once you have god installed, you have to write a basic configuration script to monitor bitcoind. This is the script we use:

God.watch do |w|
  w.name = 'bitcoind'
  w.start = '/usr/bin/bitcoind'
  w.grace = 30.seconds

  w.pid_file = "<home dir>/.bitcoin/bitcoind.pid"
  w.behavior(:clean_pid_file)

  w.log = '<log dir>/bitcoind_god.log'

  w.start_if do |start|
    start.condition(:process_running) do |c|
      c.interval = 10.seconds
      c.running = false
    end
  end

  w.restart_if do |restart|
    restart.condition(:cpu_usage) do |c|
      c.interval = 10.seconds
      c.above = 80.percent
      c.times = 5
    end
  end
end

This configuration script will result in god starting bitcoind if it's not already running. Then god will monitor bitcoind's CPU utilization, and if it is using above 80% CPU for 50 seconds in a row (at 10 second intervals), it will restart bitcoind.

There are many other configuration options available, all in a very simple syntax. Check out the God documentation page for more information.

Now, instead of running bitcoind directly, we run god:

god -c /path/to/bitcoind.god

Since we began leveraging god to monitor our bitcoind process, we haven't had any issues with bitcoind becoming unresponsive. I highly recomend it to anyone that is operating a service which relies on bitcoind uptime!

- Libertaad

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