[Development - Tutorials] How to generate a provably-fair hash chain in Python

Repository

https://github.com/algo-coder/provably-fair
This contribution applies to all commits in the repository.

Introduction (What will you learn ?)

^{Source : Gambling911}

The code submitted here allows anyone to generate a provably-fair hash chain, a necessary first step in the development of a provably-fair gambling game, such as Bustabit, EthCrash, and others... Here on Steemit we have @fairlotto who's running a provably-fair lotto.

For this code to be totally understandable, it is required to explain some fundamental concepts about the provably-fair system and cryptography.

So what will you learn ? What questions are we going to answer ?

1. What is a provably-fair gambling game ?
2. How is cryptography useful for putting such a system in place ?
3. How to create a provably-fair hash chain in Python ?
4. How to use this hash chain to generate game results ?

Part 1 : What is provably-fair ?

The principle of provably-fair is to eliminate the defiance of the gamblers towards the operator (the casino or house).

The only way for the casino to prove to players he isn't manipulating the outcome of games in real-time is to predetermine the results of the games, and give the players the possibility to verify that the outcome hasn’t been modified or altered.

To do that, a solution has been proposed by Dooglus on Bitcointalk : Solution for a provably-fair algorithm by Dooglus

Steps to a provably-fair algorithm

1 -> The first step towards a provably-fair system is to generate a hash chain.
2 -> The second step is to pick a client seed.
3 -> The last step is to hash the server seed with the client seed to obtain the game hash (in reverse order through the hash chain).

^{Sorry, I'm no graphist.}

The chronological order is really important to ensure the fairness of the game.
The hash chain must be generated first and its last element must be publicized (preventing any alterations from now on). At the same time, the client seed that will be used must be announced but unknown to both parties at that time. It is also in this publicity (meaning official publication) that the result calculating formula is revealed.

This way, any player, by hashing the current game's server seed must find the previous game's server seed. Hashing these server seeds with the client seed, and applying the result formula, he can verify at any moment that, since the beginning of the game, the operator used his hash chain, and calculated correctly each game result.

Doing that in that order, the operator proves to the player he didn't generate a large number of hash chains and picked the most favorable to him.

Part 2 : SHA256 or how to ensure security for both the players and the house

^{Source : ProvablyFairPlay}

Presentation

The SHA (Secure Hash Algorithm) allows to verify the integrity of data. By hashing a file, an output (hash) is generated. By comparing it to future hashes of the same file, you could see if the file has been altered (thus generating a different hash).
To ensure the utility of those hash algorithms, you need to be sure that two different inputs can not generate the same output, and that is called collision resistance. It is a key notion in cryptography.

Collisions

As seen precedently, the only thing that could compromise an encryption algorithm such as SHA256 would be a collision (two different inputs giving the same output).
What are the chances of that hapenning ? Galvatron gave an eloquent answer on Stack Exchange : using all computational power of the bitcoin network, it would take 5 billion years, without taking in account all problems needed to store and compare the hashes throughout the network.

Usefullness of cryprography in a provably-fair system

SHA256 satisfies our requirements of security :

• Nobody will find a collision (theoritically) in the hash chain and therefore be able to predict games by reproducing the hash chain, protecting the operator,
• There’s no way for the casino to alter a game and still get continuity in the hash chain, offering protection against manipulation to the players.

Part 3 : Generating a hash chain in Python

^{Source : Standford Edu}

Introduction

Now that the context is set, this part is the core of the contribution. I will now explain, step by step, how to generate a hash chain in Python, and the finished code is the one in the repository.

Requirements

I’m gonna use Python v3.5.2 and MySQL. You can of course adapt to your preferences : almost every langage has a module for SHA256 encryption and your hash chain can be stored on any database system.

The files:

1. hashchain.py which is the file genertaing the hash chain,
2. table.sql which contains the instruction to create the table needed.

Modules required

Only MySQLdb is not included in the Python Standard Library and will require you to install it.

So we have :
hashlib that is a built-in module that allows you to encrypt data in most popular algorithms,
MySQLdb has a name that speaks for itself, it will manage connection to our MySQL database and the storage of data on it,
string (string manipulation),
random (pseudo-random number generator).

Configuration variables

There are not a lot of configuration variables for this script. You just have to put your MySQL credentials and the desired length of the hash chain that is going to be generated.

Main Thread

So the main thread does, in that order:

1. It generates the Secret House Key and hash it. Nothing in this function generate_server_seed() will be stored, so there's no chance of the secret key being revealed or hacked.
2. It opens a connection to the MySQL database.
3. It generates the hash chain of the desired length (defined in the hashchain_length variables) and stores it into the MySQL database,
4. It closes the connection,
5. It verifies the integrity of the hash chain generated (redundant security check).

Functions

generate_server_seed()

To ensure the maximum level of security possible, it generates and returns the hash of the secret house key directly, and doesn't display any step of the generation.

It does a loop of a thousand iterations, and in each of them it generates a randomized string of ten thousands characters, hashes it, concatenates it with the previous final hash, and then hashes the concatenation to obtain the final hash for this iteration.

verify_integrity()

In this function, it just iterates through the hash chain generated to make sure there is indeed continuity, and that nothing failed in the generation of the hash chain.

Part 4 : Using the hash chain to generate game results

The files concerned are testhash_lottery.py and testhash_bistabit.py.
As we will need to do operations on more than a few millions hashes to make sure the calculations used to determine a game result are working as intended, we won't use the hash chain just generated. For this part, we're not using the hashes for real games, so we don't need to be preoccupied by fairness. The only goal is to test the result formula to make sure it does what we want.

We're gonna simulate two types of results:

• Classic lottery (generating results between 1 and 100),
• Bustabit-like multipliers (generating random numbers with a fixed median).

But you will be able, on your own, to try any formula you want, to generate by yourself results that suit your game.

Lottery results (testhash_lottery.py)

Generating a hash chain on the fly*

Here we loop on a certain number of tries (defined in the nb_tries variable, here set to 10 millions). For each of these tries, we transform the hash into a lottery result (in this example a number between 1 and 100).

We store it to be able to make statistics of all the results and determine if our formula is doing what we want.

Displaying statistics

We calculate the mean and the median of all 10 million results.

And then we display a graph with the distribution of the results.

So our formula is good for drawing random numbers between 1 and a 100, with the possibility of being provably-fair, hence transparent in our results with no defiance from the players.

Bustabit-like multipliers (testhash_bustabit.py)

Here, the principle is the same, so we will just look at the formula and the statistics.

Formula

The formula is not used, this time, to generate simple numbers between 1 and a 100, but to generate results between 1 and 10³⁵ with a fixed median.

Statistics

^{The figure has been deliberately truncated}

Here, the goal of bustabit-like multipliers is to have a formula that has a median of 1.99 (hence giving to the operator a 0.5% house edge).

To explain that simply, imagine a player:

1. That bets always the same amount,
2. Always on the x2 multiplier.

As the median is 1.99, probability of a x2 or more is 49.5%, meaning that with this strategy, on the long term, the player will lose 0.5% of all his bets (that's the house edge).

Making your own formula

By changing the way you use the hash to make a result, and then testing it thoroughly on a very large number of iterations (the 10 million used here might not be sufficient to be certain).

You can imagine a system where you want a certain mean, another median value, a number between x and y, or everything you might want or need for your own game.

If you respect the principles of:

1. Generating a hash chain,
2. Choosing a client seed,
3. Having a correct formula.
4. Publicizing at the right time all these items.

You will have the foundation of a provably-fair game. But all the UI is still yours to make.

How to contribute ?

You can contribute by creating pull requests on the repository mainly:

• By correcting errors you might see in the code,
• By optimizing it,
• By any way you would see fit.

Thanks for reading