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

Transcript

uh very pleased to introduce Justin thaler of course one of our own research partner here at a16 zoo crypto I'm also a professor at Georgetown he's going to be giving two talks so today's going to be part one which will be more of the kind of high level overview and kind of why you should care and then tomorrow we'll have part two which is more about how things actually work under the hood it's very exciting work sort of new proof systems that he's been working on with a number of collaborators so lasso jolt and the lookup Singularity and so Justin I'll hand it to you uh thanks Tim yeah so this joint work with uh srinath study Riad Wabi arasu Arun uh Sam ragazzo and Michael Jew uh arisu was a intern here last summer and

uh Sam and Michael are our Engineers here um yeah so uh this is a talk about something called snarks um and I'll I'll start by giving a brief survey of snarks uh kind of I start most of of my talks on snarks with this survey um kind of keep it updated as the ecosystem evolves uh but then I'll dive into sort of a topic that's more specific to this talk something called look up arguments because today I want to tell you about a new a new family of lookup arguments called that we're calling lasso and then I'll describe uh something called a front end a new front end technique which we're calling jolt that of course Builds on the new the new lookup argument lasso all right so obviously I'll say in much more detail

shortly what is a lookup argument what is a front end and all these terms will make sense um okay so let me start with what is a snark so in a snark an untrusted prover claims to know a witness satisfying some property so just to have a really simple example in mind the prover might claim to know like a pre-image under are some cryptographic hash function of a designated output okay so maybe like the proven verifier have agreed in advance that they care about say the sha3 hash function and the proof is claiming to know just a w that hashes to a certain string y okay um so the trivial proof that the prover indeed knows the witness that it claims

to know is just to provide the witness to the verifier who can then just directly check that the witness satisfies the claim property so in this example uh the verifier would just like evaluate Shaw 3 on W and confirm that the output is whatever the prover says it should be okay so a snark is just uh any a cryptographic protocol that achieves the same effect but with better cost to the verifier okay so ideally in a snark that Spruce will be short and fast to verify okay so uh you know snark stands for succinct non-interactive argument of knowledge and uh succinct is sort of just a technical term for short proofs and at least I personally used to think

to mean kind of any non-trivial amount of shortness so as long as the proof is shorter than the witness itself like the trivial proof is the witness so uh I call any any proof shorter than the witness succinct okay and I I ideally checking the proof will be fast um you know again I I would consider anything that sort of faster than what's required to check the witness directly for validity to be you know non-trivially fast um and I'll use the term work saving to clarify that you know the producer not only short they're they're fast to check okay uh non-interactive just means the proofs are static so they can like be posted to a blockchain um instead of requiring some kind of interaction between the prover and the verifier and argument of knowledge just

means that uh the prover can't actually find a convincing proof of a false statement unless the claim it's making is actually true or unless it can break some crypto system or something like that okay um so let me say a little bit about how snarks are designed um at least aspirationally and then I'll say a little bit more about how they're kind of actually designed today so ideally uh some kind of a developer would write a computer program in a high level language like rust or C or whatever high-level language you want to use um and I'll refer to this as kind of the witness checking program so you think of this computer program as taking as input the purported witness and just checking that it satisfies the property the

approver claims it should so in the little example from before the witness would take as input W and evaluate shot three on it and confirm that the output is y okay um so I could that's sort of the direct witness checking program okay um now in in most snark tool chains today um there's sort of a two-step procedure to actually uh apply a snark so so first you apply something called a front end which takes that computer program uh that the developer wrote and turns it into an equivalent representation in sort of a much lower level computational model typically some analog of a circuit like an arithmetic circuit is typically what the snarks like to use okay so you

can think of the circuit as sort of an implementation of the computer program on some very very low level Hardware kind of even more simple and lower level than like the hardware run on your laptop um you know this these circuits have very very simple operations that they can do um yeah and the the reason to go through the circuit is because the circuit is so simple in a sense that it's then very easy to design snarks uh to allow the prover to prove that it knows a satisfying assignment to the Circuit so I base the question but can every program be written as an arithmetic circuit yeah yeah um so uh the question is can every computer program be turned into an

equivalent arithmetic circuit and the answer is yes and asymptotically anyway the circuit doesn't need to be too much bigger than the computer programs like runtime um and I'll get into more details about that's sort of the whole point of this talk is just how true is that statement concretely you know and the completeness and whatnot but here it's really been used in a positive sense very strongly right yeah yeah and these reductions um from computer programs to circuits if you want them to be good enough for practical use you can't just invoke like cook Levin which I guess typically turn just considers like three sat the circuits that snark shoes tend to be sort of much deeper than um depth two which is and and you know

not just have terms of width three or something yeah so um it's a whole uh but sorry quick follow-up question to that sorry I realized I'm suddenly speaking out of the screen or something should we think of these reductions as being General across context or are there going to be context specific ones for given types of programs yeah great um so we do have general purpose uh Transformations uh that can take any computer program and turn it into a circuit that in principle is not too much bigger than like the runtime of the computer program typically for any particular computer program you could tailor the circuit uh to the program in a way uh that's gonna get you something um and that's always attention uh kind

of generality of the uh transformation techniques versus efficiency in any particular application so there's always a lot of work of um kind of uh protocol designers very carefully like tailoring the circuits to the specific statement they want to prove and uh yeah not all systems uh some systems are completely General others are sort of tailored to the very specific statements in the application of interest does that make sense yeah super helpful thanks other questions this is I mean it's probably this is a side track but on the generality thing is that all NP programs can be arithmetic circuits are all programs yeah great

um I so okay whether you start with a uh like a NP program where you know there's some non-deterministic input or just like a program with fixed input um if you want the circuit to be not much bigger than the runtime of the program um you the circuit uh the instance that comes out is really like circuit satisfiability and what happens is the transformations in general introduce a lot of what are called untrusted advice inputs where you think of kind of the snark prover as providing kind of um help to the Circuit um to keep the circuit small a concrete example is let's say the computer program needs to uh like divide two numbers together it's

pretty horrible in a circuit to actually Implement a division algorithm uh but you could have the prover sort of provide like the quotient and the remainder and the circuit just needs to check because it's untrusted advice is you know the quotient times you know whatever you're dividing by plus the remainder equal to the original thing does that make sense the computation has whatever time it has it's probably maybe it's more the point is the circuit is going to be as big as the running time or a little bit bigger even then the Pro uh that's right that's right um yeah and you do get into situation so like some some snarks for circuit set or like really really fast for the prover

if there like aren't many advice inputs um but are are not so interesting if there are a lot of advice inputs so it is worth noting that um these General transformation you know for specific programs you might not need many advice inputs to keep the circuit small but in general um actually the number of advice inputs will be a constant factor of like the total size of the circuit okay so just like taking a step back on summarizing the slide most Snorks are deployed in sort of a two-step process where first you turn the witness checking procedure into an equivalent circuit and then the prover approves with something called a snark back end that it knows a satisfying assignment to that circuit sort of put these two things together and the approvers actually prove that it knows a witness that the computer program would have

accepted okay all right um yeah so just a very brief summary of front ends today so I mentioned that this Paradigm I described is a little bit aspirational uh the aspirational part largely being that I said the we want our developer to write the witness checking procedure in a high level language um so there are a number of popular front ends today on this slide I've sort of arranged them from like low-level language exposed to the developer to higher level languages um so like Bellman and cercom are very popular languages people actually really like using them but they're almost having the developer specify the circuit gate by gate whereas this third category I have here are targeting uh letting the

developer program in higher level languages whether it's solidity um or uh you know even uh like a Cairo 1.0 refers to a rust-like language it's not literally rust but sort of inspired by rust and then there's a front end that will go through the whole compilation procedure I described to ultimately get out of circuit in the end in something like a circuit um and uh yeah so I'll talk a little bit more about the tooling ecosystem today later later in the talk what is the middle middle range between the first one and the last one yeah so um zoc Ortiz and XJ snark I I just say they're domain specific languages that are a little bit higher level than

Bellman and Sir com um yeah I guess I don't there's not much more I want to say about that um there's sort of a step removed from uh having the the programmer like just write down like the the gates of the circuit directly yeah uh yeah I'll just leave it at that um yeah there's uh kind of a naturally a potential trade-off between um the niceness of the developer experience and the uh both the the size of the circuits that might come out um of the front end as well as uh sort of how big a surface area there is for bugs right so kind of the more complicated the compilation procedure

from the program the developer writes to uh the circuit that comes out the more room there is for bugs of course um the sort of less nice to developer procedure the more likely it is the developer itself introduces a bug and like doesn't write the circuit correctly so it's kind of trade-offs all around are there a lot of uh hybrid front ends that sort of allow General compilation but like rely on a lot of gadgets or hand-coded libraries and things yeah um a lot of these uh languages um uh do have sort of built-in gadgets for very specific functionalities that are done commonly um they're often called like built-ins

or something um so people are sort of trying to um determine the best kind of trade-off between performance and developer experience and generality and you know uh surface area for bugs to creep in and it's a very sort of high dimensional optimization space um yeah other questions can I ask a question please go ahead um how do you make sure that the circuit actually corresponds to the software you're really interested in uh yeah great so I guess I was kind of getting at that question uh when I said that kind of the more complicated the compiler from the program the developer writes down to the Circuit the kind of more space there is for like bugs bugs

to creep in so um you know people have attempted and are continuing to attempt to kind of formally verify um as many parts of this tool chain as possible but there are a lot of parts of the tool chain um so like actually almost all of these projects um that do are aiming to expose high-level languages to the developer they all go through something called a ZK VM which kind of means the circuit actually like directly runs a computer like runs a witness checking procedure kind of inside the circuit step by step right so um if the and that means they wind up using um what what people will call a virtual

machine or CPU abstraction uh where they specify some primitive instruction and the circuit actually just you know for each step of the computer program figures out which instruction should be executed next and executes the instruction and you know just does this over and over again like in the circuit okay and so um there has been some work to like formally verify that the step of going from um like a program in the Assembly Language for the virtual machine uh does get turned into an equivalent circuit okay uh but then they have not formally verified that the compilation procedure from the high-level language down to the assembly program for the virtual machine is is correct right so um you know the

best we can do is uh you know uh short of you know formally verifying the whole tool chain is to just be very careful about how we design these things so that what comes out of one end of the compiler is equivalent to what went into it uh does that make sense did that answer the question should I say yeah but I'm like when I'm verifying I mean I'm still trying like I'm thinking as a user don't I still need to trust the compiler yeah you do um so uh let me think how to answer that um yeah so often okay so different front ends work in different ways some front

ends will actually spit out a universal circuit where uh like kind of the circuit actually takes as part of its input basically the computer program to be run okay and then um uh you only have to like there's one verification uh procedure that's going to work for you know like any computer program um it you know you just have to make sure that the the circuit is fed the correct computer program kind of um but uh yeah you could imagine uh you know there are other front ends that uh sort of the circuit itself is program specific it's not a universal circuit um and then every time you you know uh are interested in a different witness checking procedure um you're going to like the the snark

verifier depends on the circuit it's getting applied to um so you're going to have to make sure for you know every time you change the computer program that the equivalent circuit is indeed equivalent like the verifier is ultimately just going to make sure the approver knows a satisfying assignment to that circuit and if it's the wrong circuit well too bad does that does that make answer the question yeah yeah any more questions okay so uh yeah I mean I think that um the possibility of bugs in this this tool chain is a major concern in sort of the long-term usefulness of snarks um and you know I think we can

um ultimately make uh sort of the the surface area for bugs like maybe no bigger than like the current surface area for bugs in in compilers from high-level computer programs down to what actually runs on your laptop or something uh but the the stakes for bugs might be even higher than usual because you know one issue in the compiler um and all of a sudden you know like all of the money on an L2 is just gone or something like that you know um yeah and I can say a little bit more about that if I don't run out of time by the by the end of the talk okay cool all right so let me just say a little bit about how backends are designed so these are like Snorks for circuits at um so typically these are now designed in a three-step process

um so first you give something called a polynomial IOP for circuit satisfiability um I'll say in a moment what that means um and then you combine it with a cryptographic primitive called a polynomial commitment scheme and I'll say in a moment what that means if you put these two together you immediately get a succinct interactive argument um and then typically you can remove the interaction to get a snark non-interactive argument by applying something called the fiatry mirror transformation okay so um this is how almost all snarks are designed there are a couple of exceptions um say one of the two exceptions I actually don't even consider to really be an exception because it almost follows this Paradigm um and then the uh there is like a real exception which is getting quite popular

now something called Nova um or Nova is the most popular instantiation of this this other version um this other approach inherently uses something called snark recursion um whereas um the everything else on the slide like you know you can apply it recursively but you don't have to so this uh I don't know yeah this quote folding based snarks that that don't use polynomial commitment schemes um and polynomial iops necessarily um sort of are getting a lot of mileage through using making heavy use of recursion and if those words don't mean anything to you just does it don't worry about it um so the Snorks I want to tell you about today uh do fall into this this Paradigm uh so let me briefly tell you what is a polynomial IOP

um so it's a it's a proof system where uh sort of the prover sends a sequence of messages to the verify fire and okay this is actually a special case of a polynomial IOP but it's all we're going to need today so the first message the prover sends is kind of special okay it specifies a polynomial and by polynomial I really mean sort of what you saw in maybe like eighth grade or high school algebra or something I mean like like uh you know one plus X Plus 3x squared plus four x cubed right like a a sum of powers of of X um that's univari polynomials will actually need multivariate ones today um and this polynomial if you were to actually like write down all of its coefficients or something

um in in most snarks would be as big as the circuit the proof is claiming to know a satisfying assignment to so it's sort of it's too big for the verifier to learn in full that would like totally violate work saving for the verifier um so we're not going to let the verifier learn the whole polynomial okay all we're going to let the verifier do is evaluate that polynomial at like one point of its choosing okay then other than uh that one special message that specified this really big polynomial um a polynomial IOP is just sort of a standard what's called an interactive proof where the you know prover says some stuff and the verifier sends back a random challenge in the prover system more stuff than the verifier sends back a random Challenge and so forth okay um and uh yeah so uh that's a polynomial

IOP and a polynomial commitment scheme is just exactly what you would want to turn a polynomial IOP into a succinct argument okay so you know the problem with the polynomial IOP the reason it doesn't just directly give you a succinct argument is because of this big first message specifying this big polynomial so what the polynomial commitment scheme lets the prover do is cryptographically commit to the polynomial and the commitment will be really small like one hash value or one group element or something and the commitment any commitment scheme is binding meaning sort of you know you think of the prover as like stuffing this big polynomial into a tiny box and it hands the Tiny Box to the verifier that's the commitment the box is like locked right so like once the

verifier gets that box in its hands the prover can no longer change what's inside of it okay um and so then later uh when the verifier says hey I need to evaluate the polynomial at this one point um the approver can provide the evaluation as well as a proof that the provided evaluation is actually consistent with the polynomial that's inside the Box sort of the verifier never has to open the box and take out the whole polynomial it can sort of just rely on this proof that you know the prover is being honest when it says here is the requested evaluation of the thing inside the Box okay so polynomial commitment scheme is just a cryptographic protocol that allows exactly this functionality okay and this just means we can sort of run

the polynomial IOP without the prover ever sending this big polynomial and that was the only thing keeping the polynomial IOP from sort of directly being a succinct argument on its own I mean so a question about that so so after the initial sort of send the polynomial commitment message like you need a protocol then that has a short transcript right after that right right so to get a snark right right so it's not that's right that's right and so we make sure that that's always the case and this generally going to just looked like a bunch of a small number of random challenges basically from the verifier and then and in the snark all those challenges will be obtained via Fiat shimir which means by hashing like earlier messages so there's no interaction and then the previous

responses will typically be depends the snark you're talking about uh the ones today they'll they'll just be really low degree univaric polynomials so just like a handful of field elements to actually write down all the coefficients um and other snarks that might involve more commitments to more polynomials um and more evaluation proofs and things like that and so should I roughly think of it like there's going to be a logarithmic number of rounds with like constant number of bits yeah every every every uh snark I want to tell you about today um they're based on these sort of multivariate polynomial techniques and that's their characteristics so there's logarithmically many rounds and there's like say three field elements sent per round questions

yeah how does linear PCP based methods differ from this Paradigm like you mentioned they are kind of similar what is the main difference yeah I'd say in the end the main difference is um that the linear PCP based snarks don't need to use Fiat schmear and that can be nice it can give some nice properties of the snarks that the ones that everything else uses fiatrimir might not have but nonetheless linear PCP based snarks um are very similar like a linear PCP is some sort of variant of a polynomial IOP uh replace polynomial low degree polynomial with linear function and um and the cryptography used to turn those into snox is very similar to

something called kzg commitments so here's just one slide about the different kinds of polynomial commitments out there um so they're sort of three or four main categories and that sort of highlighted it for each of the main categories in green maybe what's most popular in terms of deployment today they tend to be the most popular because they have the shortest proofs in their category at least asymptotically actually think for some of these concretely they might actually be bigger proofs than some things that are asymptotically worse but anyway um yeah so kcg commitments are very popular because concretely they definitely have the shortest proofs uh evaluation proofs out of all everything um sort of the and these linear PCP based snarks use techniques very related

to kcg so there are trade-offs like kind of right and left with polynomial commitment schemes out there like you know kzg commitments have the best verifier costs but they require a trusted setup right um you know IPA also known as bulletproofs um is uh does not require trusted setup uh but it's both of these use elliptic curves so they're not plausibly post Quantum secure this third category is plausibly plus Quantum secure but the verifier costs are bigger things like that uh the the green indicates what you know kind of most practitioners should be aware of um the most popular from each category sort of in deployment and the reason is roughly because they have the

shortest proofs uh amongst its category other questions cool okay so um yeah let me just uh Briefly summarize uh snark performance today uh so I sort of told you it's a question yeah so like how much does what happens after the polynomial commitment scheme depend on the polynomial commitment like is the rest of the protocol tend to look kind of the same no matter which of these you use or yeah so um up to some technicalities you can basically take any polynomial IOP and any polynomial commitment scheme and put them together and get a snark the main technicality is some polynomial iops want to send univari polynomials others multivariate and the polynomial

commitment scheme kind of has to match um and yeah there's a there's a variety of polynomial iops out there uh there's a variety of polynomial commitment schemes um I'm gonna start talking in a moment about how the concrete bottleneck in most snarks is the polynomial commitment scheme um but uh the polynomial IOP can kind of help determine like how big a polynomial needs to get committed and stuff like that um so maybe there'll be more uh information you know I'll cover in due course like but yeah so you're saying let's really focus on the commitment scheme and optimizing that and um I think the way okay I the way to the way I think of it is one should design a

polynomial IOP to minimize the amount of stuff that needs to get committed uh and then one can just choose uh any polynomial commitment scheme to plug in um you know to turn that thing into a snark uh just pick your favorite uh kind of trade-offs from the polynomial commitment and so this knocks I want to tell you about today they can use any polynomial commitment scheme uh for multivariate polynomials um and there are you know analogs from each of these categories for a multivari polynomials and you literally can just pick your favorite one so if you don't mind a trusted setup you might pick one that's you know sort of based on kzg um if you do mind it uh you might pick one based on bulletproofs you know based on this High racks thing so we'll say

more about this so what's going to be novel is what follows the commitments came you're saying yeah so we're gonna just black box the commitments today which is actually one reason and I wanted to talk about how you have a lot of choices of commitments but now from now on we're not going to talk about how the commitments work at all okay yeah so in general today I'd say the verifier in in snarks is generally cheap certainly much cheaper than direct witness checking uh there is a lot of variation um in terms of the verifier costs but nonetheless it's still certainly like sublinger costs right um so I can actually be multiple orders of magnitude differences in like kind of how expensive is is the verifier today um but my main focus in this talk is on

the prover because I think this is really uh what sort of limits the applicability and scalability of snarks so in general um the prover today in a snark will be at least six orders of magnitude so at least a million times slower than direct witness checking than just like running the the witness checking program directly on the witness now this overhead can be heavily parallelized so you can just like throw a bunch of gpus at it and that's going to help a lot but still if uh you know if you make one computation like a million or 10 million or 100 million times slower it's still going to limit what you and what you can prove okay question what is Stark um that's a particular kind of snark

with uh I guess a pro you know everything's trade-offs right so a pro is it's it's a one example of a plausibly post Quantum snark a con is the proofs are much bigger than some of the others okay so I think the overhead for the prover can generally be broken into two parts um and they kind of multiply together so um I call it front-end overhead and back end overhead I'll put up a bunch of words on the slide but as you know that maybe just listen to me speak so uh sort of the front end overhead is like how bad is it that we have to go through a circuit you know that we can't just kind of run the computer program directly but we have to turn it into an equivalent circuit and then the backend overhead is

like how much worse is it that we have to prove that the prover knows a satisfying assignment to the Circuit versus just like evaluate the circuit on that satisfying assignment okay now each of these overheads is at least like three orders of magnitude today and they multiply together which is where you get sort of a lower bound of a million fold slowdown for the proverb okay now the bottleneck in the resulting snarks is typically the polynomial commitment scheme now that's not always the case um I think it's it's very rare that it's far from being the case I would say if it's not the case you know the right view is not that you know this this snark uh like has an especially cheap polynomial commitment scheme now it's that there's too much work happening outside the polynomial commitment scale okay so certainly for the snarks I want

to tell you about today the polynomial commitment scheme will be the bottleneck and so I'm going to like very very heavily focus on accounting for how expensive is this polynomial commitment scheme um and yeah I think certainly the polynomial commitment scheme is always a lower bound on the prover time say if it's not the bottleneck it really means you should revisit the snark because the proof is doing too much work uh aside from the Computing the commitments so you feel like that's fundamental or just kind of an artifact of the current state of the art um for some reasons like is there some kind of vague intuition about why you would expect yeah well the the intuition is the bottleneck for the prover cryptography is expensive and the more stuff the prover needs to commit to the more cryptographic operations it's doing everything that happens outside of

the commitment scheme is sort of non-cryptographic in nature and it should be lighter weight are these two overheads sort of independent or could it happen that you generate like a worse circuit in the front end which is easier to generate a snark proof oh yeah great question yeah it can be quite very hard to keep these a clean line separating these two and in fact um you you run into these issues where you might have a snark that sort of supports a more General kind of circuit um so the circuit you apply it to can be smaller but like for a circuit of a given size it's slower but like it still comes out ahead because the circuit's smaller and things like that and what I want to tell you about today and I'm finally getting

to the the new content uh the questions have been great though I hope people don't mind that if I take a little extra time is um look up arguments and I think they really really straddle front ends and back ends and it's very difficult to draw a totally clean line nonetheless I think this view of I'm pretending you can draw a clean line I think it's a powerful view anyway um to the extent that it's accurate okay yeah and if you're interested in more details about front and back and overheads last summer I wrote a blog post about this for a16z so you can check that out uh no so uh the snarks I want to tell you about today so again they can use any commitments any polynomial commitment scheme for multivariate polynomials um I think they're particularly interesting performance characteristics

if the commitment scheme is based on what's called multi-exponentiations so these are actually this is the first two categories out of the three I had or I guess I had four on the on the slide before so things like kcg commitments things like bulletproofs okay so what is a multi-exponentiation um so here we're dealing with a cryptographic group I'm using multiplicative notation here that's just a convention sometimes people write the group operation as addition instead of multiplication it doesn't matter um so I want the exponentiation is just a product of a bunch of exponentiations so these gi's are group elements and these xi's are exponents they're numbers right

um so if you did use additive group notation it makes sense to call this a multi-scalar multiplication because kind of exponentiation turns into multiplication and multiplication turns into addition and so that people abbreviate that msms so that's I'll use the acronym MSM a bunch in this talk um and yeah a lot of a lot of polynomial commitment schemes that are popular are based on on multi-expentiations uh basically the to compute a commitment to a bunch of field elements interpreted it as a polynomial in some way you literally just do a multi-exponentiation um and typically the committed field elements are the exponents in the multi-exponentiation um so gi's are somehow yeah GIS is like fixed or should I yeah they're fixed so

in um with kzg these gi's are elements of a structure reference string that was generated in some ceremony um ethereum's running one right now um and uh for something like transparent like bulletproofs um these would just be random group elements which everyone would obtain by like applying a prg uh to some you know natural seed of some sort of like the gis are like magically fixed in advance yeah yeah and then the XIs are like what you want to commit to go okay yeah and so it's compressing where you know you want to commit to nxis and the commitment is just one group element so that's what the commitments are nice and small okay now uh the naive algorithm uh to

compute a multi-exponentiation would just do each exponentiation and multiply the results okay I want to clarify an exponentiation can be 400 times slower than a group operation right basically these exponents can be as big as like the size of the group typically these groups are size like two to the 256 which means one exponentiation is like 400 multiplications because that's how much it takes to raise a group element to the power like 2 to the 256 or something okay actually a lot of papers don't distinguish between exponentiations and group operations and they're ignoring a factor of 400 if they do that um so there is a non-trivial algorithm because you don't actually care about in this uh the result of all n

exponentiations you only care about the one number that comes out of the multi-exponentiation there's something called pippinger's algorithm that can kind of reuse work across the exponentiations and this will save you a a factor and runtime of about login Um this can be significant in practice it can be well over 10. okay um on top of that this is another underappreciated fact if all the exponents are small or small and I'll say what I mean by small later um you can save another factor of 10 in the commitment time um this is just analogous to how uh you know Computing you know like raising something to the power 2 to the 16 is much faster than raising it to the power 2 to the 160. like this can be computed

by taking GI and squaring it and squaring that and squaring that if you do 16 squarings you've raised GI to the power to the 16. but you need 160 squarings to raise it to the power to the 160. so your 400 that's like you're getting that from 256 squarings plus roughly half that to sort of sum the things together that's exactly it that's where it comes from exactly um and yeah so so this 400 is if the exponents were like random as actually they often are but they won't be today they'll be small it's one of the main points of today um and that's why yeah if in fact if it's actually like a worst case exponent I guess it could be

you know 512 times lower potentially or something like that okay um okay so uh no so if all of the exponents are at most K and I guess it should be n and this size of the x multi-exponentiation is is more than the maximum exponent size okay uh you can actually compute the multi-exponentiation with just about one group operation uh per like field element that you're committing okay so this is like 400 times faster than like a naive algorithm when the exponents might be random okay I mean this is like a big difference in efficiency which is why I'm highlighting it now at the start of the talk so the summary is uh

multi-exponentiation based commitments when you're committing to small field elements are like way faster than General multi-exponentiations if you're committing to um not small field elements and this is if you're not using pippengers everyone should use pippengers though and so in your construction you're going to take advantage of this small k thing yeah so the stocks I want to tell you about today are faster for the prover even without the small k thing but the small k thing buys it an order of magnitude more on top of that okay so less than so what should I think of as like little n for you um you can think of it as like uh a million-ish

and you can think of uh K as also a million-ish uh whereas these groups have size like two to the two five six which is you know way more than is two to twenty versus two to the two five six yeah other questions okay yeah all right so let's talk about lookup arguments so um yeah I said that these things sort of straddle front ends and back ends and now we're about to see why um so suppose as an example um I think it's easiest to present this notion with an example suppose approver wants to prove that uh you know it said it ran a witness checking procedure uh but it wants to prove that none of the values arising during the execution of

the witness checking procedure were bigger than say two to the 128. say because the checks it's doing um sort of assume that their inputs are no bigger than that um and and so the a cheating prover could try to feed the witness checking procedure like overly big numbers and it would like mess up the checks right like maybe it causes some over uh uncorrected overflow issues or something like that so the approver is going to have to separately prove that none of the uh elements of the witness are too big okay so this is called like a range proof okay um now the traditional way to do this sort of inside a circuit um is to use you know this untrusted advice I had mentioned in response to a question of Joe before uh where the advice would

just be uh sort of the binary decomposition of each number to be range checked so if the prover wants to prove that some number X is between 0 and 2 to 128 it would just provide his untrusted advice like 128 bits and you know claim that uh x equals the appropriate weighted sum of those bits you know that X you know that those bits are X in binary right and the point is like if each of those bits are indeed in zero one they're bits okay then this weighted sum here uh cannot be cannot be outside of the range zero up to 228 minus one right so if the proverb provides these you know 127 128 bits uh you know prove that each of them is in zero one and

proves that x equals this sum here um then it has indeed proved that X is in the appropriate range does that make sense so this is kind of the old way of doing things and it's very expensive um because you know the something your computer could do in like one operation or maybe two if it has 64 bits at 128-bit data types is requiring approver to cryptographically commit to 127 field elements okay now fortunately they're small field elements and as I said with msm-based commitment schemes those commitments are pretty fast to compute but there's still 127 of them okay and there are certain other costs that also kind of grow with 127.

um so this is generally uh we'd like to do better than this if we can questions about this okay so kind of the whole point of this talk is to explain how you can do better than this yeah so here um why can't we just send bi into open do we also want this to be zero knowledge so imagine that uh so if you do care about zero knowledge that would be one reason but it's really a sickness issue so imagine that you had um like every single value arising during the entire execution of the witness checking procedure needs to be range checked okay so it's even you know even sending like

one bit per value is not succinct basically other questions cool yeah so in the in the snark apply to the Circuit side instance the prover is going to commit to you know all of these um bits and that's expensive it's cryptographic operations for like group operations or something for each to tie this all together so those are going to be like some of the XIs uh you're saying in the commitment basically in the in the commitment the I guess X is being used in multiple ways right so like on the last slide when you're talking about the MSM so I'm just trying to connect all the dots okay great so you're so you're committing to XIs there yeah right uh yeah that's a

different XI but yeah so in yeah in um in the snark applied to this like range checking example uh these exponents would be uh these bits like bis yeah and the bits would all be uh committed and you know because fortunately because they're like zeros and ones like you know it's only like the exponentiations are really cheap it's just sort of uh one group operation for each you know because GI to the one is GI and GI to the zero is one or something um but nonetheless that's still 127 group operations and um there are some things that happened in inside these snarks other than the commitments getting computed and so um 127 uh things getting committed is

not not great yeah really connected out so back when you're talking about the overall this sort of IOP approach right send the polynomial commitment and then you get to do like say one evaluation right and then you do this other stuff which is cheap like this is all of this is like the one evaluation you're talking about right this is this is the commitment and then and then later there will be one evaluation like kind of at the end of the snark the verifier is going to say Hey you like committed to like one or a handful of polynomials and you know now I need to evaluate um either all of those polynomials there are ways to do batching so now I need to evaluate some like random linear combination of those polynomials at one point um and that also has a cost and I'll

address that cost shortly I just want to show that confused so you go back forward to where you left off so talk about pivotrades algorithm yeah right the point is this is all about fast evaluation this is all about fast commitments okay okay so yeah polynomial Korean scheme has like two procedures there's you commit and then later the verifiers like I need to evaluate the committed polynomial at a point the short version is the the evaluation proofs um people tend to ignore their cost and they're not totally ignorable I'm going to say more about this later but um because a very nice uh batching procedures and also um because a lot of polynomial commitment schemes actually uh the evaluation procedure is faster than the commitment

um it's it is reasonable in some cases to kind of ignore the cost of computing and evaluation proof in other cases you can't ignore it and we're going to see both situations today that makes sense so here I focused just on the cost of committing um oftentimes that that's the bottleneck you can't always always ignore uh the evaluation proof okay so yeah this is sort of the naive Baseline that we need to be you know if I'm not beating this I'm not telling you anything interesting at all okay um so but look up arguments like their whole reason for existence is to try to do better than this try to do better than bit decompositions okay so um what lookup arguments will let you do is imagine you know we just

were able to somehow initialize like materialize I'll call it a lookup table just like an array of values um that store all the valid values so all the field elements zero up to the 128 minus one and no one can write down a table that big uh but let's just ignore that for a minute okay uh then each range check every time you know the approver needs to prove that this x is in this range is equivalent to uh what's called a look up into the table all right so um let me let me give a little more details um so in this range check example the table again would just be all of the valid range elements the numbers zero up to 228 minus one okay and um the prover will have uh

ultimately uh committed to uh the vector of values that need to be checked so the setting in the lookup argument is the the verify receives a commitment to a vector a and the prover claims that every entry of a resides somewhere in the table so it's in a little more detail uh the prover claims to know an opening of the commitment so that for every element of the vector a that opens the commitment there is some index in the table that equals that element of a so by opening a you literally just mean like a X1 up to xn such that if you plug

that in into the G's then you get back to C exactly okay and then more more conceptually you just think of the commitment as like a box with uh something inside of it and approvers claiming to to know the thing inside of it uh whatever that means um and uh and moreover that you know for that thing that it knows every entry of it lives somewhere in the table does that make sense so it's like in uh you know in the range check example you think of the the snark prover has like committed to like the entire execution trace of like the witness checking procedure applied to some witness uh but separately needs to prove that every element arising in that

Trace isn't isn't too big you know isn't like just cooked up to mess up the witness checking procedures checks and so it would use a lookup argument with this lookup table uh to convince the verifier that questions okay so that this is what are what I call an unindexed lookup arguments um in some applications we uh you need index lookup arguments so this means um rather than just there being like sort of one vector a with every entry of a needing to reside somewhere in the table um every entry a is paired with an index into the table right and the previous uh and the index lookup argument is claiming that for every eye you know uh AI lives in the specific index bi in the

table okay so on index lookup arguments or like you know every element of a lives somewhere in the table and I the verifier don't care where index lookups are like you know uh the elements of a are committed as well as indices and the provers claiming that each entry of a lives in a specific index in the table bisr also committed yeah so um yeah so you know I've drawn them as tuples but you could think of like there's one commitment to the AIS and one commitment to the bis and the provers claiming that this property holds so for every i a i equals the bi table element so it's like a very simple example where it's clear this is what

you want uh jolt so if you just hold your horses sure okay um yeah actually most of the papers seem to consider the undernext case but then the application we considered in this work definitely needs the index case so uh but fortunately there's a simple transformation like kind of if you can solve one you can solve the other so up to this point we're still assuming that both the prover and the verifier have the full lookup table yeah I will say in great detail later uh what the verifier actually needs to kind of know about the table uh we are not going to want the verifier to necessarily have to like write down the whole table other questions

cool so now I'm going to summarize existing lookup arguments and I'll tell you about lasso by the way I'm not going to tell you anything about how lasso works today that's for the talk tomorrow um okay so let's say we want to do M lookups into a table of size n um so there are you know there's now a long line of work on lookups and here are three prominent examples so the paper that introduced the notion of lookup arguments gave a very good lookup argument when the number of lookups is like much bigger than the size of the table okay so like the bad thing about Arya is this like table size Times log and log number of lookups term all right we don't like that log being there for example

okay but if the table size is pretty small like it doesn't really matter because there's already an M anyway okay so actually if if you really do if you have like a really small table and you're doing a ton of lookups into it I actually think Aria is probably still what you want to use today but you really need the number of lookups to be much bigger than the size of the table for that to be best okay uh then you know some later works sort of focused on the case where the number of lookups in the table size were about the same say um they're basically the case where you wouldn't want to use Arya um and so pluck up is a very popular lookup argument where the approver commits to like five times the max of the two you know number of lookups and

table size field elements um and like in every uh existing lookup argument before the work I want to tell you about today like some honest party is always going to have to commit to the table in pre-processing unless you want the verifier to sort of materialize the whole table like you know when it comes time to verify the snark um so in all these lookup arguments this is basically how the table gets specified to the verifier is um it's handed a commitment to the table and you know it better have been an honestly computed commitment or otherwise it's sort of going to bind the prover to the wrong table practical because if it's a lookup table for let's say two to the 128 elements yeah so you can't for giant tables like

that um and I'll say much more about this soon but basically look up arguments uh today or applied to tables typically with like two to the 12th ish entries something like that um and it's uh one reason is because you just can't commit to Giant tables efficiently so this one question would be do you feel like it was already in the air that people really wanted to use big lookup tables and it wasn't detect to do it properly or is even sort of that kind of a new idea to take advantage yeah I think it I think it was in the air also I think the giant lookup tables uh we wind up using in jolts um uh actually turn out to you can kind of reduce the look up into a giant table into several lookups into smaller tables

in which case you kind of could use existing techniques although I think that lasso kind of makes it easier than the existing techniques would be to kind of decompose a look up into a giant table into smaller ones I think the perspective of doing a look one lookup into a giant table is powerful and we'll see why soon so what is the sort of trade-off Point uh with current efficiency techniques of where you use the lookup table versus something naive like bit decomposition um yeah yeah uh it's a great question um so it depends on what kind of um snark you're going to sort of combine the lookup argument with because um you know we're not at the point I'm going to say more about this is what the

lookup Singularity means is it's a notion of like just you only do lookups right you don't do like anything else and we're sort of not at the point I'm not I'm not even sure if that that's achievable um what we do now is like we we turn in jolt and I'll get to Joel soon um almost everything that happens is lookups but there's still a little bit of work done to sort of uh put together the results of the lookups into um like a full snark proof um and uh and so the answer of like when when you should use bit decomposition versus uh a lookup argument depends on uh what snark you're going to use to uh prove everything that happens outside of the lookups okay and some snarks um

uh like bit decomposition uh play not nicely with okay because there there are certain other costs I know this is a rambling answer there's certain other costs to bit decompositions besides just committing to the bits which which some snarks sort of pay a heavy price for and others don't necessarily such as these opening proofs these evaluation proofs for the polynomials some snarks um like only like one really small polynomial needs to be evaluated um and other snarks like a much bigger polynomial needs to be evaluated anyway so uh ruler I guess uh kind of a rough rule would be um you should think of look up arguments as um very good

um amortizers um so bit you know bit decompositions if you're only doing like one lookup you should probably just use a bit decomposition probably right um uh for if you're doing and M different lookups okay uh that then this this can be better um and so what's happening is that for every uh if you ignore the N for every look up here the prover's committing the five field elements okay that's less than like a like 128-bit decomposition on the other hand as we'll see a lot of these are uh like arbitrary field elements they're not bits okay so like five committing to like say five arbitrary field elements can actually be more expensive than committing to 64 bits

but then there are these other costs like opening proofs and stuff that also come in that might be higher if you commit to 64 things instead of five uh anyway so uh if you just sort of ignore those intricacies just compare um like five five M uh you know the five five times Max of M and N to like 64 M or something like that 128n and pick which one is smaller um that's the precise answer could you elaborate so you had an interesting comment about amortization yeah could you elaborate on that sure uh great so if okay let's focus on Arya uh maybe that seems because I've written Aria's like the sum of two different terms okay

so there's always this n log M term okay n is the table size and maybe just ignore the login term okay so if you do a lookup argument into a sizable table you sort of you pay a a a term n okay and if you ignore the login that that term is sort of fixed it doesn't matter how many lookups you do you pay it once it's done okay uh and then you have this m term and what's you think of that as like one field element per lookup okay so if you do a big decomposition it's like you know say it's 128 bit decomposition that's 128 field elements committed per lookup now they're small which makes the faster to commit to but uh 128 field elements committed per lookup here

it's it's just one okay but it still wouldn't make sense to do uh to do it if M was like just one because of the plus n so basically you you pay some factor that depends on the table size you pay that once at that point you've paid it doesn't matter how many lookups you do um and then you get like a better like per lookup cost so that's the perspective you should have for lookup yes yeah so that makes a lot of sense interpreting these Expressions I also want to just think about conceptually should I almost think about the lookup table is basically capturing some pre-processing which are then sort of reusing across like multiple different commitments or is that not uh that that I think that's the right way to think of some lookup arguments and maybe not of others

um and I would I would actually say um because an honest party has to commit to the table in pre-processing for all existing lookup arguments that's a totally fine way to think about all existing lookup arguments but we'll see if you view lasso as really dealing with the table side 228 like no one's processing that table ever so it's probably not quite the right way to think of it um so yeah uh all of these Works um you know they have a table cost uh sorry a cost for the approver that's sort of at least linear in the table size uh there was a really nice line of work starting with caulk which is only a 20 22 paper so it's a it's really recent this whole line of work um that look to push all of the cost proportional to the table size into

pre-processing doesn't get rid of it moves it into pre-processing okay uh Now call can it turns out all of them this actually gets back to a question from before it's very they're tailored to kcg commitments and it seems that they really heavily exploit that Fiat Shamir is not getting used in kcg commitments um so it's it's not clear that you can plug in other commitment schemes into the whole line of work from clock onward uh so as a result they all require a structured reference string of size linear in the table size because that's what's required to commit to a table with kzg um and that's really limiting um in terms of how big the table you can use is um so like even something like two to the 25 size table will be like many

gigabytes sized SRS I think and anyone who wants to act as approver needs to download that structure reference string in order to use this these lookup arguments uh CQ uh short for cache quotients is the latest uh version in this line of work and after the pre-processing uh the CQ prover commits to uh sort of eight eight field elements per lookup like that's really it there's no dependence on the table size anymore um and there is some ffts the approver does um so that's n log M but that's field operations not group you know cryptographic group operations yeah so what are some uses of these sort of arguments other than range proofs like are they much more General can you use

them for looking up advice to a circuit for example yeah I'd say uh they're used quite pervasively uh basically anytime you um it would be like really difficult to turn something into a circuit it's like you know something that doesn't look anything like additional multiplication in a finite field people will think about using these is my impression um yeah and so and and you know you can you typically can always do a bit decomposition and Things become pretty easy to implement in a circuit once uh you you have individual bits to operate on I mean in principle like anything can be done as like ends and ORS right and um bits are just like true and false and um so yeah and I think you know so I people use it for like you know hash

evaluations and doing group operations inside a circuit and stuff just anything that's not nice to directly turn into a finite field Edition multiplication they you might think of using look up arguments um the you know they the whole point is they improve over bit decomposition pretty generically as long as you're doing enough lookups into one table again there's this cost that's sort of linear in the table size um that you can't avoid paying although you know lasso is going to wind up paying a sublinear in the table size fixed cost um yeah for some for some tables cool okay so now I can tell you about the cost of lass sales so um you know sort of a family of lookup arguments I'm

going to start with what I call Basic lasso which kind of the simplest and cleanest and the most directly comparable to existing lookup arguments okay and then um there are two versions um that I call lasso and generalized lasso which apply to gigantic tables say a size like two to 128. now if the tables are that big they need to have some structure to them like other no one can write down like the trivial description of the table which is just listing out all of its elements if it's size to 128 right so um lasso is the reason we have two it's a little annoying but lasso is more efficient than generalized lasso when it applies but it needs a stronger structural property out of the table we call this decomposability and it's this thing I mentioned before of like one lookup into a giant table so being answerable by

doing several lookups into smaller tables um and generalized lasso needs a weaker property than decomposability which I call low degree extension structured and you'll see uh by the time I'm done what that means okay so let me just describe the cost of basic lasso and I'm going to describe the cost for index lookups it just sort of makes the accounting a little easier but it also applies to unindexed lookups um in fact tomorrow I will describe it uh when I tell you the details in the context of index lookups um okay so to do end lookups into a table size and the the basic last approver commits to n plus N Field elements and there's some other stuff but they're low order terms it's like little ovam Little Oven concretely it

will also be sort of a low order cost I mean it really it's not just like slightly less than m n it's significantly less um and moreover all of them are small so every one of them is in the set 0 up to M and I'll say more detail about just how small they are shortly um us compares to like the four you're like you're losing a four from what you're talking about right right right um and I'll uh I'll give comparisons shortly yeah um right and so um also no commitment to the table is needed if the table is you know low degree extension structured and it turns out like there are a lot of tables that are load degree extension structured and I'll give a few examples um also I mean these may be sort of lower this sorting thing is maybe low

order but actually I've been talking to some projects where this really does matter um in all of the prior lookup arguments that I'm aware of the prover would have to sort of take the lookups and sort of sort them or at least group them by what's being looked up and you don't need that in lasso um and also you know we can use any polynomial commitment scheme if you don't use something like kcg we don't need any SRS okay um all right so how small are these M plus 10 field elements so they're all what's multiplicity so they're just sort of counting for each table elements how many times was it accessed how many times was it looked up okay which means like two things so one is like um you know they sum to M right um because M things are accessed in total

basically right so like you know at most a fourth of them can be bigger than four right something like that um and also you know if n is bigger than M then most of them are zero and committing the zeros is actually free in that there's no group operations at all required because like G to the zero is one right um now this is where I'm going to discuss the caveat about um you know uh opening evaluation proofs and how you can't totally ignore them okay so um in the lookup argument one polynomial evaluation proof is needed um and you know this okay for some polynomial commitment schemes the evaluation proof requires like sublinear and N amount of cryptographic

work okay so uh sort of at least asymptotically speaking you can kind of treat it as a the evaluation proof has a lower cost because there's like linear and cryptographic work to commit and only like square root n to open um and there's also like nice amortization where over the course of the lookup argument approver commits to several polynomials and only has to like evaluate one okay um but uh some polynomial commitment schemes actually have like really expensive evaluation proofs and then you can't totally ignore this and I'll discuss that more in the context of experiments uh shortly okay um so when I say that zeros cost nothing like they don't really cost nothing they cost almost nothing in the commitment phase

they do affect like the cost of an evaluation proof it's like uh you know it may be square root of n um cryptographic cost um and linear and then field work or something to produce an evaluation proof depending on the commitment scheme you use again all right so yeah I just uh sort of uh put up an extra term in the cost here uh leveraging the fact that um uh out of the M plus N Field elements if uh you know if if if the end term is is dominant actually like you know uh most are zeros so they're sort of free to commit to and there are some other costs that then grow within but they're sublinear in terms of the amount of cryptographic work done

um so that just makes it a little easier to compare to some of the other um commitment schemes um okay so yeah I'm gonna compare to uh pluck up and CQ because I think lookup is maybe the most popular right now um and then CQ is the best among the recent talk line of work so remember uh the plug approver commits to like five times Max of M and N Field elements um and and three times Max of M and N of them are are like random field elements so they're arbitrary field elements um there's also of course a table commitment even if the table is like structured and so forth um and so uh I'll you will actually see some experimental comparisons here but I mean basically you know we're basic lasso is committing to fewer field elements

and they're smaller okay uh now with CQ remember the prover commits to 8m field elements uh actually one of them will is like a multiplicity I think so seven of them are random seven seven and under the eight number okay um so I think if uh if m is the number of lookups is like much much smaller than the size of the table I think you'd want to you'd want to use CQ right as as long as you can like afford to have the the table committed in pre-processing right because like CQ like pushes all costs that depend on the table size into into pre-processing and so like you don't actually uh in sort of the online phase need this amortization property right it just totally gets rid

of it doesn't really go away it goes into pre-processing the cost that depends on the size of the table um now it is you know what one thing the remark on is like you know 7M arbitrary field elements is is uh you know the same as like committing to something like 70 M bits so actually in some context bit decomposition could well be better than that so it really depends on the context um just how many you know bits would be in a bit decomposition or something like that um okay but like if if m is not like vastly smaller than N I think you would want to use lasso um and I would actually expect it to be like 30X faster so basically there's something like 3x coming from there just being fewer field elements committed uh like you know seven versus two

something like that um and then all of them being small is good for another factor of ten and also the ffts um might might actually be comparable to the cost of committing to very small field elements and so um now I do want to put in this caveat which is uh you know this accounting just sort of didn't count for the time to commit to the lookups like the things being looked up like that's sort of baked into the definition of a lookup argument you can't avoid it right um this is not that like that's literally free it's just it's sort of a fixed cost for any lookup argument so should it be counted should it not be so if you do count it um these numbers don't really change much if the looked up values are small

okay but if you do have a table which like just contains random field elements then you just can't avoid committing to like M random field elements just uh by definition of a lookup argument you have to commit to the lookups right so in that case I think this like you know 10x speed up due to small elements will fall just to like something much less than 10x but there'll still be a nice a nice speed up is my is my guess okay any questions about this so this is not based on this comparison not based on implementation it's based on looking at commitment costs analytically in basic except a mobile K elements everything was Zero what was the K there so so yeah okay so the proverb commits to you know these M plus n elements and they're all

counts they're all um so they just count like for you know this n term is saying like literally for each of the end table elements how many times was it looked up okay now the count sum to M just because they were M lookups right so uh you know you can have at most You Know M over four things larger than four although some are more than m M right which means like if a few of the counts are big sort of just deal with them separately and everything else is small something like that um and of course M just can't get that big uh relative to the size of the whole field because these fields have size like two to the 256 or something okay I'm cognizant of being over time so I will try to move along but there's not there's not too much more I have to say I want to

tell you what jolt is cover some experiments um and a little discussion and that's it okay so um yeah so so lasso and generalized lasso just apply to bigger tables uh they sort of parameterized by an integer C so the protocol designer can choose the C and um it kind of reduces the cost that depends on the table size from table size itself uh to table size of the one over C okay um and that you know there is some some cost where you know uh if you if you set C bigger than one you know no longer is it like you know the the thing in front of the end it no longer is it one but it

goes actually up to 3C um and I I could I can tell if anyone asks later I'll tell you where the three comes from but um yeah what would you you suggest thinking of SIA as canonic like two or something um so in jolt the tables are going to have size like actually uh two of the 140 and so C might be like seven six um let me think if uh yeah I think she'll be like six but uh yeah but everything will be small everything committed will be small right but your point is like this one over C in the exponent is exactly why you can do big tables yes right exactly okay exactly right um

yeah and basic lasso is just general is just lasso with SQL one um okay let me give you an example of this decomposability property that's exploited by by lasso um and again like this it's really not a new property I mean our formal definition of it is but people are doing things like this before um so let's talk about the range check so um what you can have the prover do um to do you know kind of 128 bit range check is have the approver provide as as untrusted advice uh c c limbs limbs is just uh you know digits but for bass bigger than 10. I guess you got 10 fingers and C limbs or something um so each of the limbs will consist of

128 overseed bits right so for example uh you know if you're breaking 100 uh you know a number that's 128 bits into eight limbs each limb would be 16 bits because 16 times 8 is 128 right so the prover you know commits to these limbs um and and just needs to prove that each committed limb is in the appropriate smaller range and that uh you know the thing being range check equals the appropriate weighted sum of the limbs and so we've really you know just focus on the the smaller range checks so we've reduced the range check for giant range into you know like eight range checks for a much smaller range Okay so we've just decomposed one look

up into this giant table into eight lookups in this table size two to the 16. okay um and sort of the whole point of the jolt work is to show uh that this is like a pretty pervasive phenomenon probably more pervasive Than People realize and I'll say more about that shortly okay uh again people were sort of doing stuff like this already I'll also point out like um okay so the in in the lasso protocol uh the only information the verifier needs about the table is to evaluate a certain polynomial associated with the table at a random point and for you know lots of tables it turns out this polynomial can just be evaluated really quickly um by the verifier directly so for this

particular uh small range table this is the polynomial to evaluate it it's a 16 very polynomial that just the evaluation is just like a weighted sum of the inputs okay so that's why no one has to commit to the table the verifier just does this evaluation itself this is the only information the verifier needs to know about the table in lasso um yeah so generalized lasso is like basically lasso but the it doesn't need decomposable tables um it really just needs that this polynomial is efficiently evaluatable and uh that I don't have very specific examples to give you but in in principle that's like a much more general property than

decomposing one you know a look up into the big table and to look up some to smaller tables uh we'll see like these polynomials can be like pretty like for pretty complicated tables these are very simple polynomials so you're saying like one reason that might be easy to evaluate would be because yeah decomposability implies maybe not um but there will be other reasons why but there may be exactly exactly right and I'm still looking for like a really killer example of something that is not decomposable but is lde structure yeah I think we're going to find them at some point though okay um cool uh one downside of generalized lasso is that um about a third ish of the committed field elements are not

small they're like arbitrary field elements um even if all of those um even if the table itself only contains small values so that is the main reason to try to use uh lasso itself and not generalize lasso that's like the main cost of generalized lasso is giving up on all of the field elements being small okay uh so now let me describe jolt so jolt is a new front end for uh virtual machine execution so this is a pretty popular approach to snork design which came up earlier in the talk um where um people basically will Express a program in the Assembly Language of some simple virtual machine whether it's the ethereum virtual machine or like the

risk 5 instruction set which is a popular reduced instruction set from the computer architecture Community or some projects will you know design their own uh simple instruction set um and you know then people will turn the you know program written in the assembly for that virtual machine into a circuit that literally like the circuit itself kind of runs the program for a designated number of steps okay so like every step of the program the circuit sort of figures out what instruction should be executed at that step and then it executes the instruction and just keeps doing this until the time bound has been met okay so what La uh what what jolt does is it uses lasso to replace the second step with a single lookup into a giant

table what that table is it's just the entire evaluation table of the instruction okay so Tim this was the answer to your question from before about why would you want an index lookup here it is so if you want to evaluate a primitive instruction on like two 64-bit inputs X and Y you just do one look up into the table that you know for every possible input X and Y spits out the evaluation of that instruction okay um and then Joel you know the paper is going to work through all of the risk five instructions and show that the resulting table is decomposable and I guess do I have an example no I'll tell you cost and at some point I'll give you one example this is just a so the index here is going to correspond

to what uh to the input to the instruction so you know if if um you know at step you know 1086 of your computer program it's time to uh I don't know compute the bitwise end of X and Y where X and Y are two 64-bit values um the index into the table is X comma y um and the value stored there it yeah okay so yeah uh I try to wrap this up um in uh in jolt for we work through every step of the of the risk five

um instruction set um which is again a sort of a simple but popular instruction set which has you know we didn't pick it out of thin air there are other like very very nice projects targeting it um and for every every one of those instructions or every step of the risk 5 CPU uh the job approver commits to under 50 field elements and all of them are pretty small so um all but seven are are smaller than 2 to the 25 and none are bigger than 2 to the 64. okay and so if you sort of do some crude math sort of translating you know sort of committing to small elements into what it would equate if you were committing to sort of full-size field elements this is sort of like five arbitrary 256-bit field elements getting

committed per step of the CPU okay uh there are a couple caveats that's really that's really just saying like uh uh sorry like uh 43 times you know six times 25 plus 7 times 64 divided by 250. yeah you wind up like fit you know the way you wind up thinking if you do this stuff for long enough is like how many bits are in this field elements like sum up all the bits committed um and yeah uh looking at the sum of the number of it's committed and you know it's much cruder how the algorithms sort of wind up working but that's roughly the yeah okay just a couple caveats um there are a couple of risk five instructions that

we handle via pseudo instructions meaning like if we want to you know there's a instruction for division with remainder and we sort of you know have the prover provide like the quotient and the remainder and we check that you know with an addition and multiplication that those were provided correctly um so that you know each each division with remainder instructions sort of turns into like two or three pseudo instructions something like that there are also some instructions we can actually handle more efficiently than I've listed on the slide so some things are a little more expensive some some things are a little less expensive um so I do want to put these costs in context of other approaches so that's one question about this so I mean because this is obviously kind of a key part of what's driving the performance right so

should I think of this as like once you have this conceptual idea to use these kinds of lookup tables in this way like of course you can map all risk five instructions to tables of that form or is that kind of should I be surprised by that uh there is a bunch of like kind of gross work to be done but you shouldn't be shocked and if you see somebody uh I'll verbally do the examples now since um that means I make sure I don't spend too much time on them so like bitwise end um so you have two field elements you want to look at their representations in binary take the bitwise end of those two representations and you know turn the result back into like a field a field element right um so you can answer a bitwise end on 64 bits two 64-bit inputs by breaking each

input up into like eight chunks of eight bits each doing a bit wise end on each chunk and putting the results together like concatenating them um the other instructions are more complicated but it's the same flavor um So the instructions are just simple enough that you can kind of just break inputs into like their bid representations into chunks operate on each chunk not completely independently as in bitwise end it is really independent but and uh put them together in nice ways just work through it for every one of the instructions other questions yeah so it turns out to be really natural I think in the end so like it's sort of like in hindsight oh like maybe of course this is you know the way things should be done uh I mean I hope

that some people's reactions will I guess we'll see maybe I've been staring at this too long um cool okay yeah so I want to compare this to some other approaches otherwise these are just numbers you know kind of hovering in The Ether um so Planck is a very popular back end for circuit sat um and it commits to 11 field elements per gate of the circuit and I think I think seven of them are arbitrary even if like the gate values themselves are small at least six are arbitrary okay which means you know uh jolt is committing to a you know about equivalent to five arbitrary field elements per step of the CPU this is like turning uh risk five program into a circuit with under one gate per step

and applying plonk to it okay now Planck is not tailored to these sorts of circuits that come from VM abstractions but which have like a ton of structure Planck is sort of like designed to handle arbitrary circuits so this isn't really like a fair comparison but Planck is used today a lot so it's meaningful to say you know this the cost of of jolt is like applying Planck to a circuit with under one gate per step of the risk 5 CPU all right so I'm not you know that natural project to discuss is the other one that's already targeted the risk five instruction set risk zero um now they're targeting uh today right now I believe 32-bit um instructions you know uh I gave you numbers I guess for Joe with 64-bit

instructions uh their costs were probably double if you went up to 64 bits something like that for the prover um our costs would not have if we went down to 32 bits so you know um yeah they're just anyway uh that that complicates the comparison a little bit but um okay I don't Know full details of what risk zero is doing so I try to be conservative here I think it's it's clear that their approver is committing to at least 275 field elements per step of the risk 5 CPU now these field elements are over a pretty small field it's a 31-bit field called the baby bear field so if you do the same kind of crude math I did before it equates to about 35 field elements per CPU step um and yeah I get I like uh risk zero

does not use MSM based commitment scheme so it's like it's very hard to compare you know like Risk zero commits to this many elements you know with this commitment scheme that doesn't do msms to to jolt you know which commits to this many field elements per step which does use msms that we could use we could avoid msms if we wanted to but you know I think MSM is a rear like kind of the good properties of Joel are most evident yep Stark like yeah fry based yeah yeah uses a fry based back ends so they turn risk five into an air and apply Stark to air um yeah so this is really just meant to be very high level and you know I also again I might be missing some costs in in Risk five

um in Risk zero I don't know uh you just you know this is sort of the best I can do as a crude uh sense of how different approaches compare here um and then the other uh comparison point that I think makes sense to discuss um is uh not targeting risk five it's targeting sort of a custom um virtual machine called the Cairo virtual machine from from Stark starkware this was a virtual machine that was designed to be snark friendly so it has just a handful of primitive instructions it has what's called an immutable memory um the instruct you know like the primitive data type is finite field elements so it's all designed to like play nicely with snarks and uh they commit to about 51 field elements per

step of the Cairo CPU at least according to the Cairo white paper um now start work currently works over 251-bit field uh I don't think they have to I think they do this to match the field used by their elliptic curve digital signatures right so they want that I presumably to be really easy to you know quick to prove things about um so they work over a Big Field even though they don't have to for other things um but they you know they can't work over something smaller than 63 three bits because they use 63 you know numbers between 0 and 2 to 63 to represent instructions in the Cairo CPU um so you know today like what's deployed I guess they're committing to about 50 field elements you know full field elements uh per step of the Cairo

CPU but I mean it has to be at least like 13-ish or something just because the fields can't be smaller than about 63 bits okay um all right so I already you know did some more examples of decomposable things uh apologies regarding so over time all right so yeah we uh we wanted to compare uh so we implemented basic lasso okay I think I think lasso is implemented but we only have experimented on basic lasso so far um and this is Sam and Michael uh from a16z I've done amazing work to get this done um we compared to Halo 2 which is a popular and highly engineered code base that implements uh basically the Planck back end

um and it it sort of gives the choice of using the bulletproof polynomial commitment or kzg polynomial commitment um and it has a lookup argument built in which is a variant of lookup it's not literally pluck up but it's it's I'm pretty sure it's inspired by pluck up and I think it's costs are comparable to plug UPS roughly so just as a reminder the plug approver commits to like five times Max M and N Field elements where m is number of lookups and his table size and you know three-fifths of them are like random field elements uh whereas lasso it's it's M plus n and all of them are small okay so um I I so Halo 2 if you want to use kzg uh you use the curve bn254 which is um sort of the the pre-compile in ethereum and with bulletproofs It's a pasta curve and

there's a really really nice implementation of the past occurs uh from the folks at zcash I think so um yeah nice engineering um throughout Halo 2. um the polynomial commitment we used in basic lasso is is something called hyrax so I do want to mention hyrax has larger verifier costs I don't think they're astronomical but they're larger um I think uh this is we used hyrax because it's built into the Spartan Library uh which is uh we built on that code base um I think the verifier costs of lasso will be attractive like when everything is done but I don't want to like hide the fact that especially in these experiments the verifier costs are bigger and my focus is on the prover cost that's really where this shines

also where I think the key kind of scalability bottlenecks are today okay so this is Halo 2 with uh bulletproofs uh versus lasso and you can just focus on this ratio here this is the speed up offered by lasso so um if the number of lookups is much smaller than the table size which is 2 to the 16 in these experiments we're seeing this is now like wall clock time of concrete information yes yeah and I also these are all single threaded time because we're not done paralyzing lasso but there's a lot of parallelization available in lasso um and this is straight just like how many milliseconds did it take for each okay so remember like the cost of uh

pluck up um sort of it's it depends on the max of M and N right so you'll see that the costs like don't really increase until the number of lookups is equal to the table size because it's like table size dominate dominates and then and goes above that and then it's n dominates um so you know the you know the Halo 2 sort of does best when they're the same and in that case we're getting like a 19x speed up uh but elsewhere we're getting more like you know up to 50x or something um okay that's with bulletproofs okay with kzg uh with kzg it's faster and I'll tell you why in a second but you know they're going from a 7x speed up up to maybe 20 20x why is it faster in kzg it's because

bulletproof has really slow evaluation proofs for the prover B um I mean that's basically different so you can't ignore the cost of those evaluation proofs um especially in bulletproofs but again uh in in the context of a larger snark there's a lot of amortization available and uh things like that the last table was also a bit wise and by the way I missed yes yes that's all there was ends so I did uh run not on the same system but just on my laptop just to get a sense of how much slower uh the prover would be in lasso if the table was just filled with random field elements it's about 3x slower which is actually what you would expect roughly if you go through you know uh

the account it's like a third of the committed elements are 10x slower so you expect like a three to four x Slowdown um so we would still get you know uh speed UPS like in sort of every setting over Halo 2 uh but they would be reduced by a factor of like three or four um yeah so I guess that's uh that's most of what I wanted to say I think um you know we're there's a lot of engineering left to be done on basically asset we like just finished the Implement salmon Michael just finished the implementation so um I do anticipate maybe up to a 2X further speed up for the prover and lasso um but yeah I mean high level it's just uh the commitment costs I you know I

believe are the bottleneck um up to these issues about opening proofs as well um and if you commit to smaller and fewer field elements the commitment costs are smaller and these field elements being small really is responsible for like an order magnitude which I think is underappreciated today question back so on your it seemed like the workload you're simulating there is pretty synthetic it's just doing random table lookups have you thought about benchmarking this on some kind of like real proof segment that's of Interest so in uh in jolt the kind of table that will be used is exactly the bitwise end sort of table

um where the you know the big table contains the results of you know 64-bit data type and the little tables are numbers you know uh it's exactly this you know for all of the instructions um and then in terms of the cost of the prover in uh lasso the worst case is basically just Big Field elements um and so random field elements is you know within uh basically the worst case that's what that's how lasso is that a fair comparison yeah so um in in uh so we're comparing to you know Halo 2 which has a variant of pluck up which

despite the name is not Planck but um and three-fifths of the committed field elements there are random no matter what the table has so you're talking about at most a factor of like you know uh 40 difference or something and and I think for you know the the other stuff um it's also I don't know about lookups and some of the other lookup arguments the the stuff that isn't big is multiplicities and some of it it's table values anyway they're also benefiting some from it so like the the bitwise end is is what's considered you know is exactly what comes up in

jolt and like everyone kind of benefits somewhat from it and the others uh that the ones that benefit less from it um like they're they're dominant costs by far are are the random field elements that are there no matter what does that make sense okay yeah I mean I don't know if this is part of Joe's question but you could imagine trying to do like a really an end-to-end comparison where you really start with something written in a high-level language right which then generates whatever pattern of lookups to whatever right there's five operations that happens to generate and do the comparison yeah on that basis too and that I mean and when jolt is built that's exactly what we'll do yeah what I'm hearing you saying is that like actually a lot of the forces that you're talking through that work here you're actually

saying are kind of in a way operation independent like you'd sort of expect these similar factors whatever the workload is that sort of right or yeah I think that is right I think um the stuff the prover commits to uh in in lasso is going to be just determined by what's looked up uh sort of the smaller those values the better for everyone um if they're using MSN I mean maybe one's just very simple version I mean is there is like if you look at the risk five sort of instructions are there certain operations where the speed up is more pronounced oh I see it I see and if so then the question would be like okay okay the programs that people care about which operations are being sort of used the most right yeah great great so um in

in something like jolt actually jolt stands for just one lookup table there's one lookup table um uh with one caveat and so every instruction is almost the same the two caveats are the pseudo instructions thing like doing division by you know having to prove or give a quotient and a remainder and checking them um with a couple so they're you know that turns into like two or three primitive instructions um then the caveat is some instructions we can actually do uh with this much smaller table um so rather than size like two to the 128 we can do size like two to the 33 to 30 to the 60 65. uh it's because those instructions only depend on like X Plus

y um so X Plus y you know rather than having X and Y which is 64 bits each you can operate on X Plus Y which is 65 bits at most um yeah so uh there's not that much uh variation for different uh risk five programs in terms of what jolt would cost for your system right it might be for the ones you're comparing to right there there might be I think that there also won't be so much there um there there's also probably pseudo instructions in other systems um at least handling like Risk five I would I would guess I don't know the details but like I mean I think you're the way to do division is to do like a you know quotient and remainder um also they use different commitment

schemes so there's actually like even less room for there to be variation uh if you use um like these fry like commitment schemes uh like kind of all that matters is like is the stuff being committed in the base field or an extension field and like designs or everything's in the base field and I I don't actually think there there should be too much difference between you know committing to a one and committing to a you know maximal value in the base field or something in that context yeah so you actually uh there there's much less an empirical variation uh that I expect than you would think everything kind of just costs what it costs uh but obviously we'll see for sure when jolt is built so

okay I went so far over so apologies to everyone but uh thanks for being such a great audience yeah yeah [Applause]