The Future of zkVMs and Post-Quantum Signatures in Ethereum

Transcript

would like to invite our next speaker, Mr. Diego Kingstone. Mr. Kingston, the floor is yours. [Music] Uh, excuse me. I am now going to give the presentation in in English, but I hope that sometime I will be able to do it uh in Japanese. So my talk is going to be about the future of CKVMs

and especially about postquantum signatures in Ethereum which is one of the current threats uh we are facing and so I wanted to talk a little bit about some design choices or tradeoffs and some of the recent uh developments that we have seen. So this is a bit the outline of my talk. I am going to first mention some of last year's advances then comment a little bit on the quantum threat why this is important for uh Ethereum then a little bit about the different like signature candidates uh also then talk a little bit about these multilinear versus univariat

starks so uh these last few years there was a discussion between using like snarks or starks It now seems that this discussion is uh settled. Um and then we have to choose maybe which is the right way to encode them with polomials. Maybe we can have both. And then some design choices. And finally, a little bit about why uh build a different VM especially for what is signature aggregation. What advantages this can give us and um I'll finish with some a short summary of what we've we have been talking.

So some of last year's advances. Uh first we saw that uh we we have like very powerful transparent validity proofs that is proof systems that don't rely on a trusted setup such as uh growth 16 or KCG plunk. Okay. And this has like several advantages and we don't have this um point of failure. Uh so this is something interesting. Um then we saw that uh we have general purpose CKVM that allow us to prove code written in Rust. Um and these have become like really powerful. Uh in fact uh it's been

shown that uh we can prove over 200,000 uh posidon two hashes per second or even more. That depends on your hardware. But this shows that we can prove uh enough hashes for what is uh practically meaningful for Ethereum. Then we saw uh the emergence of realtime proving. Right now I think we have three or four uh CKVMs that can do this and we can expect that they will get better and better besides uh power consumption has been going consistently down and so perhaps it will be possible for us to prove uh things directly from from home and not

from a GPU farm. Um there has been a lot of developments related to hardware acceleration. Uh Nvidia has also um added in its library uh the instructions for for example Poseidon 2 and other primitives that are useful for uh proof systems. We have seen uh a lot of better new lookup arguments especially logup and GKR. We also have like new ways of uh arithmetization and that gives us like more flexibility to uh describe our BPM and then we have also more precise specifications.

So what about the the quantum thread? The idea is that uh quantum computers uh have an efficient algorithm that allows us to break uh the cryptographic uh problem that elliptic curves rely on which is the discrete log. Okay. And basically this breaks all the cryptography EC cryptography that Ethereum uses particularly BLS signatures uh which are used in the consensus. Um and this is something that is very unfortunate because these signatures uh are really powerful because we have very fast aggregation

and um the verification is rather efficient and besides these signatures are very small uh so it's very easy to to communicate them between the peers. So um this also breaks all the elliptic curve based narks for example corox 16 which is again uh very the proofs are very small uh and so we will have to handle like uh larger um proofs. Um on the other hand the security of hash functions is reduced.

Okay, but this is not as catastrophic as the case of elliptic curves. And we can always restore this by working with larger digests. That is to say, if we double the digest, we get back to the security level we had. So why is this important for Ethereum? First, because if this appears, then this can break completely a great part of the cryptography we're working on. But even though this could never happen, I think it's always good to have uh Ethereum working with cryptography that is as robust as possible because that uh makes us resilient against any kind of of threats. Uh besides we know that uh

Ethereum has already uh accepted ZK as the best strategy for scaling Ethereum. uh zigg is really cheap and fast right now. Um so it doesn't make sense for to have optimistic rollups because the cost of adding ZK is negligible and besides um having CK uh greatly simplifies the whole protocol because we can essentially uh verify just these proofs and then just update the results because we know they are correct. Okay. So the execution is basically uh offloaded.

So the thing is they are going to break our signatures uh and so we have to replace them for something else. So there are a couple of things we we would like to have. Um first of course we want them to be postquantum secure. Uh then we want as minimal and as robust security assumptions. So for example, hash functions are among the best known cryptographic primitives. So they are a natural candidate. Uh there are other primitives that uh could also be candidates but maybe they have like uh weaker security assumptions or or

stronger in this case. Then we would like to have like fast proving because that way we can um use CK to bundle and and prove lots of things. We want small proof sizes because that way we can uh communicate them in in the consensus very easily. Uh we would also like the proving to be done in consumer grade uh devices because that increases the decentralization and especially we would like no trusted setups and uh no need to update the keys uh during uh lifetime.

So there are a couple of uh postquantum signature candidates. We have X MSS which is hashbased but this is uh a stateful uh signature scheme. Then we have Falcon for example that works over latises. Uh crystal deliththium also works over latises that is for example something that uh f uses uh and also sphinx which is also hashbased but uh stateless. So uh the idea is that uh these uh signatures aren't aggregable but what we can do is use ZK to take a bunch of signatures and generate a proof that we

verify them and then just by verifying that proof it is as if we had verified all the signatures. Okay. And that way we can aggregate. The only problem is that okay this solves the problem partially but doesn't have this nice property that the VLS signature aggregation had which uh was insensitive to the order of the signatures. So basically an idea of how XMss works because this could be the the best candidate. This is because it's based on hash functions and we know that we can prove hashes with VMs really fast. So the idea is that uh the signer has a

long sequence of one-time public keys and uh he builds a miracle tree with that and in order to sign he's going to use one secret key and to show the public key uh is contained in the Miracle tree. So we give like the public key and an authentication path. Each public key is related to a secret key by performing a number of hashes and the idea is we are going to encode the message using something called incomparable encodings. Then each chunk is going to be interpreted as a number and that is the number of times we will have to hash the uh secret key. Okay.

And then the idea is that the verifier can check that this is correct by hashing the remaining number of times until he gets to the public key. Uh, of course, when we are doing aggregation and everything, we have to be careful about using the hash function for signing and then for simulating uh the random oracle. Uh, if you want, you can check this this paper that uh explains like all the implementation and all the subtleties. It's really interesting. So now we have to see okay we are going to aggregate using these um starks and so we have like basically two flavors in one case we use ordinary polomials. The

idea is that in general this is what for example SP1 risk zero uh ZISK we're using or are using but basically the idea is we want to prove that the computation is correct and this is reduced to a claim about certain polomial equations that have to be enforced over some table. Um in this case we have uh certain freedom to choose uh the finite field where we are going to work on. Um but we need it to be something called FFT friendly and then the idea is basically we get each column of this trace table. We interpolate it uh using

the FFT. We commit to each of these columns. And then basically what we do is we plug in these polomials inside the constraints that we want to enforce. And then what we do is we divide by a polomial saying where the constraints should be enforced. Okay. And to show that the constraints are then enforced, we do uh a lowderee testing. Okay. And this is the case of of fry. and we generate a proof containing u several merkel trees and everything. So this is a very uh fast and efficient construction but um in general this tends to yield um larger proof sizes because we have to interpolate uh each

column separately and we would like perhaps something a bit more more efficient. On the other hand, multilinear starks uh in general offer more chances for efficient arithmetizations. For example, there are um ones using R1Cs but also air which is one of the candidates uh for a special DM or M3. So you have like a lot more freedom. We also have a bit more freedom regarding uh the finite field. The idea is here we use multivariable polomials and what we do is we get all the trace and we interpolate it just as one

polomial not every column and then the idea is we are going to use this efficient sum check protocol to show that the constraints are enforced and essentially what the sum check does is transforms this claim to an evaluation of this polomial at a random point. Okay. And then what we can do is use a PCS to show that um the evaluation is correct. Okay. This is a standard technique uh corresponding to the what's called the BCS compiler.

So um it's interesting that we can use two techniques combined to yield very fast provers and at the same time uh small proof sizes. Spartan is particularly efficient. So in general what we want to prove is something like the product of uh a matrix times a vector is equal to something. And so the idea is you can split it as uh a claim over some random linear combination over the columns and then this random linear combination over the rows. And this uh is particularly efficient. Then wear is uh a bit more

efficient than fry because it works over a variant of read Solomon codes that are constrained. And so the idea is that we impose over the witness some some conditions and the idea is that we're again uses a partial sum check and then does some folding and reduces uh all the claims and this way we we get smaller proofs than in the case of univariats. uh something that they released a few days ago was also bin 64 that is using uh a different polomial commitment scheme but has been used to prove aggregation of XM SS signatures and it shows to be very efficient even in CPU.

So it's interesting that we have a lot of research and implementations relying on different primitives. So if I had to sum up some of the differences between um multilinear and univariat in general multilinear have gotten like way popular because of like some advantages for example uh in in the case of the sum check we don't have to calculate like inverses or anything in general with multilinears we can handle better sparsity patterns and so not have to pay for uh the zeros contain the matrix we don't need to interpolate using the FFT and in general because we

can use where we can have uh shorter proofs and we also have like more options regarding uh efficient arithmetization or even the use of binary fields as for the VMs the idea is that of course we have different choices regarding the instruction set architecture whether it's customized or risk Five whether we will have like one table or several tables. what finite field koala bear baby bear the hash function ketchup or the less battle tested Poseidon 2 whether we are going to use circuits or lookup based arguments uh for example in the case of jolt that's very easy to to audit the

arithmetization the memory argument the PCS the good thing is that if we do it like very modular then we can easily switch uh one component for the other where we are going to have a recursive prover or a streaming prover to keep a memory bounded. But in the end, I think we will need more than just one design, especially when it comes to execution to avoid any catastrophic bugs because these general purpose VMs tend to have like very large and complex code bases.

So why why build a separate VM for signature aggregation? Uh well, this is going to play an important role in the consensus and so we would like to have perhaps a simpler design that just handles the necessary logic for verifying and aggregating uh the signatures and ensures small proofs. Uh it's easier to audit. It's easier perhaps to have multiple implementations in different languages. uh we can also have a design that can be used together with general purpose VM.

So I think that uh it's worthwhile because we have like very tight constraints on what we would like on the signatures and then it's easier to reason and audit and all that. So as a summary, quantum computers are here and they could break easy cryptography. So we need new primitives. We can have this by using snarks to aggregate these new signatures. And I think that multiar snarks are a very good candidate because they handle very well sparsity patterns and we have efficient algorithms to prove uh memory accesses and all that. A simple VM can be really really helpful especially if we want to prove in weak

devices and not compromise decentralization. If you want uh to continue talking I am here. Thanks a lot for your attention. >> Thank you very much.