Understanding Math-Heavy Code

Transcript

have the understandings needed in order to actually be able to review and audit and follow that code. And in particular, Jeffrey is going to pick on a piece of code from Unisop V3 for that. Um, Jeffrey. >> All right. Thank you so much. >> Sure. >> Okay. So, today we're going to be reading uh this code. Um, all right. Cool. Based on a few reactions, it sounds like we're going to have fun. Um, okay. Now for let me just say that obviously every math uh library is different. The whole point of this talk is just to talk about how can we turn a big scary problem like this into something that's manageable because every big problem can be solved

by making it smaller. So the whole point of this talk is just to talk about strategies for how to look at a big math routine and see how can I figure this out bit by bit versus just reading the code and feeling overwhelmed. Uh so first where do these math heavy functions come from? Well most of the time when you encounter a heavy math uh library like this it's because there's some gap in solidity's capabilities that the authors were trying to fill in. So for example if you use rust you can just do um f32 log 2 and then you have your logarithm right there and it'll give you a float back but you don't get that in solidity or if you try to raise a number to a fractional power you can't do that.

Uh so that is where these things tend to come from. Uh okay. So first of all uh I'm gonna give two seemingly obvious pieces of advice, but as I've helped people walk through these things, it actually doesn't seem that obvious. And then I'll get into the more uh intricate strategies. All right. So um the first thing when looking at a math code is you don't really want to read it like regular code, right? Okay. I'm just trying as as these lines execute, this is how the state changes and one thing happens after another. It's much easier to read a codebase if you already know what it's trying to do. And math is not an exception to that. You want to know the formula that it's trying to implement and what size of numbers that it's

expecting to receive as inputs and give back as outputs. So, uh, do I have that here? No. But, so let's let's go back to here. What is this even trying to do in the first place? Well, luckily unlike a lot of other math routines, they give the formula on top over there. We're computing 1.01 raised to the tick square root multiplied by 2 96. All right, so why is it multiplied by 2 to the 96? Well, because you don't have fractions in solidity, right? So, what do we do in order to capture the value of the fractions? We use what's called scaling factors. Kind of like how ether everything happens in multiples of 10 18, right? One ether is 10 the 18 and half an ether is 0.5* 10 18 which is

still encodable as an integer. So since this square root of 1.001 raised to an integer is going to be not an integer most likely then uh we need a scaling factor in order to make sure that the decimals don't disappear. Okay I I'm not going if if you don't already know how unis swap v3 works honestly don't worry about it. It's not actually relevant here. we just want to compute this formula and trust me bro it's important but if you already know this won't surprise you okay so that's understanding the intent which means we looked at the formula and the other thing I would say is I okay we looked at something that was dealing with square roots right and fractional exponents chances are you haven't worked with

algebra in a long time unless this is something you deal with on a daily basis so it's good to bring back to the top of your mind hey what are the rules of dealing with exponents we're actually going to see that today. Uh what are the rules of dealing with logarithms if that's what your codebase happens to be doing because uh without that fresh in your memory it's going to be a little bit hard to um uh follow it. It just makes your life harder obviously. The other thing I would say is uh fixed point numbers if you're not already familiar with them that's probably the first thing I would learn if you're diving into the world of uh more intricate D5 mathematics. So the I guess the fixed point number is we multiply all of our numbers by 10 to the 18 in order to capture the decimal portion. Uh

another common thing is we don't multiply it by 10 the 18 but we multiply it by some power of two uh like 2 to the 96 is what we saw here. Now why might we do that? Well because multiplying and dividing by a power of two can be done with bit shifting which is more gas efficient. So uh when you use the power of two that will tend to be called a Q number but a Q number and a fixed point number are the same thing. Okay let's talk about uh intelligent sub goals. First one is, okay, this all of this scary stuff over here is probably not where we should start because we we look at it, then there's there's going to be spirals inside of our eyes. Uh, but if we look inside of the purple boxes here, it's actually really not that hard to tell what's going on,

right? So, they even have a nice variable. It's saying this is an absolute value. And honestly, if you look at that, it's not hard to tell that that is in fact an absolute value, right? If it's negative, multiply by negative 1, otherwise return the original one. Um, and then obviously this is some security check to make sure that's in range. No problem there. This one might be a little bit interesting. Um, but note that when we have the ratio, we we're taking the reciprocal of it. We had the ratio and then now it's in the denominator. So, we're taking some kind of an inverse. Okay. Now, why are we why are we not doing one over ratio? Well, we we cannot do one over ratio because ratio is going to be bigger than one. And then if you do one over uh something bigger than one in

solidity, you get zero back because it rounds down, right? So um this is accounting for the scaling factor. But over here we can say if the tick is bigger than zero, then we're going to compute one over the tick. Okay? So that might mean we have to be conscientious that there's a reciprocal going on somewhere. And over here the the comments are actually telling us what this code does. But remember how I talked about it you can uh bit shift by 32 which is more gas efficient. Well, that's what they're doing. and they say we go from a 128 to a 96. Well, that just means uh we went from fixed point numbers that have a scaling factor of 2 to the uh 128 to a scaling factor of 2 to the 96. And you can tell that because it's uh right shifting, so it's reducing

the size of it. Uh what does that tell us? Okay. Well, now we know that if this is transforming a Q128 to a 96, these must all be uh fixed point numbers with a scaling factor of 128, which kind of makes sense. There's these 128s floating around there. Okay. Uh so that that gives us an important clue. At least we know the scale of the numbers that we're dealing with. The other thing that we can look for, I didn't actually call this a strategy here, is that it's probably very hard to detect the pattern in these big numbers over here, but um it's a little bit more obvious what's going on inside of these purple boxes.

Anyone recognize what's going on there? Yeah, they're powers of two, right, in hexadimal. So, um that's interesting. All right, so we're going to trigger something based on a power of two condition. All right. Now, how does this relate to square roots and 1.01 raised to the 96 and all this stuff? Okay. Well, we don't know. But the nice thing is we're making tangible progress. We figured out bits and pieces of the code. And hopefully we get a connection as time goes by. Okay. Because this uh if ABS tick and 0x2 or abs tick and 0x1, okay, that keeps repeating. It's probably worth figuring out what that does. Well, this is just a bit manipulation trick. It's saying if

the first bit the least significant bit in the number is one and you end it with one is going to be one and one is not equal to zero. So that means it's going to return true. What this means is that uh this is just detecting if a bit is one inside of the number. So this detects if the first bit is one. This detects if the second bit is one. This detects if the third bit is one because the binary representation of four is 1 0 0. the binary representation of eight is 1 0 0 0 um and so forth and so on.

All right. So abs tick and 0x2 returns uh zeros and one at the second bit if it's one. So if it's not equal zero that will trigger. Okay. So we know we're doing something with bits. We know we're doing something with scaling factors. We know there's a reciprocal and some absolute value. But that still doesn't tell us how we're computing the square roots. Okay. Um, now one way to kind of get your foot in the door and figure out, hey, I need to at least get a sense of what's going on here, even though I understand little itty bitty pieces of it, is uh, let's test out the easy cases. Like, we know that the square root of 0 is supposed to be zero, for example, right? We also know we're not exactly computing the square root of 0. We're computing root

of 1.01 raised to the tick multiplied by 2 96. But anything raised to the zeroith power is one which we would know because we brushed up on our algebra before studying this right. Um but the square root so um one some number raised to zero is one and then the square root of one is still one. So we know that this whole thing is supposed to output 2 to the 96 at the end if this formula is being inter uh implemented correctly. So we know the correct answer is now we just have to figure out how does how does the code go about accomplishing getting that correct answer. Well, since we know one is supposed to be uh the output or 2 to the 96, which is the scaling factor of one is supposed to be the output. Well, luckily we do in fact see uh one over

there, right? That's one. Uh I'm not going to count the zeros for you, but you will actually see that that's 1* 2 to the 28, but it'd be very boring if I counted, but you could plug it into Python, get the string length, do it that way because counting it by hand is a bit painful, right? Okay. So, uh and under what conditions do we get our answer to become one? Well, that's when the um that's when that's when none of the bits are set, right? So, here we get one and here we get um this is not going to trigger because tick zero is not greater than zero. So, all we're going to do is just take this number and then shift it to the right by 32 bits. Okay, so that's how we get our correct answer.

All right, that was easy. Now, rather than making a Yeah. >> Uh wait, sorry. when this is false. Yeah. >> So the last bit is not is is zero. >> Okay. So um when >> abs okay let's say abs tick is all zero right. So zero um and some non-zero thing is going to be zero and zero is not equal to zero. So it's going to trigger the false condition. So that's when the tick is zero. Now, because we know we kind of want to avoid this guy over here because he's going to complicate our life. So, we say, hey, if I I don't want to be thinking in terms of reciprocals. It looks like this is

only triggered if we're dealing with uh non-zero ticks that are one or higher, right? So, what can we do to um make our life easier? Well, let's test out the negative one tick because negative 1 is not going to trigger that. We already know what's negative 1 going to do over here. Well, abs tick is just going to be one. Uh, it's only going to trigger this branch over here. And then we know down here it's just going to shift it right by 32 bits to correct for the scaling factors. Okay. Um, now let's think, well, what should the answer be? Well, according to our formula, 1.001 raised to the -1 root of that multiply that by 2 to the 96. We can do that in Python or rather 2 to the 128 because we know

we're dealing with higher scaling factors right now. and it matches at least up until we get until later. So the thing is Python uh has limited precision unless you force it to be higher. So you can use the decimal library in Python if you wanted to force it to be accurate. Uh but I just want to show this to you because you know when you first do it in Python you're like is my math wrong or no it's Python's wrong. Okay these are a lot of decimals. Okay but now we now we know where these numbers are coming from. So reverse engineering these big constants is a very nice sub goal to have because you get um you understand what the logic behind what the developer was thinking and it's manageable even though we don't understand how the entire codebase works yet. We at least got into their thought

process for where they where they generated these large constants just by knowing hey this is what the correct answer is supposed to be. Here's an intermediate state and I only have one missing piece of information so I can triangulate it. So tick two the binary representation of two is one zero. So that's going to trigger the second if statement and we can compare what we expect the outcome to be versus what we actually have in the code. And aside from the rounding errors, we can see we actually get the answer that we were expecting. All right. Well, that's nice if we're dealing with uh ticks that only trigger one if statement. But what if there's uh more than one tick? Uh but first of all, before I do that, let's just talk about all these right shifts by 128 that are happening. All right. if um ratio if you

trigger multiple ticks it's going to keep multiplying these big numbers together and you're going to very rapidly hit overflow as we multiply right so what it's doing is saying hey these numbers are scaled up by 2 to the 128 when you multiply two numbers together that are scaled up by 2 to the 128 now you're scaled up by 2 to the 256 so you need to divide by uh 2 to the 128 in order to bring your scaling back down and that's what right shifting by 128 does so it's the same as dividing by 2 to the 128 All right. Um, okay. So, let's uh figure out how does computing the tick for neg3 work? Well, first of all, what's the binary representation of three?

Very good. One. Yeah. Right. So, we know both of these if statements are going to trigger, right? both the the one that checks if the first uh bit is set and the one that checks if the second bit is set which means ratio is going to be set to this big constant over here and then ratio is going to be multiplied again by this big constant over here and then scaled back down. All right, so this now what's the logic behind multiplying these constants together? Well, it's probably not obvious at this point in time, but we know what it should output, right? Because we're supposed to get 1.001 001 raised to the -3 roo<unk> of that multiplied by 2 96. And we can check the expectation versus the outcome. We multiply those two constants together and compare to actually

computing the tick for neg3. And we see that aside from the rounding errors, we get what we expect. So we know that this code if if it's dealing with a number that's not a power of two, it's somehow able to take other powers of two and multiply them together to produce the answer that we're looking for. All right. So, this is actually what's going on. Again, we need to bring algebra back to the surface because uh when you have this kind of a I I don't when you have this arrangement of numbers, you can actually draw you can draw a square root over both of these guys and it looks like the one on the right and you actually skip some steps here. Sorry. So, when you have two square roots, you can multiply them together and bring them under one square root. And then when you multiply two

numbers of the same base raised to different exponents, then you can add the exponents together. Okay? So that's what's going on. 1 plus -2 is -3. And we brought them all under the same square root. Maybe a nicer way of thinking about it is square roots are a number raised to the 1/2. So you could think of it as umgative - 1/2 plusgative -2 halves. So um yeah, that's that. All right, I'm actually on the last slide now. So what is the codebase doing? What's the general pattern? Well, it's looking hey if we if if we have a number say 14 it's going to have a certain binary representation right in this case um 1111 okay

and if since our code is just ratio time ratio time ratio time ratio if a bit is set then we're just multiplying these premputed constants together so 1.1 to the4 14 can be represented as 1.001 raised to the -2 * 1.01 raised to the4* 1.01 raised to the8. All right. So that algorithm actually has a name which I found uh one of my my colleagues when I explained this to him he's like oh yeah that's the square and multiply algorithm. Like why did you why didn't you say that earlier? I could have just looked that up. So um if you're I mean one obvious thing you can do that I didn't mention here is just

shove the code into the AI and tell you what answer it gives you right um I've actually used this as a benchmark for sensing how smart the models are becoming because this is something that they will tend to hallucinate on but a more rather than asking it to explain it to you which it's generally going to do poorly on at least in recent tests is say hey what algorithm do you think this is implementing and then I'm going to look that algorithm up and then I'm going to study that algorithm and then apply tie it back to the code. Now, you want to ask several different AIs because they might give you some variety in their answers, right? Uh but um that can be a helpful starting point. So, the algorithm that's being implemented here is actually has an official name called the square and multiply algorithm. Uh

but using this technique, I was able to figure out what it was doing before I knew that algorithm existed. So, just to summarize, when you're dealing with math, obviously start with what's it trying to do. Don't read it line by line by line. Write out the math formula what it's trying to do. Second of all, uh any relevant math, whether you're dealing with logarithms or exponents, bring that back to your head because we had to deal with raising things to the zero, bringing things under the same square root and things like that. That would we would not been able to do that in 18 minutes if that was not fresh off the top of our head. And then the second thing is pick intelligent sub goals. So that usually means picking code paths that are going to trigger as few if statements as possible. And then moving

on to figuring out what are these large constants are and am I able to figure it out while also using the decimal library in Python to not get hit by rounding issues when I'm making estimates. All right. Thank you. [applause] >> Thank you, Jeffrey. Uh, we're almost on time. Maybe we can have time for one question if there's one question from the audience. Anyone? Okay. Um anyway, if you want to follow up, I encourage you to check uh Jeffrey's the founder of Rare Skills, which is a web 3 technical education platform where they deal with precisely this kind of stuff, both math and zero knowledge um heavy content. So encourage you to check it out to learn more. By

the way, I had flashbacks on Carmax code on, you know, the inverse square root in the Doom source code. I had like the exact same feeling when you were describing this like reverse engineering how they're using like something very very platform specific in order to derive something that's very very math heavy. Uh I love the talk. Thank you very much. >> Thank you. >> Okay. Awesome. Please round of applause. [applause] Okay.