The Supreme Ruler of the World by Don Beaver | Devcon SEA

[Music] thank you so much for that nice introduction I I did actually go all out to try to make this the best title ever or if not it's at least a tribute um what I want to talk about today just to give a level set is zero knowledge of course uh this applied cryptography track um it's intended and directed at people who have a little bit of knowledge about uh cryptography a little bit of about zero knowledge but are basically mostly uh developers interested in finding out why bother doing this and what is actually going on behind the scenes so uh without further Ado um I'm going to talk a little bit not too much metaphysical or uh or mystical but more about how do you get calculations done by powerful entities and how do you trust that those results are actually true uh when they when they get hand something to you uh this is really the realm of zero knowledge it's actually a bit broader zero knowledge and verifiable knowledge there's a lot of different properties that are important they're really important to scaling things up on the blockchain any kind of blockchain in general and uh I'm sure many of you will have seen a lot of Buzz around uh these topics as well so what's the buzz about how does this actually work uh what is what is going on behind the scenes at some reasonable level um in general I'll do quick background so zero knowledge proofs or interactive proofs are ways uh uh for a computationally limited lied verifier a client to actually ask for the truth or or or falsity ask for a a claim to be made and for somebody to uh with a lot of power to give them a proof that that claim is is true so for example uh some of these problems might be complicated like hey I know a Sudoku solution and you know a 9 by9 is not a big deal but n byn is actually an NP complete problem to solve so these are actually intensely uh uh complex problems that people work on and and try to demonstrate the truth of uh more practically you might be looking at you know consensus algorithms and saying hey look I can tell you that I checked 400,000 signatures and they all checked out uh you don't need to bother so trust me well in this setting we don't really want to just trust people we want to actually verify what's going on okay so that's the that's the setting the the scalability argument here is that one person is going to do the work and everybody else can just sort of check after that one person did the work okay so for example what did consensus say I checked a bunch of signatures uh you know did did they all pan out uh what's the new state on maybe on my own chain or on somebody else's chain uh that's a lot of work to do if you try to do that work inside of a contract it's going to be very expensive uh if somebody can do that work for you outside of a contract and just prove it to you in a contract that helps you scale because it's a much cheaper thing to check than it is to calculate and so in general these things help us scale with things like rollups with other chains with uh with uh exchanges and so forth and anytime you have a a big calculation that you want to uh land just the result of on another chain uh we'll use these kind of results so all right there are two kind of very uh closely connected problems here uh in order to motivate it I mean really we're going to talk about uh proving a calculation here which is the middle one uh it's we'll look at a couple tools one is called sum check it's actually kind of a very old play on words when you're sending a message from A to B you do a check sum to make sure wasn't actually munged in the middle uh Su check is a way of getting a calculation from A to B and making sure the calculation wasn't messed up that the result that you get is really true um related to this is something you know I'm calling some calc which is how do you delegate a problem to somebody else and get them to calculate it for you you're a contract on chain you ask somebody offchain to to do the calculation so very uh very related very related math behind it um uh you know and and then we'll go into a little bit of the math and see what helps us scale uh uh uh these these different algorithms okay so uh what's really happening here what is the supreme ruler I get to it more in a second uh it is basically a trick that helps us look at very very large calculations essentially exponential size calculations and use like a moderate amount of checking to see that they're whether they're true or false all right you can scale this down a little bit you can say maybe I have a human scale endep calculation and I have a very very tiny verifier that uh that only uses logarithmically many steps um I won't get too far into the Weeds about the complexity of the theory but but really if you want to think about it concretely you got a millionep calculation somewhere and it takes you maybe 20 sort of questions of this prover to actually make sure that the approver is behaving and the claim is actually a true claim all right so that's where we're going to go we're trying to get to this industrial applications of ZK so we can scale up things on blockchains all right so brief interlude uh from our sponsor this uh talk is is brought to you by the number two okay so the number two is going to appear a lot of different times today uh let me just give a quick outline of of many different things that we'll see sort of a duality in we'll look at a ruler we'll see where does that ruler become a supreme ruler we'll look at checking and delegating and they're very related and the tools that work uh in one will work in the other we'll look at small scale and big scale look at slow Computing like onchain Swift computing offchain what I just said gas powered Computing versus CPU Computing uh the aim of this talk just to level set is to uh you know in the days of like hey what was htps I want to know what TLS is should I use it uh what's it going to do to my performance Etc what's all the buzz about that's the level here I'm not diving too far into the crypto I hope the cryptography uh keep me honest if I do uh this is a talk about hey if you're a ZK VK verifiable knowledge adopter what's a little little bit of the math that goes behind behind it what is kind of the RSA flavor of that is not a talk about how to become a ZK evm uh developer for example uh it's how to use these tools and what what actually uh gets us to the scaling uh going to try to really hard to stick to non-mood math I'm going to uh talk a little bit about how you start with lines and turn them into something that is a multi-linear this is the real essence of the math behind most of this and I'll do some geometry for that uh and take us from an ancient kind of Jurassic age of of of checking things into what the Modern Age of really practically checking things is and how that looks so all right Jurassic as I said long time ago 35 years ago U let's start okay with sort of an everyday ruler now I am a I'm also a dad and additional to being a researcher so uh we're not talking about rulers that command the universe uh although the origin of this word is pretty much the same rulers are things that help us do uh do things like command more of the world so if you have a couple points from second grade you learn how to actually like draw a line between them okay so you draw a line out sorry for people in the back if you can't see that but you can actually extrapolate and get new points from it say normal ruler does things like that what else does a ruler do the second thing ruler align things okay it's really important you know if you want to make sure that everybody is in line or that all your data data is in line that you have a straight edge to actually line things up so this is a tool that helps you detect if something is out of line This is actually the basic mathematical idea behind most of the the or a lot of the verifiable knowledge uh protocols is actually just looking at lines and seeing whether things that are claimed actually line up so I'll get into more of this in a minute that's just kind of the geometric uh backing for all of this for what's going on okay so we'll start with a start with kind of a basic ruler and we're going to get to something that is in larger Dimensions kind of this sort of hyper cubeish looking thing that is going I'm calling a supreme ruler it is a larger scale version of a ruler okay so let's rewind a little just to set the scene to remember kind of high school math a little bit here if you start with a table and you want to draw a turn it into a line may make it may make a linear extension of entries in a table here's where we go with it okay this is just just a refresh memory okay you have some inputs maybe a one bit input it's either zero or it's one you want to draw a line through it that the GE geometry that we just saw uh a moment ago so here's what you do you draw the line okay it's nice if you have a calculator to do it uh but the technical part of this and and and we won't go too far much too much deeper than this is that the nice trick to doing this it's a little bit of high school math as well is we can use two really nice helper functions is X Al to0 the is x equal to0 function is just 1 - x on one bit inputs okay I'll let that sit there for a second 1 - x tells you yes or no is x0 and likewise you know this is this is hopefully relatively simple uh high school math at this point is x equal to one is this equal to one function okay we're going to use these okay in building up what the extension is and there's a reason I'm going through the basics we'll we'll grow it out in just a second um if you say this is basically a a short program here to say hey if x is zero output 3 if x is one output seven okay so these are kind of one hot functions they're only they're only going to be uh nonzero in certain cases and so this is how you interpolate a line pretty straightforward Okay add them up you get a linear equation and that's you know that's really what we just saw so that's the algebra side of it okay so this part hopefully is is straightforward I'm going to jump into cryptographic motivations for this uh kind of related Pro problems that are related to zero knowledge zero knowledge is a claim uh that you want to prove there are also things like delegation which is I start with some input here 0110 and I want to ask the cloud to actually help me calculate some function of that okay so all right the the the key thing here is that the cloud is not supposed to learn what you're trying to compute it might be your tax return it might be private inference that sort of thing so it's a very related to zero knowledge problem it has the same mathematical solutions to it uh but it turns out to be a little bit easier to to address uh and to find where these tools work okay so you send a message it's a little garbled you get a message back from the cloud and from that you're able to kind of figure out what you were really interested in in the first place okay here's a sort of silly way of doing it for like a line if your function was like a line not not very complicated function to compute but you say hey server tell me you know what was F of five up here hey server tell me what what what is like f of of4 and then you'd go home and you say thank you and you draw a line and then the server would have no idea what you were really interested in were you interested in Computing F of zero were you interested in Computing F of one but the point here is that you can actually do it okay so that's a that's a trick with one server now to some degree it's sort of like why bother doing this it's it's a lot of work for nothing at all you might as well just done this uh at home in in the first place but we're going to grow this uh and it turns out that if you grow it in a certain way using this multi-dimensional ruler you actually can actually delegate uh delegate uh the the query to uh a server privately uh and likewise the same tool works for for ZK as well okay so the shape of what we're going to do is we're going to look at things that are like hey points on a line and you know uh if you actually uh if you start with setting two of these points on the line you will determine the values of all the other points on the line okay uh we'll expand higher Dimensions set four points on a Boolean value square here 01 0 Etc 0 0 1 1 Etc uh grow that from there and we'll go to larger dimensions and it turns out that at larger Dimensions we actually get some payoff in this and that's where the compression comes in that's where scaling comes in the cost of going to large dimensions actually uh there's a trade-off that works really nicely there okay so I said a little bit about going back in time let me try to set the motivation here a little bit to generalize from like the one server case to a multiple server case okay there was some nice work in the 80s done on this that said for one server you could actually do calculations like this but there were kind of very limited calculations it got generalized a little bit later on to saying what could you do if I have a tax return and I want to ask you know Amazon and Microsoft and Google to help me with it but I don't want to reveal the tax return so you get you get answers back from each of them and and then you're like okay I I know what the the result of my tax return is I I owe $5 or whatever in this case okay so geometrically we take the case that was like before um except now we have different servers giving us answers so in just the linear case might go hey Alexa tell me what is uh you know F of four hey Siri tell me what is f of five and now having gotten those answers back to some maybe some very complicated uh calculations we can extrapolate ourselves to places that we're really interested in which might be something like if we are trying to find F of one okay so you're going you're asking for something on a line and you're getting answers uh back for this uh calculation and then you're able to figure out what it is you wanted to calculate okay so it's all drawing line like I said um I will take a very brief detour here this is not that important uh but it actually is part of the trick if you want to look at this later uh that's fine but there's a lot of polinomial going into this so I don't really want to uh spend too much time on this but if you secretly share you can actually go for those of you know who uh know multiparty computation and secret sharing you can actually scale this up to many many other parties and then you're not just interpolating a line you're interpolating something that is of degree n to get your answer out uh okay but that's as much as I want to say on that because that's like maybe a little too much into the Weeds on polinomial okay here's the the core trick this is what happens and gets skilled up in zero knowledge it what happens in in in delegation you actually a go out and ask for uh these Cloud servers to calculate a sum of a huge number of things two to the end things now the cloud is fine to do that for some moderate end you as the client are not bothering to do all that work uh you'll get some answers back uh after all that work is done in the cloud and locally you don't really have to to do very much locally as the the the the the weak client you're really just doing kind of like a drawing lines interpolating a small polinomial over here size n kind of calculation the servers the the clouds are these guys are doing two to the N calculations so there's a big scale difference here you're getting a lot of work from provs a lot of work from uh from delegates the flavor of this the compression that happens in all of this that that that powers all of this is that the weak person the one who has just gas on a on a chain is doing a map reduce of size n adding up N Things compared to work that's being done offchain or or by complicated servers that's on the order of two to the N so here let's you know the the the kind of cool thing here was uh is that you can delegate really complicated answers uh and and using this this this supreme ruler in a sense okay so I will skip through a little bit of the history in interest of time uh this stuff got uh um discovered back well I missed a punchline here this stuff got discovered back in 1989 most of this and it's now being implemented on chains uh other kind of important things happen there and it's kind of relevant um is that this was the kind of the era of Swift Computing if you like this is where we could speed things up by an exponential factor sorry about that um said dad jokes here um we are here now doing things like Su check you'll see things like uh hey I can do exponential calculation offchain uh and and and and get things checked in uh normal linear time onchain uh that's really what's going on here uh there's a kind of a very very uh strong relationship between the the the the delegation and the and the and the cube okay I won't go into the details of this this is a this is a little bit uh it starts to look like uh you know uh category of endofunctors kind of explanation of the math that's in here um instead you know I said no moon maath trying to be honest about that back in the day this was the interesting thing about this theoretical development that you could take hyper cubes and then squash them into like linear calculations I'll say how in just one second but uh kind of missed the mark you know nobody wanted to do the moon math in 1989 uh the New York Times said wow there's a lot of research going on here uh you know what's interesting well we're not going to publish the moon maath in the New York times will'll just say what's interesting about it so the reason I'm talking about this here is that well in 2024 it's kind of the same thing you don't need to know all the moon maath necessarily but there's a lot of hype around ZK and it's kind of nice to and what I want to do in the next couple of minutes is just go into the details of that you know without if you the the really fascinating thing that is not completely Moon math is that hey with only 20 questions you can pin down a calculation of a million steps okay that's the magic okay so I'll try to do the magic quickly it looks a lot like the beginning where we had the high school math we'll go from one bit inputs to two bit inputs just to start and so here's some random you know table that you might want to compute this is maybe a machine learning algorithm output or something like that okay well we do the same thing it's a program it's a program that is a switch case statement if XY is0 0 output five if XY is 01 output nine etc etc the interesting thing here is that well what do these e equality uh Checkers look like well if you want to check if x is zero and Y is zero you use this function which is 1 - x * 1 - y okay that's the one hot function that is only going to appear in in my lookup uh once under this condition and when you look at this this is a term that has four this is a function that has four terms in it uh it's kind of exponential already it's got four monomials uh but the is linear in X there's no like X squ or anything like that it's linear in y there's no y squ or anything like that the largest degree that you see here is two kind of the XY that's in there so it's very low degree all right generalize this you can do this at home it's you know you get a you get a interpolated result here if you look at the wall of of of latek you know this actually expresses what really the bottom line is is that when you try to do this interpolation you get two to the N monomials so you can actually Express something that's really really complicated but the maximum degree in this is only a degree nend so it actually turns out to be easy to be for verifiers to check because of that low degreen you're only just kind of looking at that low degree polinomial you're only looking at lines but the servers or the provs are doing intensely uh uh uh busy calculations in this okay so picture uh hopefully worth a few thousand words uh starting with two values we looked at two points on a line and these two points actually really constrained all the other values on the line and it means if you do one of these shell games let me pick a few of these points on the line and see if they are consistent uh you only need to ask for one or two probes on this step the dimension up a little bit and you've got four values for two bit input two bit X and Y how many probes do I need here I need kind of maybe two or three probes okay this is where the scaling actually happens it's that when you try to encode a function with eight values using this multi-linear trick here I don't need to do eight probes I don't need to do a whole thing I need to do just maybe two three or four probes to actually get this to work okay that's kind of where the math comes together it's what happens in the zero knowledge it it's what happens in the delegation and so forth okay and in general you know we sorry for the Universe I have to apologize that we can't draw you know two to the end values up here but when you're trying to uh scale this up you get a huge blow up in in in the power of the checking and to be concrete again if you have like two to the 20th values you now only need to ask sort of two 20ish questions it's it's a real explosion in scale so that's the flavor of like the basic trick that happens in a lot of zero knowledge uh so that when you're actually asking your you know asking to verify something on chain this is why you can get away with something that's very very small okay so let me let me just finish uh with this last slide or two uh zkm uh what are they doing in general a typical pattern is you run a program for a million steps you write all the values of the trace of that program on a hyper Cube that's you know 20-dimensional hyper Cube you can do this this is a you know it's a it's a computer easy for a computer to do uh you've got your your million entry table that says all of the steps of the calculation and so the flavor of this is to then build a proof around that and because of this like Dimension relationship here you only need to ask like 20 Questions instead of ask asking you know a million instead of inspecting everything everywhere so that's that's really the magic of it okay so if you really want to do ZK VMS there's a lot more you know of moon maath here that I'm skipping completely uh if you feel nerd sniped feel free to go look at it uh we're not getting into any of that this the reason why these things are hard is that there's more other more stuff to to it than than just that trick but this trick is the core of why the compression works of why compress pring million steps down to a 20 step uh probe is is is is is feasible at all okay so that's it quick summary is history you can look at this later if you want but the real interesting things here is that we started the area era of kind of Swift sound Computing 35 years ago if you like uh we move forward now and we're finally going from an era that was purely theoretical to an Era where it's all applied and we're now industrializing this where we're building programs that can take a a million step calculation and check to make sure that that that actually is valid okay picture million is what you get for the cost of 20 and that's it thank you guys so much thank you thank you Don Beaver indeed a great presentation with that jokes included and Hyper cubes and multilinear and multi-dimension so remember that we have uh this QR code where you can input your questions and the questions that were more voted are more likely to be answered so to start with the first one is there any value to asking more than 20 questions is it a high level higher level of security uh or certainty yeah no this is actually this is a perfect question I I wish I had planted it there's there's a really subtle Nuance in this um the 20 relates to the dimensionality and it is not that asking one question or two questions is is is worse or asking 40 is better if if you think about a line to determine a line you need two questions asking four questions on a line isn't helping a lot so really what you want to do here is to ask the 20 questions for a 20-dimensional thing and then maybe take another shot at it might have a chance of cheating the first time with 20 Questions next we'll do another 20 questions and we'll set the whole thing up again so the the going from one to 20 uh you really need to get to at least the 20 uh to to start off with great question great question yeah thank you awesome all right any other ones you can input if not please join me thanks so much and uh yeah round of app Plus