Taking MPC to internet scale

Transcript

Hey, hey hey. [Music] Hi everybody. Okay. Um, okay. So, uh,

I'm going to try to get a lot into this 20 minutes. Uh, so it's going to be a bit of a fast talking. Uh, I'm Eric Galansky. I'm the VP of technology at Fireblocks. Um, and the first question is why do I talk about MPC? So, there's actually two reasons. Uh, the first one, as Fireblocks, obviously we're a very big uh, provider using MPC wallets as part of our offering. um passed trillions of dollars through our system over the last few years. Uh so we've been doing a lot of production scale MPC uh and researched a lot of it, published a few different protocols. That's number reason number one. Reason number two is because I'm not a cryptographer. Uh and I think MPC and cryptography in general

are too important to leave it to only cryptographers. uh because once you introduce some of the architecture considerations, there's a lot of things that come out of it and that's a lot of what this conversation is going to be about. How architecture meets cryptography because we want to combine them into solutions. Okay. So, we're going to go through a few chapters and in each one of them we'll close with a bit of a conclusion small one and continue to the next one. The first one is ECDSA. The question is why do we use ECDSA? And the answer is because somebody patented Schnore. Okay, so Schnore is an amazing protocol, super easy, super fast, hard to easy to MPC, a lot of advantages, but for 20 years it

was patented. And so when a lot of the systems that wanted to use this kind of a cryptography wanted to use, they couldn't use it. And so an alternative was developed. I will not go into the details of this entire process but the alternative is not as nice in some places right it created some challenges but everybody adopted it because a patent and actually a strong patent can really take over this kind of a situation so we see ECDSA in blockchains like you know Bitcoin and Ethereum some of the newer blockchains adopted because it was after the patent um but we see it in iMessage internals we see it in Pasis most of pass is our ECDSA. We see it in TLS certificates today. Most of the

websites you'll visit will use ECDSA for the digital certificate. We see it in passports like and all of the digital identity stuff. We see it in a lot of places and it's not going to change. Okay. So changing a technology like ECDSA is hard and ECDSA became the de facto alternative to RSA. So if you didn't want to use RSA for all of the reason not to use RSA in your use case, you went ECDSA. And so now it's built into a lot of places. Um there's a great lecture by Abishalot that you can uh look up that talks about why it's really hard to root out ECDSA from all of the systems it's inside. Uh blockchain's included, right? If somebody wants to change those things, it's really hard to

get to the consensus unless we get to Busquantum. And this is actually probably the first time that somebody will be able to change ECDSA to something else. So it's a bit of like the, you know, the the BitMax the uh the cassette thing. Um, okay. So great, that's number one. So ECDSA is here to stay. Uh, let's talk about MPC. So MPC is actually quite a like a technology that has been used for quite some time now, right? It's invested invented in the 80s, but really found its product market fit in blockchains.

Um, in wallets specifically. We'll talk a bit about this. Uh but like now especially in our space people usually know what MC MPC means which is not the case in a lot of other places in a lot of other ecosystems. Um there's a few way to categorize uh MPC. So first way is MPC versus two PC. So it's either multi-party or two-party which is important distinction. Another distinction is honest majority versus maliciously secure, right? Like do we go by the majority or do we actually like any single participant can know the protocol is secure by definition of them being secure. And the last one is general purpose versus DSS. DSS is very specific to digital signatures. Um now

why is it used in wallets? Okay, why do people use MPC in wallets? There is actually only three main reasons. The first one is key theft. We all know that a single point of failure is a problem when we have something important to secure. MPC solves the single point of failure problem. Now you have multiple shares. You need to get all of them or some amount of them to actually get the key. Much more secure. No single point of failure. That's number one. Number two is self- custody. Now obviously self- custody is more regulatory oriented. But like if we think about the technology aspect of it, we don't want the vendor to have the entire key because if the vendor has the entire key, they can do whatever they want. But we also don't want the client to

necessarily have the entire key because if they're hacked, they lose everything. So there's like this control of the the vendor that we want limited. MPC gives us that. And there's the uh uh security of the user which the vendor can provide which MPC also gives that. So those three things basically created a situation that MPC became a de facto standard in uh um blockchain wallet security in a lot of situations especially in the institutional space. Great. So we understand we have ECDSA we're kind of stuck with it. We understand we have MPC solves a lot of problems. Now let's talk about the combination. So how do we measure an MPC

protocol is good. Okay. So obviously like the first level is like the security of it. I'm not going to go into the security footprint of MPC protocols. I want to talk about efficiency and architecture. So if we're talking about communication, we have two parameters that we look at. Number one is the number of rounds. How many times MPC is a communicative interactive protocol. How many times do we need to go back and forth in messaging to basically sign a message. So that's number one. Number two is how much each exchange like that how much data does it need to transfer.

Okay, those are things you will usually see protocols uh disclose when they uh publish themselves. So that's number one that's on the communication. The second part is more on the scalability of the protocol itself. How much compute do I need? How much memory do I need? And eventually and this is a new one. Can I scale to multiple servers? And this is part of what this basically this lecture is going to be talking about. Okay, so MPC for ECDSA is hard. I mentioned earlier it's much easier to do it for shnore because the the basically the shnore signature itself is more NPC friendly. So the first versions of Schnore had three rounds. Uh the first versions of MPC on ECDSA had eight, nine

rounds. Okay, that's a lot of back and forth communication. uh a lot of them were more like trying to be like the fast version, the efficient version. But eventually I think a lot of people as an ecosystem thought that MPC is slow. Okay. Uh because lots of round many seconds to sign a lot of overhead. The good thing is that it's getting much much better. Okay. So a lot of brilliant people have been working on MPC protocols in the last few years and they've been shaving rounds away, shaving uh computations away uh basically step by step uh uh protocol by protocol and so you can see here some of the protocols from the last few years.

You can see sometimes it's like two, three rounds. Four is like the most. Uh you can see some of them have like very low computation but then a lot of times they'll have very high communication as a result of that. And some have low communication but they might have high computation. Um, and so this is kind of getting much better, but actually with the latest protocol we published, uh, we got to this result, which is we think it's pretty meaningful and groundbreaking, but not just because of how it measures. I'll talk about how it meets architecture because I think that's going to be very interesting.

Okay, so we finally got to the architecture part. Um, how do we see uh signing? Okay, like very highlevel generic, right? We have a wallet. They need you to sign something. They send you a message. Please sign this. Then there's a protocol. Now, how long this protocol takes depends on what protocol you use. But eventually, now you need to create a signature in an interactive way between the two parties or multiple parties. And eventually you produce a signature, put it on the blockchain, right? High level architecture makes a lot of sense. Now let's choose NPC categories for this, right? So like obviously we can do general purpose MPC because general purpose is general purpose. It can do

anything. But TSS is more efficient for digital signatures. Doesn't make sense to use general purpose NPC for a digital signature. We'll use TSS because it's more efficient. Great. One choice made. Second choice NPC or TPC. So you can do MPC, right? If you want more parties. But you look at the architecture we have here. In this specific architecture, we only have two parties. So, we can do two PC. Now, I will say a bit of a cheat. TwoPPC protocols can have one virtual party that does another MPC within. Not going to go into this. We published a paper on it some time ago. Uh, but like you can get more parties involved if it's important for your security architecture, but generally speaking, TPC is good enough for this use case.

We're going to stick to 2PC. Uh, the last part is malicious security because there is no majority in a two out of two. Okay? So like the honest majority not useful here. Uh so we're we're obviously going to go to for it to for uh malicious security also because as I mentioned we want to protect the parties. We want to protect uh the client party from if they're hacked we want to make sure that basically like you know like oh you understand. I think I think I covered it. Okay great. So this is the general architecture. Let's talk about the two things we mentioned communication and scalability. We're going to start with communication.

Rounds are expensive. Okay, now I know in the table above all of the numbers kind of look the same. You have four here, seven here. What does it matter? But rounds are very very expensive. So a round and this is from a DKLS paper, not our paper, a DKLS paper from a few years ago. They measured rounds between uh data centers in Google servers, right? So this is not even client. This is not a guy in the desert that's connecting. This is like a server of Google to a server of Google can take you 300 milliseconds in communication if they're uh a bit far away. So now think about the fact this is what rounds mean for us maybe 60 milliseconds maybe 300 milliseconds that's a lot of time. So

rounds are really important. Uh now rounds are also complicated. When we think about rounds usually in architecture we're like okay if I send you a message it's a round. If you send me a message that's a round or we might think about the combination. So the thing is in cryptography there's two definition of around. So around is either I send you a message or it's we send the message back and forth at the same time as long as they're not correlated. Uh now which is very non-intuitive right so when you think about rounds if you say hey I have a two round protocol I might say oh so you send two messages. Well no we actually send four. Uh okay so like that's a bit confusing but remember it round are like they're complex uh there's like

non-intuitive things here so again rounds are important now let's go back to architecture in architecture like in computer science there is no such thing two things happening at the same time uncorrelated like there's like some flow right we need to think architecture so like when we think about the architecture our architecture here we're trying I'm going to try to correlate it. Okay, I'm going to try to correlate it to the architecture we know from the internet. Right? When you think about how Dupasis work, when you think about how web hooks work, when you think about how push notifications in mobile devices work, it's always the same way. Server sends to the client a message, hey, I have something for you to do. The client

does something, right? Maybe it's a manual process by a person. Maybe it's an automated process. Returns a message to the server. Hey, I've done the thing. Here's the things I've done. And then the servers continues like whatever possibly with some outcome. So the architecture we're thinking about internet architecture as long as we can keep this architecture, right? And the important thing to keep the internet architecture is you see the green arrow. We need our MPC protocol to basically be completed in one go, one message. Um, but there is no MPC protocol that completes in one message. So that's a problem. But if we use a protocol that has two rounds and they're both unidirectional rounds,

so they're the nicer kind of round if you remember only one message, we can actually pinpoint it into this architecture, right? Because we have the first notification message. So maybe we can put one of the rounds on that message from the server to the client. And then we have the return message. We can put the second round on that message. Now we have a full MPC protocol running within internet architecture. That's a very interesting thing that we can use in different ways. But we need to make sure our MPC protocol is optimal round complexity means two unidirectional round. Uh um yeah if we don't then suddenly we need to add more

rounds. Um and also we said like rounds are important for speed. Okay. So out of the list of protocols we defined earlier, there's a few protocols that do have this optimal round complexity we talked about. Uh uh so I marked them here. So that's great because those are protocols we might be able to use in our architecture. But I'm going to make it a bit harder because the first round I said we might be piggybacking on a notification and notifications architecturally might have limitations. So for example, if you send the push notification to the mobile device, you don't have unlimited uh uh message sizes, you're limited to four up to five kilobytes of a message depending

on the vendor. I don't remember iOS versus Android, but they have like four to five message uh size limitation. If you're using a QR code and there's a lot of use, not a lot, but there's some using QR codes, especially when you want to transfer information to a colder device, uh then you're limited to 3 kilobytes of a QR code. Now again, that's a limitation. You it's an architectural limitation. Uh so if you have a protocol that needs like a 100 kilobyte of a message and you're trying to push it on a QR code, you need to show like uh like uh I don't know like 20 30 QR codes back and forth. That's a problem, right? Um so we actually optimally want less than 3 kilobyte per message. Uh and that's what we achieve in our protocol. So this is why we

believe our protocol is groundbreaking in the ability to do architecture oriented things that we wanted on our path to internet scale MPC. Now just to summarize this we measure protocols we usually measure them cryptographically we measure them as a paper when when those papers meet reality they meet the architectural limitations of the architecture that we run on. In some situations, it means that if you have too many rounds, you're outside of the protocol and the architecture. If you have too big messages, you're outside of the protocol and the architecture. We have to start adding more rounds to get data. So, those are definitely things we don't

want when we talk about internet scale. Great. So, let's talk about scalability. MPC has been historically trying to be as efficient as possible on the machine, right? Like uh basically least amount of memory, least amount of compute, uh least amount of communication, but it all looks at things from the single machine uh perspective. That's not enough. If we want internet scale, uh we need multiple machines. We need infinite machine scale. And so this is again I want to remind this is how internet scalability works. How does internet

scalability works in a very simple way. I have many servers as a provider. One of the servers sends a message to the client. The client does their thing. They go back to any other server. Okay, not the same server, any other server. This is how we do internet scalability. Um and we want this in MPC. And so this is a place where I want to introduce statelessness. Okay. So again, if you've ever scaled internet systems, you know you want stateless services, right? Because you can scale stateless services. It's hard to scale stateful services. In the context of MPC, we need to define what does stateless mean because we have a key. Obviously, you

need the key. So the way we define stateless is that if it's a result of the key generation, it's storage. It's not state. If it's the result of the signing process, it is state. And what we want is an MPC protocol that does not have state that has a stateless signing process. We can storage, we can handle storage. There's a lot of mechanisms to scale storage, but state during the MPC process is actually hard. Now, I'll skip through this. Okay. So, can we do stateless MPC easily? Uh, there's two ways to easily try and do stateless MPC. Number one, we just add more servers. Okay? And we tell them, hey, there's this share database. Make

sure you check state on this database. Number two, we say, you know what, instead of having a database, I'll just encrypt my information when I send it to you. And when you go back to me, I'll decrypt it so I know I have the same state. So now I can use the client for the state transition. So those are two great solution except they're all vulnerable uh to attacks and specifically non- street use attack. And the way you kind of attack this is that we kind of want you to go through this door, but you don't actually want to go through the door we created. This is, by the way, the result of my dog this morning. Um, okay. So, what do what would a malicious party do? I would start the round, send you the notification. If you're a malicious

party, what you might want to do is try to get me to sign two messages on different randomness on two different servers. And by doing that if you can somehow do that you can extract the key by maliciously crafting your uh random randomness in the protocol. Now that means that in order to protect from this my servers need to be in complete synchronization and complete synchronization is not scalable. So that is that is the native solutions just don't work. what does work stateless MPC if the MPC by definition is stateless or a different way if it's deterministic then we can actually scale an MPC

protocol now there's a few protocols that we can do this on top of and we do this by combining two things the first thing is we have the kind of protocol we talked about two party two unidirectional uh rounds and so like the MPC protocols that fall within that template three that I'm familiar with. There's the uh BAM protocol which we developed. There's the BHLS protocol by Lindel uh and a few co-authors and there's the Frost protocols for ED ECDS for EDDDSA. So all of those protocols have that round complexity that we're looking for. Obviously they have different things in terms of messages uh size. Uh the second thing we need is deterministic uh generation of

randomness and that can actually be done by a new concept introduced recently called EVRFs. Um again there's an EVRF in the BHLS paper. They introduced it. We have a new EVRF that we'll be publishing soon. Um the EVRF what it does is actually make sure that the randomness created on the client side cannot be whatever they want. They have to follow a specific process in the randomness creation that is still random but does not allow them to give to give different randomness to different servers which means that that that attack vector is mitigated. Now we can actually put the MPC on many servers and we don't actually care which server you go to because you're going to get the

same result regardless of which server you went to. So this actually solves a security problem that prevented doing the scalable solution. Uh and we think this actually allows you to scale this to uh internet scale because what you can do now you can do horizontal scalability. If you have more clients just add more servers. That has not been the case in MPC protocols. You could not just add servers. Now you can just add more servers for scalability, for high availability or for disaster recovery. Um, and those are the components that allow you for internet scale MPC. And obviously there's a lot of different places where this can be used. We believe that MPC is going everywhere,

every single device. It will take a bit of time, but we'll have MPC running across the internet for a lot of use cases, not just for blockchain signing, but obviously also for blockchain signing. Thank you very much. which obviously a lot of co-authors, a lot of people involved in this research and a lot of people doing the previous reaches were built upon. Uh uh so thank you very much