Lasso, Jolt, and the Lookup Singularity, Part II with Justin Thaler | a16z crypto research talks

Transcript

welcome to today's a16z crypto research seminar today is going to be part two again uh Justin thaler research partner here at a16z crypto and also a professor at Georgetown so yesterday we kind of heard at a high level how things work and sort of a lot of the importance of this work and today we're going to find out how it actually works under the hood so lasso jolt in the lookup Singularity Justin floor is yours thanks Tim all right so just a like a one slide recap of yesterday um so I'll look up argument uh Lex approver commit to a vector of value and then prove that all entries of that Vector reside in some predetermined table so lasso is a new family of lookup

arguments uh high level I think the prover is about an order of magnitude faster than prior works and this is sort of coming from two different factors one is the provers committing to fewer field elements in lasso than in Prior lookup arguments um and the other factor which is actually more significant is that all of the field elements being committed or small um and exactly how important that is depends heavily on what commitment scheme you use but in general in snarks and lookup arguments the bottleneck for the prover is cryptographically committing the values and for some really important commitment schemes um if you're committing to small values even if those small values reside in a very big field their commitment is

really really fast to compute okay also uh in lasso sort of inherited from the fact that it under the hood it uses multivariate polynomials and non-univariate ones and we'll see details about that today for many tables there's no need for the prover to commit to the table so in all prior lookup arguments uh the prover like always had to not to prove or the some honest party in pre-processing always had to commit to the table um and the approver would have to kind of process that commitment on the fly as well um and finally kind of a distinguishing feature of of the lasso family of lookups is that they can support gigantic tables so think of size maybe 228

um as long as the table session structure to them um and uh we build jolt which is kind of a new ZK uh VM technique um out of out of lasso uh which uses a property called decomposability of the table and actually prior lookup arguments also could handle decomposable tables um but probably with more overheads and then something really unique to the lasso family is that uh so there's a a bearing called generalized lasso which exploits a weaker structural property in the in the tables and I don't think you can achieve something like this certainly it's not known uh using univari polynomials rather than multivaried ones um okay and then jolt is a new ZK VM

technique which has lower commitment costs for the prover than prior Works uh and the one sentence version of the main idea is every time the virtual machine goes to execute A Primitive instruction um the that sort of the jolt prover will sort of prove that that instruction was executed correctly just by doing one lookup into a giant table that table uh contains actually the entire evaluation table of the instruction um so if the instruction takes 264-bit inputs uh the table actually has size to the 128 because there are two to the 128 possible inputs to the instruction okay um so I wanted to uh begin today uh before I dive into the technical details by uh giving a little more context for

lasso and jolt uh so I want to explain what this term lookup Singularity means from the title um so this was a term and a vision that was sort of put forth by Barry White Hat um in a ZK Research Forum post I basically means producing circuits that only do lookups all right and uh Barry's motivations uh described in the post uh were mostly about like auditability and formally verifying correctness of the snark generally uh the idea is uh that um lookups are fairly simple and it should be easier to like audit the correctness of like an implementation of a lookup argument

and the correctness of specific tables the lookup argument is getting applied to uh versus what a lot of projects are doing today which is um having very skilled developers kind of hand code gadgets tailored to you know each specific functionality that's important in in their application so if you if you look at especially like zkevm projects you know you'll see like tens of thousands of lines of code basically devoted you know like low level dsls like Bellman or cercom or something coding up you know very optimized gadgets and it's just sort of impossible to think that in you know 50 000 lines of uh circum or something

um there's like zero uh issues anywhere in there so hopefully it's just uh you know if you're just doing lookups with one lookup argument hopefully it's much simpler to kind of um make sure the lookup argument is implemented correctly and if you change the lookup table um to make sure that the new table is commented correctly instead of this sort of endless stream of verifying that you know this particular you know hand coded circuit is equivalent to the functionality of the day okay um so you know uh Barry's post a couple posts um definitely acknowledges that uh performance considerations as well um so it acknowledges that current lookup arguments are slower than we would like for this and also uh one of

the comments I think highlights that for the lookup Singularity to be realized you probably do need to support lookups into giant tables and mentions things like structured tables um I mean possibly allowing for that um but uh that's kind of you know it's hard to say uh in this post like what what else uh maybe Barry had in mind um and certainly you know uh well I hope that lasso and jolt are coming close to realizing this vision um okay so uh I think the way that jolt Works actually uh counters a number of narratives or just general beliefs uh in sort of the community that's building and deploying these snarks so I wanted

to describe some of them so one of them uh and you see this Viewpoint expressed uh prominently like on Twitter all the time is that uh simpler instruction sets should lead to faster zkvms all right and this is a pretty intuitive statement it's like if each uh step of the VM is simpler it should be faster to prove one step of the VM right and this uh sort of viewpoint is sort of taken to its most extreme in I think the Cairo virtual machine which was specifically designed to have kind of very small set of very snark friendly instructions okay but uh you know we saw yesterday that uh two things so one is I guess the the commitment cost for the prover and

jolt are are less than existing ZK VM projects and two like the scalability of the jolt prover like actually oddly it like doesn't really depend on the complexity of the instructions so something a little weird there's some kind of threshold Behavior where as long as the instruction leads to a structured lookup table uh whatever structure you know lasso or generalized lasso needs um it doesn't matter how complicated instruction is the approvers costs are actually determined by the size of the lookup table which only depends on like how big are the inputs to the instruction think about it that you know um right so if you have like two to the 128 possible inputs like whatever the

complexity of the instruction you were thinking of putting your instruction set like information theoretically it's just like much smaller than that input space is it kind of like it's just dwarfed by the number of possible inputs um I think that is a reasonable way to look at it it's sort of um you know I'm going to give a perspective uh after uh uh after I get through the narratives uh that I think might clarify the issue uh so let me just defer your question a few more slides it kind of depends on what the construction right that would be actually not necessarily um because uh for a couple of reasons

um so one is um all of these zkvm projects are trying to represent each sort of primitive data type for the virtual machine as like one field element or something and actually pulling out like one bit of a field element it's like not necessarily nice um so but you are right like you know if if a primitive operation for the virtual machine is literally like addition over the finite field or multiplication over the finance field you don't need a lookup and that is still cheaper um but the Primitive operations even in like the Cairo VM include things that are not just additional application over finite field and are the Joe approver commits to fewer field elements than the Cairo approver even though it's a much more complicated instruction set yeah

other questions how like all of this work focuses mostly on the prover complexity do you how much do you sacrifice on the verifier side or does it stay comparable to yeah so um it's the verifier complexity um in all of these um I don't want to say this um in in jolt the verifier complexity uh involves two things so um for each instruction the verifier has to evaluate a certain um polynomial capturing that instructions lookup table um for like all the risk five instructions and jolts that's like logarithmically many field operations so think like 100 field operations or

something um and field operations are generally cheap um you know like uh one hash evaluation is many many field operations right um and then there's one evaluation proof of a polynomial commitment scheme okay um and you know uh lasso's implementation right now uses a polynomial commitment scheme where the proofs are a little bit big although actually not really much bigger concretely than um some other polynomial commitment schemes popular today Frye in particular has pretty pretty big proofs um yeah so with all of these approaches all those ekvms the verifier cost does go linearly with the number of instructions um and the verifier also has to like

evaluate some polynomials kind of capturing the instructions and uh jolt is no different than that yeah I'll you know there's some more uh intricacies but I think that's capturing most of them so roughly still comparable to State yeah once at least once we you know uh switch up the polynomial commitment schemes and again I actually think even though so hyrax is what lasso today uses because it's built in the sperm Library it has square root verifier costs um actually square root looks like poly log for small values of n uh so I I don't actually think it's that bad um and then the the one other intricacy is um you know lasso Joel really use

multivariate polynomials like at their core and so you're not going to get that you know you can't use kcg commitments um all all known multi-linear polynomial commitments have um at least sort of logarithmic about size evaluation fruits kcg for univari polynomials is constant size uh but again there are projects that aren't using kcg commitments um and we're we should be able to match their proof size for example um okay so another narrative out there is uh there's a heavy focus on supporting what are called high degree constraints um so this is just like you think of this as a generalization of like multiplication Gates where you might be um sort of multiplying more than two

numbers or you know um doing other other operations that don't correspond to like degree two polynomials um and you know for example there's a recent word called hypernova and protostar which look to uh take a sort of a very different approach for exciting approach to snox uh distinct from anything I'm telling you about today uh which previously were only known to support degree two constraints and allow them to support higher degree constraints and people are very excited about that now now jolt kind of pushes like all the work the prover does almost all of it into the lookup argument and what's left is very simple and easily captured not just by degree two constraints but actually a very special kind of degree two constraints called r1cs okay so um I just uh you know I I still think High

degree constraints are important but if your goal is a zkvm anyway it's uh it's not actually clear at all that is important so kind of what uh what's more important than high degree constraints is is being able to use a good lookup argument basically okay um there's also a view that snarks over large fields are wasteful um this is actually one of the main reasons I think people like to use fry uh I mean it's also you know a voice lip to curse so it's possibly post Quantum secure so that's nice but um in certain settings uh yeah so so one like field operation over small field is much faster than a field operation over a big field right and um I actually have a blog post coming out soon where I'll

discuss why I think you know even if you can work over small fields in some applications it doesn't actually make sense anyway I have to get into that now I want to discuss the issue about this view that we should work over small Fields because working over large Fields is like wasteful right if you if you um you know the the rough intuition here I think is um you know if you want to prove her to like commit to a value that's pretty small um but you have to represent the value as like a 256-bit field element uh well there's just like a lot of extra bits in there that aren't doing anything and that's just a big waste and you're sort of paying a price in the for the prover um and I don't necessarily think that's the case because of this issue I

highlighted that um committing with elliptic curve-based commitment schemes to small field elements even if the element lives in a 256-bit field is really fast right and in fact you can actually do it with essentially one group operation not one exponentiation one operation uh per committed field element if the field elements are small enough um and then finally uh there's this very popular approach now to snark design which heavily uses recursion where people will take a big circuit break it up into small pieces so to prove each piece separately and then like aggregate the resulting proofs to get kind of approved for the big circuit

okay um and with current popular techniques there's really kind of no major loss in performance by doing this um in fact to get good performance is like the only way you can do it because um a lot of snarks people using today have sort of super linear approver time so it's sort of a diseconomy of scale where you deal with a bigger circuit and the cost kind of pergate in the circuit goes up because of ffts and things like that okay um and a lot of one of the reasons people are doing the breaking up by the way is because something like fry has enormous space costs for the prover like hundreds of gigabytes even for small circuits and so even ignoring proofer time the proverb space just you can't tolerate it at Epic circuits um and there's not much overhead

um in breaking it up into small pieces today all you really have to do is make sure that um kind of the the snark verifier when represented as a circuit is like significantly smaller than the original circuit that was proved so that way um when you go to aggregate the proofs by kind of proving you know something the snork verifier would have accepted sort of that's a statement that was smaller than the original one and so the overhead like isn't a big deal um lasso and joltz uh you actually see economies of scale instead of diseconomies of scale so you actually would lose something by breaking things into smaller pieces and the way to think about these lookup arguments and we discussed this last time in response to one of the questions was you think of

them as the prover kind of pays a fixed cost like table size to the one over some constant okay no matter how many lookups are done all right and then that cost gets amortized over all the lookups okay um so the more lookups there are like the better uh that cost gets amortized also if you're using pippinger's algorithm to compute nsms the bigger the pippenger speed up like pipinger saves like a log Factor over naive multi-exponentiation and you know log of something bigger is a little bit bigger um and intuitively I think we shouldn't expect to see diseconomies of scale right I mean in the real world we see economies of scale all the time um so I think if you kind of use the

right techniques uh in snark design uh you know one proof for something really big um you know until you like exhaust the space you know your approver needs or something should actually be better than breaking things into tiny pieces questions so would you say it's like better to have smaller instruction sets or smaller instruction sizes but you have a large number of lookups that have more complicated instructions in your CPU ah good because if you have like simpler instructions then you'll have like a large number of lookups and then you'll get economies of scale versus um complicated actually maybe I didn't quite quite get that um say that so you're saying um have your CPU have fewer instructions some or simpler similar instructions in some sense but that require like basically

you have to do them many many times so that you'll have more lookups into the table versus like if your instruction that you have is like very very complicated and like you only need to do one of that I got it great um yeah I think um there is a tension so that there is still like a per lookup cost here so like more lookups just adding more lookups for the heck of it like doesn't help right um and you know so it might help amortize the fixed costs better uh but then like you know there's a per lookup cost all right um uh so there's tension um and I think this tension uh it remains to be explored more so again like uh I uh I I think that you see the same tension when comparing like lasso to

generalized lasso okay where uh lasso applies to less General tables although still General enough to implement jolt entirely with lasso um but needs more structure in the table so you could think about um kind of using more complicated instructions so each instruction does like more work as you were saying and uh since there's one lookup per instruction um if you reduce the number of you know uh lookups enough since each instruction is doing more work maybe you'll pay for the fact that generalized lasso has one lookup with generalized last was more expensive than one look up with lasso so it's just it's attention and uh I don't have a great sense of um where's the optimal point I think it depends uh with something like like jolt where you know the instructions that was handed To Us

by risk five it's clear where you should be but with something like you know um you know uh just some application you know I want to improve knowledge of a bunch of pre-images of some hash function or something pick your favorite hash function and no one's telling you what your primitive instruction set should be um then it's a whole uh you know quandary like what what should your primitive instruction set be how complicated should each instruction be there's a there's a lot to explore does that make sense yeah Tim did you have a question I was going to ask actually if this is second half is this um this is about the lve case that you mentioned or also the decomposable case um wait this which yeah the second Point uh this last I don't have a fixed cost

yeah just in general like for the decomposable cases it's still end of the one over c um or that you're like a higher level that you're losing um on by breaking I mean because that was like as you said there you break up a look up into a big table and do a look up a bunch of logos into smaller tables right which sort of sounds like you're breaking the computation into small pieces without any loss right so I feel like that pushes against I see yeah well it is a tension between the per lookup cost and the fixed cost and the whole point of choosing C greater than one I don't have the whole cost here I did have it on a previous slide um maybe this is not necessary but yeah so the per lookup cost grows with C

diff actually in jolt um there's not actually a factor C in front of n to the one over C it's like always uh two there might be a couple instructions where it's four um even even though C might be like six or seven anyway um so you pick take C bigger to reduce the fixed cost but you pay a price in the per lookup cost and so you kind of only want to reduce the fixed cost um uh so much as it's acceptable so you kind of want to choose C to to make c times M and end of the one over C about the same and it doesn't make sense to go any lower than that so I don't think there's any contradiction to what I was saying do you sort of want to make the fixed cost just low enough that you kind of it's

not the bottleneck but no lower because there's another cost so this commitment costs are the same for both versions whether it's decomposable or LP instruction yes uh yeah I'd say the only difference um is that with the lde structured stuff um some of uh the uh CM things are um Big Field elements yeah that's the only difference cool any other questions okay so I don't know I hope at least these New Perspectives are interesting even if I don't think everyone's going to agree with me um okay so now I want to present A New Perspective of lookup arguments as as data parallel computation

um so our intern your nuo actually raised this perspective earlier um so that was I think it's really nice and uh wanted to share it um okay so many previous Works have studied snarks for data parallel computation this just means Computing the same function f on many different inputs all right um and they consider like what I call a polynomial amount of data parallelism um so you're thinking of um uh if the input size to F is is like n Bits or something and and field elements you're thinking of M as I'm most polynomial and N typically that's typically how computer scientists think um you know like a polynomial in the input size is is what computer scientists normally mean when they say polynomial um and these um these prior Works they

uh Still Force the proverb to evaluate F in a very specific way that is they turn F into a circuit and they make the prover evaluate that circuit on each of the M inputs they want to evaluate fet okay um and basically they're you know at least for the improvers perspective they tend to only save like a constant Factor uh by exploiting the data parallelism for the verifiers perspective the fact that you know data parallel computation is kind of inherently uniform um which is you know the verifier should only have to kind of pay for like one copy of f instead of M copies of f or something like that um okay but uh What uh I want to now introduce uh is is a view of lookup arguments as exactly data parallel

computation snarks for that but now where there's a huge amount of data data parallels okay so think of the lookup table exactly as jolt does where uh it contains all evaluations of some function f and what uh the key uh sort of insight here I suppose is now uh if f is Like A Primitive instruction for a CPU uh you should think of his input size as like logarithmic and so now like exponential amount of parallelism in the size of the input size is something that a computer scientist should think about right I mean this is exactly how Joel thinks about things right you've got like uh you know uh F has 128 bits of input and you're running

your computer program for a billion or a trillion steps so the number of steps m one lookup per step and is uh is really exponential in the input size to f okay and so what like lasso is is a a really good snark for data parallel computation from this perspective so I want to make sure you understand that so because so you're saying these AIS are like just sort of counters or these AIS are you either think of them as indices into the table or inputs to F because the table is the evaluation table event okay so so what's the logarithmic and what okay yeah so um

okay forget about logarithms and stuff like let's just call so that the table size is is exponential in the input size to f okay so another way saying is the uh input size to F is logarithmic in the table size okay and the cost of of generalized lasso you know it's like CM plus n to the one over C so there's this like fixed cost of like table size to the one over C um so for this Bend to the 1 over C cost to not be the dominant cost you really need M to be something like polynomial in N it might be a small polynomial it might be under the one over eight or

something and another way of saying that is m is you know exponential in log n the size of the input to f okay so what lasso is it's like a it's a really good snark for any data parallel computation as long as there is a huge amount of data parallelism like way more than prior works on data parallel you know smart should apply our low computation considered um and uh the I thought I had one more slide here I guess not okay so I'll just say this verbally um the cool thing about lasso uh from this perspective compared to um I think like the prior works on data

parallel computation is it it kind of lets the prover evaluate F anyway once okay so whereas the prior Works would make the approver evaluate F by using a specific circuit and using a circuit is gross in general right that's why we have this whole field of front-end design for snarks um uh with lasso the prover merely just commits to the claimed outputs of f and some multiplicities like two one or two multiplicities like per lookup or something like that and that's basically it okay so in it's sort of it's forcing it's kind of kind of tying the prover's hands less tightly

and as a result like much more efficient right it's like it's expensive to tie the proofer's hands tightly you have to spend more cryptographic operation to do that okay does that make sense but this only holds for specific apps now for this lde structured apps or for any type of functions can you do that yeah so um from the the issue is just uh from uh from the severifier issue really so you can apply lasso to any any lookup table the evaluation table for Naf and the prover's costs are whatever they are um and uh the let me think for just a second yeah um the key the verifier is going to

have to evaluate a certain polynomial associated with the lookup table at around the point and so if f is very complicated it's not going to be able to do that quickly um and that's why prior lookup arguments would have somebody an honest party in pre-processing commit to the whole table exactly so that the verifier wouldn't have to evaluate the polynomial and so on it can make the prover do it so you can kind of think of of lasso uh or jolt as like uh from the verified perspective it's a reduction from like you know executing um the transition function of a virtual machine of a CPU like you know many many times like a billion times or trillion however long the prover is claiming to run the computer program for and from the verifiers perspective it reduces the

work of doing that down to more or less executing the transition function just once if that transition function were really hard that's still a lot of work but we design you know virtual machines exactly so their instructions are really simple and like taking one step of the virtual machine is is not hard seems like uh vdfs could be a great application of this now um that's a interesting question you're saying F would be the delay function yeah yeah um potentially like repeated scoring or squaring modular squaring yeah so then it's just one instruction you're

executing over and over again so um potentially and you said they just have a very uh strong competitor in folding schemes um because floating schemes are sort of like perfectly uh designed uh for capturing like iterative application of a simple function um so I think look up arguments uh could be really nice for that um but it's just got a really you know folding schemes are also like really nice for that as well so other questions okay so um I just uh yeah let me just say a couple things um about um kind of pros and cons of the entire idea of Designing a zkvm and then I'll actually tell you how lasso and uh lasso

finally Works um okay so uh you know so jolt is a zkvm I I do think the prover is significantly more performative than priors EK VMS um I do want to discuss you know kind of good things and bad things about just ZK VMS in general okay so the good things about designing a zkvn and what I mean by this is like take uh designing like a circuit that kind of forces the proof like the circuit itself like executes uh the virtual machine just like runs it for a certain number of steps right so you know the program is written in the assembly code for the virtual machine and and the circuit you turn it into a circuit that um just executes the uh virtual machine over and over again

um so if you do this if you go through like the assembly code of a of a virtual machine uh and you use a virtual machine that already existed from outside the snark Community you can leverage like existing compilers that compile like high level code down to the assembly for that virtual machine uh that's kind of the whole point of like evm projects and and risk zero targeting risk five um so this can very quickly lead to a very developer friendly tool chain where you don't have to like write these compilers down to the assembly from scratch okay um also often the zkvm approaches generate like a universal circuit we're kind of the program that you know the verifier wants approver to run is part of the input to the Circuit so you don't have to like run the front end which can

be really expensive actually in general uh every time you change the program that you care about the witness checking program and also these circuits have a ton of structure um and so uh they're what I call uniform circuits just it's doing the same thing over and over again and so snarks that leverage that uniform structure uh can be much faster for circuits of a given size than snarks that don't leverage that structure okay um uniformity is kind of already taken when it comes to circuits as far as the meaning so uh this is a very closely related meaning though yeah it's a I mean a uniform circuit is one where like if I tell you like the label of a gate uh and you can very quickly determine like what

other Gates it's connected to or whatever right and uh intuitively you can do that for circuits with some kind of repeated structure you know at least uh there's a description of for any uniform circuit in that sense there's certainly a description that's much smaller than writing down an explicit you know table of here's every gate in the circuit here's what um other Gates it's connected to um so I'm using it really to mean there's kind of a hand wavy version of that where the circuit's doing the same thing over and over again so if I tell you yeah yeah this your uniformity I mean here implies the uniformity you mean this is sort of like a strong uniform yeah this is a very exactly it's a very strong version of uniform okay

um yeah so what what are the downsides so I'd say what one is um if you like insist that your circuit um you know actually kind of run a VM for a bunch of steps um the circuit might be much bigger so even though it's all structured it's much bigger and maybe like a faster snark you know the snark is is sort of faster for a given circuit size because the circuit's uniform but the circuit's so much bigger and uh potentially you still come out behind or head it's hard to tell um and I'd say this this compilation procedure from high level computer programs down to the assembly is like some kind of bug or attack Vector it's like a surface there any bugs in that compiler you know you're the prover is going to prove it correctly evaluated circuit that's not doing what the

verifier thinks it's doing um yeah uh so yeah but just to highlight this first point um okay here is a computer program for naive matrix multiplication looks like some of the indices got messed up um by PowerPoint but um and and sort of matrix multiplication is is uh it basically is a circuit right it's like a straight line computer program like you know you know in advance uh how many iterations of every for Loop there's going to be and then it only does additional multiplication operations um so you can just like directly turn it into a circuit right if you insisted on going through a zkvn the circuit would sort of have to be prepared at every step of the CPU to execute any of the

Primitive instructions so it's going to have to include Logic for all the Primitive instructions um here you know you sort of know in advance at each step exactly what the instruction will be there's only two primitive instructions and so forth so I think you know with the zkvm approach you'll just never get a circuit that looks like this okay so you know it's just trade-offs all along I just wanted to have that discussion so you know I sort of um uh yeah I think jolt is like a powerful demonstration of the utility of avalik lasso uh but I think lasso will be useful like outside of zkbms as well so I wanted to maybe highlight that all right so how does Lassa work oh question yeah um so why wouldn't so why would why would this be a lot

more complicated if it is uh if it is trying to be implemented in a ZK VM is it because like I will implements special instructions that would in turn emulate a matrix multiplication yeah yeah so I mean you know you can naturally design a VM that has addition multiplication as primitive operations in fact most of them do um but if you sort of um take you know like a computer program um say written in assembly like if you just wrote this in the assembly for a virtual machine with like a hundred different primitive instructions and fed it through any like ZK VMS front end any like the existing projects this this is

not the circuit that will come out uh maybe you could redesign the these front ends to like uh for the developer to somehow give it hints or for it to automatically sort of figure out that look only additions and multiplications are getting done and all of the Loops have predetermined bounds and so I don't actually need to like produce a circuit that but these these projects um a lot of them generate Universal circuits right they literally like the computer program is part of the input to the circuit and so there's no way to stop the circuit from like doing all this extra work basically not leveraging this all this extra information we have about this computer program where it only does multiplications and additions and then Loops um have sort of predetermined bounds and things does that make sense

I mean basically the best case in the worst case are going to be the same at that point right okay exceptions what you're talking about where it kind of like has this special logic in it where it it can optimize the universal circuit that comes out based on like some knowledge of the program um so I'm actually not sure whether there are zkvm projects that don't produce a universal circuit but there are um you know projects that that won't that just don't use uh don't Implement a virtual machine abstraction at all so like some of these lower level dsls um I mentioned like I think uh uh you know like uh okay like Halo 2 uh

kind of the the developer directly writes like constraints some kind of constraints right so there's just no virtual machine to be found right because to me like it kind of is it fair to like think of it analogously to like producing Universal circuits because like I mean I'll just say that zkbms and Universal circuits are like one in the same um maybe I mean I think there's PR there you know one can probably come up with universal circuits that I mean if it's if it's one circuit that works for all you do need a way to describe the computation you want the circuit to do then so uh how would you do that if if you don't just have like a yeah um maybe

this is kind of like a film yeah it might be more philosophical uh I don't I know that's like I have a great answer like certainly with existing approaches they they feel like the same um maybe there's some way to separate them a little bit is there any work that you know that combines both the approaches of like universal circuit and also have the developer give constraints so you could be like okay this part generated universal circuit but like this part I know how to optimize yeah and like just slot it in so I think you you see something very close to this with the zkvm projects that have built-ins which are just like hand optimized circuits for specific gadgets and that you know those are basically saying look if I actually just wrote uh like assembly code

um you know in for the VM to compute this particular thing whether it's like a digital signature or a hash function that you know gets applied all the time um the resulting snark or the resulting circuit would be like bigger than it needs to be so I'm going to hand code a specific one um whether they their project doing more complicated things than that than just like sort of building in some gadgets for certain important things um I don't know uh off the top of my head I don't have examples but it's not hard to imagine that you can do something like that so maybe someone is you know yeah I guess I have a similar question I was gonna say like I know like in machine learning like compilers they like take a bunch of kill you like figure out the language like collapse

the matrices down to be more efficient um or the Matrix operations would be more efficient as kids if there's like a technical reason you can do something like that yeah so there's a there's a space called zkml now which is like basically just applying snarks to ml workloads and you just cannot afford the overheads of of the the VM abstraction and so none of them are going through those I guess I meant like could is there a reason you can't like have better front ends that like could create like a like look at this code to like create the efficient so it could yeah um no there's no reason for that other than you're gonna have to run the front end every time you change your computer program and a lot of these front ends are like very expensive to run okay but

other than that yeah you totally can and probably should do that we should have more front ends that do things like that actually more questions okay so this was kind of all the high level uh discussion um so now we're gonna dive into the technical details um so let me just remind you the definition of a lookup argument so um yeah the prover uh did not think this was okay let's focus on index lookup arguments so the approver commits to a bunch of index value pairs um and and proves that for each pair you know AI comma bi the value AI resides in the bi entry of the table and then needs to approve that

okay um now uh everything all the snarks I want to tell you about today you know the basic lasso and lasso snarks they're they build almost called interactive proofs so let me just briefly introduce that model um I think it makes sense to describe the model in the context of an application just kind of makes things easier to think about so imagine um somebody uh just like a week you know they have a laptop someone has a laptop and they want to do some heavy duty computation so they hire cloud computing service to do the computation for them so they ship a bunch of data off to the cloud cloud stores the data most interactive proofs the user only has to keep around a very short summary of the data as we'll see typically the summary is actually you interpret the data as a multi-linear polynomial and evaluate

that polynomial at a random point but don't worry about that yet um then the the user asked the cloud a question about the data Maybe in the form of a computer program wants the cloud to run on the data the cloud comes back and says I ran your computer program on your data and here was the output right but the user doesn't trust the cloud for whatever reason maybe there's a reason the cloud wants to trick it maybe the Cloud's just lazy and doesn't actually want to spend the electricity or use the resources to run the program properly so the user starts interrogating the cloud sending a sequence of challenges and getting a sequence of responses then eventually either accepts the answer as valid or rejects it as invalid okay so it's sort of the same thing as a snark except there's no witness only known to the

prover here there's just some some data that the user itself saw okay and there's interaction but in all the interactive proofs we're going to use today they're public coin uh what that means actually is important what is important is that means you can use some cryptography very lightweight cryptography called the fiatrimir transformation to make it non-interactive all right so um I sort of explained at a high level like how snarks were designed yesterday but I want to sort of re-explain that now specifically using interactive proofs instead of yesterday I referred to what are called polynomial iops so forget about polynomial iops for now

okay so the trivial proof in a snark the proof is claiming to know some witness W satisfying some property you know that some witness checking procedure would have accepted um the trivial proof is always the prover sends the witness to W who directly checks the witness for validity on a slightly less trivial proof system would be the prover still sends the witness to W but if checking that W is correct uh is expensive you can use an interactive proof to force the prover to do that hard work of uh running the checking procedure on W okay so you can you know if the checking procedure is hard enough you can get a work saving uh snark this way but it still won't be succinct because the proof isn't any shorter like the proof

is still sending the witness to the verifier okay so what you'll do in snarks derive from interactive proofs uh basically is the approver will cryptographically commit to the witness using a polynomial commitment scheme um and so you know that commitment is just like one hash value or one group element um and it will later reveal just enough information about the committed witness to let the interactive proof verifier sort of do the checks it needs to do okay and in all the interactive proofs um I guess that matter what that check will be is just like evaluate a certain polynomial uh that captures w at a random point okay all right so let me give a brief history

of snark design and uh sort of uh convey the perspective I'm hoping to um convince you of through this talk so uh historically interactive proofs were designed kind of first and then people looked at a variant called multi-prover interactive proofs and that led to something called probabilistically checkable proofs and then finally people built snarks from pcps now these were all Theory works in the mid interactive proofs were introduced in 85 and let's say the first snarks were given simply by Killian and Macaulay in the sometime in the early 90s I forget the exact year okay uh now it took a very long time to get you know anything resembling

practical snarks quick question sorry I certainly agree with the characterization all that was theoretical I still feel like between the pcps and the Snorks at least from my perspective there was a shift in perspective for the first time right I kind of feel like the first three of those at least certainly the first killer applications were all in kind of you know structural complexity Theory right that sort of is for lower bounds if you want to call it that way whereas snarks the minds even though those first constructions are so theoretical it's like look at this cool thing you can do in principle right is that would you say that's accurate or I think that is I think that is accurate I think one of the early PCP Works um there's a there's a quote from it actually and it was maybe like the last

PCP work um you know uh before snarks that really had this perspective maybe so I don't I don't know if it was the first but I think it might have been to last um talks about like uh uh you know monitoring a herd of super computers which is exactly like basically foreshadowing This Cloud computer scenario I mentioned before the cloud is like the super computer and the monitor is just a laptop or something um and so and then you're you're totally right I think with uh with uh with snarks even though they were you know uh they weren't practical um these early Works uh did have in mind um you know the prover knows some witness and is going to prove it knows

the witness um whereas uh the your the IPS and mips and um some of the PCP work uh was thinking about like totally intractable problems uh like peace based complete problems or even next complete problems um so there was really no thought of like actually running the prover in the real world because you can't even like solve the problem in the real world um so it is a a unique yeah change in perspective now that I think about it I mean you had like BLS in the early testing right kind of as a PCP precursor or something and that had a more positive framing actually I think yeah so I should I should track down the very first paper that seems to have had the

positive framing um and then the the framing in the PCP literature was kind of abandoned when everybody was using them for hardness approximation and then they cared about pcps for just like completely different reasons yeah and you know but fast forward to 2008 and like we still did not have practical snarks from any of these I guess um so that then there was work sort of introducing linear pcps and uh giving um what quickly led to practical snarks from them um and then only later did we get practical snarks from the precursors um and yeah actually you see a lot of the PCP papers

um will like in the introduction or something talk about um like a very simple uh kind of PCP that they're not happy with so then there's like 100 pages to like you know make them happy with it um and what it turns out is it's this sort of funny thing like those those simpler pcps from the introductions are kind of uh what some of the most practical snarks are based on um so like Killian Macaulay uh because they only use like Merkel hashing and Fiat Shamir as the cryptography to get a snark really needed like a short PCP so they they really kind of needed the other 100 Pages sort of these are these are the upper right earliest snark papers yeah so like Killian McCauley uh

say take a PCP um you know the have the proof of Merkel hash and send that to the verifier and then the verifier kind of acts like the PCP verifier um and you know the authentication paths are are what insure is that the prover actually answers consistent with the committed PCP string and doesn't like change the string based on what question what what queries the verifier makes um and if you go that route like you really do need uh so I mean the modern analog is iops right we still don't have practical pcps but the higher level Point here I guess is like we do have cryptography that's not just Merkel hashing and fiatrimir and if you use that heavier cryptography you can sort of have a start with something simpler than a PCP or at least something that

came in the introduction of the 100 page PCP paper and skip the last 95 Pages or something um yeah if that makes sense okay um now there's uh something really interesting about snarks from interactive proof so like the thing that came very first um and yeah this is sort of a personal opinion but you know I'm tried I do my very best to you know convince you to have the same same view by the end of today uh which is they they minimize commitment costs for the prover okay and the key technical tool here is something called the some check protocol which I I won't mention uh really again till the very end of the talk and even then I'll just kind of tell you what problem it solves but there are a lot of um you know tutorials I've given like online

their videos and stuff I think it's a it's a really beautiful protocol very simple and it's based on multivariate polynomials okay these multivariate polynomials were kind of abandoned uh in in later work like especially the PCP literature because they don't lead to Short pcps okay but for Snorks we don't necessarily need pcps right this is which is the point I just made um and so the subject protocol forces the prover to uh conceptually kind of materialize intermediate values uh in a computation without sending them to the verifier and without even cryptographically committing to those values and it's sort of unique in that way and this is very hard to describe like why and how and I'll try to give a sense of this throughout the rest of today's talk

um but uh essentially like all of the other techniques um just have the you know snarks derived from multi-proven Rock proofs and from you know pcps and iops and linear pcps they all have the proverb just commit to more values and that's the bottleneck for the approver those commitments okay um so even Snorks that use the subject protocol uh some of them do have the prover commit to some intermediate values in the computation example of this is Spartan and it's really based on a multi-prover interactive proof not a single-prover one and that's kind of where the second prover sort of from the right perspective is where the extra commitments are coming from um but even even Spartan has the privile commit to fewer intermediate values than

than snarks based on univari polynomials okay and I think you know like the comparison of like the number of commitments in Spartan to um snarks derived from univari polynomials it's like not so night and day that people necessarily you know like see it will they might you know people might not even agree with the statement I'm making but you know I firmly believe it's true um so I've been trying to come up with sort of Starker uh differences you know where the um uh the sun check protocol is really saving uh you know like a huge amount of commitment costs um but in general you know when Snorks from the subject protocol there's none of these quotient polynomials that all of the universe uh polynomial base narcs

have the prover wind up committing to and there are certain ways sometimes to avoid committing the quotient polynomials with certain polynomial commitment schemes but even then you still have the proof of committing to something called composition polynomials and all of the univari techniques always have the prover do ffts which the sun check based snarks don't require okay so I'm gonna try to just convey um throughout this talk uh you know the how the Sun check protocol minimizes these costs for the approver it's one way to think of this that the sort of non-sumpcheck ones a kind of more proactively checking every single step so that you catch it as soon as there's a deviation whereas some check you just check at the end right you just

sort of let it play out or um so I think uh for the most extreme uh versions of of some check with you know minimal commitments it's exactly like that so um what everything other than so what what the mips and the you know PCP snip so everything other than just IPS do the very first thing the prover does is commit to every value of every gate in the circuit okay whereas um if you want to go through like a circuit abstraction the interactive proof for that is the gqi protocol that goes layer by layer through the circuit um and there if there's any commitments at all it's only to the input to the circuit and so it's exactly like that where you're sort of deferring you know catching the prover in a lie until the very end and only then do you maybe have

the cryptography depending on context um um is it is it a correct statement to say that the lookup argument is a snark from IP because in IP you mentioned like we don't care about the Proverbs complexity so we don't in a lookup argument because we assume the table is somehow computer and it's committed um no so we I mean we do I mean the way interactive proofs were originally defined you know uh people just thought about polynomial time verifiers and didn't care about the proof of complexity but in practice we absolutely do care about the improve of complexity um I'd say uh we're gonna see that uh lasso is derived from interactive proofs like very

heavily and like not only does it use the subject protocol that doesn't use it in the spartan-like way where the approver commits to a whole bunch of things all at once it sort of it really uses what I this gkr protocol um to really really minimize the prover cost so I don't think the lookup argument is IP based just because it's like a lookup argument or something it's IP based because under the hood it's literally using an interactive proof combined with like as few commitments as possible all right I do want to briefly discuss like the downsides of some check based snarks relative to other techniques I you know it's in quotes because I don't think there are major downsides people are certainly welcome to disagree with me so the main downside is really just larger verifier costs

um however uh so in something like Spartan the proof size is still just logarithmically many field elements and something like the gkr protocol it's something like log squared we'll see why shortly log squared actually can be pretty big um the other uh but I have caveats to that in a second but the the other downside is you really you know you need the prover to commit to multivariate polynomials if it is committing to anything it's committing the multivariate ones and again we don't have you know like kzg like uh evaluation proofs for multi-variate polynomials um okay we have like log size proofs instead of constant size uh but many projects today are using a polynomial commitment scheme uh where the proof size is actually not just log squared I'd call it more than log Cube

technically because this is a security parameter and that needs to be super logarithmic to have security against super polynomial time adversaries so we're already using snarks today with with big proofs so uh you know from my perspective a lot of people are not you know going to disagree with this uh maybe by you know this work might help convey it but um one of the reasons to use these you know this big proof commitment scheme uh is to try to get a fast approver I mean that's the only reason to do it because it has worse verification costs that and if you care about post Quantum security uh since it avoids elliptic curves um I you know personally I think the kind of the right way and there's no one right way to do anything but like so let

me just say a very powerful way to get fast approver okay is um to just minimize the number and size of the field elements committed rather than committing to a lot of them and trying to work over a smaller field if that makes sense okay so hopefully this perspective just continues to slowly come across today um there are a couple of extreme examples of the subject protocol minimizing commitment costs so one is a matrix multiplication protocol that I described back in 2013 where the prover really just computes the product matrices anyway at once and uh does a completely low order amount of extra work to prove that it's correct so if you have n by n matrices like the amount of extra work to prove

that the product Matrix is correct is is linear in the in the size of the Matrix N squared um so this is like vastly faster than the fastest known algorithms to just compute that product Matrix right so you see like you know like uh the approver overhead is like under a percent even for various small matrices you just can't achieve this with other techniques so um you know with uh any other techniques the approver at a minimum is going to have to cryptographically commit to the product Matrix or send the product Matrix to the verifier which would destroys the sickness right so this is like a really extreme example and some of like the zkml projects are trying to use this because ml does a lot of images multiplications and you just can't tolerate like overhead that's bigger

than this in some of those applications um and then the other uh extreme example is this gkr protocol I mentioned okay so this is an interactive crew for circuit evaluation meaning the verifier knows the inputs of the circuit it also gives a snark for circuit satisfiability um as long as the prover sort of commits to the input to the circuit and just the input not all the other gate values in the circuit so here's here's the picture so um if you if you have a circuit that sort of there's like a public part of the input X which is like known to uh the verifier as well as the prover and then there might be a witness W that only the prover knows

okay so uh if the prover is claiming to know a w that causes the circuit to spit out some output y um you can use the gkr protocol okay and the only information that the gkr verifier needs to know about the input to the circuit is to evaluate these polynomials I keep mentioning but haven't told you what they are yet uh the multi-linear extensions of X and W uh at a single random point okay so to get a snark for circuit staff from the G care protocol the proverb would just commit to the multimeter extension of w and then when the verifier needs to know W twiddle at R some random point R the Montana the polynomial commitment will just make the prover give give it that

value so the verifier can evaluate X tilde itself right right and it's known the verifier can do that in time linear in in x x tilde and and today X is going to be the lookup table might have size 228 but if it does the verifier is still going to be able to evaluate X twiddle really quickly because we're going to be dealing with tables that structured means they have that property where is the subject coming in in this yeah so the gkr protocol uh under the hood uh is applying the Centric protocol once per layer of the circuit so the verifier costs are the depth of the circuit Times log of this can actually

be like the width of the circuit but I just wrote the size of the circuit uh for Simplicity what's happening is for each each layer of gates in the circuit uh you're running the subject protocol once so uh that's log log cost for the you know for the verifier per invocation to some check but then you apply it once per layer each invocation computes what so what's the computation you do each layer uh basically like correctly evaluate uh every gate at that layer so the gki protocol is forcing the prover to evaluate the circuit gate by gate but without using any cryptography other than if the proof are committed to a witness so it kind of like succinctly

re-evaluates the circuit on the commitment yeah though the only thing I mean just think of like um on the commitment uh the the prover you know commits to W twiddle at the start this Montana extension polynomial from W the verifier through the whole protocol doesn't need to know anything about W until the very end right when you know W twiddle of R right so um yeah the proverb is just proving like it went gate by gate through the circuit and evaluated you know if the multiplication gate said hey compute the product of these two other dates that it did that that's it so uh yeah I mean and the approver can

be implemented in in order circuit size many field operations um so this was shown via a long line of Works uh today we're only going to apply the GTR protocol to actually one very specific circuit where we already knew this back in 2013 how to do this uh it's all field work right um the only cryptographic work is involved with this uh witness commitment whereas all other snarks uh would you know the very first thing The Proven would do is commit to a value for every single gate in the circuit rather than just to this this witness at the top so these successive implications of some like is there some consistency requirement like like not only did you evaluate these correctly but you evaluated these correctly given

what you implicitly said the previous layers values were or something like this yeah that's basically how it works so you sort of apply some check like to the applicator of the circuit right and like uh at the you know at the very end of that application of some check the verifier has to evaluate some polynomial derived from the gates that fed into the output uh but it can't do that on its own so it sort of checked everything up to checking the gates that fed into the output so then it just does the same thing again so it's kind of reducing the prover's claims uh from something about the output to you know something about the gates getting into the output something about the gates feeding into them and one layer at a time and So eventually it was forced to make a claim about the inputs to the Circuit W's

already been committed at the start the verifier Knows X and so it can basically check that final claim on its own it's getting you know the what it needs to know about W from the cryptography okay um now okay so I mentioned this so so you know people normally think of X as like really small it's like one hash output the proof is claim you know like a premature that hash output these lookup arguments X is going to be the whole lookup table and that lookup table went a size 2 to 128. but all the verifying needs to know about X is one evaluation of the modulator extension and for all the lookup tables arising in jolt even if their side shoots under 28 that's that's really quick um okay so I think these gkara based snarks um you know they haven't seen deployments and I think the general

reason is that general purpose front ends especially those supporting a virtual machine abstraction use a ton of what's called this untrusted advice that I mentioned yesterday um and so that winds up in this in this W uh that I showed feeding into the circuit so the prover does have to cryptographically commit to all that advice um and so you don't really get a huge amount of speed up for the prover because that's W is actually like a constant factor of the whole circuit uh moreover the circuit model is very restrictive low depth arithmetic circuits kind of a double whammy like people don't want to deal with these circuits and you're not getting that big a speed up for the approver even for a given circuit size um so my view is lasso and jolt are trying to make these

um two extreme examples um very general right so the uh the gkr protocol applied to circuits with like tiny Witnesses very no advice inputs very few advice inputs is like spectacularly fast for the prover but in general we need circuits that have big advice inputs so it's not helpful in general um so lasso does use the gcara protocol but applied only to a very very specific circuit uh it just computes uh what's called a grand product so the input is like you know some large number of field elements and field elements and we want to multiply them all together these Grand products arise all over the place they arise in all lookup arguments they arise in you know snarks for circuit set as well um all like deploy Grand products

um they will have the prover commit to like partial products which are basically intermediate values in a circuit Computing the grand product with the gki protocol you'd cut out those extra commitments okay in fact in the 2013 paper I gave a very uh optimized version of the gkara protocol exactly for this I didn't know it'd be useful for snarks at the time but this is kind of the core of of many snarks now the proof size there is log squared which is uh not is bigger than I would like although it's still smaller than like Lambda Times log squared which is what a lot of people are using today uh there's a way to reduce it um down to basically log and if the

prover does commit to some extra stuff but it's like it's lower amount of extra stuff so concretely say um you can get this proof size with the prover committing to I don't know like n over 64 field elements so you know like just two percent extra if you already paid for commitment to size n or something I'm sorry this extra stuff and that corresponds to like the untrusted advice you were talking about or that's just uh sort of that arises from what uh it arises from the following so um the circuit uh that computes the grand product for us is just the binary tree multiplication Gates uh now most of the gates of that circuit are near the inputs right

um but most of the layers of the circuit are near their output so most of the layers are tiny uh but most of the uh rounds in the GTR protocol are coming from the many tiny layers so you kind of have to prove or commit to the values of those a hand you know just those tiny layers and it's not many values so you sort of you run like the 2013 protocol for just like the first five layers of the circuit uh and then uh you'll run something like more like Spartan where uh for everything else uh but you're only applying Spartan with its you know higher commitment costs to you know one over two to the fifth fraction of the circuit when you say first five layers you mean closest to the output to the input the big layer so you you avoid the applying the

cryptography to the big layers you do apply it to the small layers uh you see something analogous now in recursive snarks sometimes um you know Stark where like they'll they'll use like a slow but snork friendly hash function exactly in the Merkle trees at the small many small layers it'll be snark friendly uh but they'll use something fast uh but not snark friendly for the few big layers um and that way each authentication path is mostly snark friendly uh but Computing the Merkle tree is fast it's the same same idea okay so uh with all of that out of the way I can give you the details and really now now there aren't all that many details um to cover in the end

uh okay so uh I do have to change perspective a bit I guess so we're going to think of a lookup table now as a computer memory now it's like some fix you know it's fixed uh but it's not going to actually matter that it's fixed uh everything I'm going to tell you about actually would work in some kind of dynamic setting uh but I won't get into the details of that um and so yeah index lookups are just memory they're just reads into memory right does that make sense um now uh what we need so what we need to do is something called memory checking and there's a very old literature on this and so all the techniques I'm going to describe to you other than um the sun check protocol and the gqr protocol are from this very old literature of course the subject

protocol itself is also very old but uh from 1990 or something um so we need like an algorithm that can check that all the reads are correct okay but snarks are only good at making sure the prover ran uh algorithms that basically are you know easy to represent in a circuit so you know with stomach very limited exceptions like matrix multiplication like we always go through a circuit okay so generally speaking we want the algorithm that's going to do the memory checking to kind of only do addition multiplication operations and moreover since I ultimately want to use the gkr protocol to really really minimize commitment costs we're going to want the circuit to be low depth ideally that's like a parallel algorithm that's only doing addition and multiplications

all right um so here are the key techniques it's really just something called fingerprinting and I need two variants of fingerprints checking algorithm yes uh but I'm going to think of it as memory checking so and I'll explain in more detail what that means shortly but right now um we're going to I uh yeah just view the fingerprinting as just like some more background before I return to details of memory checking right just like you just think of an algorithmic problem or give it an array I'm getting the little AIS and little bis yeah to give me a very simple algorithm yes verifying that that's exactly yeah great okay um okay so two variants so let's start with what I call the equality checking

variant okay so think Allison bod of two vectors of length n they want to know are they the same vector if they don't use any Randomness it's known like out you know the best you can do is basically Alice sensor hold Vector to Bob and he compares the entry by entry okay um so is it possible for Alice to send less data than that to Bob it's known how to achieve this with a randomized procedure um so the way that works is Alice interprets her vectors uh her Vector as a degree n polynomial let's say as the coefficients of a degree on polynomial um and same with Bob okay and they just um Alice Picks a random input to the polynomial from the whole field evaluates her polynomial at that point

sends the random point and the evaluation to Bob who Compares it to his polynomial evaluate at the same point that's it so just two field elements R and P of R getting sent about okay so I call P of R the read Solomon fingerprint of Alice's Vector at r it's actually just a random entry of like the read Solomon encoding of of her Vector if you know what read Solomon codes are if you don't doesn't matter um and yeah the the key claim is that uh you know if the vectors are equal then they will always their fingerprints will always match and if the vectors are not the same then with high probability their fingerprints will not match and so they'll output not equal um so f is zero one and this is the familiar like random inner products kind

of thing yes but you um uh for random in a product you're really uh interpreting A and B as as a linear function like an N very linear function um and uh I want to work over a Big Field um and and interpret them as univari polynomials okay other questions um okay so the first claim that if uh two vectors are equal their fingerprints match is just because you wind up evaluating the same polynomial at the same point so of course it spits out the same thing um now the second claim um if Alice and

Bob have different vectors um what this boils down to is you wind up evaluating two different polynomials at a randomly chosen point and there's this basic property of polynomials if they if they both have degree at most n and they're not the same polynomial they can agree on most endpoints so the probability they happen to pick one of those n agreement points is that most n over the size of the field so you work over you know and think of any as I don't know two to the 30 and the field size on two to the 256 and this is like astronomically small like you'll never get basically a collision of the fingerprints for different vectors great um okay so the other variant we need is called permutation checking um and this dates back to a work of

Lipton in 89 and then was used for memory checking by an old paper of a Blum and others Auburn Blum and others from 94 or earlier um so here the goal is just to determine not whether they're A and B are the same Vector but whether they're permutations of each other whether they're like reorderings of each other so like these two things are permutations of each other it's just the same field elements reordered but if I change like one of the entries of a to something else it would not be permutations um so now we do the same thing okay except now we're interpreting the uh we're turning a into a polynomial not by interpreting it as the coefficients but as the roots and then the same thing works out so you

you know Alice Picks a random R and evaluates her polynomial at R and sends R in that evaluation to Bob who Compares it to his and again the point is if um if a and b are permutations of each other you know two polynomials with the same roots are the same polynomial you know it doesn't multiplication commutes um and if they're not permutations they're different polynomials they both have degree n and minus one so you evaluate them at a random point they almost certainly disagree at that point questions so I call this permutation invariant fingerprinting all right so now let me summarize this little paper of Blum and others um so yeah the remember we're thinking

of lookups in index lookups into a lookup table t as reads into memory and we want like you know some algorithm that will check that all the reads were have to correct value returned but this algorithm should only do like additions and multiplications over find it field now you saw these fingerprinting techniques only do additions and multiplications over find it Fields so you see where this is going okay so we're going to change our perspective a little bit so if I'm going to adopt a perspective from the memory checking literature we're going to think of these reads to you know in lookup arguments you know you think you know all the reads the memory cells being read and the values returned by the reads they're all committed like all at once instead we're going to think of

like a weak verifier doing the read sequentially so you know it keeps it at each step it determines hey I want to read this cell okay uh and the prover is going to come back and say the value currently stored in that cell is blah um and what uh this early work was interested in was the space complexity of the verifiers they were thinking oh this verifier has very little space so it's going to use an untrusted prover that has a lot of space to maintain the memory but it doesn't trust the prover okay we don't care about the space complexity of our verifier our verifier is really like an arithmetic circuit in the end but we do care that you know the verifier uh the circuit only does addition multiplication operations over some finite field turns out the same solution that kept

the verifier space low also turns into like a good good circuit um so uh yeah this this old work just has the verifier uh compute a couple Fingerprints of certain values that it observes over the course of the you know prover sending it you know claims outputs of the read operations and it can maintain these fingerprints incrementally right so um every time the prover comes back and says here's the result of your latest read request the verifier just like does one or two multiplications to update one of its fingerprints and moves on to the next one so that's it's both small space but I don't really care about that I care that it's just additions and multiplications and only like one or two per read okay so to make the reads like more easily checkable

um the blood metal paper they sort of they modify the reading procedure so they wind up kind of uh storing more stuff in the memory so like more stuff gets read with each so I'll explain what that means so uh with each memory cell each index of the lookup table um they're going to keep a counter and if the approver is honest this counter is just going to track how many times the cell has been read at any given point in the procedure okay now every time a read operation occurs you know the verifier says I want to read you know the value currently stored in cell bi and the prover comes back it's going to return you know both the value of claims resides there and the count okay so what we're going to sort of

augment the algorithm the verifier is going to do a follow every read with the right it's just going to write back to the seller just read the value of the proverb just said was stored there which might be a lie and if it is a lie it's sort of you know overwriting the value with what the prover said was there instead of what what's actually there and the the verifier itself is going to increment the count by one so if the prover's honest like you know you're not actually changing the values stored in any cell ever because the verifier just writing back the value that was already there uh and and the counter just gets incremented by one and every every read to that cell so the the counter really is just counting how many times the cell's been accessed okay and then the final modification is

once all the reads are done the verifier makes one final Passover memory reading uh the values and counts uh in memory at the very end and I guess uh yeah okay I think my later slides sort of forgot that there's a value here but it doesn't uh yeah the protocols are obviously work I just might be missing that little detail okay uh somehow my uh definition of these vectors R and W got cut so I'm going to verbally tell you what r w are fortunately they're pretty simple okay so R is called like the read set and W is called the right set so R is um the list of tuples uh they're each a three tuples so it's it's memory cell

value and count associated with every read operation that the prover returns okay W is the same thing but associated with every right operation okay crucially also in W is like the initialization rights which are sort of only implicit so that is for every uh memory cell there are you know capital N of them if this is a lookup table there's uh you know uh you know so for I equals one to n there's I comma uh T of I so the value stored at the I memory cell comma zero because to indicate no reads have been done yet that's R and W and sort of that initialization aspect of w is ultimately what's going to kind

of force the prover to always return the value that's actually you know was initially written um that you know that should reside in that in each memory cell okay so the uh the theorem the key theorem is that R and W are permutations of each other if and only if like the prover is honest throughout this whole protocol specifically for the algorithm you just showed us and I can sketch the proof um so it's a it's going to be hand wavy but this is really how the proof can go okay so after initialization there are like n-tuples in W but none in R right because we've sort of initialized memory with run right per memory cell but haven't done any reads yet

right so you think of how w r like evolve over time you know after initialization you've done end rights to memory to initialize the memory no read yet now each read adds another Tuple to R right because R is like the set of tuples like return by the approver on the read operations um but you know each read is immediately followed by a right which adds another Tuple to w so now if the proverb is honest like every Tuple added to R like matches the last right to that cell because if the prover is honest like every time a read operation is done it returns like the value and count that were last written to that cell

okay uh but then that read is immediately you know followed by a right that adds something new to w right and then finally like the you know the final Passover memory is supposed to like match everything uh that remains unmatched and W kind of match every final right with the read um so that's sort of what happens if the prover's honest and that's why R and W proves honest will be permutations of each other because every read is every read like matches a write that already occurred okay but if the prover ever returns an incorrect value count pair uh immediately there's uh that means there's a there's a tuple in the read set that's like the first time it does it there's there's now a tuple in the read set that's not in the right set

um and there are still and you know at all times until the final pass there are n tuples in the right set that are not in the read set which means that like the symmetric difference of them grew in size okay and basically you can never recover from this okay so um every read operation until the final pass uh like is immediately followed by our right operation so like the best case scenario is the symmetric difference like neither grows nor shrinks and then at the very end the final Passover memory you know there's only n read operations that can only reduce the symmetric Difference by n so if it was n plus one at any point it's never going back below one anyway and here I'm you know uh these are like up the permutation you know that I'm

bringing these are sets instead of vectors I guess here um when I say symmetric difference um oh there's my definition of uh well is it yeah that was my definition it says recap that was yeah okay well we've recapped the definition now great um okay so um now the question is how do we check that R and W are permutations of each other right because we've said that's equivalent to uh the memory checking goal which was making sure that all read operations return the correct value right and so what we do is yeah so so you know each entry of R and W is a triple like you know it stores a cell a

value that the claim was in the cell and a count that the proven claim was also stored in that cell um I don't like having vectors or triples so what we're good the verifier is just going to read Solomon fingerprint each triple to reduce the triple down to one field element okay um and we've explained you know that you know uh with overwhelming probability there'll be like no collisions so you won't have two different triples that fingerprinted the same thing okay which means that as long as there are no collisions um then uh you know these sort of uh fingerprinted vectors which I'm calling R Prime and W Prime which each just store you know field elements rather than triples they are permutations of each other if and only if the original thing of

triples were permutations of each other now we for each triple like we care about the order right we you know BAC is not the same as ABC or something right values are not the same as you know cell identifiers not the same as counts that's why we read Solomon fingerprinting here okay but then to check we want to check that R Prime and W Prime um are permutations of each other um so their the definition of permutations we don't care about ordering so there we do permutation and varying fingerprinting so that's this is uh this is the final check so so the capital N plus M's the capital N is that uh

uh that was what table size memory size right but as far as the so it's capital W and that's the initialization stuff that shows up in it shows up in the initialization and in the final Passover memory those are the two places then shows up okay M corresponds to the reads which are part of the actual initial thing and then the M writes that are your kind of copies here's what goes okay can that can we just review like why you did this in the sense of like what was what were the target properties because you think this problem that like is Trivial unless you know you want to solve it in a way that has certain like very lightweight computational properties right so what were you at so what what I care about uh is different

than what the old blumento paper care about what I care about is I have an algorithm that takes as input uh these triples um in R and W and just through additions and multiplications figures out um our are all the triples like honestly computed and so like depth of the computation or something you don't care about well I actually do because I want to use gkr okay um so the bulk of the computation is just these big products and so we're going to have a binary tree multiplication dates logarithmic depth questions okay great so finally I can tell you how lasso works hooray basic class so okay

so uh full details so just a reminder so T is the lookup table of length capital N B is uh you know committed Vector of table indices and a is a committed Vector of you know values that are supposed to reside in those indices and the verifier is just going to get a commitment to this multi-linear extension of a and this module inter extension would be and still haven't told you what those are uh continue to not worry about it you can commit to them with the polynomial communion scheme yeah so the you're going to think about applying the GTR protocol to a circuit whose inputs are basically the lookup table A and B which are you know a is like uh committed values B is committed indices and then this extra Vector C which is

um just these counts remember yesterday I said the prover uh in basically also commits to M plus n multiplicities and that's exactly what this Vector C is okay there's also some other stuff which doesn't you know these are the initial counts are all zero so there's n zeros um and you know the initial indices for the initialization step is just the number zero up to n minus one say it really doesn't matter you can also make it all zeros it really doesn't matter uh wait no indices can't be zeros yeah sorry they should be the number zero up to n minus one saying these are the N cells each getting initialized so that that c those are the same as the CIS that counts in your algorithm that you just showed us yes exactly okay yeah and there's also these Gammas and R's used in the fingerprinting so what's crucial

is um that and I mean it's totally standard uh the proverb will have already you know T is fixed in advance let's say proof has already committed to a and b then the verifier picks gamma r at random and ultimately Fiat Shamir will pick them and that ensure you know if the prover knew what gamma R would be one is choosing like a A and B and C actually should commit to C before Gammon R pick two if it could choose a b and c to depend on gamma R uh it could easily pass the randomized check it's like we want the circuit to run a randomized algorithm uh it's important that the random issues by the randomized algorithm not be known by the prover uh when it commits to things and then the circuit just computes these fingerprints that I mentioned um

and so I kind of like wrote what these vectors R Prime and W Prime are um is just the read Solomon Fingerprints of the of the tuples you know a b and c here again the details aren't actually that important um you know here I've replaced uh you know the for the rights like the the counts associated with a given right is is the count associated with the same read but plus one right and that's that's capturing that in the old memory checking algorithm from 1994 the verifier just every time a read returns a given count it just writes back with the count incremented by one okay so uh the right counts are just the recounts incremented by one

okay so you know what this uh we're really just multiplying you know Computing uh this Grand what these are called the Grand products uh just not directly the inputs to the Grand product are not like this Vector I wrote up here exactly you know they're sort of uh derived from it um and so this kind of funky way uh you know by subtracting R from each entry and each entry is actually obtained by the Reed Solomon you know fingerprinting you know some tuples okay so but what's going on is uh the verifier in the gkr protocol applied to this binary tree multiplication Gates just needs to evaluate the multi-linear extension of its uh inputs and you know you know R

Prime is like this simple combination of a b and c so you can kind of take the multimeter extensions of a b and c and sort of put them together to get the multi-linear extension of R Prime don't worry about the details just you know like each entry of R Prime is just like you know an entry of B plus gamma times an entry of a plus gamma Square attention entry is C so the same linear combination basically gives you the modulator extension of our priming um and W Prime it's something similar so you can take um sort of the multi-linear extensions of the lookup table a b and c and quickly evaluate or quickly reduce it until the commutes with plus and times right yeah uh yeah that's another way of saying

that like read molar encoding is linear um okay so I mean that's that's it um that is basic lasso and actually in hindsight this is already sort of in in Spartan um Spartan uh yeah we're sort of just viewing it in the right way and the other contribution is it doesn't seem that the 1994 memory checking paper was known to be secure previously if the prover could mess with the counts so um they uh I believe the initial analysis was just sort of assuming that these counts were well it actually had one Global count that the verifier could

maintain itself uh and just so every read it just gets incremented by one so it only increases the verifier space By by one that was fine for their consideration then Spartan um switched the global counts to like a per cell count and I think then it wasn't it was possible according to that analysis that the um if the prover messed with those counts it could actually you know trick the memory checking procedure so we show that even if the prover is messing with those counts uh it can't trick the memory checking procedure and That's essential for uh lasso it didn't matter for how the approver happened to use the sort of scheme in Spartan uh cause an honest party was actually able to kind of commit to the counts or something like that

um great so I I still just want to understand where the performance gains are coming from right so like one thing is I feel like comes out pretty clearly here which is what you said yesterday the number of things you're committing to is pleasingly small and pleasingly large number of those are themselves pleasingly small please do small numbers right but then then you're you're also sort of getting savings right on sort of the light the Simplicity of the computation given the commitments yes yeah exactly so here's a summary of all the savings so um if T is structured as all the tables are in jolt no one commits to it even if it has you know side 228 um okay that doesn't seem to just be

possible with univari polynomials it seems like the the associated extension polynomials of T would not have the structure even for the tables like jolt needs okay um A and B sort of have to be committed by definition of a lookup argument it's like part of the input um like you said c so really the only commitments are to see and these are just counts um cool then so uh the other savings is because like uh anything based on univari polynomials as well as something like Spartan would commit to the value of every gate in the circuit which is basically like partial products in these Grand products and we don't do that either

um the price for that is a log squared size proof but I said with just like a lower amount of commitments you can drop that almost to log uh that's this seti Lee stuff we talked about you know where you sort of commit to the many small layers don't commit to the few big layers yeah so it seems that I mean it seems like it's important not just that the computation uses only plus and times but that it boils down to Grand products is that true uh so in general as long as it's like a low depth arithmetic circuit you you could do it with gkr but the fact that it's a grand product makes it like extra nice because uh there's some optimizations in my 2013 paper okay okay yeah but that's it I mean you know I don't think this is actually all that

novel kind of in hindsight um like I said it's almost in Spartan um up to not being expressed as a lookup argument and um have you know uh not showing that it's secure when the counts might be adversarially determined okay uh I know I'm already over but I think uh generalized lasso is uh I can get through I think in maybe even five to next 10 minutes is that okay okay so I do need to cover a basic fat I'm finally going to wind up telling you what a multi-linear extension is so that's that's nice um so there's a uh first I'll start with short zipple which is um an analog of

the fact that any two degree D unitary polynomials can agree out of most like d points unless they're the same polynomial so the same thing sort of holds for uh for multivariate polynomials um so the number sorry the fraction of points they can agree at is at most something called their total degree okay and actually total degree what exactly what that means won't be important for the rest of this talk so let's just not not worry about it all the polynomials I'm going to deal with um basically they're just going to have total degree like equal to the number of variables and the number of variables will be like logarithmic in the M and N where m is the number lookups and N is the size of the table so anyway this is like will be an astronomically small

probability when you work over like a 256-bit field okay um okay so now here an extension polynomial is a poly uh so so polynomial G extends a function f that where f is only defined over 0 1 inputs okay if when you feed g0 y inputs it spits out the same thing as as f okay so G is a polynomial so you can evaluate it at points in the whole field so this is it's an L variate polynomial okay so for each of those L variables you can sort of feed into it any field element and it'll spit out something okay it's said to extend F if when you do feed into it some point where f is defined 0 1 valued inputs it does the same thing as f

and um for any any function defined over zero one to the L there's actually a unique polynomial that has degree one in each variable that's called the multi-linear extension so um here's a quick example here's a function uh you know defined over zero one by zero one so there are four inputs to it here's its multi-linear extension over like you know some large Prime field okay um so again the extension is defined you know each variable you can feed in the whole field okay but it's uh it's an extension polynomial so if you do feed into it any of the four inputs at which f is defined spits out the same thing as f so it's like a domain extension thing

and I did note the multi-linear extension with the twiddle over over okay there are other extension polynomials that are also low degree but not multi-linear here's another example uh uh here here's one that's not multi-linear and has degree two and X1 but it is an extension all right so now I'm going to tell you what problem this subject protocol solves I won't tell you how it works um so imagine like there's there's some L very polynomial G um and all the verifiers going to be able to do is evaluate G at one point okay let's not worry about how it's going to evaluate G at that point we just magically it can do that um the verifiers goal is to sum up G's

evaluations over the entire you know what's called the Boolean hypercube that is you know LL bit inputs they're two to the L of them um now if it were to do this itself it would have to evaluate G at each of these two to the L inputs and sum them up so from the verifiers perspective the sun check protocol will be a reduction in work from evaluating gia2 to the L inputs and summing them up to evaluating ghs one input but that one input will be you know in the whole field instead of in you know the special zero one valued subset uh called the Boolean hypercube so the costs are there's one round per variable okay and if G has degree D in each variable then in each round the prover

actually sends like a degree D unitary polynomial say just like it's D plus one coefficients which means the total proof size is D times L field elements so like you know D plus one field elements sent by the prover per round um the verifier just basically reads the messages from the prover kind of does you know it winds up evaluating each of the the L polynomials one per round at a random point so really uh but that's just like a constant amount of work per coefficient so that's order D times l field operations in total and at the very end it has to evaluate G at one point does that make sense okay so like in applications again like

uh L is going to be like logarithmic in m n d is going to be like two so the verifiers runtime is like something like you know two log N Field operations and evaluating G at one point and you're saying L is long exactly because it's this sort of green product kind of thing you're doing it on no it's not it's not because coming from a grand product it's because of um uh okay uh it's the multi-linear extensions basically uh so we're gonna the G we apply Sun check two will it won't it will be derived from certain multi-linear extension polynomials and um if you say you have a vector of

length capital N or capital M um you want to you wind up and I'm going to actually cover this in a moment you're going to interpret that as a function over zero one of the log M because there are M evaluations of such a functions and so that's where log M variables comes from right and this is this is sort of the magic of uh multivariate polynomials in the context of interactive proofs why they don't use univariate right because uh with you know you can take a vector size n and sort of interpret it as a log M variant polynomial with degree one in each variable and then you have the subject protocol whose cost grow with the degree in each variable

and so with no cryptography you're getting verifier costs that are logarithmic whereas in univariate like you have to have degree M to interpret that Vector as a polynomial one of what matters is like the cost in each variable you want to use many variables to keep the sorry the degree in each variable you want to use many variables to keep the degree low okay um so exactly because I was anticipating your question about like why why are there like logarithmically many variables I wanted to really quickly run through just a random application just to convey that perspective because once you get this it's literally like one slide to describe generalized lasso and then then I'll stop taking up all your

time um so let's consider this counting triangles problem um so here we're given as input The adjacency Matrix of a graph so that is their n vertices out there and there are edges that you know connect some of the vertices to each other and so there's like a row of this Matrix for each vertex and a column for each vertex and the ijth entry is one if and only if they're connected and our goal is to determine the number of triangles that is the number of nodes no triples ijk that are each connected to each other so I is connected to JJ is connected to KK is connected to I say it's an undirected graph okay now the fastest known algorithm for this runs in matrix multiplication time which is super linear you know so this

Matrix has size N squared and it's not known how to solve this problem faster than you know n to the 2.37 or something and it's totally impractical to the algorithm that does achieve this uh I'm gonna give an interactive proof where the verifier runs in time N squared so the verifier saving work by using an approver that it doesn't trust um and here's this perspective we're going to view the N by n Matrix not as an N by n Matrix but rather as a function on you know two login bits so that is the first login bits we interpret as like the binary representation of a row and the second log in bits reinterpreted as the binary representation of a column and we view a as the evaluation table of this function

okay so here's the example here's a matrix and here's how we interpret it it's got 16 entries here we interpret it as a polynomial and zero one to the four right because there are 16 Vector bit vectors of length four you know it's just like you know we're like oh this is the evaluation of a at zero zero zero this evaluation of a zero zero one this is the evaluation of one one okay so here's the protocol um so once we interpret a as a function uh whose domain is you know log n Bits it makes sense to talk about its multi-liner extension polynomial because any function on login bits has a modulator extension polynomial and so we're going to define the pilot

you remember I said the G we apply some check to is not a multi-linear extension but it's derived from them here's G so we take that multi-linear extension and we sort of take three copies of it and product them together so here x y and z are each log n variables so you think of X conceptually as like indexing one node why is indexing another node and Z is indexing another node so together they index like a triangle like three like a triplet nodes that might or might not be a triangle um and and this just spits out whether or not they're actually a triangle so this is like asking is X connected to Y this is like asking is y connected to Z and this is asking is X connected to Z all right so um you know if if any of

these are zero the whole product is zero you know it's not a triangle because two note two of the nodes aren't connected to each other if they're all one it is a triangle X is connected to y y is connected to z z is connected to X okay um so the goal is the verify wants to sum up all evaluations of this polynomial over the Boolean hypercube because summing over the hypercube is like iterating over all triangles well all triples and nodes and saying is this Triple A triangle again so you just apply some check to this polynomial um and uh yeah from the verifiers perspective uh this reduces you know Computing the number of triangles to evaluating G at a random point right

which uh is equivalent to evaluating a total at like three points so you know if uh the random point is R1 R2 R3 each is log N Field elements you need to evaluate a total at R1 comma R2 our two comma R3 and R1 comma R3 and multiply them together okay and these modular extensions are really nice uh the verifier can actually get each of these evaluations on its own in time linear in the number of entries of a so that's why the verifier is linear time and you just have gonna have to believe me about that right I'm not going to cover the algorithm how easy is it to compute the multilinear extension of a polynomial or is that something like the prover also needs to prove that this is the right um yeah so uh if the verifier only needs

to evaluate the multi-linear extension at three points and each evaluation can be had in time linear in um the input that we're taking the extension of remember I mean like how uh how does the verifier know what the multilinear extension of the the input to the verifier is this n by n Matrix yeah it it needs to evaluate the multi-linear extension of that Matrix at three points how does it get the multi-linear extension like is it complicated to compute that or is it simple given the Matrix I'm saying there's a linear time algorithm okay that given a and given a and a desired evaluation Point like R1 R2 we'll compute a total of R1 you don't write it out explicitly crucially the multi-linear extension right your output

no yeah like no one ever writes down the evaluation table of this thing because you know even one coordinate can have um you know field size many values and there are you know log you know two login variables of it right so it's like you know you can't even iterate over all possible values of one coordinate much less log in so the prover and verifier both and I'm hiding lots of details here but no one ever they only like have to evaluate a twiddle at like a small number of points for the verifiers three for the approver it's order n cubed or something I'm sorry maybe it's obvious but like the N squared's coming from well just to read the input is M Square time I see okay and the verifiers are just doing

constant Factor more work than that to evaluate a twiddle up to three points okay so it's I mean it's best you can hope for you know the linear time and the size of the input it has to read the input at least okay and when you see linear time evaluation you mean in squared time yeah um now the prover here has time and Cubed which does match like sort of the naive triangle counting algorithm that goes over every triangle there's actually a way using my matrix multiplication protocol to reduce the prover time to like um it just as long as it can compute the squared adjacency Matrix which the fastest known algorithms do anyway it just does order N squared additive extra work to to prove correctness

um so even the prover you know the one downside here is like prover time which is like you know not bad in that it matches like the simple algorithms runtime but you can actually really match the fastest known algorithms time up to a low order term so this is kind of the power of of some check um but now let me tell you generalized lasso so this is uh just two more slides I think and then we're done um yeah so this time I'm just going to talk about unindexed lookups just makes things a little simpler so the prover is committed to a vector a and claims every entry of a is somewhere in the table um and you remind us briefly what you're trying to do relative to lasso the generalized lasso yeah so I mean what the the payoff is going to be what

compared to what we already saw yeah so we're going to be able to um handle gigantic tables um with prover costs like table size to the one over C um as long as uh the multi-linear extension of the table is quickly evaluatable as opposed to like a decomposability property right yeah okay and so basic lasso itself um yeah had this thing where you know the approver had to commit to um uh you know the this final Passover memory uh overall end memory cells involved a bunch of counts now if the

table is the memory size is huge most of them are zero uh so it's this weird situation where these very sparse large vectors you can commit to them quickly but then the evaluation proofs might be enormously expensive uh so we're not happy with that so um the generalized lasso will reduce that cost uh to tableside to the one over C um and it will work as long as the table has a multi-linear extension that's quickly evaluatable actually it doesn't even have to be multi-linear extension it's any low degree extension it's fine so um yeah like when the approver commits to um a the vector of values being looked

up uh is committing to the multi-linear extension of a with the polynomial command scheme okay so that's what the verifier is handed it's uh handed a commitment to the multi-liner extension of a um now the natural witness in an index lookup there wouldn't even like uh the the witness would be baked in uh because the indices would already be there but in an indexed lookup the witness is the indices like where each AI resides in the table that's what the proof is claiming is you know for each AI there's some index where it lives so I'm going to take this witness and I'm going to represent it in extremely sparse form something a little funny we're going to take each index and write it in unary so we're going to turn it into a vector of length n that's like all zeros except

a one in the indexed Vector so the picture is in um sorry the the picture here is uh uh yeah if um I guess I didn't so you know uh if our table is you know zero up to seven and you know our lookups are five zero two four you know uh five lives in I guess it's the sixth cell but uh you know in unary it's you know zero with a one in the sixth entry you know uh zero lives in the first cell it's one in the first you know okay so that's M so it's a it's a capital m is is Little M by capital N matrix it's very sparse Matrix okay um and sorry there uh I'm gonna turn

um this property that AI lives in index J you know J of I uh where again uh the I throw of M is Javi in unary uh I'm turning I'm going to turn it into a matrix Vector multiplication that's actually that's why we Define m this way by the way this is the same um sort of witness that appears in the the caulk line of work so we sort of just take the the call approach and uh but use some check based techniques instead of um what what all the works in the call client work are doing um so so checking that uh you know this property holds uh each AI lives in the appropriate table entry is equivalent to a matrix Vector multiplication okay so for example um

you know like checking that uh you know entry five the first lookup um lives in the appropriate index of the table uh the six index is the same as confirming that the first row of the table dot uh dot the table equals five because you know this uh this is why the table is in unary like this one picks out the appropriate index from the table all right so um yeah let's uh if you let b equal m times T so if the prover's honest uh B is the same as a if it's dishonest B is different than a um now the multi-linear extension of B has a really nice expression that just like follows directly from Matrix Vector multiplication

um so you know because multi-linear extensions are unique as long as I can show that this is uh this right hand side here is a multi-linear polynomial that like agrees with B uh over the the Boolean inputs the zero one valued inputs it must be the modulator extension of B and it's clearly multilinear because M twiddle is by definition multilinear and uh we're feeding R only into M twiddle so we've got you know we've got some for each fix you know uh we've got something that's quadratic in J but then we sum J away what's left is multilinear okay so that's uh that's what tells you that this right hand side is multilinear right again we're feeding uh R only into M Twitter and Twitter's multi-linear so

the right-hand side is multi-linear and r um and sort of by definition of Matrix Vector multiplication like if R is a bit Vector uh so thereby indexing uh an entry of B uh this is uh you know just doing the inner product of the appropriate row of M and and and T it's computing um the arth entry of M times T right just picking a random row right yeah uh if or so R is this a quality holds even when R is anything in the whole field but the way to check that it holds over the whole field is to check that it's multilinear and holds over the blue and hypercube right good yeah so it's multilinear and the fact that it holds over R being Boolean zero one value it

is like just the definition of Matrix Vector multiplication great so um and by the short simple Emma you know if like uh in order to check that Mt equals a it's enough for the verifier to pick a random R and confirm that b Twitter of R equals a twiddle of R right because if they're not the same polynomial then you're going to disagree or not the same Vector then a12 R and B total bar will disagree at r uh with high probability okay so so here's lasso in one slide uh in a second and then I'll I'll be done um so yeah the prover commits to M twiddle so that's like cryptographically committing to like a witness but like a

witness in this weird sparse Matrix form like the way it's like the indices that um each lookup value resides in but written in unary row by row okay so commits this polynomial V Pixar random R and needs to confirm that a total VAR equals this thing this is this is an expression for B twiddlebar right okay so conceptually we sort of reduce like checking entry by entry that A and B are the same to evaluating like the multi-linear extension of H1 just one point and the Montana extension in B2 are just one point and uh you know that evaluation of B twiddle has this nice expression okay so the verifier is going

to get a total of R from the commitment to a twiddle like that's what polynomial equipments do is they let you evaluate the committed polynomial at a point and it's going to get this expression by applying the sun check protocol um to uh compute this sum okay so it applies the subject protocol to you know the polynomial within login variables its variables are J to sum up you know the M total of R comma J times t total j to sum up that polynomials evaluations over the hypercube and at the end of the subject protocol you know the verifier needs to evaluate um the polynomial being summed at a random point so that entails evaluating and total at one point and t total at one point

okay so in summary like what some check has done is reduce checking that you know a equals m times t to checking that a total of R uh equals some something that that's something via some check in turn gets reduced to evaluating M twiddle and T twiddle at a random Point each foreign now the very as I said the verifier gets the evaluation of a total from the commitment to a twiddle and the evaluation from M twiddle from the commitment to end twiddle and it gets the evaluation of T twiddle if it's a structured table just by evaluating T20 at one point itself which think of that as like maybe 100 field operations or something for the verifier okay CT Twitter's sort of like your

Oracle or like I'll give you that as a subroutine that's the Assumption yeah yeah so the polynomial being sum like is it involves both like as you're applying subject to involves both M twiddle and T twiddle um so you need one evaluation of each in order to simulate like the Oracle for the thing you're applying subject to okay now there are two major details I've hidden here I mean this is this is generalized lasso but the two major details are like the first one is you know M twiddle is this huge Matrix M by n where n might be 2 to the two five six right but it's very sparse okay so uh when I just say um the prover commits to M twiddle um it you really need the time to produce that commitment and the

evaluation proof to be linear in um not the total number of entries in The Matrix but just the number of non-zeros okay that for uh that's uh something called a sparse polynomial commitment scheme okay um and so uh actually the lasso gives a sparse polynomial commitment scheme you've basically seen it like basic my presentation of basic last set was basically how it works um it's the first sparse polynomial commitment scheme a sort of optimal approver cost like even asymptotically uh this is coming from uh the key to this is that um you know Spartan also gives one but these counts have to be committed honestly instead of by an

adversary and so it doesn't actually give you like a true commitment scheme where the committer can be totally adversarial um and the key the way it works is like the prover commits to just the locations of the non-zero entries of M which is a funny thing it's like you know um we're taking the natural witness which is like the indices that the lookup values reside in turning this very sparse form but then the way we commit to the sparse thing is just by going back to the dense thing and then when the verifier says hey I need to evaluate the committed sparse thing at a point R uh what the prover does is it just proves it correctly ran an algorithm that uh like iterates over all these non-zero indices uh and evaluates and twiddle uh at our kind of

one term at a time and the key point is uh this is It's a non-trivial algorithm um but all it really does is look up into a table the table has size n the number of columns in this Matrix and it's uh decomposable okay so uh basically like inside the sparse polynomial commitment scheme used in generalized lasso is lasso itself okay because basically sparse polynomial evaluation involves lookups into a decomposable table and that's what lasso handles so there's some kind of generic reduction from um General lookup tables at least with

kind of fast mod uh you know extension polynomials to lookups into decomposable tables just because the snarks use polynomial commitments in their guts and polynomial evaluation involves structured decomposable tables and then the the final detail is uh implementing the prover quickly in this subject protocol remember um the uh the polynomial that some check got applied to this like end twiddle of R comma J times T twiddle A J thing uh that's a log n variant polynomial and N might be huge like two to the two five six so that uh that's like um basically the you're taking uh like T

twiddle is like the extension of such a big Vector that if you're it's not immediately obvious how you can implement the prover in the subject protocol you know it's a sum over two to the 256 terms or something how to implement that quickly uh but the key point is since m is sparse no matter what the value of R is this R was chosen by the verifier when you fix the first log M coordinates of them twiddle to R the resulting polynomial in J is like still sparse so uh basically um ultimately some check is Computing the inner product of two giant vectors one given by m total of R comma J as J ranges over bit vectors of length log n and uh and and the table

so those are two vectors of length n and might be huge but one of the two vectors is sparse okay and also we're assuming that the table is like has some nice structure to it you know it's you can evaluate a small two inner extension quickly or something so we show that this is enough uh to implement the subject prover in time proportional to M and you don't get a factor like like n really uh yeah okay so that's that's lasso I hope that was helpful and I hope you see where we're sort of minimizing the commitments so the cryptography is only being used um really to commit to these multiplicities um that's it okay thanks a lot thank you