ZK Paris: Panel on Lookups with Anna, Mary, Ariel and Andrija

Transcript

all right everyone as you I don't know if there's anyone at the back who'd like to join us please come and sit down if you want to watch our panel so I hope everyone enjoyed their lunch and now we have a panel on lookups with Anna Rose from ZK validator Mary Miller from the ethereum foundation Andrea novakovich from geometry and Ariel gabazon from zeta function Technologies fantastic [Applause] all right so today we're going to be talking about lookups look up tables look up arguments

um actually maybe we could start with a like this is actually genuine question am I supposed to call it look up tables or look up arguments and what is the difference uh the table is the table the argument is the argument that you've looked something up correctly in the table so the argument is looking up something in the table yes okay I guess that makes sense as a topic what is the preferred term I don't know all right we'll leave it that lookups is what we're gonna go with um I want to do a short history of lookups what they where they started maybe we can start with look up which I think is I mean lookups are an older concept but yeah maybe in this context

where does the story of lookup start well actually as far as I know it starts with a paper that Mary co-authored uh go offering is the best I can give that the idea was sooner Jacobson's actually the the idea yeah ah okay cool cool uh so this is right this is a paper called Arya that's the first time I've I've seen them uh yeah uh and uh yeah and then I think uh pluck up was uh maybe the the protocol that started getting in into the I don't know

mainstream Consciousness in in some sense I hadn't realized that there was this earlier can you actually talk a bit about that uh so this was uh very very early I would say ZK evm project oh well zkvm project okay the original well the original dkvm as well uh not the original there were ones before but like uh certainly an early one um and it was really looking at a tiny Ram so that was the VM that it was using and it was sort of saying if we have this knowledge proof can we prove tiny Ram um and for that project uh they were used we were using this um snark which is like linear time and because it's linear time you can then have very nice

properties about the theoretical proving time of the system it's an early work so I say theoretical and I kind of mean theoretical um but at the same time the idea of if we use lookup tables this could make things a lot faster yeah it came up so it was useful was it was it written out in it or just suggested was it it was written in it oh cool cool nice okay and then we have pluck up uh and it stopped traffic so this button doesn't change anything I think your mic's on uh what was the question and then there was pluck up uh then then there was a pluck up yeah

uh that I think popularized uh lookups in in snarks uh uh I guess then there was the almost in parallel but uh there was the Halo 2 lookup argument which is a slightly simpler version uh of cloak up maybe or like every time I look at pluck up I get a little confused um the streets of Paris are also controlled and uh yeah and uh I don't know how much further to go so let's keep going so after those two works I'm kind of curious like when does is there anything between that and Coke

in terms of lookup work not that I'm aware of so yeah so there there's actually an interesting history because I think a little hmm well maybe in parallel or a little before there was the What's called the log derivative lookup that interestingly like people came up with independently a few people uh Liam Eagan uh Ulrich uh Havoc that wrote it the I don't know the most clearly so his paper became the the standard for that and others came up with it independently and in the end like it ended up being used in in sort of this new generation of lookup protocols uh starting from caulk um

let's talk about Coke where does the idea for that start uh so the idea actually started from a membership argument so typically when people are doing membership proofs they would do it with a medical tree right you would have this big big Michael tree and you would say I know a path to this entry therefore I belong in this set and then you would prove all that inside a snack if you want to do it in zero knowledge which means you then have to decompose all of your hash functions and it sort of takes a little bit of proof of work and the thought here was that if we don't have too big a sets if we're not talking 2 to the 60 but you know more like 2 to the 20 or something like that uh can we do better with pre-processing to which the answer kcg commitments are

amazing is very much yes yes we can we can do things where the actual if you've done a pre-processing step the actual amount of time it takes you to prove that you're in this set is logarithmic in the size of the set without going through this like MP arithmeterization process um and it was well working on this where we were there like if we if we extend this and if we're not just trying to prove one person in a set but like lots of things in a set that that kind of works too right we can we can make that work um and this is really what caulk was it was the result of that I mean I made the association between uh this is a lookup table almost immediately because I was very familiar with lookup at the time

um so that that helped cool uh and then I want to talk a little bit about the most recent work as well I know that there's after I know Coke is just sort of like a Monumental one and then there's semi Coke I think there's like another variation I think you should talk about seven let's do it oh that's something does it work I think no no that's something very different uh that's uh what Mary said um that if caulk originated for uh from like one lookup argument was a step back so oh it's returned to have this very efficient uh

one uh membership argument proofs and yeah uh we did a lot of customization and a lot of small subprotocols to make this extremely efficient cool why did you take that step back there so because we were mainly interested in can we kind of like maybe modify caulk plus which came after caulk to allow that one membership proof uh and to like easily integrate it with current proving system like Planck and stuff so that was our thinking how how we can just like easily plug it without too many changes when you say efficient how efficient is it oh yeah so uh okay

the Brewing time as we know does not depend on uh uh the the size of the set so the main goal was that you always have like uh this evm3 Lemma as our colleague they would say that if you want to have snark friendly hashes for Merkel trees you pay a lot in the smart contract for updating the group so our idea was like okay can we remove the Merkle tree so that we make everything cheap like verification Brewing time to be constant and that you pay a really cheap uh in amount of gas in the contract and that's what it unlocked so you don't

need the trilemma anymore cool okay I want to talk about everyone's recent work on this topic too Mary what's your latest on lookups so our latest work Ariel was also on this work is probably below um and this was a work that arancia was really taking the lead on but it was saying okay we have Coke we have this thing that's really nice in terms of how it depends on the size of the table but actually because we'd really been focusing around um well doing it in the case of just one lookup or a very small number of lookups we had this like additional cost which was saying that the number of lookups

you do it's going to scale quadratically in that and at the time we're there like it'll be small it'll be fine and um well quadratic isn't great if we're being honest not if you're trying to use it in the same context as people would be using the Halo 2 lookup argument or the blackout argument so it then became sort of the big question of is there a way for us to get that prove a time down and this is really what we were focusing on and we were able to get it down to um not in not carcillinia but not far off it's m log squared M and the that cost the M log squared um is coming from a trick to do with pre-processing all of

the kcg commitments cool what's your latest uh well that works right the the latest on the look up front is something called the CQ uh I think you have a second part of that well so in CQ and yeah to a degree and all this sort of latest line of lookup Works starting from caulk uh there's we use this technique uh called cached quotients so we have uh yeah we have a paper where we use cache quotients and not for lookups but for fast linear operations uh so that's a paper called the CQ lit Lin that Liam and I wrote

um yeah but maybe to give just a little uh also say a word about CQ but but give a little context so yeah so again sort of the big question was can you have a lookup argument where uh the prover time doesn't depend on the table size and and sort of caulk was the was the Breakthrough that that answered yes like uh it's essentially you know yes essentially and the basic idea there was okay let's go down to the subtable of values that we're actually going to use and work just with that uh and then sort of the the Breakthrough

step is how do you prove in time that doesn't depend on the table size that what you're working with is a really a subtable of the original table and not some values that are not in the table at all so so then there was this sequence of Works uh call plus flock of Baloo that all sort of used uh this this Paradigm of let's try to go down to a subtable and do that as efficiently as possible and then okay when we're already in a small table you can you know do whatever uh and sort of what happened in this last work uh CQ is that's what I'm saying it's interesting that sort of the histories came together there was this log derivative lookup that was not in this uh

works of don't depend have the proverb time depend on table size it did depend on on table size uh but then sort of what happened in this work CQ is we said okay if we look at this log derivative lookup and we just try to run it in a way that uh the approver doesn't depend on table size and we sort of Leverage pairings for that it it can work it basically works so there's no need to go down to a subtable and work with we can sort of directly work with a log derivative lookup on the original table in prover time that doesn't depend on on table size at least when we have pairings we can do

that I want to ask you you we keep talking about these lookup tables and the lookup arguments using the lookup tables where are these stored because I think when you use the term table you think sort of of like an index of something that's you know would need some sort of storage I sort of know maybe the answer to this but like yeah where does it exist in space is it in the math hidden in the math where is it um I think the answer to this is like a little bit dependent on your use case so when we're talking about

um calc and when we're talking about CQ and when we're talking about Baloo we're very much talking about these pre-processed tables and in this situation you would assume that the proven knows the table and the verifier has seen the table in the past but they don't need to reread it because they've already seen it they've already done their pre-processing there's also a type of lookup table called a dynamic lookup table and this would be something which only the approver ever sees because they're really creating the table during the proof is it is it a separate file entity is it like I'm still trying to get that tangibility of it oh so yeah like as Mary said once you read that stable and you do some

operation on it you will just get like a bunch of elliptic curve points okay and you just need to store them somewhere and then depending on the case you can have some service that will serve that you can like storytelling in memory in ROM whatever not it but yeah I just like now you can treat it just as a byte that you have the way to parse cool later um I have another question which is about and you you sort of touched on this in the story of the trajectory of these different systems but it's the composability with the other parts of systems so like look up tables did they work with all other forms of folding schemes like we heard about or all other

forms of uh I don't know IOP polynomial like you know is there is there like are you do you have to almost design these to fit specifically in a proving system to work together with some of these other techniques or can they be like almost generalized and work with all of them I I think I think it goes pretty smoothly uh especially if you look at uh the protostar paper so so there they they talk about just generic interactive protocols where the prover sends some messages or call them polynomials verifiers sends Randomness prover sends some messages very very sense more randomness uh so this model that also I sort of it's what I call the rap in uh uh an old

blog post randomized air with pre-processing and then you check some low degree equation on the combination of the randomness and the the prover polynomials so yeah so all our protocols uh you know copy constraints plonk Gates r1cs uh look up all all the lookup arguments we know they sort of fit into this uh this framework uh there's a little Nuance with yeah with using pairings for the further verification as you do in Culkin CQ but yeah but the short answer is it yeah just the lookups are another instant you know equation that the verifier is checking they're not that special like it's not that hard to you

and he combine them could you then switch out the lookups of Halo 2 and some of the newer work if you wanted to uh that's kind of discrete log based so you need pairings to use in your work okay what's an example of a system that you could use it with well I mean we are actually Andrea and I and others we we are working on at least the version of so CQ needs pairings so at least the fork of Halo 2 that uses kcg and we yeah we are working on amazing and adding a being able to use CQ instead of the Halo 2 lookup argument there and and we're

excited to see like what the performance boost will be cool do you want to say something about that too yeah so Arielle just asked me in yingtong do you want to do this and we said yes it was very simple conversation and yeah we kind of did it uh we still didn't Benchmark on this very important circuits that we want to optimize but we have like a lot of plans to do on that trajectory so yeah hopefully we will release uh some stuff soon uh in an interview we did a few months ago you talked about the sort of the

additive homomorphism and the multiplicative homomorphism does that play any role in which systems it can work with yeah absolutely you need you need the the this this generation of protocols from caulk to CQ they need kzg they need a pairing yeah they need some multiplicative thing got it I suspect that might be fundamental as well although I'm not sure um do you would you say uh well actually can lookup tables be used with things like Starks uh yes but not the more recent line of

work so the stuff that relies on pairings stocks pairings um pairings are sort of something which is not something you can instantiate with hash functions put it that way okay um so but if you're thinking about some of the older schemes certainly flick up and Halo 2 yes you could do that with Starks oh cool um one of the questions when I when I was prepping for this I asked a few people what they wanted me to ask and I think everyone had the question some some variation of like will there be a time where we don't need these like is our lookup tables an optimization because other parts are not fast enough

or yeah is it something that will eventually be replaced I mean it's always going to make your proof of time faster will we get to a point where we don't care about proof of time is really what you're asking I think there which um yeah I'm not showing the right person to be the judge of that hopefully I mean I think right now there's a there's competing there's some optimizations that are not competing with each other this new line of lookup protocols since it requires pairings it is a competing with the the fry the sort of fry route and uh yeah I mean it's hard to see what what

it's interesting to see what will happen with that uh because yeah using smaller Fields the sort of and even codes that are not even fry that are even faster than polynomials that they're getting a lot of speed ups that you can't in the pairing kzg elliptic curve world and the pairing kcg elliptic curve world you have these tricks like like in these new lookup protocols uh it's hard to ask like even now I would say the the speed ups are sort of comparable they come from different you're gaining from different things but the uh it might be that right now the total speed up you get on both tracks is sort of comparable I mean I'm biased toward more the pairing side uh yeah and and in the pairing side I think

you'll always look use tricks like you know fast lookups using pairings and I mean why not use it if it gives you a 5x or um yeah and in that track of you know elliptic curves you you won't have this thing that the basic operations are so cheap that that it does it just doesn't matter cool so how much time do we have a chance for us to open up the floor I'm wondering if anyone here has any questions for our panelists about lookup lookups look up arguments look up tables um thanks for the discussion uh Andrea

perhaps a question for you if you'd comment on like what are the what are the difficulties of incorporating these like log derivative based lookups together with the existing Halo 2 system that would be really interesting oh so yeah it was just something new that didn't exist and um we had like two as a real said the pairing is required so it kind of break a lot of abstractions that we had so we needed to modify like every single piece of the the Halo 2 and also these protocols which are coming with very uh specific pairings if I can say like very specific pairing equations which are not

like batched kcg we needed a smart way to automatically batch them because what you see in papers is like okay you have all these pairings and you can batch them but when you get to something dynamic dynamic like you don't know how much lookups you will have in your circuit or you want to like keep that generic we had to add more work to to make it all like generic and yeah we were able to do it thanks for the question a follow-up would be like do you um you know after this experience see any uh room for improvement in in Halo 2 like

in the in the interface or the abstractions or anything like that um so okay it didn't break abstraction like I think abstraction of how you write circuits and stuff is very nice it was just abstract abstracted from the commitment scheme which we couldn't do anymore so mainly that's why we had to break everything uh but we still like hello to a lot yeah thanks I like it too I think there's a question here so this is going to be a little crossover moments between our panels um Arielle you said that there's sort of two tracks that are tours optimization

so the fry track and the pairing track but I'd rather there's also like the folding track where we now require curve cycles and so we can't have efficient pairings on both sides do you see these things as incompatible or is it just a temporary setback uh well I actually uh I I really enjoyed the piano before and the the one thing I I disagreed with uh during the whole was was that you need curve Cycles I'm I'm of the opinion that the the number of like scalar multiplications uh you know during the fold right it's when the number of scalar multiplications is like 5 10 15. it's not that bad to do it without a cycle and uh I mean that's for

example that's what Aztec Aztec did right they have the segregation with like 15 18 scalar multiplications they just do it non-natively so so I think I yeah so so that that's I think empirically yeah people for you know maybe because of the eventual complexity they they don't they in any case they don't go to Cycles when for a small number of uh yeah scalar multiplications one of the more recent creative uses of lookups that I've heard is looking up State transitions in a VM what are the most common use cases for

lookup arguments and what are some of the biggest wins that we can get from lookup arguments I mean one thing that sort of would be quite cool to be able to do I'm not sure that we're totally there yet but hopefully we will get there is when it comes to uh trying to do range proofs in circuits at the moment we we we're much better at it than we were before is getting faster it's getting to the point where it's no longer there's this terrible operation which is going to massively drag down the speed of your circuit and one of the reasons for that is we do have these additional tools we

do have these lookup arguments we do have these ways of arithmetizing things if we can get to the point where we can just say to developers when you're writing your circuits do a range check on every single element to make sure that it's in within the range of 64 bits then we can kind of natively tackle 64-bit architectures and that would be nice there's a question back there I have like a bit of a two-part question so um with some of these lookup argument uh architectures where you have a constant time lookups like uh as an analgia suffix tree is like sure you can search

a substring at a a string Corpus in constant time but you have the pre-processing cost of creative suffix tree it also remember requirements are alike or a magnitude higher because uh you have to pre-process the the string database as this tree like architecture and I guess my question is uh is there like an increased cost board by other parts of the system with these time lookups and if not can you kind of motivate with intuition why that's not the case an increase cost in the pre-processing or processing or maybe the member requirements just basically like what's causing these lookups to be constant time in the input and not depend on the size of the table uh

yeah so it it relies heavily on on pre-processing and the the pre-processing now is is the new bound on the table size so for a table of size n you need to do a pre-processing of n log and group operations uh so right so that sort of seems to cap the current table size at uh yeah I don't know 35 bits something like that I mean hopefully we can actually get 35 bits and run the pre-processing um the if you ask like what what is the magic that allows you to not depend on the table size it's this this homomorphicity of operations like a pairing that uh sort of allows you for

example to to compare polynomials that you've never computed it allows you to compare polynomials that you've only com computed the commitments of and sometimes Computing the commitments of those polynomials is much cheaper than Computing the polynomials themselves after you do a pre-processing did you have a part two or was that both of them good good I think actually in terms of timing I think we're right at time um yeah thank you all thank you all for this panel thank you for listening thank you [Applause]