Why Firelotto’s blockchain-based random engine is not fair?

Firelotto is a blockchain-based lottery launched on January 1, 2018. It advertises itself as the first decentralised lottery platform using Ethereum (ETH) smart contracts and it is characterised by complete transparency. Its decentralised features aim at eliminating the industry’s most predominant concern, manipulation, by removing the need of a third party controlling/managing the lottery outcome. Its pre-sale of FLOT tokens started on January 15 and will last until February 15, while the main ICO event is scheduled between March 15 and April 15. By the time this article is written, more than $3M have been collected from 3300+ users.

Sounds almost perfect, but does transparency imply fairness?

Smart contracts suffer through the code used to create them being prone to bugs. Among the others, in June 2016, a hacker made off with over $50M of cryptocurrency by exploiting a combination of vulnerabilities and the user gained control of 3.6M Ether, around a third of the 11.5M Ether that had been committed to The DAO. This eventually led to the famous Ethereum hard fork, which moved the funds tied to The DAO to a new smart contract designed to do one thing: let the original token owners withdraw the funds.

Unfortunately, Firelotto’s contract code seems to suffer from various issues:
a) It has been criticised by users for its approach to selling tickets: The platform demands a wallet’s private keys to participate in the lottery. The Firelotto team claims that this solution is a temporary workaround.

b) Firelotto uses the Bitcoin block hashes as source of entropy, but as of yesterday there is a serious reported bug in their github repository, according to which:

the owner (drawer) can end the game choosing whatever bitcoin block hash they want, allowing them to precompute and choose an arbitrary winner.

c) We prove in this post that their random generation algorithm is biased (modulo bias) and the distribution is skewed, favouring the smaller numbers.

What’s actually wrong with current Firelotto’s Random generation?

After running a brute force simulation of the Firelotto’s lottery of 4/20 by taking all the 2³² combinations for the last 4 bytes, we end up in the following results:

Chart 1. Firelotto — 4/20 probability per number

In the above chart we can clearly see the effect of the modulo bias.

  • Number 1 has higher probability to be picked compared to any other number.
  • Similarly, numbers 2,3,4 have a higher probability compared to the rest.
  • And finally, the number with the worst performance is 17 which has the lowest probability to be picked.

FireLotto’s Random Generation Contract Code

Let’s have a closer look to their actual random engine. Firelotto is using a variant of Durstenfeld’s algorithm which originally moves the “struck” numbers to the end of the list by swapping them with the last unstruck number at each iteration. This algorithm is in turn based on the popular Fisher-Yates shuffe. One of the differences is that Firelotto uses an extra array to keep track of already selected numbers. This does not cause harm, but what matters is how the actual random picking is happening, which is unfortunately prone to modulo bias.

By focusing on the contract’s code (shown below) we can recognize 3 main parts:

  1. The bitcoin’s blockchain hash value (in bytes) — this is the seed.
  2. The numbers array
  3. The modulo operation which picks the winning numbers
Code 1. Firelotto getWinNumbers function

The Random generation process is well described in the Firelotto’s white paper. Basically, it uses a Bitcoin block hash value as an input entropy source in order to perform the lottery draw. Until now, everything seems fine.

However, it only utilises the last N bytes of each block (numbersCount), which after converted to unsigned int (the range of the byte after the conversion will be 0..255), they are used to determine which indices to pick (and consequently select the lucky numbers).

In the 3rd part, the modulo operation is performed between the numbers’ decreasing list length and the the next byte. At this stage, we can detect a modulo bias issue, because:
a) n might does not divide 256

b) even if it did, n is constantly decreasing in each iteration and apparently some of them if not all won’t divide 256.

Modulo Bias definition

Let’s now see what modulo bias actually is and how it affects the Firelotto’s algorithm’s fairness. Let’s assume we have a list of numbers (L)

and we want to pick randomly one of them. A very common practice is to actually generate a random number (R) between a range of 0…X and then normalise the result by performing a modulo operation on the length of our initial array. Our primary target is to pick one of the 5 numbers above. For the sake of this example, let’s assume that our random number (R) can be something between 0–12.

The modulo operation we are discussing is in fact the following one:

We are sure that by providing any input as the R number, the result (Index) will be a number between 0 and 4. So, if for example our randomly generated number is R = 11, then:

Did you notice what we just did?
We produced a randomly generated number between 0–12, normalized it via the modulo operation in order to give us an index between 0–4 and then we picked the lucky number from our list on the corresponding position, in our case 1.

So, everything sounds uniform and fair. However, it’s not. If we go some steps ahead and perform all the possible modulo operations for the random R=0..12 for our array L with length 5, then, we will observe the following results:

The graph above depicts occurrences per index. As we can easily spot, indices 0–2 appear 3 times in our distribution table, but 3 and 4 can appear only 2 times. That gives an edge on the indices 0–2 since they have higher probability to be picked. Thus, our modulo operation does not ensure that our remainders (the indices) will be evenly distributed. That’s the modulo bias.

For the Firelotto case, replace the random number R range with 0..255 and the list number of L with the range 1–20 and you’ll have the first game of Firelotto which suffers from the modulo bias. Note that a similar scenario applies to any N, eg. 45 or 60.

Chart 2. Firelotto 4/20 total occurrences per number (exhaustive search)

Why Smart Contract validation is painful and sometimes incomplete?

To adequately audit a smart contract, an organization or ICO would need to engage a network security “consulting” company and/or hire experts in blockchain and smart contract coding. Community review is also a good source of ideas and beneficial feedback. But if the above sound impractical, that’s because they are:

a) Innovative ideas, like this transparent raffle engine, are usually kept secret until it’s safe to be revealed and thus they are not well-exposed to community experts. Sometimes, it might be too late or complex to upgrade contract logic.

b) The process involves a host of specialist resources (eg. cryptographers), it might be expensive and would still be prone to the “human element,” i.e. simple mistakes, bad actors or a lack of trust in the motivations of those auditing.

Is it the first time that a random generator is flawed?

No, up until recently many cryptographic products used to produce random numbers with the Dual EC_DRBG algorithm which has been reported to contain a fatal flaw that could be exploited by US intelligence agents. Eventually, in 2014, the US National Institute of Standards and Technology (NIST) has revised its recommendations and formally removed the algorithm suspected to contain the backdoor.

Surprisingly, there is another story that proves how randomization failures can cost lives, yes real lives! “The 1969 Vietnam War draft lottery”. Briefly, in 1969 the Selective Service organized a lottery to decide which boys would be drafted into the military. They decided to draft people by randomly selecting them by their birthdates. However, by putting the birthdays into the bin in sequence and by insufficiently mixing them up, they increased the likelihood that the last days put in were most likely to be the first ones grabbed.

Conclusion
Firelotto’s contract logic requires refactoring and redesign; a concrete solution is probably feasible, but proper review is recommended before it advertises itself as secure, fair, transparent and eventually functional.

Also, we stress that developing custom random generators is not usually a good idea and based on our academic experience, research in this area requires the approval of the scientific community, for instance by submitting to a peer-reviewed conference. Their current lottery engine is skewed and the outcome is proved to be non-uniform.

Moreover, especially for this sector, external auditing is a necessity. Feedback and review from blockchain and cryptography experts, but also from the community (eg. reddit) is required. When everything is in place, it’s true that a fully decentralised lottery solution will eliminate the trust issues conventional lotteries face, as it turns out that there is a lack of oversight after an operator receives their gambling license.
For instance, the Malta Gaming Authority uses the following language on their website:

After the certification process required for issue of the full five year licence, the gaming system need not be tested regularly, but there will be follow up audits by the Gaming Authority when deemed prudent.

A similar approach is followed by the Isle of Man in their guidance for online Gambling:

While many operators may have their games’ RNG checked on a more frequent periodic basis, the GSC will have an operator’s RNG checked at least twice in a licence’s 5 year lifespan.

Due to the hype of the blockchain industry, it’s inevitable that a similar to The DAO case will be in the news some time in the near future, so let’s be proactive and obsessed with security!

Authors
Konstantinos Chalkias (Cryptographer and Soft. Engineer)
Anastasios Kichidis (PhD candidate in Crypto-currencies and Soft. Engineer)