Post Quantum Ethereum and its Signature Schemes [EN] [Ethereum Protocol Day]

Transcript

So uh I'm from Nyx Foundation and we are the research organization of Ethereum and we have some grants from EF and sected as a pharaoh at TRDR or Fish Capital and yeah there's some research and development and uh uh our team member most of our team members lives together uh at the Nick's house. Uh it's uh so close to the University of Tokyo

and uh the house is public to everyone. So if you ever come to Japan, uh you can visit. Yeah. Let's take a dinner. So uh uh this is the agenda. First uh I'm going to speak uh link consensus and the second uh I'm going to speak of hashbased signatures and at last uh I'm going to introduce the e- health paper

on the uh ecoding methods of hash based functions hashbased signatures Sorry. So the first link consensus uh what is a link ethereum? So ling ethereum was announced by just indirect last month and it's the next decade vision for Ethereum.

So it's so crucial important to the future of Ethereum and lean Ethereum consists of three parts uh lean execution lean consensus and lean data. uh Ethereum consists of three parts uh uh that that is uh uh execution layer, consensus layer, data layer and I'm going to focus on the the consensus and the cryptography part.

Yeah. Uh so like other crucial concepts are on the block production and staking but uh I'm going to focus on the cryptography uh the hashbased graph cryptography is expected to utilize the all layer like consensus layer data layer execution layer. So it becomes increasingly crucial for the Ethereum.

So I'm going to introduce the I read the originalist. Imagine the leest cryptographic brick the hash function single-handedly powering the Yawa. So I'm going to focusing on the consensus layer but it's also important to the data layer and execution layer. So uh I'm going to uh explain about the hashb signatures as the second section.

uh so as much as possible I'm going to explain uh it as simple with diagrams. So in the first time uh in the first phase uh there's a lot of post content signatures uh like uh hashbased signatures latis based signatures multibar eight signature call based signature and so on and I'm going to focus on the hashbased signature but there's a lot of other schemes

On the other hand, elliptical based signature and RSA based signatures are not postal contact. So, ECDSA is one of the uh most uh used signature in blockchain but it's not poster. So the Ethereum's execution layer uses ECDSA but it's not post content. So uh we should uh replace it with post content signatures and B signature uh used in the consensus layer but uh

it's it's to replace with poster and I'm going to uh speak of history of hashbased signatures. Uh the first uh lampot proposed the first hashbased signature. It is Lampo signature in 1979 and in the same year uh Winter's one time signature and ML signature scheme were proposed

and uh few few years later uh 2011 XMSSS was proposed and some there's some updates. So essentially there's four models. So I'm going to uh let's see the comparison of models the lamp signature and what's signature uh one time signature it means uh

you can sign the uh you can sign one time only one time with the same private key. So uh seemingly it's not useful. So it's uh kind of weird than other cryptographic scheme. Then uh XMSS and swings plus were proposed.

they can be used multiple times. So uh as the other signature scheme uh you can use multiple time with one private key but uh swing express is state rest hashbased signature but xmss is a statehood signature scheme. It means uh user should manage the uh a lot of private keys. So uh and uh you should it uh uh per per one private

key. So you should have a lot of private keys and you can sign with one private key over and over again. So in consensus uh in the consensus uh hashb signatures is the most promising signature candidate and specifically XMSS is the leading candidate.

Why hashbased? There's a lot of postquantum signature. Uh hashbased signature is less assumptions than other signature schemes because uh signature based signature and hashbased signature only depends on the uh safety of hash function. So uh it's so simple. And the next most promising approach latis based is still under analysis.

Yeah. So uh personally I I like the latis base and other signature scheme using mathematics because I measured in mathematics but yeah if you take is prioritized the hashbased and why xmss uh suffix is more looks more useful because suffix is stateless but uh you have prioritized the x ands because uh baras should be able to sign multiple times in consensus area

it's obvious so lampo signature and what signature uh not useful and bal signatures don't necessar have to be stateless because uh Sphinx is more uh the usual uh user uh can use the sphinus to the for the user signature but uh bar works in the uh computations server. So stateful signatures also works

and uh basic pro of uh signing uh the first uh key generation, second signature generation and third signature verification. So uh uh I'll introduce some schemes with this basic flow. So the first secret key is generated. It can be regarded as a signing key in the context of sign signature.

And the next private key is generated from the secret key and it can be regarded as a verification key. And then next phase uh signature generation uh you you have the row message and you can encode the row message to the encoded message. Then you can get the signature with the secret key and uh I named the process index derivation but uh I'll explain later

and the in the third phase verifier can verify that that the signature is correct with raw message and signature and public key. So uh let's take a look at lampo signature. Uh this is the first hashbased signature and the secret key is a lot of random variables and it's so simple scheme but it's the most uh initial scheme. So we should understand

the first uh the uh secret key is generated at random. The numbers are random and but it's toy example. So the number has no meaning and then public key is generated by with hash functions uh of each nodes and the in the same signature generation the low message there's row message and uh you can get the encoded message.

It's just bit conversion. The arbitrary data can be regarded as a binary and you can get the signature. Uh this is the index variation. It's a little bit uh weird but the encoded message one means uh the uh it corresponds to the 42 then the first value is 42 and the zero means 21 then the second uh data is 21.

So in this way you can get the signature. The uh concept of index variation cannot be changed as other hashb signatures and you can verify with raw message signature and public key. But uh I I'll skip the detail of verification.

Next uh let's take a look at what's press signature. It's the update version of lampo signature and uh it can be treated as a general generalization of lambo signature and uh actually it's uh the building block of xmss the signature uh in the v signature the secret key is generated it randomly but it's uh the size is less than level signature in this toy example

and uh in the k generation uh you should calculate a lot of hash functions. So the 33 is equal uh take to be the hash of 91. Uh in this way you can get a lot of values like this like this like this. So you can get a lot of values with repetition of hash function.

And finally you should calculate the public key from the sum of the top layer nodes like this. 99 is equal to hash of 7 plus 82 plus 35 plus like that. And in signature sorry uh yeah signature generation there's raw message and you can get the encoded message but it's a little bit different from the

version of lampo signature. It's encoded as a values from four 0 to four in this case and the uh same process you can get the signature like that. So the three means the 14. So the first value is 40. one means the uh it means 19 then the second value is 19. So you can get the signature value like that and then

you can verify with row message and signature and public key. Okay, this is the uh last scheme and XMss this is the uh state for hashb signature and it's bundles of what's signature and uh it's like uh it is a macro tree of bundles of what signature so I will explain A lot of process is uh almost the same

as what signature. Uh first uh secret key is generated at random and then you can calculate uh to apply applying art of hash functions over and over again and you can get the hash of some or that top layer or nose and uh you should calculate the same same process like this.

So you can get a lot of uh public keyish variable and then you can calculate the uh uh sum of uh two page keyish values. Then finally you can get the uh root of macro tree that is uh uh generated by a lot of hashb hash function uh calculation and in the signature generation it's

completely the same as what signature low message and encoded message and then you can get the signature with that index derivation. The process is totally the same and uh verifier can verify with that uh the with raw message signature and uh public key and some additional information. So it's a little bit

different from one time like lampot and ws but uh in this way you can get the uh stateful hashb signatures it enables us to sign multiple times. Okay. So, uh this is the final section uh at the top of hyper cube was uh proposed by ex cryptographer teams uh two months ago

and it's uh on the encoding function. So uh in the what signature and in the XMSS uh you can get get the signature like this uh 31 2 one2 uh and uh we are going to focus on the uh verification cost. uh verifier should calculate hash function over and over again like uh uh in this column uh verifier should calculate the hash function three times 14 to 51 51 to 53 and uh the first colum uh verifier

should calculate uh hash function one times then the total cost is Uh 9 times. Yes, the verification cost is nine and the another in the another message it uh uh encoded like this. then the verification cost is the 14

and uh in this last message the verification cost is five. So uh yeah then uh we can get some a certain hypothesis. So would it be better to cluster the encoded nodes closer to the top? Because uh the encoded nodes uh uh closer to the top then the hash function calculation is less than the bottom one.

The paper's core concept is uh this this idea. So there's three methods and but the all of these share the same basic this idea and uh of course uh the encoding should be keep it secure and the uh more likely to be encoded in the upper layers And uh this is the one of the method proposed method top single layer. Uh

it's the uses the fixed distance from the top top layer. Uh so in this paper uh parameters are proposed to ensure the uh encod bars to be secure and uh we are developing a formal verification of topple single layer with lefo. So uh I spoke this topic. Okay, that's it. Sh.

[Music] >> Uh why XMSS versus like something like modular designs? because I think if you're doing the XMSS if you're going to verify the hashes for the signatures uh it will add up quite significantly for the chain by uh a constant factor or depending on the security you want. If the string length increases, the number of hashing required will also increase. And so if you have a to compute like some of a mer tree for each hashes um it will probably scale I guess like and lock in.

>> Uh okay. you mean uh uh latis space uh so the how >> for the xmss >> xs >> you have to choose you have to choose like a bunch of so you're essentially encoding the order based on the hashing functions >> so wouldn't it be super costly because it it encodes a kind of an polomial time >> for for verification versus like a constant time which is uh used right now.

Uh uh yeah, of course it's the bunch of uh calculation of hash functions is so it takes a lot of costs but uh it's the security assumptions is less than latis based and uh uh originally it we must uh uh get the secure hash function and then uh if we uh introduce the hashbased signature then the additional

there's no additional assumption but uh uh in latisbased signature uh we should introduce some mathematical assumptions like lwe or sis or something like that. So, uh it's the EF take is it? Okay. Uh can you explain a little bit more uh about how you get the 61 12 59 is it how are the >> 6 >> 61 you mentioned it's hash what data are

you hashing together >> ah okay uh in the verific 12 59 like the same layer as 99 there. We can see how 99 just uh add them together and you get but what about 61? >> Ah okay the uh the architecture is completely same. >> Yeah there are multiple of them right? >> Yeah yeah yeah the yeah that's it.

Okay. Um a very simple question I would like to ask you is that uh except the key generation what is the main function of the link to Ethereum for the whole for your whole presentation is the main functions >> um the hashb main functions of hashbased signatures right uh yeah it's uh Uh yeah, it's the less assumption signature scheme. It's so uh essential to the Ethereum but

the function uh to compare >> maybe I can add you at your telegram and ask questions. >> Ah yeah okay let's discuss later. So uh uh my question is how how XMS or hashes uh signature handle the the the signature aggregation. >> Ah okay nice question. Thank you. Yeah uh in uh current ERM consensus uh B signatures are used to uh sign and aggregate. that uh uh

uh to to the straightforward way a xmss cannot be aggregated. So uh uh uh in the ethereum the aggregation uh will be done with gkm uh the hashbased gkm so it can be aggregated. Thank you. >> Thank you. >> So, am I understanding this correctly?

You guys are building some kind of Pentagon code scheme. >> Oh, sorry. >> You have this set of numbers here, right? >> Yeah. And you get to choose from each you have >> uh the meaning of five or >> orary.

Uh uh this is just toy example and uh you this is the parameter. So you can choose the uh arbitrary value >> from from the uh previous page I I can I can understand it uh when I see zeros and ones right that's binary >> ah ah that this code ah yeah uh so the arbitrary value can be regarded as uh binary code or uh what to say uh 10th code or 16 code or something like that. In this case the

uh it can be regarded as four for four uh four base value >> uh I'm not sure that how many is index arbitrary number it can be zero or ones in this case it's up to what >> yeah the the arbitary data can be regarded zero or one sequence. So uh in the same way arbitary data can be regarded as uh zero to four values

>> or yeah anything is okay. >> Ah this is just uh toy example. Oh, the uh I