Post Quantum Transaction Signatures #002

|2026-02-18| Agenda: #1916| canonical JSON

Transcript

Antonio Sanso:Hi everyone, I just joined,

Antonio Sanso:We're waiting a few more minutes, a couple more minutes, and then we'll start. I will have, like, a short, presentation to…

Antonio Sanso:set the stage, and then we'll go for the agenda. One more minute, and we'll start.

Antonio Sanso:I'll start sharing my screen.

Antonio Sanso:Can you guys see it? And can anyone confirm?

Mike:Yep, yep.

Antonio Sanso:Yeah, I mean, we're 2 minutes over. This meeting is then, in any case, recorded, so I will just start, and again, I will have just a short presentation to set the stage. Welcome, everyone, to the breakout room number two. Thanks a lot for attending.

Antonio Sanso:I spent this couple of weeks to just do a recap of the situation.

Antonio Sanso:And, I will post this online later on, but this is a kind of, table that compares, the next postman signature schemes, and, different access,

Antonio Sanso:So basically, last week, we were seeing a bit of, lattice,

Antonio Sanso:signal schemes, and here is a quick recap of what we've seen so far. For example, like, the signal size, Falcon is shorter than the dilithium, so it's in green, and the Gasper compiles, we've seen Renault and Simon showing that for the, for the…

Antonio Sanso:pre-compile the gases, Falcons as well, cheaper,

Antonio Sanso:We know this already, and it's kind of important. For aggregating the signatures, it's really important for the main pool, but probably we're going to see this in the future. Falcon has some solution that is based on something… something…

Antonio Sanso:some paper, they call Labrador, but with didilithium, it's, yeah, it's not so friendly.

Antonio Sanso:And, where Falcon has issues at the moment is, and Dalidium is better, is, on the hardware. Historically, like, we know that, Falcon relies for signing on floating point, and this is actually for, for Ledger or this kind of hardware. This is…

Antonio Sanso:Might be complicated.

Antonio Sanso:And yeah, we'll see in probably some future calls, the threshold friendliness for post-controlled signal tourists, in any case, a disaster. We have today some presentation on Sphinx, TSS.

Antonio Sanso:And, yeah, this is basically it. Today, we are… a lot of, topics are, at least for the presentation, about, symmetric cream, so,

Antonio Sanso:submit primitives that are, based on hashing, so… and here we have as well some recap on the standard Sphinx. We see that, yeah, we see a bit of red here and there, and

Antonio Sanso:Yeah, this is the agenda.

Antonio Sanso:We will have, Mikhail presenting their version of the hash-based signature scheme that is more efficient for blockchains.

Antonio Sanso:Then, actually, we have Nico that will have a cool demo showing this in action.

Antonio Sanso:And we'll have, Yasvanda and Naman seeing the difficulty of having, threshold signatures.

Antonio Sanso:For, hash-based schemes. And then, ideally, we will have some…

Antonio Sanso:more minutes. I did 20, 30 minutes to discuss.

Antonio Sanso:stuff.

Antonio Sanso:And if you don't have any more questions, I will give the stage to Mikhail.

Antonio Sanso:Totally, we can start early.

Antonio Sanso:Mikhail, the stage is yours.

Mike:Thank you.

Mike:You should be able to see my screen now.

Antonio Sanso:Yep, all good.

Mike:Oh, good. So, yeah, I will, give a brief,

Mike:summary of what you can do with hash-based schemes for the scenarios such as blockchains. We specifically looked at Bitcoin application, but I think most of our findings are, in general, applicable

Mike:To the blockchain environment.

Mike:So, obviously, while we're here, we have the quantum thread, we want to move to post-quantum solutions, so in case, when our… whatever quantum computer appears, we're safe, we're secure.

Mike:And, the options are actually quite… there are quite a lot of options. You can do lettuces, you can do hash-based. For lattices, you have a variety of schemes. Unfortunately, none of them is as good as our classical counterparts.

Mike:And today we will look at hash-based schemes, and what they can offer, what are the upsides, what are the downsides.

Mike:And the first, and arguably the most important upside of the hash-based schemes is their security. So it's super conservative, everybody is using hashing everywhere, there is no problem with that. If we don't have hash functions, we essentially don't have

Mike:Almost any cryptography, all the latest-based schemes still use hash functions, so this is as minimal as you can get.

Mike:But the problem, as we saw on the slides before, is that the sizes are quite large. For… there is this scheme, Sphinx Plus, which has been standardized, and, for the best sizes, kind of, there are multiple,

Mike:parameters were selected, and if we select the one with the best size, I think it's something like 7.5 kilobytes.

Mike:That's huge.

Mike:Where does this come from? Is, we have this structure, it's called a hypertree. So, essentially, it's a Merkel tree, at the top.

Mike:The leaves of the Merkel tree are one-time signature schemes, so they can only sign once, and we use those signatures to sign Merkel trees on the next level, and so on and so on and so on, until we get to the very bottom.

Mike:where we use, so-called few-time signature scheme, which we actually use to sign the message. So we have this kind of, certification, kind of. You have this, root of the top, Merkel tree, and then you show, okay, I do this signature, and I attach the annification pass for here, I do this signature identification pass, and so on, so on, so on.

Mike:And so you have to include everything that we just discussed, and this were the…

Mike:Sizes, come from.

Mike:But, there are a couple of optimizations. The core idea here is that this tree can be used only for a limited number of signings.

Mike:Essentially, if we forget about few times signatures, the idea is to create a tree big enough so that if I sample a leaf at random, they will not collide. With the few times signatures, they shouldn't collide too often, but that's…

Mike:the small detail. And so, NIST, asked for, a scheme that will be able to perform 2 to the 64, signing operations.

Mike:And, for our applications, we don't need 2 to the 64 signatures. That's… that's a definite, statement.

Mike:We looked at some numbers, and I think even, like, 2 to the 35 signatures.

Mike:of size 3 kilobytes will fulfill, the whole Bitcoin, blocks for, I don't know.

Mike:100 years, or something like this. I should double-check the parameters, but yeah, the 2 to the 64 is a huge overkill.

Mike:And, this is not a novel idea, that actually you can limit the number of signatures for hash-based schemes.

Mike:And, there is, I believe, currently also an ongoing process in NIST to standardize a scheme with fewer number signatures, so…

Mike:On the slide, you can see the presentation by Stefan and Jade that were also…

Mike:searching for different parameters by just reducing the allowed number of signatures. As you can see, so these, green triangles here, this is different parameters for, 2 to the 64 signings.

Mike:Yeah, if we go as low as, here, it is somewhere around 7,000, I think, here.

Mike:But if we go, for example, for 2 to the 20 signatures, you can get much, much smaller signature sizes.

Mike:So this is the first, and arguably the most obvious,

Mike:Modification that you can make is, decide, in your scenario, what is, what is the limit that you are happy with, and just limit that.

Mike:The upside of doing nothing else is that, essentially, you're more or less Can reuse the existing implementations.

Mike:Maybe in the future, you will be able to use some hardware acceleration, but this hardware acceleration, question mark, if it will be there or not, specifically for Sphinx.

Mike:And, whether you could use the acceleration with different parameters, this is… this is not entirely obvious, but at least you can reuse implementations.

Mike:Then, if you think, okay, I'm…

Mike:still happy to deviate from the standard, and arguably the most popular version of hash-based signatures, then there are also different modifications that you can implement. So, as you saw on the slides, we have different building blocks here.

Mike:We have one-time signature schemes, we have few-time signature schemes here, and so if you change them.

Mike:Because, researchers came up with…

Mike:Arguably something better. You can also change the performance.

Mike:And, most of this, or most of these modifications, what they do is they put extra, effort on the signer, so the signer needs to do more work, but this will either reduce the,

Mike:Sizes, or verification complexity.

Mike:Sometimes, we increase both the siting complexity and verification complexity to get more

Mike:To reduce the signatures even more.

Mike:And so, what, we can see this, on, on this slide.

Mike:We have, Sphinx, this is the first line, and, as I said, yes, 7,872 bytes. Yeah, this is, this is pretty, pretty sad.

Mike:And,

Mike:we can start limiting the number of signatures, and here, in this column, we say, okay, which modifications to apply. And already here, you can see that we can get as low as 4,600.

Mike:With similar signing time, and similar verification time, yeah? Okay, this is twice worse, but this is no big deal, and here's the same.

Mike:And, if we apply even more modifications, then we can get as low as 4 kilobytes for 2 to the 40. And 2 to the 40 is

Mike:Arguably also an overkill. Then, if you're happy to go even lower to the 30, you can reach, 3.5.

Mike:kilobytes for different cases, depends on how many modifications you want, and depends on how much, are you happy to put on the verifier. And I must say here, yeah, you have, the numbers, 8,000 compared to 2,000 here.

Mike:This is quite, quite low, actually. The 2,000 hashes to compute is not a big deal for the verifier, so it is arguably completely fine to push it even to the 10,000. This is not a big problem here.

Mike:And if you're happy with around 1 million signatures, you can go even below 3 kilobytes.

Mike:And I think this is really nice, because we start with almost 8KB signatures, and we actually can get to somewhere around 3 kilobytes, which is much, much better.

Mike:And, people always say, okay, lettuce-based, they have quite small signatures compared to lattices, compared to hash-based. And again, yes, yes, the signatures are smaller, but for most of the blockchain applications, you should actually compare signature plus the public key.

Mike:Because you will need to put both of them on chain. And, if we compare Didilithium with,

Mike:our modified hash-based parameters. Okay, yes, the dilithium can support more, but do we need more? And then the sizes can even go, in these scenarios, can even go better.

Mike:And, another, I think, which is quite, quite popular topic right now, especially in Bitcoin, is a scheme which, which was called Shrinks.

Mike:Which introduces the idea of mixing two different hash-based schemes together.

Mike:The thing is, when we talk about Sphinx Plus, it is a stateless scheme. That means you do the signing, and you don't need to update your secret key, so that, yeah.

Mike:You just do the signatures, and you don't need…

Mike:To modify your secret key.

Mike:there is, there are stateful, hash-based signature schemes, and an example, you can see on the left side, essentially you do a Merkle tree with one-time signatures at the bottom.

Mike:for example, this one can sign four messages, yeah? You need to remember which ones you have already used. So, the first message you sign with the first leaf, the second message with the second one, third with the third, and fourth with the first.

Mike:If you run out of leaves, you're done, and you shouldn't reuse the same leaf twice.

Mike:And,

Mike:Such schemes are more efficient than stateless, but the problem is, yeah, you have to store and modify the state.

Mike:And this is especially annoying if you want to do backups and then restore the backup, the backup should have the state, and you… every time you sign, you kinda need to update the backup, otherwise you won't be able to use it, and so… this is a little bit annoying.

Mike:But moreover, what we can do is, instead of using a Merkle tree, kind of a usual, usually balanced Merkeley, we can use an unbalanced Merkel tree.

Mike:Which means that the first leaf is just one, path away from the root.

Mike:And so, the first signature will be super cheap. I think, according to our computations, it's something like 300 bytes. 300 bytes is just nothing in the post-quantum,

Mike:Cases, I don't think any other signature can achieve

Mike:300 bytes, yeah, this is… this is nothing.

Mike:And, the second one will grow, so here you will need to include more.

Mike:Because you need to include the identification pass, so you will need, yeah, extra, extra nodes to include, and so on.

Mike:But also to mitigate the statefulness.

Mike:we can combine our stateful scheme with the stateless version. Okay, here it's written Sphinx+, but essentially you can plug in whatever we discussed on the previous slides.

Mike:And then you have this… Arguably a nice combination of, statefulness with very cheap, signatures.

Mike:Plus the stateless for a backup in case something went wrong.

Mike:This has also its potential downside, because stateful is still…

Mike:annoying to work with. You still need to update the state. If you generate multiple addresses, so essentially you generate multiple key pairs, you need to store the state for each key pair.

Mike:You cannot allow two signing devices to operate in parallel.

Mike:There are a lot of caveats there as well.

Mike:But, as a, as a plus, you get, you get quite, quite small signatures.

Mike:Yeah, I think this can, summarizes

Mike:Overall, the ideas that we… that we… Discovered so far?

Mike:I think I can also… we also checked different, extra applications as, threshold signatures or multi-signatures that, will be later discussed, during this, call.

Mike:But, from our findings so far, there was… there was some approaches, but none of them are super efficient and don't give too much.

Mike:Maybe there's something extra that we don't know, but let's see that later in this call.

Antonio Sanso:Mike, thanks a lot for your presentation. This is… was a really interesting result, to see that actually, happening.

Antonio Sanso:And, I will ask you if to, please, if you can, answer… there are some questions on the chat, interest of time, if you can answer in the chat rather than, than, by voice, so…

Mike:Yeah, sure.

Antonio Sanso:We'll give the stage to Nico, and actually, it's really beautiful, because Nico, as far as I know, already implemented part

Antonio Sanso:of your work, and we'll show it in action, on Ethereum. So this is…

Antonio Sanso:I cannot imagine any better segue.

Antonio Sanso:Nico, if you're here, this is your time shine.

Nicolas Consigny:Thank you, thank you.

Nicolas Consigny:So I'm gonna try to share my screen.

Nicolas Consigny:Let's see…

Nicolas Consigny:Okay.

Nicolas Consigny:Can you see my screen now?

Antonio Sanso:Yeah, yeah, we see it. All good.

Nicolas Consigny:Another short presentation…

Nicolas Consigny:So, I figured out that, like, it's better to give a short presentation rather than just, you know, showing you.

Antonio Sanso:For sure.

Nicolas Consigny:what? Hold on, slideshow?

Nicolas Consigny:All right, so yeah, I just wanted to make a quick presentation, rather than showing you, my script and my deployments, because this would be just me typing a few comments in the terminal.

Nicolas Consigny:So what did I do? I actually tweaked the Blockstream research work. So Blockstream has a very nice repo where you can look for Sphinx parameters that are nice for you.

Nicolas Consigny:So, in the EVM context, you have a slightly different

Nicolas Consigny:Constraints, because you have gas, and basically, it becomes, a research of, the most efficient,

Nicolas Consigny:parameters within the EVM constraints, so same as for other blockchains, you have the reuse constraints, so you want to be able to reuse your

Nicolas Consigny:your scheme a certain number of times, so that people don't have to change wallets all the time. And to combine this with some gas efficiency.

Nicolas Consigny:So doing this… I ended up, finding a bunch of sweet spots.

Nicolas Consigny:And I tried two of them in deployment. So these are the sweet spots that I found, and good to mention here that I, yeah, I looked a little bit, but I didn't look that much.

Nicolas Consigny:So maybe someone can find a better sweet spot, and there is a lot of design space here. So yeah, this is just a presentation to open the discussion around this, but it is by no means,

Nicolas Consigny:the Canon Equal or the best solution that I found.

Antonio Sanso:We're just trying to decipher this. Is this, like, if you try to correlate this with the presentation of Mike, is this, like, the strings?

Antonio Sanso:Or are the… the XMSS, or the Sphinx? Which, which family is this? Because… Yeah. Yeah, sorry.

Nicolas Consigny:So these are a different, variants of,

Nicolas Consigny:That are actually explained in the… Let me recheck… This link… oh.

Nicolas Consigny:The variants are actually explained in the…

Nicolas Consigny:in the repo here. So W plus C is Banks Plus with…

Nicolas Consigny:VOTs, with counter-based, VOTs, so no checks from on the chain. So you can find everything, like, all the details, all the different families inside the, the repo, inside the Sphinx Parameters repo.

Nicolas Consigny:So it's basically just a bunch of variants of Sphinx, and they have different, properties.

Nicolas Consigny:So if I go back to slideshow…

Nicolas Consigny:Yeah, so these are different families of Sphinx, and we… we select… I selected this, these ones, because they just look nice, not too big, somewhat…

Nicolas Consigny:Easy to, to, to, to verify.

Nicolas Consigny:And yeah, so I have this, small repo where I try to…

Nicolas Consigny:to do it, and earlier today, I deployed them on a test network, just to find the real cost.

Nicolas Consigny:So I ended up with transactions that are about 400K, but these are 4337 transactions, so there is a large overhead for the 4337 framework, so there is the overhead for the entry point and a bunch of

Nicolas Consigny:different things. So these are, hybrid accounts that are relying both on a K1,

Nicolas Consigny:K1 signature and the post-quantum signature, so I copied the work from Zeke and Ox, who presented last time, and I simply tweaked it with my two schemes.

Nicolas Consigny:And, it's, it's quite interesting, because, we can have, under 200K, gas,

Nicolas Consigny:signature with, the C2 scheme.

Nicolas Consigny:And 250K gas with the C3 scheme.

Nicolas Consigny:So this is something that is, big. It's about, yeah, 10 times bigger than, a regular K1 signature, but it's not crazy big. So this is, yeah, this is something doable.

Nicolas Consigny:And yes, so you have the cost, breakdown here, so you can see the…

Nicolas Consigny:The debug trace from the… From the transactions.

Nicolas Consigny:I will publish the transaction, probably, with the repo, so everyone can look at them.

Nicolas Consigny:And, yes, so this, scheme retains, so it's, to make a parallel with the previous presentation, this one is, is okay with… at 120 bits with 2 to the 20 signatures, so that's roughly a million signatures.

Nicolas Consigny:at, 128 bits of security. Then it goes down, quite nicely, because it goes… it still allows you for, like, 4 million signatures.

Nicolas Consigny:up to 112 bits of security. So if we bring that back to the context of a wallet.

Nicolas Consigny:You don't have that many people who sign millions of transactions on-chain, and if you do sign millions of transactions, you probably…

Nicolas Consigny:are a very, very advanced user, so you somewhat know what to do. C3 is slightly more expensive, but retains more security, so you can keep, about 140 million transactions at 120 bits.

Nicolas Consigny:of security, so that's really a lot. Actually, I checked quickly, and nobody has,

Nicolas Consigny:hundreds of millions of transactions with the same wallet pair on the execution layer. So, yeah, it is…

Nicolas Consigny:It is a very interesting design space to explore. So I have this meme right now, the best competitor that we have is this guy.

Nicolas Consigny:And yeah, to finish the presentation, I did all of this very quickly. I'm not a cryptographer. I have a lot of cryptographers in my colleagues and friends, so we will be looking into it, and maybe… maybe I'm wrong, so if I'm wrong, we'll just get it and find,

Nicolas Consigny:Another set of parameters that is.

Nicolas Consigny:It's a good one.

Nicolas Consigny:So yeah, that's it for today. I will taste…

Antonio Sanso:Call me…

Antonio Sanso:just because, like, it's true that there are 10 times bigger than ACDSA, but it's as well 10 times…

Antonio Sanso:less than the Falcon we've seen last week, so it's… actually, it's a remarkable low number of gas, right?

Antonio Sanso:The question I will have… probably, I should have a question before as well to Mike was about the creation of the…

Nicolas Consigny:I think we need to…

Chat Logs

Fireflies.ai Notetaker Jay:Jay invited Fireflies.ai here to record & take notes. View Security & Privacy info: https://fireflies.ai/policy Type: '/ff leave' - Remove Fireflies View Realtime notes here: https://app.fireflies.ai/live/01KHP2EJX4XHC4AZ4MWBSBVSVB?ref=live_chat

Danno Ferrin - Tectonic.xyz:This is all with 32 byte pubkeys?

Fab:Must the used state stay private? Otherwise, we could attach it to the transaction.

Fab:So the chain itself keeps track of this

Mike:Replying to "This is all with 32 ..." Yes 16 bytes seed, 16 bytes hash output

Mike:Replying to "Must the used state ..." The state can be public, but the problem is that some transactions/signatures may not end up on the chain

Parthasarathy Ramanujam:How is this different from the Ethereum Foundation’s XMSS paper released last year? Is 2^20, 2^64 you mentioned earlier refers to lifetime? https://github.com/leanEthereum/leanSig

Mike:Replying to "So the chain itself ..." The problem that we can not guarantee that the signature will end up on the chain in 100% of the cases.

Fab:Replying to "So the chain itself ..." True, but the wallet could be keeping track of that. In this case the only corner case is when you try to land a tx, it doesn't get through, you do nothing afterwards, and then reset the wallet. Still far from perfect but at least the surface is reduced.

Mike:Replying to "How is this differen..." Etherum approach focused on the stateful signing with a "balanced" XMSS. We explored stateless parameters. Moreover, the aim for Etherum project was to optimize the SNARK-ing

Fab:Replying to "So the chain itself ..." Another solution could be a public server akin to the former MIT GPG one. This server aggregates state and periodically rolls it up on-chain.

Mike:Replying to "So the chain itself ..." Reusing the state is a security problem, so for it is drastic for any user if the state is reused. I would not trust an external server with my state :)

Parthasarathy Ramanujam:Does this is uses keccak256 hash? @Nicolas Consigny