LeanVM

Transcript

[music] Thank you very much. Hello everyone. So I'm Thomas Banks and I'm going to present you what is Linvm. So to begin with, what's the problem? The problem is that we want to make Ethereum postquantum and more recently post AI and that currently all of our cryptographic stack uh relies on elliptic curves. Typically at the execution layer you have ECDSA, at the content layer you have BLS and at

the data availability layer you have KZG and all three relies in some way to elliptical cryptography which we know is broken by SH's algorithm meaning quantum computers will break it trivially as soon as they are sufficiently big and recently there is this fear that even cheaper smart mathematical AIs could also break it. And so we need to move towards this so-called hashbased cryptography, meaning we stop relying on elliptic curves. We rely fully on hashes.

And turns out we can construct all the primitives we care about in Ethereum purely on hashes. For instance, at the execution layer, we can replace ECDSA, so the signature you use to sign a transaction by something called Sphinx, which is a hashbased signature scheme. For the consensus, we can also use hashbased signatures to replace BLS. We have this is this XMSS scheme. And for the data availability availability layer we also have a solution based on element encoding and Merkel hashing to make our blobs

postquantum. So in some sense we are all covered by hashbased cryptography but there are two small issues. The first one is the size. Those hashbased uh hashbased signatures are extremely solid but they are much bigger than today's signatures. For the consensus layer, we are speaking about a 20x improvement in in increase in size. And for the execution layer, we're talking about 100x [snorts] improvement uh increase in size. One sec. Um [snorts] take

second problem we don't have native aggregation currently Ethereum performs on the order of a few hundred transactions per block at the execution layer but it performs on the order of 30 30,000 transactions per at the consensus layer because every slots tens of thousands of validators attests the block, sign the block to construct the proof of chain, the proof ofstake chain and um sorry [snorts]

and currently for these 30,000 um signatures being um handled per slot at a consensus failure. We rely on aggregation of BLA signatures because those ellipticers BLA signatures have native aggregation properties meaning aggregation is easy. You have your thousand of thousands of GLA signatures. Each is small and you can aggregate them into a same size small aggregated signature.

The issue is that we don't have this nice property with XMSS this hashbased signature scheme and it's a big problem because every signature every XMSS hashb signature is like 2 kilobytes and if you multiply 2 kilobytes by 30,000 XMSS per slot you are at like 60 megabytes of signature data per per block which is impossible to handle. The solution is STS aka hashbased successment.

In particular, in our case, what we care about is to replace this 30,000 XMS signature per block by a much smaller cryptographic proof that will attest that these signatures have existed at some point. But you don't put the signatures in the block. Instead, you put in the block a stark. So this cryptographic proof that says I know the signatures have existed in the past and here is a proof and this proof is much much smaller than the 40,000 signatures that you have every block.

The thing is in Ethereum we have this subnets these committees meaning the aggregation it's not like every validators send the transaction to a single uh aggregator that will perform all the aggregation um directly. So we have these committees um meaning a small number of validators that can aggregate their signatures to form a stark uh cryptographic proof. But then you end up with let's say 16 of these starks one per committee and you want to again combine the 16 starks into

again another stark and you can do it. You can have a ST that says I know 16 STS that were verified valid and each of the ST was saying I know 2,000 signatures that were verified valid and this is called recursion. you verify a stark inside another stark. And this is extremely powerful because it allows us to parallelize the aggregation work across multiple subnets and to in the end combines everything into a single stack. Meaning whatever [snorts] the number of validators is, you can in the end only store a 256 kilobyte stark in the block.

And LINVM is the this machine that will handle the ST. LINVM is what's called a ZK virtual machine meaning it has an instruction set a few number of instructions and you can write programs using this ISA this instruction set and LINVM will prove correct execution of this ISA and it's not like risk 5 that has I don't know 65 instructions it's a very very simple ISA LVM is a very minimal and simple virtual machine.

In particular, LINVM has only six instructions. You can think of it as something close to a circuit in the sense that most of the instructions are additions and multiplication as in a circuit. And you have a few instructions to perform hashes because we want to aggregate hashbased signatures and this involves um verifying a lot of hashes. And you have [snorts] a few other instructions for control flow to have um some loops and um conditions in the linv programs.

In terms of cryptographic machinery, LINVM recently thanks to Flock and all the recent advances um moved to binary fields meaning these fields um based on the like extensions of the smallest possible field F2 that are extremely efficient to prove standard hashes like Ketchack. Linvm uses catch 256 the same hash function the execution layer of Ethereum uses meaning linvm doesn't add new cryptographic assumption to Ethereum it actually it will remove cryptographic assumption because it will remove

elliptic curve cryptography so it will strengthen the cryptographic assumptions on which Ethereum relies So in terms of small details for those interested um the PCS is we um we use the ring switching and M3 arithmicization from binus and we use a ground product GK to handle communication via buses between the different tables the different circuits of the VM lin VM he's currently being formally verified

And we are very close to have um fully reviewed the statements that prove that LINVM is complete and knowledge sound with 128 bits of security in LIN 4. And as I said before, LINVM is based on Kshak extremely secure function, very high margins and proves Kshak thanks to GK and reverse multiplication friendly embedding um technique uh that was brought to us by Le Sukov.

And that's it for me. Um the TLDR [snorts] is that BINVM is a zero knowledge virtual machine that is as simple as minimal as possible to handle all the STS that are needed to make Ethereum postquantum post AI replacing all the elliptic curves. You replace this by only hashes. Everything relies on hashes. Everything on Kshak solid rock solid and essentially you can aggregate thousands of signatures per second. You can recurse you can handle blobs signatures at the content layer at the execution layer. You can handle everything that you need to make Ethereum work purely based on Kak. The

only cryptographic assumption in this world. Thank you very much. Awesome. So, we have some questions. Um, one of the main questions that I was like thinking about when I was listening to your talk is like, okay, so you said we use Starks, you use Starks. Is a Stark the same as a PQ snark? Like, is this the same terminology? >> Um, almost. Uh, there are essentially two ways to build PQ snarks. I would say the first way is hashes. So hashbased snarks what I call snarks. And the second way is latises. You can al also

typically jolt is a risk VM that uses latises as a building block. >> Okay cool. Um another question is is statelessness a part of lean VM road map or not yet? I would say yes because currently VINVM uses this very minimal eyesight a very simple um um stark machinery but there is a world in which we use linvm we use in linvm the risk 5 is that would let us prove um EVM blocks thanks to a risk 5 um guest program for the EVM.

Another question. So like I remember this is kind of big news. You guys were considering using like Blake 3. You were originally using Poseidon then Blake 3 and now it's Kach. It's really there's a good question. Uh >> yeah. So what are the challenges to implement recursion for Kach [snorts] I would say? Um so for context initially lin VM were using poson 2. Then poson 2 was almost broken. It's still secure but the security margins was reduced a lot.

So we moved to posedon one. Then flock came and flock was able to prove very efficiently standard hashes 23 black. So we moved to shhat three sorry to blake three. Then we realized that Blake 2 black 2S was also almost as fast as black 3 because it was the same power of two in the CSS matrices in Flock. So he moved to um um Blake 2S and then it turned out using GK Air you can have extremely efficient Kak Kak proving like this machine can prove on CPU CPU uh 600,000 Kak per second which is more

than enough to handle the signatures we need for Ethereum consensus execution and data layers and so I would say there's also like Fatu which is um considered because shhatu is already in Ethereum at the consensus layer. So in some sense it would also not add any new cryptographic assumptions. Um but chat three are good hash functions and I think we are happy with it. Yeah. So you're confident that you'll get the same performance from Kach as >> Yes. I mean maybe not maybe you could I don't know it's likely that you can be a little bit faster with black tree for instance because it is extremely fast but I don't think we should optimize for 20 25% performance improvement because

the performance is already extremely good like you can aggregate thousands of XMss per second you can have recursion in I don't know you can aggregate 8 to one recursion in less than a second. So performance is already very good and performance keeps improving like every day I merge peers like 10% 15% improvement. So I'm not afraid by performance and so I think uh we should really optimize for simplicity and security of the stack machinery because performance is in some sense a solved problem. I would say >> another question that has a lot of up votes is why only six instructions the VM is general purpose. Can you prove other types of programs not just signature aggregation? Yes, you can prove like it's complete. You can prove

everything. Um, the VM has been really optimized for recursion and aggregation of hashbased signatures. Having a very small number of instructions, it is friendly to recursion because um when you recurse you have to verify a proof of yourself and the number of instructions will impact the number of constraints blah blah blah. So having a very small um ISA means very fast recursion and so that's why we want to keep the ISA small. Makes sense. So who runs this VM? Is this running client side or is this you're running this VM?

Who runs this? >> So there are proving and verifying. Verifying the stark is done in a few milliseconds. Your phone your whatever can verify it. Uh even your ledger can verify it. And this can be useful. Um and proving would be done by validators um in the consensus. And it turns out you can prove STS very fast on a few threads like four threads of AVX2 or AX 512 is enough to have efficient aggregation of signatures. >> Makes sense. Um unfortunately >> [music]