Preparing Blockchains for the Post-Quantum Era

Transcript

All right. Thank you all for coming. Uh today I'm going to talk about preparing blockchains for the post-quantum era. Um I think it's a talk that applies to pretty much any blockchain, but of course I'm going to be focused on uh the transition for the Tezos blockchain, though I would say that the lessons are broadly applicable. Uh my name is Arthur Breitman. I'm a co-founder of the Tezos protocol. Uh I'm also a director at Trilitech, uh which is a uh entity in the Tezos ecosystem that helps the promotion and growth of the Tezos network. So, uh the main message I'm going to give you my conclusion in the first slide, uh which is that quantum readiness is a process, not a switch. Um it's a process that takes time,

uh which is why you should start now. Um the urgency doesn't come from the fact that tomorrow we're going to wake up and uh uh elliptic curve signatures are going to be broken, but you need time for your users. Um so, yes, I would like to emphasize that I don't think there's an acute threat today, but the date at which uh there will be an acute threat comes closer and closer um every day. I'm sure you've seen the papers from uh from Google recently where they have the number of qubits necessary. Uh we're not there. I I also don't think we'll be there in 2029, but it's also not impossible that we'll be there in 2029, and so it's appropriate to take the

right measures. Why? Because being early has very few downsides, and being late can cause severe disruption. Um the other point I'm going to make is there is really not no reason not to do it. Um so, let's look a little bit at the quantum vulnerable components you have in Tezos. And if you are looking at crypto, sometimes it can be confusing what's vulnerable, what's not vulnerable. Uh and the short rule of thumb is if it uses a billion groups, which are as a commutative group, so anything that has to do with factorization, uh with elliptic curves, uh with DSA, all of that is going to be vulnerable. Uh and everything that

relies on hashes and other things which don't have this nice abelian group structure in general. I'm simplifying, but in general, um is going to be resistant. You might have to double your key size uh cuz you can get a square roots uh advantage on on on these algorithms, but by and large, you're fine. So, what do we have? Well, we have the account signatures, of course. Uh we use different keys uh in the Tezos network. TZ1s are based on ED25519. Uh that's, you know, all of these are elliptic curves. Uh and of course, they are vulnerable, including of also BLS, which use uh pairing signatures.

That is also a vulnerable. Uh then we have aggregated attestations. It's fairly new, uh but so now in Tezos uh protocol, when the bakers participate and they vote on a block as part of, you know, that's what they do in proof of stake, uh we aggregate, we can aggregate the signature into a single signature. This is really for efficiency and this uses uh BLS. We have the data availability layer uh KZG commitments. So, that uses um KZG proofs over BLS 12 uh 381, so that's also pairing cryptography, also vulnerable. Data availability layer is essentially what gives you data uh availability sampling or sharding. It lets you have a lot of data for your execution environment and rollups

without having to overload the um layer one. We use class group VDF uh for randomness. Uh so, there's different sources of randomness, we'll see, but the class group VDF also relies on a billion group structure. And then we have some smart contract primitives which are available for smart contract developers like an integration of the sapling protocol for privacy-preserving transactions. Uh we have direct access to graph 16, BLS, we have time lock primitives for people who want to bring contracts which are secure against MEV. So all of these primitives are dependent on some quantum vulnerable components.

And so what is to be done? Well, really they fall into two categories. Uh one is user keys and the other one is protocol cryptography. And for user keys, the technical difficulty is very low but the social difficulty is very high. For protocol cryptography, the technical difficulty is high but the social difficulty is very low. So what do I mean by either? Well, technical difficulty is you're going to need to write code, you're going to need to assess different algorithms, pick one, implement it, deploy it. That's the technical difficulty.

The social difficulty is actually getting adoption. And so for user keys, well, it turns out that they are post-quantum signature scheme available. There's many to choose from. They're fine. They're not as efficient as elliptic curve signatures but they're fine. And it's fairly straightforward to integrate them. It's not a big job. However, the social difficulty is very high because you have a lot of users who are, you know, very passive. They they hold some coins. They just want to keep holding their coins. They don't want to migrate to new keys. And these users are going to need some time to migrate.

They're going to need the time to actually go and attach new keys and to essentially stop being vulnerable to a compromise of elliptic curve keys. That can take years. There are people who take who take actions on a network every couple years. They don't pay attention. They don't want to pay attention. They shouldn't have to pay attention. But this is a really big one-off. You know, this is is from classical computers to quantum computers a little bit of user activity it can be required and should be expected here. So, this is why we need to act now because this takes a long time. Now, the protocol cryptography um that is technically much harder uh and and and we'll see like how we can mitigate uh them, but the social difficulty is fairly low, especially on

a blockchain like Tezos, which has on-chain governance. Uh the reason primarily is that the people who uh validate the network, operate nodes are pretty reactive, they know what's going on. Uh they're online, they pay attention to the network. So, if you contact them and you say, "Hey, it's time." Uh and if you have a protocol proposal to make your protocol quantum resistance, you can do this. Um you can do this in a matter of month from in terms of like not the implementation itself, but the, you know, going into production can happen in a matter of months.

Uh if you had to do it in a absolute emergency, you could probably do it in days, but the technical difficulty is very high. So, now, what are we going to do? So, now uh the path is to first introduce a scheme for post-quantum signatures for you users. And that you should start right now because this is a process that will never finish. This is a process that will take years. I do not know when quantum computers will be there, but I do know that when they are here, there will be some users who will say, "Oh, I forgot to migrate." Like they will exist. And you're not, you know, the the choice right now is not whether or not they will exist, it's just how small of a fraction they are going to be.

Uh and then in the near term, um you start working with uh wallet and tooling ecosystem to make sure that um they adapt. During this period, this is when you have your user migration. And in long term, um you start replacing the primitive of the protocols. You have a bit more time. It's more technically challenging, but you have more time to do it. You can think about it, you can think about the right approach. You can test it. You can implement it knowing that, you know, if and when you need to pull the switch, you can do it fairly quickly. And again, you know, I think quantum is coming much faster than it we thought it was going to come 2 years ago, but it's also not coming tomorrow.

So, user key migration. Uh here are some candidates we looked at uh for post-quantum uh signatures uh for account keys. So, all of these are uh basically uh lattice-based. Uh when NIST was standardizing uh signatures, I really loved uh the oil and vinegar uh signatures for their uh unbalanced oil and vinegar uh signatures for their characteristics. Unfortunately, they proved to be uh insecure, but lattice has been fairly well tested from since the '90s. Uh your options are ML DSA 44, which is uh the most standardized one, is Dilithium.

Um standardized as well, but a bit newer is Falcon 5 uh 512. And more experimental is Hawk uh 512. And uh the factors you look at when you pick the signatures are signature size and verification time and tooling compatibility. Not listed here uh are a category of signature which I think are very important and very useful, which are the hash-based signatures like the SPHINCS scheme. They are a very conservative choice. Um it's what I would recommend for a network like Bitcoin which wants to be extremely conservative in their choices and you know, it would be easy and uncontroversial because you won't have long debate about their security. Um but validation time for them is not very attractive.

So, you know, here's a table to look at. Practical constraints for account key. So, I listed on the left some schemes. So, Dilithium one, which is uh the uh Ed uh 25519 uh curve. Uh and you know, the other curve uh are similar in uh in speed. Uh ML DSA 44, Falcon 512, uh Hawk 512. And then we also have the hash-based signatures as I was mentioning, such as SSH-LDSA 128F, uh 128F and SSH-LDSA 128S. So um client-side is quite um it it is quite um a red herring uh because you care as a

blockchain uh about the verification time, not so much the signing time. And the reason is, well, people can sign on their own hardware. Everyone needs to validate the signature, so, you know, and needs to validate a lot of signatures, but as a user, you're only responsible for making your own signature. So, you should pay attention to how long it takes because some people will have lots of signatures to make, but by and large, you know, you're kind of like naturally distributed. So, um you will see that it's very very fast for uh elliptic curve. It's pretty much as fast for uh ML-DSA 44, uh a bit slower for uh Falcon, very fast for Hawk, and then like quite slow for the hash-based signatures, but again, it's client-side, so we don't care as much.

Uh public key size, it's a bit relevant because your public key is going to have to live on the blockchain, but it's can be long-lived, you know, you reveal it once, you push it you publish it on the chain once, and then it lives there. So, you should should pay attention to it. Like, you don't want a public key that's in the gigabytes, but it's not that important. Um and as we as we can see, they're uh fairly small uh anyway, you know, like the biggest one we have here is uh is only uh 1.3 kilobytes, uh which is ML-DSA. So, that's fine. Now, what's really important, um I would say, is signature size and verification time.

Signature size because you're going to be pushing a lot of these signatures on your network, and verification time because, well, your validators have to verify them. Now, when you look at the verification time, the like the elliptic curve and uh the lattice signatures, you'll see that the lattice signatures are actually more competitive than the elliptic curve. That's great news. We're not going to spend a lot of time verifying the signatures. It would be very slow uh if you use the hash-based signatures, unfortunately, and that can be a reason uh to discount them. Although, I will say that signature verification is the thing that validators can do in parallel as opposed to executing transactions.

So, if most of if most of your bottleneck is uh IO uh and just like sequentially executing contract, and you can off- offload the signature verification to parallel CPUs, uh then the the hash-based signatures can be a good choice. But, then you also have signature size. Uh there uh you'll see there's an advantage to using signatures like Falcon and Hawk. They get quite uh smaller than ML-DSA, but four times smaller. Still about 10 times bigger than uh elliptic curve signatures. Uh so, it's it it's it's a bit annoying, but I think you can um you can live with it. And then, of course, the hash-based signatures can be much uh larger. So, you know, in uh like 17 kilobyte in one case, eight kilobyte. And you have different trade-offs where you can make

them a bit smaller, but at the end of the day, they're still uh chunky. And finally, you have HSM support uh and that's just a very pragmatic uh aspect. You're going to have a lot of validators uh on on your on your network who are going to need to to to see the signatures, and it may help them to have support in HSM uh for making the signatures, validating signatures, doing all of that. And this is where adopting standards is good uh because if it's a NIST standard, uh hardware manufacturers will implement it. And if it's a standard that was uh concocted together on forums with a lot of like blockchains people, uh it might be better, but it might not be supported by hardware. And that was one of the reasons to go with ML-DSA over Falcon and Hawk, which have better

characteristic, which is that it's more likely to have initially uh HSM support uh compared to the other two. So, how does this work? Uh on Tezos, we are going to uh have a hybrid migration period. Uh in the uh current protocol uh proposal, we're just introducing behind a future future flag uh the ML-DSA 44 signature. Fairly easy. Um then the transition period is when on an account you can have both a um elliptic curve key and a post-quantum uh signature key. And bear in mind, you do not actually need to be doing post-quantum signatures right now.

All you need to do is to make sure that your users have one as a backup. So that you can have a ripcord, and if and when there's clear and present danger, you pull the ripcord, you deprecate all of the uh elliptic curve signatures on your network, and then your users are not stuck. Why? Because they have a post-quantum key. So, there's a cost. Those post-quantum signatures, you know, they have uh bulkier uh signature sizes, but you don't actually need to use them. You don't need to use them. You don't want to use them right now. You just want your users to be able to have them. So, that's a deprecation period where PQ becomes primary and EC is valid and still discouraged. And then in validation, you know, there's clear and proven threats, um an arbitrary threshold is whenever you see 64-bit EC uh being broken, I think you need to

pull the ripcord and not have any EC signatures on your chain. And then finally, you can have a rescue period. Uh and the rescue period is you say, "Well, okay, we blocked your account. If you can prove that your public key was derived from a seed phrase uh that you know, then we'll let you like unlock this." That can work as a signature. You can do this with a stock. That's more implementation. And also, I wouldn't do it from the get-go because if you do it from the get-go, people are going to say, "Oh, I'm fine. I'll just use the rescue mode." So, you know, explicitly, I think in the roadmap you want to have the rescue mode come in later so that there's a bit of a penalty for waiting to do uh for waiting to do things.

Stateful addresses as a migration enabler. Uh so, what we're doing is that instead of uh treating uh externally owned accounts, which we call the implicit keys uh on Tezos, as uh just a hash of a public key, we treat them as a stateful address, so you can add uh multiple keys on one account. That lets you do a lot of things. It lets you do key rotation without changing your identity. I know that in principle it would be great if we were all using domains as identity and then just changing the keys, but that's not how the ecosystem has evolved. People like keys and so, you know, I think we have to deal with the fact that keys are handles. And so, just just make them handles and attach different keys to them. Uh instead of making them public key hash.

Uh that provides for elegant migration and it also gives you a a nice pathway to effective account migration. I don't have much time left. I'm just going to go quickly over the protocol level cryptography. That's more to the specific, but if I have one lesson on the first part is that do it now. There's really no cost in letting your users attach these keys. Uh but it's not enough to tell, "Oh, well, the users have the possibility to do that. You see they can use this smart contract or that smart contract." You know, there's need to be uh there need to be a push because you're facing very passive users sometimes. They're not going to do anything on their own.

They're not going to protect themselves. And yes, it needs to come from, you know, at you know, the the ecosystem entities around the network needs to actually push this if they want to make it happen. So, uh hard problem number one, aggregated attestations after BLS. BLS is fantastic for aggregating uh block signatures. Uh today we do this. Uh how do we do it in the future? Uh there's two options. Uh with lattice signatures, there's some experimental aggregation of lattice signatures or you can just say, "Oh, whatever. I'll just do a big stark out of all of this." Starks have big signature sizes, but that's not a problem because you would just have a single one for all the signatures.

Competition cost is a bit of an issue. Uh but you know, what can you do? There's not that many options. So, you know, not having that many option in the in a way is not bad because it can guide you. You know, you don't have to agonize over your choice anyway. Hard problem number two, uh doing the data availability layer without uh KZG pairing. That one is a little bit better. Um you can use fry base commitments instead of those uh uh KZGs. You can do latest commitments. Uh you can try to use starks. I like the fry base commitment for this because it kind of like mimics pretty closely what you're doing with the with the polynomials in the first place.

So, this one a bit older than the aggregation. The aggregation is really the annoying one if we're if we're being honest because you're making a a big proof out of like many many statements. Randomness and VDS I'm going in decreasing order of difficulty. Um we're not that dependent on on the VDF for randomness on Tezos. There's also a Rendo, and the Rendo was working fine before it had a class group VDF, so that was more of like a cherry on top. And then as part of the protocol as well, we are diminishing the importance of randomness in the protocol. So, for example, if you have every validator participate in the consensus as opposed to as a random quorum, you don't need as much randomization. If you start replacing

if you start doing block select block leader selection in a deterministic fashion, you can also replace some of the randomness. So, maybe you just fall back to Rendo. Otherwise, before the nice uh construction of VDF that we've had with uh with groups, we had some VDF proposals with Starks. They're fairly easy to implement. They're a bit larger. The overhead factor is not as good as they are if you do like the Groth 16 construction, for example, but you know, they work. So, maybe we just go back to just doing a Rendo.

Maybe a Stark verifies sequential work. That's generally fine. Smart contract cryptographic primitives Um so, that one is a bit tougher as well. The Sapling circuit, so that's what basically provides Zcash-like functionality. If you wanted to shield your tez or any token on a Tezos network, you can use this contract right out of the box. Um that's a bit tricky because you can't really this is not a case of like oh, I'll have a prover and a prover will just compute the big Stark proof for everyone like you would have, for example, in a ZK roll up.

Um, here you need the user to actually submit a stark. So the user would have to submit a stark which is like 100 kilobyte or more if they're used as to it could be like 2 megabytes. And then you have to aggregate all that because you can't just put them all on the on on a chain uh if you want to have any type of throughput. And that poses the question of like who aggregates it? Does it create centralization? It can be hard to find an actor who's willing to be a centralized actor who's going to aggregate a bunch of proofs for anonymous transactions. Uh, there's some lattice-based alternatives but not that great. Time lock encryption we can do uh it's really the the private post-quantum signature uh thing which is sorry the the the private transaction

with post-quantum resistant cryptography is the one that's a bit uh more annoying out of the all the lot. So plausible uh post-quantum architecture here we go. Uh accounts migrate right now and then uh if Falcon matures go to Falcon and then we have these different uh uh replacements mostly based on starks uh for a lot of the protocol math. Thank you. >> [applause]