Order Preserving Lookup arguments

Transcript

[Music] Uh hello everybody and I'm very happy to be here. Uh today I'm talking about order preserving collateral lookup or we call it projection query. Uh I'm Azam and I uh work now three years at consensus. Uh we work in linear team layer 2 scaling solution developed by consensus.

So what happened between in layer two and between layer two and layer one uh on all the story start from arithmetization. uh on layer two uh you have EVM uh bite codes that arithmetization would take them and uh kind of uh convert them uh to columns tables and constraint between uh tables between these columns. These tables then they are input to the prover where I work and uh we generate the proof from this table and uh the proof is sent to the layer one as a transaction. There is a contract on

layer one which verify this proof and if it get verified uh it means that the everything on layer two was correct and the state can be uh transit to the new state. So as I mentioned arithmetization is a mat matical modeling of EVM behavior in the language of columns and constraint between these columns. For example, if you have function H which receive input X and the output is Y. So you start with a column X which kind of uh encode this uh input. Then you have intermediate columns which in fact depending the

operations that are happening in the function you go uh you continue until you arrive to column Y which is the output encoding of the output and then there is this constraint between the columns to show that the operation the mathematical operation uh that function is carrying on done correctly. As a simple example, if you have bunch of transactions uh that uh this transaction the balance uh uh the value uh they are stored in some columns like this and uh when you send a value to another account. uh the way you get your new new uh you understand what is the

new balance is this by this constring that okay I have the old balance I spend this value to another another uh account and I pay this gas that I should reduce from my old value my old balance and then I have this new balance a more realistic example is what is happening on linear is about hash hashing of the uh RLP of the transactions. For example, here we store the RLP of the transaction in a column which is called limp and uh as you see uh hash number six all of them uh related to the same transaction. And

then you have another table uh down that shows that what is the result of the hash for for example hash number six for transaction six. We have different type of constraint. Uh the most common one are lookups which means that column O should be included in column B. Uh I would come back to this uh uh special constraint because it's the topic of the talk. You have local uh constraint which means that uh uh if you consider the first row of the columns then you expect some constraint between these elements. Global constraint which uh kind of uh true

between all the all the rows of the columns. Here you see that I expect uh for example uh at uh row i should be the sum of row i minus one and row i i i minus 2 and more more uh constraint like permutation and even custom constraint like hashing. So let's uh focus on lookup tables or lookup queries. uh here you see uh this example that we expect in fact that s be subset of the t that's why I show it with s uh s is a a subset because it just has two and zero and two and zero are inside

of the t so s is included in uh t it's a positive lookup but for example s prime is not so it's a negative lookup because 32 is not in the t is from zero until So as a positive lookup between S and T and as a prover I want to prove that indeed S was in T and I'm not lying. How we check it? Uh the first thing that we do is that we uh generate a new column which we call it multiplicity column and you say that for each uh element of the T how many times it has happened in S. For example, you for zero

you have five time in s and for two you have six time and the other zero. Then we uh generate extra columns which what we call them accumulator sigma and t sigma and they just uh accumulate the element of the s in a special way. For example, uh you accumulate a uh element of the s in a fractional way here and at the end you expect that the last row should be equal. Why uh this should be the case? Because here in the accumulation of the S you just accumulate all the element of the S and the other side you accumulate the

element of the T but considering their multiplicity in the S which is the same thing. So they expect that they should be the same. Uh if you open the last row it should be enough applications in many uh teams uh when uh they write the constraint because EVM is a very big uh very complex system. Uh so you have kind of a lot of modules which do a lot of different taskes and each of these modules I can translate them to tables.

uh and sometimes you want that okay uh I want some elements from this table to bring them to another table and do extra operations so I want this columns these elements from these columns to be included in the other one it's a lookup I mean they what they use is a lookup but there's a security consideration concern here and the reason is that okay I may in the second table I may add new elements which are not from nowhere. So how do you guarantee that I don't cheat and this data are really from the previous columns previous modules or another way to cheat is that you change the order you can change the order of

the element for example here you see that it's pink blue pink blue but the other side it's not the same order and u maybe I cannot immediately say that what kind of attack the adversary can use here apply here uh but definitely you should never uh leave the door open for the attacker. So what we believe is that we need a kind of bilateral relation to uh for example uh prevent this adding new elements. It should be both side that okay whatever I have in this side I have the same the other side and vice versa.

And we also need order preserving to be sure that the order of the element was not changed. Uh the way we do it uh regarding the bilaterality we use two columns that we call them filter and we just say that okay I expect that in these positions it should be exactly the same as the other column. Uh whenever you have you expect such thing you put one and if you don't care you just put zero. So in the when it is one it should be really the same as the other one the other table regarding the order. So it was for bilaterality and like this you could not uh add new new element regarding the uh

order some teams are they are adding a new column that they call it uh order column and uh they say that okay what what order I expect and then they apply lookups. uh this can works but of course you need to add this extra columns to uh specify the order that you want. Uh what we do in the prover team of linear is something that we has a direct query. we have uh projection query uh and the way that uh we uh ensure the order is uh we we do it during the acc uh building this accumulation uh accumulator columns because anyway you had it even the

lookup in the lookup site. So uh we um we impose the order dur during the accumulator accumulation by adding this uh random element alpha and whenever your filter uh is one the the power of alpha would increase and by this the order is preserved because if you change the order the power of alpha would not be the same in the both side and then at the end you again similar to lookup you just need to open the last row and check that the last are uh the same and by this you are sure that uh the element were the same the order was the same.

So to give you a visualization I can say that projection query is like a uh one to one arrow between these columns something like this while lookup is many to one and it leaves a lot of open space for the adversary as I mentioned you can have projection query prop security that you expect in fact from projection query you can also have from lookups but you need to add more columns while in projection query you have you have it with less columns.

Okay. Uh what I mentioned here is that uh you just need to check the last uh row. But how you are sure that uh accumulation was correct? Okay, you accumulate until that you arrive to the last row. But how you are sure that the accumulation was correct itself? The way the magic comes from polomials, polomial commitment more precisely. In fact, we interpret each column as a polomial. For example, you you can say that the elements in the columns are the coefficient of the polomial as a simple example. And by this uh the constraint between columns would be a a relation between polomials simply.

And then you use polomial commitment. What is the polomial commitment? Uh you commit to the polomial which is a kind of digest of this polomial and rep represent your polomial in a very short way and then you also can open your polomial in a given point and prove that you your evaluation was correct and also the proof is short or succinct. So what I want you to remember from this slide is that the commitment uh which is a kind of represent your polomial is short is succeeding and also the proof of opening uh proof of evaluation is success and the magic the next magic comes from short zipper lema uh because it says

that if you have a general relation between polomials uh uh over a big domain for every x for example Here you just can evaluate take a random element from the domain like alpha and you just evaluate the relation for this single random value and if it is satisfied you are sure that it was satisfied for every so how these things how these two two tools help you this commitment succinctness and this dilemma because now you don't need to check the relation between for the accumulation. You don't need to check that for every row that okay it

was really the accumulation so far from the previous line. Uh you just uh check the uh by short zipper you just check it on the random point and you know that the proof was uh the proof that you are saying that I evaluated in the random point is short also it's succinct. So this um this is how you prove in fact your projection query was done. More uh applications of uh uh projection query as I said projection query the first time we uh design it due to that this security concern that we had that adversary may add new data or change the

order. uh but uh later we unders we just uh came up with more application like like column rotation that for example you have here a column uh a row that you can rotate it and it would be the uh column in the other table and you prove uh that you have done this correctly this rotation it is really rotation of this row where we are uh regarding this query and in general in prover now we are in the distribution f phase which means What does it means distributed prover? uh for the moment provers are like a very heavy machines uh that uh take the all the trace uh and when I say the trace for us it's like

big tables a lot of big tables uh and they have to process these tables and generate the proof based on these tables but these tables as they are a lot and uh very big uh so the prover is a very heavy machine what we aim for is that okay instead of one big machine I have a small uh a bunch of a small machine and I break this uh trace in this uh sense of the table to a small tables and I give each part of the table to uh one machine and by this they can process even the bigger traces. So it increased the efficiency uh noticeably.

This is the architecture that we have really uh and as I said in the sense of the query uh when you break your uh tables to two tables then you have to say that the relation was true between all these tables together. Uh thank you and uh thank you for listening to me. Uh if you have any question I would be happy to take any questions.

All right, let's give an applause again. Thank you.