Improving LogUp with GKR - By Ulrich from Polygon

Transcript

this I'm going to okay so I hit the recording we should be fine so actually actually didn't didn't look to put I can I can with the front I can stop it if you want and we can go at it again if you need to change something or you need to swap screens or whatever no no U so you is my screen displayed because I don't see we can we can see your slides now okay so we can see your slides yeah the first page yeah the first page exactly yeah yeah yeah yeah so uh hello everyone to do a quick introduction this is ulri from polygon Z if I'm not mistaken uh he's the author of many interesting papers uh some of them have

been um have appeared uh lately this year uh quite recently and one of them is log up which is basically uh some kind of way to have much better uh or much cheaper lookup arguments uh using gkr and therefore also trying to lower a bit the the commitment costs for the witness um but he's he's definitely one that should explain all of that so uh thank you very much or for for coming here and for explaining everything to us uh as Rich mentioned at the beginning of the of our chat uh he's happy taking any questions uh during his talk so if

anyone has any kind of question just feel free to jump in and and ask uh the floor is yours Rich whenever you want thank you thanks for having me so uh actually uh before we start so so I'm going to talk about log up uh but an improved version of it it's a joint work with Shaha papini it's it's we we we put it onr when was it like end of August beginning of September so uh okay so roughly I mean let's first discuss the use case because there are so many log up lookup arguments uh so so the use case we are targeting uh is uh

not the large table track that that is followed starting from Baloo going up to uh fluk up and CQ not that kind of track so we we we we we want we we we are considering the use case where we have a typically ordinary size table but ordinary I mean it's as long as the trace is say it's 2 to the 20 at maximum maybe two to the 25 something like that so no large table lookups or the classical ordinary size look lookup tables and but uh we what we face in many applications is we have a lot of

witness columns uh is my mouse cursor are displayed yes it is we can follow with you so I can use it as a you can use it as a point that's fine so we have a lot of columns and these columns are all subject to one and the same table so what are specific examples of that for for example in in the context of the ckvm uh in particular the one uh from polygon zero the uh we we have a lot of columns that are subject to the machine word size proof so they subject to one and the same range proof uh I think I always have to ask my

my people how much but it's it's it's beyond 80 columns 8 Z beyond that which is subject to a 16bit range check so uh but also other applications we might think of of of a hash friendly uh a hash friendly uh circuit friendly hash function sorry circuit friendly hash function and in an antire specific purpose Hash a chip for it so that that computes a lot of these hashes uh in parallel so to speak so so also there because the HH uses a lot of lookups uh you need also a lot of columns which will be subject to one at

the same table lookup but beyond that uh what is often not uh not explicitly called uh a lookup any more is uh the same techniques that log abuses uh can be used to to to to uh to prove uh to prove the data bus between different components of your ckvm that's exactly the the track of uh polygon miden uh if people are interested in that I can spend some words uh at the end of of of the talk on it but in general I will now Focus go back and focus on lookup application so what will

the talk be about first of all uh I'll give some context so we will start off with permutation arguments and lookups second uh I will uh then describe the classical log up protocol and what's the base principle and the base principle is very much the same than that of fluk up from gabison and kovic we use polls instead of zeros that's the different the other Paradigm which is very useful in the context of lookup arguments and then so that's essentially uh what is covered by the ePrint from last year and then I will uh

dive into the new publication with shahab papini uh which shows how to use GPR the gold wasal Ro colum protocol actually a protocol from the I would say the pre snark area uh how to use that protocol uh to highly optimize log up in particular the commitment pressure of log up okay just for completeness I mentioned already one of the work works not two of them I mentioned fluk up and CQ so uh fluk up just as far as I

remember it just happened to be released like one week before I released my log up paper back then uh so which was bit unfortunate for me because they completely stole us the show anyway so so fluk up does the same uh not actually they address already large table lookups but there is one protocol uh which are called the proof of radical which is exactly the same like log up uh for a single column for a single witness column and uh and before that uh I I was more formulating what they what plup calls fractional decomposition I was I was putting more in the context of the formal logarithmic derivative but

essenti it's it's exactly the same so uh and but logarithmic derivatives and the usefulness in the context of permutation arguments or lookups pation arguments at least I mean I was not the only one uh that uh that was was thinking about it uh there there is Liam Liam did bulletproof Plus+ which was like a couple of months before fluk up uh which I wasn't aware of and he also already uses the the logarithmic derivative uh to be frank I never read the paper so uh so please don't ask me

what what the concrete application is in this case Okay and then CQ which I mentioned already before large table lookups Liam Egan and cison okay some background so what's the classical uh the classical approach to T permutation arguments or let's more concrete multi set equality so we consider we have given two sequences the the witness sequence the wi and another one TJ typically yeah and you want to prove that one is the permutation of another so both can have

uh multiple occurrence occurrences of one the same way it doesn't matter so we want to have multiset equality so that means each value that occurs here with a certain Multiplicity occurs here exactly with the same multiplicity and that's simply done by encoding the elements in the sequences as zeros of pols that goes back to buyer and growth I think the was 2012 so so because they're the same up to permutation uh even only these two polinomial in the code the zeros are the same and how is that proven uh the polinomial itself is kept virtually but

what but one samples a random value Alpha for x and proves that identity at that random Point instead which leads to a gr product and if you use ground product arguments from PL that's efficiently doable for lookups it's a bit slightly more complicated uh it's not slight anymore it's it's it's it's let's say it's substantial more complicated uh it's about set me membership so that that is now I've given a table sequence TJ typically I don't have multiplicities there or they're all

uh single only single occurrences to make it simple uh and you want to show that each element of wi is contained in the table U that means wi might call a t table element several times whereas in the table to use only one time in other words I call this set membership so if if you collapse down the sequences to sets you remove multiplicities then the the sequence of the witnesses the set of the witness elements is contained contained in set of the table

element and that's the case if if you now try to pull that over to encoding elements as roots of polom you need to talk about uh you need to take the multiplicity that uh that of of uh how often a table value occurs in the sequence in the witness sequence uh by by uh the exponent by yeah I think I'm sorry not directly got the sentence grammatically finished but I think the idea is clear by the formula so you want the so that means wi is contained in the T table as

set if I can find multiplicities such that this identity holds and again you just sample at the random point and prove that at the random point but the problem is exactly that the multiplicity something that is provided by the appr typically is in the exponent uh Thea paper from 2018 uh addresses this identity by providing a bit a providing a bitwise encoding of the

multiplicities so that means uh and of and decomposing this product into Pro product in of in into products of two Artic powers of that witness sequence and you that's that's that's that's doable you have to prove these totic Powers you provide you provide them you prove prove them typically if you want to keep the degree of your program of your constraints low uh but it costs at least as many commitments as uh you you have bits in the

multiplicities so that's one way to do it uh a better way to do it is plug up uh so this is this representation I think I have from the hyperon paper it's not exactly the formulation you find in the plup paper but something equivalent so uh so if you want to prove that the witness sequence contained in the the table sequence set then uh you consider for that sequence uh the differential I call it the differential so it's something like uh at the point K

uh sorry I'm jump back I accidentally clicked the mouse so given given a witness sequence uh any sequence let's call it AI then you just look you just look at the pairs of two two adjacent values in time ai ai + one it's like a vector I call it it's the difference you can consider it as a sort of difference Vector so and and and what they say is if you look at the sequence if it's then uh if it's contained in the

table then the only differences that uh it's a bit I haven't thought of that long long ago but it's you provide this this function s is a sort of integral that's why I call it Integra integrability Criterion so you you provide uh so you name all the different differences cure from the table sequence itself it's like uh the table itself

provides a grid it's like a basis grid and uh the the the only thing you need to assure is that two adjacent w i if the difference is larger that is split into the smaller ones it should be guaranteed but this uh this this Criterion sorry I did not prepare on the on the context here uh it should work I once understood it but right now I can't uh can't uh improvise good enough in that way but

that's the way so so so the these are sets if and only if there exists such a such a uh such a uh sort of interqual function so so that these two sets of the differentials are the same so you bring all the differentials the one that that are think I'm coming returning to the all differentials the one that comes from the table and the one that takes into account multiplicities which means like you don't have any difference you bring that under the hood of a single function that's the intercore so or in polinomial identities you encode these vectors by

oh sorry by uh just doing uh uh considering linear factors uh as the roots of the polom that generalizes easily you just sample now for both uh Y and X a random uh point and end up again with the grand product argument okay so the big picture here is so we start with the witness columns we have the table column and we need to provide that that uh that integral for the differentials that integral and and

that's that's as large as as the union of the Witnesses and the table so this is really as large as same thing so that you need to provide in any case then you sample uh the randomness is to to to to reduce it to to a uh Grant product argument and you need to provide uh the com the running product for that grand product argument I want to normalize this B though there are always tradeoff between the degree of the program and uh and the number of commitments to be

provided but I normalize all my observation to the case where we only have degree 2 constraints which means that the running product uh go goes over the same domain as uh as this sorted Union is larger okay so that means you provide all all over it's like you need that's that's needed anyway and you need provide twice as much so overall another two blocks of the same size and that's very unsatisfactory so this is the situation

that you face with the multiplicative view of clup log up follows the same Principle as fluk up so the main difference is now we did just use a different algebraic object not pols so we don't encode our elements as zeros of polom we do otherwise we encode them as polls so that means for the witness sequence you just add for each for each

element pole and for the table the same and the nice thing about poles is that multiplicities they don't they're not in the exponent they're not powers of linear factors corresponding to roots multiplicities are now just scolar how often the pole is taken so poles just sum up in the fractural disc that easily so and that's the core Lama which is the uniqueness of fractional decompositions so so consider with have two

sequences it's and consider that the witness sequences actually should be the length plus no no it's good enough just for the witness sequences uh the the length of the witness sequence is smaller than the characteristic of the field that's important I will I will tell you in a second why so uh and then you can say okay uh the one witness sequence is in the other if if uh if uh if we if we can uh if each V value of the table occurs with a certain multiplicity the point is so this must hold the Ral function

point is it's important that that this comp composition is unique and that we which which has to do with that if you would add the same pole characteristic many times you would end up with zero again so so poles can cancel out if you sum up poles but if you're if you per say say my witness sequence is anyway smaller than the field is larger which in most application is the case one has to be a little bit careful uh when one uses very small Fields like M31 but in general it's it's uh you never hit the characteristic bound here in any case and you can say

okay the sequence the sequence is contained in the other as sets if and only if I can provide multiplicities uh so that uh that these two rational function fractional or fractional decompositions are the same yeah and then you just sample Alpha for X randomly and end up with a fractional sum check of fractions fractional sum check so fractional sus are typically proven by making the one over

term the inverse by providing a polom for that inverse and prove it to be the inverse and that causes that for each of the of the witness sequences and also the table sequence so all of them there are subject to the fractional subject each of these sequences you need to provide one for the inverses essentially so these are the help of functions here they're just needed to turn a fractional Su Che into a polinomial sum Che but the polinomial sum check is

proven using standard techniques like running some argument sorry how how costly is to actually compute those um helper functions like is are they trivial to be derived or do they Computing is not so much the problem committing is the problem not fair enough that cost so the the they need to be provided and to be proven to be the inverses that's the classical way one one follows here so okay and uh once you have the Improvement you do you do the sum check actually over these helpful functions

instead which are the inverses that's the fractions which are the fractions so yeah but as as you see here if you have have in mind still the picture we had with plup for the many columns case where we had this block by the amount of data to be com committed on top of it another two times we are now somewhere where we only have just another time instead of two times the same block so it's like a 3 to2 Improvement I see so that means that for

multi for multic colum lookups this is definitely the way to go exactly exactly makes makesense it it's it's not the way if you have just a few columns uh with a single column I have to double check here it's Pro it's definitely not better I think uh or or about equivalent so but the the big benefit becomes feelable if you have a many columns in the in original log up paper that from two 20 2022 uh I'm even trying to predict in terms of uh of operation counts where the

speed spot might be between when when one does on top of it uh the uh the trade off between higher degree program not degree two higher degree constraints uh versus uh for paying with higher degree constraints for Less commit ments to be given in the helper functions by providing helper functions for group groups of inverses for groups of columns for the inverses of groups of columns that's doable that's are standard techniques in this tradeoff I'm not going to talk about here so essentially that's that's that's the thing to make

it comparable with plup also both use degre 2 Programs and we already have an improvement from three down to two yeah but actually one can do better and that's essentially the Insight of Shaha papini um inspired from our discussion uh we had when reading uh the work of Justin tala in the context to of the lasso lookup argument uh just a quite quite small note that where he refer to a previous work of his

uh that you can do the grand product argument using gkr uh to be honest I always looked at GK I didn't take gkr I underestimated it its usefulness uh but that that comment made me think about uh uh reconsidering gkr and it turns out that you can use gkr also in this situation uh and the nice thing of GK is that you don't need to to provide any additional commitments I will go into that in the next slides so let me go once back so this was the initial log of

22 but we can get completely rid of all these help of functions ending up with a single extra column to be provided that's the multiplicity column and that's beautiful in my opinion so let me try to explain gkr not in all generality but in that specific case that we face which is a very simple circuit in the end so uh it's back to the pre snark area essentially uh and it's made for layered circuits with a few rows I consider a

layer of the circuit as a row so you have few rows and it's similar to an air it's not exact it's not the same but I I like to to view it as a horizontal air where instead of encoding columns at polom encode really each layer each row you have a single polom it's a multivar protocol so in okay it's a multilinear polom one row one layer by layer we have one multilinear polom and the constraints between two adjacent rows is formulated while a su check and the protocol will

go will will be a multi round protocol for each step you do from the top layer down to the bottom layer something like input layer or output layer to input layer so that's how circuit for our fractional subject will look like so that's a computation we want to prove so we have given uh I'm assuming here bit uh knowledge about

multivariat uh provs uh for those who are not familiar with it just uh ignore that uh for the basic idea so this is the hyper Cube here so I have given two multilinear pols so put two two functions over the nend dimensional hyper Cube over the nend dimension Boolean hyper Cube and I want to prove that the sum of their fractions is equal to a claim p over Q two numbers that I provide circuit goes as follows it's uh like every subject check or ground

product it's a treewise circuit so on the bottom lay the layer for the hyper cube of Dimension n uh we have given all the PS and the q's all the numerators and the denominators of fra fraction I want to sum up in each so from layer to layer I just some fractions pairwise pairwise and that reduces the

size of each layer the horizontal size by factor one2 that is done recursively could could it be possible to have a different arity and like grow faster towards traversing towards the root or it wouldn't work that's that's doable but it will increase the constraint the degree of the constraint between two adjacent layer and I think in the end you don't win much if anything at all is my feeling here okay so we will see how the constraints look like in in in our case there will be only degree two

constraints if you do it really pairwise Haring at each step okay but yes you can do you can do faster steps at the cost of the degree of of each constraint you have between two adjacent layer the the expression degrees is still a power of two always so you jump from two to four and from four to8 and so on if you want to keep with a pure two aric setting of hyper Cube then it's a then then the the radics you would choose would be a power of two okay and in that regard have you done any kind of analysis on the possible uh the combinations of of different arities and the like for for

instance I don't know if you use an arity of seven or or I don't know something like that that it's like almost at the limit or something like this we didn't do something like this yet in general my feeling is often that's that's similar like also to to mix radics fft in the univarate sense that the Improvement when going to a non-ic setting is probably not worth the implementation effort so that would be a measure you do only if you need to push out if you push need to squeeze out

everything you can so in it's currently I don't know if somebody did already uh implement it but both starware and at polygon we didn't implement it yet so for that paper we just did some hand wavy uh operation counts again uh which are a quite unreliable measure but at least an indicator for the performance of the end of of of log up using gkr okay thank you very much okay so that's the circuit it's has a treewise topology each gate does the

same you take two so so you keep track of of numerator and denominator in each uh in each step so uh it it just does the sum oops what happened what's Happening Here do you see still my screen uh no we lost it now okay is it back yeah it is no okay so again yeah we lost it again I'm just using the arrow

button so let me reshare I want to switch the slide it doesn't let me so so if you look at one of these Gates it's just the addition gate of two fractions so so let's assume we have we we have the point x x is actually seen consists of many coordinates but I I didn't use the vector notation here in this slide so at a point from the so so at the point the K dimensional hyper

Cube numerator and denominator is formed from numerators and denominators from each children nodes which according to topology of the hyper Cube just means you take that Vector X and append either a zero that's the left child or a one that's the right child and the additional law is quite simple for example the numerator I mean you know how to simp symbolic two symbolic fractions the numerator is the product of the left child numerator times the right child denominator plus the right the left child

denominator times the right CH numerator we'll see in the next slide though in that slide I will immediately describe the entire sum check you do on the pols so look look at this this is just the lrange representation that's the that's what other papers call the EQ function so this just the chronic Delta so uh how to read this don't look at to to too many details but at a point so so we are now at level at at layer K and we want

to formulate its dependencies on the numerators and denominators polom uh values at the layer below it's k + one so take so we have PK +1 q k + one that that encode numerator and denominator and what you see here at Point Little X over the K at we have exact the law I was mentioning in the in the last slide so that means that reflects exactly the numerator when adding the symbolic fractions from the children Noe noes and the same uh for

the for the denominators even simpler it's just uh just the product for the common the least common not the least but but for a common denominator this just mimics symbolic addition of two fractions and yeah so so so what here is the entire system to be sub checked at each step so so how does the proof go you start with the top layer claim which is a constant polom because it's the Zero Dimensional hyper Cube here

and then uh so it you pointwise so you reduce that representation from a PO from from a linear sum using laration you you reduce that to a sub check of Scholars I was I was skipping here a little detail the top layer idea is a bit problematic in this writing because the Zero Dimensional hyper Cube is an exceptional Corner case but think of it that we would have just two two tops for a second so we would start at layer one instead of layer zero to make it simple so we have a onedimensional hyper Cube

that means you make a linear combination of these two subjects this a sort of batching uh which means that you you you you want to know that top layer polom at a random point so that so in other words uh and at that random point for capital x if you insert a specific value you have in fact a su check of scolars and not of pols again so so in our settings so you start with the

claim reduce it to a claim of the pols of of one layer below at the random point this random point is sampled in the course of the subject protocol and so on then you do then for the both of things you do a sum check and reduce it to a claim of the polom another layer below which is the layer of over H2 and so on and so on until you end up having overall reduce the initial claim to the evaluation claim of pols at the bottom layer which are the polom subject to the fractional subject so this is how it goes you don't

need any commitment in between none of the of the intermediate layers are committed you repeatedly use some check one for each layer transition first glance it seems like it would be quadratic effort but it's not because they shrink or let's say they increase if you go from top to down or so so that they increase geometrically or they shrink geometrically if go from the bottom layer up to top layer so that stays linear time in the number of field operations

okay quick recap here just the picture we have in mind uh so besides what is needed to be committed anyway that the witness sequence is subject to the lookup in the table you just have to provide a single extra column for the multiplicities then the verifier sends a random point and on this random point this defines at which point we need we we we do the fractional sub and we run GTR circuit repeatedly some check in order to reduce to a multi-linear evaluation claim of the involved pols

which are numerator pols most of them are trivial like they don't have any numerator it's the constant one uh the numerator of the M over o over T minus Alpha you know that's that's the that's the numerator for for the table part is M the denominator is T so that that domain that circuit the bottom domain is as large is a hyper Cube that is large enough to host the witness sequences and the table

sequences um one question when you said now that kind of the default element is a one instead of a zero could you could you explain why if you remember how the Su check was looking I can jump back few slides or whatever you prefer if you want to finish I try first with words if it if this is so so so what is the sum check to be proven in context of the lookup it's like the sum over one over the Omega eyes W wi minus Alpha that that pole evaluate at Alpha the Omega I pole at Alpha that sum must be equal it's one

over because it's one over the numerator is okay okay equal to and then we have this or let's say is equal to the sum of M over tus okay I see because if like if it was Zero that you could as as in lasso you could take profit of that and use a SP polinomial commitment so that you even pay less because all of the things that are zero you can directly omit them so sorry can I repeat so yeah I was I asked that because if the kind of null elements or elements that don't bring like I don't know how to say it that that are like the defaults basically if they were zero

you could you could be able to use a sparse polinomial commitment and therefore take profit of all of the zeros by just not needing to commit to any of them directly in first place but this case the witness data itself and uh it's never Spar it's always Dan right like you have Dan yeah what is spars is uh in a sense of of of representation the multiplicities are small values I wouldn't call it sparse so it's not in the sense of sparse polinomial commitment see yeah I see so so we this column consists of typically small values depends on how many how many how

large the multiplicities are at maximum as many as many elements you have for the lookup fair enough so so uh for some commitment scheme that committing m is quite cheap for the situations we Face uh at polygon uh which are Starks that doesn't matter having small values or not because R allong codes blow up to they they uh when it when you consider just the the the lde evaluated out inter the interpolant using from small values to some other C

set you have arbitrary values that look like random okay for enough so thank you for your answer okay so yeah that's the big picture just single extra column to be committed on the cost of the gkr which is arithmetic cost more that here so uh oh yeah so so we get rid of all these helper functions to be committed uh but by a more complex arithmetic protocol and if you run the univarate

appr because G is multivariate uh you need something uh what we call the lagon transform in in the paper something that uh which is a transform and yet another transform from uh which turns a univariate polinomial commitment scheme into a multilinear one so they can prove multi-linear evaluation via a Univar at IP so uh I won't go into details here but it's a quite cheap and elegant protocol uh costs just an extra commitment which is essentially the multivariat Lage at the

query point that is obtained in the course of the gtrr actually the last S Check of the GPR so but in the multi-linear case multivar case it's just a single extra col and when thinking about the expected speed up that is with a massive grain of salt here for easy commitments it's quite easy to estimate I have even was relying on on on on benchmarks that I did in the log up 22 paper uh in order that that compares orinary the cost of ordinary field

multiplications or measures the commitment cost in uh in field operations in the equivalent number of field operations per timing equivalent number and for EC based commitments uh I'd expect absolute lower bound of improvement here if you have a large number of columns that's always the important thing so for the for for the situation we face would be more than 10 fold uh when going to Starks it's a bit more difficult to answer because the commitment cost very much depends on on what type of hash you

use but committing means not just hashing it means you uh for R Solon you first need to compute the the interpolant and uh evaluate over the entire sampling domain so you need to compute extrapolations and and they're they're already costly in some sense so they have some arithmetic cost and the arithmetic just by operation counts not the best measure for real world performance but just by operational counts the encoding effort of R Solomon is quite comparable already to the GPR effort and that that leads us to

the uh to the to the to the estimate or expectation that that speed up here is is is is barely uh influenced by the type of hash you use and even if you use very fast hash like Blake two or Blake three or Monon yeah if you use very L fast hashes then we expect it will be rather approaching only to be a two-fold improve Improvement if you use slow hashes in primitive slow in primitive like posidon uh or even more like rescue Prime uh then it approaches the tfold Improvement because committing

becomes more expensive so that's what we expect but uh with a massive grain of salt here so we are curious how it will be in real world implementations so I'm not sure how much time did we take we took exactly one hour um but like I I don't know if you have any time limitations but from our side we we'll finish if it's okay from your side when people has asked uh all of the questions that they might have

yeah I'm open for questions okay so yeah now it's time everyone to just jump in and ask or put it in the chat and I can read them bloud whatever you whatever you prefer in the meantime if no one has yeah please read yeah you got got questions I I have one if no one else uh my question is regarding the the rounds that you have in JKR so how like how are you rep presenting as an Ari as kind of an arithmetic circuit or bant circuit I don't know how to say the sum of fractions because a

some OFA like at least for the school like the naive fraction in the real domain in the in the real numbers domain to sum a fraction you need to do much more stuff that like simply decomposing it into bits and just adding and subtracting some things like you need to have common common denominators is going to start so the I'm not sure if you understand the question but the circuit we use here is not a Boolean circuit because you can perform addition instead of and over the field we are using the thing is we are doing AR symbolic fraction

arithmetic so it's like a fraction is not really if you divide numerator by denominator and it's a single field element it's it's really we keep track of numerator and denominator as a vector oh I see it's like a symbolic fraction I see and we compute the symbolic fraction uh of of the fractional Su check so we do symbolic operations here and but these are all over the base over the field that we are using I see I see I see I see I see that makes sense that makes sense though okay okay that answers my

question yeah thank this makes it to this yeah so it's in the end if I if I jump back here is my slide still presented yeah we can still see them yeah okay try to go back yes that's the way you do it so it's really it's really you start with field values vectors at each at each or let's sorry at each if if I just take one gate at each input the two inputs they're like symbolic fraction numerator p q p for always for numerator and PQ of the of of this input and PQ of the other input and the

symbolic the symbolic representation is just pure polom polinomial expression you know you take just the product this is just the product of of the PK + one left time c k + one the denominator of the right plus you know it's just the ordinary law you know you know for integer I see see okay okay okay that that now that makes sense I I got I got lost here my bad that that makes complete sense now thank you thank you very much I do have another question but if anyone have has other questions like

feel free to say it or interrupt me or whatever um so when you got like when you got to this Improvement uh and now that you have like this is pretty reason of course but uh do you think there's any kind of or you foresee any kind of way to continue improving uh via gkr or via any other way uh log up does something ring a bell for you towards maybe we should look into that direction or something like this not not we didn't think about it yet at least I

didn't uh so I also never thought about what would be time optimal here my feeling is in terms of commitment effort without Multiplicity just a single column is quite good don't don't know don't know if there are further improvements here I mean there's there are possibilities as you pointed out in a previous question of yours to do a higher radic step but uh I think one has just to write down uh the cost of the

sum check of having increased degree but roughly it's uh I would say you lose what you win few steps but each step is uh is is more costly here that's fair because of the higher degree so yeah short short answer I don't it's also true that like of course not for the bottom rounds but I don't know at which point in the heath of the tree but you can definitely precompute like have precomputed table for a bunch of the a bunch of the operations that you will perform on the tree at at least up to a particular up to a particular he like of

course for 250 something bits it's definitely not feasible for 32 even even not probably but maybe at 16 bits you can already have a pre-computed table that that speeds up like this part of the three towards the end I mean this tree here is takes takes witness data from the bottom so I wouldn't know how to use precomputations here but even if you use precomputed data sorry even if you use only witness data at the bottom it doesn't mean you don't need to compute the operations in the in the intermediate uh levels of the tree right I mean typically that's that's

what you do as the pr you do step step first start with the with all the values at the bottom layer hyper Cube make the pairwise sums you have the values over oh I see size yeah uh and so on and so on that that's that's how you so so I wouldn't know I wouldn't know how to improve here but a question is that I entirely ignored from my point of view is how uh dealing with larger tables how about cross uh having a several table lookup we call it cross table lookups fractional subject that don't batch

well polom subject batch well without without increasing the degree neither neither domain size nor degree of constraints but fractional Su check uh don't batch that well so so you cannot interpolate or do anything if you just say I want to batch them over the same domain just means you increase the degree here okay the the P of Q over Q's of of different uh which are subject to different sub subjects uh if if you write the symbolic representation of the sum you have them of corresponding higher degree Mak so

so yeah it's an interesting topic anyways definitely thank you thank you very much for your answer you're welcome okay if no one has written anything I don't see anyone asking anything else so I will assume there's no more questions uh from my side I want to say thank you Rich because this is this was a really nice presentation at least from my side it's one of the present that I've understood the most things to be honest so thank you very much it was really really really nice uh it was really good and really exciteful uh so I guess that's it thank you very much for for coming here and

and talking about us talking about uh loog up improved uh to us uh I said it was really insightful and and hope to see you soon here again uh for for the rich Solomon over the Circle Group thank you very much cheers everyone