ZK14 - Proof of Seed: ZK-Based Quantum Migration Without Address Changes - Mahdi Sedaghat

Transcript

Thank you so much for the introduction and good afternoon everyone. Um I hope that this the online version and not the PDF one because I have some animations that I'm using. I hope that it's going to work. Um so in this talk I'm going to cover uh the result that we uh had and presented a couple of months ago at Financial Crypto, uh which is a collaboration with folks at Mist and Labs. Um and the question that we want to answer in this uh presentation is that is it possible to use the ZK proof that you already got a lot of insight today uh with multiple amazing talks um to uh seamlessly migrate to post-quantum world uh if this is possible or not I'm going to answer.

Um you already have the context. This is the good news. I know that this is the end of the day and you already had a very intense day. Um it's not like a super new topic. There was multiple episodes at ZK Podcast that was discussing this uh topic before. And funny enough uh last night that I wanted to go to bed I just refreshed my my podcast like application that I have on my phone and episode 400 was exactly the topic that I wanted to present and it uh forced me to change two of my slides and also um remove one of those.

Fully recommended uh by the way. So um many people uh might ask that how quantum computer is going to show itself in the blockchain space. Um for those of the people who are not believing to this like uh uh breakthroughs or like advances that is happening, I'm not um like the right person to answer in timeline, but imagine that the first uh time that is going to uh uh the Satoshi coins are going to be touched, uh this is the situation that we should expect from from the market impact. And there is also another important uh aspect that we have to consider. There are a lot of dormant accounts that uh the users are going to lose the migration calls and it's very hard to expect the users to take an action for changing their their like a legacy

systems to the post quantum secure ones. And another problem for this space is that if you want to compare it with another like spaces in the in the internet that you are being affected similarly to to blockchain in the terms of like a quantum threats is um we would like to keep the addresses unchanged if that's possible. So, a quick reminder about how the blockchain works with the focus on Ethereum itself. Whenever a user joins to this network, they will get key pair which is a signing key and also public key and the address is being defined through a hashing the public key and some specific part of the the output.

And whenever you want to like a sign and make a transaction, you need to use the signing key and essentially sign the transaction details for the integrity purposes and this is going to be submitted to the mempool. So, the validators need to know your public key to check the validity of the signature and if everything is fine, then essentially they are going to agree on the validity of the block and the block is going to be created. I already highlighted in red, there are two parts that the signature is being used. The first one is in the execution layer that the user is trying to make a transaction and the second part is in the consensus part that the signature is being used.

Another thing that I want to highlight in this slide is that the public key is going to remain hidden and is going to be behind a hash function as long as you are not making a transaction. Okay? So, once you make a transaction, you need to reveal your public key and once your public key is is revealed, then there is a possibility for for a quantum computer who has a sufficient number of logical qubits to get your signing key. And let's draw a map that how does it look like? So, as I said before, the digital signatures for the execution layer that mostly are being ECDSA and EdDSA are going to be directly impacted by this threat.

And for the consensus part, which is the BLS being used in the proof-of-stake protocols, um, is is also directly being impacted. So, in the first threat, the the transactions are going to be forced by the quantum adversary, and the second case, which is less probable from from the other one because we have to expect that the quantum adversary is rational, they already solved a super super complex problem, and they are not going to like it do a rookie mistake whenever they are going to do that, uh, is is is going to be like a the proof-of-stake attack.

By the way, quantum computer is not going to do everything, uh, better than the classical computer except these two algorithms, the Shor algorithm and the Grover algorithm. And the rest of the things are going to be either partially impacted or they are going to be secure. The symmetric cryptography and also the hash functions are not going to be impacted. So, because of this, we are just going to focus on the execution layer, and as you know that Ethereum is also working, uh, great on like a bringing this like a replacing these BLS signatures with XMSS and also using the LinVM to aggregate the, uh hash-based uh uh, signatures. So, the naive approach for this would be like, let's switch to the post-quantum signatures. We have some candidates here that was

standardized by NIST, like Falcon, like SNICKS, and also so on. Uh, but the problem is that once you change your signing key, it means that the public key is going to be changed and the hash of the public key is going to be changed, okay? This is this is natural. And our goal is that how we can use the backward compatibility feature in the legacy systems to keep the address and also not move the assets because there is also a front-running attack for the quantum adversary that whenever you are asking for the migration, they can actually do it faster than you that you can refer to the, uh, Google paper, um, uh, for more details.

So, again, we we would like to preserve the the the addresses and also we would like to just, uh, take care of the exposed keys and they are like a dormant accounts and also protect, uh, this this type of accounts and also we would like to be like a key change uh, key generation agnostic, which means that it doesn't matter that which type of account and wallet you are using. Um, and another aspect is that, uh, most of the people would like to, uh, and prefer the hash based constructions. There is a cons, uh, for for this perspective that there is no algebraic property and we are just losing some of these properties that, uh, we we already had in the ECC based constructions.

So, the core idea is quite simple. Uh, we have some modern chains, uh, like Solana, um, Sui, um, and others that they are based on EdDSA signatures and we have also Bitcoin and Ethereum that they are based on ECDSA signatures. In the ECDSA, whenever you are creating an account, you are going to get, uh, a random signing key and the signing signing key is going to give you a public key essentially, which is exponentiation in the in the in the in the group. But in the EdDSA, the key derivation mechanism and the path is a slightly different. First of all, you pick your seed and your seed goes to a hash function, which is SHA-512. It's exactly the key derivation mechanism refer to RFC 8032.

Okay? So, it is they they are just following a standard. And the core question is that can we use this seed that is protected by the hash function because we know that the Grover algorithm is just giving us a quadratic speedup for for breaking the pre-image of the hash function. Can we use can we use this seed for post-quantum signing processes? And unfortunately, it's signing key because there is no like a path except like a BIP32 and BIP39 in the hardened and key path, uh, that I'm not going to describe in this in this talk. Um, the unfortunately, there is no chance. And once the So, adversary having access to your public key, they can get the signing key, and then essentially they can impersonate you and somehow like it drain the account. But, in this case we

have some advantages in the EDDSA base chains. The relation would look like this, that you have a message that the message in the in the in the first step can be like a transaction details that we already signed using ECDSA or EDDSA, and you have also public key, plus some some extra information that is for binding purposes to make sure that there is no mix and match attack. And what this relation proves is that they're proving the knowledge of the seed and also the key derivation mechanism that reaches to the same public key, okay? That the signature is going to be verified based.

What we expect from the proving system to prove this this relation is, first of all, it should be post-quantum secure for sure. I mean, post-quantum soundness is more important that uh here we have a very critical for us because the non-post-quantum one also provides us the post-quantum zero knowledge, by the way, because it's information-theoretical zero knowledge. Um and we would like to have also client-side proving. Client-side proving is very important, otherwise you cannot like outsource your seed, which is the full control of your assets, to a server. It should be also memory efficient because most of these wallets either are in the extension of the browser or they are in the mobile phones. It's not like a heavy like a machinery that we are expecting here.

The proof can be also one-time um because once you have the post-quantum signature being supported by the chain, you can only use this technique this migration technique for keeping your address the same, okay? For account or address consistency purposes. And instead of like a putting the transaction details as a message for binding purposes, now you can use the public key of your post-quantum signature, and then essentially the the network is going to check the validity of the signature and your transactions from that time onward based on that post-quantum public key. And this is going to be a one-time ZK proof because on-chain verification for these post-quantum signatures is expensive, and we shouldn't expect it to be happen per transaction if this is the the situation that we are dealing with.

By the way, very recently Coinbase also had a report and they already also discussed multiple strategies how the migration would look like and the second column is about this idea. That somehow like can meet most of the conditions that they are just uh discussing and describing there. Another important thing is that it is somehow like a signature of knowledge. We need more than knowledge soundness. And this is simulation extractability because we don't want to like do the malleability of the signatures because someone else can pick it and make it a different. And there's also common trick that put like session ID to the Fiat-Shamir and then essentially you can have this this

property somehow for free without like expanding and increasing the proof size. How the benchmarks looks like? There is an open-source code that you can follow here. And and and the circuit is is looks like this. The blue dash box in top is something that is happening outside the circuit and the red box is inside the circuit. As you know that most of these like a client-side proving systems are based on like a ZK-friendly curves. BN254 or like the other things. And unfortunately, the the relation that we want to show is in ED25519, which is a legacy curve and we don't

have enough roots of unity. Okay? We need to do some emulation here. What we did initially was we we somehow like used three limbs for for this, you know, you know better than me. Then essentially we could come up with these numbers in Ligero ZK-VM. And this is what is that open-source right now. And we could actually like it do it better Uh using beer base and lean VM. Uh like a Easter egg that I left in this slide is that you can also use some decomposition technique because you you don't you don't need to just do everything in the single circuit uh because it doesn't necessarily that a hash relation is going to be the same as like a checking the consistency of the public key. By the way, the public key

should be checked inside the circuit. There is no way. How does it look like? Okay, it seems that it doesn't play. That's the bad news. Okay, because this is a PDF version. I just left it as a like a urgent case, but it doesn't matter. I will I will post it on my home page afterwards. Um So, the the demo supposed to show to that how does it look like? I can just describe it how does it look like. So, essentially you have a wallet and the wallet is holding the seed. You can you can copy and paste it. And whenever you are making a transaction, you just press generate the proof and the proof is supposed to be the second condition for the validity of the signature and the transaction.

And it can be like a an upgrade in the chain itself. And as long as any if the quantum adversary is trying to drain your account, since it cannot provide the second condition, it's all the time rejected. But as you know, we don't have only the software wallets and the self-custody wallets. We have different type of wallets, HSM wallets, MPC wallets. In the in the HSM base case, we don't even have the API to get the signing key and we cannot expect to get the seed, okay? Because we need to generate the proof. And we cannot run the proof inside the HSM.

Do you want to do it? Talk to this like a HSM providers. Good luck. After 6 years, they can say to you a big no and this is not going to happen. And for MPC is also the case because none of these MPC providers are following these standardized techniques and everybody is like doing whatever that they want is like a for marketing purposes or for different purposes that they just want to showcase that my scheme is secure than the others and they are just doing different stuff. Okay? So, we don't have any clean path for or for this type of accounts. How ZK can come to the rescue for different type of accounts? Because as I said before, the previous idea only works for EDDSA, which is like a very small fraction of chains that they are supporting and BIP 39 and BIP 32 for

ECDSA. Uh but we have also different type of accounts that doesn't work at all. This is the problem. You already uh I think heard about the anonymous credentials uh multiple times today in different talks. Um and uh this is the immediate solution that we can actually assume. In the anonymous credential, someone is proving that they have access to a signature that is coming from an issuer. So, as I said before, as long as you're not making a transaction, then your public key is going to remain secure and you're not threatened by by the quantum adversary. Okay? Because you the quantum adversary only has the hash of the public key and from hash to public key is is not possible.

All the time prove that uh you you have the knowledge of a signature for this transaction and also show the consistency of the address with the public key that the signature is being verified inside the circuit. Okay? So, you don't reveal anything on chain and then essentially uh this is going to uh help us to do it on top of this other like a wallet types. Again, uh there's another demo that I cannot show you, but this is also more or less the same concept that uh you can you can connect to your MetaMask that essentially you make a transaction, but you wrap it before sending on chain and this is going to be a smart contract and some delegation technique that Ethereum does let you to do that.

And we are actively working and this is also another open source code that you can you can check it out. Um we are using long flow ZK um developed by Google and we are actively working with them to reduce the on chain cost. Okay. As a as a as a conclusion and a wrap up we already talked about like a EDDSA change that they have like a structure and deterministic deterministic like a key derivation path that let us to wrap the signature using a post quantum ZK proof. Uh but unfortunately it doesn't work for any cases.

And also for for MPC and HSM that we can actually use again ZK for this purpose by hiding your public key. We call it as a hidden public key like a concept that essentially can be used. Uh again I mean refer to episode 399 is the ZK dead? I don't think so if it is my personal opinion. There there are some new like a terms and applications that we can see here as you can see is like a post quantum migration. There are a lot of a lot of traction and like discussion that is happening. Anchorage also had another idea that whenever you have a post quantum signature you can use the secret key of your legacy system on the condition that the public key wasn't revealed at all for the key derivation mechanism to post

quantum signature. Okay? And then prove it inside the circuit. Again good luck because the key derivation mechanism for the post quantum signatures is extremely heavy to be done inside the circuit. And there is another idea that to put the time a stamp because we know that at the moment there is no quantum adversary then let's put some time a stamp for your legacy system and prove inside the the ZK and the circuit that you have something valid before the quantum adversary arrives. Okay? Before the Q day. Yeah this is the end of my talk and happy to answer question if you have a talk.

Yeah thank you. >> [applause] >> Yeah so we could maybe take one question or to be honest you can ask questions we'll just be going into the break so we can stay as long as you like. So we'll start with questions. Um I just wanted to describe how a similar concept works in Zcash. So, if you look at um, uh, ZIP 2005, um, so we already um, derive the keys um, for our circuit um, deterministically in most cases. Um, so we can use something that's kind of similar to the EDDSA approach. Um, there's one

exception which is um, uh, uh, threshold signatures using FROST. Um, but because those hadn't been widely deployed yet, um, we can specify the key generation for FROST um, taking this into account. And so, we can um, kind of provide an alternative that will work um, post-quantum. So, the idea is that um, uh, you might have to to leak one of the keys from your um, hardware wallet, um, uh, and also do a um, a uh, DL-based signature. There's another alternative which um, kind of uses a

smaller circuit um, uh, in the hardware wallet and that works similar to one of the ideas from the slides. So, basically we've come to similar um, approaches from different directions. Amazing. Wonderful. Um, okay. So, if you have any more points or questions to talk to Mary about, please find him in the break. Um, we're going to break for