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
openssl can be used for
$ echo 'SEE YOU IN COURT, THE SECURITY OF OUR NATION IS AT STAKE!' \ | openssl sha -whirlpool (stdin)= 821e5d159ac7a472bb18daafe758a573dae21fcd1458ac1b85f4af0b1715b4b530c39fe36dcbdd4820f0ea8dc25cb8e6fdc2b9946ba238b99d31b0defd8f2d66
algorithm is one of the message digest algorithms supported by
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
The output is
(stdin)= LARGE-HEX-NUMBER. The leading
(stdin)= is in the way and has to be filtered away with
$ 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
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:
- John Doe
- Jane Doe
- J. Random Loser
- J. Random Winner
- 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.
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
is how to do the calculation in hex with
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
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