Random number generation

Web3 systems often lack a source of randomness, which can limit the types of applications that can be made (such as games). We can develop a pseudo random number generator (PRNG). If you know the seed it is easy to generate the sequence of numbers from the PRNG; conversely, if you observe a subset of the sequence, it is difficult to determine the seed or what the next number in the sequence will be. Hence for a PRNG algorithm to be effective, the initial seed of the PRNG should not be public knowledge.

In this example, we’ll generate a PRNG function using what is known as a Linear Feedback Shift Register (LFSR). By keeping the initial seed of the PRNG secret using FHE, we can ensure that the sequence of random numbers generated is unpredictable in end user applications.

How will our algorithm work?

A Linear Feedback Shift Register (LFSR) is a sequential circuit that shifts bits through a register while applying a linear feedback function, typically implemented using XOR operations on selected bits (taps). It generates pseudo-random sequences by cycling through states determined by its initial seed and feedback configuration, providing a deterministic yet seemingly random output. The randomness arises from the mathematical properties of the feedback function, which maximizes the period of the sequence before repeating, provided the taps are chosen correctly.

Here we will generate the step to go from one random number to the next in the sequence; in practice, a program would implement this algorithm in a loop to generate a sequence of random numbers.

Normal program (aka no privacy)

One of the simplest forms of a PRNG that is highly efficient is the XORShift algorithm. This involves XORing the current state with a shifted version of itself several times. In particular, we use the 16-bit “798” Xorshift due to its long period (65535 elements) and reasonable randomness statistics. The 798 refers to the shifts used in the feedback function.

// Take in some state as `number`
uint16_t rng(uint16_t number)
{
    number ^= number << 7;
    number ^= number >> 9;
    number ^= number << 8;

    return number;
}

Private program walkthrough

To transform the prior program into a private one operating over encrypted data, we update the function’s signature with [[clang::fhe_program]] and the inputs/outputs with [[clang::encrypted]]. That’s it, we’re done! The program now hides the initial number used as the input along with the output.

[[clang::fhe_program]]
uint16_t rng([[clang::encrypted]] uint16_t number)
{
    number ^= number << 7;
    number ^= number >> 9;
    number ^= number << 8;

    return number;
}

Running the program

If you’d like to run the program, feel free to look at the corresponding code here.

Performance

Running the program takes 0.004 seconds on an AWS c7a.16xlarge machine (64 cores) and 0.009 seconds on an 14 inch M2 Macbook Pro with 10 cores (6 performance, 4 efficiency). This particular program can use very primitive FHE operations and therefore has a very fast runtime.

What’s missing?

In a real world application, the PRNG algorithm would have to be initialized with a random seed. In addition, the PRNG function would be called repeatedly to generate a sequence of pseudorandom numbers.