So you wanna Post Quantum Ethereum

Transcript

Does it work? Yeah. Yes sir. Okay. Hi everyone. Um I'm Antonio. I'm cryptograph cryptographer working at the Atrium Foundation and today we're going to talk about um postquantum uh transaction signatures and yeah um one little notation I use at u on all my talks. It's like about afternoon so you lunch. So if you're tired, you can get an app, but when you see the red star, it's a good time to wake up. Um yeah, so if we think about Ethereum like we can divide in really for micro areas and uh yeah, we got like the execution layers where we are like all the clients like get red and so on. Uh you have consensus where you have all

the consensus clients. You have the data sampling with all the our beloved rollups L2 and yeah there is stateless that used to be vertical trees. Now um let's look a bit uh inside the engine of what is behind that and of course like um you have for execution we sign our the signature of it are sign use ACDSA signatures consensus we use a bit something more fancy that are pairings so BLS signatures for data sampling yet something more a bit more complex is KD commitments and for statist commitment and so with a with a vertical tree. Um what do they have in common?

All these solutions basically like there behind all these solution there are elliptic curves indeed for the ECDS signatures we use the SECP 256 K1 curve that is nothing else the same curves that Bitcoin use and for BLS signatures we use a pairing friendly curve in our case BLS 12381 and that is the same used u in the case commitment and the plan was to use for u for vertical tree used to to use bunders. Um yeah, so far so good, right?

Um that's this was like the status quo until a few months ago. Now without annoying too much with with the algebraic geometry, just like a quick uh a quick check on what is elliptic curves like if you plot elliptic curves over the real numbers, it looks more or less like this. And they have like a really simple load that was already noted by by the Greek. uh basically like you have like these two points on on the curve P and Q and if you draw a line uh over over this curve this line will hit the curve on the third point and this like defines a group law again I'm not going to know you with the with the fancy math uh on this talk but if there's one things you want to remember is that this

has um in in cryptography anything we do we we have like kind of trap door stuff that is easy in one direction or kind of hard in in the other direction In this case there is a simplified version of this these things this called discrete log problem and basically in a nutshell will be like if you have two to two points on this curve the the the DLP will be to to find a relationship uh between these two points. Now this is a really hard problem um that we don't have a proof like many things in public cryptography but we don't have a pro we don't have a way to solve this efficiently. Well, this is the case or was the case until 1994.

Uh in 1994, uh one one scientist Sh Peter Shaw found this algorithm to with initially was able to solve another problem. This like factorized factor number. So like composite number factorization but uh quickly after that people realized that this algorithm is actually good to break other problems. Uh so discrete log problem is one of these problem that is broken by by public by by shore algorithm. Now first things first not do not get scared. Um one reason to say that is like this u this old post of vitalic that uh tells you to what to do in case we have a quantum computer tomorrow. So

if you have a quantum computer tomorrow the best things to do is literally do nothing if you never done anything on that address. Why? Basically, how is an a address uh look like? Basically, it's like is the is the public key. So, it's the hash so ketchup is shri is the hash of a public key. And it turns out that yes, quantum computer are better breaking hash function, but not as good as short algorithm. So, we have still an quadratic advantage, but it's still good enough to resist to to ketchup. So, ketchup is still good enough to resist to quantum computer somehow. So if you have an address that you never touch, we are basically safe by the fact that your

public key is not exposed. So this this thing. So in case quantum computer happens tomorrow, move your funds to some address, don't touch your ETH, you're fine for a while. Um now with this said uh of course once the sh algorithm was discovered people mathematician cryptographer in the world I had to find a new way to have some mathematics resistant uh to this um to this uh shore algorithm. So there are basically like five different branches and one we already talked about is hashbased cryptography like ketchup is one one of this case.

Then you have latisbased cryptography that is again not talking about math today but in basically about finding short vectors on a latis. Um then you have one old really branch of uh cryptography mathematics is codebased cryptography. Then you have multi- varied cryptography and my favorite one that is super singular elliptic or visogen cryptography. But again we're not going to talk about this today. One things to uh really keep in mind is that things takes time. So um after this kind of area of mathematics has been established, people had to think how to deploy new cryptography to be deployed

to replace what secure now the web. So our all our HTTPS communication for example need to be postquin resistant. So already in 2016 there was an announcement by NIST that is an um an association in in the United States that announced the call for proposal for postquantum resistant u algorithm. So this in 2016 in 2017 the there was a proposal submission. So there were I think about 80 proposal submission that I think at least 20% were broken in the same night.

Um in 20189 uh there was the first round of evaluation that got a bit down and this continued with the second round of evaluation and few years ago ago there was a selection for the standardization. So as you said from the first announcement to the selection of the candidate it took well a while and the implementation started in 2017 right after the the proposal submission and it probably go until 2030 2035 until this proposal will go alive. I think the United States put a put a target of 2035 to remove any pre-quantum cryptography to be in their

in their uh software. Now who are the winner? The clear winner were latis. So both for signatures and king capsulation that is the competition about. So for encapsulation that we're not going to talk about it today it's cabber was the winner and this a latis solution for signature we got two uh latis uh algorithm the list and falcon and sphinx that is hashbased now um we at the foundation we start to think uh about postquantum solution a while ago we have a bit of work done in the years uh uh about solution that will replace part of our stack uh with

postquantum solution but later we we accelerate a bit and I'll show you why um in 2024 was a really peculiar year you may have read the news and there were big announcement by by Google by Microsoft let's let's see a bit some so in uh 2024 was this code uh this this this paper by Google on archive and um in uh There are a bunch of post of uh Scott Arnson. There's a major expert in quantum computing. We got actually the privilege to have him in the chat the foundation for a while for a couple of hours to to ask him question. And the message is switched from from the to the fact that you should okay take care in

the future about quantum computer to to start to have a plan and that's what we actually did start to have a plan. Um yeah just saying that this announcement of Google 24 is about willow that is basically the same paper of August 2024 but of course like people read more news than archive so it's the same things there was another announcement by by Microsoft uh even bigger than that I don't know if it still stands maybe someone will correct me but probably doesn't stand there not of Microsoft in any case um this is our let's say kind of new plan for Ethereum U for the execution layer uh well no it's not our plan this this is some ideas for the future for the ex

execution layer is um we experimented with falcon as an ethereum transaction signatures and this the main uh the main um target of this talk then you might have heard about beam chain that is this not this name is not going to stand because there's some trademark issue but probably you follow the Justin Drake talk at defcon in Bangalore talk for that availability something we have something called Freda and for stateless ethereum we don't have anymore vertical tree but the people are experimenting with binary tree plus post and hash function now um as I told you before we we focus on on one algorithm for postquantum transaction signature and after thinking

a bit uh falcon standed up like the best candidate because um has is one of the winner of the competition and has a really small signatures. So this is actually ideal but um how we want to use falcon in in introduce falcon as a ethereum transaction signatures. One way is to have a hard fork. Well, what does mean hard fork? Hard fork means having a a new EIP with a with a new uh transaction type. We already kind of tried to do this in the past for BLS. It's actually not so difficult. is will we will we will have already all the framework to do that we try to look for BLS signatures and it look really really easy and it's like if

we see the pros and cons of having and hard fork well again it's really easy to code and and and really fast I mean should we do it tomorrow we will not take a huge amount of time it's it's kind of easy the problem is like it's not future proof namely like what if Falcon is not anymore safe I mean we need to do yet another um a hard fork with yet another algorithm. Um that's why u we another approach is like to use a kind abstraction. Now I'm not going to talk about a abstraction otherwise we'll this talk will last two hours but um a way to um say what is a abstraction is making these smart contra

accounts as powerful as and flexible as um as the user accounts. So standard uh address and how this will actually could look like. So uh the first source of account abstraction was already presented by Vitalik and other people in I think it's Denver few years ago and it was this uh was not a EIP it was more like a series of smart contract and via this ERC 4337. Um but uh now with PCRA this was actually shipped uh a better way to to to introduce account abstraction in in the protocol and this EIP7702 and in the future we'll ship even uh account abstraction natively and this is going to be 7701

and what actually um pro of having account obstruction well it's really an eleg and flexible solution because basically if you know an abstraction you know that the way to insert new capabilities actually really flexible. So in in the future, Falcon turns out to be not anymore safe. Well, we just uh plug some any other signal scheme and we're still fine. We don't need to do any major hard fork. So this this is a really flexible solution. The problem that is costly in terms of gas consumption. We don't have any Falcon EIP now. So this means uh we need to have a solidity implementation of falcon and it's actually what we played with

just to give you some number. So uh this are updated number. So for falcon having falcon and solidity used to be 25 millions gas now thanks to zenox that will probably be the next talk they managed to to lower the gas to 3.6 million or even less. So it was a huge amount of optimization to bring the the the Falcon signature and solidity from 25 million to this kind of number. But again next talk we'll talk about this more. For strings is about 12 millions and yeah for multivariat mayo is like there's yet a talk after I think but it's going to be around 90 38 million.

So you'll see this number totally out of question at least the last one is no way you can having a signature cost so much. Um there is another way to actually proceed and it's probably this is gonna what we're going to do in the next um months. We're going to play with this an kind of hybrid way. This was already done in in the past for other issues in in Ethereum but it's basically like we're going to use um an abstraction but we don't use uh anymore a solid contract but we are using RIP. What is RIP? RIP is basically like EIP but for rollups. So you can start we can start play with rollups and

usually I don't know if any of you ever attend the calls for where the EIP is is decided is is a mess. All core devs is is really like complicated to to get the EIP accepted. So ARP is the process a bit more flexible. We got already at the moment we have only one deployed that is this pre-ompiled for this uh other curve. This by the way is becoming a potential in Fusaka. And basically what we try to do is having something similar having a can abstraction on L2 by air. So still we still have we still have a obstruction but we don't have anymore the we don't need to pay anymore the huge amount of gas uh on on solidity because we can use a pre-ompile on. So what's the advantage

here? It's again an elegant and flexible solution because you use a abstraction. There's only one disadvantage that um well it's temporary right? I mean it solves the problem but not for for L1 still an L2 solution. Now I just want to leave uh with the last sentence. Uh one of these um physes that were interviewed last year they talk about quantum computer and they say when quantum computer well they say I'd say 10 years plus or minus never. That's it.

[Applause] I know that it's basically off topic, but can you tell me a bit more about the Freda and BLS parts of the of the diagram? Sure. um for for BLS basically like um um the replacement is going to be part of all the beam chain um so we need the the hard part is like BLS is magic then like you have like in frequent word you have

like this this power of having signatures and aggregatable so if you have a BLS signature is about 96 bytes and if you aggregate 1 million signatures the the aggregation is still constant 96 bytes we don't have this look for postquin cryptography so we have been experimenting with two things we've been experimenting with uh hash signatures the one of this paper and with the falcon plus Labrador. So far the winner for us looks to be hashb signatures prove it the aggregation via we that is like a grandchild of fry. So stark we use stark to prove the aggregation of many signatures that are hashbased. We don't have anymore the

luxury of proving 1 millions validators. We the sets of validators will be probably big but the signal we try we we we prove is about 10,000 16,000 and but this that's it about that availability something with Freda we still didn't go too deep there to be fair I will lie that tell that anything is as much as crystaliz as for for BLS replacement but Freda is as a candidate beam chain and not hash plus starts because beam chain is not only this beam chain is a lot of things that the the replacement of BLS is not beam chain it's beam chain is many things that and this part is only one little part of

beam chain okay thanks um you mentioned these gas costs which look very scary uh do you have an idea um where the gas costs come from is just the solidity part of the implementation or is it actually that the algorithms are more comp complicated? No, no, it's solidity. I mean, if you don't have pre-ompile, right? I mean, actually, latis is it's really in general that is really fast. The problem like if you're acting purely on on solidity and you don't have the finite field for that I mean we're just going to implement everything in solidity and you need to

pay the gas, right? So, it's little the fact that you cannot leverage any pre-ompile. If you do this this with pre-ompile, maybe the pre-ompile will cost even less than the the CDSA because latis actually pretty powerful. It's really fast. Latis is about it sounds scary, but if you implement latis is all about matrix you implementing latis means doing vector matrix operation. It's just that solid is just expensive. Thanks. Why we don't pre-ompiles? Uh you've seen the pros and cons, right? There are there's the the pros is like yeah we add the pre-ompile tomorrow but then it's not good anymore.

We are we decide to take the the the slow way and adding account abstraction is flexible plus IP that is a pre-ompile for for rollups that's what we're going to start slow and maybe the will be promote to EIP as it happens for the other RIP. Wait for wait isn't it mathematically proven that this algorithm is enough for postquantum era. So what what is the possible case when you need to make new algorith? Yeah the problem like in public cryptography nothing is proven. So until three years ago one of the candidate was isogyny uh

that it was called psych that is part of sidh and basically it was supposed to be quantum resistant and eventually got broken on a laptop in five minutes. not only quantum computer. So in the public cryptography we don't really we don't have proof of security. We have just a hard problem. It can turns out that one of this hard problem gets broken for lot is probably not the case. It's safe enough but uh we just don't know right. Okay thank you very much. We are running out of time. So if you want to keep um asking question, please do it outside.

And thank you for the speaker.