poqeth: Efficient, post-quantum signature verification on Ethereum

Transcript

Yeah. All right. Uh, thanks for coming. So, today I want to talk about how to verify. Now, hopefully all of you are really motivated to learn about postquantum signatures on Ethereum. And this is a joint work uh with Ruseland, Peter and Nandor. And so, what's the TLDDR? Maybe you need to run or something. If you want to see our solidity libraries that we developed um you can access them at this link and also you can see the paper on errint uh if you want to read it it was accepted to Asia CCS. So if you are in Asia CCS at the end of August u we can meet and talk about this paper again in Vietnam Hanoi. So uh as you know Ethereum need to transition to postquantum crypto and

uh what we did in this work is that we benchmarked three hashbased signature schemes and one MQ signature scheme uh in solidity and we evaluated two verification modes. Um don't worry I will talk about it later and um yeah we release every everything that we do is we release it open source so you can have a look at it our solidity libraries and you can already use it on main at Ethereum if you want to verify and already transition yourself to postquantum signatures. Uh yeah so these are the TLDDR gas cost numbers. So we we looked into votes plus, XMss, swings plus these are the hashbased signature schemes and Mayo is the MQ signature schemes. These numbers

were already cited by Antonio. So these are the gas costs. Pretty high, but some of them are still better than uh Falcon. And these are the USD gas costs to verify a single signature on chain. And it's okay if you don't know what's an AC uh verification mode. I'm going into I'm I'm going to describe it soon. Um okay. So uh I just want to describe in the beginning some uh some preliminaries background on naysayer proofs our system model and then I will describe at a very high level these four postquantum secure signature schemes what's plus xs swings plus which is uh already standardized by n as you've already heard already today

mayo and I will close off with some uh hopefully I can inspire you with some open problems and uh future directions. Okay. So, uh you all know I just want to sacrifice one slide. Um I think it's just interesting to look at postquantum cryptography and quantum computers as an analogy to nuclear energy. So even in uh the 1930s there were high-profile scientists uh like this guy is is is a well-known physicist and chemist from he was the dean of Imperial College London and he was saying in 1939 that he thinks that there's a one in a million chance that u

people can build atomic bombs and then we know what happened six years later in Hiroshima and Nagasaki and if you ask Chad GPT Ched GPT and other experts experts will say that there's one to five% chances that we can build quantum computers that are capable of breaking cryptography. So I my point is that I wouldn't bet against technological advancements. So it's wise to be conservative and think about postquantum transitioning. Okay. So um let's jump into it. Um um as Antonio already said two talks ago, there's lots of prequantum cryptography in Ethereum today. transaction signing, KZG commitments in EIP 4844. Uh we have pre-

compiles to um compute pairings and group operations on the B and BLS curves. Uh yeah, Zerolabs, we have hash functions. So u generally there's many many cryptographic primitives that we need to reconsider once we have a uh quantum computer. And in this talk I just want to focus on transaction signing u. So this one and so how users can sign if there's a quantum computer that's capable of breaking discrete logorithm and and breaking ECDSA then how can we sign transactions?

Uh okay you how many of you heard uh account abstraction? Hence okay so everybody so the point is that on on chain there will be smart contracts that can verify user signatures. So basically if Ellis or Bob comes from the street they can define whatever signature scheme they want to use already on uh layer 1 Ethereum and this is this is nice and this is gives us a lot of modularity but it's also a little bit uh risky right because you can cook up some your digital signature scheme in your kitchen and if you want you can use it on chain um okay so EOAS will have EVM code and the point is that signatures will be verified on chain by smart contracts

So this is kind of good for us because uh we can build custom solidity libraries that enable us to verify postquantum secure signature schemes and this is exactly what we did in this work. Uh okay. So if you think about uh a digital signature scheme, it consists three algorithms and from a blockchain deployment perspective, the only interesting thing to us is the verification because key generation and signing happens offchain. So it doesn't cost us any money, right? And we only care about money. Just kidding. Uh so what we really care about in this work is verification. uh because that burns gas and that costs money to to our users and what's also interesting is that

signatures are not stored permanently in the storage. So typically it's in call data or blob data or something. So the point is that it's kind of entirely different design space as TLS because if you think about how there was a lot of discussion in the postquantum crypto community how we could transition to how we can transition TLS into postquantum secure TLS and in that case you you both care about the size of the signature and size of the public keys because the certificate chains contain both of them right uh but in Ethereum we don't really care about we are fine with largeish signatures. Uh we we only care about public keys because public keys must be

read from the permanent storage while uh signatures are in cold data or not in permanent storage. Uh okay. So uh so one one simple way is that the user sends the signature on chain and we verify it onchain entirely. That's what we call the onchain verification mode. Uh but there's another optimistic verification mode that we can do and we call it naysayer verification mode. This is just um toy example. So let's imagine that this postquantum signature verification scheme consists of verifying the correctness of this multiplication and uh you have food comma you are lazy you are a smart contract you don't want to do any computation because it's costly.

So you don't want to verify the correctness of this multiplication. So the left number is today like 2025 uh June 30 and the right date is um the birthday of John Fonoman. So who who says this multiplication is correct? Hands up. Who says it's incorrect? And and why why is it incorrect? Okay. Uh yes. Sorry. Yes. Exactly. So um right. So computing so it was there was a really great insight here computing this uh whole multiplication is toome and uh and uh boring and we don't want to do that but

there was a naysayer back in the audience who was who who could give us this constant succinct proof that this computation is incorrect and the same logic applies to postquantum secure signatures. Maybe verifying them would be really costly like but there might be some clever naysayers who says that hey look out watch out even though there's a signature on chain I can prove it to you very succinctly that the signature itself is incorrect uh and this is exactly what happened thanks uh naysayer uh so the user sends onchain for uh because we don't want to send the entire postquantum secure signature scheme we just sends a commitment to him commit

commit commitment to the signature and there's a data availability layer which can be call data, blob data, whatever. Um, and the entire signature scheme can be visible at this data availability layer. You can implement it how you want. And there's a nice party just like the gentleman at the back who can observe this uh reads this signature and acts if and only if there's some nasty thing going on. meaning that the signature is invalid and then can send a short nayer proof saying that hey watch out the signature is incorrect and what's the point the point is that if the signature is incorrect nobody

does anything we just accept the signature as it is and so that happens presumably 99% of the time but if the signature is incorrect then uh we just need to verify this short proof which is much smaller and faster to verify than the and then verifying the entire signature and I will show you some examples. Okay, so this is what we did in our work. We took four postquantum secure signature schemes and evaluated them both with full onchain verification and naysayer verification. Okay, so the first one is votes plus it's uh how many of you know lampport signatures?

Okay. So if you know Lampport, Wattsplus is just a generalization of uh Lampport. If you don't know Lampport, then bear with me. So Wattsplus is important because it's a cry building block of many other standardized signature schemes such as XMss and Swin Plus. Um and it's a hashbased one-time signature scheme. So that's the downside that for one public key we can only one sign once. If we would it's like basically sore encryption. If you encrypt a message with sword then you are cooked. The same stuff here. You can only encrypt with a given public key only once. Okay. So uh what's plus for very very simplified that's the gist of the

signature scheme. Let's say we want to sign three bit messages. Then we have eight public eight secret keys some random strings. The public key is the hash chain uh of these secret keys. So we apply seven times the hash function uh iteratively and if we want to sign a message the basically what we do with when we sign messages it depends on the message how we sign it. So um for instance for message one we just need need to hash uh the secret key one. If the message is zero then we just release the secret key and u now it's kind of intuitive how we can create a

verification algorithm for this. So the verification algorithm so for different messages we have different length of hash chains and the verification is basically you just need to finish the hash chain up to the public keys. That's the that's the verification. So basically if you didn't understand anything the point is that verification is just a bunch of hashes like brainlessly and it's okay because in solidity we have u we have pre-ompiles for various hash functions. Uh but if we have a message like the message is 0 1 2 up to seven then this would be this is the verification algorithm what it needs to do. uh but if I tell you that uh that a naysayer comes along just like the

gentleman did five minutes ago then the naysayer can point to the hash chain which is faulty right so if I want to be sure that the signature is correct then I need to compute every single hash chain but if the signature is incorrect and somebody helps me offchain then I can be I can much faster figure out like I just need to compute one hash chain let's say this one um okay so Um this this is onchain verification costs for watts plus. So um it's pretty fast. So one one signature for winter needs parameter 4 and 16 costs roughly 2,000 200,000 gas which is not great not

terrible but for winter's parameter 256 is even worse. So this is onchain verification and what you can see is that the xaxxis I don't know if you can see it the access is xaxis is the hamming weight of the message. So as the heming weight of the message increases uh we need to do less and less uh hash computation so also the gas cost decreases. Um okay and these are the numbers for if we compare onchain and naysayer verification and no surprise uh naysayer verification is much faster typically than redoing all the verifying the entire signature scheme. So how do we how the how does the naysayer prover look like? uh the signer just computes a

Merkel tree of the signature and onchain stores the merkel tree of the votes plus signature and whenever a naysayer comes along the naysayer needs to point needs to point to a part where the votes plus signature fails and what what what does the naysayer proof must contain? It must contain a Merkel authentication path and also the contract needs to check that the opened positions indeed encode a faulty hash chain operation. Um so that's what the naysayer prover and verifier uh do and these are the corresponding gas costs.

So no surprise uh the bottom line is that naysayer naysayer verification mode is faster on chain than verifying the entire signature. Um another signature scheme that we benchmarked is XMSSS. So these are already if you want to verify onchain XMSS or what's plus signatures um you can use our uh open source library. Um so what's XMSS is also standardized not by NIST but by IATF at RFC A391.

The downside of XMSSS is that the the number of possible messages that can be signed is upper bounded. Um so the in the idea is that uh the secret key is what's plus secret keys. The public keys are the public key of the scheme is that we compute the the what's plus public keys that those are going to be the leaves of the tree and the root hash of this tree is going to be the XMSS uh public key. So and now you can see why the me number of messages that can be signed is upper bounded. Uh so how how does signing work in case of XMSS?

uh the signature is a votes plus signature and a merkel authentication path that corresponds to that uh votes plus public key um and the verifier needs to check the votes plus signature and the merkell authentication path and the verifier needs to increase the counter oh I forgot to say that this xmss is a stateful signature scheme so both the prover and uh the signer and the verifier needs to have a state but it's fine in the blockchain setting because um count storing a counter on chain is fine. So um stateful signatures is actually a good fit for blockchain.

Okay. How to naysay an XMSS signature? Uh either there there might be two faults in a votes plus signature in an XMSS verification either the votes plus signature fails or the Merkel authentication path is faulty. So uh we we we we've already seen together how we can do the votes plus part but it's not clear how to name say Merkel authentication paths. How many of you have seen Merkel authentication paths or Merkel membership proofs? Okay. So everybody knows. So if if we want to prove that this value two was u in if uh oops no okay so if a value two is uh committed in this Merkel tree then uh we

need to release the the black nodes and um so the black black nodes are the Merkel path but to to be able to naysay a Merkel authentication path we also need the gray nodes the copath So essentially we need the full verification trace in order to be able to check for somebody uh to prove the incorrectness of this authentication path. So a naysayer proof for a Merkel authentication path is double the size as the regular authentication path. Okay. Uh so the naysayer proof is both the gray and the black nodes. And these are the numbers for XMSS. So uh what you can see is that the x-axis is again the heming weight of

the message and the uh the yaxis is the gas cost. I don't think you see it but basically kind of 4 million gas to verify a an xss signature and what's what's visible on this graph is that the mercury height of the tree doesn't really affect the verification gas cost. Okay, so these are the numbers. So these these are the onchain gas costs and h is the height of the tree. So if h is uh 20 then it means that we can sign two to the 20 so a million messages and it doesn't really affect so even if we can just sign two to the four messages 16

that's also 4.3 million guests but if we want to allow the signer to be able to sign a million message that's still less than five million gas and the naysayer for XMSS is a little bit more complicated because now there are three possible um faults. Um but the bottom line again is that the naysayer verification mode is much faster than verifying the entire signature on chain. Okay. Uh we also benchmark one more swings plus I need to speed up a bit which is standardized as Antonio said two years ago 2023. So uh it's a hashbased stateless signature scheme. Um there's a verifier we built a

verifier for that. So you can already verify NIST standardized signatures on Ethereum. And the last one that we uh benchmarked is Mayo which is not a hashbased signature but a multivariat system based signature scheme and now it's currently being standardized by NIST. It's in the competition so hopefully they are going to win. It's it's a nice signature scheme. Um and it has small signatures but largestish public keys. uh which is not that great. Uh and currently sadly this uh has pretty high gas costs as you will see.

Uh but if we would have SIMD which is kind of on on the road map, SIMD would also help for latisbased signatures. SIMD allows you to do um because Mayo and letes needs finite fields that are much larger much smaller than regular elliptic curve finite fields. So for instance, Mayo needs four bits or five bit large finite fields and SIMD would help uh which which is hopefully an upcoming upgrade would help us decreasing the verification gas cost also for Mayo. Okay, so these are the number that you've already seen. This is the TLDDR of this whole work. Um so are we happy? Not really because these are like who wants to pay uh transaction

fees like anytime you send a postquantum secure signature scheme like I don't know 10 bucks or 50 bucks nobody right so if you buy a slice of pizza or crossson then you definitely don't want to pay every single time uh 50 bucks so um yeah as Anthony already said onchain verifications is pretty costly maybe we would need uh pre-ompiles or some other way around. Okay. So again, here's the GitHub link, the paper link. Uh I think it would be nice if these libraries would be formally verified. So just to make sure that what we built is meaningful and doesn't contain bugs. It it would be even more amazing if people would use it. Maybe not on L1, but on some layer twos uh gas golfing these

contracts. So if you're really into gas golfing, let me know. uh we didn't really spend a tremendous amount of effort to gas golf it and optimize it but I think it's definitely possible um yeah would be nice to have some pre compiles also for hashbased standardized signatures not just falcon as other people are suggesting to do it okay and yeah there's there's many more open questions how Ethereum should transition to postquantum so I think this whole line of research and work has just started And yeah, feel free to reach out if you want to talk about uh anything related to postquantum or Ethereum in general. And yeah, there are many great E3 research posts. So I highly recommend

you to look at those. And thank you. Uh let me know if there's any question.