Demonstrably fair raffle draws

Me and a group of friends decided to organize a vacation for a fairly large group of people, including accommodation. However we ended up having more people wanting to attend than accommodations, so we decide to just make it a raffle on who would get to go and who wouldn’t. This is pretty simple for the 4 people organizing it to do fairly. However, trust issues may arise when you have 40 people wanting one of the 30 spots, and accusations of favoritism will be bound to happen at some point so I, someone else and 2 beers, decided to try and find a way that, not only for the organizers to make a fair raffle, but for the participants to know the draw is indeed fair.

The issue

• There are 30 free spots to be assigned
• Accommodations are rooms for 2 people (IE: 15 rooms)
• There are more people than available accommodation spots

What we want

• The draw must be random
• The draw must be verifiable by the participants
• The draw must not be affected by the participants
• The draw must not be affected by the organizers

As a result of the previous requirements, the draw must be:

• Reproducible by the participants

A solution

For drawing n people from a group of m we could randomize the list of participants in some way, then draw the first n people on the list. This would be a fairly straightforward solution if we can find a way to randomize the list that is out of the control of the organizers or the participants, so why not let a third party add some randomness for us, for example a real life lottery draw, and then use an algorithm that given that third party’s randomness will reorder the list in a reproducible manner. At this point we have:

• People, their names, surnames and dates of birth
  • Since these are not bound to change on short notice, it ensures that the participants don’t have control over the process
• A third party providing a random seed at a future date
  • Since no one can see the future yet, it ensures the organizers cannot rig the draw beforehand

With these ingredients we can ask cryptography to come to the rescue and do the draw in a way that will make all of the people involved happy.

Cryptography to the rescue

With the participants immutable input (Name, surname, birth) we have a fair chance of having no collisions, or if a number can be assigned to each participant beforehand that can be used in its place then, with a real life lottery draw as the source of randomness, we have a way of for each participant and a key, getting a random number, with the use for example of an HMAC.

Key (RL Lottery draw)
    |
    +--> +------+
         | HMAC | --> 0x84FA..07
    +--> +------+
    |
"Name;Surname;DOB"
or "Assigned number"
or "Nickname"
or "..."

Then sorting by the result of the HMAC we can pick the first n people on the list as the winners of the raffle and, should any of the winners decline to attend, the next in line to take its place it is clear, just pick n+1 on the list.

If the list of participants is published before the draw happens, it prevents most foul play from both parties since any change on the list would be noticed. The process is then pretty straightforward and easy to implement. With for example this code snippet below that takes the people.csv document, with rows consisting of Name;Surname;Birth it generates a draw.csv with all the names sorted by the HMAC using the provided secret SEED.

import hmac

SEED=bytes('5495993812', 'utf-8')
DIGEST='sha3_224'

if __name__ == '__main__':
  draws = {}
  keys  = []
  with open('people.csv', 'r') as in_f:
    for l in in_f.readlines():
      l = l.replace('\r', '').replace('\n', '')
      h = hmac.new(SEED, bytes(l, 'utf-8'), DIGEST)
      key = int.from_bytes(h.digest(), 'big')
      keys.append(key)
      draws[key] = l + ";" + h.hexdigest()
    keys.sort()
  with open('draw.csv', 'w') as out_f:
    for key in keys:
      out_f.write(draws[key] + '\n')

So given the people.csv here, it would yield the following draw.csv. (You can click these links to watch the result online)

TL;DR

• Gather the list of participants
• Publish it (rien ne va plus!)
• Wait for an agreed real life lottery draw
• Use the winning numbers as the HMAC key
• Calculate the HMAC for each participant
• Sort by HMAC value
• Pick the winners in order of HMAC value

How fair is it really?

I ran this algorithm for 1000000 consecutive numbers as the seed and plotted the results on a chart. There were 101 participants for 30 slots, and here are the winning percent for each of the 101 participants against the expected value:

Zoomed in to see the tiny variations.

Zoomed out.