ZK13: ISAs for MPC - Mikerah Quintyne-Collins

Transcript

[Music] Hello. Um, yeah, it's great to be here. I think I've been to two in the past and at one of them we actually presented Stufflele when it was like internal at Hashglo, but now we've like spun it out into a separate company and we've been like building it out for quite some time now. So, it's like super great to be here. Um so yeah today I'll cover you know what kind of need to think about when um you want to build ISAs and VMs for MPC. Um so I'll just like set some background first. Um so today like there's sort of two major things going on in computing um in general like distributed systems. Um we've kind of like settled on different kinds of

architectures and approaches. Um whilst like this new thing called like programmable privacy is like you know coming to the forefront. Um right so like what is the state of the shed community today we have like the basic client server model um serviceoriented models blockchains etc um but they come with like a lot of uh limitations um around like trust boundaries privacy um centralization risk and then while that's ongoing we have you know programmable privacy that like kinds of kind of solves a lot of the problems that we saw in the previous slide um and the sort of programmable privacy isn't like one thing there's like a bunch of different tools that exist to sort of solve it right so I think most people

here know what ZK is um has the most advanced tooling but it sort of limits what you can do with you know private data uh t tooling is probably also like getting there um as well um but there are a lot of concerns around you know hardware risk um supply chain attacks um and so some people don't feel comfortable storing all of their private data within for those reasons. Um this FH that's also like very popular. Um but it's still very slow. Um a lot of companies have popped up to just like invent new hardware to like run FH compute. Um whereas but we have this thing called NPC um that sort of gives you a lot of the same properties as FHE

um but is a bit bit more practical. So today we'll talk more about you know MPC is like a programmable privacy primitive today and then just the state of like computers in general like how we've been sort of you know building hardware for computers um right so you know most people have a computer in their phone um and it's usually just on a single device right uh most of it is like based on some form of like x86 architecture um but then there's like newer architectures um that are coming out like risk And then there's even GPUs that are still just like a singular device. Um, and then there's some that are sort of optimized for distributed compute like beam. Has anybody like heard of like Erlang or Beam? Um, that's like

optimized to like run on um a single runtime but like multiple nodes. And then there's some that are even optimized for um certain forms of cryptography like encryption. Um HSM like banks use these. Um, but none of these really capture both distributed systems and programmable privacy. Um, and so today we're going to talk about like how this works in NPC. So just as like a really high level overview of NPC. We'll go into like more details later. Um, it's a way to basically um computer function as a group without like trusting some external party. Um, so you see staffle here. Who's the real staff? Um the function is to determine

like who's the imposttor um or who's the real staff. Um and it's commonly used in settings where like everybody distrusts each other. Um and what that means sort of depends on the setting which you're deploying it in. Um this is very big but I'll go into like more details later about what exactly we mean by those terms. Um but just like set the stage of like if you want to use MPC today what you know you're kind of forced to deal with. Um, as a developer, um, you might like read some papers, you might encounter the word circuits, but, you know, you're not really writing circuit programs for the most part. If you use like a regular general purpose language, you're most likely dealing with like random access machines. Um, but then once you like, you know, go further and really look at um, what's available to

you today, you'll see APIs, you'll see DSLs, and then you're like faced with, you know, the decision to go even further. And then you'll see after that's all academic software to like use more interesting MPC stuff. Um and so like the state of using NPC is still like very early even though this academic software has been existing for a long time. It is deployed in in like to production to uh a certain extent um for a lot of this because like there's a huge demand but you know nothing exists really to alleviate that demand. Um and so like how can you reconcile the way people program today right like any programming language that you use today

is based on like this rap model of computation and not circuits um but there's like a lot of you know optimizations do you get from running circuits and in speed and how do you sort of reconcile that um in this like MPC environment um and the goal of today's talk is to sort of start at like like not as close to hardware but as close to heart as possible like instruction sets architecture but that are designed to work with NPC um and to start sort of thinking about how can we make you know MPC more accessible and performant for uh developers um yeah so quickly what's an ISA um if you know like a little bit of

computer science it's like the actual like set of instructions that your hardware actually uh runs in this is it's all going to be software. Um maybe hopefully in the future we'll get hardware optimized for NPC, but right now it's all software. Um and then the VM is what actually like implements um on top of a ISA like implements the actual like instructions and how their process takes in a program etc. Um so like the main distinction is like one is the specification and when's the implementation. So in more technical terms, so I gave like a very high level overview of MPC before um but this is a bit more specific. Um so you have a set of end parties that want to compute a function um over some input X um but X

is not known to any of the parties. Um and the nice thing that you want out of this is that from each other um you get privacy, right? Um so concretely in this example we have three staffles. Which one is the real staffle? Um every every staff has a set of um inputs that you know they have as proof that they're the real staff. Um but they don't want to reveal that information to each other because like what if you reveal some information to the fake staff and now he can like pretend to be the real stuff.

Um and the way that's done there's like you know these different kinds of like security notions um for like how to build these sort of kind of uh fake stockful protocols. Um right so there's sort of two angles over which we define security in MPC um and this defines uh sort of how you actually um do the operations for computing f ofx and it does affect sort of what considerations you want to uh take into account when designing ISAs for NPC. Um so quickly passive um just means that like one of the stoples here can just like observe you know everybody going through the protocol but doesn't actively do anything to to stop the protocol from

running um or some other like malicious behavior. Um active just means that you know one of the staffles actively tries to like you know mess with the operation of you know trying to determine who the real stople is. And then covert is um which this is not like a great example to show but you know maybe one of the staffles will like cheat only if they know they can't get caught. Um in this case it's only three of them so it'll be obvious like if if one of them gets caught. Um and then there's like over how many you know what proportion of the the parties are you know being honest versus being dishonest. Um and that affects like how you design these

protocols. So in this case it's only three. Um so you can design a protocol for determining who staff is um either by assuming like two out of the three honest or by assuming just like one of them is honest. So the main ways to represent MPC computation um in literature is via circuits. Um so arithmetic circuits I'm sure everybody is very familiar with this um binary and garbled circuits and then mixed circuits where you kind of combine both. So very quickly arithmetic circuits represent uh polomials. You get two operations addition and multiplication. Um and you mainly operate over like rings and fields. Um and you can like sort of represent any reasonable like polomial approximation

using this and it's really great for like linear comp computation um addition subtraction stuff like this. Um binary garbled circuits um are more closely like modeled after your regular circuits that you'll see in computers. Um and instead of having bits you have like each bit is encrypted. Um and you can do like the regular operations like exor and and these are really nice for nonlinear computation um like doing conditional assignments um and stuff like that. Um and then there's like this nice thing in MPC that we called mix circuits that combine both. Um so you can have MPC programs that um are really highly optimized for linear computation

but then when you need to like do some nonlinear computation you can switch to binary circuits and when you need to go back to linear computation you can like switch back to arithmetic circuits. Um it has like a really high overhead so it's a heavily use case dependent. Um but for those use cases it tends to be quite performant compared to just like using a polomial approximation for you know an if statement for example. So fundamentally the nature of MPC computation is such that um you're basically operating over either shares or doing oblivious transfers. Um and these are like inherently distributed objects um that you pass around to other people um in your your

network. Um and like these objects have specific properties for shares um and for like encrypted bits for like garbling. Um addition is free and by that we just mean that you don't need to send some somebody else something in order to like do a plus b. Um which is nice. That means like if in your program you need to do an addition, you can just do it yourself and you don't need to like rely on somebody else. Um but when it comes to multiplication now you need to like incur latency, you need to talk to somebody else. Um especially in the case of like pre-processing protocols, you need to you know generate pre-processing material and then share that with other people and then when you need to do a multiplication engage in a a

communication protocol and this all happens over rings and fields. Um so this like already sort of leads us to um you know trying to think about different sort of instructions or architectures that um might be amenable to like the nature of MPC computation. So what makes ISA design for MPC harder? Um so the first one is access patterns right. Um and then the second one is complex control flow, if statements, loops, functions. And then the last one is that you're inherently in a distributed system. You're no longer on just like one machine. Uh so I'll go into more details. So access access patterns I mean by like accessing arrays, um data structures that are

important. Um this is what makes like programming pretty powerful. Like one of the things that makes programming pretty powerful. You can store things, you can access them. Um but in MPC you can't just access them. you have to consider um like sure like the elements of this array they can each have like secret shared elements but if you reveal what you're accessing then that gives somebody like a lot of information about um what you might be computing um right so this is like there are many options for solving this um oram and garble are like the main options um there's also like special purpose protocols for this um one thing that you'll see commonly is

also just like leak the access patterns but like saying like okay when you need to access an element in array you need to reveal it you can't do um any fancy or things um so for the most part in a lot of ISAs this is actually like a solved problem um because there's like a lot of offtheshelf options for it um the next one that's also pretty hard to do is uh control flow um so if statements branching uh for loops while loops stuff like that um this is actually pretty hard because if you um branch then that reveals um what you're doing right if like I can like run a program

uh and look at what it's happening but I don't have like access then I can like say like oh okay most likely that this if statement happened and not that if statement so in practice what ends up happening is you need to run both branches in order to not reveal what's happening Um, and so this is the actual hard part. Um, and different ISAs sort of solve this differently. Um, but the main way that it's solved is by actually just running both branches, um, for the ISA, uh, sorry, for the MPC compute. H, and then the last bit that's also pretty solved, um, but I think it's kind of underrated is that you're inherently in a distributed system. Um, what you're building for is like inherently

distributed. like every like network device that's participating in NPC network holds a piece of it. It doesn't hold the whole um part of like the state of what you're trying to compute. Um and this is sort of what like dist distinguishes like NPC from like a lot of the other like programmable privacy primitives. um is that you know you have to design from the perspective of um every node is a part of a single runtime as opposed to every node running their own runtime and then talking to each other. Um and that's how normal computers sort of work for the most part is that they each have their own runtime and then they have to like learn to talk to each other. Um but the learning part

isn't really like learning. It's more that like we design protocols to enable computers to talk to each other. Um whereas like here you can you just have to do it from scratch and like consider that when you're building the ISA. Um so general approaches for actually designing ISAs for NPC that you'll see in the wild. Um so the most common one is to just take an existing ISA but then you do CPM emulation within an NPC network. The next one is to like design a custom one and just do whatever you want. Um and the last one is usually to do some combination of both.

um while trying to like balance um the expectations um that both like give you. Um so the first one uh which is pretty common actually is just take an existing ISA um that is like very familiar to you but then you emulate like every portion of that um instruction set within an MPC protocol. Um and specifically that means like for a specific ISA you have a CPU um and the CPU is built up of like different components. Um so you would spec specifically um take the CPU and implement each of those components uh as an NPC program. Um so uh here I'm just showing off like the flow. Uh does this

do something? Okay. Yeah. So this is like the flow of what this would look like. Um so around here you get like the actual program from um like say Mips here. um like you write your C your C program, you target the compilation to a map spy code and then you run the MEP spy code within like an MPC tool chain um and this bit right distribute state across MPC parties um that's where you do the the computation the sorry the emulation and you're doing that with a program counter that's also secret shared um so you're doing the step for every like MEPS instruction um until the end um and like that incurs like a very large overhead um because you clearly

have to go through like every instruction um and perform like a separate like MPC protocol obviously composes all together um but it's like pretty resource intensive uh especially if you have like a real large program um but the nice part is like you don't have to like teach a programmer a new programming language um the next one is basically just invent a new ISA for MPC Um, and like the world's your oyster here. You can really do whatever. Um, but in general, what you kind of see is that there'll be specific op codes for operating over specific NPC constructs. Um, so you can like have shares directly as a first class citizen. You don't need to have your ICA operate over something that's a

bit lower level. Um, you can have our codes that are specific MPC protocols themselves. um and have them be more expressive over just like being like a a load or just an ad instruction. It can be um like a a concrete example can be it can be like a zero knowledge proof. Um there are some NPC protocols that require zero knowledge proofs like special purpose zero knowledge proofs um in order to ensure like active security. Um, and instead of like having to re-implement that from scratch as you would in in um an existing ISA, you can just have an op code that does that for you. Um, and the nice thing of being being able to do this is you can take into account this distributed nature of

MPC and ensure that all the machines that implement this ISA only hold part of the state and are able to like directly communicate with each other um in order to like do the computation. Um, but then the main downside for this is that like you're inventing a new computer. Um, and so you need like new new tooling to make that work. Um, either like a DSL, adapt existing tooling, um, whatever it may be. And then like the flow is more more or less the same. Where's this cursor thing? Okay. Um, the flow is more or less the same. Um, you have like some uh DSL or high level language. um it compiles down to some error, but then you execute the instructions as you would expect any computer to execute. Um

you would just expect this to just be faster um because you don't necessarily have like a secret shared program counter. And then the last one that's also like becoming more popular is to combine both of the previous approaches. Um and the main way this is done is that for the existing ISA uh you kind of extend like the the tooling but then for the spec for sorry for the custom portion you just have like base ISA that handles all the MPC specific tooling. Um and then you use uh like special purpose MPC protocols to sort of make sure that um between the ISA the the not old but like the

off-the-shelf one composes well with the base one. Um and you still do like CPU emulation over like the existing ISA but you've like delegated like a lot of the stuff that makes it expensive off to the base ISA and so you kind of get best of of both worlds where you can reuse existing tooling. Obviously, you still need to change some stuff. Um, but it's, uh, like more minimal to like what people are used to. Um, yeah. So, uh, the implications of this is, yeah, I' I've said this multiple times. You're you're getting a new kind of computer.

Um, tool chains will need to be adapted, um, in most cases anyway. Um, most likely, you know, people will make their own set of trade-offs and there'll be like DL cells for this. Uh, I think the last one is like the most interesting implication. Um when it comes to like speed ups in cryptography, you always think about like better math and better hardware. Um but in this case, uh you can get speed ups from sort of translating your pro your problem from a cryptography problem to a compiler optimization problem. Um which is pretty neat. We don't really do that very often in cryptography, I find. Um and that means like whenever somebody says MPC is pretty slow, you can say like no it's not. you can use compiler optimization

theory which has like you know 50 plus years of research. Uh so where are we now? Um so yeah ISAs already exists for this. Um they're just in a state of being academic um and like hard to use. Um so there's yeah they already exist. There's all all sorts of them. Um these are just the names of papers and software that I've personally used over the the years. and Stafle has like only so much space in his globe. Um but yeah, there are many others. If you uh want to learn more, you can just come chat to me after. Um so yeah, this is the end.

Basically some takeaways. Um we can make MPC practical today by like designing ISAs um that are like production ready to take into account like the way developers program today. Um there's also a really wide design space for like how you want to go about designing ISAs. Um and then the last one which I just said which is uh um you can use compiler optimization theory to like make NPC much faster um and rely less on like just cryptography. Um so yeah, thank you for listening. If you uh want a die-cut sticker of uh come to me after the talk and uh just tell me a use case of MPC I may not have heard of. Um and you'll get like a cute little sticker. Um, if you

want to learn more about what Stop Labs is building, there's a link there, a QR code. Um, yeah, cool. Thank you. Awesome. Thank you so much, Mara. Challenge accepted on the sticker. Uh, we have room, we have time for probably one question. Um, is anyone in the audience, would anyone in the audience here like to ask a question of Mara based on the talk? This is what they look like. Really cute story. Okay, I have a question then. Um, so in certain NPC architectures, there's some assumptions around, you know, the relative strength of each of the parties. Does, uh, that impact how you

would design an ISA at all depending if you had like one very powerful party and then one kind of meant like someone meant to be a client or is that independent of the ISA and and considerations of how you design it? So in the can I uh yeah so in like the garbled circuit oh wait I should be using this sorry uh so for like a lot of the garbbled circuit based um MPC protocols for which like you're using existing ISA and then you like extend it um they do take into account that like one party is like the garbler and does most of the work. Um, so yeah, I would say the answer to that, yeah. Yeah.

Thank you. And let's give Mara a round of applause.