The Mess Detector – Cracking RNG with Redstone

All right [Applause] Thank you foreign Foreign Uh today we’re going to be showing you the mess detector we’re very excited about this it’s been a few years yes Earth computer how did this start okay so this started with uh the fastest XP farm believe it or not in 1.12 when there’s the latest version

So that was the dragon farm and the limiting factor in the dragon farm was being able to sort XP orbs by how big they were and there’s no way to do that um directly so what my idea was was to basically sort them by uh predict predicting yeah predicting

The RNG which uh which decides Which Way each XP orb Falls right if you can predict which way the bigger orbs fall for then you can uh you can just get uh the bigger orbs or a higher proportion of bigger orbs and send them to the player and then you

Get more XP and you have theoretically the highest speed XP farm in 1.12 right so around this time uh on my end of things I was thinking a lot about seed finding and I was thinking a lot about applying a branch of mathematics called integer linear programming to

Seed finding I had this new and cool methods like sort of floating about on how to crack these random number generators efficiently and so Earth computer came to me and he asked Matthew you know I went on crack math.random and he outlined a rough plan

On how to do it and we kind of decided that wouldn’t work but you know after like a few days back and forth we had an outline for this device but it was massive it was absurd but the thing is is that we had an explicit plan written down

And once that had happened the train sort of yes yeah so we built the device right it cracks the relevant random number generator the relevant random number generator we should say is what’s called math.random uh it’s a random number generator which Java itself provides you and Mojang uses math.random

For random numbers in a lot of diverse places in the code it’s sort of sparse it’s all over the place it’s like in particle code it’s in TNT code and it’s in these XP orbs now so early on when we were building this device uh sort of a name for the device

Caught on which initially is a joke and so you know we have this device it cracks it’s it hinges upon being able to crack and predict math.random but if you eat something that calls math.random so that would break the device so while the device is breaking you can’t eat it’ll break it but

You know that that’s not a bug that’s a feature so this is an interdimensional Aiming detector yes this is the mass detector yeah so the dragon farm thing was hard like it would take a device about this size to actually then predict the orbs fast enough and it would be very laggy

So that that never happened but so instead theoretical fastest and and come on interdimensional eating detection that’s what we got look at that I mean you know you can you can try and sell this is like oh it’s a proof of concept that we can simulate and crack

RNG in game no this is an eating detector this is an eating detector that’s its purpose I don’t know why you’d want more so welcome here here’s how it works or something when you’re faced with a problem like this we so we we now Earth computer when

He first came here with this problem this question was like okay we have math.random we want to measure it somehow recover the internal state of the random number generator and then uh reverse that and then you know use that to predict stuff but that’s less important the important question though

Is how do you measure this random number generator in such a way that you can reverse it back to the internal state and it turns out sort of the limiting factor of that kind of problem is how precisely you can measure the random number generator and math.random has some good options

For that but nothing is amazing we eventually settled on if we come down here to the TNT cannon so we eventually settled on this schema for measuring math.random in the middle we have this 360 TNT canon and this fires a piece of TNT and this goes out

On a random angle you know between well zero and 360 degrees if you measure it like that but it it’s completely smooth it can take on any angle even fractional ones and uh the point is the more precisely that we can measure the angle this TNT exited the more we know about math.random

And in terms of information the internal state of math.random contains uh 48 bits of information okay so how much information do we get from a TNT shot like this well you know if you imagine this thing firing the TNT will fly out to Somewhere Over Here Earth

So if we come out here all around this this is a circle of radius I think 120. it’ll land on one of these like 5 000 under chests around the edge and we have these observers and there’s tripwire underneath them and these observers serve as TNT detectors

Uh so there’s I think 780 of these observers all around a ring so what that translates to is that we can measure about um we can measure the TNT angle to a percentage of about I think eight bits of information that’s seven points just to clarify

Um the reason the circle’s so big is that we need to measure the TNT’s angle as precisely as possible and even a deviation of the angle by a half of a half a degree uh is is when the TNT has laughed about but sort of makes a difference of like one entire block

Um so yeah that’s that’s why the circle’s so big you know if you go to my channel you can learn about the nitty-gritty of the maths that make this thing work if you imagine a TNT approaching uh one of these detectors it’s gonna do like it’s it’s highly unlikely to just

Land on exactly one block it’s gonna sort of do some funny things and it’s going to slide between two uh two of the strings or even three of the strings and we have to convert that sort of messy physical incarnation of of TNT sliding uh into into just a number that we can

Work with or just a single detector so these detectors here like maybe multiple them will trigger multiple of them will trigger um they will go down these uh these Rail lines here and then here the first step is a pulse extender so this may not look like a

Pulse extender but it is a pulse extender uh one wide pulse extender um and so this sort of redstone flash here will turn into a longer flash obviously um and then what you have here is a d flip flop so this is on a global timer and basically it takes after the TNT

Fires or something uh basically the signal will be allowed through uh otherwise the signal is just not allowed so and it won’t do anything all right so this all of the detectors that did fire basically will get a signal through at this exact time uh because of the pulse extender that

Um the signal will be actually coming through at the time okay and then you’ve got here you’ve got the uh the signal deduplicators so what this does is if there is a detector um on this triggered on the left of the current detector then the detector won’t trigger so for

Example if uh if this detector here triggers and this detector here triggers then this part of the device here will block the signal from the right hand side one so what you actually get is the leftmost detector will be the one that uh that gets its signal uh going through

And maybe maybe worth a comment that’s why we have this ugly circuit over here because our detectors are laid out in a circle um but over here we have to have because the detectors come off the circle in these four directions we have to have these ugly little uh ways of doing this

Circuit around a corner yes it is the corner cases um but yeah ultimately the point of this is we just need a consistent way to assign a detector to a measurement and we could have chosen a number of ways but this way standardizing the time where the measurement is taken and standardizing

Um that we always take the leftmost detector that got triggered so now we gotta you know we have a pulse at a detector we now know which detector fired and we’ve got to turn that into a number which uh my algorithm can use and so what we have here is actually a

Big lookup table so in these observers in Sandstone we’ve encoded some binary uh information and what this represents is this represents the top 10 bits of I think the largest seed that would have triggered that detector is how I think this works yeah I think that was it um

And so the point is is that you could you could record All 48 bits uh but there’s the math doesn’t there’s a lot of uh redundancy built into the algorithm uh for other reasons and here it lets us get away with only storing 10 bits of a 48-bit seed but they’re the most

Significant ones so we take we take these uh 10 bits and we actually fire seven shots of TNT out of that Central can so that’s 10 bits of information from each one roughly and like I said you need 48 so you can see that we’re really well past

That 48-bit Mark there’s some loss elsewhere in the system but this is plenty of information the one question is how do you actually recover uh the internal state of a random number generator from just this information of the seeds which actually got fired Out The Observers here they will activate

And they will trigger these budded Rail lines and turn them off um if that if there is an observer underneath otherwise the the rail underneath triggling won’t do anything to the veil line and then it comes down to here so down here this just converts it into hexadecimal um

And the hexadecimal system gets shot up through these funny comparator lines um up to this circuit so this circuit looks very large it’s the big boy yeah what this is is we measured seven shots of TNT and that gives us a vector of these seven measurements which you

Know our lookup table recorded so we have a vector coming into this Circuit of seven numbers and if you go through my videos and you look at like what my algorithm is actually saying um in this instance what we’ve done is we’ve pre-computed a 7×7 Matrix and essentially multiplying this vector

By this Matrix gives us something very very close to what we want so all that this circuit is you can see how there’s sort of seven different um paths through it um those are like seven columns in a uh 7×7 Matrix so like that’s the global

Scope of what you’re seeing here uh so we can maybe talk a little bit about how an individual multiplier works yeah so uh as a a number comes up through here um you can see that this number gets distributed out to all of the different um cores here and let’s just pick the

Top color why not um you have what you actually have is a is a hard-coded value here which we’re going to multiply that number with so we have a c and we have a four um and that number will come round uh in here and be multiplied by that number

Um for each TNT shot though is a different number that each one’s going to be multiplied by yeah it’s a DOT product really yeah so um yeah and the number is then multiplied by by this thingy thing here uh this is a 16-bit multiplier

Sorry I think this one I think we cut it down to 12 for some reason but we didn’t have to do that but it was originally a 16 bit one oh well okay yeah but it okay so it’s a 12-bit multiplier then um and coming out the back here so one of the

Disadvantages of this multiplier is we couldn’t make it uh handle negative numbers all right so what we so our Matrix that we’re multiplying this input number by it has negative numbers in it so what do we do about that well what we do is we multiply it by the

Positive version of that number and as you know um as you should know um well the input is always positive so you’re either multiplying the positive number by a positive number and you will get a positive number out so then the the multiplier already does the right thing but if you’re multiplying a

Positive number by the negative number here you’re going to get the positive version of the result that we then then need to make it into a negative number so for example 2 times minus 4 is minus eight but this multiplier would give us 8 so we need to then convert eight into

Minus eight so yeah that’s what uh that’s what this contraption here does so what we have here is a piston feed tape here um this uh encodes whether the value in The Matrix is positive or negative I think the cauldron means negative um and if it’s negative then what we will um well

Um with a little asterisk here uh what we will do is negate the number um and if it’s positive then we will do nothing to the number so then what we get out is that is the real result of the multiplication now yeah we aren’t actually negating the number

Because negating the number is hard but just to interject red CMD built this multiplier for us thank you so much red CMD it’s not red cmd’s fault this multiplier couldn’t do negatives or whatever it’s I think it’s sort of related to that thing where we cut it

Down to 12 bits or something but we got we got the we had the device pretty built they’re like wait there’s negative numbers for whatever reason this is a problem and then I think I like came up with this insane plan to staple on these signs to the I’m sorry red CMD your

Multiplier would have been able to handle negatives we would have been able to do two’s complement we just We’re In Too Deep this is just a complete that this was stapled on to another one with sign extension but yeah yeah yeah something like that like we need

The output to be a certain number of bits in the input and so it needs to be filled up with ones up top yeah okay so what um what you can do to negate to do something very close to negating a number is you can just flip all the bits in the

Binary representation all right um and so that’s what this does here um flipping all of the bits in the binary representation of the number actually ends up being one out one off from the real negative version of the number if in two’s complements so what we then do

Is because this this Matrix is hard-coded and we know exactly how many negative numbers there are in it we know exactly how far off we will be and so we can then remember that error for later all right yeah but anyway this pink circuit is where the

Um is where the seven TNT shots get combined into one number in each chord uh it just adds up the outputs of of the multiplication and then it’s adding on another magic constant here uh and it’s doing that by so this is a cumulative Adder uh just it just keeps a running

Total of the of the uh the numbers that come in uh but we’re not initializing it to zero as we would normally do because we want to add a constant so we initialize it to that constant and this magic constant is where we store the offsets from uh the the error offsets

From the negation along with a couple of other constant errors from the entire yeah along with another magic value which already comes from the math that we need to add on yeah and I’d also call that one an error there’s sort of this error coming from the fact that the um

The r the random number generator adds 11 it doesn’t add zero so there’s an error term coming from that there’s an error term coming from these minus signs there’s an error term coming from the fact that we only store the top 10 bits of the numbers and there’s an error term

Coming from the fact that at the very end um the dot product that we do at the very end of this whole process should also have a constant added to it but I didn’t want to do that so I put that I pulled that constant all the way back

Through the math and added it here as well and there’s another error too concerning like negation it these are the most disgusting magic constants ever like every time I’ve tried to explain them I’ve remembered a new thing which these things get eaten up in it’s the single worst piece of code I’ve ever

Written all right so there’s this next bit of the circuit this is a right shift by 10. so what what that means is it um divides this number by 2 to the power of 10 which is 1024. yeah it is ten um so sort of the reason behind this is if

Okay I mean we’re gonna have to go watch my video but roughly we’re exploiting the fact that the the vector of the TNT angles falls on what’s called a lattice and the Matrix that we’ve multiplied by you can describe a lattice with the Matrix and the Matrix that you multiply

By is roughly the inverse of that Matrix describing your lattice is what’s relevant to this process and when you invert a matrix you get a determinant coming out in the formula and very roughly that determinant here means that we should be dividing by 2 to the 48. so

Okay but here we’re dividing by 2 to the 10 where the other two to the 38 go right because I said we’d need to divide by 2 to the 48. well it’s in the constants that we store down below so we only store the top 10 bits of each seed

That’s like storing the seeds divided by 2 to the 38 and then floored so this is where the other um uh two to the 10 goes so we’re really dividing by 2 to the 48 and 2 to the 48 is a very natural number because the

Internal state of these rngs is 48 bits but that’s why there’s 10 it’s because we stored 10 bits down below and we have to do the rest of that division so we’ve stored enough Precision to like do the part of the multiplication that matters we’ve divided out by stuff that

Can’t affect the final output yep but uh yeah yeah and so this uh this shift right by by 10 just divides by 2 to the 10 and then floors it that’s what it does uh it’s much easier to divide by powers of two uh in binary than it is to

Divide by some magic number so that’s why this circuit is so small um and then it goes through this spaghetti yes this uh all the output gets transferred down to here and they all get accumulated through here we we bullied a number of our friends into helping with this wiring oh yes and

There were a couple of issues where they were wired wrongly but they were uh fixed at the end is there another Court door still here look it’s there yes so this was an instance where it was wired wrongly yeah this this was like the last thing wrong with the device

Like we had to track down but like this line was missing that’s why it’s a different type of block and then it comes through here I don’t remember what these uh these piston things before oh it’s very simple um we accumulate uh seven outputs right so we’ve we’ve

Dotted we’ve multiplied a vector by a matrix so we’ve gotten out a vector and the next step in the algorithm is to dot that Vector with a constant over here and so what these Pistons are doing as long as I guessed correctly because you’re invisible right now but with

These Pistons out of the green circuit are doing um is there in charge of that dot product they’re they’re in charge of making sure that the value currently being read is the correct term in the dot product yep so you just take the I don’t remember

Which way around it goes but you could take the the Top Value here first um and then multiply it with the Top Value from over here which is huge as you can see it’s it’s uh this is a 48-bit value yep okay and then it goes through this

Thing this big boy here this is a 48-bit multiplier thank you red CMD so much yes there’s actually a funny story here right because we are building this device we had the circuit laid out you and I are not the best at redstone this that that’s not our Forte like you

Did all the programming and I did the math and then we’re like now the Redstone is Trivial and then the Redstone took four months or something like a thousand man hours um so bless red CMD for making this 48-bit multiplier when we were waiting

On him we were like yo red CMD we need a 48-bit multiplier while we were waiting on him he took a while right you know guys busy so I took it nothing’s complicated as well look at it so so I took it upon myself I took the 16-bit multiplier he’d already given

Us and I stapled together I think six of them yeah to multiply it naively like in like it’s in base 2 to the 16. and I built this thing which covered 200 like a square of like 200 by 200 blocks is the single worst thing you’ve ever seen it was so

Slow and massive and then like I pasted the image of this and red CMD had this thing built like in like a week he was just like no yeah we’re not using that abomination and then he made this beautiful beautiful serial 48-bit multiplier which I still don’t quite understand

Actually initially he made it 64-bit and then we gave it another haircut for some reason all right um the final step here is the output of this 48-bit multiplier goes into another cumulative Adder which we’ve already we’ve already had one of those up there yeah this one’s a 64-bit

Oh my goodness it’s not haircut no the the this it’s a member of The Beatles it’s Shaggy okay um this is uh this is the the should be a 48-bit multiplier but sorry 48-bit cumulative Adder uh but we were too lazy to do that so it’s a 64-bit one

And motor it’s not using some of it okay so the output of this uh Believe It or Not ends up being the seed so that ends up going to this uh seventh to these uh 12 7 segment displays here these are hexadecimal seven segment displays so Matthew went

In and well he’s he stole a uh uh base ten seven segment display and added yeah I think six digits to them yeah I think I stole it from my Zuma games thank you thank you thank you for your uh free work um yeah although I will say your circuit

Was annoying to adapt for hexadecimal you should have thought about that you’re welcome SMH all right um hold on I wanted to say something oh yeah yeah so we’ve sort of gone through the math now which cracks the actual seed I just want to comment because if

You go and watch my video to understand like why on Earth does multiplying by this random Matrix work you know how does the RNG work all that stuff if you ask if you have those questions you can watch my videos and you’ll get most of those answered but there’s still something which isn’t

Answered which is that at the very end of my video series I suggest that a final step uh is a sort of a linear programming step I say something where like you have a polytope in seven dimensions in this case and you take cross sections and you bound their

Width and then you take cross sections of those six-dimensional facets you get five dimensional things you take you bound those by integers you take cross sections of that and you’re searching for integer points within a polytope and here we have no such thing which looks like that it’s just all you multiply by

A matrix you round down you take a DOT product and you have the seed and sort of the point is that this was the reason for the extra redundancy and the information that we gathered at the beginning uh at the very beginning remember we said we get about 10 bits of

We get oh okay about seven or eight bits of information out of each measurement because some some detectors give you more information so the lower bounds like eight um and you know but we’re measured seven we only needed 48 bits seven times eight it’s larger than 48. and so the reason

For that extra uh redundancy is that it’s so over determines the seed that the search process that I describe at the end of my video every bound has only one integer it could possibly be so basically we can round we can just round to the nearest integer Point roughly or

In fact we’ve even arranged it here so that the nearest integer point is always when we round down we’ve made sure the air are always overestimates rather than underestimates yeah and so in this way we can dodge the disgusting linear programming Loop we can dodge like ever saying the word Simplex algorithm or

Whatever linear programming method you prefer our polytope is just so small our seed is so over determined that just rounding to nearest is guaranteed to find the integer point that actually lies inside the polytote yeah and the bounding is mostly done by that division

By uh by two to ten pi over there okay exactly so so let’s talk about the orthogonalizer 3000. ah the orthotic I think it’s sort orthogonalizer five thousand so like I said we’re trying to get this detector really small right it may not look like it to you but

This circle is quite small for what this is doing and so uh one way to get the circle smaller is to make each TNT shot give you more information about the internal uh state of the random number generator naively uh if you just take seven TNT

Shots in a row without doing anything in between there’s actually going to be some correlation between how those exit the Canon uh you won’t get the full eight bits out of each TNT shot um so but what you can do is in between each TNT shot you can call math.random a

Bunch of times so that the TNT shots are less correlated so what that means is that observing a new TNT shot is more like observing an independent event and you get more bang for your buck you get more actual information about the internal state for what your measured values were

So this this lets us shrink the circle by a diameter of about I think 20 or so blocks uh because and yeah and geometrically what this is doing is the lattice that we do lattice reduction on the um uh The Matrix that we invert by it the columns are closer to orthogonal that’s

That’s the main point of this so okay we have the seed now so what do we do with the seed so for the longest time the device was like in this state where I could crack the seed then it didn’t do anything the seed goes along two paths one way it

Gets stored over here around this area um that’s what this line is doing and then the other direction goes down here and so you can see this is a copy of that 48-bit multiplier that we have over there and all this does is this is a Java random simulator basically well it

Simulates uh 30 000 or so calls to Java random it’s possible to jump forward that much um but it it simulates exactly the number of calls that the mess detector does whenever you press the button so whenever you press the button this thing the lightest orthogonalizer gets called

Seven times at five or seven shots of TNT and maybe some other stuff happens but at the end of the day it does a certain number of calls to math.random and this circuit here is just Java random but repeated that many times um is mathematically what it is in in

Practice it’s just a one multiplication in one edition and so the output here multiplication multiplier here addition is here another copy of the adder from up there yeah and so the result of this is that we have stored um the predicted value for the next time

That we call that we press the button so over here we get stored the next time what we expect the next time we run the mass detector and so if they agree that means that no math.well or a multiple of 2 to the 48 calls to math.random uh occurred between the two

Button pushes but if they disagree that means something somewhere outside of the mesh detector has called math.random and so the result of this is that our device no longer does nothing it is now an interdimensional eating detector yeah so if you have a player anywhere in the

World you know it could be another dimension you know out at the world border and they dare to eat the game will create crumb particles causing a massive mess and this massive mess will affect math.random which will now be 46 call 46 calls more advanced than it should be oh

Dear and this device you can’t escape big brother it’s watching you it it knows when you’ve eaten I hope you enjoyed the uh the machine if you want to build this in your world then there will be a World download uh it doesn’t oh wait wait yeah it doesn’t work on single player

You have to do this on a server don’t let it rain on the device it doesn’t work if there are any mob spawning algorithms happening so either turn off mob spawning which would be cheating which is what we’ve done here or have four mob switches in the world

It does work yeah in fact you need more switches in every Dimension I believe yeah although I think it works if there’s no players in the other dimensions yeah and players can’t switch Dimensions that doesn’t match that random call yeah no players can’t mention players can’t log on oh yeah that

Doesn’t matter random call yeah no logging in that’s naughty and messy yeah you can’t like Place water in the Nether and like get those particles at those calls you can’t take items out of a furnace and get XP no creating XP you can’t throw an item on the ground oh

Dear yeah that’s very messy no no creating TNT yourself leave all the TNT creation to The Meta detector where it’s safe and contained yeah exactly all right um what else is there no creating uh obsidian with uh mixing liquids or mixing liquids in any other way like you

Can’t even you can’t even load a chunk with an entity in it like make sure that if you if you have entities hanging around don’t load chunk like you can’t create an entity entities can like exist and hang around but yeah and you can’t by the way we

Should mention because it’s funny you can’t do this on single player because on single player um they’re both client-side particles and server-side particles use the same random number generator so every single player but yeah that uses it yeah but most saliently I think every single Redstone particle would call meth.random

Which would throw everything wildly off and like it does thousands of calls per tick or something anyway yeah let’s not let’s not get into that so and one final thing one final thing the mess detector is a parkour course yeah you can get to the top of the the

Highest block of the mass detector from the platform using parkour however I’m not skilled enough to do it uh but yeah if you want to build this there’s a world download only works in 112 no 113 plus shenanigans um but let’s let’s just say it doesn’t work

In 13. it definitely doesn’t work in 14. okay yeah this is the mess detector and this is well I am Earth and this is Matthew here hello I’m Matthew Bolin hi Matthew I’m Earth computer and this is the mess detector so [Laughter] it’s Mass detector time we’re doing this

Yeah don’t even stop the recording studio I haven’t stopped the recording uh Wow Let’s computer Earth computer I’m left with the burning question what is math.random uh it is a random number generator used by the game before stop laughing hello everyone this is our machine that we built to detect when you eat

So hello everyone I’m Earth computer are you sure you sure about that there was a theoretical well that there was a fastest XP farm in existence and that was the dragon farm the dragon farm was giving you so much xp that the limiting factor was how fast the player

Can physically take in XP um the player can take in 10 x peoples per second uh so what you want is for the X people to be as big as possible but the problem was that there was no way to sort XP balls at all yeah the dragon has six

Balls but only two of them are large yeah we and we need the dragons two big balls [Laughter] they’re called orbs laughs I didn’t think of that word so normally you think about a dragon in terms of it’s dropping is egg but it also drops

And we are after those two big boss my eggs are dropping listening to this oh professors get back here right oh Yeah that’s that was there for a reason I seem to remember I don’t remember what it was though oh it’s because it’s to not power the Piston like you see that was it but doesn’t that okay could you imagine the Piston was a block up it would be powered through a full lock

Here and that’s a problem because of Randomness and dust update order like if this was to turn off before this one the Piston could get stuck on powered oh okay I’ll believe you that’s that’s the reason all right great that’s one block explained more than three thousand like a hundred

Thousand there’s three hundred thousand snow slabs down there every single one of them you know if you go to my channel you can learn about the nitty-gritty of the maths that make this thing worth um I’m sorry I I paused for a second there just because I said maths and I realized

That your britishness is rattling off of me on me yes Anyway come over here look up table look up table time but um actually no before before we talk about any of this so let’s talk about the orthogonalizer 3000. ah your thought a lot I think it’s an orthogonalizer

Five thousand was it oh I think I’m pretty sure it was three thousand I’m pretty sure it was 5376. um because we didn’t we do have it written down oh boy how many days do you think I got right chat take your guess right now three or four digits right

It’s been four years I’m allowed to forget a digit in four years so it’s 5394. damn it which is 2 697 master of random calls no other way oh yeah yeah okay so maybe we’re both almost right damn it yeah but what do you call it I need to know now

Wait that doesn’t make sense there’s a TNT that gets dropped it should be odd yeah it’s yeah the number of math random calls is odd but you’ve got a times about two because each math.band does it Advance it twice yeah but items do four calls okay yeah uh

Okay I’m gonna have to search the channel for orthogonalizer okay all Earth computer is doing that I’ll just mention the point of this um so like I said we’re trying to get this detector