*The GitHub repo for this project can be found at [https://github.com/zaljubouri/twitch-rand](https://github.com/zaljubouri/twitch-rand).*

In [part one](/twitch-chat-rng-part-1), we discussed what goes into making a real random number generator—we chose our entropy source, determined it to be poor, and decided to use it anyway. In this article, we'll dig into the details of actually creating the generator. I've mentioned the National Institute of Standards and Technology (NIST) a couple of times already and I'm going to do so again, because they also provide documentation on creating a deterministic random bit generator (DRBG) in their prequel to SP 800-90B: the [Recommendation for Random Number Generation Using Deterministic Random Bit Generators](https://dx.doi.org/10.6028/NIST.SP.800-90Ar1) SP 800-90A, revision one. A real page turner, I delved deep and discovered a gold mine—the information here forms the entire basis of my DRBG. It details the concepts and requirements that power a DRBG, and provides three algorithms based on hash functions and block ciphers that would help me fulfil my dreams of generating random numbers.

## <AnchorHeading heading="Creating a DRBG" />

A quick-and-dirty explanation on the make-up of a DRGB: entropy goes in, an internal state is instantiated, and numbers can then be generated using said internal state. The state goes through reseeding based on certain conditions, pulling entropy from a pool to "refresh" it, preventing it from becoming stale and predictable. In my case, the entropy is the time between Twitch chat messages, and I followed NIST's `Hash_DRBG` mechanism to take care of the internal state and eventually generate random numbers; SHA-256 was my one-way hash function of choice ([CryptoJS](https://cryptojs.gitbook.io/docs/) providing a JavaScript implementation). I didn't worry about utilising nonces, personalisation strings, or additional input as they are all optional and, for an MVP, unnecessary. 

<Figure id={1} title={<>NIST's <code>Hash_DRBG</code> indicates how the internal state is managed.</>}>
 <ImageModal src={"../images/hash_drbg.png"} 
 alt="A diagram representing the make-up of a hash-based DRBG from NIST SP 800-90A."
 width={300} 
 />
</Figure>

The pseudocode provided for internal state initialisation, seeding, and reseeding was relatively straightforward to implement. I tested as I was going along, but I was using "small" numbers—only around thirty-two bits in length. When I started trying the actual number generation—utilising 256-bit long hashes—I noticed I was losing a lot of accuracy. I trusted too deeply in JavaScript's `number` type, not really thinking about its maximum integer. It turns out to be 253 - 1, which was enough for my initial testing, but nowhere near able to handle the operations my generation function performs. Thankfully, `bigint` exists—which in `V8`'s engine has a maximum length of a whopping billion bits—and resolved all of my precision woes.

## <AnchorHeading heading="Entropy pooling" />

The next consideration was how to actually provide the entropy to the internal state. I needed at least 256 bits of entropy before the mechanism would instantiate, and also for every subsequent reseed. Since I fudged the number of entropic bits I was receiving, and Twitch chat fired messages off at a rapid pace, this quota was quickly met. Despite this, I felt—on the off chance all the chatters decide to observe a minute's silence—I should try to use pools to store excess entropic data, so if there is a situation where a significant amount of random numbers are requested coinciding with an entropic drought, the DRBG would still be covered for reseeding and remain unpredictable. There are two popular algorithms in pooling: the [Yarrow algorithm](https://en.wikipedia.org/wiki/Yarrow_algorithm) and the [Fortuna](https://en.wikipedia.org/wiki/Fortuna_(PRNG)) method of accumulation.

Yarrow utilises what its authors call a slow pool and a fast pool. When data is received from the noise source, it is added to a pool in an alternate fashion, i.e. the first input goes to the fast pool, second to the slow, third to the fast, and so on. The fast pool is used for frequent reseeding, whereas the slow pool is used more sparingly. A reseed occurs when the fast pool in total contains entropy above a threshold limit (e.g. 100 bits), and the slow pool is used to reseed when at least two entropy emissions are above a certain threshold.

Fortuna uses thirty-two pools; entropy is added to each cyclically for an even distribution. Pool zero (**P0**) takes the lead in determining when a reseed should occur, initiating one whenever it reaches the entropy size threshold. Its contents are used alone to reseed in the first instance, but each subsequent reseed starts pulling in the contents of other pools if **2i** (**i** being the index of the pool) is a divisor of the number of reseeds, so **P0** is used every reseed, **P1** every other reseed, etc.

<Figure id={2} title={<>My Fortuna pools, filling with Twitch entropy.</>}>
 <ImageModal src={"../images/fortuna_pools.png"} 
 alt="A diagram representing a set of 32 filled and unfilled Fortuna pools."
 width={300} 
 />
</Figure>

Fortuna has become very popular, being utilised by FreeBSD's implementation of `/dev/random`, as well as by Apple in their OSes. This is likely due to its immense security against enumeration attacks; even if you had to reseed every hundred milliseconds, it would take nearly seven years before the thirty-second entropy pool is used. Based on this, I decided to go with it to provide the entropy to my RNG.

## <AnchorHeading heading="Random number generation" />

With the pool and internal state functionality in place, the final piece was linking them to the collection of entropy, and to provide a mechanism by which I could start generating random numbers. Using [`InversifyJS`](https://github.com/inversify/InversifyJS), I can create an RNG object with the pool and internal state initialised, then find the most active current broadcasts with Twitch's API and join their chat channels using [`tmi.js`](https://tmijs.com) (the same way I did in [part one](/twitch-chat-rng-part-1)). As the bot receives message events, it adds the time deltas to the pools, and the first seeding of the RNG would occur after pool zero reaches 256 bits of entropy. From there on out, the internal state would be seeded and random numbers are finally able to be requested. As data continues to be collected, reseeding occurs using different pools ensuring the numbers are always fresh.

<Figure id={3} title={<>Generating random numbers from `twitch-rand`.</>}>
 <ImageModal src={"../images/random_numbers.gif"} 
 alt="A GIF of random numbers being generated from https://www.twitch-rand.com/rng."
 width={300} 
 />
</Figure>

I created a visual representation of the DRBG which can be viewed at [`twitch-rand`](https://www.twitch-rand.com), showing the pools being filled and emptied, and how the internal state is manipulated.

## <AnchorHeading heading="Is it random?" />

After all of this work, it would be good to check the returned numbers for their randomness; this is a bittersweet proposition, as it may show the futility of this whole exercise. However, I feel like I have learned enough during this project that I'll be satisified no matter the results—eventually. As an initial test, I generated a million random numbers from `twitch-rand` and ran it through a set of IID (independent and identically distributed) tests. The results in [**Figure 4**](#figure4) show that it (thankfully) passed, and the numbers coming out of `twitch-rand` are at least IID. Out of the million numbers generated, only 258 were duplicates, and none duplicated more than once. I was initially surprised there were so many, as the RNG was set to generate numbers up to 232, but according to the [birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) there is a very high chance of duplicates occurring, even across large numbers.

<Figure id={4} title={<>Output from <code>iid-tests</code>.</>}>
 <center>
 <HighlightedCode language="typescript">
{`
┌─────────┬─────────────────────────┬──────┬─────────────┬────────────┐
│ (index) │ testName │ pass │ counterZero │ counterOne │
├─────────┼─────────────────────────┼──────┼─────────────┼────────────┤
│ 0 │ 'EXCURSION' │ true │ 460 │ 0 │
│ 1 │ 'NUM_DIRECTIONAL_RUNS' │ true │ 1401 │ 5 │
│ 2 │ 'LEN_DIRECTIONAL_RUNS' │ true │ 3981 │ 5950 │
│ 3 │ 'NUM_INCREASE_DECREASE' │ true │ 7580 │ 20 │
│ 4 │ 'LEN_RUNS_MEDIAN' │ true │ 287 │ 303 │
│ 5 │ 'NUM_RUNS_MEDIAN' │ true │ 789 │ 3 │
│ 6 │ 'AVG_COLLISION' │ true │ 6708 │ 0 │
│ 7 │ 'MAX_COLLISION' │ true │ 7205 │ 0 │
│ 8 │ 'PERIODICITY' │ true │ 4 │ 9996 │
│ 9 │ 'COVARIANCE' │ true │ 4661 │ 0 │
└─────────┴─────────────────────────┴──────┴─────────────┴────────────┘
The data can be assumed to be independent and identically distributed.
`}
 </HighlightedCode>
 </center>
</Figure>

Other popular randomness tests include [`dieharder`](https://linux.die.net/man/1/dieharder) and [`rng-tools`](https://wiki.archlinux.org/title/Rng-tools). These are extremely tough suites that stress an RNG to its limit, especially `dieharder` which has nearly twenty different tests demanding an extreme amount of randomly generated numbers, and a lot of high quality entropy to ensure they're all sufficiently different—`twitch-rand` categorically and unequivocally failed all of these tests. It's regrettable but expected, as towards the end of [part one](/twitch-chat-rng-part-1) we recognised the weakness of our entropy source.

## <AnchorHeading heading="Fin" /> 

Throughout this project, I gained a lot of insight into how the random number generation we take for granted works. I hope that this glimpse was interesting and accessible—I realise that I have barely scratched the surface of the subject matter. A large amount of research and work is done in this area by incredibly smart people as part of both academic and private groups. Their findings and creations are responsible for ensuring the encryption systems we rely on are suitably difficult for bad actors to penetrate, keeping our digital secrets safe. Unfortunately, [`twitch-rand`](https://www.twitch-rand.com) is unlikely to be powering the latest and greatest in cryptographic algorithms, but that's something I've come to terms with.

Following on from part one to complete the DRBG using Twitch-entropy and start generating random numbers.

Using Twitch chat to power random number generation — part 2 of 2

As part of my <Link href="/twitch-chat-rng-part-1" passHref>[series]()</Link> on random number generation, I mentioned a [suite of statistical tests](https://www.npmjs.com/package/iid-tests) used to determine whether a set of numbers is independent and identically distributed. I wrote these tests using Node.js and TypeScript—for convenience—without much thought given to performance and whether this approach was truly the best available to me.

When I started actually running the tests on real datasets containing a million values, I was hit with a completion time nearing three hours. I thought a possible “easy” fix would be to utilise more CPU power, as it was clear that the bulk of the time was spent running each permutation of the dataset through the statistical tests. This didn’t have to occur synchronously; each array could have its test statistics calculated independently of the others. The [`worker_threads`](https://nodejs.org/docs/latest-v14.x/api/worker_threads.html) module has been a stable feature since Node.js v12, and this seemed like a good opportunity to try it out. I knew this would not be a panacea for my performance woes, but it couldn’t make things worse.

Of course, the first thing I did was look for a higher-level library that abstracts away much of the worker threads syntax, and provides the thread-pooling logic I required. The titular [threads.js](https://threads.js.org) was the package of choice. The documentation is light but functional, and the initial implementation was straightforward. I created a worker class which takes an array of values and runs the statistical tests on said array. A thread pool can then be initialised and tasks can be queued, executing when threads become available. I began to run the program on various datasets and everything looked great—it was utilising all of my CPU’s threads, memory usage was stable, and it finished nearly four times faster in comparison to the original implementation. A closer look at the actual results, however, led to a series of mistakes which meant that I was not nearly done.

## <AnchorHeading heading="Mistake one — shuffling the array in the parent thread" />

The test suite needs to be run on 10,000 permutations of the original dataset, and this permuting is done using the [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) algorithm. The main loop, after implementing the workers and pools, looked like this:

<HighlightedCode fileName="index.ts" language="typescript" iconPath="mdiLanguageTypescript">
{`
// Start a threads.js pool with a worker and the number of CPU threads to use
const pool = Pool(() => spawn<ExampleWorker>(new Worker('./workers/ExampleWorker')), 12);
\n\
for (let i = 0; i < 10000; i++) {
 // Shuffle the original array
 const shuffledArray = shuffleArray(originalArray);
\n\
 // Add a task to the pool to run a function on the 
 // shuffled array and run another function on the result
 pool
 .queue(async (exampleWorker) => await exampleWorker.doSomething(shuffledArray))
 .then((result) => {
 const finalResult = doAnotherThingWithThe(result);
 });
 });
}
`}
</HighlightedCode>

When I ran it, I noticed my results were extremely uniform, i.e. every permutation held the exact same comparison to the original dataset. Prefixing `DEBUG=threads:*` to my run command enabled thread.js’ internal logging, and I could see clearly that the first shuffled array sent to each worker was being reused ad infinitum. I cannot explain why this occurs (and if someone can, I’d love to <Link href="/contact" passHref>[know]()</Link>), but the resolution was to expose the shuffling method on the worker class and ask the worker to perform it instead of the parent thread:

<HighlightedCode fileName="index.ts" language="typescript" iconPath="mdiLanguageTypescript">
{`
const pool = Pool(() => spawn<ExampleWorker>(new Worker('./workers/ExampleWorker')), 12);
\n\
for (let i = 0; i < 10000; i++) {
 // shuffledArray will now be different on each loop
 const shuffledArray = await pool.queue(
 async (exampleWorker) => await exampleWorker.shuffleArray(originalArray)
 );
\n\
 pool
 .queue(async (exampleWorker) => await exampleWorker.doSomething(shuffledArray))
 .then((result) => {
 const finalResult = doAnotherThingWithThe(result);
 });
 });
}
`}
</HighlightedCode>

Problem solved, and onto the next.

## <AnchorHeading heading="Mistake two — updating the counters on Promise fulfilment" />

This one was mostly due to wishful thinking. As a way of keeping memory efficient, the original, synchronous code would run the statistical tests on a permutation, and when complete it would immediately compare against the original dataset’s results to determine which counter (if any) to increment. I simply moved the same logic to the fulfilment handler:

<HighlightedCode fileName="index.ts" language="typescript" iconPath="mdiLanguageTypescript">
{`
const pool = Pool(() => spawn<ExampleWorker>(new Worker('./workers/ExampleWorker')), 12);
\n\
const someCounterZero = 0;
const someCounterOne = 0;
\n\
for (let i = 0; i < 10000; i++) {
 const shuffledArray = await pool.queue(
 async (exampleWorker) => await exampleWorker.shuffleArray(originalArray)
 );
\n\
 pool
 .queue(async (exampleWorker) => await exampleWorker.doSomething(shuffledArray))
 .then((result) => {
 const finalResult = doAnotherThingWithThe(result);
 \n\
 if (finalResult > 10) someCounterZero++;
 else someCounterOne++;
 });
 });
}
`}
</HighlightedCode>

As you can probably guess, trying to concurrently update a variable didn’t work out very well. When multiple workers complete their task at the same time and the parent thread uses the results to increment the same counter, there’s no guarantee it contains the latest value, and so the final result will be less than it should be. One way to resolve this could be to use JavaScript’s [`Atomics` object](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Atomics), but I opted for the simpler strategy of utilising `await Promise.all()`:

<HighlightedCode fileName="index.ts" language="typescript" iconPath="mdiLanguageTypescript">
{`
const pool = Pool(() => spawn<ExampleWorker>(new Worker('./workers/ExampleWorker')), 12);
\n\
const someCounterZero = 0;
const someCounterOne = 0;
\n\
for (let i = 0; i < 10000; i++) {
 const shuffledArray = await pool.queue(
 async (exampleWorker) => await exampleWorker.shuffleArray(originalArray)
 );
\n\
 // Add each task run to an array
 myTasks.push(
 pool.queue(async (exampleWorker) => {
 await exampleWorker.doSomething(shuffledArray);
 })
 );
}
`}
</HighlightedCode>

It does mean that the 10,000 result objects need to be processed synchronously after all the statistical tests have completed, but in my case this has negligible performance impact:

<HighlightedCode fileName="index.ts" language="typescript" iconPath="mdiLanguageTypescript">
{`
// ... Previous for-loop code
\n\
// Wait for all tasks to complete
await Promise.all(myTasks);
\n\
// Loop through the task results and perform the comparisons
for (let i = 0; i < myTasks.length; i++) {
 myTasks[i]
 .then((result) => {
 const finalResult = doAnotherThingWithThe(result);
 \n\
 if (finalResult > 10) someCounterZero++;
 else someCounterOne++;
 });
 });
}
`}
</HighlightedCode>

The counters will now increment sequentially and contain the correct values when all is said and done.

## <AnchorHeading heading="Mistake three — passing objects between parent and workers" />

If you have some familiarity with worker threads (or possibly multithreading in general), you might have noticed something missing from the previous code snippets. Running the program on small datasets worked well. However, as soon as I started using my dataset of a million numbers, I would see the memory usage climb before eventually causing an error:

<HighlightedCode language="javascript">FATAL ERROR: MarkCompactCollector: young object promotion failed Allocation failed - JavaScript heap out of memory</HighlightedCode>

The heap runs out of space and the program crashes. Even when utilising the [V8](https://v8.dev/) option `--max-old-space-size`, unused memory is not freed fast enough and the same error occurs. When objects are sent between worker threads, their structure is copied over. It also seems like these copied objects are not cleared off the heap once they’ve been used. Node has the function `process.memoryUsage()` which provides a snapshot of your program’s memory usage. Some analysis—excessive use of `console.log()` and breakpoints—showed that whenever something was returned from a worker to the parent thread, the heap usage increased, eventually resulting in the fatal error. 

There’s a JavaScript concept of [transferable objects](https://developer.mozilla.org/en-US/docs/Web/API/Transferable), where ownership of the object is transferred between threads as opposed to simply copying the entire structure over—no duplicates are created, no extra memory is required. If you’ve experience with using C/C++, it’s like passing by reference. In threads.js, the helper function `Transfer()` takes a transferable object (`ArrayBufferLike`s) and marks it to be transferred between threads. The following shows this in action when returning objects from the worker thread to the parent:

<HighlightedCode fileName="exampleWorker.ts" language="typescript" iconPath="mdiLanguageTypescript">
{`
import { serialize } from 'v8';
import { TransferDescriptor } from 'threads';
import { expose, Transfer } from 'threads/worker';
import { shuffleArray, doYetAnotherThing } from 'somewhere';
\n\
const exampleWorker = {
 shuffleArray: (originalArray: number[]): TransferDescriptor => {
 const shuffledArray = shuffleArray(originalArray);
\n\
 // Convert the shuffled array into a Uint32Array which is ArrayBufferLike
 const uint32ShuffledArray = new Uint32Array(shuffledArray);
 // threads.js' Transfer method signals ownership of the result should be transferred
 return Transfer(uint32ShuffledArray.buffer, [uint32ShuffledArray.buffer]);
 },
 doSomething: (shuffledArray: number[]): TransferDescriptor => {
 const result = doYetAnotherThing(shuffledArray);
\n\
 // Use v8.serialize to transform the result into an ArrayBufferLike
 const serializedResult = serialize(result);
 // threads.js' Transfer method signals ownership of the result should be transferred
 return Transfer(serializedResult.buffer, [serializedResult.buffer]);
 },
};
\n\
export type ExampleWorker = typeof exampleWorker;
\n\
expose(exampleWorker);
`}
</HighlightedCode>

For an object that doesn’t naturally fit into an `ArrayBufferLike`, the V8 `serialize()` and `deserialize()` methods work to reshape it into something that will, and eventually restore it to its former glory. Now when I ran the code, the heap usage did not increase at a rate the garbage collector cannot maintain, the results were accurate, and order seemed to be restored—until I noticed a spike in memory usage to 10 GB.

The issue causing this is similar except it’s now a crack in what Node.js calls “external” memory usage, the makeup of which is all the C++ objects bound to JavaScript objects. Since we already *transferised*—a verb I’ve made up that denotes marking an object as transferable—the objects being returned from the workers, it’s logical that those being passed to the workers also need transferising. As these are number arrays, it’s simply a case of using `Uint32Array`’s constructor to convert it into an `ArrayBufferLike` which can then be used with `Transfer()`:

<HighlightedCode fileName="index.ts" language="typescript" iconPath="mdiLanguageTypescript">
{`
for (let i = 0; i < 10000; i++) {
 const shuffledArray = await pool.queue(async (exampleWorker) => {
 // Convert the original array to Uint32Array
 const uint32OriginalArray = new Uint32Array(originalArray);
 \n\
 // Transfer ownership of the Uint32Array to the worker
 return await exampleWorker.shuffleArray(
 Transfer(uint32OriginalArray.buffer, [uint32OriginalArray.buffer])
 );
 });
\n\
 myTasks.push(
 pool.queue(async (exampleWorker) => {
 // Convert the shuffled array to Uint32Array
 const uint32ShuffledArray = new Uint32Array(shuffledArray);
\n\
 // Transfer ownership of the Uint32Array to the worker
 return await exampleWorker.doSomething(
 Transfer(uint32ShuffledArray.buffer, [uint32ShuffledArray.buffer])
 );
 })
 );
}
`}
</HighlightedCode>

If the functions your worker runs rely on non-`ArrayBufferLike` variables, then you need to make sure to convert the input to the type expected by those functions:

<HighlightedCode fileName="exampleWorker.ts" language="typescript" iconPath="mdiLanguageTypescript">
{`
import { serialize } from 'v8';
import { TransferDescriptor } from 'threads';
import { expose, Transfer } from 'threads/worker';
import { shuffleArray, doYetAnotherThing } from 'somewhere';
\n\
const exampleWorker = {
 shuffleArray: (originalArray: any): TransferDescriptor => {
 // Convert the TransferDescriptor into a Uint32Array into a number array
 // This looks silly but TypeScript compilation will fail, and if you force-compile it,
 // a runtime TypeError will occur on execution
 const numberArray = Array.from(new Uint32Array(originalArray));
 const shuffledArray = shuffleArray(numberArray);
\n\
 const uint32ShuffledArray = new Uint32Array(shuffledArray);
 return Transfer(uint32ShuffledArray.buffer, [uint32ShuffledArray.buffer]);
 },
 doSomething: (shuffledArray: any): TransferDescriptor => {
 // Same as above
 const numberArray = Array.from(new Uint32Array(shuffledArray));
 const result = doYetAnotherThing(numberArray);
\n\
 const serializedResult = serialize(result);
 return Transfer(serializedResult.buffer, [serializedResult.buffer]);
 },
};
\n\
export type ExampleWorker = typeof exampleWorker;
\n\
expose(exampleWorker);
`}
</HighlightedCode>

With this final piece of duct tape applied to my leaky code, the program’s memory usage hovers around 1 GB with twelve worker threads.

## <AnchorHeading heading="Closure" />

The end result is a script which can employ multiple workers, each picking away at the dataset. Running the program on 1,000,000 values with one thread takes about two hours and forty-five minutes to complete. With twelve threads, it takes about forty-five minutes, roughly 3.5 times faster. A solid gain, but also indicative of other efficiencies that can be made in the statistical test implementations themselves. Retrospectively, opting for convenience and familiarity in using Node.js might not have been the best choice—perhaps another language with multithreading idiosyncrasies would have provided a better overall experience. However, that investigation is for another time and possibly another post.

The code snippets in this post omit a lot of detail in my worker thread usage. If you would like to see how it actually all works together, feel free to check out the project's [source code](https://github.com/zaljubouri/iid-tests).

Multithreading can be complicated; here are three mistakes I made trying to incorporate it into a Node.js project using threads.js.

Pitfalls of adding multithreading to a Node.js project using threads.js

Lacking the time and desire to play video games as much as I used to, I often turn to [Twitch](https://www.twitch.tv)—a streaming platform largely focussed on gaming—to satiate the part of me that still finds the hobby enthralling. Watching someone else play games on my behalf is a passive affair, requiring a lot less effort and dedication while still being exposed to some of the story, competition, and atmosphere that gripped me in my formative years.

One of the most notable features of Twitch—which arguably keeps it ahead of its competitors—is the chatroom attached to every channel. The variance between each streamer’s community is vast, and I’m almost certain a PhD could be completed (maybe it already has) on the different psychological and sociological components that drive Twitch chat. However, this will not be a thesis on what factors cause an individual to systematically copy and paste the [exact same message](https://en.wikipedia.org/wiki/Copypasta) as a fellow chatter. The interest and focus of this series is less about what causes someone to send a message and more about when, or rather the inability to determine exactly “when”.

## <AnchorHeading heading="The meaning of random" />

It’s quite commonly understood amongst programmers that when they utilise something like JavaScript’s `Math.random()`, the number that’s returned is not truly random. But true[^1] random number generation certainly exists in the computing realm, prominently `/dev/random` (and its siblings) on Unix systems. Since pseudorandom number generators (PRNGs) are essentially a series of arithmetical methods which allows anyone, given the seed, to work out what the output would be, the (extremely well-known) secret behind generating unpredictable values is in how the seed is derived. In the case of the aforementioned `/dev/random`, environmental noise collected from device drivers is the source of these random seeds.

It sounds like a chicken-and-egg problem—to get random numbers, you need random numbers. Why do we need PRNGs if we can get random numbers straight from the source? Simply because we need a lot of numbers, of varying sizes, all the time. Relying on entropic sources where you don’t know when you’ll next get a random number is incredibly inconvenient, and though you can estimate the size of the data your source is emitting, it’s not guaranteed. Instead, using these values as a seed allows you to generate as many numbers as you like, up to a bit-size defined by the PRNG, with relative confidence that your output is still unpredictable by malicious actors.

What does all of this have to do with Twitch chat? As alluded to earlier, the exact moment a person decides to grace the chatroom with their presence is not determinable. Could something as simple as the time between messages prove to be a strong enough entropic source to generate truly random numbers? It would be the first time Twitch chat is used for something good.

## <AnchorHeading heading="Deterministic random bit generators" />

The [National Institute of Standards and Technology](https://www.nist.gov/) (NIST), an American body, provides recommendations on deterministic random bit generators (DRBGs)—which is what they call PRNGs—as well on what is considered a good source of entropy[^2] used for random bit generation. They’re called “recommendations”, but if you want NIST to approve your newly-created DRBG, you must follow them. This won’t be an exercise in creating a cryptographically-secure DRBG to be assessed by the US government, but it would be interesting to run some of the statistical tests used to determine the quality of an entropy source against a Twitch chat-derived dataset, and eventually use the noise to power a random number generator.

The first set of statistical tests are used to determine whether the entropy source is independent and identically distributed (IID); whether each number has the same chance of occurring as the rest, and is mutually independent. This involves permutation testing on a dataset of at least 1,000,000 numbers using eleven different statistical tests[^3].

<Figure id={1} title="A frequency scatter plot of the time between Twitch chat messages in milliseconds.">
 <ImageModal src={"../images/entropy_emissions.png"} 
 alt="A frequency scatter plot of the time between Twitch chat messages in milliseconds." 
 title="Entropy emissions makes it sound cooler." 
 />
</Figure>

To gather the 1,000,000 numbers, I utilised [`tmi.js`](https://tmijs.com), a JavaScript package that connects your Twitch account to a channel's [IRC](https://en.wikipedia.org/wiki/Internet_Relay_Chat) using `WebSocket`. Twitch’s API provides a list of live streams sorted by viewership, which I pass to the `tmi.js` client and on successful connection, events start firing when anyone sends a message in those chats. My choice of (hopefully) random variable was the time between messages in milliseconds. The chart in [**Figure 1**](#figure1) depicts the resultant dataset as a frequency scatter plot; it’s quite clear that the distribution is not identical. Regardless we will run the data through the IID tests detailed by NIST.

<Figure id={2} title={<>Output from <code>iid-tests</code>.</>}>
 <center>
 <HighlightedCode language="typescript">
{`
┌─────────┬────────────────────────┬───────┬─────────────┬────────────┐
│ (index) │ testName │ pass │ counterZero │ counterOne │
├─────────┼────────────────────────┼───────┼─────────────┼────────────┤
│ 0 │ 'EXCURSION' │ false │ 0 │ 0 │
│ 1 │ 'NO_DIRECTIONAL_RUNS' │ true │ 237 │ 6 │
│ 2 │ 'LEN_DIRECTIONAL_RUNS' │ true │ 3994 │ 5944 │
│ 3 │ 'NO_INCREASE_DECREASE' │ false │ 0 │ 0 │
│ 4 │ 'LEN_RUNS_MEDIAN' │ false │ 1 │ 1 │
│ 5 │ 'NO_RUNS_MEDIAN' │ false │ 10000 │ 0 │
│ 6 │ 'AVG_COLLISION' │ false │ 10000 │ 0 │
│ 7 │ 'MAX_COLLISION' │ true │ 46 │ 13 │
│ 8 │ 'PERIODICITY' │ false │ 0 │ 0 │
│ 9 │ 'COVARIANCE' │ true │ 231 │ 0 │
└─────────┴────────────────────────┴───────┴─────────────┴────────────┘
The data cannot be assumed to be independent or identically distributed.
`}
 </HighlightedCode>
 </center>
</Figure>

I wrote the tests following pseudocode set out in NIST SP 800-90B as an [npm package](https://www.npmjs.com/package/iid-tests) to be used with `npx`. I published it to npm mostly to see what the process is; I don't believe there's significant demand for IID test suites written in JavaScript. The dataset is run through the tests, giving a base set of results. It’s then shuffled 10,000 times, the test statistics calculated for each permutation, and these results are compared against the original set. Counter zero increments when the permutation result is greater than the original result; counter one increments when the permutation result is equal to the original result. If the sum of these counters is less than six, or counter zero is greater than 9,994, then the data is not IID. I didn't find this super intuitive, but essentially these tests are trying to check that when the dataset is shuffled, it should give largely the same statistical results as we had originally. As predicted, [**Figure 2**](#figure2) shows that my entropy source fails to meet the IID claim.

This does not mean the journey is over, only that estimating the amount of entropy emitted will be harder.

## <AnchorHeading heading="Entropy estimation" />

Entropy estimation involves determining how many bits per byte of your noise source emissions can actually be considered entropic, so that your generator can make an informed decision on whether it can safely reseed and ensure the output remains unpredictable. This is regarded as the most challenging and important part of creating a truly random number generator. NIST SP 800-90B also assists in this regard, providing ten different ways of estimating your source's entropy.

If your data is not IID (like mine), then you are supposed to run all ten estimations and take the minimum value as your source’s entropy estimate. There is a lot of commentary on whether these are [truly suitable](http://www.reallyreallyrandom.com/photonic/technical/90b_latest/) for non-IID sources.

Due to this uncertainty—and my penchant for writing statistical tests fizzling out—I opted not to run the estimations. This proposed random number generator is supposed to be a sojourn in the world of computed chance; I am confident every bit of my source will be pure entropy.

The next part will detail how the generator is built to achieve our ultimate goal—random numbers courtesy of Twitch chat.

[^1]: True enough for any and all random number needs.
[^2]: Entropy in this series refers to [Shannon entropy](https://en.wikipedia.org/wiki/Entropy_(information_theory)).
[^3]: These eleven tests are defined in [NIST SP 800-90B](https://doi.org/10.6028/NIST.SP.800-90B).

Zaid
Al-Jubouri

Blog|

Using Twitch chat to power random number generation — part 2 of 2

Pitfalls of adding multithreading to a Node.js project using threads.js

Using Twitch chat to power random number generation — part 1 of 2

ZaidAl-Jubouri

Blog.css-dd1yji{opacity:1;-webkit-animation:blink 1.5s step-start infinite;animation:blink 1.5s step-start infinite;}@-webkit-keyframes blink{50%{opacity:0;}}@keyframes blink{50%{opacity:0;}}|

Using Twitch chat to power random number generation — part 2 of 2

Pitfalls of adding multithreading to a Node.js project using threads.js

Using Twitch chat to power random number generation — part 1 of 2

Zaid
Al-Jubouri

Blog|