Introduction to LeanSig

Transcript

block and then they want to sign it to to attest to that block. So they use their secret key to compute a signature and then we have some uh algorithm that publicly and deterministically aggregates these signatures into a short representation of all of these which is what we would call the aggregate signature and this is much shorter than all the signatures together and we put the block with this aggregate signature on chain. Uh and what I mean by public and deterministic is public means you don't need any secret keys to aggregate and it's clear I guess um so how do we currently implement this in Ethereum's consensus layer we use PLS signatures which are nice and short and elegant but

they are broken by a counter so this is where all of this started and the goal was to have a postquantum replacement for that so postquantum multi- signatures for Ethereum and uh just to clarify by multi- signature I mean a signature with some uh aggregation method that works works If you sign the same message and you want to aggregate these signatures, that's what you typically call these signatures. Okay. And uh quite early we sort of concluded okay hashbased signatures are what we should look at what we want to use and Justin already made these points but I want to repeat them. So why do we use hashbased signatures? Well they are conceptually simple. A lot of people can understand them. There's no like heavy

algebra involved. And so it's good if a lot of people can understand a crucial part of the Ethereum protocol. And because they are so simple, they are also not that hard to implement. Uh and on the sort of security side of things, they are uh good in terms of assumptions, in terms of minimality of assumptions. For instance, if you use a hashbased scheme, then it would also use a hash function. Sorry, if you use a lettuce based scheme, it would also use a hash function. So just using hash functions is more minimal in terms of assumptions. And then there's this point that having just a hash function as the basic building block of Ethereum and essentially that's all in terms of cryptography is quite elegant.

Okay. But just as a disclaimer if tomorrow someone publishes a paper about a very nice lettuce based aggregate signature scheme or multi- signature scheme that has all the properties that we need then of course uh you could convince at least me to to rethink this. Okay. So let me give you a history. How did we end up with this lean sick uh proposal? So it started about a year ago when Justin gave this talk about beam chain in Bangkok and like even before that we already started to look into that and then as a result what we now have is three uh documents or papers. So two of them I would actually call paper.

The third one is more like a technical document that merges the ideas of both. and they sort of propose this this lean sick which is the postquantum signature proposal for a and there's also rust implementation which I think is pretty stable uh as of okay so how does this how does all of this work I think Justin already explained a few things but I think it's good to repeat this because it's so central uh so as I said this multi- signature scheme is just take an individual signature scheme which allows people to sign messages to verify these signatures and some public aggregation process and the individual signature scheme would be hashbased signature scheme and this is what we call lead. So

just to clarify terminology leanig is just the individual scheme without the aggregation and then we would have a hashbased sensing argument uh which is going to be based on uh to get a multi- signature scheme that we then call multisync. Okay. So how do you aggregate using these hashbased sub arguments? Well, you take as as a witness the signatures that you want to aggregate and there's a public input or statement the message and the public keys and then you prove that for every I the I signature is valid with respect to the I public key and I want to emphasize that uh what you prove here is the verification circuit or the verification algorithm of the

signature scheme. So that will be uh important and um yeah so that's how how you do that actually uh for all the theoreticians in the room what is interesting is that to to prove security of this whole approach you need that this hashbased snark satisfies adaptive knowledge soundness and there is evidence that these schemes satisfy this I think Jako has a nice paper in the standard random oracle model whereas in the quantum random oracle I think this is still no And uh I invite all of the in um okay so for for the rest of this talk I want to focus on the lean sig the hashbased signature scheme without the

aggregation. Okay so that was our goal post quantum multi- signatures and now I have told you that with hashbased marks we can actually reduce this goal to getting an aggregation friendly hashbased signature scheme. Now what does aggregation friendly mean here? uh I think it primarily means two things. The first is we need small signatures because the party who will aggregate these signatures first has to receive them. We have to send them around. So the size of signatures uh is really directly related to the bandwidth requirements uh in our network. And just to give you one example, let's say our individual signatures have size 32 kilobytes and we only have 4,000 validators. then we would already need

something like a one gigabit per second connection to to do this aggregation and so 32 kilobytes is just way too large and actually what we are now at is something like 3 kilobytes. Okay. And the second uh the second goal is to minimize hashing and in particular hashing in the verifier of the signature scheme because uh if you remember what we prove with our snark is uh the verifier algorithm. So the more hashing we do there the more the more work it would be to do these proofs. Okay. So minimizing verification hashing means to improve aggregation efficiency.

Okay. So these are the goats and now let's look at existing hashbased signature schemes. Why why would we even design a new one? So there are primarily two uh schemes. There's sphinx and xs. So sphinx even though it's a hashbased signature scheme I would say is still quite complex and so we don't really want to use that. On the other hands is very simple but it's uh not really a full signature scheme. It's a synchronized signature scheme or what Justin called a stateful scheme before. And this is sometimes a drawback in some applications but we will see that for us this is not a problem and uh now you may ask okay XMSS if we use that what's the point of our work

why did we publish these three papers uh and I think the the point is is these two things so first of all known security proofs for XMSS were kind of non-tight and more like textbook versions to educate people and not really meant parameters in practice. And so what we did is we used modern proof techniques to uh get tighter security proofs for these XMSSS uh like schemes which then results in improved efficiency better parameters. For example, you can reduce the output length of the hash function. And the second point is that because the of the previous slide we are interested in improving the trade-off between size and

verification hashing and we are actually the first to study this at all. Um because it turns out for these schemes if you increase size then you can reduce verification hashing and vice versa. But the question is what is really the trade-off and our work sort of give the the close to optimal trade-off curve between size and verification action. Okay. So now let's try to understand at least at the very very high level how XMS works. Uh so the high level paradigm is that we take a one time signature scheme which is a signature scheme but you are allowed to sign only once. So if you sign twice you leak parts of your secret key or even the entire secret key. So never sign twice. Uh and then

you take that and you turn it into what I would call a synchronized many time signature scheme or like stateful many time signature scheme. This just the same as a standard signature scheme, but you sign with respect to slots and you are only allowed to sign once per slot. Again, if you sign twice per slot, you reveal parts of your secret key. You should not do that. Okay. So it's almost a signature scheme but we have this sort of restriction on how we how often we can sign with respect to one slot and it turns out that for proof of stake this is actually not a big restriction. So for other applications it may be a problem but for us we already have this this these measures in place that ensure that validators don't sign twice uh in in uh one slot. So uh it's it's kind of

the right fit for us. Okay. So how do we do that from time signing too many times signing let's say we have a parameter L think of 2 to the 32 some very large number which is the maximum number of slots that we can support and then what do we do we take uh L one-time public key secret key pairs so for every slot we generate one uh one-time key pair and then we put the public keys in a mer tree and the root will be our long-term public key now these one-time secret keys will be our secret And of course, you can generate them from a short PRF seed if you don't want to store all of them. Now, how do we sign? Well, if we sign, we need to uh output the one-time

public key of that slot. Remember, we signed with respect to a slot. And then we need to convince the verifier that this one time public key is consistent with our long-term public key. So, we include the the mer path and we also include the onetime signature that we computed using the corresponding one time key because only signed once per slot. It means we use every one time secret key only once. That's already a good sign. How do we verify? Well, we check just the Merkel path and we check the one time signature. And it turns out that uh in the actual constructions, you can get rid of this one time public key here in signature because you can recomputee it from the one time signature.

Okay, so that's how you go from one time signing to many time signing just using merries. Uh that's actually quite simple. Now, how do you do one-time signatures? And here again, I want to simplify a few things, but the basic idea is to use hash chains. And in this slide, I will use four chains with length four. In practice, think more like 60 chains of length eight or like something much larger. And what do we do? We sample random bit strings, let's say, or random in the case of Poseidon, random vectors of field elements. It doesn't really matter. uh S1 to SV. So in this case for each chain one random bit string and then we put that in our secret key.

That's our one time secret key just random stuff. And then for each of these we compute a hash chain of the uh of the corresponding length. So here this will be a hash chain of length four. So we take this we hash it we take the result we hash it again and so on. And the ends the end points of these chains will be our one time public key. And now the nice so the first observation we should make is we can go from the secret key to the public key but we can never go from the public key back to the secret key because inverting hash functions is a hard problem. Uh so that's a good sign already. Um okay now how do we sign a message? So that that's how our keys look like. But

how do we sign a message? For that we have to know that there's an encoding function and this encoding function will be uh central to one of the sessions. Um in this workshop and that encoding function takes a message and some randomness and it outputs positions in these chains. So let's take an example. The output could be 1 2 3 0. Okay. And what does that mean? It means when we compose our signature we include for the first chain this element because it has index one for the second chain this element for the third chain this element and for the fourth chain this element.

So our signature will have one element from each hash chain and the encoding determines which element. Now let's look at the signature size. The signature size is just V which is number of chains times the size of a hash. So if we reduce number of chains we reduce signature size. But we cannot arbitrarily reduce number of chains that will in at some point be insecure. So roughly let's say the V times log W should be 128 or something. So if you reduce uh the number of chains you need to make the chains longer.

Okay. What is the work or the amount of hashing? Remember we want to minimize verification hashing. Well the signer and the verifier together they need to walk each chain once. So the signer will take its secret key and it will walk to that position and then the verifier will take this this element from the signature and continue to walk and then at some point compare it to the public key. So together they they walk essentially this whole matrix once. So the work is V * W. Our goal is really to move most of the work to the signer because remember we proved the verification circuit. The verifier should do only a few hashes.

Okay. Another thing that I want to mention without going into detail is the whole security of this really relies on properties of this encoding and they are incomparability which is combinatorial property and target collision resistance. Uh and if you have that then this whole approach is secure. Okay. So uh let's put things together. This is sort of the big picture of of XMSS. We have these u the secret key is just these starting points of all the chains. So all our one time secret keys then we do the hash chains we get these onetime public keys we put them together in a mer tree to get the full public key okay and uh again you can sort of derive the secret key just it's just random

stuff right you can derive that from a short PRF key and then the signature will be just a few elements in the chains and a vertical path okay so uh that brings me to my last slide uh what is the current status of all of this and what are the open questions that we want to tackle in this in this workshop. uh so the status is leanig as it is with these three documents and the prototype implementation I would say it's quite stable but there is room for improvement and we should really use uh the workshop to make improvements. Uh so the first sort of open problem or like thing that we need to discuss is uh there's a trade-off between the secret key size

and the signing time. So I as I said the secret key could just be this small PRF key that then expands into all the one-time secret keys. But the question is what do I do with the merket tree? So I have two options either I store the entire mer tree which is very very large. Uh but then I have a very fast signing algorithm and this is what currently the rust implementation does. So signing is very fast. you just need to look up the Merkel path but uh you have a large secret key because you have the tree inside of it. The other option is to throw away the tree after key generation and then just uh regenerate it on the fly. Could of course do that but that will take time. So now this the

keys are small but the question is really when do you regenerate the key? How much of it do you regenerate? how should even the API of the signature scheme look like so that that clients can really uh do that in a flexible but still efficient way. And the second uh direction where we will also have a session is uh to look closer at these encodings and essentially in in all our previous works we we already looked at these encodings uh but I think we forgot one thing. So uh remember the encoding takes the message and some randomness and it outputs positions in the chain and both the signer and the verifier need to run this algorithm. So I think the encoding has two parts. It has the code which is sort of the the set of outputs that it

can produce and this determines how much hashing the verifier would do in the hash chains. I think there we are already quite good. So the current encoding that we have is very good with respect to that. We even have some sort of lower bound and close to optimal. The problem is that the verifier also needs to run this actual encoding algorithm and there we currently use some big integer arithmetic and modulo and this is actually not that uh snark friendly. So uh actually the the bottleneck is right now not the hashes and the chains but the the running this encoding algorithm and uh there's a new proposal for new encoding algorithm by Dimmitri and and Goty uh and uh we already

started to evaluate this whether it's efficient enough whether it's secure but I think there's more work to be done to to really get confidence in this new encoding and update everything and then I think as sort of the baseline I want to come back So this is hashbased signatures. Of course if the hash function is broken then everything is broken. So I think one of the most important if not the most important thing for us is to understand it because I don't secure and I think there are people in this room who have worked a lot on this and I think we should continue working on this and yeah that's that's all I want to say. Thank you.

[applause] This might be actually a stupid question but for the first thing can you use like vector commitment rather than like >> I mean a mercury tree is a vector >> yeah with like why like rather use like binaries like >> okay I'm not aware of a hashbased vector commitment that is better than mercury >> I think they looked at nonbinary versions I I think they were they were looking non-binary versions and essentially binary gives you optimality to some degree and uh speaking of the first topic there it's also yeah we didn't discuss it much but

uh there is also a recent result it's not theoretical result but more of like engineering solution is that there is this three traversal algorithm so essentially like when you do the first signature you can store some intermediate notes and then For the next one, you reuse the old ones, but you recut the very little and then nice improvement there. There was this algorithm was known for some time, but they what they also did is when you have um some disturbance in your system and so you lost some part of the state, but you know where you need to send.

Again this is Ethereum idea of like okay we know this is the epoch we are signing in but our internal this state that we are holding is broken so they also improved this like recovery algorithm that also much improved the efficiency so I think the binary version is nice and then uh applying some tree reversal will also give a good tradeoff between the storage and the key sizes. >> Yeah. So I guess one thing to add to the key traversal thing is that if you if you do that I mean that's one option but then you really make your scheme stateful stateful whereas right now we just need the index right right now you just the current API of the scheme is

not stateful it just says okay the the ser takes as input also the slot and the party or the client that calls this code needs to make sure that it doesn't call it twice. But now if you make it really uh with a pre- traversal you make it stateful stateful so the client would have this overhead of managing the state but I guess no matter what we do to solve this issue we will have that. >> Yes but again with with uh this state that you're storing this extra information about the the tree is not security concern it's efficiency concern. Yeah. So if if that state is mismanaged is fine >> if you still know which index you're

assigning. >> Um to expand on your uh caching basically uh this has been used and optimized for machine learning because basically when you do your um uh uh your deep learning uh training uh you create a tree and then you need to compute back uh the values. But there is a trade-off between memory and performance. And so uh sometimes you cache stuff so that you don't recmp compute and over time you uh limit that and I think the storage you can cache a logarithmic amount uh compared to all the total and then you have a nice asotic uh boundary on the total comput that you have to do again.

Sorry, stupid question, but uh are you like for the first part the PRS and the ash you use for things you can change the ash, right? You can like for the PRF you can use a different hash from what you're doing for the rest of >> right so for the PRF you can just use SH whatever or BL because the verifier will not see that right we don't actually it's even in the in the documents like in the that we wrote we don't even do that we just have it in the in the code just take any PF because the verifier will not see it doesn't have to be snot friendly whatever >> okay just just make sure >> it's technically can be uniform and you have to store all >> correct Can you say more about the big integer

arithmetic? Where where does it uh come from? >> Yeah. So, okay. So, how does this encoding work like internally? Let's say uh well, let me try to give a simplified explanation. So, you have a you take your message, you take your randomness and some other stuff and you hash it with uh let's say Prooseidon now you get a vector of field elements right uh the problem is that we now want these positions in chains right so the output should really be in 0 to b minus one and that raised to uh sorry 0 to w minus one and that raised to b so it has a very specific structure that is

not really compatible with this field so currently what we do is we take these field elements we look at them as one big integer. We look at these these vectors of positions in chains as being elements in hyper cube and then we sort of map to a specific layer of the hyper cube to get security and during that mapping we need to take that big integer that comes from the field elements and we need to uh reduce it modulo the size of these layers and then we have a bjection that encodes into these layers. So this modulo step is I guess the most expensive one.

Thanks. >> But there will be more context on this in the session on the encodings. >> Yeah. So thank you for your great talk and is it safe to sign uh multiple message with same parameter uh if provided that those signatures are revealed at the same moment same time? >> No. I I mean no. So, [clears throat] so if you sign twice, it could be that you leak your entire secret key and at that point people could from that moment on you could uh just sign anything.

Um [clears throat] kind of sidetracking here um but I understand that this uh lead scheme is for consensus signing blocks stuff. Uh I wonder if you have any any suggestions or or direction on say PTP authentication encryption. Um for example right now we're using set P. I guess that's not proof. I guess I think for this without I haven't thought too much about it but for this I would follow NIST I guess because this seems like a a thing that has requirements that are more standard than what we have in the consensus layer.

Yeah, the other thought that I have for the P2P network is that we can cheat a little bit and have it not be post quantum secure for a few years because we'll probably deploy the post authority before actual attacks happen. If a quantum computer does happen then, you know, the worst they can do is just you know decrypt these like ephemeral ped connections and there's no value there. I have one last question actually for me how so um my understanding is that you wrote uh the lit paper and that you were finishing your PhD and then you got hired by blockstream. Is blockstream looking to into postquantum signatures for Bitcoin?

Yes. Well, also looking at the postquantum, the thing is the core difference is that stateful is less appealing because here we have proof of stake where we have this specific uh timestamps kind of where you can do that. Hashbased is is still interesting and for example again there are a lot of trade-offs you can do uh with things. Uh there is still a limit on the number of signatures you can sign with any hashbased signature. But like for N this was uh you have to be able to sign up to 2 to the 64 probably for the this use cases you can sign you can have this [clears throat] barrier lower. So this will also

drastically reduce the size of a stateless signature. And then the next thing is that probably again uh we're not that heavy on the verifier hashing because why we were focusing here on the verifier hashing is that we're further than aggregating this and we will want to this step to be easy here this uh ratio between the computation and the size is already lower than I think we compare this with and uh if we you kind of transfer some group operations to hash operations of SHA. Therefore, hashbased the ratio is already smaller even yeah with standard practices. So still going there also

probably we'll take a look at latest based but hashbased is specifically again interesting because again uh sh 256 for example is already used. So this is the same assumption you kind of rely you don't introduce anything else and this is also an interesting topic. >> Perfect. Thank you. Thanks Benex. [applause] >> Okay. Next up we have Tom and Emil who will be talking about