zkStudyClub: Collaborative zkSNARKs (Alex Ozdemir, Stanford University)

Transcript

uh welcome back to uh to zk study club in this edition we are welcoming back alex asamir who's uh who's previously spoken here on zk study club and today he's going to be telling us a little bit about his recent work with dan bonay at stanford university uh collaborative zk snarks so alex over to you yeah so thanks for having me back alex um and uh last time i think i spoke about compiler infrastructure if i recall correctly uh so today is gonna be a bit of a change of pace we're gonna talk about a new cryptographic primitive that myself and dan have been working on that we call a collaborative zk snark which allows one to write zero knowledge proof of zero knowledge proofs about secret data that is distributed among many parties

um and so by the end of the talk you should understand what the collaborative zk snark is both in terms of syntax and security and you should also learn something about how efficient collaborative zk snarks can be how surprisingly efficient they can be but first i think it's good to start with the basics um perhaps no one needs to be reminded why zero knowledge is useful but i'm gonna do it anyways um so zero knowledge allows you to solve all kinds of problems but one classic problem one classic security problem that zero knowledge is useful for solving is the authentication problem in authentication there's lots of different ways of doing it but essentially every authentication mechanism boils down to having some client show that they know information that only they should know

that information might be a password it might be a secret key might be something else and during this process it's important that the client not reveal that secret information because if they were to reveal it directly then they could be impersonated in the future um and so they need to show that they know that information without actually showing the information itself this is a zero knowledge proof and indeed a zk snark which is sort of the general purpose super powerful zero knowledge proof can solve [snorts] this problem it's a little bit overbuilt but it can't solve the problem however z case snarks cannot solve all problems related to zero knowledge um in particular they struggle when the secret information is not a single secret that one party the client has but when the secret information is instead

distributed among many parties and that actually happens all the time so let's consider one example money laundering if we want to show that some entity eve has obtained the ransom paid by colonial pipeline that amounts to showing that like in the global graph of transactions there's a certain kind of path from colonial pipelines ransom to eve um and give me a second but yes and in this instance the uh in this instance it's it's not simple enough to just look at the graph because uh there's no single entity no single bank that actually has a view of the entire graph different entities different individuals different banks are where are different transactions um so in this

diagram color corresponds to the entity that knows about the transaction and showing that this path exists would require the green entity the blue entity and the magenta entity to collaborate in order to demonstrate that path exists and if they wanted to do this without revealing um exactly which transactions they know about or what those actions are they would need to somehow be able to collectively write some zero-knowledge proof this this path exists uh money laundering and general financial applications are not the only scenarios where this happens another example from healthcare you might imagine that there are several hospitals in some kind of network together that want to show that they're charging fair procedure prices that the the price for some procedure some

particular procedure doesn't vary too much depending on on race or on some other protected class and so what they're trying to do here is compute an aggregate statistic over the uh details of what procedures they offered which individuals at which prices um and that that underlying data uh those those procedures that's information that's that they probably don't want to share with one another in fact they might not even be allowed to um like the united states hipaa would probably prevent them from doing this um and so if they want but if you know if nonetheless they want to convince the public that they're charging fair prices then they need some mechanism to collaboratively prove that the aggregate statistic um it has some favorable value so the point of today's talk is

basically to build uh tools a collaborative zk snark that's going to allow us to apply zero knowledge in the latter two scenarios and in the case where the secret data is distributed among many entities um and so pursuant to that goal um there will be four parts first i'm going to go over zk snarks forgive me if you understand them already we're going to focus in particular though on why they do not apply to distributed secrets that's going to motivate our new cryptographic primitive a collaborative zk snark um we'll learn both about syntax and security and then we'll go into how we construct collaborative decay starts so we provide sort of a theoretical template for how to build them and we apply that template to build a number of different collaborative dk snarks

and then finally i'll tell you about our implementation strategy how we implemented them and how they end up being surprisingly efficient so um giving up the punch line at the beginning we're going to see that collaborative zk snarks and in the right situations can be just as fast to to write proofs um to prove as conventional zk snorks so despite the fact that there's some kind of multi-party protocol they're not actually going to be any slower which is which is kind of surprising okay so that's the order of events um i'll pause right now in case anybody wants to ask the question and also because i'm thirsty [clears throat] uh any questions from anybody if not maybe uh yeah we just let's roll on well just actually i have

a quick one on the healthcare one like the case that you had there was not about the data of the people right this was the prices because i know the data of people has been floated many times as use cases but today seems kind of impossible to do just because of the politics do you feel like the prices would be a better like is there a reason why you chose more like price checks so i i um i didn't choose price checks for any particular reason um and i think that the the cool thing about about a collaborative zk snark is it's going to allow you to to write a proof about any data that you want whether whether it's perhaps the health outcome of the procedure whether or not the procedure was successful um or whether it's the prices um

and um you know sort of the cool thing here is we're using the notion of zero knowledge and that means that whatever it is that the underlying data um involves that's not going to be revealed okay so then let's charge ahead um let me minimize the okay so um the background zk snarks um so zk snarks though these tools for writing zero knowledge proofs we needed a formalism to understand what it means to keep information a secret and um could you uh sorry just a quick reminder if anyone's not muted could you

just please meet your mics thank you okay i think we're good so yeah the formalism that we're going to use for the purposes of today's talk to understand secrecy is the notion of a witness relation which is fairly simple it's just x w pairs a set of valid x w pairs we regard the x as uh public and the w as secret and we imagine that there exists some prover that knows both that knows the public data knows the secret data perhaps the public data is what the average health care what the average price of a procedure is and the the secret data is how much every single individual is charged and then there's a verifier who knows just the public information and is wondering whether or not this the secret information exists um that makes

the public information valid and sort of a strongman way that you can convince the verifier that's what this exists is you can just give the witness to the verifier and then the verifier can check um but there are two downsides here the first downside that's not so relevant to today's talk but is good to know about is that um in some cases the witness might be very large so and you know in the case of healthcare this is like all the procedures that you did on everyone that's very large and it seems like sending all of it to just communicate the single bit that my average was computed correctly is perhaps overdone uh and then the more important downside is of course this is not private this does not keep the witness secret and so basically zk snarks they just allow us to implement this workflow while keeping

w secret they're sort of a layer of indirection you don't send over the witness instead you feed the witness into a proving algorithm you get a proof you send over the proof you verify the proof and you get a number of desirable properties so so sort of a key property is soundness if if pi uh if you if the prover can come up with pi then w should exist zero knowledge pi should reveal not reveal nothing about w succinctness pi should be very short very fast to verify non-interactivity pi is just a single message the prover sends to the verifier it's not some kind of interactive conversation uh there's one sort of weakening of soundness this is a system that's allowed to be computationally sound where okay if pi exists as long as it's hard to compute pi

uh and then finally a strengthening of soundness knowledge soundness um a valid proof should convince the verifier not just that w exists but the prover actually knows it so this is sort of a laundry list of all the properties that ck snarks give us the most relevant one for today of course is zero knowledge um so the fact that this proof does not reveal the underlying secret information uh and you can use um zero knowledge proves to do all kinds of interesting things earlier i had mentioned authentication as one problem that can be solved with zero knowledge let's look at how you might begin to build an authentication protocol from zero knowledge proof it's kind of a simple idea you imagine that the client is going to be the prover here they're proving that they

know secret information the verifier that's going to be played by the server who wants to be convinced that the client knows the secret information the public key that's x that's the public data the secret key that's the secret data and the the relation that we're interested in here is whether or not the secret key public key pair is a valid key pair um so that that is like whether or not the secret key actually corresponds to the public key and in the proper way defined by the public decryptor system um and so you can you can just use a zero knowledge proof to solve this problem to show that your key pair is valid um and you know the cool thing is because of that that knowledge soundness property because the proof establishes not just that the secret key exists secret keys will always exist but the

approver actually knows it um this uh this proof is sort of enough information for the verifier to decide whether or not they should authenticate this client because it actually establishes that the client knows the secret key uh i will make a small note which is that this scheme is not quite secure it's vulnerable to replay attacks but this gives you a sense of how zk snarks can be brought to bear on an existing problem in security um so this is what you can do with vk snarks how do you build them the folks in this call know a lot about that and i'm really not going to go into it today because it's very complicated and it's kind of orthogonal to what we want to talk about which is collaboration but i'll give you the names of the zk snarks that we're going to be building

on so in terms of zk snarks based on on pairing friendly elliptic curves we'll be building on grot 16 marlin and planck the latter two will be instantiated with kzg as the underlying polynomial commitment scheme um and and these are all all good zk snarks because they're very efficient essentially but they're also vulnerable at quantum attacks and so the last one that we consider is a zk-snark built from hashing and from just facts about coding theory called fractal so we'll also be building on that okay and then you know the note there are a lot of ellipses on this on this slide um i'm not listing all the zk specs in the world um these are just the ones that we're going to build on today

i mean so even though these systems are so great as i said before they have a shortcoming and that shortcoming is um what happens when there's not a single entity that knows all the secret information that's relevant to the proof what if that that data is distributed in the custody of many entities which entity plays the role of the approver they could like decentralize all the secret data and you know give it to party a and party a could be the proofer but now party a learns everything and we don't want that we want to try to keep uh we don't we want the parties to be able to write zero knowledge proof while maintaining custody of their secret information um and so that's that's sort of what the primitive that we're here to talk about today does so a collaborative zk snark um in terms of what a collaborative case

market is it's actually pretty simple it's a very natural generalization of a conventional dk snark and in the for conventional gk snark you've got approver they've got a a secret piece of information we call it w and they produce a proof pi sub w that establishes something about that secret for a collaborative zk snark we're going to imagine that there are a collection of provers in this diagram three that each have a different piece of secret information w1 through w3 in this diagram and the idea is that those provers talk among themselves they run some kind of interactive protocol that the output of the protocol is a single non-interactive proof pi sub w but now it's a w vector so this proof establishes something about the vector

of witnesses um okay so i see something in chat from victor is this also you ignore that for now if you want you can answer something at the end yeah um this is a totally great question and i am going to ignore it for now because i think we're going to like start talking about this kind of soon uh but yeah yeah so how are we going to construct this you can bet that in some sense at least nbc is going to be involved so yes the idea is that you know the provers they talk among themselves that they they interact um run some multi-party protocol and at the end you have this non-interactive proof that the verifier can verify non-interactively and and now this proof is establishing a joint property of all the secrets um which you can think of as being a

property of the vector of secrets so when you make this um generalization oops um when we actually think about sort of how the syntax is changing it's not changing too much the setup procedure of the zika snark is syntactically just as it was before uh the verification is syntactically just as it was before the only thing that changes is proving we no longer have a proving algorithm now we have a proving protocol where all the parties are given the public parameters that define the proof system and they're also all given x the public data and then parties uh p1 through pn provers p1 through pn each have a different witness and so then these provers are going to interact and

they're going to produce this proof uh so syntactically this is this is sort of straightforward um in terms of the security definitions it's a little bit more complex but still not too bad one immediate thing that has to change is our notion of zero knowledge because now um if i'm a prover participating in this protocol i don't just have to worry about the verifier learning things that shouldn't i also have to worry that the other provers might be learning information that i don't want them to learn so i have my own individual secrets every approver does and they don't want that secret to be learned by the other approvers and so the way that we formalize this is with a property that we call t zero knowledge and it says that any adversary at a high level any adversary controlling at most tea provers should

learn nothing about the witnesses of the other provers beyond whether or not the witnesses are collectively valid um and so i'll just to give a diagram if we've got a sort of a five prover protocol here parties one through five and witnesses one through five and there's an adversary who has corrupted three of these proverbs these three these three provers are colluding and trying to learn secrets about the others if this uh the collaborative zk snark that we're using has three zero knowledge then this adversary should not learn anything about witnesses four or five beyond whether or not the witnesses are collectively valid i mean you know in some sense it's impossible to avoid leaking the validity of the witness because we're writing a proof here so you know if it's not valid the proof

isn't going to be isn't going to uh be successfully checkable um but but you the idea the definition says that you shouldn't learn anything more so how do we formalize this um we use basically the machinery of mpc security definitions um so we imagine that there's an adversary that controls at up to up to t approvers and we require that there exists this simulator that when given the corrupted witnesses and x and that validity bit that indicates whether all the witnesses are collectively valid can simulate the view of this adversary and the idea is that if the adversary's view can be simulated without any of the secret information the adversary hasn't learned any secret information

so this is sort of standard run-of-the-mill uh npc style security definitions um and then as an additional note we do this uh we do our analysis and we specialize our definitions to the explicitly programmable random oracle model so for those who are sort of interested in the formalization one thing that i want to note is that this definition subsumes traditional zero knowledge because you can think of the verifier as an adversary that controls none of the groupers um so you know a system that has even zero zero knowledge is going to be zero knowledge for the verifier um so this is this is in some sense a generalization okay this is another question do individual approvers notice total number of troopers in the set ah that's a

really good question um anna and the answer is yes so so we imagine that the approver might learn how many other provers it's interacting with and in fact in some sense it already knows that because the relation here takes um one piece of public data and then n different pieces of private data and n is going to be leaked there um now one thing that approver doesn't know is whether or not the other entities participating in the protocol are like sybils of one another or really distinct identities and establishing that is sort of out of scope for this work okay so uh good question so this has been our definition of zero knowledge um i'm gonna go on and give the the sort of the other modified definition and then we'll pause for a moment for questions so the second definition that needs to

change is knowledge soundness the fact that the prover knows the witness and of course that needs to change because now there are war provers and the witness has been split into different pieces i mean there's all sorts of ways that you could imagine formalizing knowledge soundness in this collaborative setting one natural formalization would be that prover one knows witness one proofer two knows witness two and so on um so you know in that system when the verifier sees sees the proof and the proof gets verified the verifier knows that there you know there's a prover one that knows what this one and so on um but this is actually not the definition that we formalize so we formalize a slightly weaker definition which says that the provers if they collectively pooled their all their information

they could construct all the witnesses so this is uh this it turns out that this notion of knowledge it actually has a name uh so if you go back to this this old paper it back to my favorite paper in computer science written by halpern and moses um let's see joe halpern and jorah moses at ibm back in the 90s formally this is called distributed knowledge so it's like what you would know if everybody pooled their their distributed information um and so this is this is the definition that we end up formalizing and actually we believe it's a little bit harder to we believe it's somewhat hard to get a more precise notion of knowledge than this because um we're talking here about non-interactive proofs the verifier doesn't interact with each prover individually and fed it receives a single message from all of them and in that setting it's hard to imagine

how the verifier could end up believing precise things about what different provers know because it doesn't get to interact with them individually and in fact actually from the verifiers perspective perhaps this this proof was written by one party simulating all the different provers in its head so getting getting a more precise definition at least in a generic sense is kind of tough um dara has posted this this linked archive that i'm not going to follow up on right now because i don't want to change my screen but um i will follow up on it in the future that's just the help in this respect oh yes fantastic thank you yeah those i would highly recommend that people read it it really is my favorite paper in computer science [snorts] um okay so uh also we do this in the random oracle model and so that means

that we imagine that there exists an extractor that gets to rewind the whole proving protocol which it does by reprogramming the random oracle um this is sort of standard um and and sort of the interesting thing is it sort of generalizes very nicely to a multi-prover setting okay so these are our security definitions i'll actually pause now in case we have any questions about them do you have any um i notice no i don't see any uh notion of like liveness or otherwise like basically saying that an adversary can't uh halt the protocol i guess is that kind of

is that kind of not a non-goal here that that is going to be a non-goal so so we're going to we're going to limit ourselves to proverbs that actually want to produce the proof um it's it's a good question um what a sort of aliveness or like a guaranteed output delivery property would look like for a collaborative proof um there are analogs of this in the mpc literature the term is guaranteed output delivery and you need a strong number of honest parties to make it work out but um yeah no i think it would be an interesting generalization to consider and it's not one that we have considered so far okay so um i have a question um so if you have i i'm thinking of similar

situations for um threshold signatures and in the in that case you may have the problem that if um the protocol is run concurrently um several instances then um there are attacks that wouldn't be in the the single instance case um do the security do your security definitions take that into account uh it's a good question and actually we don't know the answer so it's certainly true that in our experience doing cryptography let's see if the protocol is zero knowledge it may not be zero knowledge under parallel uh composition um that's sort of a protocol to my knowledge that's a protocol by protocol question and we have not answered that for the protocols that we build here that's a

very good question um and and actually also i i would mention this at the end typically but but it's sort of related to your question so i'll mention it now one thing to be cautious of is that engaging this protocol ultimately leaks a single bit of information and so um in an application you want to be cautious about how some entity having some entity be willing to engage in large numbers of these of these protocols with the same secret information okay um so let's let's charge ahead um so i i want to get into the constructions in a moment here um you know this will sort of transform into like a more npc style talk um but

before we get there there's sort of one detail that we have to address which is the class of relations that we're going to support and what we do here is pretty standard we follow what people have done before by supporting r1cs relations and i don't want to go into the details of what rncs is today um but suffice it to say that this is a class of relations that generalizes arithmetic circuit satisfiability so if your computation can be expressed as some kind of arithmetic circuit where all the different provers have inputs to it and there's some public inputs and you're checking whether or not um the output is zero or one uh then then it's going to be covered here i do have the definition if you if you want to look at it but maybe now it's not the time

um but i want to say something which is that we do something even more specific than focusing on r1cs in particular we assume that at the beginning of the proving protocol we already have secret shares of the r1cs witness so we have secret shares you can think of it as every circuit of every wire in the circuit um and and what we're sort of assuming here is that there exists a compilation phase that runs before the proof protocol and the assumption that we're making that's a little bit stronger than what has traditionally been assumed to improve systems and that we're assuming first of all that you can take your general relation and compile it into an rncs relation and we're assuming that compiler also produces a witness extension protocol that takes your general relation inputs and produces secret shares of the r1cs

inputs we believe that assuming this compilation phase is the right thing to do for this line of research because what you want to do is you want to disentangle relation specific details from the proof system and this division achieves that but it's a really interesting question what compiler is going to be able to not only compile general relations to r1cs but also produce these multi-party protocols that can can do witness extension and produce secret shared r1cs witness material um i i actually think that our previous work source would be great for this because it's sort of a compiler that can comprehend producing an npc and producing uh other kinds of relation formats like r1cs um but of course it doesn't have to be cersei and just i want to know that

in general this is sort of an interesting compilation problem but it's not one that we're going to consider today so for the purposes of today we're imagining that our proving protocol is given secret shares of the r1cs witness and the public data and its goal is to prove that that uh witness um demonstrates that x the public data really is in the r1cs relation i'll pause here in case folks want to ask questions about this because this is sort of a lot to digest my intuition is that compilation is hard in general because it's definitely hard in general so actually let's just think about sort of like the worst case scenario which is like a vdf right right [laughter] something that's highly sequential and

it's gonna like so like in general that witness extension protocol it might take a long time especially if it's a very if it has a high multiplicative depth and is like very unfriendly to mpc um and that's in our belief that's probably unavoidable um but the interesting thing that we're going to be observing today is once you have produced um sort of the the the secret shares of the relevant information uh we're actually going to be able to write the proof that you did that correctly very quickly so so is there some general even if it's extremely inefficient way of doing this for an arbitrary statement of doing um the the splitting into shares

so i think one one thing that you can do um is if you could take your um statement and actually express it as an arithmetic circuit that checks it um then you can bring to bear traditional mpc generic npc protocols and use them and you can ask them to like save their secret shares as you go assuming that the nbc protocol security properties are okay with that um and then you can sort of take them at the end and write the proof and then what you're doing if you sort of like imagine that workflow essentially the the collaborative proof here is sort of boosting the security of the mpc so that parties who didn't participate in the npc are also convinced that it was right okay that's that's a nice way of thinking about it yeah thanks sorry yeah this thing is actually a bit

more complex than that because your generic mpc has to not just check the relation but actually compute it so things like inversions you have to compute the inversion inside mpc versus um for proving you just need the secret shares of the inverse um and you can do the multiplication and so in practice i expect the mpc to actually compute the secret chest to be much more expensive than the mp than the sort of collaborative zika is not proving that might will be the case and it's a really good question i i think ultimately the way that we thought of it is the cost of this mpc is going to depend on the relation and the cost of the proving stuff that we're going to talk about today does not um and so we're going to we're going to talk about that stuff because we can give a very

clean answer to how expensive it is um but yeah this these other questions are like super interesting and definitely we want to look into it as well okay so let's let's charge your head um so how we're going to build these things uh well uh someone earlier was asking like is mpc going to be involved do you bet um and you know it's sort of like one naive approach for constructing these and it actually ends up not even being too naive is uh you can bring to bear a generic mpc protocol and what these protocols do is they allow you to take any computation expressed as an arithmetic circuit and securely evaluate it over secret shared data that is exactly what we want here um so you could imagine just taking your generic nbc protocol and instantiating

it with a arithmetic circuit representation of your snark prover um and you know that that's the end of it but this this uh sort of this approach while it solves the problem at a theoretical level has some some practical concerns and the practical concerns go like this uh both zk snark provers and generic mvc protocols are known for being slow um i uh sort of like uh back of the envelope calculations i often treat these like they're a thousand times slower than their underlying computation the approver is a thousand times slower than just checking the property and the mpc protocol is a thousand times slower than computing the thing locally and so the thing that we're worried about here is that when we take these two relatively expensive um

pieces of general purpose machinery and combine them we're going to end up with something that's a million times slower than the underlying computation um and one of the you know one of the really cool things that's happening right now um is that we're finding cool applications for for starks and for mpc both of which are sort of a thousand times slower but but our fear was that something that's a million times slower is just too slow uh and actually i think that that's true in many scenarios um yes that that is exactly how i feel alex yes frowny face okay um so so the question is whether or not we can affect this composition without eating the million fold slow down and what we'll see is that the answer is yes so we're going to end up accomplishing this composition um with something like a 1

000 to 2000 x slowdown um so in particular what we're going to show is that the collaborative proof in terms of wall clock proving time is just as fast as the zk snark prover um or is about twice as slow as the zk snark prover uh and uh yeah look forward to if you're skeptical look forward to the evaluation because we'll sort of like look at this in many scenarios how's it how does it vary with the number of parties yes yes so this is going to be for small finite numbers of parties and a good network connection not like an unrealistic network connection but a good one and and also like we're like the if you start to imagine like evaluations in this space there are a lot of variables we're going to look at them all okay so let's let's charge ahead so um

our goal is to npc the approver we're going to find some way of doing this slightly non-generically in order to avoid the terrible slowdown and essentially the project at this point becomes somewhat straightforward i might say um there are a lot of potential performance problems and we just got to go through and clear them out um and so uh the first place to look is of course all of the traditional bottlenecks in single prover proofs because if those are getting dramatically slower in the multi-party computation setting then that's going to be a problem and so the first traditional bottleneck is elliptic curve operations um these actually it turns out if you don't handle them right they can become they can give you that that million fold slow down um but in the literature they're the beginnings of a good

solution to this problem and in this work we take uh those ideas and develop them further so i'll go into that in a slider too how we handle elliptic curve operations another [snorts] traditional bottleneck for your transforms when your proof system gets big enough and assuming your proof system is using for your transforms eventually those actually even take longer than the olympic curve operations um and the nice thing here is that the fourier transform as you might recall from your signals and systems engineering class is a linear operator um and because the mpc protocols that we're going to be building on uh perform extremely efficiently on linear operators these end up just not being a problem which is great beyond the traditional single prover bottlenecks we also have to think about operations that aren't traditional

bottlenecks but might become a bottleneck in the multi-proofer context often because these are operations that are highly non-linear or have high multiplicative depth and there are a whole host of these potential problems one example is polynomial divisions lots of provers reason about their data in terms of polynomials lots of them divide those polynomials by other polynomials polynomial division highly non-linear could be a huge problem uh but we go through our proof systems and we find out that actually for our proof systems it's not a problem because and this is somewhat technical the divisor polynomial is always public um and that means that when you view the operation as an operation on the secret data it's actually linear maybe that's not obvious maybe you have to prove it you can see the paper i don't know maybe it's obvious depending

on your background so this ends up being very very efficient which is good one thing that is sort of honest to god highly non-linear is that uh one of our our provers planck needs to compute a sequence of partial products um so that is like the worst case it's just a sequence of multiplications um the the depth of the circuit is as large as the sequence and the sequence it turns out is very large um but fortunately it turns out that in the literature um uh let's see in a very old paper by barlon and beaver there is a special purpose mbc protocol for computing sequences of partial products that runs in a constant number of rounds and so we can just break that out uh and then there's this sort of one final problem that's not a traditional bottleneck but it could become a

bottleneck in the the multiprover context which is merkle tree evaluations and in general hashing um and this is of course critical for the hashing based snarks and it's potentially a problem because well hashing is very very non-linear evaluating hash functions inside an npc is is not good um and on this front we we sort of strike out we we have like a partial solution to it that we don't like very much i'll tell you about the ideas we have so far um but we're ultimately not able to get the hashing based snarks to work as well as um to work as well as the elliptic based ones let's see produce as a comment it's linear because you compute the polynomial division via ffts and iffts yeah that's that's that's really great

intuition for for how it works um it turns out that you know if the divisor is is uh also secret then things get more complicated but but in the public case bingo um it's actually a good question do we use ffts so actually the answer is generally we end up not using ffts for this because the divisor polynomial is not only public it also has a small degree um and so um you don't use the school book division well i guess you do use in one case you use this that division algorithm um but yeah so so we actually do not break up the entities um you can actually use standard um sort of polynomial division not the f50 if the if the divisor is known okay cool um so let's uh so we have two

things to talk about we're going to talk about how we handle it to curve operations we're going to talk about hashing um and then we'll we'll go into the implementation and evaluation so um unfortunately i can't just tell you immediately how we handle elliptic curve operations first i have to give a little bit more background on how mpc protocols work and so the let's do a little crash course on those so at a high level mpc um protocols the generic ones at least the ones that we're building on uh they allow you to evaluate an arithmetic circuit over a finite field um so the circuit has um the values are in some finite field the gates perform addition or multiplication and we have secret shares of of the

inputs and so what i mean by that i mean that the inputs are represented according to a secret sharing scheme that's defined by the mvc protocol there are all kinds of secret sharing schemes the one that i want you to think about during today's talk is additive secret sharing the the classic um where if you want to write secrets here a value x you just come up with n random values that sum to x and then you distribute those n random values among the parties and now no party in fact no collection of n minus one parties has enough information to recover x on their own so this so npcs stage one they secret share their inputs and then every generic mbc algorithm defines some kind of secure protocol for taking secret shared inputs and computing secret shares of their sum and or their product

so these are sort of secure sub protocols just for computing pluses and multiplications and then once you have those secure sub protocols you just sweep through the circuit you evaluate every single gate using these secure sub protocols you end up with secret shares of the outputs and then you can reveal the secret shares to the other parties um so these are the kinds of nbc protocols that we build on more specifically we build on on two protocols one of them is called speeds it's it's a classic um and it has the cool property it's kind of like additive sharing and it has the cool property that it's secure as long as at least one party is honest um and then we also build on a newer protocol called gsc that was published at crypto

last year either last year or the year before um and it is uh it's a little bit faster um but the downside is that it's only secure if a majority of the parties are honest so um these are two different uh mpc protocols they each have their own secret sharing scheme um and in some sense our techniques are going to apply to both okay so that's that's sort of the landscape of how npc works um you can evaluate arithmetic circuits how are we going to handle elliptic curve operations ah okay great so victor has a question what does secure mean in this context i'm really glad that you asked so um in the case of the um in the case of the mpc protocol the the

notion of security that's going to be most relevant to what we're building is secrecy so in the case of gsc if a majority of the parties are dishonest then they can learn potentially all about wire values in the circuit um and so ultimately the um the security threshold for the mpc is going to correspond to the zero knowledge threshold for the collaborative zk snark but i do want to emphasize that the soundness of the snark the fact that it's convincing that is not contingent on any of the proofers being honest does that give you some more useful information victor okay cool i'm really glad that you asked the question i should actually be talking about that myself [laughter]

okay so back back to so elliptic curves so so you know we can evaluate arithmetic circuits how we're going to handle electric curves well there's sort of a natural approach which is well you know elliptic curves um they're kind of complicated mathematical things but basically they're just x y coordinates or or maybe some other kind of coordinates over a finite field let's say x y coordinates for now and so what we can do is we can secret share those coordinates we can have secret shares of x and secret shares of y for every curve point and then if we want to add two curve points in the elliptic curve sense of the word add then we can just evaluate the elliptic curve formulas over these coordinates to compute the coordinates of the sum uh the formulas are a little bit nasty but you know they're not they're not too

bad [snorts] however unfortunately this approach ends up um well it's conceptually very nice it ends up being very inefficient and sort of the problem here is that even the elliptic curve addition formulas involve a whole bunch of multiplications in the field and and um the way that mvc protocols work addition is often very cheap and multiplication very expensive and so what we're seeing is that even basic elliptic curve operations when you take this approach end up being very expensive because they involve all these field multiplications um so this is this is an approach that doesn't work so well like i said this is this is the kind of thing that's going to lead to maybe not million folds slow down maybe like 100 000 fold slow down um just kind of like back of the envelope um

fortunately though there's there's another way so the second option is instead of secret sharing the x y coordinates you can secret share the curve points themselves as elliptic curves earlier i described additive secret sharing where you split a value into n values that sum to it you could do exactly that where the sum is now in the elliptic curve sense instead of the field sets um so this is this is a and once you do this now doing additions uh well you can in the case of adding the secret sharing do that share wise and in general other secret sharing schemes have efficient elliptic curve edition sub protocols as well and these are especially nice because at least all the mpc protocols that we build on do not require any communication to do this kind of this

sharewise edition so this elliptic curve secret sharing is very cool it turns out in the case of speeds one of the protocols that we build on folks have observed in the past that you can do this curved secret sharing and it allows you to do quick elliptic curve editions and it actually allows you to do a very quick elliptic curve scalar multiplications as well so that's pretty cool and then what we do is we show that for the gsz which is this this new mpc protocol that we were building on the same technique essentially applies the the gsc protocol is also compatible with elliptic curve secret sharing and in fact both these protocols are even sort of compatible with mixed elliptic curve field secret sharing where you've got some some circuit that's doing field operations and curve operations in the same circuit um and you can you can run

it all through the same mp3 i was going to ask about that whether um using elliptical um sharing prevents or or makes field additions less efficient yeah so it doesn't so the short answer is you imagine we call these circuits like elliptic curve circuits they have field operations in them they have curve operations wires have types they're either in the field or they're in the curve um for our purposes the field is always the scalar field of the curve and the answer is um yeah so like all of the field type wires you secret share them in the field all the curve type wires you secret share them the curve and now you have a lot more sub protocols you have like a field field product sub protocol and a field field sub sub protocol and a field curve

product photo sub protocol and finally a curved curve sum protocol as well uh okay and unfortunately it just all works [laughter] yeah it's a little bit tedious to implement but the theory is pretty clean um okay so so that's that's kind of the approach that we take to handling olympic curve operations um and under this approach elliptic curve addition basically is going to slow down almost not at all in the mpc and then uh curve scalar products can slow down in the case that both the scalar and the curve are secret but it turns out that doesn't actually happen so often um okay so this i'm not going to go through like every step of the construction but this this

sort of clears out the bottleneck from the perspective of elliptic curves from the perspective of the elliptic current based snarks now i want to talk about hashing um so for hashing um for the hatching based snarks they do a lot of hashing for a lot of reasons but essentially it's all centered around these merkle trees um so they've got a whole bunch of values x1 through xn a big vector they want to hash them together pairwise and some kind of binary tree to get a root r and the problem here is that these values in our context are secrets they're going to be secret shared and that means that these hashes are going to be evaluated over secret shared data and hashing is highly non-linear in fact it has to be for security reasons um so this is going to suck uh and you know just it just does suck um there's

frankly not a lot that you can do about it um the one thing that that we we suggest is sort of the natural thing which is that instead of um having sort of like having the provers collectively compute a miracle root for their vector you could have each uh prover compute a merkle root for its own shares um and then you could sort of treat these now and big n as in the number of provers merkel roots as your vector commitment to this vector um and then when you want to do an opening proof every single approver has to produce their own um opening path and then you have to like add together the things that you open from all the vectors or in general unshare um so the downside of this is that the proof size um ends up going up by a factor of n the number of provers and

the verifier work also goes up by a factor of n um there are ways around this natural ways around this in fact um one time i was doing this talk and riyadh was in the audience and he was like well this is you know a pretty natural approach here which is like you just do like a layer of proof composition where you take all of these merkle proofs and you sort of like write a proof that you verified them correctly and added and added the values correctly or in general unshared the values correctly um so yeah indeed that that sort of works and that would be an interesting direction to explore um but but also it'd be nice to have like a post quantum um collaborative zk snark where you don't have to do this kind of composition that we know is is often very expensive in practice

um so yeah on the hashing front we end up not doing as well as you might hope um but um the elliptic curve stuff went super well so we went ahead and implemented all that yeah i i guess you don't want to use players and ashes because the whole point is to avoid is to be post quantum in those two systems yes yes exactly exactly that um and but yeah pedersen hash would do the trick yeah they would and it would even make allow us to use our fun elliptic curve stuff so we would you know we would extra enjoy that solution okay so anyways we go ahead and we implement um collaborative uk snarks we our goal for the implementation was was very ambitious um so we wanted to implement a whole bunch of different

collaborative zk snarks built on a whole bunch of different underlying conventional proof systems we wanted the building graph 16 marlin and plunk we thought that uh collaborative zk zknarks based on all of these should be quite efficient but we didn't just want to say that we wanted to show it uh we wanted to build our collaborative case dk snarks to different levels of zero knowledge that that t variable um and so we had two notions in mind we wanted to support t less than n and also t less than n over two um and on top of of building all these club average dk snarks our goal was that our vision was that these should actually be able to be very concretely competitive with their conventional counterparts so at this point basically we thought that we should be getting within 10x of a conventional zk snark um and uh doing

this is actually quite challenging because the existing zk snarks these are like mature code bases that are pretty well optimized um and you know we're lazy and so our goal was to be able to do this without having to work too hard in particular we did not want to implement 10 years worth of optimizations um and uh sort of we envisioned that our secret sauce here was that we we figured that we'd have to iterate a lot on sort of like specific sub protocols that were a performance problem and so we needed some implementation strategy that was going to allow us to swap out the protocol for prefix products or swap out the protocol for polynomial division and you know the question is how do you actually do that in the implementation and it turns out that there is a way um so um the opportunity that we saw is that

there's this really nice code base developed by at least one one person in this call called artworks um and artworks is fantastic for a lot of reasons but one of the reasons that's fantastic is that all of the provers and artworks are implemented generically over their elliptic curve so the elliptic curve here is represented as this pairing engine um and that's like just some trait it's actually extremely big and complicated but i i've summarized it very briefly here on this slide that defines how you do field operations in the base field and in the scalar field and how you do curve operations and all that kind of stuff and the different forms of the curve that are relevant um but so the idea the reason that arc works is implemented this way is you know we do active research on elliptic curves and all the time we find better

elliptic curves or elliptic curves you know we find out that an existing olympic curve isn't as secure as we want um and so artworks was designed so at any point in time you could swap out your elliptic curve you could reinstantiate your proof system over a new curve um and our our idea was to sort of take advantage of that level of indirection if you would that of that generality i mean so basically the way that we see it is you know there's the arc works prover and there's the arc works curve and the prover relies on the curve um but we were going to cut that bond and insert some new stuff in the middle um so we started by implementing the basic mpc like the generic mpc protocols for both field and curve operations so we did this twice once for speeds once

for gsc we actually did it a few other times for fun as well but we won't get into that um and so what we ended up with at this stage is a bunch of implementations of npc protocols um where like the object that you hold in the protocol isn't a value but rather a secret sharing of the value that only has significance because you're in a multi-party protocol with like these other machines and then we took these secret shares and we wrapped them in some kind of wrapper type that implemented the artworks curve and field and et cetera interfaces and so the idea is that you have this token that that's the secret sharing and you can run the artworks field add or curve add function on it and it it does that by way of a secure multi-party protocol that it runs with the other

machines and then it gives you a new token which is the output um and then we just took this and we plugged it into the prover um and you know the first order this just works that's not quite a lie like it breaks like in a few specific situations and you have to fix it up um but more or less this works and the sort of the cool thing is what it's allowing us to do is take this single machine prover this this prover that was written with only one machine in mind and kind of misappropriate it as this multi-party protocol um and this i want to emphasize this strategy it does not work in general like in particular there are things that you could do in your computer that do not translate into even an elliptic curve circuit um but for provers it turns out that it does

work and that's that's pretty cool um also this code is public so like if other people want to build npcs on top of this we would encourage them to do do so um but yeah it's just kind of a cool thing i have a question you you had said originally you were building on both types of npcs but i'm not clear from this like why are there two are you combining them are you actually doing separate uh implementations and where where are they like which part are they being used for different parts of this are they just like options so you can see which one does best yes it's that's a great question anna um so let's first by start by talking about how this diagram reflects two and then we'll talk about why we did too

um so the way that this diagram would reflect two of them is that we actually implemented two different mpc protocols and have two different wrappers around the mpc protocols that gives us gives rise to two different kinds of approvers and the reason that we did that we did too is because the two nbc protocols they are private against a differing number of malicious parties in the protocol so one of them is private so long as the majority of the parties are honest and the other one is private as long as at least one party is honest and so these correspond to different key thresholds in the t zero knowledge property so one of them is like n over two zero knowledge and the other one is like n minus one zero knowledge so there's one like fat like faster to run but less secure and one is more

secure but slower to run that is exactly what we're gonna see we haven't seen the performance yet but yeah it turns out the one that has a smaller zero knowledge threshold um is going to end up being a little bit faster okay so let's actually take a look at that evaluation then so the experimental setup is mostly pretty straightforward um so the goal is always wall plot wall clock proofing time that's what we're going to measure we're going to change the number of provers big n the number of rank one constraints little n the link capacity this is a multi-party computation so uh the sort of the network matters a lot we'll be varying that as well we're going to be varying the base uh conventional zk snark as well as the mpc protocol that we use to generalize it to

a collaborative zk snark this corresponds to varying t the zero knowledge security threshold uh we make two simplifications first of all we run all of the machines locally in single threaded mode we don't believe that this is something that you have to do but it makes the evaluation simpler so we do it and then the other thing is that we skip mpc pre-processing um for the improving the proving phase and the reason that we do that is because we do a few calculations and basically we see that for our computations even though mpc pre-processing is traditionally rather expensive it's extremely cheap um because sort of basically writing a proof is already so expensive the mvc pre-processing kind of gets crowded out um i think for a very large number of

approvers that might be less true so we probably have to remove that simplification for a large number of groupers okay so anyways those are the simplifications we make um and then we do a whole bunch of experiments uh changing these parameters um so let's start with the main experiment where we change uh essentially the number of rank one constraints so we try to prove more complicated properties and we do this for a small number of parties um i'll talk about the exact configurations in a moment and we do this over a good link so a three gigabit per second link which is like what you can get over an ethernet cable like a lan and this is also what you'll get in a data center um so um i'm going to sort of present the results

piece by piece i don't overwhelm us um so the first sort of experiment that we did is just the baseline so we ran a single prover um doing its computation locally and looked at how proving time grew as the number of constraints grew and so here i'm showing this for the grot16 improving uh proof system and you can see that this is slightly super linear but it's almost going up linearly and what we see is that for the uh honest majority protocols so for example a three prover protocol that's private against one corrupt prover so so that a corrupt proofer here is in the minority as the number of constraints grows proving time becomes essentially indistinguishable from single proof approving time

which is very cool um and then for the malicious majority protocols so three proofers two of which are corrupt or two provers one of which is corrupt um the proving time ends up being about twice the proving time of the conventional proof system and so this this pattern that the honest majority uh version is just as fast as the single prover algorithm and the fully secure version is is uh twice as slow uh that's repeated throughout all of the different conventional dk snarks that we build on uh and i want to emphasize this is pretty cool um most uh computations when you put them into a multi-party computation slow down by like a thousand fold and you know here we're seeing like

one to two x slow down so so this is this is pretty pretty exciting um in our second experiment though we wanted to falsify some of these these uh ideal assumptions um so in particular the second experiment considers many proverbs we fix the number of constraints and now we just increase the number of provers and we also fix our spells to the grot 16 um grout 16 based collaborative proofs um what we see here is as the number of approvers grows the system does slow down quite a bit um and so um we're doing this for the two different security thresholds honest majority and in full security um in both cases the slowdown which is sort of the um the time that it takes to go to produce the collaborative proof divided by the single proof of time is growing

um and actually one of the interesting things is that we're seeing that the um the honest majority protocol so the less secure protocol initially it's faster but as the number of approvers gets big enough it's actually slower and uh this is like sort of an opportunity for research there's no reason that should be the case that's just sort of an artifact of this particular mvc protocol that we're building on it would be it would be good to try to close that gap we also do experiments over links that have lower capacity so over a bad network so here we fix ourselves to two provers a thousand constraints we're doing the malicious majority protocol and we're doing this for different proof systems and we're looking at how the slowdown increases as the bandwidth decreases and so what we see is as you get down to megabit per second which you can get

more or less anywhere in the world uh slowdown is growing it's getting up to like 16 or maybe 32 but it's still not a thousand and that's pretty cool okay um so this is basically where we're at the end here um a few things i want to discuss um one thing that we saw in those latter experiments is actually maybe i should pause yeah i'll pause for questions on just the experiments before i wrap up okay can you go back to the um the one that's increasing with n yes uh sorry the previous one the um little n yeah yeah sorry little end up

again uh i i'm just having a look at the concrete performance here oh yes yeah so yeah sorry i should talk about our baselines here so our baselines here for grout 16 and marlin are the existing artworks implementations which i think are not quite state of the art um uh and then for blanc it's our own very very bad plunk implementation don't don't use it um [snorts] and um so sort of we believe very strongly that for almost any implementation you should be able to get the 1 or 2x slowdown um but of course we're only showing that for the for the artworks implementations okay yeah that's there's nothing surprising to me here so that's good any questions about the other

experiments okay do you have figures for um where you have a sort of a moderate number of provers and also a fairly large circuit so let's say um uh two to sixteen constraints and twenty provers uh we i don't have those numbers but the this the performance is predictable enough that i think we can we can compute them right now in real time um so like let's say that it's 32 provers so our slowdown is like 16 from that well actually i guess you'd be using you'd be using speeds there so our slowdown is more like three i guess okay um and so now let's go back so like how big do we want our circuit to be uh two sixteen two to the sixteen okay cool so it seems

like uh let's say 2 to 15 so because it's easier to read off yeah so it seems like um so our our single approver variant here is running in about eight seconds and we expect the slowdown to be about three from the previous plot um so that's going to be like 24 seconds okay pretty good to be clear though this is all over a three gigabit per second link and so if the link is not so good then that's like another source of slowdown so so what about bandwidths the the the total um sort of transmitted data uh yeah do we have like the the like net communication we actually didn't record that um um

ballpark it's going to be like probably a kilobyte per maybe a little bit less than a kilobyte per gate i guess um but yeah unfortunately we did not measure that okay that that's not too bad for some applications yeah okay so um let's try chad so okay um discussion um so there's a few notes so one thing that actually is even coming up right now is as the number of parties grows as the network degrades eventually communication becomes the bottleneck not not computation um and so a natural question is whether or not you can improve uh the

amount of communication that we're using and we think that's definitely possible but we do show a partial asymptotic lower bound in this space so in particular if you consider only two provers and you consider an additive secret sharing scheme or it turns out you can you can show this i believe for any linear secret sharing scheme as well although we did not do that uh there's there's actually an omega of little n lower bound on the amount of communication that you need so if my circuit has size little n then asymptotically i need at least little end communication and that it turns out is just unsurmountable in particular you can show a reduction from this classic problem called disjoint which is known to be communication complexity hard so there's a reduction from it to

constructing a collaborative zk snark um and that gives us a partial lower bound we actually think there's a lot of interesting sort of follow-up communication complexity work to be done here um we think that there are a lot there are stronger bounds that should also hold but we were writing a security paper not like a communication with paper so we didn't try to improve these another really important thing to do is to use parallelism within the prover um we don't believe that there's any reason that you you can't do this um the the pair sort of the parts of the prover that are traditionally accelerated with parallelism are local in our collaborative dk starts so it should it should be pretty straightforward but we didn't do it and that would be a good thing to do uh and then finally as i alluded to earlier it would be nice

to have a better post quantum collaborate zk snark okay so um basically at the end here um hopefully as promised you've learned what collaborative zk snarks are if you forget everything else you should remember that they support zero knowledge proofs for distributed secrets and if you can remember one more bit of information you should remember that they seem to be very concretely efficient um typically multi-party computations are like a thousand-fold slower than their undistributed version and here we're seeing slow downs of like one to two x and then we're as good as one to two x and that's pretty cool uh it's interesting to think about why that's the case um essentially these uh these provers they're highly algebraic highly linear um and we're able to take advantage of that in the mpc protocol and snarks are

not the only algebraic cryptographic protocol so it makes sense to think that this approach could be applied to create collaborative versions of other primitives as well uh so uh at the end of the talk thank you very much i'll take any final questions and then i guess we'll wrap up so so let's say using the elliptic curve sharing um but my intuition is that it's surprising that you don't get more slow down just as a result of doing that because the cost of elliptic curve addition

is obviously significantly worse than a field edition yes yes so i i think i'm going to like focus that question on one specific operation which is the huge multi-scale multiplication that basically sorry yeah multi-scalar multiplication that basically every single uh snark that we ultimately implement needs to do um and so for this multi-scalar multiplication we have to do a lot of elliptic curve operations already so the question is just do we have to do more yeah um and in the case of gsc which is using xiaomi sharing it turns out the answer is no you're doing a different multi-scale or multiplication but but um you're still doing one multi-scale multiplication the size is the same

in the case of speeds it turns out you have to do two and the intuition here is that the way that speeds works is that you have an additive secret sharing and then you have essentially an additive secret sharing of a mac or an authentication code on the original data and you more or less just have to duplicate the computation you do the msm to both of these and so that's like exactly where the 2x slowdown comes from okay yeah that's that's pretty intuitive thanks so so there really is that that is where all of your overhead is coming from basically yes yeah in the case of speeds it's just it's like you're duplicating the computation [snorts] you yeah

this is a classic example of you you design the system you optimize it you predict the performance and the implementation meets your expectations exactly cool awesome a couple couple uh or some words of gratitude in the chat from everybody uh aside from those does anybody else have any final questions for alex okay hey this was awesome alex thanks so much for presenting this work i was really really good discussion and and this is really exciting hopefully we'll be able to see this applied somewhere out in industry here soon and thanks again for coming back on zk study club

yeah my pleasure and and and of course hopefully it goes without saying but um you know this is a cool thing but it'd be cooler if people needed it for some reason or wanted to use it so if that's the case come talk to us the implementation is public there's a link on the slides nice awesome but but also we're happy to play a support role there um as well yeah and if you want to share the slides with me after this then i can post it on the on the youtube channel as well so yeah i'll do that