zkSummit -Groth16 is not dead: Exploring the tradeoff space of ZKP Systems -Georgios Konstantopoulos

Transcript

[Music] I'll thank you for being here so I'm George's and this is going to be a talk about things that I learned in like last few months so I haven't been doing this like type of work for too long so please don't like judge me so okay I think everybody in this crowd knows this so this like the snark I know something I want to outsource like the verification to somebody and like how am I going to like prove this computation like in a short way like I have to encode this computation and some proof the toolbox that we're using so I want to take like a very practical approach for this talk

it's like a bunch of things so for the snark usually we do pairing based cryptography somes form of accumulator which usually is myrtle tree some like vector commitment or something and we have some assumptions so like all of these protocols that we've seen so far they're like either in the algebraic group model or the generic group model which like - things that currently they're like slightly stronger assumptions and like the usual ones that we'd have if we wanted to recursion usually you'd need like some curve that is like like that has some cycle like but shown like maybe have like some breakthrough on that and usually the like thing that's like a very hard part to do is like properly instantiate in like the protocol so

usually like you you could very easily like do it with a trusted like party that generates some string or you can like do some multi-party computation to avoid the setup and recording like view that we have is like that you have some statement you have like you make some information theoretic like statement about it and then you compile it you use some compiler to go to a snark and we have this pattern again like which started from like the CS proofs then to ballistically checkable pay and proofs and so on where they prove a send some commitment to the computation to the verifier and that the verifier starts making queries at different points and depending on like what type of a

constructor using this could be like a polynomial IOP linear like what Ben was talking about and so on so this like what this triggered this new wave of like snarks realizing that this technique could be applied like in this case so this is the normal snark and this is like a pre-processing snack so basically you have a snark where some of the like computation some like usually to have a construction verifier you need the way for the verifier do not have to read the whole like circuit but like just a short description of the circuit and usually this means that the common reference ring that the wave that you have generated is like kind of in the size of the computation yeah this usually has this problem so what can we

do to fix it firstly like the one thing that we know that works there is like the world 16 and with the previous construction before it which is like pretty fast so like to group 1 elements 1 group 2 and like a short amount of pairings and however like the initial growth paper was not like MPC friendly then we had like a paper in 2017 which showed how to do it in a multi-party computation and then we had one more paper which showed by Mary molar I believe which shows that you don't even need like some of the assumptions that were in that paper however like what we really want is like to have a universal set up and how can we get that like the first approach was like from my understanding this was like

the tiny room or the warnimont a Niram approach where you have a cpu and you run one computational step in the in the snark and then you keep like iterating on that the other approach was to have like that you initially have like some like reference string that is like common in like random and then like each time that you have like a specific like a computation you like try to derive like the specifics of the specific string from that one and the one approach like the one that we had in sampling and the other one was like by like a mmm in 2018 however the common reference mean was like too big in that case and we need something else like both Universal updatable and practical some review okay we have the polynomial

we want to commit the polynomial the commitment is like short commitment to it ideally we want this to be like very very short and independent of the size of a polynomial when the opening says that I'm going to evaluate the polynomial at some point and I will also give you and I will return you like an evaluation of the polynomial plus some proof they calculated that attest that like they I calculate the polynomial correctly and the verifier will like return 0 or 1 depending on if that witness passes some things so if you remove the polynomial this looks very similar like through some miracle trick commitment however what we really want it's like a constant size like opening or like commitment which if you have a constant size commitment allows you like

to avoid look very ethnic terms in your like proving and verify it seems that like all like constant size schemes require a set up which is like what they cut by linear in one required M so I have a question like if like at some point we're able to have a constant size without the setup so can we have indicator then we have the dark like which we heard about earlier which are based on groups of unknown order you can share them with an RSA like number so like depending on what you trust maybe like you can use that it's fast maybe has a set up all you can use the class groups which are like slow but they don't have a set up and slow and also big and there's like one other approach

which I believe is like what's used in fractal and like in also in polynomial commitment scheme by law so when I mean which is like very similar to fry which is used primarily in Starks where you get though which works but it gets you like a logarithmic like term overhead due to the make the metal trees that you're using so a caveat on the darks is like that if you notice like okay sure it is transparent however it has this logarithmic term which if you use a set up it moves over here and also another like part of the say of the die of the darks is that if you notice here yes indeed it has like a logarithmic term

improvement over the fry based protocols but it's in groups of unknown order rather in class groups if it actually is transparent and and also this like this type of Parisian like much much much more expensive than hashes and forum a practical standpoint like if the operations like hundred times worse it's it's bad so we need to like figure out like some way around it what you could do here is that you could have like a hardware like acceleration like have some ASIC that's able to calculate that but at that point like you're kind of like comparing apples to oranges and now let me talk a bit about the universal set up again from a practical standpoint because the whole idea of the universal

set up is that firstly it is able to like be used like for any kind of circuit and also if it's updatable you're abled like to always trust it in some way so okay I have the public parameters I have a deterministic derivation for a specific circuit and I get like proving he a verifying key a and I distribute them like to the people that want to use it and if I have another circuit I can do a deterministic the evasion and I get like another system this works very nicely in the sonic construction they show how you can do it very efficiently this derivation so we're good there however like it's like an implementation detail as they would say like with respect to like the continued set up and let's say that we

deployed blockchain scenario we have a miner who is like the natural part we like to have both the proving he and the verifying he actually and let's say that we have Alice that does not trust this setup because isn't so Alice goes to the common reference drink updates it in some way and then gets back like the new proving key and verifying the thing here is that if Alice wanted to generate the proof for this circuit and who is going to verify that proof in order to verify that proof you must also get the updated proving key so they the new like same statute reference ring must also be

distributed to the people that you're trying to prove it so the issue is that in this case either Bob in order for Bob to be like part of the same system as Alice they receive the new proven key or like the miner has to keep like previous verification keys and this might seem obvious like oh yes of course like this must be done if we're on different proof systems if we're on different instantiations like how gonna speak to each other but but from a practical standpoint they continue setup is not continuous per se it's like continuously update it's updated like in discrete time steps so if you're in a blocking scenario you can not really have a transaction which like says at any point in time like update the setup because it also has the danger that can cause like

some sort of race condition well I am preparing a proof for the current instantiation of the circuit then somebody else comes in contribute to the randomness it generates the new like circuit specific like reference thing then the minor updates they're like they're the verifying key and I'm left with a proof from the previous instantiation of the setup so it would be nice in this case if I was either like able to kind of update my like already generated proof and some proof that is like with the new randomness because otherwise I have to like regenerate like the proof so like what would you do like I think the solution to that would be like to add like discrete like updates like let's say like mini ceremonies like every week that the randomness gets updated and you

trust model kind of switches from like the one time setup to the weekly setup again from a practical perspective like the question I had like with this like new system like okay we have the system that was deployed on sapling is it actually like that so sonic was like this initial thing which says okay we have an r1 yes we will encode it in a bivariate polynomial that polynomial has to have like a certain structure so that I'm able to like convert it with some way like to a univariate one and then I'm utilizing like the polynomial commitment schemes that are univariate and have like so nice properties and so mix performance compared to like growth

so will this like taken directly from the paper so with bulletproof it does not like stand much like to compare you to the linear verifying of but compared to growth sonic is like much more expensive and in the health mode yes it is like a of good and it's like very practical for like blogs and applications in van helped all the sixth ranked mode what you call it I believe it's like way way worse so we can see that it's like 273 exponentiations like it's way too expensive and it's like three ways that you can like ram sonic so if they're in the help mode with shannon mentioned or the full sex ain't all there like you can do client side parallel proof generation because the way that the

protocol work is that at some point i receive a challenge and that challenge does not have to change like if I have multiple proofs on my if I want to like prove like ten transactions I do not need to like I can reuse the challenge so this allows me this would be nice if I could somehow as a minor you could look at this like the help mode being a synchronous protocol whereas a minor like I received like ten proofs which I already signed an eyepatch name and the parallel proof generations kind of like an a synchronous one-way I have like different like different like Zed eyes my eyes and like it allows me to improve my proof generation time and I think that like you could probably like utilize the halo construction in this in

this scenario to do this sort of like aggregation of the proves the plunk what it does is that contrary to like sonic which kind of is are ones yes it says okay we're not really into the rank one contain system situation we're just gonna you wanna use this equation which allows us to do like more complex circuits so it's kind of like an r1 CS on steroids and the whole issue with the whole hard part of long is not really like proving a multiplication or addition it's literally showing that like the output of like some gate gets correctly fed as an input to the next gate and the novelty here's like the very nice permutation argument based on de Lagrange raises and if we compare so

plunk also has like a sibling called or a light by RL gaps who is watching their lives we might be live so which is like this very nice trade-off in my view again for the like blocking deployment setting which is like a very much faster prove it but like a different like a bit like a bigger proof so like the this what I'm trying to say that like you have Sonic Blanc and Aurora on the order a light and like depending on like exact what exactly like deployment situation you want to have in your block chain or your application you can pick one like depending on like which proof sizes fit you best and again for like probably for like actual deployment like I think you're like siding between you're thinking between Aurora light or sonic health and the plum verifier is like

here like to show this how like it's only like two pairings and like summit renunciations compared to like like the sonic which like much more expensive so now we have Marlin which is also it was like done concurrently like at least more or less during with the plant in the dark work which as we can see like from the graph it's as like more or less about like an order of magnitude difference with growth and like about like like 4x like difference in verifier time so how relevant this is like at this point the very farm time I could argue that like after some point like it no longer matters you're fast enough to

verify it there's no way you're gonna have blocks that arrive like every millisecond so you're most likely good however the proving time it in in my view at least like that's a very important thing so we need to like beating paying attention to the proving time and the proof size so none of this construction so far like postponed tomb so what can we do for that we can instead of using the current polynomial commitment schemes we can have like a we can learn from the Starks and fry and basically like use low-degree testing to have like some way to prove that we need know the polynomial while using just hashes and this is what the fractal uses which my understand is that it's like an

optimization plus extension on modeling and also the polynomial commitment scheme by blah which cars like the same like over here there's a stark if we can compare like the verifier and approvals like they're basically the same and these are like this like a screenshot taken from a less talking Simon's last month so we can see the like more or less like the very fire time and the approver time within like one order of magnitude with each other so it is kind of good enough already and the verifier times like 10 to the minus 2 so like okay how many proofs are you gonna do like like blockchains already without any like soon all the troops

they'll read like take too long like even propagate the block so even if like your cryptography is build like eventually you run into like networking bottlenecks and what's really interesting in this is like how for example fractal and aurora which are like the - postman - snart or Starks and they have like huge argument sizes like 10 to the 4 to 10 to the fifth and the constraint system grows and growth 16 and marlene like which are not like post quantum they're like you cannot even see them so they're like very very very small and if you're building a blockchain again you want very very small so probably like these are like Madeleine seems to be like a better choice like with respect to do that and some like things that I like about growth is like firstly it's like Frank

quantum state system like we know it's Aaron Sears we have languages that we can use to compile down to it and we know how to model it it's great it already implement it like in multiple backends we have like circum bellman lipsmack using it there are but very fired for it like algorithms which like have like better you can play to make but verify the proof faster GPU prove it which like there was a big bounty by code like run this year they were distributed provers which Howard showed less last year and also there has been like a real world bounty like a lot of money is like it's take if you break growth and my understanding is that currently there was a paper released by Noah and Mary like maybe ten days or less where they have a very nice inner product pairing

inner pairing product argument which they use like to make BLS a verification BLS signature verification more efficient for like a more for many messages over the previous state of the art but my understanding that like this could be used like for store ads if if I'm storing n growth proofs I can kind of like aggregate them and store only look and have like total store that size of log n which obviously it makes the block chain smaller if you're storing proofs and my thinking of it is that even if it does not allow you like to make proof for varying or verifying faster blockchain smaller so similar to how you can use for example cut through when you're doing Mabel wimple to like kind of make your chain smaller you can like kind of like do

some pruning of your chain using this technique and I hope the paper gets updated like to include some notion for this and I've taken like this picture from with Alex blog post on plunk and added like three more like pictures so we see how like as you go more to the left like your proof size like gets bigger but like your your your assumptions are like improving so like top left we start and fractal with like very very minimal like security assumption with like pretty big and like as you go more to the right so like bottom right previous night it's like growth which is like tiny but also programmed setup and what I'm really looking for is like some way to apply

like the all the innovations like founding Marlene and Sonic and plonk primarily on the graph like so that we can somehow like get a set up that is like at least verifiable so like perhaps like you could use the ZK sharkon cycle which I did not have time to put in this country in this slights and buts about my talk and one question I want to pose to the audience is that like all the a.m. these constructions they kind of like don't off the way of their like through the pure are ones yes kind of like add extra variables in the equation to make it more expressive like so not only are you not at are are ones yes with fun into and fan out and limited

you have like like gates getting input from like gates but in the next level so is it worth it like to kind of like get rid of our 1cs and like try to find a more expressive abstraction which perhaps with uses like if you said sometimes to zero to R once yes I don't know like this is like my question to which I'd like to discuss and thank you very much [Applause]