ZKPodcast: Cryptography 101 Multi-Party Computations

Transcript

welcome to zero knowledge a podcast where we explore the latest in blockchain technology and the decentralized web the show is hosted by me Anna and me Fredrik [Music] in this episode we try to introduce multi-party computations we start at the basics and try to lay a foundation for episodes to come [Music] before we start we want to say thank you to this week's sponsor Aragon if you're

looking to connect with some of the brightest minds working on decentralized governance and web 3 development then you should check out Eric on the first Aragon community conference happening on January 29th and 30th in Berlin enjoy presentations and discussions on important topics like open source sustainability models humanist technology in oppressed societies and a retrospective on the Dow by the creator himself you can learn more about the conference and sign up to attend at Eric on dot one that's ara co n dot o ne C and Berlin one last thing if you want to connect with us or if you want to support this podcast please check out the links in our show notes and now here's our episode on MPC's hi Fredrik

hello today we're gonna be talking about multi-party computation or MPC's this is a topic that I think has come up enough times that it seems really worth it to do a deep dive and a real introduction personally I feel like we've heard about it a lot in previous episodes and even though I have a had a rough idea of what an MPC is I haven't really had a chance up until now to dive in I think it's worth noting as well that MPC is such a huge broad topic that that spans like several different technologies and DIF like areas of cryptography and math and everything that we obviously can't cover even a fraction of it here but I think

the goal is to at least give an idea start with some of the fundamentals and then maybe we can lay some groundwork for future interviews so I think maybe just start off we should define what an MPC is I have a few definitions here there's a couple I like a multi-party computation an MPC is a cryptographic protocol that would allow a group of actors that may or may not trust each other to compute a program and generate a new function using their own secret inputs in this setup each actor would have secret data and each could not infer the data of others from anything that they're getting so everybody's data is secret from the other people in it when people talk about NPCs when they present

them in videos or what-have-you often you'll see computers in a circle each one of them representing actors and basically what they're doing is they're going to be contributing something to this NPC that would result in an output the inputs would be completely secret from one another the output could be shared often is shared and I think where we've seen this covered in the past and where we've talked about it before just to give a concrete example off the bat is like in the ZK snark scenario where you have this quote-unquote trusted setup or toxic wastes you know thing or when we talk about random beacons that's a multi-party computation to produce a

random value so it comes up a lot in the blockchain world in different scenarios and they may or may not be called NPCs but something like the Z cash you know ceremony powers of tau is another example of like a multi-party computation so yeah I think going back to the reason why we wanted to cover this as mentioned it's come up a number of times in previous podcast it gets mentioned our thinking with this episode is to really go into the basics to look at examples where you our listeners can hopefully even understand it from just us describing it on a podcast like always with any of these topic I personally like to look a little bit

into the history try to frame it like when this happened so secure computation originally was devised in 1982 and this was a secure two-party computation and this was introduced by Andrew Yau but NPCs as we know it the first initiation was done by gold rise McCallion whit Gerson funny Macaulay comes up a lot in a lot of these talks so this was the first time that they started to add this like multi-party aspect to it this was all done I believe in the 90s like late 80s in the 90s but the first time that you actually had it applied in a large scale was in Denmark in January

2008 it had to do with a sugar beet farmers where they were actually selling their wares in a market and they were able to use MPC's to basically create this privacy that one would need in such an auction and that is indeed one of the types of use cases here where let's say you have an auction and you don't want to reveal your bids but you want to be able to reveal what the highest bid is of something like that and yeah then you can have a secure multi-party computation where the computation is find the highest number and each individual doesn't have to actually reveal what their bid is so let's go back to this definition of MPC's and get into some of the building blocks of npcs

when you talk about basic MPC's you're definitely talking about a combination of polynomials and it's funny like to anyone who is in computer science and has studied maths and works with math a lot polynomials you'll feel like yeah polynomial that's cool but as somebody who studied math in high school a little bit in university and has not really looked that much at math for a while I actually had to go check out polynomials when I looked at it I was like oh wait this is so we've all we all know polynomials they're basically something like if you've ever seen a function with like five plus three x plus x squared plus something x cubed that's a

polynomial and in high school you very likely done things like added polynomials together subtracted polynomials you've maybe even done a little bit of interpolation so finding points along a curve and then figuring out what the function is from that and these these functions actually do make up the basis of npc's at least the basic MPC's as far as we can tell of a type of MPC yeah so let's talk a little bit about how to do secret sharing with just basic polynomials and sort of how that works I think it's useful to visualize a graph like a graph paper blank slate in front of you if you have one dots on

this graph then there are infinite number of lines that can go through this dots but if you have two points on a graph then there's only one straight line thing that can go through both I think this is basic intuition and anyone can sort of easily visualize this in their head I hope so if you wanted to then say you have a function f of X this is a straight line so it's something plus X or something times X and if you said I have the number six this is my secret you take a function such that f of zero equals six

and then you create a line such as six minus X that would go through f of zero equals six and some other points and then if you wanted to share the secrets where it can only be constructed by bringing two things together you take any two points on this graph on this function six minus X and you give one point to Alice and one points to Bob now Alice can't reconstruct the secret because she only has one point and there are an infinite number of lines that go through this point Bob can't reconstruct the secret because he also only has one point but if both of them go together and join forces they can reconstruct the

secret because they both have the share of this secret so basically our breaking up the secret into two points and or two shares so this is a very simple model basic intuition it breaks it up into two shares and both shares are needed to reconstruct the secrets but if we want more shares or if we want to sort of an end of M system where it's n number of shares that is needed out of the M total to reconstruct the secret then we have to expand on this so the first obvious expansion is that we can go to higher degree polynomials so what I said was a first degree polynomial there's

only X if you go to x squared then you can have three points on this graph if you go to X cubed thing you can have four points on this graph and I don't even think it's you can have you actually will need yeah every time you go up a level you're gonna have to add extra data points in order to actually recreate this function indeed and so you can sort of choose the degree that you want and the number of shares you want to split up and you will always need more than K shares and the K degree polynomial but you can apply various tricks so if you want an end of M system you can make some of the shares completely public to everyone and then

distribute them accordingly but these are less important details so maybe to go a little deeper into this we can use an example that we've seen in other videos and and descriptions of NPCs the idea here is that you could actually create a voting system where individuals could submit a vote and the outcome the total tally would be calculated but no individual vote would be revealed to other individuals voting and the example that I think we're gonna describe has three actors should we give them names sure Alice Bob and Carl or Carol so in this example you have three individuals

each of these actors will have their own polynomial function actually so they'll have a s of 0 it represents their vote and a function going through it and those functions can be totally different from one another but when you combine those functions you actually get a function that represents the tally so maybe we should go a little bit deeper into that so yeah they all have their own unique polynomial F of 0 is basically their votes which we can say for simplicity is 0 or 1 for a yes or no when it comes to sort of tallying up these votes we add all of their polynomials together so f of 0 of resulting polynomial will obviously be

the addition of F of 0 of all of the parties polynomials so it will very simply be the tally of it but how do you construct this added polynomial in the other points without revealing each individual's polynomial well it turns out that by revealing a point on that polynomial they can reveal some information about their polynomial but not the entire thing so Ellis reveals F of one Bob reveals F of two and Carol reveals F of three and so we can then do Lagrange interpolation to find out the resulting polynomial and then we with

that polynomial King calculates F of zero and get the resulting votes all right the resulting tally of the votes so what's interesting in this example is you're kind of making a few assumptions here you're assuming that people will actually say 0 or 1 in terms of a vote and you're also assuming that the because you're kind of doing this sequentially you're assuming that the person who's kind of reporting last would be honest those are things that are not in any way taken into account by the construction of this so that's a bit of like a flaw in this in that you wouldn't want to do this for

voting in a mass scale but if you have like three semi trusted friends and yet you don't want to reveal your vote to them this might work yeah so although this is kind of not something that I deal with on a regular basis and not something that I'm super into or like know a ton about but I can see how it goes from this to a more advanced system because of these things that you're just talking about first of all there's an honest majority assumption here and that most people behave honestly or you can sort of cheat and reveal what other people are doing there's the last man problem they were talking about where

when it comes to the person they can I like to take the other people's reveal the information and either reveal their information honestly or they can change their votes to affect the outcome such that you know they then when it comes to them and they reveal something that they hadn't originally intended on revealing and then of course like in a simple math based system like this we say that it is the rule of the system that you that f of 0 should be 0 1 but I can make a function such that F of 0 is negative 12 and I messed up the entire thing and there's nothing that anyone can do to prove that I messed up

the entire thing so there's obviously a ton of downsides or a ton of like floss in this system and obviously it's because it's so simplistic but what I would really like to do in future episodes is dig in with people that know more about this on how you address these flaws I wonder I kind of want to go back a little bit to the to the example we just gave because I think like as you were saying earlier Fredrik with this graph so you have like a y axis and an x axis you have a dot in that first example where you had a dot or two dots in this case what the line actually looks like it's not a straight line often it'll be something like each

individual function will have a few dots along a curved line and wherever it's passing through the y axis if it's passing at 0 or it's passing at one that actually reflects their secret it's that f of 0 which actually defines what they have contributed to this and each of them should be crossing through the y axis somewhere which represents where their vote would land and then the larger function wherever it crosses through the y axis that is the tally so that example that we just gave we're talking about a polynomial with order 2 an example could be 3 plus 1 x + 4 x squared as you increase the order you

will go into X cubed you'll go into X to the 4 the complexity of the calculation we'll also increase and higher-level NPCs will be doing more to these polynomials than simply adding them yeah even with this simple thing doing multiplication this is significantly more difficult and you have to modify the system to be able to do that so before we cover maybe some more just examples of this simple system what I would say is I highly encouraged people to check out the videos and in the show notes that sort of explains the simple system and then go and like code it up because it's so simple and easy and you can easily do this like in an hour or

two and just working with this practically I think you will get a great sense of how this stuff actually works at a very basic fundamental level and give you an intuition of how these systems work that might then lead to something more useful down the line so another example that I did see was so the voting one as mentioned one of the issues we have is like there's no constraints over whether it's 1 or 0 we're just sort of trusting that the participants put in 1 or 0 but they could screw that up and put like minus 5 but another example which we couldn't look at would be contributions to a bill so say you're sitting at a table with some cryptographer friends because we

all have those and we do actually and you want to pay the bill and everyone wants to contribute something or maybe nothing but you don't want to reveal what each of you is contributing you just want to know that you've reached the top the sum that you need to in order to pay this bill so this could be another example where you actually would use a very similar setup but there your contribution it wouldn't only need to be between 1 or 0 I guess and this this is something also that sort of goes out as as we're talking about this I guess that you have to somehow in most of them work like advanced NPCs create a constraint system so that you aren't able to go

over a certain limit or you have to always have an F of 0 that lands on something that's expected I very curious but that would actually look like yeah likewise PS this is a true zero knowledge episode we really like living are living our name right here I also want to go to more dinners where I'm allowed to contribute nothing all right and then I think the most the most relevant example of an NPC that we have definitely talked about on this show and we kind of mentioned earlier in this episode that is ZK snarks and the trust of set ups so

the example that we gave is mentioned is extremely simple the trusted set ups have different characteristics than the NPC that we just described for example the embassy we just described you need to actually have an honest majority whereas if you look at trusted set ups and CK snarks those are NPCs they're a forum of an NPC but in those multi-party computations the majority of actors could be malicious could act incorrectly but if one honest participant contributes their secret value correctly then the outcome is still correct toxic waste in in our simpler like super simple example is your polynomial like

in this system yeah there's an honest majority type of thing let's say that it is the same type of constraint that is in in the power so tell for instance where at least one honest player is needed for the system to work the polynomial equivalent of that would be that at least one person after contributing their public value throws away the polynomial so basically they construct this polynomial provide their F of one function to the public and then deletes their entire polynomial so that no one can reconstruct it and then you've contributed your public part and deleted your private parts and the private part is the toxic waste so in in

a powers of tau setup if someone collects all of the secret polynomials then they can reconstruct the z case marked parameters and crates of this sort of fake snark that validates to the same thing I've been kind of curious about that do we do we read toxic waste as each individual secret or as the combined secrets I guess each one is slightly radioactive yeah yeah exactly I mean it it's the components I think Zuko said the components of the of the toxic waste and that the toxic waste is if they are if all the components come together to create it but yeah they are all kind of toxic yeah a little bit so you'd like

that's why you want to delete it I was in a workshop recently where we were actually going through the steps of a trusted setup and someone did make the statement that if there were you know in a trust to set up a few members that likely wouldn't get rid of that secret they wouldn't destroy their polynomial or what have you that it would be less secure but that's not really true it's not that it's less secure it's as secure because it doesn't matter if there's one or two malicious actors the only risk as I've understood it is if everyone's colluding that means like if you have a smaller groups they have three people who know each other the likelihood of

them colluding is probably higher than like a hundred people who are scattered around the world and driving into the woods and yeah I mean it is probabilistic they're like security argument of if some people are keeping their secrets around it is more likely that everyone is keeping their secrets around but it's only a security risk if indeed everyone kept them around when you dive into these topics when you talk about NPCs they are often combined with or compared to some other encryption ideas so one of these is fully horrible if I can say that hold on fully

homomorphic encryption feel like everyone stumbles over this fully homomorphic encryption yes fully homomorphic encryption fhe for short that is often either yeah it's often used either in tandem with an MPC or compared to so do you want to do a quick maybe high-level explanation of how you understand f8 fully homomorphic encryption yeah sure so fully homomorphic encryption is where you can encrypt something but you still retain a domain of functionality over it so let's stick with a simple example of

addition again you have numbers and you have addition so you want to encrypt the number or six and then send that out to people then someone wants to add something to this number but they don't know what the number what the original number is so I want to add four to this number six but I don't know that it's a lower like I'm not allowed to know that it's a six so I get the encrypted text and then I add four to the encrypted text and get another encrypted text then I send that back and the person who originally encrypted the six can decrypt ten so they know that a four was added

but you do not the person who added four don't know that they added it to a six and so you could you could construct a similar voting system here where the original person sends out a zero every one adds one to it and keeps sending it along down the chain and then when it gets back to the originator they're the only one that can actually decrypt this so they're the only one that can see the tally and when they decrypt it they see how many people at it and I want to it whereas each individual wouldn't have known what others yeah they can see what came before them and like when in sent around they can't see what the actual talent is just in the example you gave the difference here that I can already

see is that at least with a lot of the npc constructions that we've looked at the resulting output is actually u it is known by the participant or it's used for some then it's somewhat public yeah in this case what you're talking about is people having they I guess they could still be using something in secret but they're just adding something into a black box and the outcome of that is completely unknown yeah and you can extend this to quite a large domain of stuff and so that that's where the problem quote-unquote of fhe is is that the greater you expand this domain the more difficult it becomes to do it so there's

you know new cipher has been doing some great work speeding up fully homomorphic encryption for some domain and what they're doing I don't mean in in principle you could envision if you wanted to do like video compression without revealing what the video is you encrypt the video send this out and then do video compression on this encrypted texts that you have no idea how to decipher and then you run that through your entire compression algorithm and out at the end comes another encrypted video that when the originator gets it back they can decrypt it and have a an actual iing transcoded video transcoding

something in a fully homomorphic domain is probably impossible right now but you can do certainly much more than addition and multiplication these days but that's the simplest explain or like simple simplest example I often like I think you often hear people talk about fully homomorphic encryption as a no as an option but when we dig into it we also I think everybody will admit that it's it's just not there in terms of the research yeah I would say that it's it feels like a similar state to the Starks were like when we talked to Stark where you know just three years ago and doing simple stuff required hundreds of gigs

of RAM and we can do that today without a problem I similarly I don't know with fuller no more freaking encryption if it's like a research problem or if there's like some innovation so necessary it's actually like break through some of these bounds or if it's an implementation problem and no one is really like put in the effort to make a really fast and performant version yeah so I don't really know where the boundaries there lie and like what can we do today what is too much and I'm like that again we should have a new cipher on to talk about what their work has been done on that field because they've they've sped up some things like 10 10 X but just through implementation as far as I understand but you know

whether or not that's practically useful and applicable yet or if they need another 10x or 100x before it actually is I don't really know now one other term that you often hear used in relation to NPCs or compared to NBC's RT es the stands for trusted execution environments so I think the comparison comes because it can guarantee like the integrity and confidentiality of some data but this definitely seems like a very different concept in this case you're talking about a secure place in the hardware where a computation can be done but I don't see it using any of the same concepts or many like polynomial

concepts that we've just been talking about and yet it's often compared yeah I would say it's very different but a lot of people trust the hardware manufacturers a lot here which I find questionable so the this T is like Apple's secure Enclave that almost every iPhone has now like that's where it stores her fingerprints and you know supposedly it's a like this thing isn't connected to the internet so no one can like Hackett's if you actually break into the device it's supposed to be hard or impossible to get out like physically and you can like it has certain properties of how things are executed so

you have some evidence of it being executed correctly but again this is down to implementation of like how are the hardware hackers actually do this and there's there's some good people like playing around with this stuff in the fields like both in blockchain and crypto in general that I'm sure have much better explanations of this than I can but yeah it's it's like you say it's a hardware play where you kind of have this execution environment and supposedly produces some evidence that a computation has been done correctly would you say that there's any other technologies that also are in this

category I feel like I sometimes hear like ring signatures put into this but that's really different isn't it yeah I mean it's multi-party in that like a lot like multiple parties are going into the ring signature with their signatures yeah but calling it a multi-party computation we maybe in the broadest definition of the term when we were talking to Ellie Ben Sasse on from Starke we're in a very recent episode I asked him like where the future of you know Stark like or zero-knowledge technologies could come from or what you know what is he looking forward to and

he mentioned that this concept of NPCs it's been around for a long time but like Starks were like starts there weren't necessarily technologies in place it would make them usable and I would I'm actually really curious about like what other NPCs are out there like what what super hyper theoretical cryptography NPC constructions are floating around and they're still totally like impossible but you know maybe they come into two relevancy in the near future maybe in this space specifically so maybe to wrap up we've mentioned a few concepts that are sort

of either competing with or being used along with NPCs there are a couple other at least terms that are brought up one of these is Shamir's secret sharing and the other Isla Grande interpolation maybe we can talk very briefly about yeah so what I would say is if you go from that easy polynomial example and that's something that you've played around with and understood the next logical step to go to and start playing with this Shamir secret sharing so here you're making it a little bit more abstract a little bit more complex and you're breaking up a secret into an N of M system so you can

say I want this secret to be broken up into 23 pieces and I once you know you need 17 of them to be able to reconstruct the signal secrets so you can fully define all of these parameters and then you know break up this secret into multiple pieces and this is something super useful too if you have like a private key and you want to distribute that over five USB devices that you spread around your house like this it's it's a useful tool in itself where it's the polynomial thing is more of like a learning experiment and we have like Rob that parody he has a library for Shamir secure cheering in

rust that's pretty easy to understand and nice to look at so I can link that as well so that that's a useful thing that might be fun to experiment with as well I don't know how you would use it in sort of a replacement for a zero knowledge proof kind of setting but as a replacement for election or signatures or other like an event signing systems I could see like a multi-sig type thing but it these the secret sherry and it's like the data is broken up but when you combine it it becomes the full piece of data you don't actually do it through polynomial interpolation or do you because it sort of looks like yeah you

do so it still works on the same basis so yeah so if you go to implement this you do create these polynomials and you you do create them with like super large prime number stuff to have security and then you go to reconstruct to these things so basically each of these secret pieces is a point on the polynomial I mean it's still the same fundamentals and then you use l'orange interpolation which is just a formula to reconstruct the original polynomial but instead of like being a number that is the secret outputs it can be any like 32-bit value

I mean you can always see any random any arbitrary number of bits as a number but yeah it's it depends on how you interpret things and the other thing you just actually mentioned another term that has come up a lot and that's this Lagrange interpolation one thing I actually went through a few exercises to do some interpolation but what I realized I didn't quite understand was how to introduce the finite field is that the thing that makes it a Lagrange interpolation I don't know I think you you would call it a Lagrange interpolation even if it's not or finite field and I think we we've definitely

mentioned I think we've already covered what interpolation is it's this idea of taking a minimum number of data points in a graph and being able to recreate a function from that actually I am curious how exactly the Shamir threshold relates to npcs because they're always used together or it's almost like you need to understand Shamir threshold schemes in order to be able to build npcs correctly yeah I've noticed that too that they're the basis for a lot of things and I guess that's how you kind of define your fundamental building block on which you attach the rest of your logic but I

don't really know how how that ties together what's yeah it's it's a cool concept I like I'm still I think my I'm still not sure how it relates to exactly how it relates to NPCs like it obviously it's in the same space but yeah I'm wondering if it's not like a used in tandem or if it's actually underlying more advanced multi-party computation if anyone feels like they have a great explanation to that hit us up on the email and in general I think that's what we want to we do want to say to you is we are we are zero knowledge and this is a show where we often bring on experts to explain this stuff to us this is an episode which we did a little bit of

research on our own but it would be wonderful if you want to send us an email telling us where we're right where we're wrong if you want to ping us on Twitter and let us know if you can answer some of the questions that we brought up I'd be really fun to hear from you anyway thanks Frederik thanks for uh thanks for having this chat thank you and I'm looking forward to digging into this a lot more in the future and to our listeners thanks for listening thanks for listening [Music]