Discuss
  • PRNG - currently available solutions aren't addressing many use cases

PRNG - currently available solutions aren't addressing many use cases

# Michał Wadas (9 years ago)

As we all know, JavaScript as language lacks builtin randomness related utilities. All we have is Math.random() and environment provided RNG - window.crypto in browser and crypto module in NodeJS. Sadly, these APIs have serious disadvantages for many applications:

Math.random

  • implementation dependant
  • not seedable
  • unknown entropy
  • unknown cycle
  • returns float
  • portable

window.crypto

  • not widely known
  • not portable
  • not seedable
  • low level interface requiring passing typed array
  • allow to get maximally 65k values at once
  • cryptographically secure
  • allow any type of generated numbers

require('crypto')

  • not portable
  • asynchronous
  • low level interface
  • returns series of uint8
  • not seedable
  • cryptographically secure
  • asynchronous (can be advantage or disadvantage, depending on use case)

As we can see, all these either unreliable or designed mainly for cryptography.

That's we need easy to use, seedable random generator.

Why shouldn't it be provided by library?

  • average developer can't and don't want to find and verify quality of library - "cryptography is hard" and math is hard too
  • library size limits it usability on Web
  • no standard interface for PRNG - library can't be replaced as drop-in replacement

Specification should probably include:

  • seedable random generator instance (new RamdomGenerator(algorithm, seed)) with methods random(), ramdomInteger(min, max), fillWithRamdom(typedArray)
  • seedable sequence (infinite iterator)
  • promise-based solution for asynchronous tasks

Questions, ideas:

  • should we provide Array.prototype.shuffle?
  • should be internal state of generator exposed? Should it be read-only?
  • how many algorithms should be obligatory?
  • should we have methods like randomFloat32 corresponding to typed arrays?
  • GPU accelerated PRNG as optional extension?
  • UUIDs built in standard library?

Have I missed some use cases or restrictions?

Michał Wadas

# Calvin Metcalf (9 years ago)

node crypto is asynchronous or sync and it returns a buffer of binary data uint8's are just the default way of that node buffers represent data

# David Bruant (9 years ago)

Le 01/12/2015 20:20, Michał Wadas a écrit :

As we all know, JavaScript as language lacks builtin randomness related utilities. All we have is Math.random() and environment provided RNG - window.crypto in browser and crypto module in NodeJS. Sadly, these APIs have serious disadvantages for many applications:

Math.random

  • implementation dependant
  • not seedable
  • unknown entropy
  • unknown cycle (...)

I'm surprised by the level of control you describe (knowing the cycle, seeding, etc.). If you have all of this, then, your PRNG is just a deterministic function. Why generating numbers which "look" random if you want to control how they're generated?

window.crypto

  • not widely known

This is most certainly not a good reason to introduce a new API.

As we can see, all these either unreliable or designed mainly for cryptography.

That's we need easy to use, seedable random generator

Can you provide use cases the current options you listed make impossible or particularly hard?

Why shouldn't it be provided by library?

  • average developer can't and don't want to find and verify quality of library - "cryptography is hard" and math is hard too

A library or a browser implementation would both need to be "validated" by a test suite verifying some statistical properties. My point is that it's the same amount of work to validate the "quality" of the implementation.

  • library size limits it usability on Web

How big would the library be? How much unreasonable would it be compared to other libraries for other use cases? I'm not an expert on the topic, but of the few things I know, it's hard to imagine a PRNG function would be more than 10k

  • no standard interface for PRNG - library can't be replaced as drop-in replacement

We've seen in the past that good libraries become de-facto standard (at the library level, not the platform level) and candidate to being shimmed when the library is useful and there is motivation for a drop-in replacement (jQuery > Zepto, underscore > lodash). This can happen.

We've also seen ES Promises respect the Promise A+ spec or close enough if they don't (I'm not very familiar with the details).

# joe (9 years ago)

If you port the example code from the Wikipedia Mersenne Twister page (and add a float interface), you end up with around 80 lines of code. See here:

pastebin.com/KiKUcBpH

It works extremely well and is quite fast (I've not noticed any performance difference with Math.random, which on V8 is implemented as a simple congrual PRNG).

Speaking of simple congrual PRNGs, those are particularly easy, just a couple of lines:

function random() { seed = (seed*MULTIPLYER + PRIME_NUMBER) % MAXIMUM;

return seed / MAXIMUM; }

But, they suck (Wikipedia has a nice graphic illustrating this). Still, even they would be better than nothing.

# Ron Waldon (9 years ago)

---------- Forwarded message ---------- From: "Michał Wadas" <michalwadas at gmail.com> To: es-discuss at mozilla.org Cc: Date: Tue, 1 Dec 2015 20:20:34 +0100 Subject: PRNG - currently available solutions aren't addressing many use cases

...

  • not seedable

Chance JS is a fairly prominent high-level JavaScript library for this purpose, has a configurable seed, implements a Mersenne Twister, does not use Math.random(), but is likely in the PRNG class, not in the CSPRNG class: chancejs.com/#seed

That said, it would be interesting if some of the ES2015 primitives had built-in random generators: synchronous for PRNG, and asynchronous for CSPRNG. e.g.

Boolean.random() => Boolean

Boolean.randomCS(callback?) => Promise

Number.randomInt(min, max) => Number

Number.randomIntCS(min, max, callback?) => Promise

etc...

But these can be and are implemented just fine at the user-land level. As such, it's hard to justify making the standard library larger for this purpose.

For CSPRNG purposes, however, it could be valuable to standardise either Node.js crypto module, the window.crypto, or something new (that supports seeds)?

# Steve Fink (9 years ago)

On 12/01/2015 01:45 PM, David Bruant wrote:

Le 01/12/2015 20:20, Michał Wadas a écrit :

As we all know, JavaScript as language lacks builtin randomness related utilities. All we have is Math.random() and environment provided RNG - window.crypto in browser and crypto module in NodeJS. Sadly, these APIs have serious disadvantages for many applications:

Math.random

  • implementation dependant
  • not seedable
  • unknown entropy
  • unknown cycle (...)

I'm surprised by the level of control you describe (knowing the cycle, seeding, etc.). If you have all of this, then, your PRNG is just a deterministic function. Why generating numbers which "look" random if you want to control how they're generated?

I don't think the idea is that you need to know the cycle length, it's more that the spec does not currently mandate a minimum cycle length so implementations can and do implement Math.random in a way that produces cycle lengths much too short for some uses that might be expected to be reasonable. For example, if the generator internally uses independent 32 bit values and doesn't mix them together before producing a 64 bit result, then the cycle length of each half of that result is at most 2^32. You could record the whole set of them and perfectly predict the sequence with a couple of GB storage, much less if you can side-effect the generator you're after by drawing values from it yourself. Which perhaps doesn't matter, since you should be using a CPRNG if you're worried about prediction in the first place, but having a short cycle length for a subset of the bits will still bite you if you're masking off most of the bits (directly or indirectly). Having a birthday collision can really suck -- you thought you rented out the whole place for your party, only to find you have to share it with 3 other people. And they like very different music.

On the other hand, mandating a minimum cycle length may not help that, if the problem is with subsets of bits.

I'm not sure what "unknown entropy" means. I mean, in a way, if you seed it then there's zero entropy. Perhaps this refers to the capability of pulling from an external entropy source?

# Raymond Toy (9 years ago)

On Tue, Dec 1, 2015 at 1:45 PM, David Bruant <bruant.d at gmail.com> wrote:

Le 01/12/2015 20:20, Michał Wadas a écrit :

As we all know, JavaScript as language lacks builtin randomness related utilities. All we have is Math.random() and environment provided RNG - window.crypto in browser and crypto module in NodeJS. Sadly, these APIs have serious disadvantages for many applications:

Math.random

  • implementation dependant
  • not seedable
  • unknown entropy
  • unknown cycle (...)

I'm surprised by the level of control you describe (knowing the cycle, seeding, etc.). If you have all of this, then, your PRNG is just a deterministic function. Why generating numbers which "look" random if you want to control how they're generated?

​So I can reproduce a simulation exactly to figure out why it's not working. Well, only being able to seed is really required for this. ​