[00:00] a man holds his phone up to a slot machine He played a few rounds. He won some, lost some, and then he got up and walked away. [00:13] but now he was winning on spin after spin. of the casino roughly $10,000 richer. [00:28] and California saw the same thing. and then leave, and minutes later, they would return Investigators were brought in, [00:42] they all seemed to be working fine. and they noticed something strange. they didn't play like normal gamblers. [00:56] They'd hover their hand over the spin button, wait, as if they knew when to press to win. Perhaps there's some way to predict what was coming next [01:11] by a computer inside the machine. but the casino provides an ideal venue because theoretically, that computer uses a [01:26] So are those numbers actually random? to connect finding diamonds in Minecraft to the development of the entire digital world. [01:42] of creating true randomness. that chance plays a surprisingly important role in [01:54] It works something like this. Take a core of uranium-235. When a neutron hits a U-235 nucleus, it can cause the nucleus [02:06] or three more neutrons. Now, if on average each split triggers more than one more split, you get a runaway chain reaction. [02:19] those neutrons take. or does it bounce off or get absorbed By 1945, [02:32] of each of these events happening, speed and what it was passing through. and trillions of neutrons, [02:47] to calculate one by one. was Stanisław Ulam. But then one morning in January 1946, Ulam woke up [02:59] It was encephalitis Luckily he survived, but his recovery was slow. So he spent weeks in a hospital playing a lot of solitaire [03:13] of winning a game? but a deck of 52 cards can be shuffled in 52 factorial ways, [03:25] of 67 different arrangements. Now, Ulam spent a lot of time trying to work out the answer But then he had a much simpler idea. [03:42] to lay it out, say, 100 times and simply observe That would give him some sort So say you win eight games out of a hundred, [03:58] of winning are probably around 8%. idea, but for neutrons. he could just start with a hundred neutrons [04:13] So say a neutron hits an atom. or a three, it bounces off the nucleus. If I roll a four or a five, it causes the nucleus to split. [04:26] And then I just follow what happens to that neutron that it produces using more random numbers In the real simulations, the scientists used probabilities [04:41] corresponded to which outcomes. or direction could also change. for its new situation. [04:54] and then they kept following what happened. how all those interactions added up. the chain reaction takes off. [05:08] But if more are lost than are produced, it fizzles out. So by simulating just a tiny fraction of the possible paths reaction would behave. [05:21] by hand seemed impossible. and Los Alamos advisor, John von Neumann, had been working computers, the ENIAC. [05:33] how it could follow 100 neutrons of collisions in just five hours. what would happen to a neutron. [05:47] they used books of random digits like this one. And the ENIAC didn't have nearly enough memory So von Neumann came up with a surprisingly simple way [06:02] for the ENIAC to generate its own random numbers. So the way we're going to do this is I'm actually going So let's try with 2,137. [06:19] and 2,137 squared is 4,566,769. but to do that first, I have to add a zero to the front [06:35] I won't use the digits at the edges So the last two digits only depend on the end of the seed because 37 squared ends in 1,369. [06:49] So anything ending in 37 squares to something ending in 69. Also, every seed in the 2,100s is going to square So they all start with a zero [07:04] But the middle digits get a contribution from So 5,667 is going to be the next number in the sequence. 32,114,889. [07:23] end, and you can just keep going. but watch what happens if I keep going. [07:37] after 43 steps, I get 4,100, then 8,100, and then 6,100, and then 2,100, and then 4,100 again. [07:52] From here on, the generator will produce these same four and nearly two-thirds of all four-digit seeds end up in this exact loop. [08:08] and once they do, every number that follows is also zero. Almost one in five starting values end up here. value, every single sequence eventually gets stuck in one [08:25] Now, von Neumann knew So for the first ENIAC simulation, so they produced much longer sequences before they looped. [08:39] for randomness by hand, they programmed the ENIAC to restart from the original seed And in the spring of 1948, [08:55] the ENIAC finally ran the first computerized simulations Von Neumann wrote to Ulam, "The results are very promising and the method is clearly a 100% success." [09:08] after Monte Carlo, Monaco, Today, it's one of the most important tools in statistics Now, this sequence of numbers isn't truly random. [09:24] you get exactly the same sequence every time. but that didn't actually stop them from being useful. so did this demand for pseudorandom numbers. [09:40] who considers arithmetical methods of producing random digits is of course in a state of sin. with three major challenges. [09:52] One, sequences could get stuck in these short loops. Two, even sequences that looked random could hide patterns. they could work out every number that followed. [10:04] They were predictable. So you, you got to show me - This is Matthew Bolan, Minecraft expert University of Toronto. [10:19] Minecraft before, diamonds are a big deal. - We're going to change that today. - Every Minecraft world is made up of chunks. [10:33] and 16 blocks in the Z direction. And in our version, each chunk originates at most a single that is hidden somewhere below the surface. [10:48] - So we are looking for either a clay patch What you do is you pull up your F3 screen, [11:00] you locate which direction is positive Z. - Yeah. - And what you do for clay, you add three. [11:12] and we go one, two, three in the positive Z. And now, if we dig down here, unless it got blocked by bedrock or something, [11:25] where it couldn't spawn in, there will be a diamond ore - Let's give it a shot. - All right. - Oh, no way. - Did you get anything? [11:39] - I did. I got eight. - You got eight. Let's go. - Okay. the game uses an algorithm [11:51] where resources like clay and diamonds appear. So I'm going to take a wheel with seven positions. It has numbers going from zero through to six. [12:06] and then multiply by some number. So one times three gives us three, Now, we multiply three by three again and we get nine, [12:20] so we're going to have to wrap around. and that gives us a remainder of two. This kind of wrapping [12:34] And now we keep going. So two times three is six, And then six times three is 18. So we get to four. Four times three is 12. [12:51] Five times three is 15. So what we've done is we've gone through every number except The formula for this kind of algorithm looks like this. [13:06] between the current number and the next, after dividing by m. the values wrap around falling along [13:20] So it is a linear rule using modular arithmetic, of pseudorandom number generators got the name linear [13:32] congruential generators, better known as LCGs. LCGs can produce enormously long sequences In the 1960s, IBM developed one called RANDU. [13:47] and used in simulations of everything from radioactive decay to instruments aboard NASA's Skylab Space Station. before repeating, so at least [14:01] But a long sequence doesn't necessarily mean a good one. consecutive numbers and we plot them If the numbers behaved independently, we'd expect the points [14:17] And from this angle, they certainly seem to, but if you rotate the cube in just the right way, you can see that they actually line up in these 15 [14:31] where RANDU will never place a point, of all LCGs because of that linear relationship. and the third from the second using exactly the same rule. [14:48] So all three numbers are linked by a linear equation. a linear equation describes a plane, and the mod step creates a series of parallel planes. [15:00] that pattern especially obvious, In the 1990s, Java adopted one and a much larger modulus. [15:13] Its sequence takes over 281 trillion steps before repeating. and what we get is this. because they're so closely packed together [15:28] that the points more or less look like a random cloud. So that is problem two dealt with. - Occupational hazard. [15:41] So for most of the game's history, it used Java's LCG to determine the placement of resources in a given chunk. it didn't use completely independent starting numbers. [15:56] and added a different fixed number for each resource. those starting numbers differed by just three. before using them, so the difference wasn't always three [16:10] of a few predictable values. to choose their position were related. the shared unknown part cancels out. [16:25] The location of the clay patch was enough Matthew has a great video on his channel that works through description if you want to go check it out. [16:41] The outputs themselves can reveal enough information See, Java's LCG keeps track of an internal number and this is what Java's LCG uses [16:57] But when it generates an integer output, of those digits leaving just 16 hidden. And since it's binary, each can only be a zero or a one. [17:11] So that's just 65,536 possible values. but a computer can test them against the very next output And then you know the full 48 bit internal number, [17:27] every number that follows. They can produce incredibly long sequences but their simple mathematical structure still [17:40] - Like LCGs, they're, they're not good. They're very exploitable. They're for when you're, and dirty and you're not too worried about people like me. [17:56] work on the most recent versions of Minecraft. - Once I published this trick, it got patched out - Oh, no way. - I think a bug report was made [18:10] What they did is they actually switched the random number to a different random number generator - They changed the whole, [18:24] - Yeah, exactly. You can do the honours. - Okay, okay, okay. Let's see if I can remember. - Oh - Boy. Okay, check this out. Here you go. [18:38] Pants, boots, chest piece, helmet. to put this particular random number generator into the [18:50] when you're building software. Hostinger is an all-in-one platform for building, running, or an online store, you can manage it all from one place, [19:07] So for example, let's say I want diamonds that I just mined. and Hostinger's AI is going to build an initial version. [19:22] And if I want to change something, I can just describe it, because I can also add my own custom code. I can just spend more time mining diamonds. [19:35] and if you go to hostinger.com/veritasium, I want to thank Hostinger for sponsoring this part where gamblers were exploiting random number generators [19:51] to win thousands of dollars. of the gamblers who had been repeatedly winning on slot [20:04] - So when they picked these guys up in California, and they were able to see that the video was actually being - More specifically, a team in St. [20:19] Petersburg, led by a hacker only known as Alex. of its gambling and thousands So Alex got hold of some of these machines [20:32] - There's a processing board, which is a slot machine interface board. the processing board is locked into the game. [20:44] That comes with the machine. So if you can... it's just a matter of time before you're... using an LCG like Java. [20:57] - A lot of them were using the same - This algorithm still starts with a seed, it fills a table of 624 numbers. [21:14] combining the binary digits from different parts of the table to produce 624 new numbers. through another series of calculations, [21:28] and it produces its first pseudo-random output. and the next until it has produced 624 outputs. and the process continues, and its sequence is huge. [21:44] 6,000 digits. But despite all that, every step still followed these fixed that Alex was actually able to work out [21:58] So when his team received videos of spins from casinos in the US, they could work backwards and predict when a winning spin was most likely. [22:13] the random number generator kept running even when nobody at the instant the player pressed spin. So the gamblers had to press at exactly the right time, [22:27] So Alex built that delay into the system. quarter of a second before they actually needed to press, and... [22:43] but a four-person team could reportedly take more than $250,000 in a week, so it was pretty effective. of the scheme were charged with conspiracy to commit fraud. [23:00] while one chose to cooperate with the FBI. exploit in casinos still? - Yeah, I would be completely surprised if they weren't. [23:15] There's a lot of those boxes are still out there. of these generators fail at being unpredictable if you know and if you can study enough of their outputs. [23:27] They're used to protect everything from our messages to our bank accounts, and if those numbers can be predicted, then that security can be compromised. [23:40] and Technology in Boulder, Colorado. NIST sets the standards for secure random number generation, - So what we're trying to do is say, [23:54] that nature allows you to build? - And that's what, that's what this is about. to make the world's best random number generator, really try [24:09] and science to try to develop the best And then we use those measurements to develop standards. for generating random numbers for digital security, [24:25] the ones we've seen so far. different kind of generator. Start with a string of numbers, say just one, two, three, [24:39] of those numbers into an encryption algorithm. which is based on a large random number. that without the key, the outputs look completely unrelated. [24:57] It's the one random number you need to start, and it decides every number that comes out. of its hidden state, and with the Mersenne Twister , [25:11] Here, even if you know exactly how the encryption works, and outputs, there's no practical way And guessing it isn't realistic either. [25:27] A common key length is 128 bits, so that's 128 trillion possible keys. output, it's practically impossible. [25:42] cryptographically secure pseudo-random number generator, But where did that secret key actually come from? nothing on its own, it actually needs [25:58] And for that, computers turn to the physical world. random number generators to provide those unpredictable seeds. [26:13] even uses a whole wall of lava lamps to generate random seeds for its algorithms. So does that mean the problem is solved? Not exactly. [26:25] as a random event, heads or tails. you can actually make the coin land heads every single time, [26:37] of classical mechanics. and how it's flipped, you can predict The French mathematician, Pierre-Simon Laplace, [26:51] He imagined an intelligence that knew the position So according to classical mechanics, - You know, I looked long and hard to try to figure out [27:07] definition of randomness is just something that nobody could have predicted in advance. but like anything in the universe. [27:20] not just to generate numbers that seem random, - We don't want to do seeds at all, because some quantum measurement outcomes are [27:37] - So on this setup right here we start with a very bright of these pulses per second, [27:49] and interacts with this crystal here. with this crystal sometimes one of our [28:01] and fission into what we call a pair of daughter photons. - Now, each photon has a property called polarization, electric field oscillates. [28:17] that the pair can be produced or both vertically, but there's no way to distinguish which. of both possibilities. [28:32] - This is very much like a Schrödinger cat type state, and now it's like they're kind of both - The photons share a quantum state no matter [28:44] In other words, they are entangled. the results are correlated. to two separate measurement stations, [28:58] to get each photon into an optical fiber. - The really hard part is these fiber cables right here, It's only about 10 microns in diameter. [29:12] that's about one-tenth the diameter So it's a very, very tiny target. to call quantum archery. [29:27] and the fact that, you know, you could kind of pull back Yeah. And then it can keep shooting arrows We're doing a version of that [29:42] where now Robin Hood has two targets and he has a single bow and yet he's able to continually keep - Into these 10 micron holes. - Into these 10 micron holes. [29:56] - The photons then arrive at two measurement stations This means that even a signal traveling at the speed to impact the measurement. [30:09] the researchers measure the photon's polarization, angles to measure it at. before the photon arrives. [30:22] and there that gives you that ultimate final random number? A detection gives us a one. No detection gives us a zero. [30:37] to choose the measurements in an experiment that is designed It doesn't make sense. How are these guys random - So you know, it takes randomness to, to make randomness. [30:53] And this whole setup is a way to kind of purify and turn it into something that is like certifiably - The first numbers choose which measurements to perform, [31:07] and ones coming out of the detectors. there are four possible combinations of measurements. [31:19] answers for every possible measurement, stations could be correlated. the correlations exceed that limit. [31:35] We actually made an entire video about Bell tests So we've linked it in the description if you want Because the measurement choices are independent [31:49] during the measurements, that means the photons' results of locally predetermined outcome. So the experiment is actually testing whether those numbers [32:02] But there are other potential loopholes. with was called the Freedom of Choice loophole. gets the quiz ahead of time, knows [32:16] These particles, again, to speak kind of anthropomorphically, before they reach their detectors. And that goes back to randomness really at its core. [32:30] of measurements to perform had no kind - There are a few ways to do this, but David Kaiser - What we wanted to do was turn the universe itself into a [32:44] - They pointed two telescopes at distant quasars on opposite photons arriving from each of the quasars [32:56] Now, that light had been traveling for billions of years, to communicate with each other since nearly the Big Bang. [33:08] any hidden coordination between the measurement choices to happen billions of years ago. but it pushed that possibility much further back in time. [33:25] explanation could account for the results, - If I was a hacker, how would I attack In principle, two people working together could shine [33:38] And control which measurements are selected So NIST has to keep the random number generators used outside interference. [33:52] That makes it much harder for someone to hack the system, of the devices being tested. NIST still has to assume that along with the impossibility [34:06] and distance measurements, and faithful secure If those assumptions hold, then the Bell test can certify the detector outputs contain. [34:21] If we use entanglement, you can do these types that could have predicted what's happening in advance. But the raw measurements aren't necessarily an even [34:34] There might be far more zeros than ones. how much unpredictability is present across millions of evenly balanced, independent, random bits. [34:50] The basic idea is similar as his state of sin joke. If you get heads, then tails, you call that a zero. [35:06] And if both flips match, then you just throw them away. and the bias doesn't change, heads, tails, [35:19] So what's left is perfectly fair. Now, NIST technique is far more powerful, The Bell test certifies at least 820 bits worth [35:34] And then using a mathematical technique called randomness to just 512 bits. that we make contributes to every bit. [35:50] that we've seen throughout the video, Their unpredictability can actually be certified. - Albert Einstein, his argument was [36:05] That's this famous Einstein quote. In fact, these experiments that we do here that show that really, you know, this predictable nature, this kind [36:19] that Einstein espoused really is - Yeah. - So if God does play  And it's this experiment. [36:33] This is the most random source of entropy you can generate. - God's dice are not loaded. Exactly. Yeah. [36:45] nothing in the universe could have predicted in advance. NIST actually publishes this on random.colorado.edu, along [36:57] and verify how the numbers were generated. and I can really use the, the bits that are generated here or a red sweater, and I'll be using these entangled [37:13] to me if you were a red and green sweater, It's like, it takes a lot of equipment. how we actually interconnect [37:26] and these different beacons together and sources of randomness can kind of actually form a layer to randomize is the internet. [37:39] can we just make everything more secure? - Okay. One last thing. Last year we launched the official [37:51] It's a game with 200 questions about science and technology, See, there's a confidence mechanic in the game and 10 on your answer. [38:06] you may lose out on points if you're doubting yourself. and it has been super fun. that it's now available. [38:19] to the Elements of Truth website. and as always, thanks for watching. that... no, [38:36] - No. I don't think I should die. I'll be fine.