SNARK Design, Part I, with Justin Thaler | a16z crypto research talks

Transcript

morning everyone uh welcome to uh this morning's a16z um crypto research seminar very happy to introduce justin thaler who um as you know just showed up this week as a faculty fellow he'll be with us for the rest of the summer which is very exciting um justin's a professor at georgetown and today he's going to give the first of his two-part tutorial series uh on snarks just a couple reminders um so the second part will be tuesday at the same time at 11am and actually in the meantime later today at 2pm we'll have scott commoners as well as a seminar okay so justin all yours thanks a lot um yes i'm going to tell you a little bit about snark design well what what snarks even are

how they're built and how they're used in roll-up projects which are pretty exciting right now as they're being built for blockchain scalability today will be not super technical tuesday tim said i could just go crazy so okay so what is a snark um so in a snark some untrusted prover claims to know some witness satisfying some property um so a couple examples that come up a lot in cryptography so the approver might claim to know a pre-image w of some designated output of a hash function right so here the witness would be a w such that h of w equals y where sort of the prover and verifier

have agreed in advance on the hash function h and the output y and the approver is claiming to know w and the verifier doesn't know w and wants to make sure the approver does um another example which is related but not quite the same is you know the witness might be a private key corresponding to some known public key for some crypto system okay so um there's always a trivial proof for the prover's claim which is to just send the witness w that it claims to know to the verifier then the verifier can just check that w satisfies the claim property for example in the in the first bullet point here the verifier could just evaluate the hash function at w and confirm it equals y okay so what a snark does is achieve the

same goal but with hopefully much better cost for the verifier so this is a funny acronym it stands for succinct non-interactive argument of knowledge so let me tell you what each of these letters mean so succinct means that the snark proof must be shorter than the witness w right so there's like a trivial proof it's just the witness um so anything that's shorter than that i'm gonna cost succinct in the research literature some authors will reserve it to mean like logarithmic and w or even smaller than that i just think anything non-trivial should be considered succinct ideally checking the proof should be faster than the runtime of the verifier in the trivial proof system

that's not actually captured by a letter in the word in the acronym snark so if i have to clarify that issue we'll call it a work saving snark like the verifier saving work compared to the trivial proof system could be you have a short proof that takes a lot of time to check right but that wouldn't be work saving okay the other letters so non-interactive means the proof is static it can be posted on a website or sent an email um and then argument of knowledge just basically means if the prover can't break some cryptosystem then it really must know w um in order if it's going to produce a convincing proof is there like some motion to sing this in short relative to the size of this statement too because it seems like for

the hash tree image like the stark is never going to be um sorry that's shorter than th okay so yeah there's like an asymptotic question versus a concrete question um you know there are snarks with um like non-negligible sound sorry with nick yeah non-negligible sound this error that might be shorter than 80 bits in principle anyway i think that that's possible

uh anyway in practice you're not going to get a snark proof that's smaller than several hundred bids so if your witness is that short um you really you're in practice you're not going to be more succinct than that um but there are statements that could have larger witnesses um the approver is proving to know many witnesses uh you know or sorry many pre-images or something um yeah so they're they're in practice there is a limit to the sickness the most succinct snarks it's uh three cryptographic group elements so you're talking what is that like 600 800 bits i forget and so just for a green issue if you're thinking about shorter and faster just like logarithmic

length yeah so um there for we'll get into issues like transparency not transparent snarks um there are non-transparent snarks where short really means like three group elements in cryptographic group that's like 600 800 bits i think um if you want a transparent snark you're probably not going to do better these days than logarithmic in the statement size or logarithmic something okay um and then uh yes and i'll say more about what fast means like you can hope for a few milliseconds for these non-transparent things when the proofs

are really short and tens or hundreds of milliseconds for the transparent things i think for the verification yeah okay and something i just mentioned uh the roll-up application does not require zero knowledge if you're not if you don't care about privacy you just care about blockchain scarability you don't need zero knowledge so i will not call them zk roll ups i think it's a bit of a misnomer um i will call them validity roll ups today if i have to clarify what kind of roll up i mean okay so here's the plan for today um first i'm going to tell you about power snarks designed um then i will give you sort of a taxonomy of existing snark constructions and the pros and cons and

sort of that'll give you really boils down to right now like four classes of snarks out there today that people are using or might use soon um so kind of you can fit it all in one slide and understand how they relate to each other and after that we'll turn to rollups i'll tell you what is a roll-up how they're using snarks and there won't be time today i don't think but if there is more time i'll start the slightly more technical overview so if parts one and two do feel a little bit technical or just dry because you don't care about cryptography just come back for part three you won't need to know parts one and two for for part three so how are snarks designed at a high level most snarks work via a two-step paradigm

so ideally you would start with something like a computer program written in a high-level language and that computer program is just going to take the witness that the approver claims to know as input and check that the witness satisfies the property claimed by the approver so in like this hash pre-image example from earlier where the approver claims to know a pre-image under cryptographic hash of some hash output the program would just evaluate the hash on the witness and check if it equals the claim value so like applying like a snark directly to a computer program like conceptually like we don't can't really be done so the first step of this two-step process is to transform that computer program into an equivalent model that is

amenable to probabilistic proof systems and typically this is some kind of circuit satisfiability instance or some kind of generalization of this some people like something called r1cs it's a generalization of circuit satisfiability you don't have to worry about the details there's a movement now to go sort of beyond even more intricate things even beyond r1cs but this this transformation from the program to something like a circuit is is uh that's called the front end of the system and then you would apply a snark for circuit satisfiability to the circuit that's called the back end so all of these like snark names out there in the literature which maybe you've encountered some of them before they refer to the back end the probabilistic proof system where the approver is now sort of claiming to know a satisfying assignment

to a circuit instead of like i'll witness you know that a pre-image of a hash value or something and they're equivalent claims right the front end is ensuring that the circuit sat instance is equivalent to you know the original computer program essentially um it's just circuits are kind of like a lower level language if you will than c or java kind of does that make sense one question so all right so in step one you talk about uh turning into an equivalent model of manhole to probabilistic checking and so i'm wondering if you can say something about like why right and you never talked about problems with chatting before you said

the goal is just to sing this sorry i suspect what's going on is sustainness will come there'll be a particular way that you the succinct proofs will mean something like a bunch of probabilistic checks and that's why you wrote that stuff yeah that's right that's right so what's happening in these proof systems and these snarks is um you conceptually that the verifier is sort of randomly challenging the prover um but then the randomness and the any interaction um is is completely pulled out of the protocol using cryptography and kind of replaced with sort of the keys of a crypto the randomness kind of replaced with the keys of cryptosystem if you will and in that way you wind up with the static proof where the verifier never

has to send a challenge to the approver or anything um so yeah this uh in principle you could imagine any number of approaches to what a system group might represent but like the dominant paradigm is what it represents is the results of a bunch of random challenges given that that's the dominant approach we shouldn't be surprised to see that step one means you need to basically re-prepare the same program in a way that you check through challenges as exactly yeah you said everything much better than i did so i won't try to repeat it yeah cool i'd rather just like concentrate think about the difficulty of step one for step two is like reducing every like general program to like this circuit representation like what's the bbc converted to or like how's that

so um easy and hard might not be the right wording it's uh the question is also the overheads like you know if the program runs for 100 steps but the circuit has a billion gates like that's not great um but also if the circuit has a billion gates and sort of the provers run time is you know equivalent to evaluating a circuit with you know 100 trillion gates that's also not so good so there's going to be overhead in both steps you know some computer programs are much more amenable to being turned into small circuits than others um you know asymptotically speaking we sort of have both steps close to the best we can hope for which is you know

up to like log factors in either um step we kind of you know can't hope to do any better but concretely those log factors matter and the constants matter and everything in practice these can be quite nasty um yeah um but no the the infrastructure itself kind of building it and even understanding it um maybe that's what you mean by difficulty can be quite challenging like you know if you if you don't care about really squeezing as much overhead out as you possibly can making these as performative as possible there are fairly straightforward ways to kind of do both steps i mean even even the simplest things for step two use some of the most celebrated ideas in theory of computer science but if you if

you really want these things to perform everything is is kind of challenging to understand the details of and to make sure it's bug-free and all of that they just get complicated does that answer the question so there's another way so basically step one it should be intuitive that like yes we should be able to do something like that that's kind of conceptually i want to say straight forward but you know we're used to kind of different levels of computation stimulating each other where step two is not clear up or that should be possible correct correct yeah and i would say to unpack step one just a little bit um you know there are the the world's kind of dumbest uh program to circuit transformations um

would yield it would it wouldn't turn into a how do i want to say that yeah like cook's theorem like your laptop is is really built out of a circuit right um but there's so there's a question of is it circuit satisfiability or circuit evaluation and you run into this issue where the approver is claiming to know a witness the verifier doesn't know so there's kind of non-determinism already built into the problem itself um but the the really efficient transformations from programs to circuits they will add more they will like extend the witness with advice inputs that help keep the circuit small um this is actually you know i have a

sort of book and um i have a reading group and this is one of the concepts that's sort of hardest to describe verbally is like the circuit satisfiability instance the witness to the circuit um is actually the witness in the prover's head with extra stuff in it to help the compilation from programs to circuits so um yeah you're you know snark programming is something like the practitioners refer to and they're talking about how you put in these extra advice inputs to the circuit to keep the circuit small and yeah so even even like relatively straightforward things um here are going to use those advice inputs and hence it's a different way of thinking than cook's theorem might be say a little bit so i hope that color is a little helpful

um most of this talk is on back ends but i will talk about front ends because in the roll-up context you know the overheads at both steps are really important pictorially though you know here's the picture is a computer program gets turned into some kind of circuit stat instance and then the proven verifier you know they both sort of know the circuit somehow and they apply a snark uh for the preview to establish it knows a satisfying assignment to this circuit uh the last thing i'll say is um these front and the front ends that people are using that a lot a lot of you know the front ends um the idea that they would start with like a c or java program is purely aspirational and people aren't really doing them in practice many people are writing in very low level languages such as like bellman and

uh what else do they use circom they're almost just writing out the circuit gate by gate okay and then other approaches will have you know something slightly higher level than that but it's still like an assembly-like language and so you know obtaining front-ends that really you know would take an arbitrary c program and spit out some circuits that instance that's not just horrible is really not um it's still an open problem i would say so just some extra color there about where we are and and yeah what the programmers are really going to be writing if they want to use these snarks okay so with all that said uh yeah my main focus and my main expertise really is on the back ends um so our back end

goals are we want a snark for circuit satisfiability where the prover is not much slower than just what it would take to evaluate the circuit gate by gate on the witness like with no guarantee of correctness so that's sort of the best you can hope for it's like proverbs at least convinced himself that the witness satisfies the circuit right so we want the proof to be as small as possible so yeah the smallest uh but non-transparent snarks will be a few hundred bytes or it turns out if you if you want a sort of a a nice version of non-transparency there'll be a few half a kilobyte to a few kilobytes actually even even the transparent ones can we can get down to a few kilobytes and we want the verifier to be fast as possible again from a few milliseconds is sort of the fastest we have now to

maybe 10 times that or something there are other properties we would want beyond just fast prover and fast verifier so now we get to yeah i've been saying this word transparent i haven't told you what that means and i will say in just a second the other thing we would ideally like is for the snark to be uh post quantum secure meaning um if there's the prover has a quantum computer and is trying to find convincing proofs of false statements it still can't do it okay so what does transparency mean so in a non-transparent snark uh the the prover will have to know what's called a structured reference stream so this is a very long string they'll call it a proving key in practice

typically it's as big as the circuit so it's big and there'll be a trap door such that if the prover knew the trapdoor it could easily find convincing proofs of false statements okay um so like to generate the srs like kind of someone will have to know the trapdoor srs is a structured reference stream and you have to sort of trust that party to then forget the toxic waste you know dispose of the toxic waste so what people do now there's been a lot of really nice work to sort of minimize the trust assumption um people will run like a giant secure multi-party computation protocol hundreds of participants and unless they're all getting together and colluding no one

knows the toxic waste so kind of as a trust assumption it's fairly minimal now but as a headache and something you don't want to have to do over and over again it's still you know it's a giant pain right um so i'll say more about how various snarks differ in terms of the kind of trusted setup they require but yeah if snark is transparent it means you just don't have to worry about that at all there is no trusted setup there's no trapdoor that someone might know to and could forge proofs of false statements on if they knew it so sometimes i hear about these distinctions between right setups that are circuit specific versus that's exactly what i was getting into that i'll get into that more later

yeah so but the point yeah but i can say now like the um you don't want to have to run a different trusted setup for every every time you tweak your circuit or you know ideally you'd like you know 200 people get together run the trusted setup and you know forever in the future anyone doesn't matter what circuit they care about they can use the same srs as long as the circuit isn't too big and that's kind of what people are doing today you know like zcash and others ran some of these trusted setups a while back and now other projects get to use those same strings as long as they believe that someone in that ceremony from long ago people called these ceremonies um was honest and didn't collude with every other person in the ceremony i see there's something in the

chat should i pull that that up okay that's simple oh okay good thank you someone like the definition of a snark so okay okay actually one other question so i want to be helpful to we keep talking about these circuits in the abstract which in some sense we're all used to but looking ahead toward roll-ups especially sort of discarding the privacy aspect of what there's a canonical circuit let's say for like you know you know literally roll-ups built on ethereum trying to think of it as taking it as input like state route and a bunch of vertical proofs and a transaction and then sort of also then the alleged consequent state route and i'm just checking that that's legit that's

exactly it yeah yeah and i'll say more about that later but and and then for the uh the simpler example of just a hash pre-image right the circuit would literally just like evaluate sha-3 on the input that's it i've thought about like the transparency issue and i guess like how much do you think it's a real issue in practice with all the like multi-party setups and stuff versus like a branding issue in the cryptocurrency space yeah um i think my personal feeling right now which sort of evolves over time and probably will continue to is that the biggest downside of the trusted setup is it limits the size

of the circuit you can deal with and if we you know ever want to apply these snarks and in blockchain applications the statements being proven tend to be very simple in like a cosmic sense like you could imagine using snarks in other contexts where the statements are vastly more complicated um circuits would have to have trillions or more of gates not going around trusted setup for that um and you know there are techniques you can use to try to mitigate this like recursive composition which i'll say a little bit about um but that's that's what i feel um i i i'll say more about um where trusted setup has been like a thorn in people's sides if i have time later in the talk i'm not so worried about the trust

assumption i think if two other people get together um that they're not all employed by the same person or something that they're probably not um colluding um last thing i'll say um you know there there have been bugs in private in z like z cash the z cash bug was they included extra stuff in the srs that shouldn't have been there um and that would let people potentially create zcash out of thin air sort of uh something like that so just maybe that means that the complicated nature of you know these snarks with an srs i don't want to draw too strong conclusion from that but you know it was it was an srs issue that led to that bug so just depends on dots there you said

your main concern about trusted setups is limiting the circuit ties you can handle so is that because you know you said that the reference string needs to be basically order size of the circuit and then the question is the point is just like people actually carrying out the npc just realistically it was only so long yeah yeah exactly and um it's got to be distributed to anyone in the world who wants to operate as the prover which in the blockchain setting could potentially be anyone in the world yeah so it's just expensive to generate and distribute and if it's trillions of gates i mean that that thing has to be you know a trillion cryptographic group elements we could distribute that to everyone in the world

that doesn't sound like it it'll work to me um the verifier of course doesn't have to know the whole srs it only has to know like a couple of few group elements or something um but yeah if you want unless you want the approver to have to have a massive memory machine or something it's not not gonna be nice and every single person in the npc to have the same memory that's my take it could continue to evolve so does that mean so like for the surgery we just discussed about validity of sort of you know a state transition in ethereum it almost feels like you're saying like it's it's sort of inconceivable you'd have a non-transparent like then you'd have

something with a trusted setup that could handle that circuit is that right oh yeah i mean well people are running roll-ups now and the bit the reason circuits can get big there is because they want to handle a batch of huge number transactions and so the circuit's not just doing one state transition plus merkle authentication pass for like any piece of data access but rather you know hundreds of thousands or something like that more questions okay um so here we get to sort of the more technical part of today so if you want to zone out it's really not going to matter but maybe maybe you're interested so here's kind of the main paradigm for developing a snark for circuit satisfiability um this

in turn this has three steps sort of in and of itself so first you designed something called a polynomial iop i'll say in a moment what that is um then you combine that with a cryptographic primitive called a polynomial commitment scheme say shortly what that is um and the combination of the two will give you a succinct argument but it'll be interactive and then you can pull the interaction away and just be left with a static proof by applying something called the fiat mirror transformation the details of which don't really matter for this talk so let me tell you um what is a polynomial iop but first uh let me yeah i'll clarify the statement that all snarks are designed in this three-step paradigm so that is almost

true there's just like one exception which uh happens to apply to some of the first snarks that were deployed in practice especially in zcash was maybe the main uh initial deployment so these snarks are based on something called a linear pcp which uh while the letters are different is actually fairly close to a polynomial iop and in fact um if you if you look at the crypto that's used to turn the linear pcp into a snark in in this class of snarks it looks very similar to a certain popular polynomial scheme so i really don't feel like i'm lying to you very much when i if i just kind of hand wave a bit and say all snarks are designed in this three-step paradigm it's a slight lie but not a major lie okay um and in particular these snarks

um that went into the initial version of zcash and became very popular and still are they are they require a circuit specific trusted setup so if you're not happy with that then you really have no choice but to use this three-step paradigm so i like this paradigm because you can sort of get a unified view of every snark that's out there and given how many snarks are out there that that seems like a useful view to have so okay so let me say a little more about what is this weird thing called a polynomial iop i'm actually only going to describe sort of a special case of that it just makes a little easier to present so imagine um you have a proven verifier and they're willing to interact with each other which means like the approver can send a message to the verifier and the verifier

will respond with the random challenge for the approver who will respond with some response and the verifier would send another challenge and get a response and at the end of the interaction the verifier is going to like accept the provers claims as valid or reject them as involved um so polynomial p is just like that except the first message in the protocol specifies a polynomial and i really mean like in many cases it's a univariate polynomial so like a plus b x plus c x squared plus d x cubed and polynomial except the polynomial might be really big might be as big as the circuit that the prover's making a claim about so you don't want the prover to actually have to

truly send like all the coefficients the polynomial of the verifier because that'd be a huge message as big as it's not succinct at that point the protocol um and you certainly don't want the verifier to have to read like all the coefficients of the polynomial because then it won't be work saving for the verifier so instead we're going to ensure we're going to tell the verifier look like we're just not the approver is going to kind of send you this polynomial but you're not going to be allowed to learn the whole polynomial all you're going to be allowed to do is like evaluate the polynomial at one point okay um so that's what a polynomial iop is is you sort of have this initial message that's special so it's like it's like some giant polynomial and because it's

special the verifier doesn't learn the whole polynomial it's only allowed to evaluate the polynomial at a single point but then like the rest of the protocol is like the interactive proof i just described where you know whatever message the verify the approver sends a verifier the verifier is going to read the whole thing respond the proof is going to send the message and verify reads the whole thing so it's just it's an interactive proof but where the first message is this weird giant polynomial that the verifier only gets to evaluate at one point does that make sense any questions about it so in the real world right we don't have a way for the prover to like send a giant polynomial to the verifier and the verifier to evaluate it at one point without like reading the whole

thing right so that's where cryptography comes in so polynomial commitment scheme is just sort of exactly what you want to implement polynomial iop without the prover like literally sending the whole polynomial to the verifier so at a high level it lets the prover bind itself to the giant polynomial by sending just a really short commitment typically this will either be what's called a merkle hash it's just one cryptographic hash value a couple hundred bytes or something more it will be um something like a pederson commitment uh that's just a single element of a cryptographic group if you don't know what that means it doesn't matter um the point is it's just a really small message from the

approver to the verifier the verifier can read that tiny message in full and sort of once the verifier knows this commitment you think of the prover as sort of being stuck with whatever polynomial it sort of had in its head you kind of think of that polygon as being like shoved inside the commitment and a lot the commitment is locked and the prover can no longer alter the polynomial once he sends this locked box to the verifier okay so then later when the verifier chooses the input x that it wants the to know h of x you know the polynomial committed polynomial evaluated at x the polynomial commitment scheme has to come with a manner in which the approver can provide the evaluation as well as a proof that the evaluation is consistent with the committed

polynomial and this is just exactly what you want to sort of implement the polynomial iop without the prover like literally sending the polynomial in folder the verifier so the way you described it the verifier could in principle choose their x as a function of the commitment they see from the proverb correct i assume that whenever you do this if he's just using x randomly independent of the actual commitment is that right yeah so in the end x will just be random and the variable if you don't care about zero knowledge like none of the verifier has no reason to try to read anything into the commitment

like the the protocol the proof systems will be sound if x is chosen at random the verifier just wants soundness means um for anyone who hasn't heard of this it just means it's it's a security it means that um if the approver is making a false claim the proofer can't find a proof that convinces the verifier the claim is in fact correct so the verifier just cares about soundness so let's make sure the proof is not lying and to guarantee that it's going to be enough for x to just be random if you cared about zero knowledge you're certainly going to have to worry about whether this commitment reveals any information about the witness and in fact it might if you're not careful but we won't care about dear knowledge today other questions

okay um so now that you know what a polynomial iop is and a polynomial commitment i can give you the taxonomy of snarks essentially there are a bunch of different polynomial rpgs out there a bunch of different polynomial commitments and you can just mix and match the two with some caveats but um most polynomial iops will sort of combine with most polynomial commitments and any combination of the two gives you a snark with sort of a different cost profile so costs are sort of inherited both from the polynomial iop and the polynomial commitment one thing i'll mention is these properties that are important in practice whether uh for you know uh practical reasons or or

branding um you know for both transparency and post quantum security they're determined essentially entirely by the polynomial commitment schemes so any polynomial iop could be yield a transparent and plausibly post-quantum snark if combined with a transparent and plausibly post-quantum polynomial commitment you know up to some subtleties that's really not worth getting into certainly not today of you know um details of quantum security proofs but if we're just talking about plausible post-quantum security we we really don't even have to worry about those subtleties so yeah um transparency and post-quantum security it's all coming from the polynomial

commitment not from the polynomial iop yeah um so the reason you would like mix and match is that the iops are doing some operation with the the commitment and then based on their you know runtime of whatever the iop is and then it's making the black box call called this thing that has a tone right and so that's why it may make sense to mix and match rather than just yeah yeah so um basically the polynomial iops um come with a bunch of costs of their own right so you know the the approver is going to um you know obviously uh even ignoring the

approver will have to use a polynomial commitment scheme to commit to some polynomial and later like proven evaluation of it like there's no avoiding that right but on top of that the prover is going to have to you know compute the polynomial that needs to be committed and then send other messages to the verifier in the protocol so sort of outside of the polynomial commitment there's prover time there's communicative proof length you know messages the prover sent to the verifier which have to be ultimately in the snark proof there's the verifier time to check those messages um so the total cost of the final snark is like the sum of sort of the cost of the polynomial iop and the cost of the platinum commitment so if your polynomial iop has like biggish proofs there's not much point to using a polynomial commitment

with really small proofs if it has you know worse costs on other axes that's kind of the reason for that okay can i rephrase my question so the all of these things you mean are just songs they don't interact in a funky way no um yeah i mean there's um other than subtleties about how some polynomial iops can't quite use some polynomial commitments and that just boils down to you know the the prover in the in the polynomial ilp sort of wants to represent the polynomial via a certain set of coefficients and the polynomial commitments might or might not work with those kinds of coefficients and that's like way in the weeds we don't have to get into that but like for the most part if for some reason i decide all i care about is

they're the best iop and there's the best yeah but then uh the the desire for transparency and post-quantum security can then you know change which one you have to use yeah other questions okay so at a high level there are kind of three classes of polynomial iops um the the details i'll maybe say something about on tuesday but today it's not really going to matter it's just sort of you can design a polynomial iop sort of based on something called interactive proof something called multi-proven or active producers and something that i call them constant round polynomial iops and i've roughly listed them just in order of increasing prover costs from top to

bottom and decreasing verifier costs so it sort of makes sense that you know prover costs and verify fire costs are in tension because if you could kind of if they weren't then there'd just be something to rule them all there's something with the best proof of the best verifier and why everyone would just use that so it tends to be you know stuffed with the fastest prover has slightly bigger proofs and somewhat slower verifier and stuff with the fastest verifier has slower is there a sense that that tension is fundamental or just sort of an artifact of the currently wait wait for two slides okay and then there are four classes of polynomial commitment schemes um i'm going to ignore the last one because um there it's not practical

i thought um yeah so let me just focus on the top three um so the first one um is the only one that's not transparent so it has uh this this is basically where um uh trusted setups come from in snarks um and the most popular variant here is uh due to kzg everyone calls them kcg commitments kate at all um and so i i've highlighted it in green um so for each category i've highlighted in green um the commitment scheme that certain right now is sort of the most popular or widely known and in each case uh they they have the shortest proofs and so i i think what what's happened the reason the ones in green are so

popular is in the blockchain settings these proofs get stored on chain and they get they get verified on change so people are sort of moving to the extreme of you know good verification costs so the ones in green in each category are the ones with the best verifier cost so there's another category which is transparent but it's not post quantum because it's based on the hardness of discrete log which is a problem quantum computers can solve efficiently um so the most popular one here is probably bulletproofs maybe some of you have heard of it so basically kzg like evaluation proofs are constant size that's like three group elements or some not three anyway some constant number group elements um bulletproof is log log number group elements

and then the last category um is both transparent and plausibly post-quantum um and the most popular one here is fry um fast read solemnia and interactive oracle proof what that stands for um and the proof length there is like log squared times the security parameter or something like that so um i've listed the three categories also in in sort of this time in increasing order of proof length so constant size evaluation proofs log size poly log um so this is like is that blocking what the like iop sends to the equipment

scheme is um okay so in most snarks um the polynomial committed to is like as big as the circuit and possibly even bigger by a constant factor and also some of them you're committing to multiple polynomials the proof being multiple polynomials that are as big as the circuit um there's only one category of snarks and this gets into how there are these you know trade-offs between proven time and verifier time interactive proofs can make the committed polynomial only as big as the witness to the circuit um and not as big as the full circuit but to support general trans like efficient transformations from computer programs to circuits you know the the witness will have to have these extra

advice inputs and in general there might be a ton of advice inputs so you know you sort of like that that difference between circuit size and witness size sort of in general is is only a constant factor anyway but there might be some settings where you don't actually need many advice inputs to have a small circuit and then these interactive proof things will start to look really nice for the prover because it's only committing to a tiny polynomial and that's why these things are so hard to compare to each other because you get into you know interactions between the front end and the back end and is the witness big or is it small you know did that answer the question for post quantum secure the all that means is that once quantum

computers exist i should no longer use something that's not post quantum secure it doesn't mean that once quantum computers exist there's something insecure about things that already happen um that's right so basically to a quantum computer could find a convincing proof of a false statement um but if you're confident no one had that quantum computer when the proof was generated you have to worry about it another thing i'll say is if you do care about zero knowledge for all these snarks it's the soundness that might be broken by quantum computer zero knowledge is perfect so the quantum computer will not let you violate the privacy of someone you know 50 years from now or something so that's nice is that always true uh essentially

um basically you can in in theory like asymptotically you can kind of choose do you want perfect zero knowledge and no i'm going to get this wrong versus sickness you're always going to need computational soundness well anyway um yeah let's just leave it as like every every snark in existence the way they're made zero knowledge makes it perfectly zero knowledge i mean so fry the way you discuss it it's almost like the only reason you would do that is if you wanted if you really cared about post quantum or is there a different reason you might um so when yeah when you get way into the weeds um there are some other reasons so involving what what fields your circuit

is defined over so you know certain computations sort of naturally want to work over some field or another and if you use one of uh these two category discrete log that field kind of has to come with a nice elliptic curve it kind of matches the field in some sense whereas this iop based stuff is it doesn't it's just based on hashing so you don't get field size restrictions from that but you get field size restrictions from other other things like most fried needs ffts so that creates other restrictions on the field size so weigh in the weeds of how these work there are some other reasons you might want one or the other

further complicating the comparison between all the snarks out there other questions okay so now you sort of know the full taxonomy of snarks uh you know we've roughly had three classes of pioneer iops four classes of polynomial commitments of course in each class there were multiple so you're talking something like uh even if they're only one inch class that's already like 12 snarks and there's more and so there's like this contour explosion let me make it even worse for you so tim this is your question oh sorry my next slide is uh the answer to your question um yeah so i want to run

through the taxonomy of you know some of these kind of 12 possibilities and tie them to like the name of the systems people are really using okay so the first class was sort of this exception class that wasn't quite based on polynomial iops platinum commitments but if you squint it's very similar um so the most popular snark in this class is now due to growth 16 because it really has the shortest proofs just like three group elements um and the downsides here tim tim mentioned in a question um the the trusted setup for this snark is circuit specific so you change the circuit you need a brand new trusted setup um it's not post quantum and the um prover you know i would characterize as pretty slow and space intensive okay but the verifier like really fast

um and the proofs are really short okay so there was um interesting progress a few years ago um that kind of the the big benefit was to turn the circuit specific trusted setup into a universal one so uh all that matters there is how big the circuit is not like the specifics of its wiring um and so that's the big benefit and so so the main examples here are marlin and planck and people are using these a whole lot today um the the proofs are bigger and the prover is is slower than the already i called slow proof of growth 16.

um there is a counterpoint which is the snarks that are truly based on polynomial iops so every everything that i'm going to describe but the top category they can kind of use more general circuits so you might wind up in a situation where like for a given circuit size like the planck prover is significantly slower than growth 16 but you can apply the planck prover to a smaller circuit and so like slower approver applied to smaller circuit turns out in some cases to be faster than faster proof replied a bigger circuit things are complicated to compare okay the next category um now moving to the transparent snarks are you know take any much interactive proof or interactive proof and combine it with one of the fast

prover polynomial commitment schemes uh which of course tend to have bigger proofs these things you know tend to always be in tension proof of cost and verifier costs and the benefit of this other than transparency and uh and plausible post quantum security is going to be this is how you get the fastest approver in the literature but people aren't using these today because the proofs are pretty big and verification costs are very important in the things people are using these snarks for today and the final category is like it doesn't really matter what polynomial iop you use but if you use the fry polynomial commitment you're going to get the shortest proofs among possibly post quantum snarks be transparent too and the downside is you know the the prover is is pretty

slow and the proofs are still fairly large like lambda that's the security parameter times log squared is bigger than log is bigger than constant in some cases by significant factors and i'll say more about that later okay so that's that's the world of snarks yep so like if you imagine a little like non-blockchains but like where your phone is like having a snark like a server something like generator is the most useful where you're going to like previously between like the server and doesn't care alarms for blue sizes uh yeah and then you might want to choose a snark that people aren't really using today yeah okay and then finally to get to tim's question so this is um sort of ongoing work um so i don't have a specific

result to tell you so i'm just gonna say it's a what i consider a very promising approach uh to try to resolve the tension between prover time and verifier time and it's not even a new idea it's like a simple it's very simple um it's known uh but the devil is in the details of like will it actually concretely be nice so the idea is to take a like a fast prover but kind of big proofs maybe slow verifier snark and compose it i'll say in a moment what that means with the small proof snark so what that what this means is the prover like in its own head is going to use the fast prover snark to come to computer proof but it's going to be a pretty big proof he's not going to want to send that proof to the verifier instead it's

going to use the small proof snark to prove that it knows the big proof and send that proof to the verifier so that proof is small and can be verified quickly um but as long as the big proof snark i say it's big proof that's sort of a relative statement as long as the verifier of the big proof's mark is like sub-linear in the size of the original statement being proven right like you know computing the small proof uh to you know what what you're doing is you're turning this verifier into a circuit and applying the small proof snark to that circuit so as long as this verifier is work saving

right that circuit is going to be smaller than the original circuit that the fastprover was applied to this might be hard to grok online but it's in a sentence what in in principle what this does is it makes the prover time dominated by the fast prover prover time and the verification cost dominated by the small proof so you get the you get the best of both worlds right so like fast proof or big proof that could be like linear time proof or square root proof size or something or square root like verification time right and meanwhile maybe the small proof slow proof or maybe that's quadratic proving time but you're invoking it on

the sort of square root size proof so that's just another linear term yeah yeah so that's exactly it except um in practice quadratic prover would not be that bad it'd be like quasi-linear prover with just like gross constant and log factors um and uh but square root is exactly right so like the the fast proof or big proof those snarks really do have square root size proofs so like quasi-linear and square roots is still smaller than linear and yeah the the reason why this is still ongoing work is because doing this requires taking the verifier the first snark writing it down as a circuit and then applying the prover of the

second snark to that circuit and that's just like a nasty thing to do people are doing things like this all over the place but i i mean my guess is just the groups doing that are just not very familiar with the the snarks with the fastest prover um so i think that this very simple you know just one composition of two snarks actually is going to wind up yielding very soon um snarks with very nice cost profiles they're not going to literally dominate on every axis but i just think they'll be very nice profiles that might be attractive even in the roll-up context yeah so people have proved like very recently there was a nice workout um that sort of

uh so they're lower bounds with caveats so you can sort of prove that like without using certain kinds of cryptography you can't hope for constant proof size um you know you can you can prove things about like the kind of cryptographic assumptions you need to base your snark on i don't think we have i mean asymptotically speaking um the snarks we do have are really good like you know we have snarks for the prover runs in linear time can't help to do better we have snarks where the verifier runs in you know constant time uh but there's an srs or logarithmic time but there's no srs so the lower bound you could hope for is

to say like you know a transparent star can't do better than logarithmic time for the verifier and i'm not aware of a result of that but i don't you know does that mean it does it does but as stated this could potentially um do better than all of the things we listed before so yeah yeah um so if you if you don't care about like logarithmic factors and like practical performance you don't need composition to get everything you could ever want

um if you care about the difference between log and constant so you really do care about you know for the verifier um yeah i actually don't know uh yeah i don't even know if composition is going to get you there um without without a trusted setup so i i mean for this slide to be really a statement where you care about log factors and constants and concrete performance and yeah people are composing snarks today but they're basically they're they're not using mip and ip based snarks that have the fastest prover um in that composition and i think essentially if they did you'd get like new cost profiles that

would be very attractive yeah and then how does the like the transparency and postponed security composed if you were to do this great um so if either one of the constituents darks is not transparent uh the result won't be transparent if either is not post quantum the result won't be post quantum um if they both are um then they well transparency will be preserved and post quantum is sort of heuristically preserved but that's not a formal statement so like plausibility is going to be preserved i i think it's fair to say yeah means like we you're not i would be surprised if you came up with the non-contrived example anytime soon that

broke that you know where they're both independently post-quantum and you compose them and you can show the result is not post quantum i'm not an expert on formal postgraduate security proofs but if you came to me tomorrow and said here are two natural snarks that are both quite but their composition is and i'd be like wow okay um by the way when you compose known transparent snarks today the the security is like even uh classically is going to be heuristic this is in the weeds of crypto but like without the composition you could unconditionally prove them securing something called the random oracle model with practitioners they're quite

comfortable with but if you want to compose them you you're going to lose security in the random oracle model so security is already going to be heuristic anyway and people and i'm like very comfortable with that in practice as and i think all practitioners are i mean they're out there composing snarks today um so yeah this whole plausibility with post quantum is sort of no worse than the situation even with classical security and composition is there an easy intuition for why composition can mess up random oracle-based security yeah um so you have to represent the verifier as a circuit to then apply the next snark to um so you know in practice the random

oracle gets replaced with the hash cryptographic hash function so you have the circuits have to compute the cryptographic hash function like in the circuit cool okay so i really was hoping to be able to come here and be like look at my exciting new snark but i couldn't so i'm just going to say i really hope that this leads to something we'll see um okay so now we get to the final part of the talk looks like i have 30 minutes is that right tim yeah okay roll ups okay so um let me tell you what the context is for rollups and then how they work so the idea is that public blockchain should be verifiable by weak nodes

um you hear from you know sort of the bitcoin community they'll take this to extreme they'll say if you're not running your own node you just can't trust anything so you want sort of um verifying the blockchain to be doable by you know certainly a laptop maybe even a raspberry pi if you talk to you know the really people who are extreme about this a less extreme view is like if you if you need an amazon server to run an ethereum node like you can't call ethereum decentralized at that point so um we ideally want it to be possible for like weak devices to verify you know that um all transactions that have been

processed by the blockchain today are valid right something like that okay so there are two costs to running any blockchain node um the first is that they have to do computation to validate transactions um and in a little more detail like for basic transfers and swaps and things i think this computation is mainly just like checking digital signatures and making sure people don't overspend their accounts but in general on ethereum smart contracts the nodes might have to execute arbitrary evm byte code and just a little more information about that if you're not familiar so smart contracts and ethereum are typically written i believe in solidity it's a high level language and then

compile to something called ethereum virtual machine byte code evm byte code and the ethereum nodes execute that byte code so you know in principle these smart contracts can do like arbitrary computation so the nodes kind of have to be prepared to do arbitrary computation but then like you know i think uh my understanding is a lot of the volume on ethereum is just people sending each other money and stuff and that's very simple transactions not doing any crazy computation inside them um so in addition to the computation nodes have to do they have to store all the data that live on chain with some caveats about um you know like clients and full nodes and i myself am not super well versed in those differences

but conceptually yeah you've got computation and you've got storage those are the two costs okay so um yeah let me just call like the data stored on chain like the state of the world and for simplicity you can just think of them as all ethereum account balances just if you want to make things concrete okay so the very first idea of a rollup is just to treat the blockchain or really the blockchain nodes as computational verifiers and the roll-up service as an untrusted proverb and this idea alone can save the verifiers work so like rather than checking the digital signatures on a ton of transactions directly you could imagine like some some proof gets posted to the blockchain that all the digital signatures are correct and then the verifier just like has to trust the proof and not check

each one individually so this is great this will save the blockchain nodes work but it doesn't directly you know reduce the amount of data they have to store yeah so we're going to get to that as a second idea i think yeah okay that's some some storage you're saying um like don't even you know uh instead of putting digital signatures with each transaction put a proof of knowledge of a digital signature with each transaction yeah like if you have like one proof that you know signatures for like transactions great yeah so true and i think that's another

way of phrasing what i'm going to call the second idea if you disagree let me know and we'll talk more okay um oh by the way like from now on in case you haven't seen this terminology before we're going to call the blockchain like ethereum we're going to call that an l1 and or the chain and the roll up we're going to call that l2 layer 2. okay um so here's the second idea for rollups this is to try to address the storage issue and again i think joe just said this more or less so we're not going to store the state of the world on chain we're only going to store a cryptographic commitment to it and you can think of this is often just like a single hash value 256 bytes or something so the binding nature of the commitment scheme will now ensure that once the

commitment is on chain and everyone agrees on it no one can alter the data that's committed to so if someone comes and says look here's like a piece of data that's consistent with this commitment and like here's the authenticating information that kind of establishes this consistency claim like binding you know the cryptography is ensuring that like their claim is true and indeed like this is the data that was committed to by the on-chain commitment the key conceptual consequences of this is you no longer need to rely on the consensus mechanism of the blockchain to ensure that no one is messing with the data that the blockchain is really representing like as soon as there's a cryptographic commitment to the data on chain

like the binding nature the commitment scheme means no one can go and alter the data okay this raises the issue of now the data is only committed to it's not just like stored on chain so you can ask like well what if someone in the future needs to access some of the data that used to be on chain and now it's only committed to this is referred to as data availability issue and there's sort of two approaches people are pursuing to this i guess it's a it's actually a my understanding is a rich design space but at a high level the two approaches are like stored on chain anyway um or use economic incentives to get off chain entities to store the data and make it available

um so as far as storing it on chain anyway it can live in cheaper storage uh called call data this is like the ethereum terminology which my understanding is only stored by full nodes there are definitely people who know more about this than i do and moreover ethereum is considering changes to the protocol itself to make this you know sort of semi-unchained option more scalable so i know they're considering letting holiday to expire after year and then sort of move to kind of the second option for kind of stale call data if they implement sharding which is going to happen sometime after the merge it's kind of late in the in the game plan um that will increase the amount of onstage storage um it'll do something

like i'm probably going to say this wrong but there's something like multiple sort of related but blockchains getting stored out there each shard is sort of kind of like its own chain i shouldn't have said anything because i'm probably saying it wrong anyway it's going to increase the amount of orange chain storage um but if we're going to stick with this on chain option it will sort of put an upper bound on the possible benefits of roll-ups because no matter how fast the verifier is for verifying the proofs you know the dominant cost will just be like storing all this stuff on chain that is like not actually part of the proof right it's just the data that's kind of committed to has nothing to do with how efficiently the proofs are verified yeah um like a very minor user of ethereum

can i feasibly just store like i don't know i'm interested in my own account balance maybe like one or two smart contracts or you know can i just like store that information myself or is that or am i going to have problems if i don't know some like local state when i try and spend my money so i think if you send money to someone else no that might be that might be that might be okay you the data and um of do purple proofs

and stuff to prove that it's okay but even like receiving a transaction from somebody else if you want to verify the transaction you need to know something about their state you need another transaction counter so it's a bit tricky to validate anything if you don't really have the call to state you either need all the state or you need to talk to someone you can improve stuff so even like just for you to send receiving money is more complicated it's a great question and yeah this

roll-up part of the talk um i i did my best to become well versed in the whole idea of rollups but you know this whole data availability stuff is not directly related to snarks so you know keep that in mind let's put the two ideas together um sort of the first one was about saving computation the second one was about keeping less data on chain or keeping it in call data instead of in the more expensive parts of on-chain storage so a first attempt at how a rollup would actually work is sort of at all time the l1 is going to store a commitment to the state of the world that's like all of the data that used to live on chain um and the roll up will like take a batch of transactions and sort of you

know apply it to the current state of the world to get an updated state of the world and then post a commitment to that updated state on the l1 and the problem is just how does the l1 know that the new commitment is correct and basically the snark is going to prove that so the roll-up will also post to l1 a proof that sort of the updated commitment followed by applying a series of valid transactions to the old state of the world and you know everything was valid and it produced you know the new state of the world produced this new commitment and then note that the proof is going to the stock proof will be verified one chain so like every blockchain node in the world will have to run the snark verifier

so the transaction is executed or part of the witness yes as is any authentication information like merc authentication pass for any like pieces of data you know that the transactions need to know to be applied well in particular you're not focusing on the current paradigm where transaction descriptions you're posting is called data you're actually thinking maybe that's off chain too right potentially yeah you're like you're at your agnostic event yeah yeah and you can run into situations where like if multiple transactions in batch hit the same account then you only need to provide authentication information kind of once for you know um they're all hitting the same leaf for

the merkle tree so you you only have to do one look up to the you know uh initial account balance at the start state of the world so you get savings so like the bigger these batches are kind of the more that happens and so you get extra savings because you know certain accounts might be hit many times so there are there are incentives to make the batches big beyond the fact that um you know the well we'll get in we'll get into the main incentive to make matches big soon okay so um if everyone is sort of clear enough on how roll-ups work and what they're accomplishing we can talk about their performance ask other questions

not too bad on time i'm only slightly worried sorry but like so is it say that you wanted this property that like you and i can trade money without knowing the entire state i don't know a lot about like c cash but like presumably that's feasible to do on cpas because no one's supposed to know the entire state anyway is it like so i you know i'm trying to think of this in my head um you know to provide authentication information um for even just you and i our accounts um

there is information about other not uh people you need to know or it's not you know it's really um you've got okay you've got this big hashtag i haven't told you what merkel tree is but it like takes all the account balances and it you know pairs them up and hashes them and then pairs those up and hashes them and and the authentication information is like all of the kind of all of the hash values on like a path from like your account leaf to the root and like my account leaf to the root so you need to know more than just like you know that you have x ethereum and ify ethereum uh it gets pretty hard to to not to not know the state of in our is like something fundamentally different than that

joe do you wanna yes i think the difference is like in z like the definition of the transaction is like the proof that a transaction is valid relative to some kind of like state snapshot because the whole thing is like wrapping stark and in ethereum people think of a transaction just like this signed statement and then to verify that you need to go check it against the state but you could sort of like expand the notion of a transaction ethereum to also include like merkle paths that prove that the signed parts of the transaction are actually what's committed at that point in state so it's like you yeah you could redefine what you mean by ethereum transaction a little bit to make it like as verifiable as a zcash transaction you just have to add some

extra stuff that people don't normally do because it's kind of like assume that everyone has the state stored anyway and just because z cash is you know zero knowledge private whatever doesn't mean that necessarily that people don't need to store a lot of state it's just the state isn't leaking anything about anyone's data and i'm not saying that people in zcash do have to store a lot of state i have but it doesn't inherently mean that day well yeah in practice they do because most of the cash transactions are not based on non-zero knowledge transactions which are just the same as anything else but

if you you like forked z cash and had only uh shielded transactions okay so let's let's talk about um roll-up performance and how we would even measure that um okay so as something of an outside like i'm an expert on snarks but you know not specifically roll up so as an outsider to the space i've it can be a little challenging to sort of understand you know how people are measuring performance and kind of the states of various projects that are you know they're very actively developing their capabilities so

tracking it can be difficult um so i'll give you an example of of just some language that uh i think can be confusing if you haven't seen it before so so here's a proof of a tweet of starkware uh you know they said you know we had three thousand transactions per second um all three hundred thousand transactions in one proof um and it took us six minutes three seconds um so i don't know does anyone want to suggest what what is a natural interpretation for that like what that means so what does uh 3 000 transactions per second and six minutes total mean yeah um so that's what i thought

as i was trying to kind of understand the the space um turns out that that that would be a little fast um like here's another example um this one from zk sync they're talking about 20 000 transactions per second so that's even faster than 3000 transactions per second um so as far as i can tell it so this is not talking about uh proof generation um so there's a difference between latency and throughput so this becomes very natural kind of once i tell you what i'm i'm pretty sure that the roll-up companies are thinking but you know if you if you haven't seen it before it's not so natural i think so so latency refers to the delay between a transaction posting to l2 and a proof capturing it hitting

l1 and this is determined by two things um so like the time to compute that proof um but also like uh if your volume on l2 isn't that high you're gonna have to wait around until you have enough transactions that you're you know then comfortable generating a proof and posting that tail one other otherwise you're going to have too many proofs on l1 and if you're going to have like some congestion issues if you're oh if your volume's too high yeah yeah i don't even know what you do sort of if uh if your volume is uh is way too high like how you would keep up yeah yeah and uh maybe it's just like queuing theory yeah over time

yeah so we should we maybe want to actually discuss this after we get to the the other um notion of performance which is throughput um which is probably exactly what you have to think about with transaction volume okay so so throughput is the number of l2 transactions that can be processed in a given amount of time and and this is what i think the the tweets i just put up are really talking about when they talk about transactions per second um and as i'm going to explain this has technically this has nothing at all to do with prover time so this is this is what i i'm pretty sure they have in mind so suppose one can upload a proof capturing x transactions um and it takes y seconds to upload the proof so forget about how long it takes

to compute the proof it's what you have it it takes y seconds to upload so you can do something called pipelining so what's going to happen is you know every every y seconds you're going to have collected a batch in the last five seconds you ship it off to the approver to start chewing on and at the same time some proof is going to have just finished being proved you know you now have this new proof you start uploading that to the l1 okay so kind of in steady state this is getting kind of uh x transactions are kind of getting proved to the l1 every y seconds okay um but it says absolutely nothing about latency like the approver could

have taken a year just after a year this pipelining has started posting to the l1 and from that point on your you know they're year old kind of transactions but they're getting a very high rate on on l1 throughput is what determines like blockchain scalability meaning like how many transactions are kind of getting summarized on the chain every second but latency demands will ultimately constrain the batch sizes like people aren't going to wait a year just that's an extreme example and i think you know i find when some of these roll-up projects are talking about their performance you know they know throughput is blockchain scalability that's what we care about so they'll talk it's very natural that's what they care about they talk about throughput uh but there's just no mentioned latency at

all and that can be very confusing um when you just see these things without that context so this past week i've been trying to learn about this stuff and i had to puzzle this out so hopefully i'm saying this correctly yeah um so like on the partner side if you have like approver for like if you're like did you just circuit like the first like 10 transactions can you like pipeline that and like add on like you're tackling the circuit like starting over again adding new transactions yeah um so if you were we were talking about this uh if you have a certain kind of proof system that supports a functionality called incrementally verifiable computation you can do something like this where you can kind of prove a bunch of transactions

and then in the prover's head right and then like more transactions come in and kind of updates the proof to incorporate them and then and kind of whenever it's ready you can kind of stop and post the running proof to the blockchain um but as far as i know the current blockchain projects are not supporting that functionality does that make sense but i mean we know how like there's a lot of interest in that functionality like they could be supporting it their protocols known that support incrementally verifiable computation yeah i do want to mention some counterpoints to this um focus about on on latency um which is alternatives to these validity roll-ups do have high latency so optimistic rollout my understanding

is right now they're sort of waiting around seven days giving people a chance to identify fraud so you don't really get finality on l1 for a week you know the non-blockchain solutions like visa you know it looks like your transaction went through right away but it takes like 48 hours or something to settle so people are tolerating pretty high latencies now in some contexts they don't mind and even with the rollups it could it might not be the end user that's taking on any risk of latency it could be that a centralized exchange is the one interacting with the roll-up and they're going to promise users you know finality and if something goes wrong it's the exchange that's going to be out a whole bunch of money or something like that

so you know um if there is highly you know people might tolerate a really high amount of latency in certain contexts anyway um yeah so can we close the loop on the tweets let's say yeah yeah sure so are you saying that with this what says take the one on the left um so is it implication here that i said 3 000 per second is what like the l2 infrastructure could handle presumably are they claiming that actually if l2 throughput was saturated they would be able to generate proofs sufficiently quickly to get to keep up with that i i

think that's right so i actually i emailed um starkware about this um and some other things um which i'll i'll get to um and my understanding of what they told me was that this is counting upload time six minutes is upload time i don't know how to explain actually 300 000 over 300 seconds is 1 000 not 3 000 so i don't know about that but um uh yeah so i i think so this is upload time is my understanding of what they said um and and then i sort of have puzzled out this whole throughput thing uh as the reason that this is makes sense to just count upload time and improve your time right right and like we're you know so i

do not know how long the prover took here but the idea is like that's going to determine latency assuming there's enough volume anyway that they're not waiting around for batches to fill but you know this pipelining thing sort of means and if you're not you know forget about latency like sort of doesn't matter for throughput with this pipelining thing right i mean like the failure mode would be like you know a thousand transactions come in you start getting approved for it and then in the meantime let's say you only have one machine right and then while while you're generating proof for the first thousand two thousand new transactions come in mm-hmm right then you approve for them and but then four thousand transactions come in when you're doing that for you

just kind of yeah you don't you don't keep up yeah so i'm saying like is this an implication of this that they can they're claiming they can't keep up i guess yeah and there i i mean i guess so i mean this was they were tweeting about some sort of um sort of proof of concept if you will for reddit right it had like a competition for rollup projects i don't know the details so there's some context here of this tweet that you know i'm not getting into and don't necessarily know all the details of um but and i will say you know i have a slide that we're probably going to run out of time for but various kinds of composition of snarks can help address some of these issues potentially where um so maybe i should just jump to that real fast so one really question so like

improver time as a function of the number of transactions as a function of the batch size is it sublinear in the match size time i mean you have to at least read the all the transactions in the batch so linear in the prover time can't possibly be sub-linear in the yeah so i guess i mean like the the computational cost per transaction you could imagine that being decreasing in the batch size yeah that's not how it's increased you know cut uh otherwise i'm confused otherwise it seems like you're gonna have a limit on how big your batches could possibly be if you hope to keep up you might yeah i thought that that batch size might be well less than the sort of throughput that the l2 infrastructure

so here let's let's jump to something here is um how you might use kind of proof composition to address some of these issues that you're raising um i think um so imagine you had i'm calling these sub-blocks but you could think of them as just multiple different blocks okay um so block one comes in you ship it off to the approver to compute a proof in the new commitment okay um as soon as you have the new commitments you can start processing a new new block you don't have to wait for the proof to be done to start working on the next block of bat batches of of

uh transactions and i think imagine if the proof of time was like a plus bx where x is a number transaction like that where a is big mm-hmm and b is small so the hope would be that b is so small that actually you could keep up with the l2 infrastructure okay and then the point is you need the batch size big enough so that the per transaction approval cost yeah is approaching b yeah supposed to be dominated so that's that's exactly right but then the the problem is that the snarks people are using today the approver time is uh like n log n and so you're right like you if you if

you take the batch size big enough you know um i mean it's super linear road time for the like the per transaction proofer time is getting worse not better but why i have this light up like let me point out like um something that can help kind of improve latency um even if the provers are slow is snark composition so you could imagine uh sort of breaking the block up into much smaller the batch up into much smaller batches have the prover true on each black batch in parallel

okay um now because they're small batches if you were to post each of these proofs to the blockchain that'd be no good that's a lot of gas okay so instead you can aggregate the proofs and this is very similar to the snark composition thing i talked about um for you know resolving the conflict but the tension between prover and verifier time so this proof is going to prove knowledge of these proofs each of which would have convinced like the roll-up verifier to accept you know given the preceding no it's okay if they do so so like

you know the the this this proof would establish that like um pi2 would have convinced the verifier that commitment c2 followed from commitment c1 by applying some batch of transactions and so the point like you you you need to know to start chewing the proverb to start chewing on on this batch needs to know c1 but does not need to know pi one and and you don't know c1 quickly because that's just like merkel hashing but pi one is what takes like a long time to figure out um yeah yeah yeah and that lets you sort of rather than waiting for the whole giant

thing to fill up and then having like a super linear time prover chew on like a giant batch so that's kind of bad for two reasons um and this is this is getting similar to ivc and it's not exactly ibc with this incremental thing you can you can get the provers going on smaller batches in parallel and i think this will improve some of these issues in practice but there's a limit to it because representing the snark verifiers as a circuit is going to be nasty and that's going to mean that the number of sub-blocks really can't get that big um while i'm talking about this i it looks like i'm going to pick up um where i left off you know i'm going to finish this talk next time

um but i might as well finish talking about this now so several projects are doing this zk sync has been doing this for a while my understanding is so they use plonk um i saw a blog post from 2020 that said they were doing this with plong so it's been a while they were actually doing this initially according to the blog post um not for through uh latency reasons but they were using a structured reference string that was just not that big and so if the blocks got too big their circuit would need to be too big they just couldn't improve so that is joe i said i mentioned at least some issues with srs later that's an example of one they found the way around it obviously um so just much more recently um starkware and polygon zero are doing this with fry

based snarks um and you know i don't really know what the performance is um i i think it'll buy them some you know levels of speed ups due to the parallelism it's unlocking is my guess but like the fry verifier like i said the proofs are pretty big um so i i think that the number of sub blocks is going to have to not be super giant because you're just going to this the uh the statement being proved to aggregate the proofs is just going to get real nasty it's my guess um yeah about parallelism aren't there techniques to generate proofs using parallelism like to go short of actually like you know full recursion or

yeah yeah so a lot of proof systems can be parallelized um most of these do a giant fft which is kind of nasty to paralyze you can do it but um so this is kind of a way to sort of more automatically do the parallelization and then the other thing is a lot of these snarks when applied to big statements in a non-recursive fashion very space intensive for the approver and the proverb will just you know like fall over because it's out of memory unless it's like on i just start where at least old work they were using terabytes of ram um i don't know what they're doing now so they're just basically gross cost to having giant blocks so this can help those costs in various

ways you know n log n is is nicer if if n is smaller because that log n factor is smaller um so yeah there you you can get parallel speed ups and and people are without doing this um some are also talking about i know starker's talking about um now having an l3 so it's like these proofs are getting posted to l2 and then the uh these proofs thinking you know pi is getting posted to l1 i um i don't know exactly the details of the benefits of that um rather than just kind of waiting around to post python you know i guess having these on l2 is um i don't know um so these are things people are thinking about so i think i think there's going to be web

yeah it's uh i think i've seen mention of l4 so i don't know i don't know why i think if they want zk maybe there's a reason to go to l4 so yeah the numbers will get bigger i saw this as people talk about web5 but i think that was some kind of joke i didn't get the details of um okay so i'll finish up the rest of this presentation next time and then tell you um some more technical details of how these polynomial iops and polynomial commitments are designed uh but yeah thanks for all your questions um it's really good that i i had time because it means the questions were good uh and yeah i'll say more next week