Problems Using Math.random () / Mail.ru Group Blog

In English there is such an abbreviation - TIFU. We cannot give its exact meaning here, but you can easily find it on the Web. And after the "literary processing" TIFU can be translated as "today I messed up everything." In the context of this post, this phrase refers to the use of the Math.random () function in the V8 JavaScript engine. Although this did not happen today, but a couple of years ago. Yes, and I broke firewood through no fault of my own, the root of evil lies in this very function.

“Many of the random number generators used today do not work very well. Developers usually try not to delve into how such routines work. And it often happens that some old, unsatisfactory working method is blindly adopted over and over again by many programmers, who often simply don’t know about its inherent flaws. ”

Donald Knuth,“ The Art of Programming ”, vol. 2.

I hope that by the end of this post you will agree with two statements:

• We were idiots because we used a pseudo-random number generator in V8, without understanding its limitations. And if you are very lazy, then it is safer to use cryptographically robust pseudo-random number generators .
• V8 requires a new implementation of Math.random (). The work of the current algorithm, wandering from one programmer to another, cannot be considered satisfactory due to the weak, non-obvious degradation, which is often found in real projects.

I want to emphasize that the V8 engine itself is a wonderful product and its creators are very talented. I do not blame them in any way. It’s just that this situation illustrates how much even small nuances influence the development process.

The operation of the Betable project depends on random numbers. Among other things, with their help identifiers are generated. Since the architecture is a system of distributed microservices, it was easier to implement random identifiers than sequential ones. For example, with each API request, random request identifiers are generated. They are placed in subqueries in the headers, logged and used to compare and correlate all events occurring in all services, as a result of a single request. There is nothing complicated in generating random identifiers. There is only one requirement: The

probability of double generation of the same identifier - the occurrence of a collision - should be extremely small . Two factors affect the likelihood of a collision:

1. Identification space size - the number of unique identifiers that are possible.
2. Method for generating identifiers - how an identifier is selected from a common space.

Ideally, we need a large space from which uniformly distributed identifiers are randomly selected (since we assume that any “random” process uses a uniform distribution ).

We calculated the probability of collisions from the birthday paradox and accepted that the size of the request identifier would be 22 characters long, selected from a dictionary containing 64 letters. For example, EB5iGydiUL0h4bRu1ZyRIi or HV2ZKGVJJklN0eH35IgNaB . Since each symbol of the identifier can take one of 64 values, our identification space has a size of 64 ²² ≈ 2 ¹³². With this amount of space, if identifiers are randomly generated at a speed of 1 million per second , then the probability of a collision within 300 years will be 1 to 6 billion .

Well, the space was big enough. How do we randomly generate? The answer is: using a decent pseudo-random generator (PRNG), which can usually be found in many standard libraries. At the top level of our stack is the Node.js service, which in turn uses the V8 engine developed by Google for Chrome. All compatible ECMAScript (JavaScript) implementations should use Math.random (), which returns a random number from 0 to 1 without any arguments. Based on the sequence of these numbers from 0 to 1, you need to generate a random word consisting of 64 characters of the alphabet. This is a fairly common task for which a standard solution has been developed:

var ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_';
random_base64 = function random_base64(length) {
    var str = "";
    for (var i=0; i < length; ++i) {
        var rand = Math.floor(Math.random() * ALPHABET.length);
        str += ALPHABET.substring(rand, rand+1);
    }
    return str;
}

Link .

No need to criticize this code, everything is fine with it, it does exactly what it should. Move on. We developed a procedure for generating random identifiers with an extremely low probability of collision. We test, commit, push, test, deploy. The above example got into production, and we forgot about it. But one day a letter came from a colleague saying that the incredible happened:





"Anyone who allows the use of arithmetic methods to generate random numbers commits a sin." John von Neumann spoke of the obvious: the assertion that deterministic methods (for example, arithmetic) cannot generate random numbers is a tautology. So what is PRNG?

What are pseudo random number generators?

Let's look at a simple PRNG and the results of its work:



This illustration explains von Neumann's idea: it is obvious that the generated sequence of numbers is not random. For many tasks this is enough. But we need an algorithm that generates numbers that seem random. Technically, they should appear to be independent and equally distributed random variables uniformly distributed over the entire range of the generator. In other words, we need to safely pretend that our pseudo-random numbers are truly random.

If the result of the generator is very difficult to distinguish from a truly random sequence, then it is calledhigh quality generator. Otherwise - low quality . For the most part, quality is determined empirically by running statistical tests at a level of randomness. For example, the number of zeros and ones is estimated, the number of collisions is calculated, the Monte Carlo method is used to calculate π, etc. Another, more pragmatic method for assessing the quality of PRNG is to analyze its work in practice and compare it with truly random numbers.

In addition to the randomness of the result, the simple algorithm that we are considering demonstrates other important features common to all PRNGs. If you generate numbers for a long time, then sooner or later the same sequence will begin to repeat. This property is called periodicity, and all PRNGs “suffer” it.

Period, or cycle length , is the length of a sequence of numbers created by the generator before the first repetition.

You can consider PRNG as a highly compressed cryptographic book containing a sequence of numbers. Some spy could use it as a one-time pad. The starting position in this “book” is seed (). Gradually, you will reach its end and return to the beginning, completing the cycle.

The large cycle length does not guarantee high quality, but contributes greatly to it. Often it is guaranteed by some kind of mathematical proof. Even when we cannot accurately calculate the length of the cycle, we are completely capable of determining its upper boundary. Since the next state of PRNG and its result are deterministic functions of the current state, the cycle length cannot be greater than the number of possible states. To achieve maximum length, the generator must go through all possible states before returning to the current one.

If the state of the PRNG is described as k-bit , then the cycle length is ≤ 2 ^k . If it really reaches this value, then such a generator is called a full cycle generator. In good PRNGs, the cycle length is close to this upper bound. Otherwise, you will be wasting your memory.

Let's now analyze the number of unique random values ​​generated by the PRNG using some deterministic transformation of the output. Suppose we need to generate three random numbers from 0 to 15, like 2, 13, 4 or 5, 12, 15. We can have 16 ³ = 4096 such triple combinations, but the simple generator that we are considering can produce only 16 combinations:



So we come to another property of all PRNGs: the number of unique values that can be generated from a pseudo-random sequence is limited by the length of the sequence loop .

It doesn't matter what values ​​we generate in this case. They can be 16 combinations of four values ​​(or any other length), 16 unique matrix arrays, etc. Not more than 16 unique values ​​of any type.

Remember our algorithm for generating random identifiers consisting of 22 characters, taken from a 64-character dictionary. It turns out that we generate combinations of 22 numbers from 0 to 63. And here we are faced with the same problem: the number of possible unique identifiers is limited by the size of the internal state of the PRNG and the length of its cycle.

Math.random ()

Let's get back to our sheep. Having received a letter about the occurrence of a conflict, we quickly reviewed our mathematical calculations for the birthday paradox and checked the code. They did not find anything criminal, which means that the problem lies deeper. They started to understand.

Here is what Math.random () says in the ECMAScript specification :

Returns a positive numeric value greater than or equal to 0, but less than 1, chosen randomly or pseudo-randomly with approximately uniform distribution in this range, using an algorithm or strategy that depends on a particular implementation.

The specification is poor. Firstly, nothing is said about accuracy. Since ECMAScript uses IEEE 754 binary64 double-precision floating-point numbers, we can expect accuracy at the level of 53 bits (i.e., random values ​​take the form x / 2 ⁵³ , where x = 0 ... 2 ⁵³ - 1). Mozilla's SpiderMonkey engine is of the same opinion , but it is not. As will be shown below, the accuracy of Math.random () in V8 is only 32 bits (the values ​​take the form x / 2 ³² , where x = 0 ... 2 ³² - 1). However, this is not important, since we need six bits to generate random letters from our dictionary.

But what turned out to be really important for us is that the specification does not define a specific algorithm. There are no requirements for a minimum cycle length, so goodbye quality: the distribution should only be “approximately uniform”. So, to find the cause of the collision, you need to analyze the specific algorithm used by V8. We did not find anything in the documentation, so I had to refer to the source code.

Pseudo Random Number Generator in V8

“I had to put up with Mersenne’s whirlwind because everyone uses it (Python, Ruby, etc.).” This brief description of Dean McNami is the only meaningful response to the analysis of the PRNG code in V8 when it was first communicated on June 15, 2009.

Over the past six years, the PRNG code in V8 has been remade and straightened. It used to be native code , but now it is in user space . But the algorithm remained unchanged. The current implementation uses an internal API and is rather confusing, so consider a more readable implementation of the same algorithm:

var MAX_RAND = Math.pow(2, 32);
var state = [seed(), seed()];
var mwc1616 = function mwc1616() {
    var r0 = (18030 * (state[0] & 0xFFFF)) + (state[0] >>> 16) | 0;
    var r1 = (36969 * (state[1] & 0xFFFF)) + (state[1] >>> 16) | 0;
    state = [r0, r1];
    var x = ((r0 << 16) + (r1 & 0xFFFF)) | 0;
    if (x < 0) {
        x = x + MAX_RAND;
    }
    return x / MAX_RAND;
}

Link.

It looks obscure, we will understand.

There is one clue. In older versions of V8, there was a comment: "The random number generator uses George Marsaglia’s MWC algorithm." The following was found in the search engine:

• George Marsaglia was a mathematician and spent most of his career studying PRNG. He also developed Diehard tests to measure the quality of random number generators.
• MWC stands for multiply-wit-carry . This is a class of pseudo random number generators developed by Marsaglia . They are very similar to the classic linear congruent generators (LCG), an example of which we examined above. And if you believe paragraph 3.6 of this document , the MWC is fully consistent with the LCG. The only difference is that MWCs can generate sequences with a longer cycle length with a comparable number of processor cycles.

So if you need PRNG, then MWC seems like a good choice.

But the algorithm implemented in V8 is not like a typical MWC. Probably the reason is that this is not MWC, but two MWC generators at once - one in line 5, the second in line 6 - together generating one random number in line 9. I won’t post all the calculations here, but each of these regenerators has a cycle length of approximately 2 ³⁰ , which gives a total length of the generated sequence of approximately 2 ⁶⁰ .

But we have, as you remember, 2 ¹³²possible identifiers. Suppose that the condition of uniform distribution is met. Then, the probability of collision after randomly generated 100 million identifiers should be less than 0.4%. But collisions began to arise much earlier. Probably, we made a mistake somewhere with our analysis. Perhaps the problem is a uniform distribution - there is probably some sort of additional structure in the generated sequence.

The story of two generators

Let's take another look at the ID generation code:

var ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_';
random_base64 = function random_base64(length) {
    var str = "";
    for (var i=0; i < length; ++i) {
        var rand = Math.floor(Math.random() * ALPHABET.length);
        str += ALPHABET.substring(rand, rand+1);
    }
    return str;
}

Link .

Of great importance is the scaling method in the sixth row. It is recommended by MDN for scaling random numbers and is used very widely ( example 1 , example 2 , example 3 , example 4 , example 5 , example 6 ). The method is known as multiply-and-floor, take-from-top . He got the last name because the lower bits of a random number are truncated, and the left - upper, top, - are used as a scaled integer result.

Note: if the ratio of the output range of the PRNG to the scalable range is a fractional number, then this method works with a small bias. This is usually solved with the use of the rejection sample used in standard libraries of other languages .



Notice the problem? Two generators mix rather strangely in the V8 algorithm. Numbers from two streams are not combined modulo 2 (xor). Instead, the bottom 16 bits of the output of each subgenerator are simply concatenated. That seems to be the problem. When we multiply Math.random () by 64 and reduce it to the smallest (floor), then we will have the top 6 bits. These bits are generated exclusively by one of the two MWC subgenerators.



The bits from PRNG No. 1 are highlighted in red, and from PRNG No. 2 in blue.

If we independently analyze the first sub-generator, we will see that its internal state has a length of 32 bits. This is not a full cycle generator, the actual length is about 590 million: 18,030 * 2 ¹⁵ - 1, details of the calculations can be found here - link 1 , link 2 . That is, we can generate no more than 590 million unique request identifiers. And if they were chosen randomly, then after 30 thousand generations the probability of collision would be 50% .

But if that were so, we would almost immediately begin to notice collisions. But we did not notice them. To understand why this did not happen, let's recall the example of generating combinations of three numbers using 4-bit LCG.



In this case, the birthday paradox is not applicable - the sequence cannot even be called random, so we cannot pretend . Obviously, there will be no takes before the 17th combination. The same thing happens with PRNG in V8: under certain conditions, the lack of randomness reduces the likelihood that we will see a collision.

That is, the determinism of the generator played into our hands. But this does not always happen. The main conclusion that we made is that even in high-quality PRNGs, distribution randomness cannot be assumed unless the cycle length is much longer than the number of values ​​you generate.

If you need N random values, then you need to use PRNG with a cycle length of at least N ² . The reason for this is that, given the PRNG period, excessive uniformity can reduce performance in some important statistical tests (especially in tests for collisions). To prevent this, the sample size N must be proportional to the square root of the length of the period. You can read more about this on page 22 of the wonderfulthe work of Pierre Lekue, in the chapter on random number generators.

In cases like ours, when they try to generate unique values ​​with the help of several independent sequences from one generator, they are worried not so much about randomness as about how the sequences do not coincide. Suppose we have N sequences with a length L from a generator with period P. Then the probability of coincidence will be equal.



For sufficiently large values ​​of P, the probability will be approximately equal to LN ² / P (details: ref. 1 , ref. 2 ). So, we need a long cycle, otherwise we will mistakenly pretend that our sequence is random.

In short, if you use Math.random () in V8 and you need a fairly high-quality sequence of random numbers, then do not use more than 24 thousand numbers. And if you generate in several powerful streams and you need to avoid matches, then generally forget about Math.random ().

A Brief History of MWC1616

“The MWC generator concatenates two 16-bit multiply-with-carry-generators [...] with a period of 2 ⁶⁰ and seems to pass all random tests. My favorite standalone generator is faster than the KISS containing it. ” This is an excerpt from the description of the MWC1616 algorithm that underlies Math.random () in V8. Judging by the words of Marsaglia, it satisfies most of the main criteria by which PRNG is chosen.

MWC1616 was introducedin 1997 as a simple main generator. The phrase “seems to pass all tests for chance” betrays the empirical nature of Marsaglia’s methodology. He seemed to trust the algorithm since it passed Diehard tests. Unfortunately, the tests he used in the late 1990s were not good enough, at least based on current standards. If we run MWC1616 through a more modern testing framework like TestU01 , the result will be disastrous . Even the MINSTD generator shows better results, but it was outdated back in the 1990s. Probably, the Diehard tests simply were not sufficiently detailed, so Marsaglia made this conclusion.

// January 12, 1999 / V8 PRNG: ((r0 << 16) + (r1 ^ 0xFFFF)) % 2^32 
var x = ((r0 << 16) + (r1 & 0xFFFF)) | 0;
// January 20, 1999: (r0 << 16) + r1) % 2^32
var x = ((r0 << 16) + r1) | 0;

Link .

As far as I know, the concatenation procedure of two subsets of generated bits, performed in MWC1616, has no mathematical base. Typically, the bits from the subgenerators are combined using arithmetic modulo operations (for example, xor). It seems that Marsaglia was preoccupied with the lack of a mathematical base shortly after the publication of his algorithm as a component of one of the versions of the KISS generator . On January 12, 1999, the MWC1616 version used in the V8 was released. And on January 20, Marsaglia published another version of his algorithm. In it, the upper bits of the second generator are not discarded, the flows are mixed more precisely.

Both versions of the algorithm appeared on different resources, which caused confusion. The late (improved) version calledMWC with Base b = 2 ¹⁶ , published on Numerical Recipes under the heading “When You Only Have 32-bit Computing”. And instead of introducing one of the algorithms, it was suggested "to use the compiler better!". Pretty dull advice regarding an algorithm that is better than that used in V8. For inexplicable reasons, the January 20 version is provided on Wikipedia as an example of a computational method for generating random numbers. An older version of January 12 was included twice in TestU01 , first under the name MWC1616, and then MWC97R. This algorithm is also used as one of the generators in the R language .

In general, MWC is used quite widely. And I hope this article serves as a warning to many developers, becoming a development and confirmation of Knut's observations:

• In general, you need to independently analyze the work of PRNG to understand the limitations of the algorithms used or implemented.
• Do not use MWC1616, it is of little use.

There are many more useful options. Let's look at a couple.

Alternative as CSPRNG

So, we had to quickly replace Math.random () with something. There are many other PRNGs for JavaScript, but we had two conditions:

• The generator must have a sufficiently long period to generate ^2,132 identifiers.
• It should be thoroughly tested and have good support.

Fortunately, the Node.js standard library has another generator that satisfies our requirements: crypto.randomBytes () , cryptographically secure PRNG (CSPRNG), which calls RAND_bytes used in OpenSSL. According to the docs , he gives a random number using the SHA-1 hash with an internal state of 8184 bits, which is regularly re-randomized (reseed) from various entropic sources. In a web browser, crypto.getRandomValues ​​() should do the same .

This solution has three drawbacks:

• CSPRNG almost always uses non-linear transformations, and therefore they work more slowly than non-cryptographic alternatives.
• Many CSPRNG systems cannot be randomized (seed), which makes it impossible to create a reproducible sequence (for example, for testing purposes).
• CSPRNGs can unpredictably stand out from all other quality measures, some of which may be more important for your project.

However, there are advantages:

• In most cases, the performance of CSPRNG is quite sufficient (on my machine I can use crypto.getRandomValues ​​() to get about 100 Mb / s of random data in Chrome).
• To a certain extent, unpredictability implies the inability to distinguish the result of a generator from truly random data. So we can get everything we need from a pseudo-random sequence.
• If the generator is positioned as “cryptographically secure”, then it can be assumed that its code was analyzed more thoroughly and subjected to many practical tests for randomness.

Some assumptions still have to be made, but they are at least pragmatic and based on some evidence. If you are not sure about the quality of your non-cryptographic alternatives, it is best to use CSPRNG. At least until you need deterministic randomization or strong evidence of generator quality. If you do not trust CSPRNG from your standard library (and for the sake of reliability of cryptography this cannot be done), then you can use the urandom , which is controlled by the kernel (Linux uses a scheme similar to OpenSSl, and OS X uses the Yarrow generator ).

I don't know what the length of the loop is in crypto.randomBytes (). As far as I know, this problem does not have a closed solution. I can only say that with a large state space and a long flow of incoming entropy, the algorithm should be quite safe. Since you trust OpenSSL to generate public / private key pairs, what's the point of worrying about this? After we replaced Math.random () with crypto.randomBytes (), the collision problem disappeared.

In fact, Chrome could force Math.random () to call the same CSPRNG that is used for crypto.randomBytes (). Apparently, WebKit does just that . In any case, there are many other quick and high-quality non-cryptographic alternatives.

Disadvantages of PRNG in V8

I want to prove to you that it is impossible to use Math.random () in V8, this tool needs to be replaced. We have already discussed the presence of obvious structural patterns in the output, failed practical tests, and poor performance in real projects. If you still have little evidence, then take a look at this:





Top - noise based on random data from Safari, bottom - from V8. Pictures are generated in the browser using this code :



Calculation of the number π using the Monte Carlo algorithm, 10 ¹⁰ iterations. Code .

I hope you now agree that it's time to do something with Math.random (). The question is what exactly. Correcting a single line will improve bit combining, but I don't see any reason to stick to the MWC1616 at all. There are better options.

I am not going to arrange here a detailed comparison of the many existing methods for generating pseudorandom numbers. But at least I formalize the criteria that suitable generators must satisfy:

• A large state space and a large initial number (seed) - ideally, at least 1024 bits. This will be the upper limit for other generator quality parameters. In 99.9% of cases, a state space of size 2 ¹⁰²⁴ will be sufficient, while ensuring a good level of security.
• Speed . Take at the level of the best modern implementations - 25 million numbers per second on my computer.
• Эффективность использования памяти. Вероятно, для генератора с 1024 битами состояния в пользовательском пространстве JavaScript понадобится не менее 256 байт (мы можем использовать только 32 бита на каждое 64-битное число). Если это нереализуемо, то можно воспользоваться обходными путями, но будем считать, что это возможно.
• Очень длинный период. Генератор полного цикла — вещь хорошая, но и периода длиной больше 2⁵⁰ будет вполне достаточно, чтобы избежать цикличности. А при 2¹⁰⁰ мы можем безопасно использовать 2⁵⁰ и продолжать притворяться, что у нас истинно случайная последовательность.
• Прохождение практических тестов на случайность. Как минимум — TestU01. Он строже, чем Dieharder. Дополнительные баллы даются за прохождение BigCrush и хорошую равнораспределённость. Про тесты NIST или rngtest ничего сказать не могу, но их тоже надо бы использовать.

There are many PRNGs that satisfy or overlap these requirements. The xorshift generators (also developed by Marsaglia) have high performance and show excellent results on statistical tests. One option, called xorgens4096, was implemented in JavaScript . It has a state space of 4096 bits, a cycle length of about 2 ⁴⁰⁹⁶ and works faster on Chrome on my machine than MWC1616. In addition, BigCrush does not fail systematically.

Recently been shownthat multiplying the output of an xorshift generator by a constant is a fairly non-linear transformation, so the generator will not pass BigCrush. This class of generators is called xorshift *. They work very fast, use memory efficiently and are easy to implement . The xorshift1024 * generator meets all our requirements, some even in excess. Xorshift64 * consumes the same amount of memory, it has a longer cycle, runs faster than MWC1616. For the new family of hybrid linear-non-linear generators - PCG - the same performance and quality characteristics are announced.

In general, there is plenty to choose from. The safest thing is probably the standard Mersenne vortex. Its most popular option is MT19937, presented byin the late 1990s. Since then, it has become a standard generator in dozens of products . The thing is imperfect, but well tested and carefully analyzed. It’s easy to figure it out, it behaves well in practical tests. The loop length is already 2 ¹⁹⁹³⁷ - 1, it has an impressive 2 KB of state space and is criticized for its large memory consumption and not too high performance. There is also a JavaScript implementation . I did not compare its performance with Math.random () in Chrome on my computer.

In short, I completely agree with Dean McNami's commentary six years ago and recommend using the Mersenne vortex. It can be safely used by those developers who are not well aware of the design of pseudo-random number generators. If you want, use more exotic alternatives. But just get rid of the MWC1616, please!

Summary

It was a long post. Let's summarize:

• В движке V8 функция Math.random() использует алгоритм MWC1616. Если вы используете только самые важные 16 бит, то у этого алгоритма очень короткая и эффективная длина цикла (меньше 2³⁰). Показывает низкие результаты при прохождении практических тестов на качество. Во многих специфических случаях будет небезопасным притворяться, что данные получаются истинно случайными. Остерегайтесь использовать этот алгоритм для любых ответственных задач.
• Если у вас нет возможности тщательно выбрать некриптографическую альтернативу, то лучше применять криптографически безопасные PRNG. Безопаснее всего (в том числе для криптографических задач) — urandom. В браузере можно использовать crypto.getRandomValues().
• There are many other non-cryptographic pseudo-random number generators that work faster and with better quality than the MWC1616. V8 should implement any of them. The most popular and probably the safest candidate is the Mersenne Vortex (MT19937).

In conclusion, I note that the Mozilla LCG generator used from the util.Random Java package is not much better than the MWC1616. So it makes sense to update the generator in SpiderMonkey.

At the same time, browsers remain a dark and dangerous place. Take care of yourself!