Efficiently Signing Encrypted Transactions with FHE

Transcript

[Music] All right, everyone. Thank you for joining. My name is Jonathan. I'm with Flashbots and today we're talking about how to efficiently sign encrypted transactions in FHE. Uh, so let me give you a bit of context first as to why would we even want to do that. Um, you might be aware that we are working on something called MEV. uh which is this stands for maximal extractable value. Uh it's known to be a problem on public blockchains. Um I'm not going to you know give you like a full rundown on me.

We don't have time for that. Uh and I've got many talented colleagues who are here speaking today which I encourage you to attend their talk or look up online afterwards if you want to to learn everything you have to learn about me. The only thing we'll have to agree about is that MV is a problem we can tackle. uh and if we want to tackle it properly and not to fall in this me trilemma that we've got here uh we have got to inject privacy preserving methods uh in it to make it uh to make it better and of all preserv preserving methods uh we'll particularly focus on FHE uh so just like a one slide uh shortcut about what is FHE for those who don't know yet so it's just this idea that instead of

like encrypting something and not being able to do anything with the cipher text uh you retain the possibility to compute uh over what you've encrypted, right? So, it means I encrypt something, I give it to you. I don't trust you. You can still do computation on it, give you back the result, for example. So, it's great. Uh it sounds magic. There's a few things to keep in mind is that um there's a huge overhead when you're doing that, of course. So, it's not free. Uh you add noise. Uh you have to manage this noise. So, it's like tends to be expensive. So most of the time you want to be careful uh what you do with it and especially like how you're doing it. So it's not as trivial as like I take an algorithm and I just like throw it into the FHE circuit. And we say

circuit by the way for if you hear me say circuit or program for FHE same thing. Um and the idea is like we want to use this tool uh as like a first layer to maybe build a a a mini encrypted mele in a way. So we you know most of the issues we've seen with MV stem from the fact that all transactions are visible in the traditional old school meool. What if we encrypt them but we want to retain the ability to compute over them. Okay, so we did that actually uh in a paper from this year's FC conference if you want to look it up and to summarize it in like one slide um we want to enable the ability for a searcher so these actors that extract

the MV uh on the network to back a user transaction and what we mean by backrunning it means that I'm able to in a way react based on like what I see in a user transaction and create my own transaction that I want to be executed right after the user transaction which is why we call it backending. Uh that's because of how um the the the blockchain works is that you have perfect certainty and like the state between these two these two transactions because there's nothing changes between between the exection of two transactions. So if you are trying to do something based on external events like the price on a centralized exchange, you know that at least whatever happens on chain is not going to change between the user transaction and yours. Hence you want to

back run and the settings we had uh was relatively simple. Uh so we assumed like a user transaction user encrypts the transaction send to the searcher in one way or another encrypted meool direct RPC whatever you want. Um, and the searcher can run uh an FHE circuit that basically encodes what we call like a searching strategy that computes uh over the users transaction, tries to see how it's going to impact the price on a unis swap pool, for example, and generate its own backing transaction based on that to capture an arbitrage opportunity. Right?

So the searcher has an encrypted resulting transaction, right? That's that's the result of our FA program and it sends it to a builder and in our setting the builder is trusted. The builder can decrypt and has the job to basically package all that and put in the block to land on chain. That's great. Uh or is it? What's missing here? Huh? Well, um we've not talked about signing, right? So, the FHE searcher is generating a transaction which is basically like a raw transaction in a way, but it's not signed. Uh, so it's not going to land on chain, right? Um, so okay, the obvious thing you'd tell me would be why is it hard to sign in FHE?

Uh, well, if you know your Ethereum, uh, you know that we're using a combination of like Kak hashes and ECDSA to sign transactions. Uh, and these two things happen to be pretty cumbersome to handle in FH. Uh, ECDSA uh, is an elliptic curve based uh, signature scheme. Tends to be expensive to run in FH. is like a an interesting like uh article on the on the Zama blog uh that estimates that it takes like one to two days on a 60 machine to crunch like an ECDSA. To be fair, that's the extreme setting like they try to do everything in the encrypted realm. They don't premputee anything. They do like all the heavy uh modular arithmetic of fields within the

FH circuit. So that's kind of like the low the the the very high end of like what you can expect. uh but before you can even sign that you need to hash your uh transaction right so you need to run ketchack uh within the f circuit and that's tricky as well uh there's also a paper at DCSFC uh that showed that you know even if they try to really push it to the limit uh they can basically uh bring down the runtime of a catch uh from 2 hours 30 to an hour and a half uh on the single core machine so you can make that faster but it's still going to be not super great Um, well, you could maybe just like try to sign the resulting cy text, right? The searcher generates his thing. It's just like this

blob of data. It doesn't know what's in there, but it just like signs it into the builder. Um, maybe, but uh remember that if we want to eventually have a valid transaction, once the once the builder decrypts it, that's still not signed. So it needs a new interaction between the searcher and the builder to finally get the searches transaction. Uh and that's potentially so it adds latency. We don't like that in ME. Uh so not good. Also like many many other things that could break. Uh pretty hard to do composibility with that. Uh and you require like further cryptography guarantees to to do that properly. Uh so we're not happy with that. Right. I hope that now we are aligned on like what the

issue is. Uh but before we dive into the approach uh we still need to go through like two methods uh that are going to be relevant to the rest of the presentation. One is uh a con obstruction right uh 4437 a con obstruction uh you might have seen that before. Um the idea is to introduce like many things uh by uh basically changing the way user accounts are handled from like externally owned accounts to uh smart contract based accounts. And you can do a few cool things. You can like dedicate payment. We don't care about that in the setting. Uh the interesting thing you can do in that thing is that you can change the way that transactions are validated. So you see like there's

like a validate user up like step seven on the on the diagram and that is custom. So you can do whatever you want to validate transaction. You're not bound to catch an ECDSA anymore. That's interesting. Um and all you have to do is to package your thing into this data structure called a user operation and then a new actor a new rule that we call the bundler is going to make sure to send that to your uh smart contract wallet somehow right okay so let's see what's in there so this user operation thing uh has has two stage that are uh relevant two stage that you need to implement two stage that you can customize to execute your transaction uh one uh is the validation which is the one we want to focus on on

this talk. So the idea with that this one is that um that's where you implement the logic of how do you make sure that this blob of data in the structure that we call the usual operation is valid and that the smart contract wallet can use it to generate a transaction on your behalf. That's what you want to do with the validation and and then the execution is uh basically executing the logic of the DAP uh based on based on the validated structure. Uh but if we want to zoom in on this validate user up function uh that's where we're going to have our custom logic right. So here that's where we can start encoding noncdsa signatures which is great if we want to get rid of

signatures in FHE. So it's like one building block uh we're pretty interested into right flexibility the bundler. So this new role doesn't have to be a separate actor to be fair. Uh but just like think about it as a new role that's uh that's off chain could be like a separate meool like aggregating user operations. uh the one thing we want to know about this uh actor or this role is that it needs plain text access to these user operations because it needs to then post them on chain, right? So that's that's really a critical part of uh of the solution. Uh it could be anyone uh because these these actors can be incentivized uh by getting a tip uh based on like what's in the the user

operation. Uh but maybe that's a natural fit for a blog builder to double up as like a bundler and we'll see why that could be interesting later. Um the one thing I want you to remember from that is that they do need plain text access to the user operation. So just like keep that in mind as like another stepping stone in our solution. New concept um we've seen a construction. A construction allows us to basically get flexibility on on what we use to sign and to hash. Uh so what do we want to hash with? Uh well let's see. Uh there is this concept called chameleon hashes. Uh if there's one thing that you might know about hashes is that one property we want is

collision resistance, right? So I inject like two different things in the hash. It should be super hard to get a collision um to get like the same digest from from the from the hash function. Well here we actually want collisions, right? We want but we want control collisions. So it means we want a way to for two separate messages different messages we want a way to on demand generate the same hash right and that doesn't come for free of course uh we want to do that by introducing uh what we call a trapdo so think about as like a private key so if I know a private key I can run like a different hash function that allows me to find the exact same result than I had before on a different message and hence I get uh a collision

Why is it useful in our case? Well, it means uh if I can do that I know the hash beforehand. So even before I know the actual message that I want to sign, I know the hash. So I can sign this hash even before knowing the message and I can sign it with whatever signature schema I want ECDA or whatever the way it looks. Uh so we've got this secret key uh just like a randomly chosen uh field element. Uh and that looks like a a a group generator. So like that's a discrete log assumption. We just generate a public key on that. This public key can go can be shared uh can go in a smart contract for example. And the only thing we do uh is that that's the operation at the bottom that we're using to calculate the hash. So as you

see it relies on like the message uh or public key and a piece of randomness that we've uh just generated on the fly, right? And using like some simple like arithmetic in the exponent, we can just get a new a new value here that is the hash. Interestingly, uh we've not seen the the the the magic in it yet. Uh what's uh relevant for that is that we want to be able to generate these collisions. How do we do that? Well, if we observe that, you know, we've got our first equation that we had before and now imagine the same equation. uh we want the same hash uh so this h value we want it for a different m prime and a different random value r prime if we observe that you

know they're both using the same generator we can just equate these things uh and and that's the equation we need to solve so at the end of the day uh we basically when we want to find a collision we just want to run this equation right so that's basically the step that we want to compute in f to generate a hash collision in in that case. So that's uh pretty cool because like using this trapdoor based approach uh we've basically reduced the complexity of uh hashing from multiple rounds of kack multiple rounds of beatwise operations of a large state to a handful of arithmetic operations. So it should be faster hopefully.

Um let's put this all together in the methods. Um, okay. So, remember our goal is to sign an encrypted transaction without relying on on very expensive uh FHE signing operations. And now we've got the building blocks to split the signing process into an offline and an online phase. So offline the signer can prepare the signature. Right? Now we know how to know the hash of a future message in a way. So we can do this notion of like delayed binding of a message to a hash. We don't even know the message yet. It's going to come from the FHE from the user actually. Uh but we can still premputee a hash and we can still pre-sign this hash even before starting the FHE bit and the FH bit just

like uh ends up being like calculating this collision that we've seen uh before. Um so just to make it clear what we do concretely is that offline the searcher in clear text so no FHE picks a random number uh computes uh the initial hash over a dummy uh piece of data doesn't matter signs it with whatever signing algorithm it wants and keeps it somewhere right privately then online when it receives the input from the user encrypted uh it does like all the me magic that it wants to extract and when it needs to sign then it just has to inject the pre-mpted values and calculate the collision as we've seen before. So that's that's what we need to

sign a transaction in FAT in a way. Now when we want to verify that onchain uh assume like our bundle has landed into into the different mele using the bundler uh well the validate user op function only has to recomputee the hash and we know it's kind of like trivial using the public key that we've stored maybe on the contract uh and verify the signature on this contract on this on this hash sorry. So that's the two operations. Uh we can even like think about it as like having different hashes. We can reuse uh the K check of of the envelope for the user operation.

If we want to skip uh to skip like more signature verification and save some gas, but that's just details. But basically that's the two steps you need to do. So to summarize that uh offline that doesn't look great, but that's all right. Uh there's like more flashy colors uh on my version, but uh that's like green, red, and blue. Um searcher picks a random number, pre-calculates a hash, signs it, and then when it comes online, just looks for the collision using the simple equation we've seen online. The user wallet checks the hash using the public key and then verifies the signature on this hash.

And the way our uh builder comes into play and I hinted before the fact that the builder uh was a good fit to be a bundler is that remember we still need to have plain tech success to the user operation data structure. So once the once the searcher circuit has generated the hash using the chameleon algorithm uh it sends this uh this bundle to our builder and we're happy with the builder to trust it because uh it runs in a T like most of the day most of the builders these days uh happen to run in TE so we can kind of like trust them and give them secrets that's like a an okay assumption um so the builder can decrypt uh whatever it receives and pack that into user operation that it sends uh to

users uh smart contract wallet. So basically we've closed the loop uh and we've solved our requirements. How does that look concretely? Uh well this is like still a very early prototype but I just wanted to give you an idea of like how um how it could look like. It's using insecure values. So don't uh don't assume that you know that's going to be the final uh numbers for this kind of approaches. Uh but basically the overhead uh in terms of like the smart contract wallet should be around 14 to 16k gas. uh it's basically dominated by like doing an EC recover uh to validate to to verify the signature and uh module exponentiations uh to calculate the chameleon hash. So it's not too bad. Um and on the FHE side uh for a relatively

unsafe and low modulus uh we can get to 1 million bootstrap operations which is what is really like the the juice of FHE and what is what where the overhead comes from and it runs in a couple of seconds uh on on the laptop. Uh so going to you know higher secure modular uh will have to go for larger servers of course but there's a good chance that it still uh remain manageable which is great. Uh one thing that's not too great right now is like we're currently mixing different security assumptions. Uh FH is like postquantum. We've injected like discrete log assumptions in there. Uh so it might be great to have like everything postquantum uh down the line.

Uh but that's also a good uh use as we've seen for u the synergy between TE's and FHE. Uh one thing that I really like to remind every time is that all of these privacy enhancing methods should not should not be thought of as like a a silver bullet. Most of the time you want a combination of them to operate together and that's like a very good example here. Uh if that's inspiring uh we happen to have many more of these problems online. That's new. Uh we've just shared our research problems database and you're more than welcome to check it and come to chat with us about it. We're going to be there all week.

Another info from our sponsor is that we are hiring uh and we are looking for uh different roles both in in product and research and we happen to have like our amazing recruiters at FCC this week. So you can come and speak to us. You can come to speak to our recruiters uh or you can just like look uh these information online if you want to. Thank you very much for bearing with me. Have you um looked under any distributed

key scenarios? So that'd be uh compatible with distributed keys. Uh, I guess the the where where it could come into play would be that instead of like having the Oh, okay. You don't have the size anymore, but like remember there was like a builder with the the secret key in there. Uh, that would be the obvious place where to inject distributed keys. Uh, you could still have them in TE's. Uh, but what you'd have is like you'd have a threshold decryption of like FH cipher text with the shares each maintained in like different different TE's for example. So it's totally complimentary. Yeah.

Thanks so much. [Music]