Using Random Numbers in Neo Smart Contracts
Sometimes in computer programs like smart contracts we need random numbers. For example, in a lottery, you need to rely on a strong random number to select a winner. In a game, you might need to determine the outcome of some interaction between players. Randomness in computing is a really interesting topic in general, and I encourage you to read more about it.
In this tutorial, I’ll talk about how you can make use of randomness in a Neo smart contract.
Determinism in Neo smart contracts
Neo’s method of consensus requires that contracts be deterministic. A deterministic system is a system in which no randomness is involved in the development of future states of the system¹. Because execution of our contracts is distributed over multiple nodes, it makes perfect sense. Given the same inputs, each node will need to come up with the same output in order to reach consensus and form a new block in the blockchain. This works like a “pure function” in functional programming:
So, given this limitation, how can our smart contract programs determine a random outcome? Fortunately, Neo accounts for this and gives us a way to use random numbers. We can use data from previous blocks in the blockchain to provide our contract certain “random” values as input.
Generating a random number
The NeoContract White Paper mentions two methods of picking random numbers:
- Referencing the “Nonce field” of a block; or:
- The hash value of a block.
The latter method works because each block contains some intrinsic randomness from transactions, but this produces a “weak” random number. The former method is just as easy to use, and provides a better random number, so we’ll focus on it.
In the Neo Node documentation, the header of each Neo block contains a field called “Nonce” that stores a random number that the nodes all agreed upon when the block was created. This works in Neo’s deterministic system because every contract executed in future block will share the same number.
It’s worth noting here that, at the time of writing, Neo’s default implementation uses pseudo-random numbers that shouldn’t be relied upon in security-sensitive applications.
Here’s an example smart contract that finds the last block in the blockchain and sends a notification with its nonce, available in the C# API as a field called called ConsensusData:
Executing this contract results in output like this:
[Neo.Runtime.Notify] event name -> A random number:
[Neo.Runtime.Notify] item Integer: 49972955530062602That’s a mighty big number. Its type is uint64, or in C# a ulong, an unsigned 64-bit integer. In other words, we have a way to generate a number between zero and 18,446,744,073,709,551,615!
Finding a more useful number
That’s really cool, but how practical is it? Typically we either want a percentage or a number in a specific range. Let’s look at a few ways to use our newly found random number.
Percentages
Typically in programs, we want to represent a percentage as a floating-point number between 0 and 1. Neo VM, unfortunately for this purpose, doesn’t support floats or it would be as simple as:
float percentage = randomNumber / ulong.MaxValue;Instead you could use an integer between 0 and 99 (or 100, depending on your purpose). Let’s look at how we can find numbers in a range.
Ranges
A commonly used way to find a number between 0 and n is to use a modulo operation. (sometimes called “modulo reduction”). Let’s look at an example of this to find a number between 0 and 99:
Here’s the output:
[Neo.Runtime.Notify] event name -> A random number between 0 and 99:
[Neo.Runtime.Notify] item Integer: 39Easy, right? Except there’s a problem, depending on what you’re using this number for, this technique introduces a bias toward certain smaller numbers². This is obviously a big problem for games of chance, like a lottery or a raffle. It’s also a fairly expensive computational operation.
We can think of the problem we’re trying to solve as reducing our random number in scale, from the 64-bit integer range to our smaller range. For example, if we had 50 people buy tickets to a raffle, we want to reduce the random number we generated from a range of 0 through 18,446,744,073,709,551,615 to 0 through 49 to find the winner.
There exists a method³ of finding a fair mapping of these numbers by multiplying our random number by the size of the range we’re looking for, then bit-shifting the result back into place. What we’re left with is a fair number in the arbitrary range you need. This method requires the product of the multiplication to be a larger data type than our initial range can hold, and Neo’s random number is already 64-bits. We don’t have access to 128-bit integers in Neo, so how can we make this work?
The solution is pretty easy! We can just use the first 32-bits of our random number to perform the calculation. In the following example, I shift Neo’s random number to discard half of the bits, and then I apply the fast range technique to get our number:
[Neo.Runtime.Notify] event name -> The winning ticket is:
[Neo.Runtime.Notify] item Integer: 485This method has the additional benefit of being extremely fast on 64-bit processors. Double-win! So there you have it; a practical and fair method of finding random numbers in an arbitrary range in a Neo smart contract.
Have fun, and thanks for reading!
