Stark Recursion

Transcript

hi everyone we can finally start um sorry for the delay so my name is avio i'm head of product soccer today i'm going to talk about stark recursion and this is uh what i'm going to cover in today's talk so basically i will give you a little bit of a background because i do mention things like starks stark proofs and cairo and sharp and even starknet so i wanna uh if you don't know what it is i wanna give you in a few slides uh some background about it and then i'm gonna explain what recursion is and in particular it's very important for me that you will all understand today

some great benefits that recursions brings with it and eventually i'm also going to present some numbers and some upcoming optimizations great so i was playing with the idea i gave actually i talked about recursion a few weeks ago and i was playing with the idea to now play the video of this talk and in this talk i will get to this point and then i will click and play the video of this talk and so on and so forth but eventually i i voted against having stupid recursion jokes in the presentation so you won't see that now but i do want to say that the last part is new so even if you watch this uh previous talk you

still get something new today okay great so here behind me i was told not to move too much from the stand so behind me you can see uh the topics that i'm going to cover now it's going to be a crash course so like three slides i'm going to speak about proofs cairo and sharp stark net if you don't know what it is there are like many people in the audience here with stark wear shirts should go to them afterwards and they will tell you all about stark net great so what are uh stark proofs and cairo what do they give you so the general idea is uh pretty straightforward you have a computation that takes time t proving it takes more or less or is linear with the time so it also we

can say takes time t but very verifying the computation verifying the correctness of this computation once you have a proof only take take time log t which is much much much shorter than running rerunning the computation this is great this is what we want and cairo is basically the tool cairo is a programming language that enables you to take any logic in the world and rewrite it in cairo and then once it's written in cairo it can be proven very easily so here's an illustration you have some logic that you wanted to prove you rewrote this logic as a cairo program great now you wanna you wanna prove some verifier that if you run this chiral

program on some input say x you get an output y and the way to do it is to generate a proof uh that the verifier can verify okay great now you know enough about proofs and enough about cairo and we can go and speak about sharp so sharp is a shared prover it's initials for short prover and what it gives us is the following suppose you have many different chiral programs with many different inputs you have a cairo program for starkx immutable let's say and a different kind of program for stark x-ray and another chiro program for stagnet those kind of programs they

they represent different logic and they can have different inputs but at the end of the day you don't want to get to a point where you generate a proof for each program separately why it's because it's wasteful if you do that then at the end of the day you're going to pay a lot of millions of gas per every single program so what sharps gives you is given different chiropractors with different inputs you can still generate a single proof that attests to the validity of all those programs with all those new inputs every job here is a program and input and the proof uh show correctness for all those jobs simultaneously which is amazing and can save a lot of gas and this is how

we work today on ethereum okay now you have all the background you need and we can talk about recursion so does anyone know this uh tv show great great i love this tv show it's called rick and morty and this specific episode is from some episode that i think explained very well or shows very well what we do in stark recursion so there is this crazy scientist trick and he has the he has his spaceship and spaceship sorry and the spaceship gets broken and the problem is in the on the engine and it turns out that rick has built a full universe includes many many green

creatures that all their uh purpose in life is basically work to run his battery and those creatures so rick finds out they realize that at some point and they create their own universe to run the battery for them and this universe at their turn they created their own universe to run this battery which they have to run and you understand the basic idea here so the same goes with recursion so what is recursion basically this is what we got used to do so far we had an original program we wanted to prove we proved it and then we had some verifier program that verify

the this proof verify the execution sorry and but this verifier is a program by itself and because it's programmed by itself you can also generate a proof not for the original program only but you can also generate the proof and prove the verifier program running itself right so instead of verify the proof of the original program you can verify the verification of the proof and you can even prove the verification of the verification and so on and so forth so every every um box in this diagram is a different program that you can prove and you can do it

many many many times and this is basically what we are doing this is basically what we call stark recursion okay i'll give you a second great so now we understand what is recursion but why why do we want recursion what does it help us with so do you remember that i mentioned earlier sharp well you don't have to do once you proved programs in recursion you don't have to continue the recursion on a single program you can also take for example two verifier programs that were verifying different programs and prove them

together so you can do this in this uh phase where you take two different verify programs and prove them together and here is some motivation so if you have in the original program and the original program took uh two steps to run then it will roughly take also two steps to prove okay but if you now proved it the verifier program you if you remember we mentioned it earlier the verifier program takes around log t step to run and though and therefore also log this step to proof and we can use that here is a hint of how we can use that and i'm going to give a couple of

a couple of examples of where do we use it in recursion why why why it's so helpful okay so the first one is about gas cost and proof capacity here is a problem that we have today we have some very large computer we have a program to take t-steps and this computer happens to prove to be able to prove maximum t steps so today if we have two different programs that has each t steps we can't prove them together on the same machine what we need to do is to generate a single proof of program a and a different proof of program b and this means that the amortized gas cost per transaction in every program

will be basically um will be blocked by this uh capacity meaning if if verifying the proof cost five million guys and this capacity of t let's say it's t transactions that i then i can only go as low as five million divided by t transactions which is still good but we want to do better so here's how we can remove this barrier what if we instead of proving every program separately and then sending it to the chain we would prove every program separately but then we will take two verifier programs and prove them together now most of the times uh t will be much larger than two times log

t which enables us to basically take pro take those proofs we generate for every pro for every program separately and generated a single proof that goes on chain and now we can do two t steps for a proof that goes on chain but it gets wilder right because we don't there is no reason we will stop at two right we can do it also for four and so on and that means that in this example i now we now manage to do four times the number of steps we previously did which is amazing um the next thing that recursion improves is latency and this is this is less straightforward so here is sharp that we mentioned

earlier now normally what happens is that let's say starknet generated a block and sent it to sharp and then later on a different program sorry generated a different block of transactions send it to sharp and so on so sharp waits to get all those jobs it might take some times sometime and then once he has enough jobs or there is enough time that elapsed then it can generate a proof so you wait twice you wait for all those transactions to be included and then you wait again for the proof to be generated now with recursion we are not we are not bounded by this anymore because what we can do are two things we don't have to wait

anymore which is very important we can take a job the moment it arrives and start proving it and we can also prove things in parallel meaning if you got a job from sorer and a job from starknet we can prove them at the same time and we can unite different recursive jobs while we are getting more and more jobs into star into sharp so eventually while we are waiting for more jobs we can basically prove the existing ones and once we decide okay we have enough jobs or enough time elapsed we only need to do the late little less recursive step and we are ready to go and release it to the chain so the latency drops a lot with recursion as well

which is amazing okay another topic which is a bit separate from recursion but i think it's important to mention here is that one of layer three now this uh this uh picture that you see here it says two things one is that i draw the layers differently than most of the world because i like to see a theorem on the top and then all the layers beneath it and the other thing is that you don't even have to stop at layer three that you can go to layer four and so on and so forth so what is layer 3 here is the basic idea up until today what we are used to is that we have only serum a solidity verifier

and we have some layer 2 on top of it of it and what it means is that this layer 2 generate blocks with transaction and those transactions are being proven and the proof sent to the cut to the solidity verifier but in fact we are not we don't have to just uh end there we can take the cairo verifier program that we mentioned earlier for the recursion and deploy it on starknet and then we can take any other program in the world let it be another stark net program or or a different stark exhibit program or even an a different implementation in cairo of any vm so it can be a ck vm or an orbit vm you can take any vm in the world implement it in cairo and then send prove it and send

the proofs to the cairo verifier on layer 2 which is amazing and i i'm very curious to see what other kinds of chiro programs and vms will appear as their threes over the year and the benefit here is that those number three they can have their own zones so they don't take for example air to storage but they can still communicate through layer 2 which is much cheaper than communicating through layer 1. so it can be an interesting universe where people deploy their evm contracts on one layer 3 and running their statics transaction or another and so on and so forth okay one last point which is a simpler solidity verifier and

i will give a very specific example so in cairo what we we have what we call built-ins um built-in is basically a more efficient way to represent a specific function and when i say more efficient i mean more efficient to prove than just write it in cairo directly um but every every such i'll give an example a ketchup hash function if you want it to be proven uh more efficiently we will probably want to have a built-in for it and a representation in error for those of you are familiar but um there is a problem here and the problem is that once you work on such a building say catch a built-in now if you want to add

it to the existing prover then you need to add it to the solidity verifier and in starks it potentially means that you have a more complex reality verifier because you have for example more constraints and more computation to do on the very far side and we don't want that we don't want to pay more gas for every new building that we had so we recursion let us do this which basically means that now the solidity verifier can still stay as simple verifier doesn't need to know anything about those constraints um and we only tell the constraints to the verifiers in the higher level of the recursion so what it means is that we can now introduce more built-ins faster

without additional gas cost and without adding more complexity on the solidity verifier we do have the all the work on the cairo side okay here's the example with a keychain um i want to die i want to give a little bit of like some numbers and talk about optimizations i won't touch too much uh i won't go too much uh deep into this because i only have five minutes and i wanna also leave some few minutes to questions so here are some news uh the first version is going to be live in production in less than a month and probably it's not

a commitment but most likely on the second week of august if everything goes well and this is only a very first version that works in production so it's not just highly optimized but even that even though you can still get up to eight times more transactions in one proof and you can reduce latency for transactions in approving up to four times now those are like just numbers that we work with our current setup i think those are like conservative numbers but you won't always gain them it really depends on the load on the system but nevertheless it's still i think it's still very impressive okay optimizations

um i'm going to talk about two optimizations one is what we call flexible ash commitment and if i have time also about state updates and data compression um i just wanted to mention that those are like just two optimizations out of probably more than two that we will apply and the way that we currently work is that we think on optimizations and trying to improve our recursion then we recourse better and then we try we repeat one so it's a loop it's not a recursion here um okay this guy i i think is mr pederson and he is the one

it was hard to find his picture he's the one supposedly invented the pedersen hush which is a great hash to prove but it's very slow to compute on the other hand we have the hashes that people know and are being have been using for several years now so one example is blake which is very fast to compute on your computer but it's not very efficient to prove and what we have today basically in the prover we have a computation for a commitment tree which if you don't know where it is it doesn't really matter right now but it means that we compute many many hashes in a miracle tree all of those hashes are of type black and what we want is to replace some of the hashes

in this tree with a pederson ash instead of blake so basically this right um and why why do we want to do that what do what do we gain so here is what we get in a second i will talk about what we pay what we get is a more efficient cairo verifier program why because what a verifier does it doesn't really uh go over the entire tree otherwise it wouldn't be succinct instead it peaks or it randomly picks some paths in this tree and only verifies them so for the verifier taking for example 22 out of 32 levels in the tree will

affect in potentially very large saving on the verifier program side when you want to prove it which is great but now you will ask okay but you pay something on the prover side right which is true i do pay something on the prover side because let's take an example let's say the 22 out of 32 levels on these three are pederson and the rest are still blake so you would say oh you look at this area of those triangles it's very big and it takes a lot of the computation for the prover but this is this is a misleading picture is right here because the miracle tree looks more it's even more extreme i just couldn't i couldn't draw it my drawing skills are

poor but it's more extreme than this every layer is double the previous layer so if i take the first 22 layers of the tree right it's only about one out of thousands of hashes in the tree which means that even if i pay let's say i pay 1000 time i don't know what are the exact numbers but let's say i pay a thousand time more for every pedestrian for the prover to compute over blake then in this construction which is just an example i will pay only two times on this entire tree and only 1.2 extra over it for the entire approver so i saved the verifier a lot let's say a factor of three or eight or something in between it really i don't

want to get into exactly why it saves more than three um but for the prover only cost a little so overall i get a speed up which is uh in fact surprisingly pretty big speed up okay i don't know if i do i have time to one more optimization okay i'll go for it um i'm i'm going to run it very fast if you didn't understand me you can come to me later with this so today uh there is still some cost with every uh recursive leaf if you want a recursive job and this cost is because every job separately represent state transition and separately represent

includes data that has to be published and today it means that even if i do like the most efficient recursion i can only go that much to how much how low or how small every job can be and i want to remove this this limit so just to to make it more clear here it means that if i have three different leaves in the recursion tree i'm gonna pay three times for store on ethereum and three time published data which might include similarities what i can do is i can in a complex way that i didn't get into here i can

change it to only store the total state diff state transition sorry and only store the only publish the total statistic of the data and i think this is also an important improvement that we will have so here all the topics i touched i think recursion is great it brings a lot of changes and improvements to our systems a lot of new capabilities product version in production on mainnet is coming mid august and there are many many more optimizations on the way and as i said recursion is great thank you very much [Applause] are there any questions i don't know if

we have time but yeah you hello you thank you for the talk you mentioned this uh really important assumption that if a computation takes like around t steps the proof is like at most t or like around t or so does that hold like what can you tell more about that is it an average are there outliers it's it's not really there is a factor there this factor can be sometimes 100 sometimes can be 1000 it really depends on the computation there are some computations that are very hard for the for to prove for example if you take a ketchup hash it doesn't have a structure that you can use but i'll

give it like the other example is if you take um peterson it has a lot of algebraic structure you can use and it really varies a lot so on pederson maybe it will be i don't know what 20 40 times let's say 40 times more than the computation and ketchup it can be over a thousand so is that like a big limitation because when you're doing the recursion and you start parallelizing the proofs you're still kind of blocked by the slowest one right so if you have an outlier like correct so eventually it's it's very good questions what we do eventually is we have some limits on the size of every job at the at the beginning of the tree and basically every job can translate to trace sales or even cairo steps and

we we are targeting every job to be more or less the same size and not too small not too big got it okay not too big because we don't want to delay everyone all other jobs are not too small because if you go into too many too much small jobs then you will end up having the job smaller than the recursive step cool thank you okay thank you very much [Applause]