STARKs in SNARKs Jordi Baylina

foreign [Music] that's how we are a verifying uh a stark with a snark as I explained it before in the panel the last piece of the of the of the proverb is mainly converting we have a stark and then we want to prove that on chain and what we do is we create a circuit that verifies this start and then we we prove it in in in the snack okay um well this is uh well this is the the KVM that we're building mainly we are using pill this polynomial identity language to build out the full system and at the end what we have is a set of polynomials with a set of identities that needs to fulfill with this can generate automatically the idea of this is that once you have this pill you can generate automatically a stark and not only that that uh with this with this Stark you can also automatically generate a start that verifies that that that other Stark okay so we have our recursion Starks and you can we can do that many times and we can even aggregate uh we can even Aggregate and then we can build a system that looks something like that we can have many proofs of many blocks and then we can pack them together in a kind of a tree and then at the end in the last step before before sending to the ethereum we just convert this Stark to the snark and this is this is done quite automatically so you need to care just about building the pill and the rest is quite uh straightforward okay so let's see how how we do that okay so what we want to do is we want to build a circuit actually we want to build this uh circum circuit that as an input you have a star proof okay so this is the start proof so in the circuit you have to validate this star proof so we need to dip in what's inside the star proof what what's what Circle what means this of a star proof well the first thing that one things that you have the first thing that you have is uh you have the transcript transcript are mainly hashes okay so you need to have these random numbers that goes back and forth this is something that we need to compute inside the inside the circuit these are mainly hashes okay as a transcript in this case we are using uh well a hash function in this case we are using uh for the Stark we are going to start with a hash function that's a fairly hash function in this case a Poseidon with a BN Corp we are just using this hash function to compute the to compute the the the randomness the of the of the transcript okay another piece is well if you have a polynomial evaluations and then you need to check uh you need to check that this polynomials evaluations are are okay that they are fitting that means that you need to do a lot of arithmetic and in the case of us we are using the Goldilocks brain field and but here we are in the BN so we need to work with this cross Prime field we need to do this cross brain field operations so we need to do cross Prime field inside the inside the the the inside the inside the circuit um the next thing that we have to do is we need to do openings okay so the start mainly is a miracle trees and we need to just validate these Miracle trees here the trick is again use the Poseidon hash function so if you use a position so a snack freely hash function then doing that that inside this inside the circuit is relatively cheap so we do that uh for the for the openings itself okay once you have the openings you need to evaluate this opening polynomial which is a derivative polynomial you need to evaluate those openings at that point okay so you need here more arithmetic operations okay and finally we have the fry okay fry is openings again so lots of openings that's one thing so every time that you go to us back in the step you do on uh you do openings so this is again Poseidon uh here and then you have to do polynomial evaluations but this is our in the cross Prime this is in the Goldilocks Prime field okay the best way to do a polynomial evaluation is mainly doing an fft kind of a kind of an fft okay so and finally in the last start we also need to do uh um an fft for the for the final polynomial that we need to check that the final polynomial of certain degree mainly you do an fft and check that the half of the or that part of the bits are zero okay so this is a structure of the of the of the star so here the I'm going to jump this so here the the well the the the trick here is how much so how we do this cross Prime field operation this is probably the most uh simple thing and the idea is where we are just doing in a naive so in a very naive way okay so we just uh if we're doing an operation like that like a multiplication uh in this case is uh well we just do a couple of uh rain checks okay that means that uh more or less uh Prime cross so a multiplication with a goldview locks multiplication it costs 146 constraints okay the fry and this is a one one thing that's specific on the fry the Goldilocks is a very small Prime field so uh once you work with a random number you cannot work with the base field because it's very small so you need to work with extension Fields so you work with extension in this in our case we're working with an extension three of the Goldilocks okay so that means that doing a multiplication in the extension field three this is uh something that's 400 400 438 constraints which is a lot you know compared to one but it's not that much okay so here the thing is okay let's let's do some numbers of some examples of some Starks uh how it would look like okay well this is the the the for the hash functions we are using a 16 inputs so we can do uh trees that goes at four at four and then a constraint is just 612 constraints just doing a single hash which is quite optimal uh if we do it in that way okay so let's put some example this is these numbers are not exactly but are similar to the ones that we are using for the ckvm circuit in this case we are talking about let's talk about uh 1000 polynomials okay uh we have a let's do a blower factor of two that means that we need to do a lot of queries in the in the in the snark in this case is 128 queries uh this is we have that it's important this raw factor of two because if you go for example lower factor of four that means that we are doubling the proving the proving time okay so we need to go to the minimal especially when we have so many polynomials here so that's why we use a row of factor of two okay so let's talk with uh sides of a polynomials of 2 to 24 after the lower factors so 2 to 23 to 224 okay and of course we have constraints let's assume that the number of constraints is more or less the same number of polynomials this is just uh just uh subjection and then we have in each constraint we have like two multiplications for each constraint okay these numbers of course depend on the circuit and depend what you're doing and so on but this is just would say it would be a good example of a zkbm circuit-like okay it's a big circuit okay so for this is okay here let's see how much boot it costs this uh in in number of constraints here of course the transcript is not that much the checking the polynomial constraints uh uh at the random Point well it's start to being an important number but not that much uh the number of queries we have so many polynomials so we need there are so many polynomials so mainly what we do is a linear hash of the evaluations and then do the miracle lights but this is this is just for the the queries the first query is not in the fry yet but for the first queries of all the polynomials this is our DOT and here is the big probably the biggest part okay the biggest part is when we need to compute this opening point polynomial there are so many polynomials we need to do so many multiplications out of the field that this is a number that grows a lot okay and here is the the big part of the proof is this 112 Millions what else we have we have the well this is the queries of the fry here are the ffts the the the polynomial ovulations the entities to going deep in the fry and the final and the final and the final polynomial evaluation so this gives us something that's huge is 127 million constraints but it's it's doable this is a circuit that's for example the Hermes one circuit had this number of constraints more or less so and you can do that in about 100 seconds in a big CPU okay so in Rapid snark so that's something that's doable but you know it's going to be a big circuit okay the thing is that with uh uh what we can do the technique that we are using is that instead of having a snark so we have a we have this big circuit so instead of this proving directly with a snark what you can do is you can do different level of different levels of recursion so you can build a Stark that verifies another Stark so you get a proof that's much smaller maybe you you can do repeat that again you do another Stark that verifies the Stark so you get even a smaller proof and at the end you can have a a final proof that can be much much much smaller okay and this is this is actually more or less what we are doing here is here I put you the real numbers of the current structure this is a structure of the proverb that we are running right now in the public test net okay so this is a three steps okay the first step is uh with this number of polynomials but you need to count that this it's about 1000 polynomials but then we have 43 block apps one permutation check but we have different different properties so this is a big circuit we are working with 2223 we'll have a factor of two here you see the structure the way that the structure we are of the fry so we are building the fry okay so this goes to another point so it goes to another proof second proof is a proof that's much smaller it's just uh 20 polynomials with uh sorry 12 polynomials 20 of them are constant uh 10 in terminatory polynomials no block ups just one connection check and uh yep and 23 23 identities and then we do go to the third one this is also you see here it is the GL GL means Road Delux this is a a a stark does ability with Goldilocks but the last one is built with BN 128 okay and the last one is just a smaller it's just 20. it has only 12 polynomials but the and the size of the polynomial is 2 to the this is just 24 uh so 2 to 24. It's 22 and the double factor of 4 in this case we could do it smaller okay but at the end here is a compromise sometimes you you get it smaller but then the proving time of this smaller is bigger so at the end is better maybe to have a bigger last circuit that it's a bigger last circuit than uh that just squeezing to the end through the smaller and keeping uh uh and keeping bigger so this is our balances and checking what's the best structure uh uh on that okay so if we go to more uh something that we can go far so that we can squeeze more uh the last circuit you can do well five can well let me just with something that's 60 polynomials with a blower factor of uh 16 uh so two to the four and uh um this you with this you just require 16 queries which is to having the same 120 128 bits uh um security uh you can go uh polynomial after overload factor of 2 to 24 so we'll be a polynomial of two to a 20 that goes to 2 to 24 and yeah this is our number of constraints and if we do the numbers with this see that the numbers are getting much much smaller at the end we can if we add them all together we can have something that's below 2 million constraints and this is something that can be built in less than two seconds it's really uh it's quite insignificant uh compared to the to the proving to the proving to the proving time so um this is very much the the conclusion I just put this a slide from the ckbm but this is uh the full just to to to to explain you what are the current times of the of the full ckvm improver okay so currently in an uh in uh big machine you know this is a 192 cores uh machine uh it's uh ten dollars per hour machine uh more or less in AWS okay um the this proof it takes nine minutes okay uh we can well you can process four million gas in this proof so this would be equivalent more or less a cost per transaction will be less than a cent so zero seven cents per dollar but you see that this is actually uh it's a proof that's actually running the public that's not is running so and you can see the code and see how the approver works and when you can build your proof uh in there okay this is just a CPU approver and here there is lots of margins to to improve here from GPU we expect maybe one order of magnitude faster and fpgas the new CPUs are doing are performing much better yeah there are a lot of things that that are happening but this is just a a have you want some numbers some idea of where the approving times uh are on the direct question another thing that's not here but somebody already put it in for and is that verifying a growth 16 in evm this is 200k around 200k gas which is probably the cheapest way the cheapest thing that you can that you can do plonk is 300K which is not that much you save the truth so probably it's going to be the options that we will put it in mainnet and yeah that's mainly my presentation I don't know if there are questions thank you [Applause]