Episode 392 - lean Ethereum Part 2: PQ Signatures and Poseidon with Dmitry and Benedikt

Transcript

Welcome to Zero Knowledge. I'm your host, Anna Rose. In this podcast, we will be exploring the latest in zero knowledge research and the decentralized web, as well as new paradigms that promise to change the way we interact and transact online. This week we have our second episode in our six-part miniseries on lean Ethereum. For these special episodes, we have Nico as our host. We also are releasing these in video form over on our YouTube channel. Links are in the show notes in case you want to check it out. You can also see the video on our website. And if you choose to watch the

videos, be sure to subscribe to the YouTube channel while you're at it. For this week's episode, Nico chats with Benedict Fagner and Dimmitri Corvatovich, cryptographer researchers at the Ethereum Foundation. This is our second installment of the lean Ethereum miniseries. And here they dive deep into postquantum signatures, specifically lean sig, a hashbased multi- signature scheme designed to replace BLS in a quantum secure Ethereum consensus. They unpack the security trade-offs, encoding challenges, and the ongoing crypto analysis of Poseidon, the hash function at the heart of the design. Hope you will watch and listen along to this and other episodes in our miniseries. And yeah, let us know what you think. Please

note, this episode was recorded before the recent attacks on Poseidon by Mertz and Garcia and does not take it into account when discussing the latest state of cryptonalysis on Poseidon. Before we kick off, three quick points. First, ZK Summit is coming back with its 14th edition. Applications to attend and or speak are now open. It will be on May 7th in Rome. So, I hope to see you there. Second, ZK Mesh Plus. Our paid subscription tier is rolling. We have released a few bonus clips over there as well as some of our exclusive research reports. If you want to get access, please join the paid tier. Third, if you're looking for other ways to support

the show, we have donation accounts visible in the footer of our website. Support definitely goes a long way. So, if you do decide to donate, thank you in advance. That's all for now. Links are in the show notes. And here is Nico's interview with Benedict and Dmitri. Today, I'm here with Benedict Wagner and Dmitri Corvich, cryptography researchers at the Ethereum Foundation. This is episode two of our minieries on the lean Ethereum upgrade and this one is dedicated to postquantum signatures. Dimmitri, your return guest. Welcome back to the show.

>> Hi Nico, my pleasure to be here. >> Great to have you. And Benedict, I believe this is your first time on the show. >> Yes. >> Welcome as well. >> Thanks for inviting me. >> Always a pleasure. You know, this is like um Anna gave me the keys to the house and I get to have a little house party and bring bring friends in. So yeah actually very briefly because we have these shorter episodes I wanted to hear a bit about uh you guys and the kind of research you do. Uh Benedict what was your journey into the Ethereum research team? >> Uh yeah so I did a PhD in cryptography. Uh I finished in 2024 and before that like one year before I finished my PhD I did a uh research internship at the Ethereum Foundation where I worked on

data availability sampling and so I knew uh the team or at least parts of the team. I knew what it was like and it was very interesting because it like motivates a lot of interesting cryptography problems and so I thought after the finishing the PhD this would be a good place for me and yeah so I ended up in the cryptography research team. >> Nice. And Dimmitri I think you were there a bit before Benedict. Were you already there when you came on the show the first time? >> Yeah I think so. I joined uh the foundation at 2019. So well I did my PhD 15 years ago in Luxembourg and since then I've uh done lot of different things mainly symmetric crypto but then

at some point uh I was intrigued by this uh ziki proofs in particular starks there were some insecure hash functions in the first proposals and then we sort of suggested a more secure proposals and when I gave a talk about this proposal uh in Tel a Viv by eleason invitation I met Justin Drake at the conference and he invited me uh to the foundation saying that there will be a cryptography research and you will be the cryptographer >> uh at the team. At the same time he met Marer and told her exactly the same. So she would be the cryptographer.

we started uh together uh and then we felt kind of uh alone and we invited other guys and yeah some point we started working with Benedict and so far this has been really good uh collaboration. Yeah, it's been a very busy collaboration actually preparing for the episode. I looked up, you know, the papers that you guys wrote together specifically about this topic. And over the past year, there's already five of them. And this is just one topic cuz I know you guys are doing work on like other stuff on the side. So very very uh busy collaboration, right? >> Yeah. But it's also a very nice collaboration. I really like it.

>> So let's get into the main topic of today, the postquantum signatures and multi- signatures for lean Ethereum. I guess my first question is like we're used to our BLS signatures. What kind of signatures are we using here? Like how do we name them? What do they look like? How do they work? Okay, so maybe let let's start with what what BLS actually gives us right now and what we want to achieve. Um so BLS gives you a not only a signature scheme where you can sign messages but also uh a mechanism to aggregate those signatures. So uh if you think about elliptic curves, you can just add the points together and that would actually be an aggregated BLS signature that is uh equally short or like equally large as a single BLS

signature but it represents uh a lot of them. And this is crucial for Ethereum consensus where validators vote for blocks by signing them and then you aggregate those votes and so you have a short certificate that says okay these parties have uh have voted for the block. Now we want the same thing but secure against quantum computers because BLS is based on elliptic curves and uh if you for instance if you break the discrete logarithm problem which a quantum computer can break then you can forge BLS signatures so they will be completely insecure and now yeah we essentially want to move away from that to a scheme that is secure against

quantum computers and in short what we propose here with with leanig uh as sort of a replacement for BLS is a hashbased scheme that is based on very classical cryptography and like uh the main design has been explored for for decades but we sort of tweaked it to be to to match sort of the needs that the very specific needs that we have in Ethereum right so this is actually an interesting point right the the core cryptography has been around forever it's not like was it even invented before elliptic curves >> I think yeah in the early in the early days of of modern cryptography. I I always learned it in like cryptography courses as more like a feasibility

result. So there's a basic question in cryptography which is if I just give you a one-way function which is a very basic primitive what can you build from it? And this sort of these techniques they were mainly developed to show that one-way functions while they cannot give you public key encryption uh they can give you digital signatures and so it's a very yeah it uses a very weak primitive in our case just a hash function uh and it gives you a very powerful primitive like a digital signature scheme.

>> So what's a good like mental model for how the scheme you're going to use works? uh I think a good mental model is to start from a simpler primitive which is a one-time signature scheme. So you can think of it as a signature scheme but once you have used your secret key a single time so you have signed one message you have to throw it away and generate a new key because if you use it twice will be insecure. So if you sign twi two messages it may be insecure and it's but it's one time secure. So if you only use it once then no other party can forge a signature. So this is the starting block and this is this can be built from hash functions uh using what is called hash chains and once you have

that this the simple building block you can put a lot of one-time public keys into a Merkel tree and commit to them. So you have a short Merkel route that's just one hash that commits to this very long sequence of one-time public keys and then when I want to sign my say fifth message then I take the fifth leaf of my merkel tree and I sign using that one-time key pair and then I also add a Merkel path that convinces the verifier that you know this this public key that I include there is really the one that was committed to in the long-term public key. So I don't get a full signature scheme from that. What I get is a say if with key lifetime L an L time signature scheme where I can you use every leaf

just once but as it turns out this is already sufficient for Ethereum consensus because there we sign with respect to slots and we sign only once per slot and so this is the perfect fit and it's very a very simple scheme >> right so you go from a onetime signature to like many time signature >> yes >> and So do we have to decide ahead of time how many signatures the validators can do forever? >> Yeah. So we we decide on a maximum essentially. So uh the current thinking is like 2 to the 32. So that's a huge amount and this will >> do you have roughly an estimate and like how many years of Ethereum this is?

>> I remember that I calculated it for 2 to the 26 or something and it was already like 10 years. So if you go >> to uh 2 to the 32 this will be hundreds of years. >> Um and yeah because of the the nice the power of Merkel trees you know the the Merkel path is still only 32 hashes that contributes to the signature size. So um this it's actually uh fine and you can think of it as unlimited lifetime because 2 to 32 is just so large. Can we extend it? Like if we get to if we do finish the 22 32 is at the end of Ethereum.

>> Well, I would I would uh just generate a new public key, you know. >> Okay. >> You can you can either sign it using the last leave, sign the new public key or you dregister as a validator and register again. >> Okay. And so we have this signature scheme. I'm now curious, were there any trade-offs you guys had to explore? Are there any downsides or any other options that maybe were considered? >> Well, the main trade-off we actually explored was say size performance trade-off. So in this uh hash chain based signature that we're looking at there is the tradeoff between the number

of hashes one has to compute like either prover or verifier and the size of the signature. So one can imagine then for the same level of security this construction must have either uh longer chains or fewer chains. So you can imagine it as a rectangle which is like either wide or tall. So that like a tall rectangle means smaller signature uh and uh more hashes to compute like more path to walk on a chain uh on like on all the chains in total whereas like uh a wide rectangle something like bigger signature but in total you would have to walk smaller distance.

>> Okay. So many short chains or fewer long chains. >> Exactly. >> And the length of the chain is the computation we need to do and the number of chains is the size of the proof. >> Uh the number of chains is the size of the proof roughly. Uh and the length a chain is the combined work of a prover and verifier. >> Okay. >> Uh so like on each chain the prover has to do the beginning up to some point and the verifier has to continue from there. And if you optimize the signature scheme for the verifier because for example we want the verifier to be encoded uh as a circuit for a snark then we want the verifier to do smaller work uh because the circuit will be smaller uh and then

prover would have to do more work. If you optimize on the prover side because you kind of sign a lot for example uh then uh it would be the other way around but the kind of the sum of works for proof work verifier for particular set of parameters uh stays the same. Okay. Actually, you've touched upon like the next thing I want to talk about. You said like, "Oh, if you want to do a snark of the verifier. That's already a little hint." And actually Justin in episode one already told us like to get multi- signatures for this, we're going to use snarks, right? Um so can you tell us a bit more about how that mechanism works and um why we resorted to doing a snark of a

signature? >> Yeah, so I guess uh the point is that we want to have aggregation. So, so what we explained so far was the basically a signature scheme, but as you mentioned now, the term for the thing that we want is multi- signature scheme. So, what is that? It's a it's a scheme like BLS where you can sign, but then you can also aggregate these signatures to have a short certificate or like aggregate signature that represents a long list of signatures. Mhm. >> And in the classical world where we don't care about quantum computers, BLS gives you a very nice mechanism of doing that. And there are other structured schemes that have like the algebraic structure to give you that. In the

postquantum world, >> there's no scheme that has such nice features as BLS. This is very sad, but it's it's, you know, we have to deal with it. >> And there are certain approaches to solve this. So for instance, you could try to use more structured cryptography like lattice based cryptography or something. But even in the lattice based setting, I'm not aware of a scheme that has this nice non-interactive aggregation feature like BLS. >> And maybe we can talk about that later, but we we decided okay let's try to use hashbased schemes because they are minimal in terms of assumptions and so on. Mhm.

>> And if you want to hash hash functions just don't have algebraic structure. That's kind of one of >> one of the points the function right. >> Yeah. So if you have a hashbased scheme, it doesn't have the algebraic structure that you need to aggregate it say natively. And one way you can always aggregate any signature scheme is you use a snark generic snark that proves knowledge of a long list of signatures. So this long list of signatures is your witness and then the resulting succinct proof will be your aggregate signature. So if I see that proof I am convinced that the party who produced the proof knew a long list of signatures >> valid signatures. Right.

>> Right. So uh why why do we now need to express the verifier as a circuit? Well because this snark it proves a certain NP relation which is expressed as a as a circuit. And what is this relation in our concrete setting? uh I know a long list of signatures which all verify I know a long list of valid signatures. So I need to express this the verifification algorithm of the signature scheme in my NP relation in my circuit and the way I express it or like the way this this verification algorithm uh is designed has a huge impact on the proving performance or like in terms of multi- signatures the aggregation

performance and this is what Dimmitri uh was saying before >> right so actually circling back now that we've had the parenthesis on like why we want the verification to be fastish. How did you tune all these tradeoffs for what is now being called lean sig? >> Well, that was kind of this is still an ongoing process. >> Okay, >> the thing is uh well, we have this generic idea that we have a size performance trade-off. Well, I'm calling this the cost of computing the signature on the verifier side just performance.

And yeah, we we know that there is this trade-off and uh we have come up with a set of parameters for kind of the standard signature scheme uh which is known as winter signature >> or watts. So for watts uh we have come up with a set of parameters uh that uh we consider fine in terms of the security level we achieve. Well, assuming certain uh security of the underlying hash function. But uh also later uh when we investigated this question further, we figured out that uh it might be possible to improve the entire trade-off by having like both

smaller and uh faster to verify signature. But uh and this is the paper we eventually published at crypto last year. >> What's the title? The title is at the top of the hyper cube. >> Okay. >> Well, the name comes from viewing this set of chains, a hyper cube. And basically, we said that it's apparently better to use longer chains and uh use only the top of the hyper cube uh to sign. And the problem with that idea is that it requires more effort on the verifier side to process the message and to sort of map it into this uh points on

on the chain on each chain uh where where verifier starts from and this is called encoding and this encoding turns out to be a really sophisticated thing. So when you do it on a PC it doesn't really matter but whenever you try to encode it uh for a snark you encounter certain problems and uh this complexity we haven't really uh overcome yet. So like theoretically it's a nice scheme but uh whether we use uh it in its entirety uh for linse this is still uh under investigation.

>> Okay. So specifically you mean this at the top of the hyper cube optimization is uncertain to make its way into lean Ethereum. Did I understand that correctly? >> Somewhat. Yeah. >> Okay. >> Like but but but we have made progress towards this. So uh we just put out like in January a new paper uh it's called uh aborting random oracles. It's a very weird name. It's about an a new like cryptographic model and like toolkit that allows you to make an easier analysis of of certain encodings in some way. when we had this this whole top of the hyper cube thing uh we came up with certain encodings and then we learned okay they are not not that great for the

verifier for I for for the verify in a circuit because they for instance use big integer arithmetic >> and so there were some ideas uh for instance Dmetry had a very nice algorithm for doing it without uh big integer arithmetic but uh it would abort some of some non-negligible amount of times you know So it was not not at all clear how to do the security analysis. So it's a uh an an elegant algorithm and we were like intuitively it was clear to us that this should be secure but uh of course we we aim for a very conservative uh workflow here. We want to have >> intuition is not enough. Huh.

>> Uh right and so we came up with a new like formal model um that we related to existing formal models. So it's equally conservative let's say. And uh in that model we can now prove the security of this of this new encoding. >> Okay. So just to make sure I also understood correctly this encoding we're talking about is how do we map messages onto operations on these hash chains. Is that correct? >> Right. You take a message and some random salt and you map it to positions on each hash chain and you can view the vector of positions of these hash chains as an element in a certain hyper cube and uh this is why this thing was called

top of the hyper cube and this this way of looking at it is sometimes useful. Um and yeah this encoding algorithm needs to be executed by the verifier in the very first step and so uh yeah it needs to be proven inside a a circuit like in in in our generic snug and so um we need to optimize that. >> Yeah. So I was curious in all these papers I'm sure there's there's a lot happening. I remember reading the first one, hashbased uh multi- signatures for Ethereum. Um, and it mentioned something about like having to redo parts of the security analysis or having to do something tighter like what is happening there and is this something for Ethereum

or is this just like a nice cryptographic thing to study? >> I think it's both. Uh, I mean, >> okay. So, so as Dimmitri said, our goal is to minimize both the the verification hashing or like the optimize the performance of the verifier and to minimize signature size because we will transmit these signatures. They need to be sent over the network. So, this has direct impact on bandwidth. Um and just to give a feeling like these signatures are something like uh 2 to 4 kilobytes whereas a BLS signature is just uh 48 bytes I guess >> I think 96 Justin was saying >> uh 96 because you do it on the other on the G2. Yeah. Okay.

>> Okay. >> Uh depends on how you do BLS but I guess we do it with the 96 version. Yeah. Um right. So they are much larger and we so we want to squeeze uh signature size and verification hashing and one way to make signatures smaller is to you know this this these signatures are just a long list of hashes in the end. So just make one single hash smaller. So use a hash function that has a smaller output. That's one way of making it smaller. But the question is is it still secure? So uh if you use a small output it's for instance it's easier to find collisions.

So what how does that impact security of the whole scheme? And so what we had to do is to find uh a very tight analysis of the scheme. What does tight mean? It means that the security of the hash function and the security of the scheme are about the same thing in terms of concrete numbers. Yeah. So there there were security proofs of that but they were done in models that we didn't like that much. I mean in some sense like uh we thought that we should do it in more conservative models and so in these more conservative models there were no yeah there there were just a few proofs and they were really not tight so they would have blown up the signature size a lot

and so yeah that's why we had to redo a lot of this work and find the tweaks here and there to to make it uh as tight as we can but this is also still ongoing work there maybe even tighter analysis in the future. >> Oh, interesting. Okay, I will fill in a few details of these models you're talking about because this actually recoups something we've already discussed on the show, which is you're doing signatures that involve hashes. We as cryptographers like to model this as a random oracle. We say, okay, a hash function is a random oracle. Life is good.

>> Now, we're doing multi- signatures. So, we're saying, all right, I'm also going to have a circuit that does the verifier, right? So I actually now need a circuit that does random oracle calls >> and that's something we can't do. And that's something we've already seen with recursive proofs actually like folding schemes. >> We've discussed this quite a lot on the show with Biny last time he was on and we'll have a link in the show notes. >> Um so how do you get around that with this multi- signature scheme? >> Yeah, I think you summarize it pretty well why we don't like the random oracle model so much in this context. So just to be clear, I think the random order model is a great thing. Uh I think you just have to be careful. There are like even results that show like you cannot

build a proof system for so-called relativized languages which are just as you said circuits that call random oracles. Um there are certain impossibility results which does not mean that it's generally insecure. It's just that we have to be careful about it. Uh and so we thought let's be conservative. Let's do a proof in the standard model. So the standard model is just don't assume your hash function is a random oracle. Assume your hash function is just an algorithm where everyone knows the algorithm, everyone knows the circuit description. So this is sort of that's why it's called the standard model. This is what actually happens in real life. Yeah.

>> You know, everyone can look up how Poseidon works and so you now do the security analysis. But if you are in that model, you have to make assumptions. You can only prove your scheme secure if you make assumptions. Otherwise, you would already prove P not equal NP. So, >> we make certain assumptions about the hash function. For instance, target collision resistance, pre-image resistance. We didn't want to use collision resistance because that would impose a very yeah large parameters. Mhm.

>> Yeah, we did we did uh define a bunch of security properties for the hash function and then we showed if these properties hold then the scheme is secure. >> Mhm. And now it all boils down to does the hash function that we use satisfy these properties? And now to set parameters we somehow have to use again the random oracle model because otherwise how would you figure out how long the hash output needs to be so that it satisfies this. So in some sense if you plug everything together you you get back a random oracle analysis. But it's in some sense more conservative and more structured because you reduce to standard model properties which can

already be the target for cryp analysis >> and then you just do this horistic thing to to argue uh that you know this is a reasonable way to set parameters. So I think this is more conservative and more uh structured and easier to verify uh as a proof paradigm than just proving everything from scratch in the random oracle model. Yeah, this is actually the perfect segue into the last thing I wanted to talk about with you guys, which is the hash function that's being used. You mentioned poseon, you mentioned cryptonalysis. We have Mr.

Crypton analysis and Mr. Poseidon here with us, so I would kick myself for not asking. Uh what's the role that Poseon plays here and like what's the status of cryptonalysis on Poseidon? >> Yeah, that's a great question. So uh well there are two versions of Poseidon actually. So there was very first one that was designed by for big prime fields back at the time when like snarks over elliptic curse were in fashion and uh this what uh was designed even before I joined the foundation in 20 2018 and uh this version uh stands uh very good but the thing is we uh can't really use

it in this context because to be used in postquantum uh proofs uh it's better to use it on small prime fields otherwise you suffer huge performance penalty and because of that at some point uh the Poseidon team decided to to make a new version uh with little modifications on the linear parts I would say um and constants a little bit uh that was designed and tailored to small prime fields >> and this is the version we actively analyze right Now, so as customary in symmetric crypto, uh we can't prove the security formally of block ciphers or

hash functions and the way to establish our confidence in the security of of these designs is through public scrutiny. So basically we sort of publish a design and say okay we've tried our best to break it from all different perspectives. We have failed here is kind of the evidence that we have failed. Please try yourself. And then the community uh joins and try to also attack attack reduced versions, attack weakened versions like with some components removed here and there tries to challenge the designer decisions whether all of them are sound, whether some of uh things are redundant and so on. And yeah, this is the this was the process for example when the shash

function was selected back 15 years ago. And this is uh the process we sort of try to imitate here for Poseidon. Uh kind of two years ago it became evident that Poseidon is used in more and more applications if not in Ethereum itself but on the L2 >> uh in rollups and in many other places. and the community kind of the bigger community wants to know is it really secure uh this hash function or we just kind of use it because no one bothered to try to break it and because of that uh two years ago we started what's called Poseidon initiative uh that's a series of grants bounties workshops that

tries to invite as many cryp analysts from all around the world to work on Poseidon and try to break it from all different perspective and of course we didn't expect that no result is published so of course some new dents were made into the security of Poseidon but so far so good I would say like the security margin uh has become naturally smaller than it was but it's still there and uh yeah this year we plan to do more workshops and grants targeting specific applications in particular we target this properties that we want from Poseidon within Linig. This called

target collision resistance and multi-target collision resistance and there probably will be dedicated bounty for this sort of attacks. >> Are the same properties relevant to you know the snark that's going to be used for multi- signatures. >> It depends on the kind of snarks. But if you consider say snarks u where you use a hash function basically in two capacities. So one is to build the Merkel tree for commitments >> and in this context usually collision resistance is is required. So there is some ongoing work trying to show that probably some weaker property is sufficient not just collision resistance but so far just the collision resistance

is required. Uh and the second thing is fetchamir. uh for fat shamir it's very difficult to formulate what exactly you need from a hash function and uh we have tried to also come up with some kind of boundaries or exercises uh that I inviting people to break uh like toy protocols uh with the chamir and poseidon inside there are so called zero test properties uh that uh one may try to break and actually yeah uh we expect new bounties to be public within a few weeks and I invite everyone who wants to try their uh cryp analyst capacity to try to break it when they're up.

>> Nice. Great. One last thing you also mentioned you know Merkel trees and the snark and the last paper I have from you guys that came out most recently is called the billiondoll Merkel tree. Can you touch on this very quickly? I think we only have a few minutes left. >> Yeah, so it's it's not so much related to leanick directly. It's more related to generic snarks and and uh CKVMs which are also a big topic in Ethereum layer 1 right now. The story of this is you know mercer trees are very powerful and they are as Dimmitri said they are used in in Starks for instance >> and essentially a big part of the industry relies on one specific Merkel tree implementation which is the one in

the plunky 3 library >> and so we we looked at this and we figured out that this is a very unusual way of doing Merkel trees right >> like the first thing we thought Dimmitri and I when when someone told us about how this design works is, you know, this sounds completely insecure, but uh so we looked at it closer and it turns out that there's sort of some final twist that they do that at least intuitively makes it secure. But as we said before, we don't want just intuitive security. >> We want formal verification everywhere.

>> Yeah, in the end we want formal verification. So the first step is to have like uh pen and paper like security proofs in a PDF, you know. So we we uh looked at this and we did a security analysis of this and it turns out uh you can formally prove security of it. So uh it's nice and we communicated to the maintainers of of PL3 so that they know about our work and yeah we put it uh on e-rint recently. Um yeah so that's a quick summary I guess. >> Amazing guys I think this is a a lovely way to wrap everything up. Thank you so much for coming on the show both of you.

>> Thanks for inviting. Thank you for inviting us, Nico. >> I also want to say thank you to the podcast team, Anna, Rachel, Henrik, Tanya, and Hector. To those of you catching us on video, thanks for watching. And to our listeners, thanks for listening.