ZK9: logUp - Lookup arguments based on the logarithmic derivative - Ulrich Haböck

Transcript

foreign [Music] thanks for the introduction first of all so I'm gonna talk about uh log up uh usually I'm not a friend of names for protocols but after a while I I was tired always saying about lookup argument based on logarithmic derivatives and uh so it somehow just happened to be called log up uh quite recently actually the paper uh well the ePrint that I I did this piece of work actually was initiated by the ck8 in Berlin

so I was sitting there watching Benedict's talk also William talk back then no idea about multivariate provers uh and started to think how could you ever prove the permutation argument without having a Time action on the Boolean hypercube uh so and uh yeah so and that put me that that that really set me back to the uh to the idea that I had back when I was at Horizon Labs like one and a half years ago or something they just played around yeah you can turn the grant product argument of long into a grant some argument using logarithmic

derivatives I didn't see any use of it but now it seems to have found its purpose and its batch lookups or what I call batch column lookups so just just the frame here what what I considered because there's so many terms there is there are multi-column lookups uh some people call them Vector column lookups and so on uh so what I consider as batch lookup argument is really uh batch column lookups so that's uh so you have typically one table one column table I mean that's not restricted to one column but an ordinary size table so

it's it's of size of uh of an ordinary Trace length let's say 2 to the 16 to the 20 it's not so we're not gonna Target the techniques of gabison and Eagan that go beyond that that do that are able to Leverage linearity of kzg in order to provide what I call huge table lookups so this is the classical framework here so no kzg typically below but it's not restricted to that so uh so we have one column table say but we have many many columns of witnesses that are subject to one and the same lookup and this situation this arises but

specifically when you deal with ckvms just consider uh typically what they need to prove at certain for certain Columns of sck VM if not many uh is that they're all all entry in each column is say a 16-bit word so it's a so you have many columns subject to one and the same range proofs uh I don't not sure if Hamish is here Hamish is here I never can remember for example the arithmetic unit of system zero how many how how many columns are subject to 16-bit lookup something like 70

yeah 70 200 so just to give you the scope so it's not it's not uh how to say uh exotic that situation that you face many many columns 70 to 100 columns subject to one and the same range check or look up another thing is that that was pointed to me actually by by bobbin from from Biden so if you have a ckbm and you decide for a lookup-based arithmetic hash function like tip 5 or take reinforced concrete or something like it you typically by chip design end up with a hash chip

where you face the same problem because you want to scale you have a lot of columns subject to the same lookup so these are the use cases the two main use cases that are faced maybe there are others I don't know but these are the main use cases uh so this stock just the structure of it I'm not gonna be very math-like so it's early in the morning I had some beers yesterday uh actually good white wine so I'm gonna keep that as reduced as possible and as picturesque pick to ask how to say that okay so so I will just give a quick intro how

in general uh multiset checks permutation arguments and lookups what's what's a little math behind what's the idea and then we go to this state-of-the-art protocol if you don't use kzg and this cash quotient improvements so the state-of-the-art generic lookup protocol is plucker so that we that I will just simply sketch what's the main idea here I call it a geometric idea I'm not sure how Ariel would would see that uh I confronted the other day so and then I'll talk about vlogger what just a quick overview uh and last but not least that's very important because uh

I'm not the only one who was thinking almost at the same time on uh using logarithmic derivative something that goes back to you know uh calculus one you know uh its usage in the context of of permutation arguments lookup arguments and likewise in crypto uh and most of all I was not aware of this work at all lime so uh yeah very easy hi uh so it was on RL who to first he was the first one who pointed me at it you know like when when flucoff was already out and also my paper uh which I called very complicated

something like multivariate lookups on whatever even remember the name so it's the one that I referred and I will post the link at the end so and uh so flow cup is very much related even the the don't explicitly call it using logarithmic derivatives is implicitly always present it's even more present in the subsequent work uh even together with gabison CQ and I'm looking forward to your talk to Ariel's talk on SQL in okay so multi-set checks promotation arguments so how do they work so typically you do just one thing what do

you want to prove you have two sequence sequence here this is the witness sequences that's typically the table sequences sequence uh in this case they're of equal length say and you want to prove that these sequences are the same up to permutation so that means uh we fear one value occurs three times it cookies has the same occurrence number here so that's why it's called multi-set equality or multi-set check so and what we have in mind is that okay you just construct two virtual polynomials uh I I come back to it why version so virtual polynomials you just have to remind in the designer group and they all encode just by zeros uh the the the the elements of the sequence

and uh of course uh these two are combinational permutations of one another if these virtual polynomials on the left side and the right side are equal as polynomials and that's what you use because you don't want to put that for approver to compute this polynomial it would be too expensive what you do is it it's kept virtual nevertheless it's challenged you challenge if you challenge you sample a random challenge for x and then you reduce it to just proving products of Scholars instead of linear factors

so we reduce It To The Ground product identity and typically you prove it the Planck way in the end but that's not so important so that's the thing you have virtual polynomials so two two sequences are the permutation of one another if this virtual polynomials are are correct and overvaluing the in the randomness you sample uh if the pro if the products the grant products are the same then we may conclude over overwhelmingly that the polynomials are the same so that's that's the that's the way that's that that's the idea behind any permutation argument and this idea at least goes

back to buy a growth if even not further I'm not sure rbl you probably know better yeah I don't know that's my requesting okay lookups is a bit more subtle why that so you again we have two sequences and now they're not necessarily of the same length so with the sequence and table sequence and you want to test what are called set membership so you remove all the multiplicities reduce them to multiplicity one even if a value of Q is 10 or 100 times and and you want to prove that that the the set of values of the one sequence is

contained in the set of values covered by the table sequence and what does it mean you have to take into account that uh that certain table values that occur in the witness Seekers occur more often than just once the table typically references just once so you uh and that's the case even only to talking again in this virtual polynomial uh uh representation it means like uh this uh this sequence is as I said contained in the other even only if you can find multiplicities integer values zero one two three whatever you have to adopt them accordingly at most as like

the length of the sequence of course this typically is not too large but large enough but in any case so you find if there exists a sequence such that uh this polynomial can be produced by the table roots choosing the right multiplicity which might be zero so if something doesn't appear at all in one table value it doesn't appear at all we choose the zero here if it occurs once you choose one if you could use 100 times you choose hundred so that's that's that's the that's the issue here to find uh to uh the problem is you can't prove it that easily the I an IOP for this type of identity is problematic and the first one that I

know uh that tackles it is uh the one from the Aria paper and what to do is uh because you know this sequence let's say it's it's 2 to the 18 typical Trace length uh long so so you decompose the you know that the multiplicity can be at most two to the 18 let's say they have almost 18 bits so they encode the multiplicity bitwise use the speed representation of course it's always challenged this virtual this polynomial is always kept virtual it's challenged at the random Alpha but then the main importance is you encode the multiple Simplicity in a binary representation and then uh you you

commit to this uh to these bits column I mean instance wise and then you prove uh you prove these powers of two of uh you you put together using the powers of two of the table roots and you prove you and I mean they can be pre-computed so so I I'm it's not so important I didn't well explain it right now uh it's not gonna be important for the rest it's complicated that's the only thing uh that I want to give here so look up uh I call it the integrability Criterion I don't know how Ariel would see it

so uh so that's the way a house seeds so so you have this is amazing idea in my opinion so to prove so so consider if you have a sequence consider the derivative what do I mean by the derivative of the sequence it's uh it's something like this this is the point where at where I'm looking at the derivative and this is the increment the next value is irrepresentative for the increment and if you have one if if you want to prove that one sequence is contained in the other it means that every increment in that sequence

must occur also in the table wait it's not that simple uh so consider maybe the constructive ways easier here to explain why this Criterion holds so give your guess a hint of it so you take put this sequence together you take the union of these sequences and sort it okay then of course uh you can say that if you look at the derivative of this sequence that uh the changes where I make changes could be only come from the table and then you hit that value

of the table a certain number of times multiplicity many times that value occurs exactly with no difference at all because it's sorts not well explained but it's this I hope it gives you a Direction so uh in short we have this this subset contained the table sequence set even only we find a function as an integral that puts together the derivative of T and uh and here always equal derivative set to Zero from from the witness sequence or it in polynomials it looks like this if it's too much just think of

the lunch in a few minutes and so on yeah so so this is just yeah you encode these derivatives as zeros in the multivariate sense so this is like decomposing a multi a pivariate polynomial into its sotus called zeros and and the vector uh which encodes coefficient wise exactly the derivative vector and here this is the corresponding encoding for the table uh increments and this is the corresponding term for the witnesses uh always at the same level so zero increment here

yeah and that's as usual he's only kept virtual and then you sample randomnesses for x and y and end up with Grant products to be proven so how would that look look like for batches uh it's generalized straightforward so it doesn't so what in the previous slide it was considered just one column sequence same holds if you have 100 columns table you merge them and you sort them so that you end up with something like this I may just this line in order to visualize that it's just as large as the union of these two

yeah yeah I think these slides are shared I'm not sure are these slides shared or on the web page or I don't know in any case I will yeah maybe one thing to say about that that's not the form you find in the book of paper that's the one uh you find in a blog post of uh in a hack MD of Ariel so it's it's the more elegant one the the one from the paper is more even directly

thinking in the derivative uh having here not the next point but the difference really the difference so it's really more pure at it's it's the vector field you get when you're uh the vector field of the derivative so uh going back to Patches so you you take the joint Union you sort it accordingly what I'm never saying what's the order the order is as given in in in the table uh and so so you person it to so this depicts just the main cost of the protocol it's it's very rough so if I only look at how many extra columns you

have which has impact on the commitment effort of the prover that means beside what has to be what is committed anyway because typically it's part of the IOP for some snark or so uh you need to commit the sorted Union of this uh of this joining here the sort of unit and then you need to prove exactly the product we were talking about this one you know challenge at alphabet repeater so uh and this leads you to if we just restrict ourselves the data to just for Simplicity and to be able to compare the

log up if you restrict yourself to to to an IOP of degree 2 only that that amounts to having running product uh as many columns as these two boxes are large you take the quotient of the two that's why you add only one running products you prove it's equal to one like in Planck so so this is this depicts uh the commitment effort of plan lookup applied to batches of columns and that will keep in mind I'll return to that you don't have to keep it in mind like autistic so so I I'll I'll return to that picture in a

second so log up yeah logarithmic derivatives uh yeah it's a simple thing from from from local calculus from analysis you know uh you take you take uh if it's analysis you know you take the logger you can take the logarithm of a function typically if it's not negative valued or so you know and what happens if you make the the derivative of it although it's the chain rule no chain rule all the derivative we have the log of some in a function all the

derivative is uh 1 over the something and then times the inner derivative and that's called the logarithmic derivative because it's the derivative of the logarithm of something and that's exactly also what you use in the discrete world as definition logarithmic derivative the definition of it is the formal derivative which is s it defines just for polynomials you know like uh I will do some examples it will be become clear from it so it's a formal derivative of uh of the polynomial in

question and then over the initial polynomial here why do we do it the main reason is what important property does the logarithm have it turns products into sums and the same will hold also for the derivative we'll see that in a second I just have to switch one thing more yeah that turns product into some let's let me let me show that on the on the sketch part it's more it's a nice surf here so

so let's consider product here uh well maybe it's better to use the formal definition here you know I mean from from from using calculus one it's obvious you know just just to to par to rephrase what I've said you know it's it's it's the sum of the logs first of all as a function before I do any any derivative and now and now I do the derivative consequently bilinearity we have the local Republic derivative over of p plus the logarithmic query but

derivative of Q and that holds also formally there's always a strong relationship yeah okay so uh just quickly uh going over that uh over that example you know if you have two functions one is a linear factor with uh with that root and the other one with the other we get here this you know just if you use definition you make uh the the derivative uh we take the product rule here it's one time one times this plus this times one over the original and if you can

always cancel out if you split the sum and counselor out with the common terms you end up you see it once again it's the sum of the two so zeros are turned and the important so what we see here that's why I choose this example zeros are turned into calls and if you have the same zero doesn't matter this whole whole things work so then we have the same here so the same Polo Q is twice additively twice or more General if we have some uh see some root with a certain multiplicity it occurs exactly with the same multiplicity of the pole and that's the useful thing used by log up lookup and fro and others sorry

yeah I mean just as a definition you have you have a poll of order one here uh yeah in that case so so uh even if you have a root has multiplicity 10 it's a simple Pole with Multiplicity 10. so and that's that's that brings us to the key Lemma of uh of of log up so we now can the funny thing is that additive multiplicity is much more easy to handle the multiplicative uh so multiplicity of poles are much more easy to handle than that of of of roots and uh so one is

contained in the other if we find the multiplicity sequence such that we have we take the multiplicity of the pulse and get the sum of the poles of the witness sequence and that's the one what you challenge and end up with the sump check not Grant product with a sump check it's rational though so you have to turn it into a polynomial expressions and so on but it's a subject okay so how does it look for batches so many columns table we have to provide the multiplicities as many as we as the table is large many and and uh these are the helper function returns uh the turns

a rational subject into polynomial expressions to to prove in a polynomial IOP the one over terms uh I I was wasting too much time in the introduction so I cannot explain this now but believe me you need them unfortunately but then for the for and that's that's the key difference to pluck up and that's the power of Grant sums over Grant products fall together without increasing degree even if you have one million columns it's still a degree one some check you do so uh so you end up with a single but having a law degree with a single

column of rounding sums okay so just to recap the two uh the two generic lookup protocols lookup you know what extra columns do we have besides the witnessing table sorted Union there's no way around it and then the running product uh for you know that lookup identity lock up the helper functions but then only a single column for the running uh for the running sums and that's the big difference and moreover you can in the same way if you say I don't want to run a degree

tip the two prior program I can I can go to degree five seven like plonky two uh then you can do the ordinary off trade between reducing the number of columns that holds also for the five for the running products here your batch products together by increasing so let's call less running uh running products columns versus increasing the degree and here's the same less helper functions so just recap that's the conclusion sorry for being a bit longer so so just roughly to give you an impression uh log up has about 50 less extra columns to commit and that counts for

this wide Trace programs uh several ckvm implementation phase uh it's and moreover that what I said before that can be reduced using this off trade degree versus less columns it's already implemented by William so we have it now plonky two code base it's not that you reviewed but it's online it's public so and if you would like to see some math some more details uh click on that link thank you [Applause] yeah thanks a lot Ulrich for this nice

talk um we can maybe take one or two quick questions while the next speaker can already come forward and set up um I will go around because otherwise we don't hear the questions on the recording and can you answer into that microphone please so any questions yes might be a stupid question but between permutation argument and look up subclimation argument you look at the cardinality lookup value look only at the sets that that's the middle way right when you look at there's a middle way where you look at the sets but you also want the cardinality to to be less than in the other set I'm not sure it makes

sense so but is is that a middle middle way between the two sink never thought of it before and I'm to be frank I'm not sure I don't don't can't come to 100 follow your question okay yeah so so between look at a permutation argument where well the cardinality should be the same in two sets and and where you only look at the set inclusion yeah there can be a version I'm not sure it's useful well the stat inclusion is is important but the number of elements should also be less than in the no I mean for the lookup the big witness sequence can be super huge yeah because if if you only mentioned uh values from that comparable small table then uh as a set it reduces to something

small in any case yeah yeah okay so that's good thank you more questions thank you for the awesome talk and research uh in the paper you mentioned uh yeah you can go from a multi-period setting to a univariate setting do you have any intuition that you can share if any behind how that reduction occurs I've been to Pro the only reason why I wrote that paper for the Multiverse setting was because it originated in my thoughts about multivariate Planck so but uh everything that I was talking

here I mean I was that actually applies to the only variate case it just simply just the same if it's the same I did it because I wanted to learn multivariate the world nice but in the end it's the same you just have different techniques so some check is more the core in the multivariate thing but you don't need to have questions you better don't exist quotient polynomial on the other hand so so but essentially uh I mean plonky two is an univariate prover so it's if you maybe if your coder look look there if it's not obvious to you how to put the the multivariate polynomial IOP into the Universe I will dive in this week okay

all right so I guess we need to move forward let's thank Ulrich again [Applause]