Challenges of Bringing a zkTrie to the OP Stack | Jan Gorzny - Zircuit

zero knowledge rollup we started building on the op stack we're not on the super chain but we do love what they do and uh we want to talk to you about some of the struggles we had in making their code our code and the big one that we had over the last couple of months was uh this thing called a ZK TR and if you don't know what that is hopefully in the next couple of minutes you're going to find out so let's get into it a little bit of background for you uh I'm going to Target this in a really weird place I'm going to assume you know what a rollup is so I'm not going to go through explaining that if you don't know there's a couple slides where it might become very clear what it is but it's easier if you know so apologies if you don't if you have any questions come find me afterwards happy to explain also l2s types of rollups other things um and we'll also assume a little tiny bit of op knowledge and um zeret and basically I just want you to know that optim or the op stack generally builds optimistic rollups that's may be changing now with op cinct and other things and zerit is a zero knowledge rollup so it's a key differentiating factor circuit's also got other unique features which we would love to talk about but they're not the focus of this talk so I'm going to skip that but nonetheless let's get into it the title is bringing azik Tri into the op stack why do we want to do this well the first one is just can we like I I'm a technical person I want to see what the chall challenges of this are maybe I get some benefits out of it and it turns out sometimes you might those times you might is when you're trying to build a zero knowledge proof uh or Zer knowledge R up because uh you have to always use this ZK TR um or rather the MPT in gu to sort of show that you've updated State correctly and the one that currently exists by default um on the op stack and gu and other places is a meracle patri Tha which I'll talk about in a minute and that is apparently not very good for zero knowledge proofs it does operations that zero knowledge proofs take a very long time to do and it does this because it's built on this notion of kak 256 which is a famously you know good but ZK slow um hash function so if we could change that to something that's a little bit more favorable like Poseidon you've probably heard this all over the place uh that's not so bad for ZK proofs so let's see if we can do it spoiler alert we did but before we get there I want to talk to you about um what we're actually talking about cuz I just realized that last slide you know I dumped a bunch of jargon on you so what is what am I talking about with the ZK TR what do I care about well rollups have to post summaries of their state to other places right so they have to post the layer one to ethereum itself in order to inherit some of that security basically they post an updated route and everyone agrees through some smart contract rules that that um final route is the real last thing you've seen on the L2 and um therefore unless you can change that on the L1 there's some level of security so that's really you know helpful and useful and very uh very very effective and typically it's done through something like a Merkel Patricia try or this plus some additional data um or this with various other things in it and a Merkle Patricia Tri just sort of looks like this it's a tree likee data structure it's a TR technically not a tree so there's some sorting and how leaves are placed but it is very much like a tree and every node is sort of the hash of this children's nodes data and if you're a branch or if you're a leaf node uh you just hash the data that's in it and essentially this means that if you change any piece of data and all of the data you have is eventually hashed into a single rout um the whole roote changes so any small change anywhere in the blockchain OR in this data set will result in the root changing and if you just change that rout then and just update that route I can be very effective at uh posting us a very short summary of my data and the root is just the thing at the top that is dependent on all the other hashes right this means a change to any of the data in the leaf um nodes changes the route so if you update a balance of an account the root also changes that's critical so you can't get away with cheating because every time you make a change the Root's going to change and you're have to post a new State Route so because of how this is built um there's a lot of hashes going on and so when I say kak 256 might be too slow for zero knowledge proofs I'm not just concerned about you know doing it once or twice or you know some small amount I have to do this every time I update any state in my rollup and so I'm using this a lot so if I can get some optimizations I'm really happy to do this so where where are they used and what what happens with them why do I really care I've told you about this data structure well these are summaries for rollups so let's think about how a rollup works for just a second you have this notion of an L1 in Gray you have a sequencer that builds blocks maybe people call a different name maybe this is a block Builder component that's slightly separate doesn't matter you get some transactions either from you know other people interacting with the network directly or bridging on to the network from L1 deposit transactions you build some layer two blocks and then you propose that to to say this is my new state route and you post it on chain sort of locked in subject to these rules where the verifier might interact the verifier in an optimistic rollup is you know the fraud proof system or fault proof system where someone might challenge you and say actually you did all of that wrong I saw your MPT I saw your list of transactions uh you cheated let's fight and you do something and is there a knowledge proof um it's less explicitly an actor and more just a smart contract that verifies a mathematical proof that a compan is this and that's where we want to go but I'm talking about the op stack so I got to include both if we look slightly more specifically at the op stack these components have real names and real pieces of code associated with them they're not abstract um there are various things that need to change if you touch a state try and we're going to talk about this so the node um the sequencer is sort of a coupling of an OP node program which sort of drives the consensus for the op stack and an execution engine op gu which is a fork of gu that they've modified in some ways uh to produce layer two blocks on optimism or any other op stack chain and then they have an OP proposer which occasionally takes all that stuff posted to a Smart contract and then the op program you know can be used to challenge these things so you start seeing all these components and actually there's probably a dozen others that you may or may not want to touch if you're if you're screwing around with an OP stack codebase um but there's a whole bunch of stuff you can change and so let's let's see where do we have the ZK or try or the MPT try oh turns out everywhere right all of these critical component on are going to be touched by this MPT so now if you want to say you know change your state rot summaries to be a ZK TR you can't just go to one piece of code and say import you know Poseidon instead of KAC 256 that would be great if someone could refactor that code base to make that work that would be huge I don't think it's feasible I think we got to go component by component and at zerit that's actually what we sort of had to do we wanted to go through um and take out this MPT and put in a z try and so we started looking at all these things and I'll tell you we got a little bit lazy and I'll tell you a little bit how in a bit but let's go through why we needed to do this and why we couldn't skip any of these steps or at least we had to skip them in a clever way first the op note it's the consensus layer it's sort of responsible for actually instructing the execution engine to build the blocks um it is going to get deposit transactions from L1 it's going to get other things it's going to rederive the state when need needed so if your node goes down you can run it up and it can read from L1 and rederive all the chain so unsurprisingly if it'sing trying to rederive or build blocks for the L2 it's got to touch the state TR it's got to figure out what's going on one really important place it does this is a function called prove withrawal parameters for event it's complicated name whatever uh the idea is that this gives you that withdrawal proof so at the end of the day on an OP STX system you have to prove as a user that you submitted a transaction on the L2 that was eventually written to L1 as part of the state and you need to call this function somehow indirectly probably you don't call it you know on your control on your uh conso but somehow this is called and uh you know that means it's very critical and everyone touches this so you can't skip this because then you screw with people's withdrawals and people can't take money off of your chain they're going to be really upset with you so you got to touch it there's a couple other places in this derivation stack that also touches um the try and the state summary the next one is to actually build this summary sort of the obvious candidate shows up gu or the thing that looks like gu op gu I might call it L2 gu because that's what we call ours uh and uh it's sort of the obvious one in the sense that it is responsible for changing uh State balances and accounts based on transactions when you make these changes therefore you have to update the summary of of the uh balances and um this is where probably the largest number of touches to the codebase needs to occur you need to go into a bunch of places into gu to figure out exactly when this tree is re read or written to and update it and change it to um say the Poseidon Bas e TR that you care about and uh you know it does a whole bunch of stuff go through some of it um for the people who don't know it's uh definitely going to do at least the following where you know it'll store a summary of the nons a balance and a storage route or the code for contracts so basically it really takes the whole summary here and then it'll update the try in such a way that it remains a try not just a tree it'll order things in an appropriate way and then finally does all this hashing and you're done but if you want to execute that correctly and quickly you do need that ZK try once you get all of that changed it's the biggest piece of code to change by far you have to submit the new state route on chain and then you have to tell people that actually it's you know going to do something different and now if you go back to derivation maybe you need to use a different function to change the withdrawals or you have to have made that change and um essentially you know it it touches the output no surprise um this is this is great so these are the the three sort of things that we really really cared about at circuit because we wanted to switch to a ZK roll but there's also verification so the challengers then also need to be aware of this change so you can't run you know ZK Tri op stack with a fault program in MPT out of the box I would imagine it'll be very difficult to do it all but um you have to make this change and so the fault program also needs to be updated and basically what this means is you've touched very critically almost the entire stack this is a non-al challenge um I encourage you to try and play around I think it's a fun thing to do you really understand how transactions flow work if you can trace where this TR is updated and read and you know touched throughout this code base um especially if you're here as a hacker uh it's more something that's very very interesting and in a couple reason a couple slides I'll tell you why that might still be interesting even though this is very hard and will take you probably longer than a week um but essentially yeah you still need to touch the uh the verification okay so let's take a step back why why were we doing this we wanted to get faster uh proof generation on blocks that were now built using a ZK TR not an MPT uh and in short there's a lot of work this took us a ton of effort um to do there's uh as far as I know no good open source Fork of you know the op stack that uses a ZK try we're going to open source our code base soon so maybe ours will be one that's really helpful other people have done similar things so scroll for example has put a zry into gu but not necessarily the same version of gu and because they're scroll they wouldn't have touched like op program or op node they'll have their own versions of these systems which is totally fine but it's a lot of work so it was a challenge and we wanted to do this for ZK rollups and because it was so much work uh we thought we could do something a little bit different and we just released a test net earlier this week where actually we are doing something different we are going to touch this code base in only a couple of places we're actually not going to touch too much of the op um node or the op well the proposer will change uh but we're actually going to have our gu Computing both tries so that we can actually have the op proposer still write an MPT State Route that's normal and fine and then we can also generate a proof for a ZK try and we can make sure that those are mapped sort of one to one or one never falls behind the other in some nice safe Manner and people can have the ux of working with an MPT from the op stack but also we can get the performance and the proofs from a ZK TR this is not a long-term strategy um right now we're doing this in part because we want to see if we could and part because we needed to increase performance um but in the future and I'm going to talk about this on the next slide uh we want to know what we're going to do with our chain and probably a bunch of other people on op stack chains also want to do this in particular this may not be super super relevant if we change back to a zkv m if we go find you know something like uh risk- zero based um general purpose zkm uh it doesn't really care too much about the uh try that you use to record your state it might there might be performance hits but it might not be as important as it is right now where Halo 2 really struggles to do CAC um and and maybe it'll be worse I'm not sure but we want to have this flexibility and in the next version of our release whatever that looks like we'll pick one of the tries to be final and say we're good right um but so this this flexible approach that we're taking for Now is really really nice and helpful um and you know why you might also care is that this might not be the last time you have to touch this code base like you as a community or you as a developer um in the future ethereum wants to you know put veral trees inside gu and maybe that means all the op stack needs to change for that again so getting good at this or modularizing this now would be really really valuable now I'm not saying that's an easy task I'm not even saying it's a feasible task but a man can dream and I think it's worth trying and at the very least you can play around with it now so that when you want to make these changes later it's maybe not so um scary um but either way I think it's an interesting technical challenge I'm basically out of time and I got only one last thing to say which is ethereum uh sorry metallic tweeted this the other day and um it sort of gives exactly a good reason as to why this might be prominent be uh because he says uh they might want to switch just that CAC to Poseidon for Native L1 clients and that means if optimism or other rollups want to be exactly one to1 with the ethereum node on the L1 you would have to do this anyways so all of the stuff I talked about we have to get good at practicing and doing right and like we hope we did it right we got audits we checked all of that stuff but um you know other teams should also take on this Challenge and maybe we can make it easier or better and uh this is not just like an exercise and can we do it because we have engineering Manpower lying around it's something that might be very very necessary in the future so I think it's a little bit more wider reaching than my title suggests but still interesting anyways I'm out of time uh I have uh no more slides if you have any questions or concerns um come talk to me I got we got a booth down there uh just go that way we have plushies and I'm happy to answer any questions and uh discuss circuit or our modifications at the op stack there or online through one of these meet uh methods so thank you