Completing the Circle: Transitioning from Verkle to Binary Trees in Ethereum

Transcript

Um so hi. Um yeah so last year in Bangkok I was uh you know making a presentation about why vertical trees were still the thing to do. Uh so that hasn't changed. Vertical things are still the thing to do. Uh but there's been so many changes uh that uh this comes into question. So I'm going to basically give an update on uh this presentation of last year and um announce that well it's pretty obvious by now to everybody involved but announced that we're moving away from from vertical trees and uh we're going back to binary trees. So I started

working in uh binary trees on binary trees in 2018. Got uh interrupted to by by research to say you should work on who said you should work on on vertical trees and here we go again more preeemption uh time to work on binary trees. Um so let me give you the the status quo. Um vertical trees are the only option we have right now. So this hasn't changed since since Bangkok. um they are much smaller than uh than the Merkel like the tree itself is much smaller the the proofs are also smaller and um and uh yeah it's uh I forgot something but it's also ready yeah that

was the that was the important part uh so we could we could ship uh we could ship it okay maybe not today but after a year worth of work we we could ship it so if we ever need to ship some stateless solution this is the the only thing we have on the other hand it's uh pretty obvious that this is not uh the perfect solution it's not the most uh ZK friendly solution it uh it is it was the most ZK friendly before Starks got very uh very popular but today using um binary fields um or smaller fields is uh is all the rage provides better performance so it makes sense to to look

at this uh The other the other thing is that the crypto especially the commitment is pretty slow. So it's not like we uh we absolutely need to do vertical or die. Uh it's just that it gives us a very good reference point to to compare everything everything else. And so we are back to the drawing board and we're looking at this that gives us the opportunity to look at a lot more options. Um so you have a um at least two um two uh dimensions that I think are important. Uh you have the solutions that are in protocol to the to the right and the solutions that are out of protocol to the left. Uh you have solutions that are completely uh

stateful and solutions that are completely stateless. And vertical is in the bottom uh left corner. It's completely state stateless and it's in protocol. Uh you have uh regular clients which I call status quo where we are today. Uh it's completely stateful and it's uh in protocol. You could uh think of several solutions in the middle. So there's VOPS. I'm going to get into this. There's state expiry and there's um there's a typo. It's a substate not sub state. Um, and of course at the very bottom you have ZK Stateless which is uh the thing everybody's excited about but

it's completely out of protocol. Although it's trying to move uh in that direction uh it's we're looking at several years of development before we can get there and uh that's also one of there's a lot of questions to be answered before we get that. So anyway, uh VOPS or validity only partial statelessness is something we started looking uh at this year. It's um about realizing that some machines on the network are just very specialized and they don't they do don't need to hold the entire state. They only need to store what as much data as they need to to uh perform their function. So if you

think of something like uh inclusion list like fossil which is the latest uh censorship resistant proposal um you don't need to you just need to to build an inclusion list you don't need to know the the state of a contract you just need to know what the balance and the nons of that uh function are of that account are and that's it. So instead of getting the the whole tree where like here the the account uh the account tree is in red and the storage trees are in cyan um you just keep like you delete all that and you just keep the nons and balance and that gives you this foot disk footprint of 14 GB. This could potentially uh hold in RAM. So you can uh yeah you you can function at a you

know in a degraded mode in a way you can't do block produ production with this but you can definitely uh do something useful for the network. So that's the first uh the first idea. There's uh the arbitrary substate approach where um this is left this is completely out of protocol. So this is the other extreme. You just delete what you're not interested in. So for example, someone's interested in this account uh and not this account. So they delete it. Uh this could be useful for example for DAPs who need to serve state or connect. They're only interested in uh in tokens. They're interested in user balances. Uh they're interested in their own state like the unis swap uh storage for example. But

they are not interested in stuff that they can't trade like uh you know some NFTs that cannot be traded or cryptokitty. I actually don't know if you can trade cryptokitties on on unis swap. That's uh that's a question. But assuming you can't, you could delete this. That's a lot of data you you don't need. Um and yeah, so I covered the idea what I call the the spectrum, but actually this is uh a bit of a like I would like to add another dimension which is very often overlooked in when you hear about all the great ideas uh of ZK statelessness. It's um decentralized block building versus centralized block building. Sorry, it's the other way around. Decentralizes here and

centralizes here. And you can see that okay the status quo it's um it's at the top it's still uh completely u decentralized block uh like the block building is completely decentralized but it's collapsed uh VPS can actually interact anywhere like for example uh centralized builder can al decide to keep uh so can decide to keep only what they want uh if they decide to censor transactions they can perfectly delete the addresses that they don't they don't want to keep and uh no one could uh could do the same thing uh could could prevent them from from doing so. Same thing with the arbitrary substate. Uh so this is not in protocol. So the builders

could say look if you're sending a transaction that touches this this place this address I don't like. I will not include you. Um and then at the bottom you have zk stateless and this is where the major difference is with with veral. It's that uh it's very centralized. Why is it centralized? Because to build those proofs, you need to uh you need a very powerful and expensive machine. And this is where you get to my controversial slide here. Um you have a risk of heavy centralization of the block building process. Why? Because like I said, you have um you know, you you if you go to eastroof.org,

You will see it cost 0.1 0.1 cent to build a proof. That's awesome. But 0.1 cent every 12 seconds. That's $300,000 per year. Who's going to pay for this? Any taker? Didn't think so. Um, so you have to find a reward somehow. You have to find a reward for every proof system, every builder, and they need to make at least 300,000 uh this year, right? If you have a validator, you know, for $1,000 about, you can run a machine and the network will pay will give you more than this.

So, you you break even with this. It's not clear how you do it. Um, so I think there's a big question of who's going to provide the proof, who's going to hold the data, and this is not answered. And I think what we don't want uh is go the Solena route. Uh you know like Solena, they're not stupid. They're not evil. They just chose performance over decentralization. And they're trying to get to decentralization, but that's clearly not their uh priority. The priority is performance. When we get to that same position, we'll have the same problem. doing uh ZK statelessness e things uh will I mean we already signaled we prefer doing fancy cool math

stuff over decentralization going back is going to be a challenge just like it is for Solana so yeah uh I think people should be aware of uh of this problem anyway that was how stateless could happen the question is the next question is when can it happen um I think in core development ment until now we have done a lot of uh we have always done things without wondering how or when they were needed and so we started this new effort which is called the bloat net and the idea is going we're going to take the current mainet and we're going to bloat up the state to a very heavy um very heavy uh weights uh in a in such a way

that you know the the state is going to be double the size four times this size okay Maybe maybe not 100 times the size because no no no machine on on earth can can hold this but uh we want to make it as large as possible. And this way we can see what breaks. We can see is is that snaps sync that that fails is it just the performance that goes uh really like that starts slowing down up to a point that uh that we can't just produce block anymore or uh verify them. Um and we once we've done this we want to to test it on every single EIP. So every time there will be a new AIP proposed, it needs to be implemented. It goes on the bloat net uh and we see what happens so that we can try to guess the future.

Um so yeah, so that uh with this we're going to have a stateless decision table or at least a course of action. What do we do uh when we notice like when when we determine that something is going to break like when we when we find a breakage point, what do we do? If it's today, it's vertical. That's the only uh that's the only way you you can handle that. If it's in two years, you can have we can consider binary trees with some hash function. If it's in five years, presumably the performance of ZK VMs will be such that we don't even have to change the tree. We only need the code chunking method. And I will explain what they are, right? Um and whatever you do at some point, someday the state will

just be too big no matter what you do. So in a 100 years you need to implement state expiry. So let's start with uh state expiry. Uh we have this uh we have this uh person working in my team Han who uh is uh looking at it. He proposed the first version of the EIP which was called the 7736. It's vertical based unfortunately. Uh it could be adapted to binary trees and it provides a lot of uh interesting results like we know most of the state. So the blue part uh is what would be kept after 6 months like if we expire something uh every 6 months this is how much state you would have to keep uh the rest you delete and if you need it again you need to provide the proof to the

builder that you used to own that state. The problem with 7736 is that it's very inefficient in the way it stores the data. So the gain even though the percentage of deleted stuff is really high the you need to keep markers in the database and it's not very uh it's taking it's still taking a lot of space. So unfortunately we cannot uh we cannot uh it's not really worth it. It's maybe you can delete maybe 20%. I forgot the exact number but it's it's really underwhelming. Um nonetheless uh we have a 100 year to figure it figure this one out. So uh the the work needs to continue and this is what we're going to to keep doing. Uh binary trees we

proposed a new uh EIP to do this uh Ignasio from from my team until tomorrow uh used to uh like created this this EIP. It's basically take what we learned from vertical trees and uh adapt it to binary trees so that we try to get the the best uh the best of both worlds. the size is probably still going to be much bigger than the MPT. Uh but uh we are in the process of finding out really if we can't find some uh some smart optimization to to make it happen. Uh the problem with binary trees is that uh it's still it it still has a lot of floating parameters. One of them is the hash function. People would like to use

Prooseidon because ZK friendliness blah blah blah. Uh but we are not 100% sure that Poseidon is really secure. So the EF is currently running some um program to try to get people to break Poseidon. Uh the problem being that until they do I mean we will never know that Poseidon the Poseidon hash function is very secure until someone breaks it. Uh but at least in 2027 we will have a good idea whether uh it's secure or not or it brings some measure of safety. Um but yeah and uh the last thing uh that I want to talk about is code chunking. So

we could just say okay we keep the MPT but the problem is the code size like uh developers uh want more like the the current code size is limited to 24 kilobytes and developers just want more. Uh if uh you know Vitalik has been talking about risk 5 is even less space efficient than the EVM. So if we start using risk 5 um the the code size is going to blow up by a factor of about four. Um so um yeah we we need to do something about this. Why? Because well first it takes more uh space in RAM. It takes more space on the disk. Uh but on top of that you need to uh also when you

if you want to do real-time proving you have to load this code and pass it to the ZQVM. And this is one of the best example uh of ZKVM of a prover killer. um is just that there's just too much data and that means you know the because you have all this polomial magic it blows up the RAM and uh it crashes uh it crashes the provers and for $25 we we have done that Ignasio has done that for $25 uh you can crash all the provers on east proofs um you know so $3,000 on one hand $25 um and uh yeah right and also if you want to do just regular inclusion

proofs, you need to pass the code on the size that's 300 megabytes at today's guest limit. Um, if you want to put it uh attach it to the block for, you know, the the inclusion proof for every every location attached in the block, that would be 300 megabytes. If you increase the gas limit as we want to, that's going to be even bigger as a as a worst case uh scenario. So what we do is yeah we currently we load the the code in RAM and we find out that oh we actually needed just this bit and this bit. So we loaded the whole thing for nothing and which is why the ZK prover attack is so efficient because you can have one very cheap interaction with the code but you still need to load the entire the entire

code. So the the answer is simple. you just cut the the code in chunks and you only load the chunks on demand as you need them and of course you adapt the the gas model to to reflect that you're loading uh chunks and this is this is what you need. So I forgot to mention it on this uh slide but we have an EIP uh 2926 that uh that is suggesting this that we're going to push for for Glamsterdam. Uh I think I went a bit uh fast but uh yes this is the end. Um so any questions? Three minutes questions. Yes sir.

In the beginning you had this sort of like three-dimensional graph where you had state expiry as being out of protocol. Yeah. Can you elaborate on what you mean by that? Because my understanding was that state expiry is always in protocol because you can provide back the state even once it's expired. Right. So I guess uh you are absolutely correct. It's uh it would be in protocol. I mean, okay, you there's an uh that that's why it's there because it's kind of confusing. I agree. Um you could have it completely in protocol. You could also have it completely out of protocol if you decide to do it yourself. And then when you need the state, uh you you go get it. You find it somehow. Uh and the somehow is why I would say it's um it's kind of pro out

of protocol. Yeah. Uh but yeah, okay, that's a good point. and it was confusing. So, thanks for that. Can you iterate once more on uh you said binary trees would be more preferable over two years. Yeah. Um not sure exactly what what would change in two years that will make binary trees preferable over trees and what's stopping us now? uh we will know what transition function is uh sorry what hashing function is uh is the best or at least we will know if poseidon is secure in about two years. So that's the

first uh thing. The second thing is uh for binary trees to be interesting you need uh you need performance EKVMs and in all likelihood we're not going to get this uh for another two years like I know there's big announcement of uh real-time proving but between the announcement and actually running them on a live network you have uh I'd say two years at least okay one last when you say chunking the code and the the object object format won't help to that. Um, help what exactly? And in the theum object format, didn't you can just load parts of the bite code? Um, okay.

So, I'm not an ef expert, right? But my understanding is that uh this was not part of the spec. Uh, like code chunking and eof were two separate things. Uh, they are in the Okay, I see. I understand where why you're saying this because they are sections and you could only load the sections that you want. Um, but the sections presumably are going to be much larger than the ideal chunk size which would be 32 bytes. So, okay, I get it. Yes, but we need better than that. Okay, thank you everyone. If you have more questions, please continue outside.

Thanks.