Provably-fair selection "k out of n"

pickWinner.py

#!/usr/bin/env python3

# This script computes an ordered list of k random integers from the range
# [1, n] (both inclusive).  This is done in a provably fair way based on
# some hex seed (may be a Bitcoin block hash, for instance).

import codecs
import hashlib
import math
import struct

# The seed, from which random numbers are computed.  This can be arbitrary
# hex data, like a Bitcoin block hash.
seed = "00112233"

# The total number of available choices.
n = 10
# The number of choices to select.
k = 3

# Convert the seed to binary data.
binSeed = codecs.decode (seed, "hex_codec")

def getRandom (nonce):
  """
  Computes a random number in [1, n].  The computation is based on the seed
  as well as the given nonce, which can be used to find multiple independent
  random numbers from the same seed.
  """

  # Hash the base seed together with the nonce.
  h = hashlib.sha256 ()
  h.update (binSeed)
  h.update (struct.pack ("<I", nonce))
  rand = h.digest ()

  # Use the first four bytes of the hash value as 32-bit integer and
  # compute the final result from it by scaling to the output range.
  # In contrast to simply taking the value mod n, this avoids a bias
  # towards smaller numbers.
  num = struct.unpack ("<I", rand[:4])
  num = num[0]
  scaled = num / (1 << 32)
  return math.ceil (scaled * n)

# Use the random number function we have to pick an ordered set of k
# non-repeating items.
result = []
found = set ()
nonce = 0
while len (result) < k:
  item = getRandom (nonce)
  nonce += 1

  if item not in found:
    result.append (item)
    found.add (item)

# Print result.
print ("Sorted list of winners (in the range 1..%d inclusive):" % n)
for r in result:
  print ("  %d" % r)