Proving you hold a private key in the post-quantum era is easier than it looks

Transcript

[music] >> Hello everyone. I'm Fabrizio and I will tell you about how to prove that you own the seed of that generates a private key you know, in preparation for post quantum you know, quantum computing attacks and stuff like that. So this is a very high-level overview of what is we are going to do and then my colleague Stefano is going to tell you you know, give you more details about this in the second part of the talk.

So this idea was originally let me actually go with you know, word of caution first. This talk will make heavy use of like Italian proverbs which are like small bite-size takeaway messages of the situation. Okay, so um Up until very recently we know that you know, many people underestimated the impact that quantum computers would have on this landscape. Um and basically you know, only I would say recently people are starting to you know, catch up on this and a lot of new solutions are being proposed. But as usual you

know, talk is quite cheap and you know, in this particular circumstance the point is that we have to evaluate the consequences of what we do on a very long-term time horizon which is always very very hard. So you know, it's very easy to propose reasonable solutions or stuff like that when you know that no nothing will happen for five or more years. Now you know, every day seems to be a lower estimate but So yeah, basically what we say in Italian in the situation is that when the sea is calm every can be a sailor.

Um okay, so recently the wind has changed. So we know that you know, days ago Google released documents pinpointing changing like the timeline roadmap Justin and uh Quaratom I think it's called the company published on the same day papers that you know, put the bounds the upper bounds on timelines way lower than we expected before and many people were taken by surprise by this.

So my personal opinion, I may be wrong here but it seems that when it comes to being quantum prepared Ethereum is leading the pack thanks to Antonio that is here for being part of one of the the guys that believed that this was a problem way before everyone else did in Ethereum. So At the moment I mean their Q day date is around 2029 2030 or early 30s and they seem to be on track with it. There were a couple of Ethereum events recently before you know, the official start of the conference that were completely like stormed by talks about post quantum secure updates. So that's a very good

thing to to know. And but there is still an absolute probability that Q day could come sooner. Basically we know that at the moment the uh quantum business is heavily VC dependent and so many companies have a lot of incentives to boast about every little thing they come up with and that's why we have a constant inflow of papers but notoriously there are some other companies like Sci Quantum that publish very very very little and they got two billion dollars in funding. If you think about it game theoretically there's a possibility that you know, they maybe have a real breakthrough and are not openly talking about it because why do

you want to give away your secret sauce when you can just show a working scalable quantum computing device exposed. So you know, that's also something to take into account and that's why I am confident that the timelines will shrink even more and probably you know, it is good if we have a solution that we can deploy really fast. So we want full barrel a drunk wife. Basically that's how you say it in Italian. We want everything and we want it now. Okay so in 2023 Vitalik proposed an idea to take your you know, seed phrase that generates your public and private keys and use

that wrapped into a zero knowledge setup to basically prove that you own it. And the idea why this works is that in going from seed phrase to private keys there's a lot of hashing involved and hashing is quantum resistant. So we can use this step to basically lift the security of the mechanism back to the seed phrase and we have this mode. Um this doesn't work for all wallets by the way, only for the ones that were generated using a seed phrase which today is the overwhelming majority of the wallets in existence in all blockchains.

You know, some very high profile exceptions are probably the original Satoshi wallets and stuff like that but for you know, average Joe this proof of seed works and what that could allow you to do is that in the event of a Q day you you know, if the chain is prepared and has an in place upgrade then immediately you just download on your ledger or whatever an other Ethereum app which is like safe Ethereum that allows you to sign things using proof of seed.

So yeah, that is basically the the idea. The proposal was very good but lacking of a lot of details. We have a this saying in Italian which is not exactly polite so I'm probably not going to repeat it out loud out loud but yes, that is that is basically yes, that is basically how it works. Okay, sorry. Uh Um okay, so now how does this work? Like first and foremost the ZK stuff is a jungle basically. There's a lot of stuff going on. You know, people doing polynomials, people doing hash based zero knowledge. So the first thing that we needed to assess is what is the right thing that we want to

use? And basically we need a post quantum resistance zero knowledge setup and so the first thing that we exclude are sorry, I wrote STARKs is SNARKs but as SNARKs are usually elliptic curve based and so not exactly good for us. Now we also have our requirements that the proof generation of the proof of seed should be able to run on a ledger device. These devices are really memory bound. They're like they really have very very very little resources and for this reason a lot of like these SNARK STARK zero knowledge suits do not really work well. For instance, if you

look at STARKs so Fry, Weir, Ligero etc. They basically do not fit in this constrained environment especially because the memory of the environment is really really restricted. So we say it in Italian that it doesn't matter how much chocolate you add a third one turn into an eclair and that's pretty much what happens here. Basically it doesn't matter how you optimize these methods. A lot of them just sits on different orders of magnitude of resources and there's nothing we can do about it.

Okay, so after an extensive review we found that the mechanism that can sustain these very constrained memory requirements that is ZK-Boo which was proposed a very very very back in the day like before zero knowledge was really probably picking up in crypto at all. And the point is that these ZK-Boo thing works like a sort of like pasta machine. Basically you use a technique called MPC in the edge. You produce three threads in your computation and the only thing that matters is a slice of these two threads that is constantly updated. So basically that's why it fits in very little memory.

But the proof that ZK-Boo produces are very very very very big. So the kind of like you know, eye level solution here would be to wrap the ZK proof into another succinct ZK proof so that you generate the proof using ZK-Boo and then you use another zero knowledge system to compress it. And the way this works is that the compression step can run outside of the secure enclave because basically to produce that you need a proof that can only be achieved on the secure enclave and so by doing that there are no you know, security problems. Basically the second stage is only used for compression.

And yes, this seems all nice but as we say like fry the fish but look for the cat. So there may be a lot of other things that you know, go wrong and we need to you know, be mindful about. Okay so what is that we still have to think about? Well, now we have a way to prove that if we own the seed phrase we can you know, prove it in zero knowledge but we still need to make this usable in an everyday context. And basically the way this works is by using a counter abstraction. This has been something very much used and discussed in you know in the

environment. And so yeah, that is basically what we are going to do. And so yeah, this again fits perfectly with the Ethereum roadmap and it's actionable today and allows people to yeah, perform transactions even if you they didn't migrate to post quantum signatures yet. So it can crew and straighten itself which is great. And yeah, some caveats I'll be very quick here. There are things that need to happen at execution level client to make this actionable. We already you know talking with people about that. In a Q day emergency we need to be against build a sort of like big red button to be able to perform an in place fork of the protocol. It's very little stuff but we need to do it to make sure that we

guarantee security without downtime. And by the way, this doesn't cover consensus is only covers users transactions which we still think it's very very useful because users will be most likely the latest to the party to migrate. So yeah, only that is no solution and that is basically the eye level proposal. THANK YOU. >> [applause] >> MY CLICKER. ALL RIGHT.

FANTASTIC. LET'S see if this is if this starts. Good. So I will skip the introductory part cuz Fabrizio did an excellent job at summarizing what we're doing. This is just a in two steps the proof proposal the proof of seed proposal consists of this proof lifting technique where you take something which is quantum weak and you exploit the fact that along the derivation of the quantum weak part the public key or the private key there is some step which is cryptographically hard to invert. For example a hash function that a quantum computer would not be able to break and you just lift your scheme by proving that you know something before that step that a quantum computer would not be

able to attack. So that's the basic idea and the second step of the proposal is that this needs to now be verified on chain in some way. So there are some constraints that Fabrizio already discussed where we have to take something which is not too big not succinct as you would technically say and you have to make it succinct. So there's this succinct lifting stage that that needs to come and we focused on BIP 32 and hardware wallets. And so for BIP 32 you don't really need to lift all the way to the seed even though the technique is called proof of seed.

Technically you just need to lift to the next step in the tree. So if you have an exposed child key and a non exposed parent private key you can lift to that. If you have an exposed master key you can lift to the master seed. If you have a compromised master seed you can lift to the seed phrase. So as long as you have something above with some cryptographic hash in the middle you can always recover. And this is a pretty powerful thing. Like technically if you compromise your master key which is usually the end of the line in this kind of setup you can even prove that you were the legitimate owner of that because only you know how that was generated. And so that's a pretty general technique you can do a lot of things with it.

There are some fairly tight constraints that we had to face. One of our interesting things was to adapt this to ledger wallets specifically and here the most important thing is that the memory available is in the order of a few dozen kilobytes which is definitely not enough for anything ZK modern. There are very few ZK techniques today that would fit there. In fact in practice we have about a 32 kilobyte stack limit and a 7.5 kilobyte heap limit so dynamic allocation which further restricts the sort of things that you can do in practice. So those are the two numbers at the bottom that we had to abide by. We have to fit in there which is very tight margins.

So the plan is to do in two steps. Step one we use ZK-Boo which is old but very nice ZK technique which is not succinct but does run within the memory constraints and the storage constraints. And then there's a second part of the of the project which is work in progress not in this talk which is going to be to take that proof which is not succinct but is ZK which is now out of the secure element and then wrap it into something which can be verified on chain. Now there's some interesting properties for this second step which which I think should be briefly discussed.

The proof is already ZK. It came out of a secure element. You don't need to worry about leaking any information anymore. So you can delegate the computation. You don't have a cluster of GPUs no problem. You send it to somebody who does. You can use techniques that are not ZK to make it succinct. There are some really nice techniques such as Binius that are still work work in progress when it comes to the ZK property. But nonetheless would produce much smaller proofs and are nice with bit operations and those could be used because the ZK property has already been provided. It's already in the initial proof. And so there's a lot more like you can heavily parallelize these.

You can stream these. There's this is pretty convenient but it's work in progress. It's something that we will do over the next few weeks. The Okay. Now very quickly meeting the constraints that we have on the secure element which was the real challenge of this particular part of the project. First things first compute. These are slow. It's a secure element. It's a 70 megahertz 32 bit architecture. You need to do things as efficiently as possible. And so one nice property of ZK-Boo the ZK-Boo implementation that we made is that you can use native implementation of all word sizes. All bitwise operations can be the one done by the CPU. All arithmetic operations can be the one done one done by the CPU.

And the overhead that you get for the proving side is actually minimal. It's a few additional operations like two ends, four XORs and unfortunately two pseudo random generations which involves some hashing that that is the slowest part. But nonetheless it's it's a limited it's a contained overhead. And if you use zero cost abstractions one response generation time so one fragment of the proof for a single trace can be generated in with a seven X overhead which is not terrible. Unfortunately the proof consists of 438 of these things. So that's ultimately still quite a big overhead but these are all independent. They can be generated potentially in parallel although not on secure elements. But nonetheless there

is there is some element of optimization there. The storage constraints again circuits are huge. If you write them as just literally explicit materialized circuits they have millions of gates. They don't fit in 1.5 megabytes. Of course you shouldn't do that. And so in reality we implement them as programs and we use some dynamic memory allocation techniques to just make sure that we use the minimum amount of state necessary. And if you do this with native word sizes this can be optimal. And so you can use literally the minimum amount of space that you could for that particular computation.

And in particular this helps you with the memory constraints which is the real challenge. It turns out that you can generate the entire proof with within three times the amount of memory that you would require to run the actual circuit which for something like SHA is is pretty small. And so you can do this by not storing the entire trace but just intermediate state using hasher states rather than keeping the whole thing and hashing it at the end. You just progressively update hasher state. You just keep things as close to one individual computation step as you possibly can. And that's the trick. Use a memory manager to dynamically allocate and ensure that you don't have like empty words. You just

rewrite overwrite anything that you don't need anymore. And we use Rust's ownership model to make this quite quick. So we don't even have to worry about that. We just know that Rust allocates and deallocates in a certain way and we exploit that to implement this. And the proofs themselves are ultimately streamable. You don't need to actually store them in memory. You can just push out little fragments one by one through the coms in parallel to the computation. So that's a independent part. As you produce it the proof gets streamed down to the machine that ultimately has to either assemble it or use it as part of the second succinct lifting step depending on how you want to do this.

And this overhead from sort of responses is completely negligible. It's a few dozen bytes or maybe 100 bytes. It's nothing. And the result is that well you can actually fit a lot of things in memory. In fact those are the basic building blocks of BIP 32 derivations. There's SHA, HMAC, additions, multiplications modulo 256 bit elliptic curves, then addition of points and public key production of points and these are progressively worse. In fact in terms of memory the worst one is HMAC. Like hashing. And it fits you can see it fits within the stack budget at the bottom 8 kilobytes out of 32 and the heap budget at the top it's about less than 2 kilobytes out of

seven available. So this works. These are pretty small numbers. The real problem are the numbers at the bottom which are the proof sizes. And if you have to do operations like elliptic curve then you have about a gigabyte of proof with the current implementation which is it's not that it's big cuz it will be made succinct. It's that it will take you something like 40 days to stream out of the secure element and that's the main issue here. So we do have work to be done cuz the pub key generation operation is absolutely brutal. But there's a nice conclusion to this which is that well not everything needs pub key operations. There's quite a lot of applications of this like hardened private keys, master private keys,

compromised seeds where you can do the proof without ever having to compute something on on a And so for those you can already do it without any further optimization. For other things, we'll have to optimize the code further and see how far how much mileage we can get from from our work. Uh but nonetheless, I think for any hash-based technique, this could also allow you to link old old private keys, which you can now burn cuz quantum computers exist and so they're not really private anymore, and go up the tree to the seed, down the tree to your new hash-based um signature system.

That proof doesn't in any way involve any of the big elephant stuff. And so, you can you can probably already do this today within within a ledger. Now, of course, this will require some more uh refinement. Uh thank you very much. We have um a lot of work to do, but it's very exciting, has a lot of applications, and we already have a lot of buy-in. So, thank you to everybody who came and and talked to me, and I'm happy to take questions later on cuz I think I ran out of time. Thank you. >> [applause]