ZK7: Efficient Private Delegation of zkSNARK Provers - Pratyush Mishra - Aleo

Transcript

[Music] i'd like to invite the first speaker to the stage pratush from elio who's going to be talking about efficient private delegation of zk snark approvers welcome pratush [Music] okay all right hi everyone fantastic to be here and see a lot of familiar faces and not familiar faces also in person okay my slides are up and this clicker might run out of battery but let's see okay fantastic you can see what i'm talking about okay so yeah hi everyone i'm pratyush

and today i'll be presenting our work on delegating or outsourcing zika snark provers in a privacy preserving manner this is joint work with my excellent co-authors alessandro ryan and you know okay let's get started so we all you know no one loves ek snacks here but i'll still quickly recap what they do so zika snack is a protocol for approver to convince or verify that some statement is true without revealing why it's true so hiding some secrets and in a way that um the verify can check quickly right the the succinct proof is very efficiently checkable you can see the stuff at the bottom right okay fantastic so there's many applications of zika

snacks in particular the zk part leaving aside the succinctness you have things like private transactions private smart contracts some of which you know people talked about just a minute ago things like decentralized hidden information multiplayer games and many more right so there's there's a lot of cool things you can do with these zk snarks but unfortunately applying them applying these snarks to these applications you run into one bottleneck and that's proving right we all know that proving is really really really slow so if you're trying to prove that you know the hash is 10 kilobytes uh of data with sha2 then it's going to take like a you know over two minutes but it just takes a couple of milliseconds or maybe

not even that i don't know microseconds uh on your computer right so snarks are slow so one thing you can try to do is just say okay i'm not gonna run it on my phone i'm just gonna throw it off to the cloud and have some powerful machine run it for me and give me back the result after you know running the prover in some amount of time and you know if your computation is particularly large you can even do things like use a cluster like a spark cluster to run your computation and this is work there's a paper called dizzy which shows how to do this right and you get very nice scalability okay but the problem with this with all of these techniques is that you reveal your secret information to the to the worker that you're using

right that cluster or the individual server learns your secret witness which you wanted to keep hidden okay so idly we'd we want to outsource proving but with privacy we want to hide the witness while still not doing the work of generating the proof right so what we want is a delegation protocol or a scheme where the delegator can obfuscate the witness before sending it off to the cloud in some way and then there's maybe some interaction between the cloud and the and the delegator and in the end the the delegator gets back this proof that they can you know give to whoever they want

all right so what we want in term from these delegation protocols is first it should be efficient right it should be much cheaper to outsource your your proving to the cloud than it is to do it locally because otherwise there's no point right uh second the delegator's witness should be hidden from the workers this is the privacy goal right we don't want to reveal the witness again otherwise we would just do it on our machine okay now the problem is that you know straightforward approaches to this using mpc and like fhe are really heavyweight so when you try to use like cryptographic tools you your total runtime is going to far exceed the running time of like doing it on your on your device so you don't want to do that so what do you so okay so if you want to just use a single server you

can't do that so maybe what you can do is you can sort of relax the security guarantee a little bit and say we only care about threshold privacy so i'll outsource my proving to you know a set of machines and they can interact and you know you know compute the proof for me via some sort of cryptographic protocol and the guarantee that i want is that now as long as one of these workers is honest and doesn't collude with the others my witness is hidden right so as long as one machine is uh behaving honestly yeah you're fine so you think maybe you know one of those machines is aws one is uh you know google cloud and the other one is azure or something like that right so they might not be colluding with each other uh for competitive reasons

okay so this is sort of a more achievable looking goal so let's see what we can do okay so what we do in this in this work which is not here online is construct exactly these kinds of uh delegation protocols for zika stock approvers for these popular class of zika snacks which rely on polynomial iops so things like planck marlin sonic every you know sort of recent work on zk snacks falls into this category and we show how to construct delegation schemes for this entire class of snarks by constructing first delegation schemes for polynomial commitments which i'll talk about you know in a couple of minutes and then for the polynomial iop itself

and then finally a compiler which takes these two delegation schemes for the sub components and constructs the delegation scheme for the entire zk snark all right so yeah it's not just a theory paper because otherwise you know i have a very concrete motivation it'd be kind of disappointing to say okay i'm done with the proof so we actually implemented and evaluated our protocols and we have a bunch of metrics that we'll talk about at the end of the paper but the tldr is that when you're delegating from your phone to this cloud server um generating the proof end to end takes 26x less time right so that 140 seconds becomes like five seconds so this may be more reasonable if i have my math correct

okay all right so the straw man so let's see how we can do this the straw man technique is to use what's called mpc or multi-party computation this is a cryptographic technique which allows a bunch of um i guess parties which i don't want to collaborate which have some interest in keeping data disjoint from each other to jointly compute on their on their data in a way that uh you know they get the result but no but no party learns any information about the other party's inputs right so every party's input is kept secret so basically it's a way to do distributed computing on secret data all right so you could just throw this you know generic crypto tool at it um but the problem is that off-the-shelf

mpc tools are very very very very very expensive um yeah they also require expressing your prover algorithm as uh as this this arithmetic circuit which you might be feeling familiar with in the context of zika snarks very similar thing happens for these npc protocols yeah but the problems being that the prover circuit itself ends up being again very very large for any of these ecosnacks that i talked about all right so why is this circuit large so we'll as i said we'll focus on this class of snarks which rely on polynomial iops and polynomial commitments so polynomial and iop for those who are not familiar is an interactive protocol between approver and a verifier where

the provers messages are polynomials okay so sort of you know this includes sonic mullen basically all the protocols i talked about on the slide there and the other component is what's called a polynomial commitment scheme so this key this is a thing a primitive you know anna i guess had very useful descriptions but basically it allows you to commit to a polynomial and then later prove that the evaluation of that polynomial at some point is correct is is the claimed evaluation okay and again we have many insta instantiations of these such as the kcg10 one uh things based on inner product arguments dark high racks bunch of things okay even fry right

so the zika snack prover circuit consists of sub-circuits for both of these components and both of these are like fairly heavy cryptographic objects right so the two problems end up being is that first stitching together these um circuits for each of the sub components is itself expensive because you have to do things like reason about different finite fields and secondly the sub-circuits as i said can themselves be quite complex right so we want to simplify both that plus sign and the in the two sub like little boxes inside as well so let's see how we can do it let's see how we can um i guess start solving part one so before i guess i dive in i'll do like

a very quick very well-wind recap of how you can construct these because this will be useful in the construction later i think i'm doing okay on time but yeah let's see all right so in these snarks which rely on these polynomial iops what you do is uh the zika snack prover runs the polynomial iop prover and the same thing for the verified runs the polynomial iop verifier uh the approver it produces some polynomial you commit to it using the polynomial commitment send over the commitment uh the verifier runs the piop verifier you send back the challenge whatever you repeat this for a bunch of rounds you get some commitments okay and then comes the query phase where you have to prove that these committed

polynomials when you evaluate them at some query set you know the evaluations are correct okay this is a worldwide overview you don't need to understand too much but just basically the takeaways that you produce the polynomials and you commit to them okay and then you later prove that those committed polynomials evaluate to whatever you claim they evaluate okay all right maybe i should stop for questions at this point any questions about anything no okay i'll go on feel free to stop me uh within i guess time bounds all right okay so this is basically the the structure of these zika snarks

um the other building block that we'll be using before we dive in is this notion of um additive secret shares you might have heard of shami's secret sharing this is a very simple version of that which basically says that you can take your message and split it up into like n chunks or shares such that as long as you don't have all n of them you don't leak any privacy even if you have at most n minus one of the secret shares for a given message you can't learn any information at all about that message okay on the other hand if you have all then shares you can combine all of them and get your message back and the other interesting property that we'll care about is this thing called homomorphism or additive homomorphism which says that if i have a secret share

of a and a secret share of b i can just add those secret shares and get a secret share for a plus b okay um so this is called additive form of them in cryptography it'll be useful in just a second all right i think i'm speaking fast i'll try to slow down a bit right so let's uh you know handle each of our problems one by one starting with this issue of combining sub-circuits right so the problem that we had was we're just trying to take the zk snark prover as a monolithic object and throwing an npc protocol at it right but actually our zknock prover has this underlying structure so let's try to exploit that so we'll take advantage of the this modular nature of the prover and say instead of doing a monolithic mpc

we'll you know construct an mpc for delegating just the polynomial iop and we'll combine it with mpc protocol just for delegating the polynomial commitment scheme and this will give us our protocol for delegating the zk snark all right so this is the high level structure um i'll talk a little bit about you know what this combining step looks like and then we'll dive into um how to actually construct each of those uh boxes on the your left okay my left whatever okay all right so let's see how we can do this so let's say we have these two boxes as given right uh how we start off with is the is the

delegator sends secret shares of the witness to each of the like let's say there's only two machines in this example right to each of the two worker machines then what they do is they take these secret shares and they invoke this mpc for the piop approver and get secret shares of the first polynomial so the polynomial produced in the first round for example okay then what they do is that um they'll take they'll invoke the mpc for delegating pc schemes uh and get the commitment for that polynomial shares of the commitment for that first round polynomial okay and then they can do the same thing as the as you saw in the in the sort of the standard snark they just repeat these two operations over and over again in

sequence until they have this vector of polynomials and vector of commitments corresponding to all of the rounds and then they can run the sort of proving step to produce the evaluation proof for these commitments right okay so it's the structure is basically the same as that slide earlier we just replace sort of running the iop prover and the pc scheme committer locally you just replace that with these mpc protocols we're doing the same okay so the high level structure is is very clear okay so at the end of uh and at the end of doing this now these workers they have shares of the final zk snack proof right they have

shares of the commitments they have shares of the evaluation proof and they have shares of the evaluations themselves so they send this stuff back to the delegator who can combine these shares and recover the actual zika snark proof which you can go use in whatever application it wanted to use okay so that solves problem one any questions on that yeah wait actually actually i wonder yeah so you're going to do talk question talk questions i can do either way we have to get it on the mic for it to work so sure okay sorry i should have asked before so my question is how you compute

challenges so yeah so that's a very good question so what you can just do is you can select actually that previous diagram i lied a little bit you can actually it's okay just for the commitments to to be sent to all to one party so this fellow on the bottom can send his share of commitments to the worker on the top right and it can combine it and then you can get the actual commitments in the clear and run the random oracle on those um you could also send it back to the delegator and the delegator could give you the random oracle challenge that's another idea that you could use we have a different couple of different variations in the in the paper which is not online yet yeah very good question i think there's

another one here um for so for something like planck you'd have to compute something not at it like you'd have to multiply two polynomials together for example to get a polynomial later around um so the diagram showed only interaction between the servers but i'm imagining that you would there would be continual interaction between the phone as well right that depends again on the setting i'll get into it when i talk about how you actually implement both of the boxes yeah okay very good questions all right so that's i guess a high level overview of the compiler which takes these two you know delegation schemes for the underlying

uh components so let's see how we can actually construct these underlying delegation schemes all right so and that's solving the problem of yeah getting cheap sub components okay so we'll start off with constructing delegation schemes for our piop provers right so that's what we want we want something that says given a secret share of the state of the approver at the given point at the given round give me the polynomial for that uh for that round right uh our secret shares of the polynomial for that round okay now the operations before we can talk about how to speed this up right or how to implement it efficiently we have to figure out what operations are actually done by these piop provers

and by and large for all of the stocks that we care about i think um these operations are just basically these four you want to evaluate your polynomial over some multiplicative subgroup uh your evaluation domain if you're if that's a better term for you um you want to divide your polynomial by some vanishing polynomial of that same subgroup you want to do some affine operations you know additions subtractions adding a constant or something and finally you might want to do some polynomial multiplications right between secret shared polynomials so the good thing is that the first three of these they can all be implemented via linear operations on your secret shared polynomial so this doesn't require any interaction between

the workers at all right so this is this is very efficient to do you just do local operations on your polynomials and you can get the secret shares of those results but for polynomial multiplications that's not quite true to multiply two polynomials uh of say degree d what you have to do is this is getting a bit technical but bear with me use an fft to get the evaluations of your polynomials over your subgroup or your multiplication or evaluation domain you do a pointwise multiplication between these evaluations and then you do an inverse fft to get out to interpolation to go from these evaluations back to coefficient form right there's a whirlwind overview of

polynomial multiplication now the nice thing is that steps one and three are again linear they they're just ffts so they don't require anything any sort of secret multiplications but unfortunately for us step two is a multiplication between two secret shares right and our secret share is they have additive homomorphism but they don't have multiplicative homomorphism so you can't just multiply two secret shares and expect to get a secret share of the um of the product but thankfully in our setting and okay normally in like this is this key sticking point a lot of mpc this handling multiplications or and gates is the is the very expensive part of

mpc protocols but in our setting we have a helper we have the delegator so what we can do is if your workers have secret shares of two things they want to multiply they can just send those secret shares back to the to the delegator who can just combine the secret shares compute the product and send back fresh shares of the product right so we're really making we can leverage this um delegate and the key thing here is that field multiplications are very cheap right so i'm not asking the delegator to do something like a multi-scale multiplication which is expensive and kind of would defeat the purpose of delegation right but these field multiplications you can do them in like a few nanoseconds right

they're they're quite efficient all right so this is how we can leverage the delegator to get um very cheap polymer multiplications with just one round of interaction with the delegator and actually in the paper we have other techniques that you can use the delegator doesn't even have to be around during the execution of the protocol you can just send some pre-processed material beforehand and then sort of go offline and just receive the proof at the end but that's um for the paper okay so this is how we can uh you know very efficiently implement like 99 percent of the operations that happen in in modern zika snack or piop approvers all right so that handles

the first component what about delegating pc schemes so i'll particularly look at the kcg10 because uh polymer commitment scheme because that's the most popular one and recall that we have we want to do two things we want to first take a secret share of a polynomial and get a secret share of the commitment and then given the secret share of the polynomial and an evaluation point i want to prove that the committed polynomial actually evaluates to whatever the claimed evaluation is right so the two things i want to do committing and opening um in terms of committing the cool thing is that the commitment scheme is linearly homomorphic also so

a commitment to the shares of the polynomial is a share of the commitment to the polynomial yes i got that right okay so just assume that the you know your vector of the shares has this structure then a commitment a share of the commitment is just the standard thing that you would do with kcg which is compute the multi-scale multiplication right so there's really almost no difference from the actual kcg algorithm and the same thing um when you actually want to produce the evaluation proof you compute your share of the witness polynomial which is this quotient thingy right uh yeah whatever that expression is um and the cool thing is that this also

does not require any secret multiplications this is a linear operation so basically the takeaway is that the complexity is literally the same as the standard kcg you know on non-shared or non-secret shared polynomials so committing to a secret shared polynomial and proving its evaluation is is literally the same there's no difference here so that's i guess wraps up the two components okay yeah i just want to say there's a couple of other recent papers i've appeared which have similar techniques uh to the stuff that i've mentioned just now in different contexts not for delegation but for like mpc over proving over shared data okay so there's tons more optimizations

in the papers um you can really take an advantage a large advantage of the uh the setting of you have a trusted third party in some sense to do the expensive operations a few of the expensive operations for you um okay this is working again all right so we have the optimizations on the crypto techniques as well as on the system side um so it when the paper is online i would encourage you to read it so we've solved at least hopefully both problems one and two so the question is okay i've talked a lot about theory and things of polynomials and all this garbage okay but the question is does this actually result in concrete performance

improvements can you actually take these protocols and get something and implement it and get an actual speed up for your application today and the answer is thankfully yes we implemented this uh using arc works it's me so i would do macbooks obviously um but yeah so we have delegation protocols for kcg we want to implement it for the inner product argument scheme as well for the marlin piop but it should be fairly straightforward to extend it to things like planck whichever variant of planck you want um and you know by compiling by putting it together with our compiler we get a delegation scheme for the marlin snark okay in terms of actual concrete performance we

evaluated these schemes in like sort of three different settings a laptop which has very fast internet access and here you can see there's a latency reduction of 9x compared to normal execution but something that's really interesting is that i guess the last two columns the first one says how much time does the delegator actually spend actively computing something versus waiting waiting for stuff to be computed right and the answer is that the computation active computation goes down by 600 times almost so this is like a massive energy savings massive you can do whatever else you want on your computer in the meanwhile another benefit is that you can actually um prove much larger instances within the same memory budget compared to uh if you were proving it locally right so

this is 256 times larger so if you could prove something of a you know size a million on your computer now you can outsource uh the computation and prove a circuit of 256 million constraints which is kind of insane right okay um the other settings are a laptop with the you know standard home internet and here we see sort of less impressive numbers because the uh communication overhead back and forth within delegator becomes kind of problematic and the final one is uh doing the same experiments on a mobile phone and here because the phone is so much weaker even you know despite the slower internet you're still able to see quite large performance improvements all right so that sort of wraps up my

presentation i think yeah so the paper is coming soon to a new print near you and the code also hopefully yeah fantastic thank you everyone [Applause] [Music] two questions up front uh hello so i have a question or maybe a suggestion how to possibly make your uh this fantastic thing is like 30 times better so you know actually in many uh proverb use cases you know well then the number of impossible possible witnesses is is is small for example recall like z cash or tanada

cash you have a tree having a tree like to the 32 layers uh 32 layers 2 to the 32 possible leaves and to every leaf you prove that you know a primitive but actually you can delegate uh all possible uh paths from a leaf to the root to delegators they compute like two to thirty two leaves and you retrieve one of them using private information retrieval for example and you yourself you compute only a proof for like this tiny thing which is 30 times smaller and this one you can delegate using this thing so you can but if you are able to combine their proof for like almost the full path with your proof or hash primitive that you

can make it like 30 times faster yeah so that's a cool technique uh does that require sort of splitting up the circuit um into something that the i guess you pre-process and then later on yeah i think so that the i guess the motivation of this work was to just say i don't want the application developers to do anything for their applications you just want to you know literally like you can use any existing verifier to do this but yeah i think i think that's a cool technique and yeah there's a lot of application level optimizations that you can also do combined with this and other techniques like your idea yeah yeah hi maybe a trivial question how easy is it to find faulty or malicious workers how easy does it find a faulty sorry

what faulty workers like yeah so in some sense the result of the computation is self-verifying right like if the worker is cheating then you'll get an incorrect proof right otherwise you sort of broke in the soundness property of your zika snark right um so from that perspective it's it's like at the end you'll know when you have something that's correct or not uh from a liveness perspective it's not like this protocol at least in like the instantiation that we have in the paper it's not the greatest because uh one of the workers could just decide to like drop out and then you're waiting for that worker to finish so you might have a timeout or something um so they can do like a denial of service attack um but otherwise as in terms of actually influencing the correctness of the proof

there's not anything they can do that's not that's not detectable any other questions uh i was wondering sorry i was wondering does it this ability to produce shares of the polynomials does it also presuppose that the circuit itself has been somehow cut up into um shares of the circuit as it were and is there what is the communication between the different workers basically so that's linear in the circuit size it's not uh it's not like uh something like dizzy or you know like sort of each worker is not doing a chunk of the computation they're doing basically like the full prover computation with some caveats

which would be very interesting to see how you could combine techniques from dizzy with with this work to see how you can reduce the load at each worker that'd be very interesting future work i think yeah great questions i think there's a question all the way back so kcg polynomial commitment seems to be quite npc friendly right uh what if you use something that utilizes stuff from fry like fry based polynomial commitment yeah there's a couple of things that's a good question there's a couple of things you can do there um so the problem with fry is that it's all hashes right so there's no additive

homomorphism that you can leverage what you can do is at the very leaves you can say i'm going to commit my merkle tree is going to be built over additively homomorphic commitments for example um and then the workers exchange those commitments and at the end somebody builds a merkle tree over the commitments so you'll have commitments to the secret shares which are secret shares of the commitments right um unfortunately from a delegation perspective that doesn't make too much sense because the cost of computing those commitments is very high uh much higher than the merkle tree cost itself so you might end up with like a overall slower approver but it might be helpful in other protocols like we just care about privacy and not actually delegating there's also other things i think the

ob 22 paper they have another protocol where the proof size grows logarithmically with the number of uh workers basically build like a mini merkle tree at the leaf consisting of all the workers shares you can do that also [Music] uh sorry what who who just asked that question can you say it into a mic i can i can repeat the question also yeah so the question was just can you uh for this you know fry technique can you actually uh use mpc friendly hashes but i think it doesn't work you you would pay a large cost just because the um

you'd be running your hashes inside npc which is expensive we wanted to avoid running any expensive crypto in like off-the-shelf mpc okay there's another one over here okay um so the uh depending on how you know how many workers you pick the global energy usage may be higher and then we'll go up yes so what do you think is a reasonable trade-off in terms of you know total energy usage and uh i think it depends on like sort of the cost of privacy in your application and the cost of privacy to the user in particular like if i don't care about you know particular zcash transaction somebody knowing where it's going then i can just do it

on my computer but if i'm like you know a very paranoid person then i might and but i don't have a good computer because you know i don't trust powerful computers so then in that case i might outsource and be willing to eat the additional energy cost um there are things that you can do to optimize it so that the work at uh like all the workers are not doing like all of the protocol all of the prover work um in particular if your protocol has this sort of structure where parts of it are witness independent then only one worker has to do it so for those things it's not any more inefficient compared to running it on your on your own device so for example marlin has that structure any further questions

all right one at the front we're almost front um some practical one when you when you compare the phone implementation that was also arc quirks yeah okay yeah i mean i mean imagine you could have like a more optimized implementation but i think sort of any optimizations that target your phone would also hopefully translate to your server implementation thank you anyone else if not then thank you so much for touch for the talk thank you so much everyone