ZK11: MPC-Enabled Proof Markets - Daniel Kales

Transcript

[Music] yeah welcome everyone my name is Daniel from too and yeah as we said I'm going to be talking about the topic of NPC enabled proof markets and yeah going into the motivation CK proof markets a very Hot Topic at the moment you can of course Outsource these heavy costs of the proof generation to powerful servers and even even more Topic at the moment use dedicated Hardware to speed up the proof generation even further in a normal workflow a user might just request approve from a proof Market the proof Market assigns this chob to some kind of prover note and then the user must provide their witness input to the

prover the prover delivers the proof and receive some kind of payment for the work that he's done and often neglected this this privacy loss aspect of the delegator that you essentially have to give this Prov your secret witness your secret input because he has to do the actual proving and one technology one technology that can help here is secure multi body computation and while CK might be the Privacy technology that most people here are very familiar with MPC is also another very common privacy technology that essentially allows multiple untrusting parties to compute some function on their secret inputs without revealing them and then some output is revealed to

one or more parties most NPC prot protols are based on some form of linear secret sharing where linear operations are then free to compute and this free is kind of under quotation marks because you still need to do the actual computation but parties do not need to interact with each other however for things like multiplication of secret values you have to communicate with each other the MPC parties do and so these are a little bit more costly and the secrecy of the shared values is guaranteed as long as no more than some configurable threshold of parties collude with each other and are honest NPC is also a very flexible

technology and you can use for example the same fields for your MPC protocol as you do in Zer knowledge proof systems and you can also build MPC protocols that work over elliptic curve groups allowing you to do stuff like multi Scala multiplications and so one uh thought process that has happened over the last few years is what if the function we execute in the MC protocol is actually the CK prover itself we have our private witness which is the secret input which you share among the MPC noes and then the proof is just the public outputs and this is exactly the setting that is matched by this MPC proof Market setting where the user is now again requesting approve

from the MPC proof Market we select some notes the user then shares this witness to these notes and the notes together do the MPC computation and then the proof gets delivered back to the user to the market and the MPC notes that uh contributed to the computation they get some kind of reward so this topic is often also called collaborative snars and these MPC use cases are just a small use case of collaborative snars and in the next part of the talk I just want to give you an overview of why MPC and CK is a nice combination together in this use case and some of the efficiency concerns and

challenges that are still out there there are only a handful of papers uh in this topic I've given them here on this slide and I would implore you to have a closer look at these papers if you're interested in the topic of MPC combined with s knowledge but in the interest of time I will not go into too much details here but rather try to give you an uh overview of the MPC friendliness of these building blocks why this is a good fit for MPC so first very common building blocks in Zer knowledge proof systems are ffts and essentially ffts are just a linear operation in the input vector and then due to the linearity of the secret

sharing scheme we can just have the parties essentially perform the ffts on their local shares to get shares of the output and this is very nice because all of because all of the operations are essentially local you do it on this same field as you do in the Ser knowledge proof you can even reuse some Hardware acceleration for this uh process a very similar uh thing happens for multiscalar multiplications which is a linear operations in for example the scalar and in most use cases that we need for zero knowledge proofs the points are actually public for example in commitment schemes so you can again perform multiscalar multiplication on the shares of the

secret scalers and again can use re use the hardware acceleration polinomial operations are at the heart of many CK proof systems so again we have for example polinomial addition just a linear operation parties can do it uh on their own shares and then for multiplication we go through an fft do ele element wise multiplication which again as mentioned before requires some interaction between the parties and then we go back through an inverse fft polinomial division is also pretty nice if the deviser is public which is also often the case in CK proof systems this is again just a linear operations which parties can do locally and otherwise the cost is about two multiplications and

finally evaluation again evaluation often happens at public evaluation points which again parties can do on their own local shares of polinomial going into a little bit more complex building blocks for example sum checks and product checks so for a sum check we just have a very simple proof via commitment to a related polinomial and this related polinomial can again be computed with just subtractions and division by by a public value so again parties can do this operation on the local shares and then we have to do a polinomial commitment so this is essentially just the cost of the polinomial commitment scheme again and

also in the multivariat subject case they're also very efficient uh protocols to do it in MPC for the product check it's a little bit more complex since the helper polinomial that we need here is a little bit more complex to compute we essentially need a help of polinomial where the values are the partial product so the products up to a certain index are the values of this polinomial and there are specialized NPC protocols to compute this partial product in a constant number of rounds but we still have linear communic ation so is a very common thing that you take some part and replace it with a more specialized MPC protocol talking about polinomial

commitment schemes for very popular ones like kcg and in a product argument the commitment is essentially just a multisol multiplication with public points which is very nice for multi computation and then for kcg the opening is again just a commitment to related polinomial which we again can arrive at by uh division by public value and subtraction and then again a polinomial commitment for the inner product arguments you have some logarithmic number of rounds where you do some kind of random linear combinations which are also pretty good for MPC however the situation is not as nice for fry based commitment schemes where

the actual low degree tests are actually very MPC friendly however the big bottleneck is the vector commitments so you commit to evaluations of uh some polinomial over a very large domain essentially and then uh the hash function calls themselves are the cost because since the values are secret you have to evaluate the hash function in the MPC protocol and even if you use something like posidon which is not only CK friendly but also pretty MBC friendly this is still a very uh impractical overhead and these commitment schemes are also the bottleneck in some of the other commitment schemes or that are using some Merk Tre

commitments as a uh first trick to work around this issue we can have MBC parties commit to their shares instead of the underlying values so this means that parties now no longer have to evaluate the hash functions in MPC however each party does their own Merkle tree and adds it to the proof so this means the proof size Grows by a factor of n the number of NPC parties and also the verifier work Grows by this Factor since he needs to verify much more Merkle trees and recombine the shares and continue with the verification process and then we can work around this issue even a little bit more by adding a recursion step that is common place anyway in many fry based systems where

you have essentially a recursive verifier that handles all of this new MPC stuff does all of the verification all of the recombining and then because there there's no need for privacy anymore in this recursive verifier you can do it outside of MPC finally one of the challenges that many academic papers do not talk about the papers mostly focus on the compatibility and efficiency of these proof system building blocks and only talk about uh extended witness generation and passing and extended witness generation is essentially the the process of going from the the input the witness input to something that can be used in the proof system like the uh witness columns in the plunk assignment

table the full rncs witness whatever and if you think about something like ckl the actual input might be to a machine learning model is very small usually but the whole execution traes might be multiple gigabytes in size so this is a very large difference in the actual input and the full extended witness also these witness transformation might have Transformations from circuit evaluate to Circuit satisfiability problems for example in the field inverse in Z knowledge we usually don't compute this inverse directly but rather inject the result and then just show that b * a is equal to one however if this is a secret witness we actually need to compute the

B value in multi body computation and therefore we are going back again to Circuit evaluation which might be more costly for a lot of problems and there might be many gadgets that are NPC unfriendly in this way so thank you for this uh for your attention in conclusion I hope to have given you some overview of why CK and MPC can be a very good fit and there the main building blocks are already very NPC friendly but there are still a lot of challenges to solve to kind of bring this field forward so more research is needed and especially more research in this intersection of MPC and C knowledge because there are hundreds of CK resarch papers every year

but only a very handful of them are in this MPC zero knowledge intersection and also something to help push users to actually play around with this stuff and this is something that we are working on uh now and over the next few months is to actually try to bring this to kind of production systems that are already out there that users are familiar with uh CK dsls to also essentially enable them to do MPC proofs and if you're interested in this topic I would implore you to join the uh telegram group for collaborative snars or contact us directly thank you thanks any

questions hi thanks for the talk I actually have two questions do we have time for two questions right so first question is you mentioned uh that we have protocols for multivarious subjects to can you tell us a little bit about it um yeah essentially the the main operations there are uh from what I remember the essentially building the bookkeeping table to have essentially fast provs and they are also just essentially doing linear combinations in each step so this is also very efficient there and one of the four papers on the on the paper slide actually covers the the multivariat uh Su check case and they show that this can be done very

efficiently yeah okay so second question um so different papers deal with the malicious security case different so I don't know the EOS paper for example does something ad hoc and sort of clever there other papers go blackbox what how would you summarize the status about that but yeah so that's also something that's very interesting as you said there's one paper that takes an approach that the CK comput computation itself is already kind of error checking and so you can kind of use this property to kind of reduce the need for malicious Security in the MPC protocol of course you can take an Malicia secure MPC protocol and just treat it as a blackbox

but this is more expensive but of course this requires a lot of custom work because it's not that easy as just trusting the CK computation you have to do a little bit of extra like the the EOS paper did so it's a trade-off that you can either have a generic solution that works is a little bit slower or you have to invest some investigation and proofs for the specific proof system I would say thank you okay so maybe the next speaker can already set up and then we have time for one more question hey thanks for the talk again H more on the on the whole idea of using MP CN ZK to build pro proofs that are

private and also not not build in the user's device isn't there a wait for the isn't there an incentive a perversive incentive for all of the MPC parties to always store the encrypted data because there's no way to really slash them if they ever disclose them and they there might come up point point in the future this data becomes valuable it might be extractable so I was wondering is there a mechanism to actually like slash them or penalize people that eventually share their their secret shares yeah it it that's an interesting uh area of work that's not really present in the the current proof markets because they just select a single party and then you have a little bit more interaction uh between as with this party in the in the PC setting you would

have to select many notes and then uh depending on your threshold if one of them is behaving honestly then you're good enough but if you have like an economic way to select these notes for example by via bits then you can just Mal ious ly bit very low or very high depending on what you need to get selected and then kind of try to steal the secret so you cannot use kind of normal strategies to select these nodes but have to have either some kind of trust additional trust with te MPC nodes or have some Randomness in there and stuff like that so it's it's a open question I would say to really how to

select these nodes in a in a good way okay thanks a lot