ZK12: Open Problems in ZK with Solution Hints - Vanishree Rao

Transcript

[Music] all right um I'm very excited to talk uh and my name is vanishri I'm founder of FMA um FMA just to give you a very quick intro about FMA FMA is a universal proof generation layer uh which can generate proofs for any proof system in a cheap and performant man and we are not talking about FMA today but we are talking about something very very very uh important for FMA which is ZK in general and I'm going to talk about a few uh open problems uh that I

think are very interesting in ZK okay so we are insanely close to having m adoption of zero knowledge proofs thanks to the significant advancements in proof systems and the infrastructure to support these proof systems to to visualize where we are in this journey of uh ZK Tech Evolution imagine a rocket that is racing towards space as it accelerate it reaches this critical point called the max Q point

which has this maximum aerodynamic pressure on the rocket and uh it is at this critical point that the strength of the nuts and bowls and the uh system calibration all get tested um and even a small flaw can lead to catastrophic failure this is why I think it is a good time for us in the ZK space to step back from the intricacies of ZK and

identify the areas in ZK which are very critical and try to tighten the tighten them up and um this is what I'll try to do to some extent in this talk oh um so I have a I have like a few in in my notes I have I have like a few a handful of uh interesting open questions but for this talk I picked two questions uh both of them uh are intriguing intriguing and are related to the setup ceremony um part of the ZK stack um why should we care about the

setup ceremony part of the ZK stack because if we because for most proof systems if we don't get if if there if if the setup ceremony is flawed then you don't have soundness and that is really bad and the other way is true too so any advancements we make in our understanding of how to do setup ceremonies well can actually have a very huge impact and very wide impact across various proof systems across various Pro project so I think this is a very uh focusing here has has has a huge bank for buck um this is why I picked two

questions um to focus on okay so let's start with the first question um so setup parameters right um they basically are a function of to recall they basically are a function of too uh which is supposed to be uniformly random and it has a few elements in in the set of parameters in the set in the set of parameters it's just a bunch of functions of Dao and uh the way these proof systems are

constructed is by starting with uh hardness assump assumtion that assumes that this to is uniformly random and we we we then make an assumption that this hardness uh assumption holds and thereby we prove the security most typically the soundness of the proof system right we start with to so to summarize we start with to uniformly random hardness assumption hes for uniformly random to and based on that we prove soundness of proof systems now what if th doesn't have full man men

anthropy right if it doesn't because we are doing setup ceremony right no there is no God who is giving us true Randomness all the time so we're doing setup ceremonies it may or may not have full mopy the question is what what if it doesn't have Min anthropy we don't know whether the setup whether the hardness assumption holds because uh this hardness assumption has been studied in complexity in in in in in in in we have been studying the this hardness assumption and and whether it's true or not um in um in the uh group model or many other models

only by assuming that to has has the highest Min entropy what if it doesn't have Min entropy we don't know uh okay so we don't know how the hard hardness assumption will change if hopefully there is a graceful degradation of secure degradation of assumption hopefully the uh hardness assumption doesn't completely fall apart okay let's hope hope that hope that and even if it changes to some extent for this changed assumption how does the soundness of the proof system change you don't now um okay this is where we are uh here is just a uh quick uh V visualization of of how typical uh setup ceremonies happen

where you you um at least part of setup ceremonies happen where you where ta is computed as a product of uh contributions from various parties this this is just there for as as a slight digression for us to recall how uh setup ceremonies happen but back to the main question how do we tighten the setup ceremony given the set setup ceremonies given the fact that uh we don't have true Randomness um so so I don't have an so I I oh I forgot to say the two questions that I have I don't have full answers to them I I only have some directions that I think are potential to expl explore uh

for them and I and uh would love to jam with anybody who are interested in these questions or the other uh questions um that I have and are are also very interesting I think um okay for the directions uh for the direction to to um address this problem I would say let's start with the following question um so recall we we are Computing products of contributions right they have some mintrop these these uh variables have some Min entropy but very likely not the not not the full Min

anthropy now uh what we care about is the Min anthropy of the product and how the mopy of the product keeps changing as we add more uh uh more um uh elements to the product um it'll be great if the Min entropy of the product keeps increasing it'll be great if we if somehow you know intuitively it feels like here's a here's a random variable with with some uh minant tropy K1 here is another random variable with some minant tropy K2 you Pro you generate a product hopefully this product kind of uh smoothens out the probability Mass this

is the Hope but but it turns out it's not always the case um the it can happen uh but but but it really depends on the exact distribution of the two random variables and we are we we are we don't have any control on the exact distribution of the two random variables you don't know how people are generating their own Randomness are they using uh raindrops to hit their keyboard and take the output and and that's the source of Randomness or uh they're using a lava lamp uh or I don't know we don't know we can't have any um uh restriction on the kind of uh distributions for

these random variables so we don't know we we so this question uh doesn't give us anything uh we had to start there but but but it doesn't give us anything so what do we do we need to think about I think what are the um what are the strengthening um approaches we can put on our setup ceremony as it is done what can we do there that no matter how these very no matter how these contributions um from participants are constructed there is some strengthening to the minant tropy happening because of the way we are doing our setup

ceremony um so um the one uh clear direction we can take to modify the setup ceremonies to um increase our uh to to to to get closer to the Assumption the hardness assumption we have made is by using uh random extractors right R random randomness extractors have existed for a while there is such Rich uh uh research in this area um so what they do is you start

with something that doesn't have high minant tropy and you create something that has high minant tropy and there are multiple ways of doing this but uh let's focus on the two ways um that that I think are are uh are relevant for our case so the two ways are um you start with a random completely random pure purely random uniformly random seed and then you then you can use there there are ton of uh extractor constructions you can use them to uh generate a truly random uh string however where you're you're you're now Shifting the problem

uh but probably decreasing the the size of the problem by saying that you you now you don't need an entirely long uh random string but you need a random seat but even that could be hard so instead what we can do I think this is a more instead here is another approach which I think is more amable to the situation we are in for setup ceremonies and that is you use a two Source extractor right here here here is here is an extractor and it it it is a function that takes two random variables and uh spit splits up one that has uh um High higher Min entropy and and and the

assumption is that these two random variables are independent and um so here so having said that this is think of what I said as a Prelude to the approach I think uh is uh do the approach that can make sense and and the approach is that um in instead of having your participants create one source of Randomness have them create two independent Source sources of Randomness not the same way but two independent two somehow independent uh ways of generating Randomness and put them together into this Randomness extractor and the output uh so let's say they have some in entropy you you're actually in a

better better better spot there could be other things that that we can do but I think this is a very lwh hanging uh fruit that we can do in modif modifying the way we do our setup ceremonies in increasing our chances of being closer to the ideal uh way um setup to the ideal output we need from setup ceremonies um like I said this is this is a direction and and I think we can uh the I'm happy jam on the exact uh uh uh exact two Source extractors that might make sense but um I'll pause this part of the uh this part of the question for

now and now let's go on to the next question um so trusted setup again right here is Imagine This great Ideal World where there is this one one truly Universal setup parameters that all proof systems can use right wouldn't that be amazing uh can we even get there this is the question so let's start by asking why different proof systems have

bespoke um setup parameters right reproof system has uh um different par set of parameters and this this is this is our ideal goal just this is our ideal goal where there is one set of parameters for All Pro systems anyway um why do they have bespoke uh set of parameters and that is because so if you if you think of um uh if you think of the way we are constructing proof systems these days they're there is there is an inner proof and an outer proof right an inner proof uh does this really hard lifting of maybe either

starting with uh starting with a very easy to use uh language that's how you represent uh your competition and and you generate a proof uh for that competition but you don't worry about the uh about the efficiency of verification or the size of the proof in that stage and then then on top of it you put this wrapping outer prooof like gr 16 that has good uh ontain verifiability this is this is a typical there are many uh uh there are many good uh uh proof systems that don't follow this right but but let's focus on

this huge class of uh proof systems that follow this um follow this trend so um having said that why is it that different proof systems have different why is it that different proof systems need different uh set of parameters it is because so it's it's the gro 16 layer that that need set of parameters right H look at this outer layer the outer layers Pro is proving verification of the inner layer and because the verifier of the inner layer changes across

different proof systems what this the the computation that the gro 16 Pro is doing changes across different proof systems and therefore your set of parameters need to be different across different proof systems right this is the reason why different proof systems currently um need bisoke setup so how do we get around this problem can we is there a way to go towards truly Universal setup and uh let's in this talk we will explore the direction we will we we will um eliminate certain natural approaches and we will land at an approach which I

think is promising um what if we start with something like flan that uh doesn't need any trusted setup so here are the two issues right if the outer layer is flun um the computation that this flan prer needs to compute you you look at that competition there are two uh ways of doing that competition either with the custom Gates that flan or plon has the custom Gates or without the custom Gates and and and representing the entire computation in

uh in an in an arithmetic circuit addition multiplication arithmetic circuit if we go the custom Gates route then the outer layers verifier also depends on that on on those custom Gates and that is not good for on verifiability I think I think we shouldn't budge from our our goal of of onchain verifiability being independent from the computation being constant from the computation being and being like gr 16 um I think let's let's set that in stone and now what can we do uh flan doesn't help if uh we start with custom Gates as the way of representing

computation for the for the prer in the outer layer what if we do it just with addition and multiplication it's very likely going to be very very very hard with with huge circuits and it may not be a feasible Direction can we do better what if we go through bulletproof based Direction like uh bullet bulletproof IPA uh uh polinomial commitment Direction so here the um here of course there's no trusted setup that is great no pairing which is great so the no pairing part will become relevant in just a bit um let's just note it there um

and um the problem is that the uh proofs generated by bulletproof uh proofs generated by IPA are are not as small as uh it it not not as small as gr 16 proofs it's way far from being there it's not even constant so so um this direction also has some problems what if we do two level smoothening so you I I use smoothening as a to to continue with the with the image uh that I have here in representing uh provs and

verifiers um and uh okay so we start with uh um the inner Pro how about we put Bulletproof on top of it and then put gr 16 the gr 16 so here here is why this could make sense I I could be proven wrong after this talk if anybody sees why this may not work I would love to know but but as far as I see I think it is promising and here is why so you start with the inappro you put Bulletproof on top we have the limitations that we just talked about which is the which is the uh proof generated by bulletproof isn't

small enough but it is not as big as where we started initially from the innermost proof um so we are getting better now what if we put gr 16 at the very end but now we are um so so putting GR 16 at the very end is now a little bit easier uh because um because you can represent all the um because um yeah okay uh there there are a few things going on in my mind one um one reason why this might make sense is that so

bulletproof and Gro 16 uh bulletproof doesn't need pairing Gro 16 needs pairing you can use a half pairing cycle and uh the pr in the outer layer is is it isn't as huge as before so it's even in a we are in a better situation in in the total proving time um so yeah this might work uh is my thinking um and uh the bulletproof verifier we can have it in a way where it it it is uniform like with different proof systems it doesn't change um yeah these are these are the reasons why this might be a good direction I know we are getting close to

uh the end of time but I'll I'll pause now um but summarizing two questions that seem interesting to consider and to dive deep and research and figure out a solution for are how do we have a trusted setup that is truly Universal across multiple uh proof systems to help alleviate the oper operational hardness of of so of of doing this it's it's it's operationally really hard timec consuming uh error prone um there are so many good reasons why I think this is a good aim good goal to aim at and the other question we talked

about was how do we have um a trusted setup that is tightened up and doesn't have uh the what can we do to tighten up setup ceremonies um give the fact that the the the participation inputs don't likely have highest men enthropy I'll pause here thank you so much thank you vanish so we have a few minutes for questions so are there any questions from the audience for vanishri please raise your hand if that's the case don't be shy come on we can wait yeah take the mic

please so that pleas record it uh how I mean so I'm assuming this is just an idea for now right yes just an idea I don't know if any of this will even work out maybe maybe maybe we will figure out that this direction is flawed but I think it's I think I think it's a start of a direction and and you must have an idea of maybe a sketch of how you would maybe what would be the first step in experimenting whether this would work or not what would be the first thing one would have to do what would be the first like to actually like just uh implement this what would be like you must have some sort of a sketch in your head of like what are the first things that you one should be

doing SK so to make sure I understood your question correctly how do we go from idea to practice go on last time what's a good experiment to prove this this idea that that's what I think this specific one I think we just need to go very deep and probably test this for one proof system and see I I think we just need a lot of double clicking in each of these parts maybe there are new nuanced uh parts that I'm not that that that is not

visible just by looking at this approach um um like for example when I started thinking about this uh I was thinking flan and so when I started thinking about this um I would I suddenly realized that how do we do um uh what is the what are the right uh tic curves to use bulletproof in Gross 16 and you know there there are things like these that are that are that are not visible from from just the idea phase so I think we just need to double click and see and uh and uh uh and figure out whether this is the real

Direction I think some someone just needs to put like a lot of time in making sure that this this works there is no experiment or anything it's just I think I I think we just need to write down the whole protocol and I would love to collaborate with somebody if anybody is up up uh for leading this okay thanks are there any other questions from anyone is it the raised hand no okay uh okay well if that's the case uh thank you very much vanish so we're just

going to take break and then