Provable

A Provably fair random hash generator which can be plugged into random-js.

Install

npm install --save provable

About

This library attempts to implement the algorithm first outlined in the bitcoin talk forums: https://bitcointalk.org/index.php?topic=922898.0. The idea behind provably random is that a deteministic series of related but random hashes are generated before any random outcomes are calculated. Once generated, each hash in the series is used to create a random outcome.

The provable part comes in when a client wants to verify the integrity of the outcome. After every outcome is produced the hash which produced it can also be made public. If one has access to the current hash and the previous hash (from the previous outcome), then a SHA256 can be used on the current hash to generate the previous. This should hold true for all hashes in the series as they are exposed. You cannot predict the next hash, but you can verify the previous hash by hashing its predecessor. Any deviation from this verification result would mean that the hashes were tampered with and not part of the pregenerated series. Hence you can "prove" the random outcomes were fair.

Bear in mind since the series is pre-generated, this means eventually you will run out of hashes to generate random outcomes and a new series of provably fair hashes must be created.

Usage

This library can be used standalone to generate a series of random hashes generated by nodes crypto sha256 hasher. By default the engine will only supply a 32-bit random integer based on the next hash in the series. The state of the engine can be saved and resumed as needed.

This library includes some simple utility functions to convert a hash into float, int and bools from a single hash.

When the engine runs out of hashes ( reaches end of series) an error is thrown. Its up to the user to catch the error and determine how to proceed from that point. Typically you would switch to or generate a new series and continue.

  var Provable = require('provable')
 
  var engine = Provable({
    count:10000, //default:1, number of hashes in the series to produce, takes longer depending on how big the number is
    seed:'optional seed to start your series with' //defaults to some random string with letters and numbers
  })
 
  //return a random int32 and increments the internal state to the next hash
  var int32 = engine()
 
  //raw sha256 hash. Increments your hash index. Throws an error if no hashes left.
  //if you want to do your own random calculations then use this. 
  var hash = engine.next()
 
 
  //static conversion functions, no dependency on random-js
  //these functions have no affect on internal state
  var float = Provable.toFloat(hash,0,1,true)  //hash, min, max, true = include max | false = exclude max
  var int = Provable.toInt(hash)  //same as int32 from engine()
  var bool = Provable.toBool(hash,.5) //hash, percent true, .5 = 50%
 
  //internal state of the engine. Use this to save and resume your engine.
  var state = engine.state()
 
  //resuming will re-generate the entire hash chain 
  //from your seed and pick up where you left off with the index
  var resumedEngine = Provable(state)
 

Random-JS

Random-js can give you more options over the types of random values you can generate. Keep in mind that random-js only uses 32 bits of the hash and 2 hashes in order to generate 1 outcome. This is important when developing your third party verification. This provable engine defaults to using the 32 least significant bits of the hash when generating the random integer.

If you dont want to use random-js there are static functions included with the library which will generate ints, bools and floats from a hash.

  var Random = require('random-js')
  var Provable = require('provable')
 
  //initizlize engine with 10k hashes
  var engine = Provable({ count:10000 }
 
  //we make a never ending hashing function to feed into random js
  //the provable engine will throw an error when the end of a hash series 
  //is reached
  function next(){
    try{
      return engine()
    //only throws when hashes run out
    catch(e){
      //create new series
      engine = Provable({ count:10000 }
      return next()
    }
  }
  
  //use random like a random-js object
  var random = Random(engine)
 
  //some examples
  random.bool()
  random.integer(min,max)
  random.real(min,max,inclusive)
  //etc...
 
  //keep in mind random js uses 2 hashes per outcome. You will need to also use
  //random-js on your third party verification site
 

Proving Fairness

When proving fairness to clients, you must expose each hash only after they are used to generate the random outcome. Never expose your seed parameter. Generally you can provide some third party site, like JSbin to create a third party validation site. The latest version of provable comes bundled with pre built js which you can include on a page. You should not include them in your production site because minified file is over 300k.

Using from third party client in browser

This library comes bundled with the full version and a minified version of the library, which can be included with a script tag in your html:

674k https://cdn.rawgit.com/daywiss/provable/master/dist/provable.js 383k https://cdn.rawgit.com/daywiss/provable/master/dist/provable.min.js

You should not include these files in your production site, as even minified the file is over 300k.

Instead include them in your js-bin or other third party link for verifying your provable outcomes.

Provable will be added to your global namespace which will have the same api as the node module.

Example Third party proof

Simple jsbin example program has been created to show how to use provable to verify your hashes

JSBin Example

Other Things to know

On construction, the engine will generate the entire hash series, the length of which is determined by the "count" parameter. By default count is 1. It is suggested to change this to something large, like 10000 or more. Hashes are generated syncronously so there may be blocking for long periods if the count is very large. Hashes are also stored in memory as 256-bit string, so memory usage can grow quickly.

Hashes are created in a deterministic way, so if you seed it with the same value, the hashes will come out the same. Never expose your seed or all your outcomes can be predicted. If you want random series every time, do not provide a seed on construction, a random UUIDv4 will be generated for you.

All parameters passed into the engine at construction time represent the internal state of the engine. As hashes are used, this state changes. State changes can be observed through the onChange callback or polled through the engine.state() function. At any point you can resume where you left off by constructing a new engine and passing in the last state.

When hashes run out, the call to get the next hash will fail and throw an error. Its up to you to handle how to proceed when that happens. You can also peek at the next value to see if its undefined, which means the next call will throw.

API

Provable(config,onChange)

Create a hash series and start the stateful engine. Optionally provide a state change callback. All parameters are optional, but in practice you should provide at least a hash count to generate.

  var Provable = require('provable')
  //node the actual list of hashes is not passed in as option. This will be generated on engine construction
  //based on the config you supply. You can get the list with engine.hashes()
 
  var config = {
    id: // a string representing the unique id of this hash series, randomly generated if not supplied
    index: // integer representing which hash in the series will be used next
    count: //the number of hashes in this series
    seed: //a string to seed nodes crypto engine to start generating the first hash (last hash of series). Withold to seed with random hash.
    publicSeed: //an additional seed string value which can be made public, and/or chosen by your clients. 
                //will update the hash before being returned from engine(), engine.next() or engine.peek().
  }
 
  function onChange(state){
    //persist state change somewhere
  }
 
  var engine = Provable(config,onChange)
  //do stuff..

engine()

The default function of the engine is to provide a random 32 bit integer. This allows random-js to wrap the engine and produce random primitives. The integer is based on sampling the least significant 32 bits of the current hash. If a publicSeed option is supplied on engine construction then all calls to engine() will be rehashed with the public seed.

  //integer is random between [0, 2^32) exclusive
  //this increments your hash index and will call the change callback
  var integer = engine()

engine.next()

This gets the next raw sha256 hash in the series and increments your hash index. Will throw an error if no more hashes are found. If hashes run out, then generate a new engine with a new seed. Do not reuse old seeds as you will generate predictable hashes. The publicSeed parameter is optional. If supplied the hash will be combined with publicSeed for more fairness. publicSeed, if provided, should be published with the hash when proving fairness.

  //the next raw sha256 hash in the series. Update hash index and throws if no more hashes found.
  var hash = engine.next()
 

engine.peek(index)

Peek will return a hash without changing engine state. The index parameter is optional and will default to the current engine state index, which is essentially the next hash. If index is provided it will return to you the hash at that index. Returns undefined if you have reached the end of the series or there is no hash at that index.

  //the next raw sha256 hash in the series, does not change state of engine. 
  //will return undefined if no hash is found, or end of series will be reached
  //with next call
  var nextHash = engine.peek()
 
  //return hash at index 100
  var specifiedHash = engine.peek(100)
 

engine.last()

Returns the last hash which was used.

  var next = engine.next()
  var previous = engine.last()
 
  //next === previous
 

engine.hashes(start=(0), end=(hashes.length), includeSeed=(false), reverse=(false))

Returns the raw hashes which get generated from the seed. Include start and end indices which will be sliced from the hash list. By default it will return the whole list.

IncludeSeed variable will include original seed of the entire hash chain at the end of the hash list only if end == null or undefined.

Reverse variable will reverse the hash list after all queries have been applied. Use this when verifying your series on a third party site. The hash you are verifying is the seed at index 0, and all hashes after that are previous outcomes that have been played.

  //array of raw sha256 hashes. publicSeed not applied.
  var hashes = engine.hashes()
 
  //returns
  var hashes = engine.hashes(0,10)
 
 
  //"Proving" hashes
  var provable = Provable({
    seed:'hash to verify',
    count:10, //number of previous hashes to show
  })
  
  //returns 11 hashes, the seed hash + 10 previous outcomes
  var hashes = provable.hashes(null,null,true,true)
 
  //if you had a public seed you will have to hash against it manually
  hashes = hashes.map(function(hash,i){
    //ignore seed hash
    if(i == 0) return hash
    return Provable.rehash(hash,publicSeed)
  })
 
  

engine.state()

Returns the current internal state of the engine. Use this to persist and resume engine function. Does not include raw hash list, as it is regenerated on construction.

  //returns state of engine
  var state = engine.state()
  //persist state somewhere
  persistToDB(state.id,state)
 
  ...
 
  //get back old state
  var state = getFromDB(id)
 
  //resume from where you left off
  var engine = Provable(state)

Static Functions

Provable.toInt(hash, maxHex=(8), mostSig=(false))

Returns an integer based on any hash. Max hex is the number of characters sliced from the hash to determine your integer and bit count. It defaults to 8 characters which is a 32 bit int. MostSig allows you to take your int from the front(mostSig=true) or back of the hash(mostSig=false).

Provable.toFloat(hash, min=(0), max=(1), inclusive=(false), maxHex=(8), mostSig=(false))

Returns a float between min and max. You can include the max number by passing true to inclusive.

Provable.toBool(hash, percent(.5), maxHex=(8), mostSig=(false))

Returns a boolean value. The percent true can be adjusted through the percent parameter, defaults to 50%.

Provable.generate(count=(1),seed(required))

Generate a raw hash series. This is used internally by the engine but is exposed in case its useful to use directly. Consider it like a static function, does not reference the internal state of the engine. The result is an array of hashes which should be used starting at series[0]. Its important to use the hashes in the correct order, or they will be predictable.

  //generate 10000 hashes and returns an array of them with the seed value of "seed"
  var series = require('provable').generate(10000,'seed')

Provable.createSeed()

A static function which returns a random string created by Math.random. Use this to seed your call to Provable.generate.

  var Provable = require('provable')
  //results of this will be random every time
  var seed = Provable.createSeed()
  var series = Provable.generate(1000,seed)

Provable.rehash(firstHash,combineWith)

Combines hash with another hash through HMAC.

  var Provable = require('provable')
  var updatedhash = Provable.rehash(hash,publicSeed)
   

Provable.sha256(seed)

Hashes seed using sha256.

  var Provable = require('provable')
  var hash = Provable.sha256(seed)