Lacking the time and desire to play video games as much as I used to, I often turn to Twitch—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 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”.
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 true1 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.
The National Institute of Standards and Technology (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 entropy2 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 tests3.
To gather the 1,000,000 numbers, I utilised tmi.js, a JavaScript package that connects your Twitch account to a channel's IRC 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 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.
┌─────────┬────────────────────────┬───────┬─────────────┬────────────┐│ (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.
iid-tests.I wrote the tests following pseudocode set out in NIST SP 800-90B as an npm package 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 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.
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 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.