Online Raffle

How To Do a Fair Online Raffle?

How can you draw the winner in an online raffle in a fair and reproducible manner? Fair means that all participants have an equal chance of winning. Reproducible in cyberspace means that every participant can generate the same result without being physically present at the draw.

It is common practice in an online raffle that all participants enter their names in a list. If that list has for example 2304 entries you just have to generate a random number between 1 and 2304 to determine the lucky winner.

Sources Of Random Data

The website www.random.org provides truly random data generated from atmospheric noise for everybody. On their start page you can create a random integer number in a certain range with one mouse click. This is probably a fair draw but it is not reproducible because every visitor will get a new random number from the site.

Fortunately, random.org also offers pregenerated files with random content for every date. The rules of the raffle can for example state that the winner will be calculated from the file of the end date of the raffle. However, due to bandwidth issues, you currently cannot download the files without registration.

But there is another free source of truly random data generated from atmospheric noise: the tweets from Donald J. Trump. You just have to slightly change the rules so that instead of the random data provided by random.org you base the calculation of the winner on the first tweet of Donald J. Trump following the closing date of the raffle.

Creating a Random Number From Random Text

For an example, let’s check Mr. Trump’s twitter account @realDonaldTrump for his latest tweet. At the time of this writing the text was “SEE YOU IN COURT, THE SECURITY OF OUR NATION IS AT STAKE!”, can somebody in the White House please fix his CAPS-Lock key?

That is our random text. How to turn that into a random number? We can calculate a check sum - also known as a message digest - of that text. The command-line tool openssl can be used for this purpose:

$ echo 'SEE YOU IN COURT, THE SECURITY OF OUR NATION IS AT STAKE!' \
    | openssl sha -whirlpool
(stdin)= 821e5d159ac7a472bb18daafe758a573dae21fcd1458ac1b85f4af0b1715b4b530c39fe36dcbdd4820f0ea8dc25cb8e6fdc2b9946ba238b99d31b0defd8f2d66

The Whirlpool algorithm is one of the message digest algorithms supported by openssl. Try openssl sha -h for other choices. I will pick whirlpool here because a whirlpool is also used when brewing beer, and the raffle that inspired this post was for a very cool brewing kettle.

The output is (stdin)= LARGE-HEX-NUMBER. The leading (stdin)= is in the way and has to be filtered away with sed:

$ echo 'SEE YOU IN COURT, THE SECURITY OF OUR NATION IS AT STAKE!' \
    | openssl sha -whirlpool \
    | sed -e 's/.*= //'
821e5d159ac7a472bb18daafe758a573dae21fcd1458ac1b85f4af0b1715b4b530c39fe36dcbdd4820f0ea8dc25cb8e6fdc2b9946ba238b99d31b0defd8f2d66

That leaves us with the hexadecimal number only. We will later use the arbitrary precision calculator bc for doing the math, and bc expects hexadecimal integer constants to use uppercase characters. The utility tr does the job for us:

$ echo 'SEE YOU IN COURT, THE SECURITY OF OUR NATION IS AT STAKE!' \
    | openssl sha -whirlpool \
    | sed -e 's/.*= //' \
    | tr '[:lower:]' '[:upper:]'
821E5D159AC7A472BB18DAAFE758A573DAE21FCD1458AC1B85F4AF0B1715B4B530C39FE36DCBDD4820F0EA8DC25CB8E6FDC2B9946BA238B99D31B0DEFD8F2D66

We now have a very large number in hexadecimal format calculated from the input string and since we are using a cryptographically secure message digest algorithm, this number will be completely different even if a single bit in the input changes. We at least believe so, based on today’s knowledge in number theory.

We also need a list of participants:

  1. John Doe
  2. Jane Doe
  3. J. Random Loser
  4. J. Random Winner
  5. Johnny Appleseed

Randomly picking an item in the list is very easy if we have a large random integer. Say the random number is 508. We just have to divide that random number by the number of participants and the remainder of the division plus one will point to the lucky winner:

508 ÷ 5 = 101 remainder 3

508 = 101 × 5 + 3, and hence the remainder is 3 but since the range of possible remainders is 0-4 we have to add 1 to the result for picking the winner. Participant number 4 in the list above is “J. Random Winner”.

With bc this becomes a piece of cake. The modulo operator (which gives you the remainder of a division) is % in the bc language:

$ bc
508 % 5 + 1
4
quit

But our random number is in hexadecimal notation. 508 in hex is 1FC. This is how to do the calculation in hex with bc:

1
2
3
4
5
ibase = 16
n = 1FC
ibase = A
n % 5 + 1
4

In line 1 of this bc script we set the input base to 16. Input numbers are now interpreted as hexadecimal, output will remain in decimal. We assign the hex number 1FC (508) to the variable n. In line 3 we switch back to decimal, and 10 is A in hexadecimal (our current input base).

Finally, in line 4 we do our calculation and the result is still 4.

How can we create this bc script on the fly? Perl will come to our help:

$ echo 1FC | perl -lne 'print "ibase=16;n=$_;ibase=A;n%5+1"' | bc
4

Voilà! Note that we have to replace the newlines with semi-colons, when we want to pipe input into bc.

And now go back to the original example with the message digest from Donald Trump’s tweet and 2304 participants:

$ echo 'SEE YOU IN COURT, THE SECURITY OF OUR NATION IS AT STAKE!' \
    | openssl sha -whirlpool \
    | sed -e 's/.*= //' \
    | tr '[:lower:]' '[:upper:]' \
    | perl -lne 'print "ibase=16;n=$_;ibase=A;n%2304+1"' \
    | bc
1639

Participant number 1639 has won!

Replace 2304 in the above example with the number of participants and use Trump’s current tweet as the source of entropy and you have put your online raffle on rock-solid, cryptographically secure foundations!


blog comments powered by Disqus