Proving Less, Verifying More: 3.5× Faster L2 Validity Proofs

Transcript

Hi everyone, my name is Mosen and I'm going to talk about uh faster L2 validity proofs. Uh this is a project that I did together with my colleague Pedro at our time uh at Zirkhead. I'm now with Monat Foundation. Um so let's get into it and see how we went through this problem. Um the first thing that I need to establish before talking about the uh optimization is um how does optimism work when it comes to derivation. So as an L2 in order to be trustworthy for users you have to submit all the transaction data on L1. So that's your anchor of trust.

And um once the data is submitted on L1, the rollup has this mechanism that continuously monitors um the published data on L1 goes through through all the blocks. um validates you know all the transactions that are relevant for the DA the call data and blobs assembles back you know those uh frames and channels this compressions that optimism does and then executes um you know those recovered blocks from L1. So basically the entire state of L2 is dependent on what is already shown on L1 and at this stage you know the rollup is considered finalized or secure and against this secure state you can do

your withdrawals. So basically everything you know is anchored on L1. You have a role of a batcher here that submits you know your DA uh the list of transaction compressed uh to a to an inbox and that's you know the role that's the the actor actively involved in doing that. Um now if you want to do validity proofs for rollups u the typical way of doing that is to have a range proof. So a set of blocks you can decide how large that set is going to be. Um so it could be 100 blocks. You do a state transition for each of those blocks. You check everything and then you compute a range proof over that one. And you need to

pass you know the list of transactions as input to that to a range proof. You don't want to submit the range proof directly to to the chain because you know it's going to cost a lot for every range that you have to to submit a proof. you rather want to use recursion in uh in your scheme and compress and aggregate all those proofs of your ranges into one aggregate proof that you periodically submit on L1. So this continuity of those ranges is verified by the aggregate proof and once that proof is you know available on L2 output oracle then you can basically start withdrawing the chain is basically 100% finalized.

Now we we did the migration to ZKVM. We were using SP1 and we saw that contrary to our original benchmark that we did um the ranges were expected to be between four to five billion cycles. But we had some set of very mysterious ranges that they kept popping up rather consistently and they costed 10 times more. So they they were in the magnitudes of 40 to 50 billion cycles and this was 10 times more than what we expected that we would need to prove um those ranges and this happened consistently.

Then we started investigating. We looked through the the breakdown of the proofs and we saw we were looking at which part of this range proof computation is you know taking most of the uh cycles and turned out that derivation the process that surprisingly I spoke about a little bit in the very beginning that one is taking most of the cycles so most of the effort is spent in that basically um derivation step 85% the execution just set off you know L2 blocks with L1 deposits only considered 10% of the entire time spent in the proving and everything else was just negligible less than 5% for you know decompression and

everything else you were doing was just basically nothing 85% is pretty much why is 85% of the time into derivation wasted so for that we had to look deeper and do some instrumentation and see which step exactly in derivation is costing that And I need to go very quickly over high level idea of what those are. So derivation basically fetches all the blocks that are deemed relevant for deriving the state of L2 and that's basically L1 block filtering uh fetching. Uh once blocks are fetched then all the receipts in those blocks need to be uh checked because you know the protocol has some update path that

you can change the batcher. So those events that are relevant for the derivation process need to be all processed as well. Then there is this filtering for TX for transactions that bear any DA data. So any you know call data or blobs. So that's basically going through the transactions and finding those um DA bearing uh transactions and then frame assembly and everything else. And those are rather quick. So those two boxes that I have in red, those are the expensive operations either derivation. So most of the cycles were spent exactly on those two. And then while we were looking at this, we had an idea of why uh this is very slow and how this is

happening. We had an incident. So over the weekend u there was a batcher timeout. So the batcher stopped submitting the DA transactions for a course of nine hours we think and then we ended up with some ranges that needed more than 100 billions of cycles to be proofed and that basically means we cannot do that. So we have to skip over those. So we have to skip those things in our test net. So those are basically a denial of service thread basically that we are seeing here.

This situation was much worse actually on test net on seapia and we were puzzled if this is a deterministic behavior why on sepoleia we're seeing much worse results than maintenia at the time of the analysis blocks were much more filled because you don't pay for those transactions that you're submitting on seapia so I assume people are submitting more on the test So we have on average 278 transactions on Seapoleia and mainet is you know 192. So it's like 45% more transactions and this directly correlated with the higher cost that we

saw on Seapoleia. Now let's take a closer look. I already spilled the beans uh but let's take a closer look and just spill it out. Um the bottle the bottleneck in the pipeline is basically once you have L1 blocks that are deemed as relevant for um the derivation. Um there is this step that scans all the transactions in those blocks and this is a complexity of o of transactions in the blog is linear but those transactions could be quite a lot and after the filtering you will be ended up with a set of um transactions that are relevant for the derivation. So those are batcher transactions and

that's a very small subset of you know all the transactions that are on L1. So here the inefficiency is that you have to traverse so much to just extract so little of transactions that are relevant. And to give you an example, 382 relevant, you know, blocks identified by the derivation process would have 7 73,000 transactions in them. And scanning all of that, you would only need something around 15 transactions out of all of that. So you can see how much wasted computation is done here to just find those 15 transactions.

What we want. So I already explained the left side. So full traversal you have the host you know fetching all the L1 blocks and passing them to the ZKVM to compute you know and find the list of DA transactions for you and do the derivation. This is very high overhead expected here. What do you want to do? We want to actually do the host to do a little bit more work outside the ZKVM. You want the host actually to do sparse or do a search of transactions outside the ZKVM. find those 15 transactions that we deemed as relevant or how many they are and then only pass those subset of transactions inside uh ZKVM. Right?

Here's a little bit of problem though. If we just did that, just pick those transactions we deem relevant and pass to ZKVM, we could violate some safety guarantees. So, we would have some soundness issues. Um, let's get into that. what could be potentially a problem if we filtered everything outside ZKVM. So number one is basically soundness problem of um allowing the host the untrusted entity to basically emit to omit any DA reorder the DA or basically replay the DA because you know the ZKVM only sees the set of transactions that it it is told to trust and derive from them. So basically if the host is cheating it can

pass whatever transaction it want and then the ZKVM would just accept them. So one quick way or one easy way to to solve this problem would be actually introducing this nons continuity for the list of transactions that are passed inside the ZKVM. We say okay all the transactions must have this incremental continuously growing by one uh transactions. So if you skip any transaction, if you reorder, so the nons would not match and under the assumption that the batcher only submits DA related transactions, then we are covering this problem of you know introducing gaps or omitting or reordering. So this should be solved. Um there is one catch though here uh the batcher itself could be

modified, could be updated and that would you know be a protocol level change. I'm not going to get into that but this is something that we also consider and uh deal with it as well. Another problem is if you just look at the nonses and give list of transactions still the host can actually do some um attacks they can forge they can say oh this is the transaction here is the nons go for it. Um so the signature needs to be valid it must be from the batcher. uh they can also you know um make a transaction that has the signature but is sent not to the batcher but somewhere else right so you still have the non continuity you have the signature matching but is sent to somewhere else so tx from needs to match the protocol

level batcher it has to be from the batcher that we care about currently set in the protocol tx.2 two should be the batcher the batch inbox and you know if any update happens we need to be able to detect it and that's the next optimization that we introduced to solve this problem by looking at logs blooms there are no false negatives in logs blooms so we basically look for any update events rather than going through all the receipts we look for any update events if we hit if we find them then we say okay this is the sender the sender must be this address and that problem would be solved as well. The third thing now so far I talked about the ranges. So each range needs to have this continuity

of nonses. The data has to be authentic. It must be sent to the from the uh batcher and it has to be set be sent to the uh inbox. Um but so far we only have these guarantees at the level of the range. So each range has all these soundness properties that we care about. Right now there is no check cross boundaries because we do separate ranges for each set of blocks. We do one range proof, the next set another range proof and now this one would have the nons continuity and all the checks you want. The next one starts on its own and it would have its own nons continuity. So in between I can basically skip a nons right and there is no way for this proofs to know about the skip nons or change of sender. So we need to

introduce another soundness check at the level of the aggregate proof and that's basically by ensuring across the ranges the nons are still consistent and the sender is still matching. So we are taking away one of the optimism um you know features here um because you can change the you can update the batcher on the fly to whatever batcher you want. But for the standard practice this is not a big limitation because if you we introduce a new lane that you can update the batcher address as you wish but those must go through a different lane cannot go through dayto-day range and aggregate checks you have to update that separately and this um check of the sender and nonsense has to be intact for

any normal operations that you are doing very small you know overhead uh if you if you are changing uh your batch address which we never did at the time you were operating But if this this is something you need that's something that you have to address in your maintenance flow and it doesn't have to be part of the critical path of your application. So now I have covered you know the optimization itself filter transactions and then introduced this soundness checks why we need them what kind of attacks we are mitigating with those and the implementing the scheme itself. So after implementing this sparse uh filtering we notice 6.5x speed up in the derivation. So the

derivation is significantly faster. Um overall ste speed of the end to end proving for those ranges 3.5x faster. So the ranges are being computed much much faster now. Um and for different um channel duration, the timeout that you're submitting your batches, this gains could be different. So now opposite to what it was in the unoptimized version or the baseline, the longer you wait, the larger, you know, set of blocks that you have to actually uh consider in your derivation, the wins are are actually much bigger. And this is useful because for if you more

frequently are submitting the DA, you have to pay for the gas of those DA. So you can find the sweet spot that you submit less without sacrificing you know the efficiency of your range proof. This is something that on the baseline you cannot do because you can see at the baseline with 500 millisecond we basically have uh 4 um almost five uh billion of cycles and this is the unoptimized version. With the optimized version this this has dropped to 1.4 billion basically.

Okay. So what are the key takeaways? what we did look at here and what did we learn from this. So first off, uh ZKVM amazing tech. You can just take a program written in Rust and just run it on uh the ZKVM back end. Um and then you can have verifiable execution which is amazing, right? Uh this doesn't work well uh for all programs um in a way that um the performance is going to be maybe far lower than what you expect it to be. Um there could be some edge cases also that you might not see immediately.

So in our case our initial test showed really good result. We were like very happy with that. Uh but with some you know pileup of the DA we saw that it was much worse denial of service attack or a risk of denial of service. If this data piles up then maybe you cannot even prove it anymore. Um although the ZKVM can do any Rust program but if your program is has this risk of you know having way too much input if it piles up over time unbounded input this could be actually a denial of service risk. Um we designed a sparse input. So we optimize the data that goes into your ZKVM. But I showed you that actually this is not enough. Just optimizing the data is not

enough. We needed to introduce some soundness guarantees here as well. And this was done by tracking nonses, you know, signature checking and L1 anchoring. So having the nons across the ranges for the aggregate proofs with this kind of optimization 3.5x faster proofs we basically um can do we get much closer to real time uh proving and if I want to say broader impact of this this could be applied to any ZKVM application that deals with large inputs partially relevant uh for the actual computation. the same technique could be applied. Verifiable execution doesn't necessarily mean efficient execution and

if it's efficient doesn't necessarily mean it's going to be sound. The source code is fully open source. Uh you can take a look at the code yourself. The preprint is also on archive. Um you can see my telegram. Um you can reach out to me if you have any question. If you're working on similar problems, I would be more than happy to answer questions and give you um some feedback on the design you're having. More than happy to help in any way. Thank you. If there are questions.

Well, thank you very much.