Correcting some SNARK misconceptions | Justin Thaler, a16z crypto research

Transcript

a giant table uh sort of being built out of much smaller tables is exactly what's going on um in jolt and you know lasso um from their Viewpoint of calling things tables okay but um uh if you there's another perspective which I actually prefer and I kind of only Ed the lookup table view because the community uh was using it you know before we wrote lasso um the perspective is the following um let's say you have um two uh computer scientists call them bit vectors um and you want to uh compute their bitwise xor so what that means is you know each Vector is a bunch of zeros and ones and you know uh you go you know you look at the first bid of

each of them and you know if they're if they're both one or both zero you spit out zero uh but if one of them wases one and one of the other is zero you spit out one and you want to do that bit by bit um so on on you know modern computers uh the bit vectors have length about 64 um so that means you know uh 64 for 64 bits you're looking at you know two bits and you're saying you know are are they both zero both one or or not okay um and uh this whole decomposability property of the giant table into smaller tables what that uh turns into in the context of this bitwise xer operation is the following um so rather than handling all uh you know 128 bits at once you know 64 bits in in each of the two

vectors instead we can um break each Vector into chunks say 8 bit chunks that's one B chunks and we compute the uh to you know to get the bitwise xor of all 64 bits you can compute the bitwise xor of each 8 bit chunk and just concatenate the result together okay and that's that's the sort of that that that's the decomposability property that lass was exploiting okay that you can take these 2 64-bit vectors break them up into smaller chunks operate on each chunk individually and sort of glue the results together to get the you know result of the the whole operation that's what lasso is exploiting and there were already lasso andol and there were there already snarks today and zkm even that exploited things like that okay but um

because lasso andul use the sun check protocol um the process of doing the lookups into the small tables which is equivalent to operating on each small chunk um of the input to the instruction is faster for the prover and the process of gluing the results together you know the the results for each chunk into into a single result for the whole computation is also much faster um and so you just get better performance for the approver um and uh I think they can handle like more General kinds of gluing together procedures and things like that which we actually do exploit for some of the risk five instructions um and so get I think one of the reasons people have been so slow to recognize the performance benefits of the Su protocol

is like you can build all these things without the sum protocol it's just slower for the prover right so people were already doing similarish things um not with exactly the same Viewpoint um and it's just more expensive for the pro as we're seeing with the release of jolt where there's a lot more optimization still to be done and it's already the fastest CBM to date prior to risk zero and now sp1 and and jolt um um all Z kvms targeted um I cooked up instruction sets so that is snark designers uh designed their own simple CPUs where they chose the Primitive instructions to be ostensibly friendly to the snark proving Machinery

okay now in my view this has multiple downsides like this is just absolutely the wrong decision okay uh for so here are the reasons so um I think jolt uh actually shows that this decision is bad for performance so they they made this decision because they thought it would lead to faster provs uh because you know they chose the instructions to be you know friendly to the proof Machinery um you know jolt supports risk five and even more generally like any instruction set where the pr of instructions have this natural decomposability or like chunk ability property we discussed before and like I think like you know most natural instruction sets uh you know that chunk ability property seems

to be roughly like what what makes instructions good for real machines to run so you know um that that broadly speaking tells you that instructions good for real machines should also be good for snarks right and so people have been designing quote snark friendly instruction sets uh they've really been designing them to be friendly to today's like limited snarks um they're artificial limitations they're not actual limitations so they did this for performance motivations I think it's actually bad for performance but on top of that it's also for the developer experience and for auditability and usability and all this stuff because you know if you use an existing instruction set like Risk 5 we you know the computer architecture Community has created all

sorts of tooling around that instruction set compilers from high level languages you know down to risk 5 you know hopefully they brought you know some formal verification tooling to bear on those compilers if you have a new instruction set like not only are you going to have to do a lot of compiler work uh just to you know have your compiler you know spit out decently performative assembly code for your you know new custom instruction set but um you know you're going to need new tooling to uh make sure that compiler is correct because any bug in the compiler is going to lead to potentially catastrophic vulnerabilities you know in the you know settings where the proof system is applied and all sorts of things so I think it's it's doubly bad or triply bad you know for developer

experience you know for for you know uh verification you know uh and safety and audit ability and then finally it's it's actually bad for performance too um so you know people were doing this for performance reasons I don't even think it helps performance the current implementation uses uh a polinomial commitment scheme you know that is it's the only cryptographic part of the protocol really um uh based on what's called elliptic curve cryptography and um elliptic curves uh need to work over what people call big fields this just means that the numbers arising in the protocol are really big um so writing down each of

those numbers takes up to say 256 bits um so it's just like you know each number Rising is like a really really big number it takes a lot of you know bits a lot of zeros and ones to even you know uh tell the the protocol what number we're we're talking about here and so operating on those numbers you know people think it's it's slow um and uh protocols that like snarks that do not use elliptic curve based commitment schemes um they tend to use uh the cryptography they tend to use instead is is is Hash functions only um they're sort of free to work over smaller Fields keep all the numbers arising in the protocol much smaller and it's you know uh for each of those numbers it's like much faster to add or multiply two small numbers than than two big numbers um and

so it sounds very plausible right like keep the numbers small and everything should be faster okay um and so there there's this very widespread view that um you know you would for performance reasons you should avoid elliptic curve based commitment schemes um so this view is largely wrong I would say to the extent that it's right it's right for different reasons um than people think it's think it's right um and jolt demonstrates that because it's the fastest zkm to date and it uses the curve-based commitment scheme today now I I do think we'll we'll get an even faster version of jolt by moving away from curve-based commitment schemes but the commitment schemes we're going to move to different than the than the ones people use today um so you know I I don't think you can take the commitment

schemes people use today and and make jolt any faster than it is today um and so what one thing people are missing here um is that uh is the following so um again the the deployed snarks today that people kind of draw all of their conclusions about performance from they don't use the Su check protocol and for performance you should use the Su protocol and uh the way I think of it uh of snark performance is the following in snarks theover commits to a bunch of data um and then proves that the committed data is well formed okay so um that means that you know the the the data um satisfies all the properties it's supposed to satisfy if the Prov is

honest okay and so the the situation is that the more data you have to commit to the slower it is to compute the commitment to that data and also the slower it is to prove that the data is well formed okay the key power of the sum Che protocol is that it reduces the amount of data that the prer commits to okay which which has two benefits one is the Computing the commitment is faster and the other is um proving that the committed data is well formed as faster okay now all of the commitment schemes people that are most popular today and the two most popular ones are called um fry and kzg kzg uses elliptic curves and so people think fry is really fast because it doesn't use elliptic curves um they are targeted at uh you know in the guts they're targeted at what are

called univariates Pol but the sunre protocol needs to use multivari pols okay what that means is the uh commitment schemes people use today um don't even directly work with uh you know the snarks people should be using to have a Fast Pro um and the reason the pro is faster with the subject protocol is because it commits to less data okay so to summarize um today we use a curve based snark uh sorry a curve-based commitment scheme uh in jolt um it is none even even though it uses curves and works over this very big field very big numbers arise in the protocol it's still faster than all the other ZK VMS out there the reason being that the prover commits to much less

data because jolt uses a sunri protocol and um the other snarks don't okay um when if we if we do go to switch jolt as we plan to to a non-elliptic curve based commitment scheme we will not want to use the commitment schemes people use today because jolt uses multivariant rather than univariate polinomial so we'll want to use a commitment scheme that is tailored to multivariate polinomial and moreover um has I I I think the the Univar commitment schemes people use today generally are are worse for the prover um you know it's slower to commit to data for the prover um than than the ones we we plan to use um so yeah okay so hopefully that that makes some sense

we have some explanation for uh uh some of what's leading to this confusion