Beyond Ligero and Brakedown: Building a Fast Prover Based on List-Polynomial Commitm... | Devcon SEA

[Music] hi everyone so today we're going to talk about how to build provs uh this is a joint talk with my colleague aam and um yeah um the main purpose of the talk is to see how we can use list polinomial commitments and we're going to create something based um on Lio and breakdown which are two pre just works uh so just a quick word about us uh we're both cryptography researchers uh at consensus uh and we're working in the linear pro team and since you here you probably have been hearing all this time how to make proofs how to make proofs we want to make proofs um and this talk this intermediate cryptography talk is about how to actually uh do that mathematically and how to construct a system so we're going to dig into some details some mathematical details but we're going to do that hopefully in a way that carries information across to you so just some motivation um at the high level we're interested in how we can move from a evm state to another one uh there is the eternum virtual machine State transition um that basically explains how that happens and what happens in the layer two rollups is that that this state transition is being arithmetization happened properly and why this is useful is that not all nodes will have to perform the St transition themselves they can just verify the proof and since verification um will be by design a very cheap operation uh the overall system is going to um to be quite efficient and as I already um um as I already um prepared you uh we're going to look into how to construct such a proof system there will be two parts in our talk the first part will be uh the polinomial commitment scheme um which we call Vortex and the second part will be how to use this pomal commitment scheme some other Machinery in order to um reason about the evm execution so let's deep into cryptography uh with polinomial commitments um so basically like these two parts um are the main building blocks of how to build a snar so po polinomial commitments uh first you're going to have just a setup algorithm and um at a very high level it's just going to give you some public parameters so public parameters and if you want to commit you're going to use these public parameters you're going to use some polinomial you want to commit to a polinomial this polinomial will have some bounded degree K and you're going to out output some commitment C and then we want to reason about this polinomial about this commitment that we just made and basically we're going to look at a protocol that's interactive between a prover and a verifier they both have access to the polinomial to the parameters to the commitment and in the case of the prover also uh yeah also the polinomial the verifier doesn't know the polinomial only knows the commitment and the prover basically attempts to prove that P of X is indeed equal to Y and this happens over multiple interaction rounds um very high level the security condition that we want to achieve is that the approver should not be able to convince the verifier in the case that he committed to something to some polomia that actually does not evaluate to to the claimed why and we want to do this efficiently we want to amortize our costs so basically we're going to do something called batch polinomial commitments in instead of committing to only one polinomial we're going to commit to n of them uh we're going to have we're going to claim n evaluation n evaluations and basically the proof is going to be a badged proof a combined proof that all of these polinomial evaluate properly and also the verifier now knows the evaluation um the claimed evaluations and let's look into the math that we use in order to build such a thing um these are called the read Solomon code code and without getting into the nitty-gritty um we're going to use a finite field fee F uh if you don't know what a final field is just imagine uh uh integers modulos some prime p and we are going to take some subset of n elements A1 to a n from this final field then encoding a polinomial so this is about the codes ining a polinomial we just be evaluated the polinomial at this end points and in order for you to actually in order for this encoding to actually Express information about the polinomial um you want that the degree of p is actually smaller or equal than n uh in order to be actually be able to express it uniquely and in fact you want to have this n is going to be much higher you want to have redundant information about the polinomial in order to error correct um and now let's look at the uh what we uh where we took the the starting point where we took inspiration for our work uh which is the Li breakdown protocol um these are two separate schemes but um uh they have a very common structure so in this previous work the setup algorithm would give you a hash function as the public parameters and then in order to commit to n polinomial what you're going to do is that you're going to you're going to first compute the encodings the r Solon encodings of the N pooms each row now corresponds to an encoding you're going to construct this Matrix and you're going to apply a hash function on each column in order to get H1 then you apply the hash function on the second column to get H2 and so on and this is going to be your commitment your commitment is this hashes of The Columns of the encodings uh of your polinomial so that's how you commit and I put this here in case you forget it uh now we also interested in how do we open how do we actually prove to the verifier that uh our claimed devaluations are correct and in a secure way so basically the verifier is going to send the coin beta to the prover the prover is going to compute this looks like a complicated equation but actually it's not it's just you have each row and each row gets multiplied with the power of beta so it's a linear combination of the rows with this beta that comes from the verifier this is a vector U send it to the verifier the verifier now picks an index that it wants to check it's only going to be able to check one send it back and the prover replies to the column of that specific index in this case this is the first one the verifier does two checks it checks that indeed when it applies the hash function to the opened column to the one that we just revealed it is equal to the one in the commitment and it checks that indeed if you compute the linear combination of the betas with the revaled columns then you're going to get the I coordinate of U in this protocol is going to ensure that all the rows are indeed code words but we want more than this we want to actually make a proof about the claimed evaluations of the polinomial not just show that the rows are code words and what we notice um in this work is that if we interpolate this Vector that is sent by the prover to obtain some polinomial and then we also check that this polinomial evated that X is equal to the linear combinations of the Y's if we do this additional check you can actually ensure we can prove that the polinomial is evaluate properly and um this proof can be very simple if you are in the unique decoding regime which I'm just going to talk about next um the point is that if you want op if you want optimal parameters the proof becomes very complicated and I'm going to give you just a flavor of why that is um so basically when you're talking about codes you you can consider two cases there is the unique decoding which in this case is exemplified by this radius this is the target Vector that we want to decode and this is a radius around it and as you can see if you set it to this length then there is only one code word however you can also consider relaxing this op this U this parameter to be able to include multiple points that are candidates for your decoding and the proof for our polinomial commitment schem becomes much more complicated if you want the optimal parameters if you want to have something that's efficient in practice so as I said the small one is the UN coding regime there's only one candidate and the yellow one is the least one multiple candidates um so the security guarantee in the that we show in the listed coding regime is that there will exist polinomial polinomial a small degree that evaluate correctly and this commitments will have only a small amount of coordinates that are different from the target commitments that we are decoding um and if you want more details for the proof of security you can check out our reprint uh and there's also thanks a lot I'm going to now now we're going to move to the second part of the talk where we're looking at how can we use this pomal commitment to um in conjunction with other things to reason about the evm and I'm handing over over to my colleague aam thank you B uh so uh let's go to the second part uh how uh and here we are focusing what is happening on Layer Two linear and how we generate proof from evm execution via such polinomial commitment uh there are a lot of Step until we can generate proof the first step in this journey is arithmetization and arithmetization for us is mathematical modeling of evm by columns and constraint between columns for example if you want to prove that a transaction had a valid signature first you hash the signature so you have to prove that the hash was correct so if I want to here to show that hash of is y I start with column X and column X is a kind of a describing your input EX for example you can consider the bite of the X which are splitted in the cells of these columns then which uh with each steps of the uh computation that is happening in the hash uh this column you would have a new column with new values in the cell and so on until that you would arrive to column Y which is your output and there is constraint between this column to say that uh how the computation of the hash is going on so by this arithmetization here you we get bunch of columns and constraint between columns uh there are different uh constraint uh for example it's just uh example here there are more uh Lop constraints or Lop query we Alo can say which says uh column o is included in column B uh or local constraint that says okay if you have two columns then uh the first row of these two columns are equal Global concern which are very important for us and uh they are more about cells uh the relation over the cells of or the same column or even between several columns uh I'm putting an example here for Fibonacci sequence for uh for this Fibonacci Sequence we know that for each cell is in fact addition of two previous cell so you write the constraint like this for this uh and we call this one Trace uh trace of execution or fibon okay if you want to verify this Con constraint as a verifier definitely you don't want to do it uh like this because it's too many effort especially Global constraint because they are over the cells and you have to check a lot of uh relation between columns and cells so and that's where uh uh polinomial commitment comes to rescue we write each column as a polinomial uh we interpret the column as a polinomial for example you can say that okay the values in the columns you can see them as the coefficient of a polinomial and by this the constraint would be translated as a relation between pols and from here you can apply polinomial Comm commitment I want you I remind you that polinomial commitment can do two task for you which are very simple but very important one task was it can commit and by a short commitment and you can use the commitment uh to open to request the evaluation of the polinomial uh another interesting uh property of the polinomial is that why we are interested in polinomial and why we are going from columns to polinomial is thanks to this LMA Schwarz Zer LMA and it says that if you have a relation for a polinomial between polinomial commitments you don't need to check the relation for each ex you just take a random point from the domain and if the relation over the random Point Alpha satisfied then you know that it was satisfied for every ex this would simplify everything and that's why we are interested in polinomial because by this verifier uh task is very easy it just needs to take a random point and then verify the polinomial and constraint over this random Point uh so by this so we can get now uh pols a bunch of polinomial and constraints we are very close to get the proof but we are not still there and the reason is that these constraint are not the constraint that uh I want uh the constraint that we are interested in are Global constraint why Global constraint because uh thanks to this Schwarz Zer Lemo uh you can verify them easily uh Global constraint are between cells so you don't need to check them between cells you use short zielo over global con straint and you just check in a random point so we are interested to kind of reduce this constraint every constraint that you have for example Lup queries permutation queries and a lot of queries that may happen in during arithmetization we want to replace them with global constraint because from there we have we can have a simple verification uh via short Z LMO to do this to go uh to get global constraint we need uh piop but what is piop piop stands for polinomial interactive Oracle proof uh it's a idealize ideal modeling of a protocol between PR and verifier uh you have a SE party between prover and verifier uh this uh handsome guy uh that we call it Oracle Oracle is honest and can answer any question so prover and verifier start their interactions and they use this uh Oracle to help them to reduce their constraint uh to Global coning and uh there is a theorem that says that polinomial commitment in such construction uh resemble to an oracle because Oracle does not exist uh such guy does not exist unfortunately so we have to replace it with something real and there is a theorem that says that polinomial commitment is a good candidate and you can replace it with this guy to help you to reduce your polinomial to constraint to normal to Global and now we are fine so we use piop we reduce everything to the global constraint and we can use a polinomial commitment for this but we cannot use our Vortex and the reason is that our Vortex is not a standard polinomial commitment that and the theorem is not true uh it's not a good candidate for Oracle uh why it's not good candidate it's because of this uh property least property uh why it makes problem why it cannot work with piop and the reason is that in piop you have rounds of interactions between prover and verifier and uh in fact due to this Leist property polinomial has a lot of choices in different rounds and he can do kind of mix match attack between different rounds and different polinomial from the list uh but we have a trick for this we uh can prevent uh in in fact we use a trick to force uh which we call it Comet separately and open colal ly and by this uh I don't go to the details theoretical details but by this trick we are uh we are able to force the prover in fact to open uh all the uh polinomial commitments at the same position over the D skill let's say uh so for the first round maybe he has choices but for the other rounds he doesn't have choice and he has to stick to the First Choice uh so this would solve the problem of list but still Vortex is not good one more step and why it's not a good it's now because this nice property I I call it nice because it's batching but batching uh uh it's not an uh General batching uh as you see in Vortex the batching is just batching of all the pols over the same point uh and in the real application poop applications when you applied your piop in fact you are in the general case that you have many polinomial many uh points so this kind of batching even though it's nice but it's more fantasy and it's not applicable here uh but we also find another theoretical trick to solve this problem still I would not go to the theory just uh uh the general view is that we come back uh to the step that we designed our poop uh and we kind of modify it to be able to use batching over the same point and the way that we modify it uh is just uh first they uh convert uh can speak freely and at the end we apply uh a kind of reduction via Oracle over the same point and from here now Vortex is applicable we can replace our Vortex with Oracle and we are done finally we have our first proof and here is just an example of the parameters if you are interested thank you very much thank you very much uh I love the dynamic between the two of you explaining the different SES it was cool uh we have some questions and uh also some that I had sorry I also introduced you wrong I said you're from the prover team of consensus and then I was like consensus doesn't do proves so from the Linea team and I guess that became clear immediately but yeah so one of the first questions was uh is this the vortex that line uses uh yes uh this is the first proof uh that's why I mentioned that finally we have our first proof this is the first proof that we generate after there are a lot of more layers that will come to aggregate the this initial proofs and uh finally a final proof to be compatible with uh ethereum uh but this is yes this is the first proof that we generate in lineal and the classic uh any benchmarks how fast is it Benchmark was uh because uh as I said this is the first proof so we have uh several kind of recursion and uh our estimation is that uh you need uh for 100 bits of security you need 15 millions of constraint uh inside of for the verifier of Vortex inside of plun and uh comparing to breakdown and liero that are in unique decoding uh this is four times fast the not faster but the size of the proof is four times smaller nice so I think this uh question comes up or well this might answer the next question in part at least so what are the advantag ant ages disadvantages of Vortex compared to other polinomial commitment schemes so in terms of pro time proof size you mentioned with proof size already but uh yes I mentioned about proof size that uh is a uh faster than breakdown smaller than breakdown four times due to due to the least uh commitment property and regarding the Prov time uh uh um both are uh good I mean it's as good as buron but it's also I can compare it with a fry for example because uh Vortex it's very important property that it doesn't need thrusted setup it's like fry and uh comparing to fry the prover is faster yeah good so a last question uh is batching over the same point does it impact the security uh that's why we went all through this uh uh modifying poop and modifying distri of uh commit separately open collectively all of this was for the SEC uh proof of security so the paper in fact analy the security that okay it's not a standard commitment so how can we use it uh securely nice I see maybe one more question came in as we have two minutes left for questions maybe we can can uh scroll and see I actually left my uh phone okay never mind what question would you love to hear pick your own question H what field do you use uh uh in fact the only property that we need is because you uh uh we use fft so the only property that we need is to add city which means that the order of a uh if your field uh is uh Q uh the prime that we are using Q minus y should be a big factor of uh two to uh so if you have this property it's enough for us after uh because we also have used uh it's a a ltis for the hash for hashing of the columns uh so we may for optimization can we have uh more choices in distance but already this the this fact that we just need to add the city is it would give us a big Choice nice good and thank you to whoever upvoted the question so we could read it collaboration at its finest so let's thank the speakers once again um thank you and yeah catch them if you want to know about L's Prov thank you very much bye uh