ZK10: ZKML Endgame: Specialized ZK Proving with GKR - Ryan Cao

Transcript

foreign [Music] we're going to dive into zkml now so yeah up to you thanks Ryan alrighty thank you so much okay so hi everyone I'm Ryan I'm the CTO of module slabs and I'm here to talk to you all today about r4a into gkr which is a proofer system specifically tailored for zero knowledge machine learning proving okay let's get started so before I get started I just want to say that we here at modulus have been working very very hard on the promo zkml since last year and basically today's talk is to kind of share with y'all some of the wisdom that we've

gained from basically implementing complete projects in zkml and where we think we kind of need to go next and so that's why I'm here to bring you the modulus perspective so this is also the roadmap for the talk and if you ever get lost don't worry this roadmap will this roadmap will come back and you know exactly where we are so first off uh we believe that basically there should be specialized provers for what we call Specialized computation regimes so you can think of an evm as one type of computational regime you can think of General smart contracts as another type or in our case machine learning now it turns out that yeah as I was saying machine learning we think is a specialized regime and it's actually very very different from the other computational regimes which is why we need a specialized proofer such as gkr

to do basically proving for zkml and finally once we've discussed GTR and why it's so cool and why it's so fast we'll talk a little bit about what's next in store um which is hint remainder it's our implementation but again we'll leave that for then all right okay so let's get started with specialized proofers for specialized regimes and so for each of these sections there's going to be one key takeaway so for example in this first section all provers are specialized and we'll see why this is the case so if you think about basically the kind of land of proving systems and like all the systems that are out there you can actually kind of start to categorize them by what they were designed for slash what they're really good at right so for example if you care about constraint or circuit flexibility

and like ease of design and things like that then you might want to go with something like Ultra plunk or sarcom which allows you to Define lots and lots of constraints however you want on the other hand if you care about proving the program trace of an uh basically of VM execution specifically then you might want to consider air or Starks because in there you basically have this specialized like two times step constraint that says that this time step should come from exactly the previous one plus whatever assembly instruction you're doing alternatively if you care a lot about proof recursion then you might want to look into for a high plus E2 since this uses basically all Native Fields arithmetic and there's I guess nothing yeah everything's just very fast about it small Fields also if you care about

vdfs or IVC naturally folding and uh basically in the form of Nova or other faulting schemes is like literally Tailor Made for This and finally if you care about machine learning inference due to the structured nature of machine learning algorithms as well as the data parallel nature of how we process such obviously inputs to those models you might want to consider gkr now you might be asking yourself why why would I consider gkr GTR is crazy no one's ever used this before so a little throwback um uh basically at the beginning of this year we actually wrote this paper uh called the cost of intelligence which went ahead and took actually a lot of the proof systems that you see on the screen right now including gkr and ran a bunch of neural Nets through them and so

for a little taste of our results here you can see basically on the x-axis the number of parameters in the model that we tested and on the y-axis you see how long it took to generate the proof so this is just one kind of metric that we cared about but the point is that if you look at this orange star line right here this is the line for basically gkr and so clearly it performs very very quickly it scales very well and actually it does even better than what we're showing here because the implementation here was a single threaded implementation whereas everything else on this graph had like 64 cores or whatever the machine had so it's very very fast so even before knowing what machine learning is or before knowing what gkr is you can already see from numbers it's pretty good okay so now let's dive a little bit

into machine learning and why computation in machine learning doesn't quite look like computation elsewhere so the key takeaway here is that machine learning algorithms are both what we call structured and also what we call data parallel so before we actually talk about that um I'm just going to give a quick primer on machine learning so for folks who are vaguely in the know or aren't in the know uh basically machine learning just says okay I have this model uh it is just a model of I guess something that I want to predict the inputs to this model are for example a cat image or a dog image and what this model is going to predict is basically whether it thinks this image is a cat or a dog and so there's basically two phases in machine learning there's the training phase in which you basically

take your big training set of a ton of examples you feed it through this model and the model learns the correct parameters to make the predictions afterwards you basically fix the parameters and you fix the model architecture and then you throw real world data at it and you say hey here's this random image that I found off Google tell me what it is and the model says oh I think that's a cat or I think that's a dog and so it's precisely this process this basically computation during test time with real world data that ztml tries to prove it is proof of machine learning inference so that's basically what all these words say you don't have to read them okay great now that you know what machine learning is um we can talk about basically the structure of it so consider the structure of a typical kind of neural

network so this is what we call a feed forward neural network most of you've probably seen this before a couple key things to note is that one you can already see there's like layers in this right so here's the input layer here's where all the inputs are coming in some transformation happens to them and then here's the next layer and then some other transformation here's an X layer so on and so forth right so machine learning has this already very layered structure and on top of that for each layer so for example let's consider a linear layer in which you basically have a matrix Vector multiplication so in this case the input to this layer is basically X here the weights are W actually I have colors for this okay so the weights or the parameters to this layer are the W which is the Matrix uh

the actual inputs to this layer are the X and then the outputs are the Y and so if you think about the actual operation which is happening in The Matrix Vector multiplication you'll notice that basically in order to compute this first output y we need the first row of W's dotted against all the X's right and in order to compute the second output Y2 you need the second row of W's and so on and so forth and so there's this very kind of natural structure here where basically the location of the output or kind of like the index of the output if you will depends directly on the index of the input which is coming in right you can literally see it in the colors y1 always comes from the first row of w okay so that's for basically a linear layer there's another type of layer

called basically a bias layer it's even simpler you basically have X which is again the input to this layer B which is some just shift that you're going to shift all the inputs by and then Y which is the output of that shift and so again if we look at the individual operation we'll see that all the Y's come from exactly the first row of v's and X's so on and so forth so this whole mapping from output index or like location to input location is exactly what this structure is all about so keep that in mind okay uh the other part is that machine learning is what we call data parallel in other words normally again let's say you have this cat dog classifier then I can feed an image of this cute Pomeranian through it and I can get out the labeled dog but why

should we stop there we have gpus these gpus have thousands of cores in them we can run tons of examples through them right so I can run all these at the same time and so what that should scream at you in ZK circuit land is basically I'm running the same circuit right the same model same architecture there are many many many many different inputs um and so this is what we consider kind of the data parallel setting um and it turns out that gkr just supports this natively so it's pretty cool um so it's a quick recap um first machine learning models are very very structured they run in data parallel settings both of these things tend not to be true for other compute regimes and also they are huge and I mean huge right there are these things have billions of parameters like

gigaflops to teraflops to the compute it's very very difficult to circuitize these things and actually prove that they execute it correctly we need something different we need something better and that's where gkr comes in so for the GTR section there's quite a bit to cover this will get a little bit into the weeds you'll see some equations if you don't understand them it's fine I tried to break them down I'm very happy to answer questions uh obviously afterwards um yeah just uh you got it all right so the point of this section is that g car is cool that GTR is very very fast and also that it proves machine learning circuits pretty easily and we'll see what that means okay so first let's talk about why it's cool as a real quick background on gkr it was actually

developed in 2008 as kind of a complexity Theory result and it was later refined into something that's been practical basically throughout the years um gkr itself is what we call an interactive public coin protocol in other words there are basically rounds of GTR that happen and it operates over these things called layered arithmetic circuits so similarly to how you saw the feed forward neural network had layers the gkara circuits also have effectively layers that line up adjacently to each other cool and then the final thing is that at a very very high level the way that GTR works is that it iteratively applies the subject protocol which we'll talk about a little bit basically to reduce what we call proverb claims from one layer to

the next in other words imagine that you are the verifier and I am the prover and I'm saying to you hey the output of this circuit that we've agreed upon is this value right so that is a claim I'm claiming to you that the final layer in this circuit uh basically evaluated at these points equals this value and so you say well I don't believe you why should I believe you and I say great let's play the some chat game so we do some check and then we reduce that claim tweet claim on the previous layer and then you say well I still don't believe you because I don't know what that layer is supposed to be and I say great let's Play the soundtrack game again so we do this uh basically over and over again until we get to the input layer of the

circuit at which point either you already know the input to the Circuit because it's public or I've given you a polynomial commitment to the input and I produce an opening proof for that polynomial commitment so this is kind of of the high level picture of how gcare works so just keep that in mind as we go on okay so that's kind of I guess like the background and why don't we actually just look at a concrete example of a GTR circuit so industry here circuit uh we basically have again this input layer here which consists of what I'm going to call X which are kind of like you can imagine again the model inputs W which are kind of the model parameters and B which are the model biases and the operation that this circuit computes is w h hadamard product X which is just

this element wise basically product between the x's and the W's plus b so we're just going to add all the B values onto here okay so that is what this circuit does and if we introduce a little bit more storage Here style notation it turns out that if you look at these layers as basically Columns of values like arrays if you will you can actually just represent these using multilinear polynomials so multilinear polynomial is just a multivariate polynomial that happens to be linear in each variable and the nice thing about these particular multi-linears so V2 tilde V1 tilde and V zero tilde is that when you plug in basically the appropriate binary values into their parameter set it turns out that they

actually just spit out exactly the values from this layer for you in other words evaluating the polynomial V2 at 0 0 should give me this first element right here and then evaluating this polynomial V1 at 1 should give me this element right here so to make things concrete uh this is the thing that we just talked about v2000 equals the first element oh my gosh the first element of X right here and then similarly V2 at 1 0 1 should give you this one right here which is just B1 okay so that's kind of the quote-unquote data representation in the circuit um if we think about actual kind of relationships within the circuit on the other hand let's take V1 of 0 for instance so that's this one and the way

that we actually compute this one is by taking V2 of 0 0 and multiplying it by V2 of 0 1 0. so this turns out to be kind of the circuit-wise relationship for V1 of 0 and you'll notice that here we have basically this binary multiplication Gates um similarly uh v01 uh which is this one comes from basically the addition of two other values in particular this one and this one and so you'll see that the lines connect which means we have an ad gate there okay all right so this is basically the GTR circuit sort of setup and so now we're going to talk a little bit about something that I'm calling the canonical gkr relationship so this is a basically equality that Maps between any

particular multi-linear extension or the data in any particular layer and that of its the data in the previous layer uh so there's a lot of math coming up ahead but we will break this down okay so if we look at the left hand side v i tilde of Z basically says in the ith layer what is the value at index Z right so uh also I used a bit of shorthand here Z X and Y are all binary strings um yeah so just keep that in mind but the point is that v i tilde of Z for example could be V2 of 1 0 1 right like that it could literally just be like this value here and so the question is for any particular value in the current layer index.z what is that expressed in terms of the values in the previous

layer and so you can do this as it turns out by basically taking a big summation so this is a summation over X and Y which just represents all pairs of gates in the previous layer so you're basically saying okay for every pair just just give that to me in like an iterator almost and then you're saying okay now we have this basically wiring predicate at I plus one at zxy so what this says is is there an ad gate at basically X and Y which yields the current value of Vi at Z right and so it'll be a one if that's the case and a zero otherwise and so if there is well clearly the right thing to do is to basically contribute those values from the previous layer in an additive fashion so that's exactly what this part does and then similarly with the

multiplication Gates um so again is there a multiplication gate here right like are there the two lines that are connecting in a multiplicative way to receive basically the current value that you're getting and so the answer is yes then we contribute those previous two values multiplicatively so in essence uh you'll notice that on the left hand side we have VI and on the right hand side we only have the I plus y one and so the relationship between a previous layer and an X layer is effectively established cool okay so at this point um we now have I guess like how a circuit looks and we also have how to relate basically layers in a circuit to each other um ah yeah so I guess as a very concrete example here um you'll notice that instead of this particular relationship

the V1 of 0 equals v20 times V two of zero one zero we can replace it actually with a multiplication gate which kind of says the same thing which is that we're starting from zero here and then zero zero zero from the previous layer and then zero one zero from the previous layer should give you one so that's effectively what these wiring predicates are doing um however okay so now that we kind of have like the relationship established the question is how do we actually prove this relationship or how do we actually do this claim back propagation stuff that I was talking about and the answer is through some check um so the version of soundtrack that I'm going to get or that I'm going to give is not very complete but hopefully the abstraction makes sense and hopefully you should be able to go from there but

the tldr is that um in some check uh a prover is able to basically prove to some verifier that a particular sum over all binary strings of length K over a multivariate function that takes those as input is some value right and you can see why this is valuable for us because in our canonical gcal relationship that's exactly what we have here and so we would like to reduce this summation check into something that's much easier for the verifier and that's what soundcheck allows us to do so in some track basically the way it works is that you start with this big summation and then the proven verifier play this one round game where the verifier says Ah here's a random challenge please bind the first index basically in the original function to

that random Challenge and also we're only going to sum over everything else right so we're not going to sum over B1 anymore we're only going to sum over B2 through BK and so it turns out that if you keep on playing this game and you bind more and more things basically to random challenges then at the very end the only thing that the verifier needs to check is what we call this Oracle query in other words the original function within the summation F evaluated at all of the random challenge points but there is no summation anymore right so this is effectively what we're going to use to basically do the claim reduction thing okay so again I have up here the actual like relationship expression and so if we think about what happens after the entire subject process the Oracle query in other words the F of

R1 through RK that was on the previous slide basically gets boiled down to this so what's happening here is there's no more summation and the X's all got bound to random challenges U and the Y's all got bound to random challenges V so the verifier just needs to evaluate this particular expression and it's good to go so we're so close we're almost there okay so the question is of course how does the verifier actually check this Oracle query right like how does it know what the value of this is supposed to be well let's break it down so first we have these wiring predicates and the nice part is because the verifier already knows the circuit ahead of time right as it should um it can just evaluate this on its own so it's totally good there on the other hand um for these values the I plus one at u

v i plus one at V so on and so forth these values are proven recursively via some check right because these are actually values which are supposed to come from the next layer of the circuit the I plus one whereas currently we're looking at VI so that so basically we can take these values and say well I still don't trust these values but I'm going to use them as is and then I'm going to force you the prover to prove to me that these values are also correct also via some check and so you can see how this process basically repeats over and over again until again we get to the input layer and then we can do something else there okay so to recap um the approver claims basically that the output of the circuit v0 equals y um the verifier reduces this claim to

the next layer um by basically playing the soundtrack game with approver this happens so on and so forth until the verifier is left with the claim on the input and then you can just verify this by either PCS opening or by directly evaluating the input yourself cool okay uh okay so G here is very very cool it's also very fast um so GTR is speed also IM speed because I don't have that much time left okay uh okay so one cool thing is some check Works purely over field elements there is no group operations happening there is no pairing and it's also extremely paralyzable on the prover end so it's very very fast also as opposed to for example in Planck circuits where you need to perform polynomial commitments to every single column in your plonk table G care only needs to polynomial commit on the circuit's input layer so

all those intermediate layers you're good because you can use some check also there exists kind of these separate time optimal subject protocols happy to talk about that later or offline and actually it turns out that parallel proving for such Opera for such operations is actually sometimes faster than sequential Pro uh Computing so pretty fast okay finally GTR proves a machine learning circuits easily and so we can see this by basically the structure of the machine learning circuit that we just looked at so in other words um yeah there's a lot of text here it doesn't matter too much but if we look at basically this the structured GTR circuit that or the GTR circuit that we had previously it turns out that we can write it in a structured way in other words if we look at the relationship

between basically v0 and V1 well it turns out that v0 at zero comes from V1 at zero right and V 0 at 1 also comes from V1 at one so instead of writing zero and one let's just plug in B1 directly here and then same thing for view one here and so the point is that basically it's the same bits it's the same indices which happen on both sides of the equation and that is the structure here and so it turns out that if you basically have this type of relationship you don't need the wiring predicates anymore and the verifier actually has a really really really really nice time basically doing the claim reduction so doing that soundtrack process okay um and I guess the sleight of hand that I pulled on you was that oh this was

actually a machine learning circuit and so machine learning circuits are structured so you can do the structured thing so everything's fast blah blah so on and so forth okay all right so what's next and the answer is well it's remainder so we have app modules have been working very very hard on implementing uh such a GCR proofing system specifically for basically zkml so it'll be a robust implementation also it has built-in data parallelism for when you want to batch over your AI computation um the open source version will be coming out by Year's End so it'll be an early kind of New Year's gift for everyone and also we are supporting data parallel and also large scale basically decision Force inferences which we'll Showcase in November so stay tuned for this

um if you're not convinced you should listen to our expert testimonials Riyad wavy says hmm Justin thaler says huh and if you're still not convinced or you want to feel these motions for yourself feel free to join us on Twitter or join our telegram group in which we will post lots of nice nice gkr and zkml related content thank you everyone [Applause] thank you Ryan you get me worried for that screen that I love The Passion of the presentation we have time for questions so yeah please raise your hand thank you for the talk my question is about non-linearities basically in the

network you just mentioned like metric multiplication but like it's much deeper or like skip connection self-attention and non-linearity so I'm interested like how this work yeah yeah so skip connection so residual connections and things like that are actually very straightforward you can just wire things like however you want to um in terms of nonlinearities uh yeah so uh currently I think binary decomposition of things tends to be the best way to go um however given knots look up lasso um and hopefully other multilinear lookup arguments coming in the future um those should be much easier to deal with Once those can be basically integrated and we've I think fairly good reason to believe that you can integrate lookups actually into gkr cool thank you I'm not too familiar with GTR but

doesn't it require a fan in two where each gate has only two inputs uh is there like a way around that to do more complex models or uh is that lighted decision trees ah okay so I guess the first part of the question does g here always need fan in two not necessarily so in the kind of canonic gkr um I guess equation uh it does have fan N2 right like there's explicitly two values that are being contributed um you can easily imagine though just adding another variable here and saying ah z u v w or whatever and having the I plus one U plus v i Plus One V plus V plus one W uh actually there's a way to generalize this to uh actually unbounded fan in at least for ad Gates or for addition Gates um I

think for a higher degree uh you might want to consider the trade-offs of like oh I have a degree six multiplication gate therefore I need to send degree six univariable polynomials during some check um so there is some exploration to be done there but yeah hold on with this structure can you cover a touring complete operations or just like these uh like multiplications and additions ah okay so I think chronic gkr is oh your ghost is going to Arachne for

this let's talk about this offline um yeah uh I yeah the one thing I will say is that uh actually these structured or regular circuits cover a surprising number of operations as in for the circuit that we have for decision trees only a very very small component of it cannot be written as a regular circuit yeah any other questions yeah yeah hi thanks a great presentation so any Benchmark result can you share about gkr like a cost of intelligence fall off yeah so the benchmarks you see in cost of intelligence are written in possibly

the world's messiest least commented code base ever it was an academic code base um from the folks who authored the zkc at end paper which we basically played with made non-interactive whatever um for us we are coming out with benchmarks soon uh but we've been working on basically uh actually getting the code base Al game the circuits out um so I think with the open source we'll be able to offer some benchmarks yeah thank you we do have a bit of time if anyone else has a questions otherwise yeah okay be back to you you already got one yeah so why were the testimonials uh oh I put these slides together last

night and I didn't have time to Ping them to see if I could get actual quotes so I assume both of them have said this in our meetings at some point okay good enough I have more sorry I mean as you can see it on on the public change that is zero so that's right I I assume about ipfs uh oh wait sorry could you repeat that um I I mean that you can see your slide on ipfs oh um uh sure yeah I I yeah I don't know how to do this distribution but I I will share the slides in whatever form

factors yeah okay more like a high level question like where do you see zkml going in terms of use cases uh yeah this is a really good question so for us I guess looking at basically inference since training is a strict superset of inference and also not super clear what the value prop of trading is um I think for us it looks like basically saying hey which projects I guess in the crypto space um really like would be would benefit like tremendously from machine learning models like whether it's decision trees whether it's neural networks sems whatever you want and basically for these I guess like Services um I guess how much of a value add is it such that like the cost of CK right because ZK is you know we all know this

like it costs more to prove than to not prove so you need to I guess like pay extra in some sense um but it's like where where does that make sense so for us actually one thing that we're coming out with very very soon is basically a verifiable nft project so we're doing this in collaboration with polymon monsters or polishing monsters um and the idea there is that for nfts normally you have basically ownership provenance right because of the chain but you don't have data source provenance in other words the first person who basically put that thing on chain you don't know where they got it from you don't know who authored it uh it could be any number of things and so in this case once you have a ztml proof that a generative art model actually created the image in the nft you now

have complete picture provenance you know everywhere it's been and also the exact model it came from and that model itself could be like an nft or something like that so an online AI artist in other words but do you see use cases outside of let's say blockchain space ah use cases outside of blockchain space I mean the example that I always like to give it's very far out in the future but I guess the way that we like to think about it is basically right zkml is like the I guess the marriage of two things it's like machine learning and ZK so machine learning obviously is really really good for when you can't code an explicit algorithm to solve a problem right like the best you can do is just gather a lot of data and then basically try and train a system which you know

may or may not be explainable probably isn't explainable if it's working very well um to basically solve that problem for you um on the other hand ZK basically gives you I guess like output provenance right it tells you that this output definitely came from this model that you care about so where I I guess where we see that maybe most obviously is what I like to call like the language model judge example which is where currently in a court of law you can see the jobs you can see them you know where they came from you know all the cases that they've done before you basically understand their experience and so when they tell you their sentence like you can't really refute it in some sense right in the future on the other hand if for example a language model became a judge that is something that we really

really really want to basically prove via zkml you want to make sure that the language model is fair you want to make sure that it's unbiased and make sure that it's robust you want to make sure that it's the same language model which has been used for all the cases before you right um and so and and also I guess the point is that the result there is very very sort of like life-changing as in they could sentence you to whatever um and so in that case it's very important that we know where the output of the model comes from like which model comes from yeah so that's kind of the I guess like the high level like framework that we like to think about this cheers thanks to answer your question the the talks are recorded so you can kind of get the slides through the video I guess thank

you very much Ryan thank you for your questions thank you so much and yeah now it's time for a break