leanVM-03: Compiler (Workshop)

Transcript

Yeah. So I think this session maybe like this part but like the goal for this session was more to talk about like the memory model of the machine and everything related to the and stuff. So a lot of very interesting discussion. So as I just mentioned like the goal of course is to prove the aggregation of signature but also to merge some previous aggregation because when you have like you have to imagine like of nodes and some nodes are responsible for aggregating like a bunch of signature

and others would be responsible for merging those proof and at the end a single pro. Um the memory is really only we had like a long debate because originally like you had some VM using read only some other using read write memory but we thought that for our use case which is like quite a reasonable program this is maybe more trackable to have like a read memory and not a readr memory that should be good for material.

for very large program but for a very restricted program this is better. This has also like the advantage to be cheaper to prove and so as a pro cannot override memory then we simplify the lookup work and avoid more complex techniques. Um but like yeah the main challenge there is how do we efficiently prove that the the prover memory operation are valid and consistent. So we have to prove that the same memory address always return the same value that means that if you an access a v is inconsistent with another access a v prime

v should never be not equal to v prime and also the continity. So of access memory address from a complete continuous range and so it should enforce directly this and yeah to to inform this we use lookup. So lookup is a way like to enforce like memory capacity between different tables. So if you imagine that in a very simple way and you should be familiar with that you should prove that there is a link between the tables and some sort and so you have different methods of that. The most common is to run like a

grand product. Uh the ground product is using a product basically because like you have a multis set. The multis set is that you can have on one side of the main tra >> why do you need the second property security property the contiguous >> I I think that this is because at the end like I don't know if you you agree that we should have like a continuous after the first pass I think in they need continuity um because the the way I think they're like an and they are all the memory accesses and

so to make it work they need to to have a continuous memory but I believe in our case you can we don't really need discontinuity even though to be as good as possible as a continuous memory is good for performance >> yeah that was my question like >> I know it's to simplify the constraints like when you have like things like the memory slot one after another one like you can you can substract the addresses and check if if they are one and that's a little bit about strength of the memory.

>> Yeah, I think it's somewhat related to the question that you had this morning during the first pass when you go over this is it possible like to add more checks and to make the memory continues in order to simplify the work that we have to be done there or is it something that >> actually I think in they did this because What they do is that they um they reorder um the the memory and that is an air that asserts that once reordered um you can either have so there is index value index value and um when once reordered there is a constraint that say that either the index should be

non decreasing and that's why they need it but in our case uh I don't think it would because it's like the look of argument is quite different from so okay because in Ko what they do is that they use I think a run product to prove that the index the the the accesses during the execution are the reordering of something else which for which to prove that it's freely they need continuity And so in the end they only use a contradict a comp argument where they they have sorted the indexes and they

need the consu because when it's sorted to to have like an air constraint to that it's sorted it's easy if it's simply non decreasing without any gaps between indexes >> but in our in our case I think it we can make it we can make make it work without And I'm not aware of speed ups that we could gain with continuity. I'm not 100% sure. But the continuity I think is used to to enforce easily the read only property >> because um if the address is matched then uh uh the values should be the same uh and then the problem is if you had

like a variable gap it's like impossible to to ensure that um >> the difference is no longer one. So the multiplication in the constraint doesn't make sense. Yeah, >> you need to like check the ordering relation in a harder way. >> Yeah, you would have to to put like straight that something is different from zero which is like way >> you need to find >> you can do it. We did it in valida. It's just would would be cheaper to to check that ordering uh by address if if you have this property.

because in they they use a permutation check while currently in the implementation it's so in the end they use a product argument and currently we use a lookup argument but it's a bit different I would say and that's why we don't need this continuity >> but you like it anyway because your memory argument makes you pay for the gaps >> obviously we need it for for performance but if there is one little gap It's not that but yes.

Okay. Yeah. Thank you for the question. Um and so yeah the core idea like to to verify this corresponding multis set could be for example to run like a product where like you have the roots and then element that is alpha there and we have like initial binary constraint let's say and then we update the rules line after line in the in the trace and we just check that the final conraint So that we have read all of our product and we know that there is cons consistency sorry between the different tables. And if the product is one, this

means that all of the terms in the numerator cancel out with the term on the denominator and so you go through this. But um this structure is quite rigid and this bring you with a product to run on each your line and so this can be quite costly. So there is another model also there is a problem but because if you are in this condition and there is a multiplicity that means like some values that are used multiple times into one of the tra then you have like this exponent and then you cannot transform that this way. So what you can do there can I go next slide? So yeah so what are we

trying to prove? So, so what is so we saying that you have your the memory trace that satisfies these two properties and your raw unsorted what is the raw unsorted memory trace here that we're trying to like what are the two sets we're trying to show equal >> there are multiple look multiple lookups for instance there is a lookup from the execution table into the memory >> and there will also be a lookup from deposit tables into the memory >> okay I see I see okay I Yes. Yes. So, so like so you're trying to show that like your the execution table is aligned to what what's in the in the execution you will have something like an index column and a value column.

You want to ensure that if the index is three the value correspond to the memory at index. >> Yeah. Yeah. >> So it's like an index lookup from the execution table into the memory. >> I see. I see. So So do you So you only need these lookups then for those additional op codes you've added, right? like for besidon to some of these fields >> also needs it for the add of codes because when you add you access you access data memory. So if you want to um say memory m memory at index fp + 3 yeah >> plus memory f + 7 equal 20 you have three memory accesses.

So one instruction leads to three memory accesses. But isn't the point of like isn't isn't the reason we're writing this VM that we the VMs can be easy to prove, right? Like >> but but like so so proving like like can't you just commit to your memory as a trace and then like proving addition is just like a constraint you added? I think this relate to the point of a circuit build things. No, because you can build that with a circuit build a little bit like done in the bron recussion project and avoid all of the work with the compiler and so this is what you are saying.

>> I I possibly I guess I'm just trying to understand like like I thought the whole point of the add operations was they were like really easy to to to prove, right? >> They are easy to prove. >> Yeah. >> So So then why why They need to look like don't they don't they not need to look up like aren't you just proving that the addition is correct? >> But yes, but you need to look up because you you need to fetch the data which is in memory at index FP plus three which with the certain value of FP. So you need to access this data. >> That's how proofs work, right? like like you commit to a trace and then and then the addition turn like and then you have like your then you do some sort of general mumbo jumbo and then you you at

some point check that like everything agrees on some extension field element sample. Could >> could I like draw a picture? >> Sure. >> So >> yeah, I think I'm just a bit lost on the go. >> All right. So um so so we have like let's say uh a bunch of um operations um and I'm going to find them numbers the clock values right this is the first thing that happens and so forth um so you know let's let's uh just deal with um you know one column of operands because that you know suffices for the purposes of this explanation um

so uh you know like let's say uh here I'm just going to write address here this is the the address that my operation is working on here, right? And maybe uh different operations that are uh distributed in time will access the same address. Um and then uh when that's the case, uh I care that uh they're the same value, right? So so this this is not okay, right? because because the value at address five should be the same in all instances. Um so in order to check that um I want

uh like a memory table where I'm going to have um address value. Um this may not be exactly how it works in lead VM but if so then then I can be corrected. So, so let's say um you know at clock zero I've accessed address five and um it had value one and um you know at clock right two I' I've access five five and got value three um now what's different here in me versus here in the uh execution trace let's say is that mem is sorting everything by address. Um so

uh as so so like you know right before right so we've got four five six whereas over here it's sorted by clock here it's sorted by address. So now the constraint that was not easily checked over here that these are supposed to be the same that's easily checked over here because these two rows are now next to each other. So we turned a non-local constraint into a local constraint. And now the purpose of the permutation argument is to ensure that what's happening over here, all this stuff corresponds with all of this stuff. Is that cleared up?

>> Thank you. Yeah, >> I think this is very similar to Kro where you have memory access in the execution table and you there memory access in another place and then where you can enforce the fact that it's read and there is to prove that it's the same set. I think one thing I don't really understand yet is that in your approach you've got the uh program counter in and pointer in the memory as well as values at the beginning of the right I think >> it's not really memory it's apart it's

two registers apart different from memory but sometimes you need to write them in memory in particular when you want to call a function you need to write them at the beginning of the new frame of the function in order for this function to be able to come back at your at your previous frame. >> Yeah. >> But actually it's it's quite separated from >> would you say that like the main function has got like we could also say that like the main function has got zero at the beginning and then every time I call I I start like the issue is that um those values FP and PC are accessed at every cycle and so you don't want So it's it makes sense to have dedicated

columns in your air for if you store them in memory you need to look up them at every cycles multiple times. So it would be possible I think but it's more costly and when there is value that is accessed absolutely every cycle I think it makes sense to store it in a dedicated code if it question. >> Yeah I think uh I guess My question is like when I have like a function called I also do like I've got a a different lookup argument for the PC and FP just to this is like something similar to Ko but in the currentation it's not exactly

implemented like this it's a bit different >> can you explain the differences >> this This is based on a permutation like a productation check and this works it works um because checks the equality between two sets and Lucas checks the inclusion between two set between two sets two two sets sorry and what you use is actually precisely an index lookup Yeah, you can like I have the lines

so easier for you. >> Yeah. So the picture I drew that works for read write memory but if it's read only then we can simplify the picture a bit. >> So um to check equality equality between two sets. Look up is to check inclusions. For instance, you have a column A and you want to check that all the values in your column A. Sorry, all the values in your column A appear in another column.

And you want every value here should apply. This is an lookup argument. And an index argument is when you have an index column um let's say a table column and here let's say 8 9 10 um 11 and one and and the result of the data let's say one here Three. So 1 2 3 11 0 8 1 9. Okay. Am I here?

Zero. >> This is log star. >> Yes. But but yes. But more generally this is an index. You can build it without star. >> Yeah. And we can discuss star later because this is like just conceptual definition. This is an index lookup and the lab used the notation um like this. And it turns out that if you have a lookup argument, it's easy to build an index lookup argument. So using log up which is the most famous lookup argument currently you can use you can build an

index lookup argument using using simply lo and um so this is an index argument and in the current proof system you have you commit to your memory which is one long slice like one long slice um field elements in in the basis field and you have your execution table and in your execution table you have like three indexes let's say index one index two etc and um corresponding to this indexes you have values

for instance if index one is let's say two here you want memory at index If it's three, you want memory at index three, etc., etc. And this is simply an index lookup where I is this column, T is the memory and you will look up into the memory and obtain the resulting values D here. And using this just conceptually it's quite simple in index look up where you have a table some indexes and the result the resulting data and so actually in the current execution table there are three

column three indexes column and three resulting data column that will store the values of memory accessed at the corresponding indexes and three because in our op codes add etc. There is always three values x + y= z. And so we need three lookups, three index lookups. And um that's it. And and you and you so in this construction you don't have a permutation argument where you use product you what conceptually what you need is is like simple simply index argument.

So what are the indices in this context? Sorry, what are the indices in this? the index the indexes is so in the execution table you have you have one column actually three but let's say one column um which will store indexes and for instance when you say you want you want to add you want to add memory index FP + 3 plus memory let's say I don't know anyway here This will be this will appear in your index column.

>> So you would assign a number to FP + 3. >> Yes. Okay. This will appear in your index column and there is a system there is a lookup an index lookup that enforce that if FP + 3 appears here automatically in the corresponding value column there will be memory indexed at FP + 3. So, so is is the number assigned to FP plus3 the actual physical memory address?

>> Um, sorry, >> is the index assigned to FP plus3? Is that the address? >> Yes. >> Okay. So, you would take the current value of FP you would add three and that would be the index. >> Yes. >> Okay. Got it. >> Yes. Correct. Great. I mean anywhere. >> Sorry. >> Yes. But not in spots like this and in the end you need to prove a global consistency to ensure that the pre-ompile score when you call

it's like it's coherence >> right >> and in this time you need some kind of >> they are not doing groups right because I mean the majority of people doing that >> like it's a it's a there is a conf >> why did you decide to not go with that pharaoh because >> seems a little bit more complicated >> yeah the advantage is that um actually it seems Like uh actually lost star which will be introduced later enables

to save a lot of commitment cost because in star this column value this column that contain the index data here you do not commit to it. Oh, okay. >> And so there is some pros and and cons, but in particular, this was a look up about the memory from the execution table in the memory, but there is also a lookup from the execution table into the bite code because you want at each cycle to fetch the current instruction, the current of code. And you can see this as

an index look up from the program counter column into the bite code because if the counter is 11 I want to fetch the instruction at the 11 inction. >> How do you enforce that the FP there the FP + 3 is actually the correct value? >> There are some constraints in the execution table and that will tell you if instruction is There is like some I don't know if you the minimally it's an air conraint

>> why do you need to fetch the instruction the array embed in the table like when you need to fruition >> because like you put like the the decoded instruction instruction on the on the trace And yes, already there. So you don't need to go to memory like just >> it's a look up for instance in in Ko what you would what you would do is that you would put it to something like 15 column columns that contain the decomposition of your instructions.

>> Yeah. And you can interpret those 15 columns as an index lookup from the program counter into the B code. >> When like a multicolumn index lookup and using the web star you can avoid committing to these 15 columns because they become virtual thanks to the web star. And this is the the the exact location stack will make you gain a lot because you will avoid committing to these 15 columns which is a lot like >> yeah in the end you commit in the current implementation you for each

cycle in the execution table you commit to five columns which is much less than >> did you say it was the data that's vual not >> exactly the the so the table is like the memory and so there is a look from from the execution table to the memory but in this case the table is the memory the index is like F fp for instance >> in Cairo sorry the flags those are indices or data >> they are the data like the result the from the background so the index is PC

>> right of course and and the the 15 flags are the result of this >> right >> um one of the criticism that mentioned u an advantage of job versus kium is the number of uh committed uh elements compared to other v do you know how much they have use in short I I don't know but what I can currently in this system we commit table. So if I do not consider the memory, >> there's only five field elements committed per second.

>> Um can you clarify a little bit more? um the two the two default arguments the one thing the execution the memory compares to the execution the bite code like in the case of the memory I understand that you have this key column you know that you have all the information but in case of the right code like what do you have that is the film indicated that you shouldn't there is um FP PC Index one. Index two.

Can you read what I write? >> Yeah. >> Yeah. >> Okay. Next three. Uh I want index value one value. Okay. Value two. You understand? And value three. Okay. And I continue there. And then okay. I will just write one index and one value. Okay. Index index one. two and three and value one. Okay. And you also have um up code flag one up code

flag two etc etc. let's say 15 or 16 of them that represent that encode your instruction and so here is you know at first we only add four instruction so one of those flags uh even though there are four instructions to encode the toent memory or imaging >> exactly exactly for instance and there are some Yes. Correct. And the jump you jump, do you update FP or not? Yeah.

And so this is the name. Okay. Okay. And this is the B code. Okay. represented vertically because there are like 15 colors. And so this is like the first instruction, then the second instruction, etc., etc., third instruction.

And there are two lookups that you very important. First you want that the value correspond to the index in memory. So these two columns here are linked to the memory that there is an index to get into the memory. And then there is the flags for the de composition of your up code which is related to the PC column. So PC goes with those up code flags and there is an index lookup into the bite code.

>> Is that index or the index? is address >> the index is the counter at which location are we accurate. So for instance initially the program counter will start at zero which mean that at zero I should have the first instruction the first here. So this line here should appear here. Okay. Um is there an uh well is there an advantage to having um code flags instead of calling them add and add I for example for add and add

immediate u jump and call versus red because yeah I would say it's equivalent okay yeah but indeed you could have more granular way of doing it yes it would work but actually the add I and the add would have quite some part in common in the air constraints. But but in the same in there they have a bunch of op codes but in practice you could create new op codes because there are flags and you can you can put whatever you want in the flags. So you you could create a instruction with a very weird behavior by mixing the flags.

Yes. And the key point is that you do not commit. So this value here not commit to it. And this value this column like all the columns that are the result of an index lookup argument are not committed and you this is so this is a topic I want I'd like to discuss to wait the pres the pros and the cons of log star with the lookup on memory it's an interesting subject but the when it comes to the b code the advantages are absolutely clear because you uh because for for lost star is extremely efficient in two cases.

First when the table okay rest when the table in our case the B code is small which is the case in practice the B code is small because the execution table think like a million cycles something like this the B code think a few thousand instructions maximum. So and second multiple columns in which case log star is also very well suited. So the log star lookup is extremely well suited when it comes to the b code when it comes to memory it depends in some context and this is interesting subject mean sometimes it will be slower than classical log sometimes it will be

faster. Okay you show us log of star. So yeah the basic yeah the basic log as I say the basic log like you have this with the product and with the log you just take like the derivative with the log and then you end up with a sum this sum you run this sum like line by And so at the end you have like the initialization and then at each line you have this implementation line by line and at the end you just finally check

that your final line is zero and not one as we mentioned previously with the product that is log and then there is this log star technique. So as just mentioned by you have this table T that is a small table usually and you have the index column E that is a a large column so be quite large but with element very small in there uh and so you just two times the value like this um I have this explanation then there so this is basically what we are trying to

do So high star t. So you have this table of index and the value that you want to check at this corresponding index. Um in this case like so you just do that. So basically if you have a very small table t for and you have the index then you just do that. So that to grab the different index value.

If you go to this and then I think I have an example of yeah so for example if you have this and with all of this index so you can see that typically this can be big numbers and this is very small because this are index and if you had to commit to this multiplication table this can be as it is a combination this is large table with large f is very costly to come to uh and so you have this new idea maybe like this could help you I think that would be better to explain it because

this pull pull back and push forward so this is this technique with a subject in the middle uh yeah here I have some equation so yeah you have this you rearrange in some sort an A and then you have these sums and so you compute for each G A multiply by A and then the sum over A I= G where you compute that for each G this is correct um and so finally after you add this so you

have this uh table that seems small That is back and then you use this duality lema. Correct. >> This is the key thing. >> Yeah. So yeah. So this is basically an equality that helps you rearrange the term and then end up with the final. So for example maybe can you explain how you implemented this into the code like this this rearrangement of stuff you want that you take some time in the mathematical details on everything in it's possible but

>> I don't understand the explanation so >> yeah okay so the notion of pullback. This is the the index look up I presented. You have this this is the index. So if you access at index I this is the pull back.

Let us go with this is a different motion but similar. So I take some and I= this is okay. Is this

>> Yeah. Yeah. >> Is is this pullback a pullback in the category theory sense? >> Yes. >> It's a pullback in preomposing with a function. It's much simpler. I don't think we need to talk about categories, right? >> Okay. >> Okay. And and the key point is that and just for instance um Okay. And the key point is if you have two table so first the pullback is that is it for everyone like if you have like a table 10 20 30 then you have another table of

indices and then you just go to T of I for the first one for example it's T of two. So you all of them if you rearrange the sun you can say and you take all and then is public or somewhere.

>> Yeah. Yeah. This is I think I can tell you >> Tom, if you want to direct your slides and the hacking to me, all put them all in YouTube comments. And so I'm going to try to collect all the presentations, the videos, transcripts, put it all on the lean Ethereum GitHub or so that people can go back to it. We have got the ones from ECC at CAN a few months ago too.

>> Okay. So anyway, spend too much on the details. >> That's the proof, right? Okay. Just continue. >> Okay. Just because it's simply it's there are two songs. You need to switch indexes. It's it's not very complicated. Just switch indexes in the song. It will work. Okay. Um and last words >> as an exercise to the reader. >> Yeah, exactly.

Um actually what you want to do in practice is to evaluate the column containing the index data at random point in the extension field. So what you want is to have like the multilinear extension of this thing evaluated evaluated at a random point in the extension field. Okay. But this thing can always be understood as an inner product. So with the equality and here you can use this lema and

switch and you access this and here you trade the pull back for the push forward. just here maybe like with small just with a small example to show this product. So if we take a b and i, if we go to the same steps that I just mentioned before. So you just do b1. So that 20 10 20. So then you have this vector of e cross b and then you do the first side of the the multiplication. So you do two * 20 + 3 10 and 4 20. You end up with 150. And then you compute the other way

uh and you end up with three six. And then you compute like the dot product again. And you see that 150 that you obtain this by doing this way is exactly the same dot product that you obtain here by doing the other way. That demonstrates an example this equality. And um this equality the idea is that you will run a check to prove this thing because it's like inner produce at the end of the check the verifier will access.

you interested. Thank you. So this okay and at the end of the sub check the will need to query this multiar polinomial and this multilinear polomial to be able to evaluate the expression inside the sum. This thing the table has been previously committed or is accessible because T is either the memory or the B code. If it's the memory, it has been committed. So the can

at some random point. If it's the B code, the verifier can access by itself by evaluating the B code as this thing is less trivial. So the vifier needs needs to evaluate the push forward of the equality kernel at air at some random point. Let's say sorry the verifier needs to compute this thing at a random point let's say alpha and to do this it's the same trick as in logup so you will use a sum of fractions

but here the sum of fractions will be slightly different is what you want to prove is X minus indexes. Let's say you want to prove because in log you want to prove to pull back.

Let's say you want to prove a push forward. So you want to prove this equality. Okay. It turns out you can use something very similar to which is this indexes. Okay.

Okay. Okay. Okay. This thing is true only when Y is indeed the push forward of this system. And so you evaluate it at random like you take random challenge. And so

alpha you replace it X by alpha. And this whole sum of functions will be equal with high probability if and only if this thing is indeed. So you will need to run something very similar to to log up we need to compute some function. So in the end the cost are similar to it's like the similar to and in our case the a is the equality at the random point.

This is the indexes that we know and uh yes and you need to it okay and Um yes. Yes. And so in terms of cost and I'm sorry I'm not the extra I'm sorry but in terms of cost the the main difference with log up I think this is maybe the the most important thing to speak about lo you have to commit to four things.

So you have your indexes, your table and the corresponding data. You log up you commit to indexes. I you commit to the table. It's committed. You commit to the data and you commit to the accumulator where in for for each accessed index in the in the memory or the the B codes like the data you access needs to tell how much time did you access this data like the accumulator.

>> How many times? >> Yes. Ex. Exactly. The In log star you don't commit to the res the resulting data and you don't commit don't commit to the accumulator but you need to commit to this thing to this thing and this thing has the It's multilinear which has the same size memory as the table. So if the table is small, you commit to something small.

And that's why we love star when the table is small. The key draw the main drawback is that if your table memory is in the base field, this thing unfortunately is in the extension field. So this is like a point because for the lookup of the memory you need to commit to something of the same size of the memory but in the extension field and this costs quite a lot.

>> So when your table has the same size as your indexes clearly lost star is less performant than log up because of this thing. But in practice in our case there are three indexes column per cycle. So each cycle fetch three data from memory and you can approximately say that each cycle will use a new cell memory. So there are approximately as many cells in memory as there are cycles in the execution. So the size of the

memory is approximately the number of cycles. And so in our case if the indexes sorry if the the table has length n the indexes as len three length 3 n. And so if we count things in logup classical lookup you commit to the indexes. So you commit to 3 n, you commit to the table. So n, you commit to the data.

So 3 and you commit to the accumulator. So n overhaul 8 global stuff. You don't commit to data and accumulator but you still commit to index table but this you don't commit but you commit to the push forward of the kernel which is a n times the extension degree of the field let's say five 5 n if you do the sum 3 + 1 + 5 you are at 9 so in terms of commitment cost It's it's

a little bit worse than log up classical. It's not very so the thing that that I want to express is that it's not it's for the lookup in memory lookups in when there are three times more indexes than there are then sorry when the the ind the column indexes is three times larger than the memory the commitment cost of local staff are similar to the commitment cost of log normal and after this there is the same um sum that you need to comput the sum

of fractions and it would be the same in star so in terms of cost it's roughly the same and after this there is a question on how do you compute this sum and you can use it like you can commit to CI columns and you use dimension like an F f constraints to enforce the fraction equals one or something. You can also run GKF. It depends. But the point I want to transmit is that as long as there are three times more indexes than data indexes, star is almost as good as for the memory and for the B code is it's 10 times better.

I'm sorry for maybe what we could do is I I have final example everything. So maybe we could go to this and then talk about like the pros and cons of everything because there are a lot of varants including like the same chain. There is a log log plus GKR lot of stuff. So yeah. So yeah as just mentioned let us talk about brief example see how star work and then we can finalize with some questions.

So let us imagine that we have a table t and hide with indexes. So small values but large table big values but small table if like you get like the index you have 100 x 200. Let us suppose that we want to evaluate that as as a random point. This one representing on the virtue. This correspond to a selection of index two because of the index 0 0 and then 0 0 1 and then 0 1 0. uh is that you don't want to commit as just

mentioned by email into the this big table because in reality this can be really huge and with big values. So again like the prover did initial claim that is that I do t of 2= 100. Then we define that is a defined by there and Um so basically this a air saying is saying that uh it's evaluated to one only at zero one zero and zero everywhere else. So this is just like a selector

then we can compute like i by the expression with the big sum that was me at the beginning. So for example if we go to = 0. We have the sum. We have i of 0 = 0. I of 2 = 0= 1. So only i = 0 as x of 2 = 1. And so finally this is one. If you do exactly the same thing for one, this is of i of 1= z. And then at the end you obtain this final vector of one zero.

Then you do the magic trick of switching the product. So at the beginning you have this and then you you just switch to have this. If we go numerically with the example you still have like 100 and 200 and you have one and zero. So you just do the dot product. So 100 multiply by one and 200 by zero. This match the K value. Then you have the subject coming in. Uh you have to prove that the S check and you open the final evaluation thanks to like the verifier random challenges doing the same check. And the key point to to have in mind there is

that with all of this we never committed to this big table and instead we committed to this one. Correct. This is what you explain that is small value and much smaller. My question there as a follow up are like I guess that has a lot of complexity inside the code. I guess compared to there is only this only inside check here. But once you've done this check, you need to prove the same type of sum of of fraction as in. So the only difference I believe is the sun

check. So you just reuse the same check that you use in the zero check of the P just call it there. And I have seen that a bunch of stuff about like lo and GKR. A bunch of teams have tried the tool and finally end up with simple logo without GTR. Do you have any opinion on that stuff to add GR >> right?

>> I think so. >> I was thinking that they just because we we asked for example to start and they tried both and with GKR and finally they just abandoned the GKR option. This is still in their code but not used just >> why did they run it? >> Because they didn't see any benefit of this >> wasn't also this um security risk with GKR. >> Yeah.

>> Yeah. This is also a possibility. >> This is a proving false statement. >> Yes. Yes. >> That one doesn't really affect GK, but that one only affects GKR if you let the prover have like complete control over over sort of I mean it's a bit like airs are also broken if the prover gets to write down their own air and they have a broken air >> like if I if I claim this air says the sentence's correct and the air is just nonsense it doesn't >> that's a bit different but I see the right I mean air is a specification language surely you can specify pointless statements that's different is not but the point stands yeah I mean if it's just log it's not that that attack will not be relevant

>> you will have a G close to the hash function like a very complex structure in the G to be able to access >> back I don't know if back when Shahar was there some time ago I remember like his answer was that some things were faster not all of them I don't think it He told me that it was possible to catch that kind of things. >> When like you said that when Shah was back then in he told you that GR is faster for some >> it depends what are you doing but sadly

I don't remember the full analysis. Same talking with with Bobin. I think he he mentioned that in it didn't make things like way faster. So it didn't make sense to have something way more complex in their code base faster. I would say the answer depends on how fast is your commitment compared to proving like because if you don't use GK you have to commit to every data >> and I guess that if you have if you use a fry with kak it will be extremely fast >> but just to give you an example

like two two days ago I was able to gain 50% on the on performance for proving pos2 using so simply by going from constraints of degree three to degree 9. So increasing a lot the degree of the air constraints. I I modify the the I used the sphereization. Yeah. But I like the initial and final steps I batch like instead of doing a f cube by cube I do a cube and cube and then I quit. And using this I reduce the number of committed columns. And it turns out it's faster

like even It increases the the degree of the air. So the the zero check is slower but the PCS is like much faster. So like we gain like maybe 30% of the PCS and because the PCS is is not that fast in our case because win compared to F and check I I think for us committing is slower than other. So you you you removed cells uh and added higher constraint. So why is it faster? I I I removed from the possess half the size in the air if you will do

degree n constraints because you get to do you do like a cube things right and so if you have if your constraints go up to degree nine you can sort of do two rounds at once because you just do two cubes How many >> I think 64. >> Okay. >> So before it was 150 or maybe 160 something like this. Yeah. And going to like 100.

>> Okay. There are four partial wounds at the beginning, four partial wounds at the end and and each partial wound you needed to commit 16. And so if you cut two and two, you gain two plus two. So 64. >> But then bumping up your degree of the air to nine, doesn't the rest of the system come? >> Yes, obviously. Yes, but It's slower, but overall you gain because the PC is faster.

>> So, would it be possible to kind of automate and let it run for I don't know 3 hours to check what kind of degree C. Yes, >> it's a good point because it was easy to go to degree 9 using maybe the optimal is degree seven. I don't know. But it's it's much harder to arithmetize with one degree cuz you said like 3 9 27. >> Yes. Obviously between three and nine it's less clear how to implement it. >> Yeah. I mean I think for Kal there wouldn't be any there wouldn't be much point. I mean if you pick a different field like baby bearing you much do what you said and then obviously you get you get the advantage of having everything.

Um yeah, but otherwise I think well I think you you just want to go up in like 30. Yeah, makes sense. Um what was the reason you choose here? >> It's more than three. Anyway the log if I I think um I I would bet that lo G in our case will be faster but I am not I don't know you also recently I think implemented something like Jed PCS. Yes, >> maybe it's a good time like to talk

about >> Okay. >> Very like >> is it something that is in competition with the >> compment join the point we want a break before or after this? Is it time for break? Yeah, we can take a break. >> Okay. But it's a