Elm comes with a nice purely-functional random number generator in the standard library. In fact, it’s a port of the Haskell’s System.Random.

Not only this random number generator implementation is deterministic (that is, given the same initial seed it will produce the same random sequence), it is also strictly purely-functional (just like everything in Elm, actually).

generate : Generator a -> Seed -> (a, Seed)

Above is the signature of the generate function that you use to produce random values. It takes a generator (Generator a) and a seed (Seed), and returns a randomly generated value (a) and the new Seed. And if you want to generate another random value, you need to use this new Seed in the next call to generate – if not, you’ll get back the same number that you got the first time.

So generate’s type signature explicitly tells us that the random value generation is completely defined by the seed that we supply it. This means that, if we have the initial Seed, we can get the whole sequence of random values.

Can this kind of generator be suitable for security-sensitive applications?

Secure random numbers

Probably not.

Deterministic random generation is great when you want to reproduce the application’s behavior consistently, for example in automated tests. Such generators can, of course, be useful in many other scenarios. For example, in deterministic models in game development, procedural content generation, etc.

But for security-related applications it is completely opposite: you definitely don’t want anyone to be able to figure out your randomly generated private key. If we wanted to generate random values for cryptographic purpose, we definitely wouldn’t want the random generator to be so explicitly predictable.

The perfect generator

Surprisingly, the core Elm library doesn’t come with such a random value generator.

So we’re going to try to bring it to Elm. To start simple, let’s limit to generating Ints – the rest we then can easily derive later.

Suppose our ideal random value generating function would have the following signature:

getRandomInt : () -> Int

According to this type signature, we don’t want to give the generation function any context at all, and we want a random Int in return. As the function doesn’t take a seed or other random generation algorithm parameters as an argument means that the function caller is not in control of the random value generation anymore – perfect.

So how does one implement such a function? Well, turns out it is impossible to do in a purely-functional way. Think about it, how would you make a random number every time if all you are given is a ()? Even returning just different number on each call is impossible:

getRandomInt : () -> Int
getRandomInt () = ... -- what?

Mathematically speaking, the function’s image can not have more elements than it’s domain, by definition. Domain, in our case, is the () type, which is inhabited by exactly one value (or element). This means that such kind of function can only return the same value every time.

Breaking the math

So mathematically, we can not make a perfect random number generator. So what? This is not a maths class, this is hacking!

Given that modern browsers already provide a cryptographically secure random number generator implementation, the window.crypto.getRandomValues function, we will only need to provide Elm bindings for it!

Writing Elm bindings for raw JavaScript code is not complicated. In our case, it would look like this:

// boilerplate
Elm.Native.SecureRandom = {};
Elm.Native.SecureRandom.make = function(localRuntime) {
  localRuntime.Native = localRuntime.Native || {};
  localRuntime.Native.SecureRandom = localRuntime.Native.SecureRandom || {};
  if (localRuntime.Native.SecureRandom.values) {
    return localRuntime.Native.SecureRandom.values;
  }

  // actual code
  var crypto = window.crypto;

  return localRuntime.Native.SecureRandom.values = {
    getRandomInt: function () {
      // generate a singleton array of unsigned 32-bit ints and return
      // that single value.
      return crypto.getRandomValues(new Uint32Array(1))[0];
    }
  };
};

And the Elm module:

module SecureRandom where

import Native.SecureRandom

getRandomInt : () -> Int
getRandomInt = Native.SecureRandom.getRandomInt

Side effects

Okay, this should work, right?

Wrong.

It will run, but will work largely not the way one might expect. The problem is that this isn’t a pure function anymore: the math is broken, and it will not return the same value given the same input (hello, random number generation?), by causing a side effect of changing the random generator’s internal state.

Now if you consider this type signature again, you might see that it doesn’t really make any sense in a purely-functional programming language: it will have to either return the same value every time (because how can a function’s value vary if it can’t get any variation in it’s input?), thus not being random at all, or completely abandon purity (that’s what we did with our JavaScript bindings).

Being impure might not seem like a big deal, but there are practical implications to this. As referential transparency is now broken for your impure (or effectful) function, you can not make a lot of assumptions about your code by just looking at it. The state that the function depends on (to provide the side effects) is now removed from the function’s type signature. You now will need to mentally manipulate this state every time the function is called in order to determine the call’s result. And as this state may change on every call, you now can not tell the result of your program until you actually execute it.

The compiler is now misguided too: since it assumes that all functions are pure, it may decide to reorder, inline or substitute function calls for optimizations. As an effectful function’s result now really depends on some hidden state (of which the compiler is not aware!), these optimizations may result in an absolutely unpredictable and most certainly incorrect program behavior.

Taming side effects in Elm

As we established that our getRandomInt function will have side effects, we now should use the power of the language’s type system and encode this fact in the function’s type. We will also need to use a proper implementation.

One way to accomplish this in Elm is using the Task x a type. It is widely used to do things like HTTP requests, local storage access, reading cookies, etc. All of these operations have side effects, as they either depend on or modify some global environment.

A Task x a value means that some, possibly effectful, action (task) will be performed at some point in time, and a successful result of its execution will be an a value while a failure result will be encoded with an x value. It is not that dissimilar from the .NET’s Task<T> class and Haskell’s IO a.

So our updated function signature should now look like this:

getRandomInt : () -> Task never Int

We know that we want to do an effectful computation – generate a random value of type Int. We’re keeping it simple for now, by saying that our computation can never fail – that’s what the never type variable means in our case.

(The name never doesn’t actually matter, it’s only important that it is a free type variable and our function’s return value of type Task x Int can be used with any x, depending on the context.)

But how do we know that this kind of function will not have any (unwanted) side effects? We know this by inspecting the possibilities that Elm gives us to operate on Task x a values:

  • You can not get the resulting value out of a Task immediately, thus causing the side effect to happen arbitrarily
  • You do not control when the Task is actually executed – the Elm runtime does this for you, and you should trust it

You are fundamentally limited to just two things you can do to Tasks:

  • You only can wait for the Task to complete, and then perform another Task:

    andThen : Task x a -> (a -> Task x b) -> Task x b
    
  • And you also can create a Task that will bear no side effects, and will just instantly resolve as completed and either return a particular value or fail with an error value:

    succeed : a -> Task x a
    
    fail : x -> Task x a
    

It turns out that this is enough to do all kinds of things when constructing simple or complicated task workflows. In fact, the Task x a type forms a monad.

But there is no way to explicitly run a task in Elm – you run tasks by connecting them to a port. Here, the Elm runtime protects us from using tasks in an incorrect way by completely monopolizing the way they are executed.

Native tasks

Okay, let’s now fix our code to generate random numbers inside a Task. Here’s how our JavaScript code should look like:

// boilerplate
Elm.Native.SecureRandom = {};
Elm.Native.SecureRandom.make = function(localRuntime) {
  localRuntime.Native = localRuntime.Native || {};
  localRuntime.Native.SecureRandom = localRuntime.Native.SecureRandom || {};
  if (localRuntime.Native.SecureRandom.values) {
    return localRuntime.Native.SecureRandom.values;
  }

  var crypto = window.crypto;

  // the Task module
  var Task = Elm.Native.Task.make(localRuntime);

  return localRuntime.Native.SecureRandom.values = {
    getRandomInt: function () {
      // create the Task
      return Task.asyncFunction(function (callback) {
        // notify that our Task has completed with some result
        callback(
          // wrap the random int into a succeeding Task
          Task.succeed(
            // generate a random int
            crypto.getRandomValues(new Uint32Array(1))[0]));
      });
    }
  };
};

We create the Task by calling the Task.asyncFunction function and giving it our worker function that will be called when it’s time to execute the task. Our function will be given a callback, which we should call when the Task is complete, and we are ready to return the resulting value.

Elm code:

module SecureRandom where

import Native.SecureRandom

getRandomInt : () -> Task never Int
getRandomInt = Native.SecureRandom.getRandomInt

As you can see, only the type signature has changed in the Elm module.

Conclusion

I’ve used this approach to accomplish secure random password generation in Elm. (I know, I already did this twice!)

I’ve put these Elm bindings together into a library, which you can find here on GitHub. There is a simple example of how you can use it in practice, but you can also check out the source code of my password generation app. Hope you will find it helpful.

As for side effect management in purely-functional languages, it may look a bit daunting in the beginning, but it definitely pays off in the long run.

comments powered by Disqus