Demystifying MPC for coSNARKs: How to Collaboratively Prove Sumthing - DeFi Security Summit 2025

Transcript

Hi, can everyone hear me? Everything good? Okay. Okay, thanks. So, welcome everyone to this workshop part of DSS. I really appreciate you being here because there are so many competing uh talks, each one more interesting than than the other. So, I really appreciate you being here. Um I am Vaseline Valichkov ZK security researcher at open zeppelin and I'm part of the zk team and what we do um we do uh audits of zk cryptography components and also we try to educate our our auditors about cryptography and and zk in general and what you are going to hear today is part of this um this uh training process so I I'll be talking

about uh um MPC computation for uh for Cosnark works. Um so I just want to to check a bit like to get a feel of um of the audience like how many of you are vaguely familiar with snarks zk snarks zk snarks like vaguely familiar. Okay, cool. And how many of you are deeply familiar like to the technical details like how plunk works, how growth 16 works, commitments, polomials, polomial arithmetic, not many. Okay, you're at the right place.

Uh, and have you have you heard about cosarks? Uh, yes. Cool. So, yeah, so this talk is about snarks and cos snarks. Um, the idea is to start from the ground. So, so hopefully uh we will introduce everything that's not uh not familiar to you. But the the goal is to to illustrate multi-party computation of cosnark. So how you how you collaboratively compute the snark proof and the the the the motivation of the whole talk is that um like many people especially like many auditors are interested how co snarks work. Um and if you want to explain this you first start you need first to start with explaining

how snarks work and then snarks is already a deep area in itself like if you if you start with um some production level snarks like plunk or growth 16 um there are so many new concepts that you need to introduce before even touching the um area of MPC that it it's simply not feasible like it makes up for a whole new course. So that's the reason why uh we take a different approach. We start with a very simple protocol called sum check. It's an existing protocol. It's an old protocol. It's widely used today even in production levels and starks. So we we start with it and then directly we jump into MPC. So with some check we illustrate what it means to prove something in particular what it

means to prove correctness of a computation and then we directly discuss uh multi-party computation how you can collaboratively compute this proof and once we are there then we can introduce all the topics that are related to to ZK snarks such as for example succeedness commitments blinding arithmetization um and this will not be part of this talk so this will be at I will mention it only at the end and the idea is that the toy protocol that we develop is modular enough that you can build on it and once you're comfortable with MPC you can also start introducing all those critical components.

Um okay so that's briefly the plan I will follow. So basically the whole workshop is broadly divided into two critical parts. So one is introducing sumche. So how many of you are familiar with sum check? Uh oh cool that's that's nice and if you have if if you are not we'll spend quite a deal of time like introducing it maybe about 20 minutes or so and after that we will show its MPC version. So um how you can collaborate collaboratively compute an MPC proof and at the end depending on how much time we have we will talk a bit about the missing parts uh what what what we still need in order to build a full-fledged ZK snark

okay just to clear clear up some basics in the beginning what is um zero knowledge proof of knowledge so basically it's a protocol between a prover and a verifier in which the verifier proves the the provers that they know a certain fact which we call the witness for some public statement and a public input such that given relation holds. Now it's a mouthful we have this y= f of x comma w. So you can think of w as the secret input the witness x is the public input known to prover and verifier. You can think of f as the relation and y as the public statement. Um [snorts] and just to relate it to something familiar, a simple example is proving knowledge of

the pre image of a hash function. So um you you as a prover want to prove to the verifier that you know such a W like a prey image to your hash function H that when you hash it, it results to the output Y. So W would be your witness. It's secret. It shouldn't be revealed to the prover to the verifier, sorry. Uh and uh Y is your public statement. H is your relation or the hash function. Okay. And in the protocol we we we have some interactive process between prover and verifier. It can also be made interactive uh non-interactive.

Um and um zk snarks are one class of zk proofs of knowledge. Just a few a few words about them. Um they um just to break down the whole like acronym zero knowledge succeive argument of knowledge. Zero knowledge the proof does not reveal anything besides it valid validity. Succinctness means the proof is short. We will talk a bit more about what short means but basically it should be um short in in comparison to the size of the witness and to the computation.

Um non-interactive means that you don't have like a sequence of messages between prover and verifier. You only have a single computation on the prover side then submitting the proof to the verifier and the verifier verifying it. And finally, argument of knowledge. So the provers not only that um that there exist a witness that that satisfies the relation but also that he knows this witness. And finally uh just a note about um difference between proof and argument. So we will be using the two interchangeably in this talk but technically there is a difference namely a proof is about um proving um unc unconditional unconditional soundness or unconditional security. uh meaning security for unbounded provers. So we

don't assume that the prover is computationally limited while argument is more about all our proofs will be under the assumption that the the prover is computationally bounded namely he's polomial he can can run at most at polomial time meaning that if you have a more powerful prover can also break the system he can uh he can fake proofs this is just a technical detail u and the core properties of zkar completeness so an honest prover always um convince a verifier probability one and soundness is about the fact that you still have some some probability um some possibility to cheat. So there is still

a possibility that a cheating prover may convince a verifier that he possesses a witness even if he doesn't but typ but typically this probability is negligible so it's not feasible to uh to find such a witness. Um and finally zero knowledge we talked about it doesn't leak information about the witness and two properties that are desirable but but most commonly they are um they they are present succinctness so size of proof and the pro proving time is sublinear or even nearly constant in computation size and non-interactivity um we we discussed it already so specifically um zk proofs have found wide applications in um in blockchain and they actually were um catalyzer to

to to quite a bit um um evolve the field even research wise in particular they are very useful for scaling and privacy. So scaling uh it's ZK proofs that allow for example ZK layer 2 roll-ups to batch multiple transactions um together offchain produce a single succeeded proof proving that these transactions are valid and they cause a valid transition from a uh from a uh root to the next route and then only post this succeed proof on chain which is critical because that's what we are paying for.

So we pay for the size of the proof in gas on on layer 1 and thanks to ZK proofs then it becomes cheaper and uh therefore scalable for Ethereum and for privacy um which is a big buzz word and this addition of defcon connect um it's clear how it helps privacy right because uh because of the zero knowledge property you can hide identities and uh and the mounts um while still uh making it compliant still being able to to to prove um that uh the transaction happened for example. Um so this is how it looks. Um it's like a high level uh workflow. On the left hand side you have offchain computation. So a program or a circuit.

This may be like a circuit of your VM. Uh a public input and a witness. Then a prover or sequence that computes a proof. This is completely offchain. He passes the the proof together with the public input. So you have the public input and the proof to the verifier which is typically a smart smart contract on chain uh which um checks whether the proof holds or not. And now slowly moving to the to the the core of this topic like cosarks what what are they are um what what they are.

So um the thing is that like everyone is focusing on the verifier. So we we've made like we've gone through through long lengths of um making sure the verifier is is efficient because you want um uh your cost to be low. uh but and and and the reality is that the prover is the bottleneck now because proving is expensive uh in terms of uh time and memory but it it is also like not so critical because it happens offchain yet if we want to like onboard um resource constraint devices like for example mobile phones if we want our mobile phones to be able

to compute ZK proofs it will be it would be nice if we can outsource the computation of a ZK proof for example example to the cloud where they it has uh um much more powerful servers and they are able to do this. Uh on the other hand we also want to keep the witness secret right we have secret data. So how do you resolve this? How do you on one hand um outsource your computation and on the other you still keep your data private? Um and that's the whole motivation for for proposing cosnarks in 2021 by Osmir Bonet uh which um in which they they propose to to outsource this computation to a network

of MPC servers and MPC stands for secure multi-party computation which is exactly the technique that allows us to to securely um share the witness so share the secret input to proof um to a network of nodes in such a way that none of them learn anything about the witness itself. Yet they can com they can perform some meaningful computation on their part of the witness and then accumulate their results together and come um come up with the final proof and that's that's the whole process we will be talking uh in more detail now um and the same picture as you saw before except in the MPC setting. So all the

components are more or less the same except now we have this network of provers. So these are MPC nodes uh which receive as input instead of the witness. You notice here they receive this special notation like square bracket W with which we denote uh shares of the witness. So now every node will receive its small piece of the witness. We will see how these pieces are computed uh and they will perform computation on those pieces. They will come up like conceptually uh each of them will produce a small fragment of the final proof and then combining all the fragments you end up with the full proof which is then pushed to the verifier.

And if you notice from the point of view of the verifier um things are the same. So the verifier cannot tell whether he's uh where the proof came from from this MPC network or whether it came from from a single verifier. Uh and there are already production uh systems that implement this approach. Um um Tasio is just one example where uh you can see like the end users in the form of mobile phones for example um that they they uh push their computation to MPC node. So hopefully by the end of this uh workshop you will have a better at least better feeling and intuition

but hopefully better understanding of what is happening in all in in all those MPC nodes notes and how all this uh process works. It's not to say that it's exactly what Tasio does but it's more like conceptually um understanding it. Um and um so this here is is a whole road road map of how you would go to to build up a a simple toy uh ZK snark from the ground up basically. Um such that it is NPC friendly. Uh and we we start with the check protocol which we introduce in a moment. Then we add MPC computation and then we add all the other components that are needed for for

a snark like blinding, commitment, succinctness and arithmetization. But in this workshop we focus only on those two first blocks simply because time is limited. Uh we will talk about proof of correctness and then then outsourcing this proof of correctness. Okay. Are we good so far? So any any questions? Okay. I'm not sure how you can ask a question in this you know setup but maybe if you raise a hand I'll come over and ask you uh okay um okay so some check I think we we can easily spend about let's say probably about 20 minutes just talking about some check because that's the underlying part of

the whole of everything that follows so the check protocol basically comes down to proving knowledge uh and it's a bit of a weird setting when you state it at first, but later on we'll see how it can be useful. So you have a function and you want to sum this function over all of it all of its inputs in the boolean hyper cube. So what boolean hyper cube means is just all the 01 possibilities of the whole n bit string. So you have n variables they are not necessarily defined in f_sub_2 not necessarily boolean they can take any any value in the field but you evaluate them on 0 and one and you take like 00001 plus 0 0 1 0 plus 0 0 1 1 and

so on 2 to the n and you compute your value t prime and the whole protocol is about proving to a verifier that this function sums to a particular value t prime T prime. Why would you want to do this? It's about saving um saving computation. So in this setting, we're completely clear. Nothing is hidden. Both the prover and the verifier know the function f they know their degree. Sorry, it's a polomial. The polomial f they know its degree. [snorts] But computing t prime is computationally expensive. Like n if n is for example of the order 32 or more then you need 2 to the 32 operations to compute this t

prime. And the verifier wants to save this. He doesn't want to do this. So the prover says okay I I have computed this t prime for you. Uh and u this is the proof that this is correct. So then the verifier engages in this pro uh some check protocol and verifies that okay indeed that's the that's the correct result. So his um then his computation goes down from exponential to to the end to actually linear in the number of variables which is a huge saving. And of course looking at this at the moment it's a bit like it's very strange how it would even relate you know to ZK proofs because in ZK proofs we talk about an arbitrary computation but it turns out that this very simple protocol just working over

the booleans you can with some additional you know um techniques you can easily turn it to be a a proof of of of correctness and later of knowledge for an arbitrary computation. >> Yes. Sorry, >> can you clarify exactly what's being summed? >> Oh, these binary representations we got every combination of them. What what is actually being summed? >> Yes. So the question is what exactly is being summed here? So let's say this f is some polomial maybe like um x uh x1 2 + x2 + 3 and then you take x1 and x2 you make them 0 0 and this gives you some value. Then you give 01 you add it one zero. So it's like an accumulator.

Yes. >> For argu for arguments, right? How to if they are not boolean, how to make them? >> Oh, so so the question is if the inputs are not boolean, how to make them boolean? In fact, they are not boolean. So this polomial will be we'll see later this polomial will be defined over a field. So these values can be any any any element of the field. But for the protocol you only take the 01 uh values because it's a polomial you can take literally any value in the field and zero and one are as valid as anything else. Um and and we'll see how it translates later on to to snarks. Uh more questions. Uh

yes. So uh this is the so this is the setup in a bit more details. So we have the function we define it in this way. Uh we have the n variables as before and now think of this w1 to w k just as constants that parameterize this function. But we need them here because later on when we want to add zero knowledge we want to speak about the witness. We want to speak about secret part and then that's when this will come handy. So this will be potentially our secret that we want to preserve. But for the moment these are just constants and the polinomial is defined over the field. f it's a like field of prime order doesn't matter and also an important detail is that the degree of the polomial is bound so every um every

variable will show up with degree not more than d so you will have x1 to the d minus one x2 to the d but you cannot have x i to the d + 7 or whatever so you're bound by degree and that's important for the soundness we need this this d to be fixed and relatively low to compared to the size of the field. When later on we want to prove soundness of the protocol and the first step is the prover computes this huge sum that's his computational bottleneck. He comes up with the value t and then um uh and and and then it engages in a protocol in in in certain number of

rounds. The number of rounds is the number equal to the number of variables and every round is like conceptually the same thing is going on. So once you except the last round it's a bit special. So as as long like when you understand one of the rounds you have understood the whole protocol basically. So in every round the prover will be sending always a polomial of a single variable and this variable will be progressively one of the variables of the f polomial like first one then two and so on. So in in round one we we we prover sends p1 of x1 and how does he compute this polomial? Well he takes the original polomial f he

leaves x1 to be free. So the the polomial will be in x1 and then he sums all the remaining n minus one variables. So he assigns them. So here we have a sum over 2 to the n minus one. Uh and this this just remain fixed as before. So in a sense you you get something like this t prime but it's it's another constant. Then the verifier upon receiving this polomial p of one p1 he first checks the degree because the whole polomial is bound by this. So this P1 of X1 must be also of degree at most D. And then the verifier performs this um this simple check. Now he takes this P1, he evaluates it at zero, then he evaluates it at one, he adds the two.

And here it's obvious that the sum of the two should equal T prime. Right? So that's the first check that he does. Of course, T prime may be like the prover may be cheating. That might not be the correct the correct value. But this if he's checking cheating we will recover this later on specifically at the final round. Okay. So if the check passes the verifier samples a random number. So that's that's that's where whole the whole soundness of the protocol rests. This R1 or this RA it should be chosen uniformly at random from the field. Okay. And this is the interactive version. So just opening a bracket because I I didn't introduce specifically like uh how do you construct non-interactive versions from

interactive but if you want to make it non-interactive instead of asking the verifier to randomly choose R1 you may just hash all the elements that were seen before that and get the the the hash as the like this pseudo random value R1. It's just a detail just to keep in mind that this protocol can easily be made non-interactive as well. But explaining the interactive version, it's a bit better for for uh for a start. Okay. And then number i. So you have the same structure going on end times. So at at number i, we have the same thing. P i xi, this one is free.

We're summing over the remaining n minus um n minus i values. But crucially, everything that we have processed already is fixed to the random values that were sent by the verifier to this point. And we'll see why why this matters. Like basically when you show soundness, it rests exactly on this random values. Again, verifier checks the degree, then checks this summation. So the summation here is a bit different in the sense we don't check against the initial value obviously but what we check against is evaluate pi at zero evaluate pi at one sum them and we expect the sum to be

equal to the previous polomial that the verifier received evaluate it at ra minus one the previous random value and if you think about it that that should hold if the if the prover is honest right so um the previous polomial had this one free here all the summation was here and the rest was fixed. So by doing P pi0 pi 1 you essentially assign 0 and one here and this one was free before but now you fix it to r minus one which is exactly what this how this pi is defined. So for an honest prover this equality should hold.

Uh so I I'll give you a chance for questions in a moment but just want to complete the the description. This is the final check and in the final check we have already assigned all the values to this random variable. So all the variables to this random values. Uh so at this point the verifier actually evaluates the original function f. So the the real function at this point you you cannot give him a fake function because he knows it. uh he will evaluate it at R1 to Rn and he will ask whether this evaluation equals to the last send polomial PN of R RN.

Now this is the check that binds the final the final sum to the original polomial and if you remember the first round was the check that bound the claimed value to the first polomial. Now if you think about this what happens is like you you have a inductive basically inductive binding you you bind the last polomial to the previous the previous to the next one and so on and so on and so on until you reach the top value which like if all checks pass then you're sure that uh the sum is correct. I mean it's more than this but like algorithmically what happens. Um okay any questions? Did I manage to to lose you already?

I already already see faces looking at their phones. In the beginning, they were more fresh. Now I'm starting slowly to lose you. No, but ask anything if you if you want to. I I have a very nice animation right now which hopefully will will make it a bit clear. Um okay. So take this very simple example. We have a polomial in three variables x1, x2, x3 and we want to exactly to apply some check on it which means like evaluating on uh the hyper cube of dimension three which is just the cube in three in in 3D and the the blue dots are simply the points and at which we want to evaluate our polomial.

So we want to sum basically all the all the blue dots. Uh and how we go about it what happens like conceptually when we do the P1 X1 polomial is we are dividing all the values like in two sets. One is the the blue dots the other is the red dots. So the blue dots you get if your x1 is zero. So we are here and then you work only on this face of the cube and the red dots happen if uh x1 is one. So you work on this face of the cube. So essentially the first check is nothing but like summing this uh this this points and then summing this points which like obviously is the whole the

whole thing like all all of the points. But then the interesting part is that you you collapse your dimension by one. So from from eight points you collapse it down to four. And how do you do it? It's precisely by fixing your polomial P1 to some random value R1 which means like again like hypothetically that you had this Q but you also have a polomial that it can go not only through the value zero and one but just to any field element and you exploit this to say okay I've now I've received this polomial P1 and now I want to kind of commit to it.

I want to fix it and that's that's why I just take a random slice of the cube at some random value that the prover cannot predict it cannot manipulate and and and he says okay from now on work now on this polomial only in this space which means that now we we we we are back recursively we are at where we started from except we have lowered our dimension now we need just to sum four points instead of eight and it goes on like is we divide by by two um assuming the blue dots and the red dots. Um so that now the check is um the check is again against the R1 value. Um

sorry then we are at the dimension one until we reach a single point and that's where the final check uh the final check happens. Now, I guess this is more or less true, but but probably what is like hanging in your mind is like why why would it work, right? Like uh maybe you feel a bit cheated like why why would it why would this work? Um and the the the the like the the trick is in those random values and that's that's where this um zip lema comes into place which is widely used in many snarks actually and

it it basically rests on the simple fact that like if you have some non-zero polomial f that is of bounded degree so some fixed d um then this polomial can have at most d0 so it can be zero at most deep places. Right? Now if you query the polomial at some random point just anywhere on the blue line and this blue line it can go forever you know although we are in a finite field so it's finite. Now the chance that if you query the polomial this random value r the chance that it is zero it's precisely d the degree over the size of the field. Why? because it's

just the chance that you hit one of his roots. You just pick something at random and if it happens to be a root it will be zero. But if it's non zero then it means that the polomial is non zero. So essentially this gives you a way to check that a polomial is really non zero with just a single random query. So that's the whole magic of it. Um and if your field is a huge size like 2 to the 128 and if your degree is even like 2 to the 33 you still are left with a very low probability of like hitting one of the roots. Um so was this was this clear so far? Any any questions? Uh cuz the next slide is actually the connection to sum. So how how does this apply to some?

Wellma lipo what lipo lema what I described is how you apply it to show that the polomial is non zero right but you can easily translate this to actually checking whether two polomials are equal because suppose you want to check whether the polinomial f is equal to polinomial g and you know that both of them are bounded by degree d well you can simply say in fact of checking f and g I will check a new polomial h which is equal to f minus G and now checking whether F equals G comes down to checking whether H is zero or not and which is precisely applying the the Schwarz PM. So u then by simply querying h at a random point if the the the query

turns out to be non zero then you know that f cannot be equal to g but if the query turns out to be zero then you know with very high probability that the two polomials are the same and that's exactly what happens in this uh in this critical check at every round of sun check like like conceptually we are abusing notation here a bit but if this is your polomial from the previous round And this is your evaluation for the current round. You this will be your F like your F and this here will be your G. So by this check you're simply verifying this equality. So by by zippo at every at every round we we make sure that like the polomials are correct correctly chained to each other and

that's where the whole soundness rests on. Um okay we have another 25 minutes. Any any questions so far? Uh yes. What is the strategy to choose randomness? >> Oh, so what is the strategy to choose randomness? It should be uh uniformly random. But you are asking how do you choose it? >> Yeah. >> Okay. Yeah. Well, to make the theory work, it should be like as close as possible to uniform distribution, right? But how do you do it in practice? For the non-interactive version, you just hash the transcript. Your hash is the R.

But in a in a random in a interactive setting I don't know you flip a coin what it turns out like no seriously they they are called like uh coin flipping protocols you know yeah uh any any questions uh uh okay so okay a few words about the complexity and then we move to MPC Um okay completeness is clear. I think if the prover is is is honest then every all the equations all the checks should work. the prover is not honest. we come down to the probability with which the zipo lema does not hold like the

probability with which you may hit one of the roots which is like 1 minus so we said it's d over f but we have n rounds and now if you do the math by union bound you end up with n * d over f but this is still um still negligible uh for communication the prover sends nd elements because you have n rounds and at every round you send a polomial of degree d so that's like d plus one coefficients while the verifier he just sends random numbers. So he has complexity order n the prover is order two to the n and the verifier order n and the proof size is n and the elements. So the proof is not succeed because as you can see it's like it grows linearly with

the with the degree. So the longer your polomial the longer your proof and we'll see how uh we can address this later. Okay now we go to we go to multi-arty computation. So what we we what we have done so far is the ability to prove something. So it's not a proof of knowledge. It's not even a zk proof of knowledge but it's proof of correctness. So someone did some computation and he wants to convince you that the computation is correct. You know the function but you cannot compute it yourself. So all this block here does this proof of correctness. And now we want to outsource this proof of correctness to a network of MPC nodes.

Um so just take as a simple example this polomial a wx1 x2 plus bwx2. Now a and b can be thought of as the coefficients of the polomial and then w is your like potentially witness but it's a constant for the moment and you want to compute the the sum of this polomial. So like coming back to the to the beginning what I mentioned now the challenge is how do we hide so the prover doesn't want the nodes to know the witness for sure but potentially maybe also the coefficients of the polomial maybe he also wants to hide the polomial so our challenge now

is how to outsource the computation of this sum 2 to the n like 2 to the two in this simple example without revealing a w and b to the to the np PC nodes and a and a very in like a very natural way to split a secret value among let's say m parties is just to like randomly pick m minus one random numbers from the field like uniformly random and then the final value the mth value you comput it by simply subtracting the sum of everything else of all the random values that you computed subtracting it from the

original um secret value. So the the the whole goal of this is that you end up with m shares such that when you sum them you have your uh you have your your secret element w. So here like you have the secret you split it into like in this case three elements and you get your your value and this it's super yes. Yeah. >> What exactly is happening with that W?

>> So >> W is just it's just a field element. Yeah. >> Yes. So the question is what we are sampling here. Yes. Exactly. So this W so first this W without the superscript is just a field element and this W with the superscript is also just a field element. Yes. >> How are you determining what that is? >> How are you determining what W with the superscript is? uh >> is random. >> It is random. Yes. I'm I'm sorry that I didn't clear up some notation, but like when you have this sign, it means like just draw a random element from the field.

>> And when you say draw, you just mean basically like pick a random number that's less than the field. Subtract it. >> Um yeah, subtract it from this one. You mean >> Okay. You're just trying to make a set of field elements that sum to the what? >> Yeah. Yes. That sum to the W. Yeah. Yeah. Yeah. Exactly. And indeed. So this superscript like from now on you will keep seeing it. It just denotes a share a random share of of the value W and then we have this square W it means um basically the whole vector of shares. It just means that this W is secret shared among M parties. So when you see the the the square brackets you think of it like a whole vector of shares.

Uh and this this method is very simple, very natural and it already gives like what what we need essentially. Uh it gives you perfect secrecy because no less than marty so no less than all of the parties can reconstruct the secret value and they cannot even infer information about it. You need all the M shares in order to get your value. like you need to sum everything in order to get the the original W. So that's why it's called M MFM uh threshold scheme because you need everything basically to reconstruct and it's very powerful. But you also have TFM threshold schemes where you may need some small fraction

of the of the whole set to reconstruct for example like Shamir secret sharing which is based on on polomials but it's maybe a bit more complicated to introduce but this already works for us and it also has some very good properties like almost all of the properties are good for example it is linear with respect to addition meaning that if you want to compute the share shares of the sum. It's sufficient to uh compute the sum of the shares basically. So you have you have your shares, you just you just um sum the share and you already have a share of of the the sum value. Uh and similarly for

multiplication by a constant like you've shared this value x but you want now to compute the the shares of alpha x and alpha is a public constant. Well, you just um multiply alpha by all of the shares in your in your vector. However, multiplication is the problem and it's not not so simple with multiplication where you like when you simply multiply two shares, it does not result in a valid share of the multiplied value. And all of this here it it like slowly drives us to the to the problem of um remember at the end of the day we want every node to be able to compute our function but working only on his share. So he only knows his own

share. He he has no concept of the secret values. And that's why these properties are super important because this simply means that in your function whenever you have an addition or a multiplication by a public constant then the node can just do his computation in isolation. He just works on his own shares and he already provides a valid share. But whenever you have a multiplication then you are a bit stuck and that's where you need to do some auxiliary communication with other nodes to get some more information to move forward with the multiplication. And we'll we'll see in a moment how this this works. So this auxiliary information comes in the form of this special triples called beaver triples.

And a beaver triple is just this um three field elements of which the first two are completely random like chosen uniformly at random from the field R& multiplication. And every party every every MPC node will will get a share of this beaver triple for every multiplication in your in your polomial. Um and we denote like in this way we denote that the the beaver triple is is shared. So with the use of beaver triples how do you compute a multiplication? So that's that's another I think uh critical part of this

workshop and if you get this I think we are already on the way to actually compute the full sum check in MPC. So we have the shares of X and Y and we want to compute the shares of Z such that X * Y equals Z. But also remember that none of the nodes actually know X and Y. So they only have their own share. And let's see just the process from the perspective of one node from of the i node. So pi will compute those two special values e and f and those are simply he takes his own share of x and he subtracts it he subtracts from it his own share of the three of the beaver triple r and then the same for this value f except he subtracts from his

share of y the other the other the other half of the beaver triple the other element. Then all the nodes exchange this information. So each of them they exchange this EI and FI so that every nodes has the EI and FI of all of the others. And then they can now perform this summation of all of those EIs and FIS to come up with the actual non-shared value E and F. And the crucial part is that this E and F they don't leak anything about the secrets X and F because R and S are random. So if you have a value that that is fixed not random but and if you subtract from it a random value then

you get a random result. So it doesn't leak anything about what what the secret is. So the fact that they exchange their shares and they sum them doesn't doesn't make them learn anything new about X and Y. But they have those values and they're instrumental in what happens next. So next every node in isolation will perform this magic computation. So he will take his own share of the beaver triple t then multiply the e that he computed by his own share of the of the beaver triple then add to it f that he recovered by his own share of the r plus e and f that he recovered times this 1 / m. Now this one over m looks a bit weird

here. So it doesn't mean I mean it will work if you have if you have an inverse of m in the field but in principle that's not so critical. You can also make one node to hold the whole value ef and all the other nodes to just to hold zero. The idea is that when you sum all of their shares of enf but e* f but for the moment just think of it like ef divided by m. And the claim is that whatever each node computed as ZI is actually his share of the result after the multiplication. So that's the claim and why we see here essentially we want to show that when

you summed all the shares as we computed them in the previous slides we will get X Y. So first we rewrite x * y in this way which is exactly like the way we we set e and f right like e was uh x - r and f was x - s. So e x * y is this multiplication when you expand it you end up with this and now when we are summing the shares we want to end up with this uh with this value here. So summing the shares simply if you go back to the to the expression of Z we had TFI. So now we are summing all the TIS and we end up with the with R* S because by definition T equals R * S if you

remember from the beaver triple right then we have E times you're summing all of the S's you end up with S. F all of the Rs you end up with R. Uh and now this is where this one over M comes into because you sum all EF over M M times so M cancels and you are left with EF and if you just like sum this part you end up with with exactly what we expected. So that's why these beaver triples are helpful and and and work and it gives you a bit of a roundabout way to compute multiplication using linear operations with some extra communication.

Uh so now equipped with this new tool of beaver triples and keeping in mind that addition and multiplication by public constant is linear in the shares meaning all each node can compute this independently without any additional communication and having a way to compute multiplication on shares using beaver triples. Now we can actually apply some check on this original um original function that we had. Now the problem was we don't want to reveal AB and W. So now every P uh PJ every note will hold shares of those three ABW and

on top they will also hold shares of beaver triples for every multiplication present in your polomial. And in this case we have two multiplications. So AW and BW. So for each of those in an offline phase even before the protocol starts we need to make sure to distribute the right number of beaver triples to each of the nodes. So that's we what we do here and uh I think the first step is that like it already illustrates how how the MPC computation works because the next steps are mostly linear. In the setup, we want the nodes to collaboratively compute this uh this value the claimed value t prime without knowing a a w and b but

only having shares. Well, each node simply starts by computing a * w just following the beaver triple multiplication. So won't go in detail here but that's exactly what we described in the previous slide and [snorts] the same for bw. So as a result they end up with a with their shares of AW and BW. So they now have shares for this multiplication without having learned anything about A and B NW. So now every PJ like every node has computed its own share of T and if you sum them up you end up with the final value.

uh and in the next steps I mean we just follow some check except we work on pay uh on on shares um and there is not not much nothing much interesting happening here in the sense that uh we don't have any more multiplication so no nothing no more communication between the nodes is necessary for round one it's just local operations so the note already has this aw share and bw share um and he just needs to you know perform perform the summation over x1 and come up with his uh his share of p1j. Um and similarly for p2j and then the final the final check the the trick is that once every node

computes his like shared polomial he also needs to send it to everyone else so that they can uh recombine them. Um so I have also like um short animation describing this process in the general case not for this uh example but maybe if you want to ask something at this stage uh uh I hope you you can still follow at least a bit okay okay good thanks not not to underestimate your intelligence it's just that time is very limited and there is a lot of content to present and I'm speaking very fast that's why I'm constantly you know

asking uh otherwise given the time I'm sure uh you'll get to grips let let's see with the animation maybe if something was left unclear so basically repeating the previous process but in the general case not constraining ourselves to a fixed polomial um so we have the prover uh that distributes the shares of w and the the necessary number of beaver triples to all the nodes um and then claiming his sum is t prime equals to t.

So then each node computes its own share of t prime like its own share of t like ti as we saw before. Then they exchange them um sum everything and come up with the final value. Then this final value goes I mean here is depicted that it's sent to all the nodes but actually each node has already computed it and then each of them just computes their own uh part of the of the pi polomial they reconstruct the final polomial uh then they uh like this shows the non-interactive version in which the challenge r is um computed as as the hash of the everything that was seen

before. So each node will actually compute the same challenge art which is important because like the verifier doesn't know whether we we we work with an MPC setting or like a single prover. So he needs to have the same the same challenge and that's the final the final check where they they compute their own like partial evaluation of the function and the share of the the final check and uh performing the like they reconstruct the the evaluation of the function in the end and u show the final proof. um a few a few words about

complexity and security and like what like stressing why there are so many imperfections in this uh in this scheme so far. Uh so complexity is still two to the end for every node because every node regardless that he works on shares he still need to do this two to the end sums uh communication now we have we have an overhead per round because now each node has to send his pi polomial to the other nodes so and the pi polinomials are at most d + one coefficients and you have m nodes so n * d so this is one level of communication overhead. Another level is every time you have a multiplication you need to do

this distribution of beaver shares like not distribution beaver shares but like exchanging the partial information of this E and F uh computation. So which means that MPC is very sensitive to multiplication. So if you have a polomial or or a circuit that has a lot of multiplications then MPC will be a problem for you because then you need your communication cost will increase dramatic. Um so so much uh for complexity and for security like there are many problems here. Uh first of all like the fact that the nodes reconstruct those partial

polomials this actually leaks information. um they will learn a w a * w and b * w. So they do not learn a b and w explicitly but they learn the multiplication of those two and they can potentially do some um extract some value from this and even worse the final evaluation. So each of the nodes learns the final evaluation of this um of the polomial at a certain uh fixed value. Now this already gives you one one linear equation in A, B and W. So if you can generate more equations like this, you can potentially also recover um the coefficients or the or the witness. Uh

finally, we also work under the semi-honest um uh uh semi-honest MPC party assumption, which means that we don't um we we assume all the nodes follow the protocol. they won't do anything malicious in the sense of you know sending invalid shares um um sending you know or not or withholding a share. We we assume they follow strictly the protocol but uh they can still like extract information from from from their their transcript which is still a li like it's it's a limitation um and that's where all of the other you know parts of our stack come into place. So what we show so far

hopefully gave you a better idea of how MPC works like in detail but leaves a lot of like empty areas. For example, we don't have ZK at the moment for the reasons that that I just mentioned. It's not even argument of knowledge. It's just a proof of correctness. Um we don't have an arithmetization. So um you may may think like how this this like super contrived problem computing boolean sums relates to arbitrary computation. Um and and that that's solvable but we we didn't describe it. So that's where all of the other uh blocks come into play to address those limitations. Um I will very quickly uh just show you that in in

fact it's easy to like relatively easy to just take an arbitrary circuit an arbitrary like computation of addition and multiplication gates and by assigning every gate like to a to an index you essentially end up with you see like a a function that given some like boolean values it will give you the values of the of the nodes in your circuit and then you can have a constraint function that is constructed in such a way that when you sum this f over the booleans a b and c if the result is zero this will imply that uh these abc values are a are valid um valid assignments of your

circuit and that's where the connection comes between arbitrary computation and and some check you can actually craft such a constraint function that when you sum it over all the like boolean possibilities if you end up with zero result you know that your circuit is constrained. Uh I think it's time to already end. Um so hopefully I I gave you a bit of more understanding now how multi-party computation works in order to to compute ZK snarks. We started from the ground up with little assumptions on like on on the background and like mathematical concept. Um and on the way we kind of

built a toy zk snark from the ground up although we only covered part of it. Um which is like of independent interest. I think if you want to if you want to learn um snarks it might be one way to to to get a better understanding. Um um and um so if we had more time of course we could have seen more realistic examples uh when when what happens when you add zero knowledge and commitments and blinding and all the elements that you have in in typical snarks. So if you are interested definitely uh feel free to to

to contact me um either on email or my telegram um handle happy to chat more about this happy to share my slides. There is also a short write up that accompanies the slides. Um happy to share it as well if it will be useful for you and hopefully by now this picture makes a bit more sense. um um and uh we will at least motivate you to learn even more the the like the details of of coax. So thanks uh thanks so much for your attention. I really appreciate you being here. [applause]