In light of Team Liquid's CS:GO giveaway, I wanted to devise a way to ensure a fair drawing. This blog post explains the method I've come up with which is based on the drawing method of reddit's "Millionaire Makers" giveaway. Please let me know if there's any improvements to be made or if I missed something!
Using the Twitter API, you can only get the latest 100 retweets. I wrote a script that polls the API every 30 seconds, fetching the latest 100 retweets and recording the date and user id.
The bitcoin network will be used as a source of randomness and timestamping. The merkle root of the first bitcoin block mined after the contest closes will be used as a source of randomness. The block timestamp must have a timestamp after the contest closing date to be considered valid.
A string will be created consisting of the numerical user_id of every entrant (including duplicates where multiple entries are allowed). The user_ids will be placed in ascending order and separated by a single space with no newlines. The SHA256 hash of this string will form the entrants hash, and can be used by an entrant to verify they were included in the drawing. The merkle root (m) and entrants hash (e) will be hashed together using SHA256 to create the drawing hash, in the format SHA256(m||e).
The first 8 bytes of the drawing hash will be converted to a little endian unsigned 64 bit integer. This integer modulus the number of entries will be calculated to come up with the winning entry number. The entry number is an index into a list of entrants sorted first by ascending entry date, then by ascending user id.
The winning account will be checked manually to ensure it is following the giveaway account and otherwise complies with contest rules. If the winning entry is deemed ineligible, the drawing hash is passed through another iteration of SHA256 and the process repeated until a valid winner is found.
Prior to releasing the winner, wait until the next bitcoin block is mined to ensure the block used in the drawing is not orphaned and thus is available publicly for provable fairness.
A hash of the drawing method as described here can be embedded into the bitcoin blockchain, acting as a secure timestamp to ensure the method does not change. As the transactions and nonce used to find a block in the bitcoin blockchain are unpredictable, it is impossible to know the winner beforehand until the block is mined.
Since it is difficult to obtain a full list of retweets from Twitter, it is hard for a 3rd party to verify the index picked matches the list of entrants. This can be mitigated by releasing a full list of entrants after the drawing, allowing each entrant to check their presence in the giveaway. By mixing a hash of the entrants list into the drawing hash, this ensures that the list of entrants released matches those that were used for the drawing.
As only the latest 100 retweets are available from the API, it is possible that some retweets may be missed during high activity periods such as when the tweet is first published. This can be improved by using a high polling rate (every few seconds) for the first few minutes after the tweet is published.