Episode 394 - leanVM, a Custom VM for Signature Aggregation

Transcript

Welcome to Zero Knowledge. I'm your host, Anna Rose. In this podcast [music] 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 [music] online. This week in our fourth episode of our six-part mini-series on Lean Ethereum, Nico dives into the topic of Lean VM and Lean spec. He is joined by Toma Courtois, PQ lead at the Ethereum Foundation and Emil, researcher at the Ethereum Foundation. For these special episodes, we have Nico as our host. We are also releasing this in video form over on our

YouTube channel. Links are in the show notes in case you want to check it out over there, and be sure to subscribe to the channel while you're at it. In this episode, the conversation focuses on the design and implementation of Lean VM, the minimal ZK VM built specifically for post-quantum signature aggregation on Ethereum's consensus layer. Nico, Toma, and Emil explore why the team chose a VM over a fixed circuit, how Lean VM draws inspiration from Cairo, and what it means to enshrine such a system into Ethereum consensus. The episode examines how the team is making post-quantum SNARKs performance simple and secure enough for Ethereum's core protocol.

Hope you will watch or listen along to this and other episodes in our mini-series. And yeah, let us know what you think. Now, 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 hope to see you there. Second, ZK Mesh Plus, our paid subscription tier, is rolling. We have already released a few bonus clips from the show, as well as some of our exclusive research reports, like the State of ZK report and its addendums. If you want access, please join the paid tier on ZK Mesh Plus.

Third, if you're looking for other ways to support the show, we have donation accounts visible in the footer of our website. So, if you choose to do so, thank you in advance. That's all for now. Links are in the show notes, and here's Nico's interview with Toma and Emil. Today, I'm here with Toma Courtois, researcher and PQ team lead at the Ethereum Foundation, and Emil, also researcher at the Ethereum Foundation. This is episode four of our mini-series on the Lean Ethereum upgrade, and this one is dedicated to the implementation of post-quantum SNARKs and the design of Lean VM.

Hello, Toma. Welcome to the show. Hello, Nico. Thanks for having us. Pleasure, and hello, Emil. Hi, Nico. Thank you very much for for having us. So, you know, before we get started on like Lean Ethereum and all these things, you guys are both first-time guests. Uh so, I'm curious to hear a bit more about like your journey into ZK and where you are now and what you've been working on. Yeah, I can start. So, before doing all this, I have like engineering background. I did a engineering school, and then I did a PhD in applied maths. It has nothing to do with crypto. It was about physics and implementing some physics equation in inside a code and solving some physics

problem. >> [snorts] >> And then I I came to the crypto industry, worked for a small startup, and then a bit closer to StarkWare. Um this is where I discovered Cairo and the world around like ZK and ZK VM. Then I I joined Kakarot, um which was like ZK EVM company, and then just after like the talk of Justin at Devcon Bangkok about Lean um I joined the Ethereum Foundation to work full-time on Lean Ethereum and everything related to crypto.

Nice. How about you, Emil? Um I started uh um ZK with an internship at Linea, the L2, like 3 years ago, when I was still in in an engineering school, and um I really started to read papers and research um about a year ago, and then I first uh worked with some some grants uh on Lean Ethereum, and recently I joined officially the EF to work fully on this project. Nice, amazing. So, probably now is a good time to get talking about the project. Uh

I'll quickly recap where we are with our series. Um so far, we've been talking about the Lean Ethereum upgrades. We know that the consensus layer is moving to being post-quantum secure. Uh this requires post-quantum multi signatures, and the solution chosen was to use hash-based signatures and aggregate them using a SNARK. Um the specific SNARK is a hash-based SNARK. We discussed this on the previous episode with Giacomo and Antonio, and we mentioned that it has sort of its own arithmetization, its own VM that's called Lean VM.

And this is why I have you guys here today cuz you did you both did a lot of the implementation and the design of uh Lean VM. So, before we get into the weeds of Lean VM, the first question I have is like, why why choose a VM? Why not like have a circuit that does like signature aggregation and that's it? I think there are many two advantages. The first one is that in the network, you want to be able to aggregate a certain number of signatures, and this number may vary, not always a perfect power of two or may depends.

And you may then want to recursively aggregate those previously aggregated signatures. So, we need recursion. And once you have aggregated, let's say two previously previously aggregated signatures, you may want to add like you are validator, you just receive received some final XMSS, some final signature, and you want to add it to your aggregated uh like to your final aggregated signature. And so, you may want to add some small number of remaining XMSS in the end. And if you have one circuit, it means that the sizes are fixed in advance. And so,

you are only able to aggregate, let's say, 1,000 XMSS and to do two-to-one recursion. It could work in the sense that you can every like you can always reduce your aggregations to a uh a fixed number of steps like 1,000 1,000 XMSS, and then you apply recursion until everything is aggregated. But, the power of the VM is that the number of signatures that you aggregate and the number of recursion that you do in one step is variable.

Mhm. And uh so, it gives you more more flexibility on this part. And second, it's easier to reuse the infrastructure that you've built if it's a VM. For instance, if you want to cuz for now, we focus on the consensus part of Ethereum, but the execution part will obviously also also move to post-quantum. And for instance, uh if you want to aggregate Sphinx-like signatures, you with Lean VM, you could totally do it. And it's the the changes need needed to make it work would be very minimal.

By the way, just to clarify, XMSS here is uh the signature scheme that is also being called Lean Sig. Yes. Okay, cool. So, the the successor to BLS, let's say. Exactly. And if I may add something else also like um we have right now discussion with some folks uh around this debate of ZK VM versus like circuit because a lot of people are working on how to make maybe some compiler efforts to render like a circuit much more affordable um to make. But, we have also this aspect of security in mind because as this minimal ZK VM will have to be enshrined into the consensus of

Ethereum, this means that it has to be perfect and it has to be secure and without any bugs. Otherwise, it is it could be catastrophic. And so, we have also formal verification efforts in mind so that the whole um ZK VM, the the Lean VM, is so simple and so lean that it could be easily formally verified, which would be much more difficult, we think, uh with a circuit due to the complexity of the recursion inside the circuit as well. Nice. So, this brings me beautifully to my next question cuz I wanted to ask you about how the VM is designed.

And you've both sort of been dropping hints like a minimal ZK VM, a Lean VM. Like, what does this mean? I think that it means that the minimal we you can think of a VM like Cairo or because this VM is a lot inspired by Cairo. Um because this Cairo was the first ZK VM on the market, and they came with a beautiful new ideas, and so the inspiration of Lean VM directly comes from Cairo.

It is minimal in the sense that we have very few opcodes, just four opcodes inside the VM, and a minimal number of precompilers as well, just two of them. This means that we really emphasize simplicity inside the VM um in order to reduce at the maximum the number of line of code, for example, the number of logic um and ev- ev- everything around this, so that we are sure that this VM is it is not meant to be general purpose. That means that we can't really compare it to OpenVM or SP1 or other VM of this kind of the market that are much bigger and much more general purpose than LinVM.

But LinVM is really performant to do one job, that is signature aggregation. Mhm. And there is simplicity at two levels. So, this level which is the VM in itself, the opcodes, etc. Similar to Cairo, very simple. And there is also simplicity at the proving level. And for this the you can think of LinVM as basically the simplest proving system you could think of, which is multilinear. Important clarification.

So, basically, you have three air tables that you commit using Stark polynomials and Weir. Mhm. Then you have one lookup to prove the intera- interactions between the air tables. And then you prove the validity of the air tables again using some check. And uh finally, you need to you have so like a bunch a bunch of um opening points and you need to provide a a Weir proof for it. And that's it. So, historically, there was a lot of um fancy proving stuff to make it faster.

>> Okay. For instance, uh proving Poseidon with GKR um univariate skip lookup star. It helped a lot to make the prover uh faster. But >> Mhm. when we had to implement recursion in it turned out that those fancy tricks made recursion much harder. Uh both uh in terms of uh speed like because the verification program was uh bigger and more importantly, in terms of uh simplicity. All those fancy tricks to make the prover faster uh each trick brings you like 20% uh prover speed, but

if you cumulate them, you end up with a proving system very hard to understand and to explain. Right. And even the verifier becomes harder to express, and therefore the recursion becomes harder to do. That's very interesting, this trade-off. >> I I think this is also very important like to mention that all of these efforts are ongoing efforts. And uh Emil took the lead from from the start on LinVM working full-time on it first on a on a grant program and then within this uh post-quantum team. Um and so we always like try to bring simplicity to the game. Uh we had a lot of change like in the past few weeks.

>> of Yeah. In in the past few months and even in the past week, we still had a lot of change. So, everything uh that we are mentioning here is really fresh. Uh and we are keep improving the the system step by step um improving simplicity. I think that in the past months, for example, the VM was simplified by a lot. Wow, okay. What's the best way for people to follow these efforts and contribute maybe to the simplification or their understanding of the VM? I think that we have couple of um first like we have open discussions. We are working a lot with with Telegram and we have like dedicated um PQ channel where all of this is discussed. Um we also

have like a week on a weekly basis post-quantum uh interop call that are called to talk about like uh cla- full client specification, but also updates on the cryptography side. And we have a dedicated um Lin Ethereum GitHub organization where we have all of this repository. So, we have a repository for Lin sig. So, this is the XMSS signature scheme that is implemented in Rust with performance in mind. And so this is a standalone repository where you can contribute uh to improve speed.

Uh we can you can directly contact me and we will find issues together for you to tackle or or anything related to speed improvement. And then we have like this Lin multi-sig repository uh that Emil is working on full-time and where you have also a lot of improvements like to participate in. Um and even sometimes we discuss with collaborators that are also interested in the very primitive level of the stack. Mhm. And so, they want to contribute as well on Plonky3, for example, or on Weir. Uh these kind of things. Cool. And we'll make sure to have links in the show notes. Um you're talking about Plonky3, and that's actually something I wanted to touch

upon is like the implementation and what tools we use. Just before we do a few more words about the VM. Um you've mentioned the comparison to Cairo often. Is it fair to say like that's closest relative or the closest comparison Definitely. Yes. Cool. It's even simpler than than Cairo because we removed the AP register. So, in some sense, you can think it's it's even it's sorry, it's even simpler than Cairo. But it's like very similar to Cairo. I'm not sure if everyone knows what the AP register is, but for those of you who don't know, >> allocation pointer. It's simpler. Cool.

Um And so, my last question about the VM before we move on to the implementation is how do I write programs for this? Are we writing assembly? Like are we writing instruction by instruction or do you have a DSL for it? Similar to Cairo, we have a high-level DSL that compiles to those uh low-level uh four different opcodes. Mhm. And recently uh the compiler has been partially updated to move from a Rust-like a Rust-like syntax to a Python-like like syntax because for the recursion, we need to write the verification program with with like using our uh ZK DSL. Mhm.

And we will also need to specify the recur- this verification program for LinVM inside the specification, which is a Python specification. And by moving to a Python-like ZK DSL, we will be able in the end to have a single file, which is a subset of Python, that we that will be at the same time executable from the spec and that you can compile using the LinVM compiler to the low-level uh ISA for LinVM.

Okay. Actually, you're now opening another topic, which um will be interesting to touch upon is the spec like specking things. What is the role of a spec and um how do we push it But before we go there, a bit on So, Plonky3 you've mentioned already. Uh Weir as well. What were the implementation choices that were made and what's the current status of the implementation? We are working a lot with the Plonky3 um and with the Plonky3 forks. Um we implemented a lot of tricks inside Plonky3 because what we have to keep in mind is that the current other ZK VMs that are racing for L1 proving Mhm. are operating on GPU.

And so, this is very different from our needs because for the consensus, we want validators to run on very low-end uh devices. Mhm. And so, we target CPU mostly. And so, our optimization are completely different. Right. So, we can't really take inspiration from the GPU optimization, but we have to work a lot on CPU. And so, we made a lot of effort with Plonky3 forks to implement better parallelization for the fields, the field computation, the DFT, um all all of the primitives that are used inside the VM. And we are also using SIMD techniques. So, in these are like fancy technique uh to optimize your

GPU operation. So, we worked a lot, for example, on our hash function that is Poseidon2 to implement fancy SIMD techniques on all of the available architectures. Uh for example, on your Mac or on a Linux laptop or anything like this. So, we are spending a lot of effort on this. And for us, even like 10% improvement on the multiplication of fields is very important because at the end within the VM, you do this computation a lot and a lot and a lot.

So, this is very important for us to optimize these very low-level things. So, we are working a lot as maintainers of the of the Plonky3 repo. And also Weir as you mentioned is a primitive of LinVM directly used as a polynomial commitment scheme inside the the proving system of the LinVM. And so, we have also a separate repo on this that we will soon be upstream directly into Plonky3 because we know that other teams are interested by this such as OpenVM who designed its new prover uh methods using uh Weir at the core. And we are working a lot on this uh to optimize also we're at a bunch of

levels. Yeah. And we're was chosen because it's sort of hash-based replacement for FRI, I guess, in people's minds to stay simple. >> Yeah. And has smaller proofs. Is that correct? >> It's basically FRI plus sum check. Okay. >> And this gives you the rate, like contrary to FRI, at each step the rate decreases at each round, and so you get uh like significantly shorter proof in the end. Okay. To give you an idea, um classical uh STARK-based uh VMs, you can do smaller, but it's often on the scale of the megabytes, the proof.

>> Mhm. Currently, on Lean VM, we are below 256 kilobytes, and you can even do like 150 kilobytes using uh an aggressive rate. Mhm. And uh this is with proven security, and uh close to 128 like contrary to most of the projects, we need like we cannot use simply 100 bits of security for Ethereum, obviously. You just look at the hash rate of like the the historical data of Bitcoin and uh 100 bits is clearly not enough.

So, we need more, and we use for this uh next extension of degree five for the we we we use the Gold Bear prime. Actually, yeah, that's a good point. I never asked that. What field do you use? >> [laughter] >> Gold Bear. So, that's like a small prime field. Is that correct? >> Yes, exactly. 31 bits. And most projects use the degree four extension because it gives you like 100 bits of security. Mhm. But we need the extension of degree five to get with we're in the Johnson regime to uh close to 128 bits of security. Okay.

There is something interesting in what you mentioned. As you just said, like we're is in fact FRI plus sum check. And so we had to do a lot of effort on so on sum check implementation on CPU using fancy SIMD technique to optimize at a very low level our uh sum check implementation using also some papers from the Gold folks and and all of these to to implement this in a most efficient way. We have like Onear also working with us on a on a grant at the EF working on this very low-level optimization right now in we're. Um and yeah, so that is also a very important effort that we are conducting around sum check. Amazing.

And how do you benchmark these efforts? So, you have this VM, you have this implementation. How do I know that it's fast? In the past, you know, like all these different VM projects have been using weird benchmarks of like how many hashes can I do or like recently, Eth Proofs set the benchmark to be, you know, like proving an Ethereum block. Um what's the benchmark that you guys use, and how does the VM do? I think that we have different level of benchmark, and like Emil, you can talk about like the the higher level, I think, after that, but like we have very low-level benchmark on on all of the primitives. Mhm. So, for example, when we work on a fancy Poseidon optimization using parallelization or

um CPU techniques or SIMD or anything, we just have specialized benchmark um inside the primitive library just to do the a difference um with a rest tool called Criterion, where we have very precise um benchmark that are showing you like the percentage of improvement or degradation of your implementation. So, we use that for all of our primitives, like multiplication, field operation. Even in in we're, we are capable of like um tracking all of our optimization with very precise benchmark on very low-level stuff. And then we have a like all of the benchmark conducted by Emil on the on the Lean VM side of

things, where like the on the readme page of Lean multi-sig, you have a very nice comparison benchmark graphs like designed by Emil, um where you have a like all the numbers showing you um the time for a recursion, the time for a given proving. So, yeah, you can talk about this, Emil. On the on the readme, we find, as Emil said um the two real-world benchmark that we want to improve, which is first, recursion time, like two to one recursion, basically. So, two proofs coming in and one new proof coming out.

Yeah. Exactly. And and the second, the XMSS aggregation. So, how many uh signatures can you aggregate in 1 second? Right. That's the thing we were trying to do in the first place, right? Yes. [laughter] Yeah. Actually, [snorts] uh it's it was surprising to me how, to some extent, it's not sufficient to prove Poseidon, so the hash we are we using, uh fast. For instance, basically, you can prove Poseidon with GKR. On a Mac, you will be above a million Poseidon per second quite easily, like it's not very hard.

And it's not sufficient to prove Poseidon to prove signatures. Even if our signatures, XMSS, are mostly composed of Poseidon, because first, there is the logic. You need to glue those Poseidons together to form chain hashes, the Merkle tree, etc. So, and there is overhead at this part. And second, in XMSS, you need to compute what's called an encoding. Basically, you need to hash some message and randomness data into some part of like a fixed layer of some hypercube.

And this step must be part of your SNARK for technical reasons. And it turns out this like this trivial part is uh close to as costly as proving the Poseidons, because you need to be decompose a lot of stuff, and in the end, my point is that proving Poseidons is not enough to prove XMSS in an efficient way. There is, as always, some details that need to be handled.

Right. By the way, I want I'd be curious, do you guys have real numbers of like how many signatures can you aggregate uh like how quickly can you aggregate them, and how many are needed actually for the network to run correctly? Um currently, on the main branch, you will be above 500 XMSS aggregated per second. Mhm. If you move back in the past, like a month ago, you will find 1,000 XMSS. Right. >> It's on an on a Mac M4, so it's a pretty good laptop.

>> Mhm. Um and the reason we went down is that we implemented recursion. And so we had to get rid of all the fancy tricks that made the prover fast in order to be even able to implement recursion. And so now we end up with like a very simple prover, but obviously, it's a bit slower, but still you like a two x slower prover, uh which is simple enough to be proven secure, is uh worth much more than a two x faster prover, which is insecure in some sense. Mhm. I guess. And I guess in

some sense, that means the benchmarks were like almost over-optimized for uh signature aggregation and forgot about recursion and we're like Yes. Yeah. And actually, can you tell us how many signatures per second are needed for the network? I think that we would need like a couple of thousand. Not sure about the like the exact number, but yeah. Yeah. In the in the short term, one it would be nice to be like at a 1,000 XMSS aggregated per second on a Mac in the short term. Mhm. But obviously, if we can do better, it's always like it's always nice. But this is on CPU, and it's important to keep it in mind cuz at some point, we may implement, and it's it's not very hard to implement,

some like at a bit of GPU acceleration will bring you at much more than a thousand XMSS per second. And like this is very important also to keep in mind that we have always couple of trade-offs, because we have like the number of XMSS that we should aggregate per second, that is an important metric, obviously, but we have also like the recursion time, that is also important, because um we have some peers that we want like to aggregate some fresh signatures, but we have also other peers of the network we want to like recursively aggregate signatures. So, that is also an important metric.

And another metric on top is that we have to exchange those objects, which which are like proofs or signatures, among the network. We know that BLS signature and their aggregates are really, really small. Yeah. Post-quantum objects are much larger, and so this is much more like difficult to exchange them over the network. So, we have also like this important trade-off of like number of XMSS we can aggregate, number of recursion that we can do, and also the price and the cost of exchanging information around the network. And so we are not, obviously, like peer-to-peer expert, but we know that for sure we'll have like work to be done on the on the

peer-to-peer layer side of things. And actually, that is the topic for the next episode. So, that's a great little segue. Um one last thing I wanted to ask you guys about. You mentioned a Python spec earlier. Um I'm curious to know what what is a spec? What does it mean? What is it used for? Why is it written in Python? Yeah. So, historically like we have this uh Python specification for both like the consensus layer, the execution layer, for client teams to be able to implement to implement the spec and follow the rules of Ethereum.

And so, what does it means? It means that you have a Python repo. And inside this Python repo, you have all the rules of the consensus or the execution layer of Ethereum that are written down. This is very important because also in this spec, you have tests that the client teams can consume to be sure that their like implementation is correct and satisfies the rule of Ethereum. So, inside this Python specification, we have implemented the fork choice of Ethereum the networking layer of Ethereum, the validators role, the state transition

function, everything related to the block, and we have also implemented our new post-quantum signature scheme and the aggregation. And we all of this we are able to conduct with 10 client teams, some devnets, where those client teams communicate together, so they interrupt as we say. And they are able to test the network and the validity of our assumption. Because even if we build this minimal ZKVM in this mode, at the end this is very important to confront with a reality. And so, this is very important for us to benchmark all of this effort to see if what we thought is finally okay

and everything. So, we have 10 client teams and we have weekly calls lead by Will at the Ethereum Foundation, where we discuss all of this topic and all of the subject related to client implementation. Oh, again, I think unknowingly you're doing some perfect advertising for the next episode. So, thank you very much. >> [laughter] [gasps] >> Guys, I think that's pretty much everything I wanted to cover today. Thank you so much for coming on the show. This was super instructive. Thanks, you. Thanks a lot for having us. Yeah, it's always a pleasure. It's always nice to also see people who are very active in the community to come on the show for the first time. It's really fun to have you here.

I would like to also thank the podcast team Anna Rachel Henrik Tanya and Hector. To those of you catching us on video, thanks for watching. And to our listeners, [music] thanks for listening. >> [music]