The Verge: Converting the Ethereum state to Verkle trees

Transcript

foreign okay well I guess I'm gonna start so thank you for coming this presentation is going to be about uh an upcoming upcoming Fork which is called The Verge um so yeah for all the French people uh in the room I didn't pick that name um so what is the Verge The Verge is can I get that awesome thank you um if that works if it doesn't it's okay right so the Verge is uh The Verge is about uh changing the

format that ethereum stores its data in and we want to switch from a structure called the Merkel Patricia try or Patricia tree into a vertical tree so I've made many presentations about the structure of the tree I did it at nauseam really so I will only focus for this presentation I will only focus on the how the fork happens how the conversion happens from the MPT to the vocal tree you only need to know three things sorry two things about this the first one is the goal of this Fork is to create make blocks like self-contained execution units so you you get a block you do not need anything like any prerequisite you don't need to sync you

don't need to to do anything like this well you need to make sure of course the block belongs to the chain but that's pretty much it and the other thing you need to know is that in the current MPT every value is uh accessible through a key and the key is a hash of the address or of the slot number we change the hash function so we have to rehash everything and that is the problem because by the time the Verge happens hopefully next year there will be about 1 billion leaves in the tree that's a lot of data we cannot translate everything in one go we can definitely not translate that in one slot we're

talking about days if not month so um yeah like the point I want to make is there's too much data this change is very risky because it's effectively irreversible we could but there's no practical method to do this so I'm going to pre to present the new like the the method that is currently favored to execute this this conversion and it's called the overlay method if you've seen some of my former presentations you might have seen that I was at the time talking about another conversion method but there's been some optimization work recently by myself but more importantly by inesio Hagopian that really improved the performance of of

vocal tree execution and and the overlay method so now it's the favorite uh the favorite approach and how does it work well the idea is that you freeze the and the current MPT at a fork block and you lay a tree another tree which is a vertical Tree on top of that on top of that tree and so every right goes into that new tree and there's an extra twist every block we move we take n values from the tree and we convert them like we convert their keys and we insert them in the overlay tree and there's another difference with respect to maybe other Forks normally

you have a fork it happens at a given block a block height or it happens at a given timestamp and that's it now because of the the amount of data that needs to be translated there's a lot of data so we know when the what time stamp or what time or what height the block the the fork starts but we don't really know when the the conversion ends when the fork ends so it's uh it depends on how much data is present in the tree at the time we start converting so visually how does that go uh yeah I'm kind of in uh in the way so I'm going to present the structure of the yeah like how it plays out so you have the fork the like you have the blocks

and we have a block that is currently just before the fork and we have the that thing here represents the the current uh Marco Patricia tree at the at the height of the block and every blue square in the tree represents a value that was written before the fork so right now it's only blue squares um and the the red like m-like structure represents the inter internal nodes of the tree and the last thing is this green arrow it represents the head of the iterator because we're going to convert n values each time and because we do this we need to keep track of what has already been converted and what has not

it's getting more intimate nice um so you start at the fore height we start with a new block still trying to make some uh to make sure everybody sees it um the the new the new we start with a new tree the tree is a vertical tree it's currently empty but because it's vertical I used an inverted triangle uh to to represent the root and then we start executing transactions in the block and because these are new rights like either updates to the state or rights to value that did not exist they go directly into the the overlay Trader top tree and it's purple to note that those values were written after the fork

and then we have this uh translation process this iterator sweep that goes over the values of the MPT and here uh n equals 2 so we only convert two values that we move into the the overlay tree and the head of the iterator moves by two then the question comes what if we want to access data that was that is not present in the vertical tree but is present here in the in the MPT well first we hit the vertical tree to see if a newer value was not present and if no if that value was not found as is the case in this example you have to

hit the MPT and find find that data there of course if you don't find it that means the data was never present in the state so one point before we continue that means that you need to read two trees instead of one there's going to be a consequence for that in terms of gas but so okay after that the process repeats we the iterator moves by two more leaves and uh for whatever reason this uh some value that was converted before got overwritten so we have an extra purple uh purple Square and the interesting thing is once the the fork block has been finalized we do not really need all the internal nodes

so they can be deleted so we can save some space it's not completely true because those internal nodes are very useful for snapsync but in most likely like you know where what we're gonna do is make it uh an option that needs to be willfully activated so people who really need it will find that they need to activate this option to delete the data most people who never read the manual will keep serving that data and that will be great but of course if you want to be um you know if you're a big operation and you want to make sure that you can still snap sing during the during the conversion you will have to make sure that you have your uh your node that you can snap sync from at any time anyway so

um eventually The iterator Sweep covers everything and we can therefore delete the MPT because all the values that were in the amputees npt have been converted so yeah how does that fare um not great um we have uh okay so first of all it's actually not true this this thing is a week old we manage I mean especially in yasu has managed to make this much faster um but by the look of it what we can see is that 10 000 leaves you know it's um it's manageable but it's it comes out of cost this is only a problem if you're

going to full sync because when you full sync you have to do this n uh iteration sorry this uh n leaves conversion thing as you as you think so it probably adds two weeks to one month into a full sync which is kind of crazy but no matter the method you choose you will have to do something similar and the other thing uh is that thankfully it does not really affect block production so if you're already following the chain you have this uh like the slot is split into 12 second sorry a slot is 12 seconds but really everything needs to happen for four seconds and then you have eight seconds where it's kind of more idle and you can use those eight seconds to prepare start converting the

leaves for the next round and that's actually you know with 10 7 leaves on an average machine uh you can do this conversion the those this n block transfer in line one second so as long as you can fit one second into eight seconds seconds you don't really have a problem um okay no more response from the okay um so what timelines are we looking at well if we choose to transfer 1000 leaves it's gonna take six months quite long uh if we pick 10 000 it's only going to be 15 days so that's much more acceptable but why not try to you know why not buy

the buy the bullet and translate 1 000 leaves in one go well the problem is that there's a trade-off the more leads we transfer while still trying to to follow the chain like if you get over those eight seconds you will fall behind and the question is how fast is your machine can your machine indeed translate for example 10K in eight seconds and you still have a bit of slack in case something goes wrong um we see that some machines like uh I mean I will get I will talk about this next slide but some machines have a hard time following others yeah have no problem so we have this in this model here we have the the blue line here that represents the target of

one month and it tells you how many leaves you need to translate per block given the amount of um given the amount of nodes that drop off the network and still make the target of one month so basically if you're above the Blue Line everything is fine you will hit one month if you're under the blue line it's getting um it's getting less likely um what I mean is this is for so what we see is for example the the 5K line which is the red line uh we'll tell you that we can still reach the target if we lose about five ten percent of the nodes and if we translate ten thousand leads per per block uh we can still hit the target with uh half the network of course this

is just how you hit the target if you start losing half the nodes on the network it's not going to go well so document results um on an reasonably old AMD 64 machine we get like we can handle 10K that's not a problem the problem comes with The Rock 5B and all those cheap arm machines we got some optimizations like recently as in yesterday that seemed to point out that 5K May 5 000 leaves per block is possible um but yeah we we want to make sure before uh before we go we say okay it's 5K and everybody has to has to accept

that uh when you when the conversion is over you see this message the elephant is landed so what's the connection with this presentation absolutely none uh it's just that we are in a process of selecting our spirit animal every Fork has a spirit animal uh I'm just campaigning for the elephant but so when it comes going coming back to the method um it's like here are the like the greatest the great Advantage is that whatever code you write for this uh for the for this for this transition can be reused in sync more importantly what happens is that uh all this conversion happens inside the consensus

so if uh if we are doing um uh if if one of the clients has a bug it will immediately appear there will be a chain split we can intervene and fix it a lot of other methods don't have this this uh this propriet this property and also quite important in case you find a bug you can because it's part of the consensus you can interrupt the conversion upgrade your uh your client and uh resume it and it should uh it should reorgan and continue the the conversion and all the code that has been written will be reused uh it's not like code we've read once and and forget uh uh yeah like and have to maintain even

though we never use it again and yeah the the problem if we look at the the drawbacks of this approach um it might be that some low power machines will drop off the network so if you are a home Staker with a rock 5B we're trying to make it work but we can't promise it at this time um and because I was saying the full sync is a bit is going to be a bit slower um you know if you have to interrupt and you have to rejoin it might take longer than it normally does it's not great but it's manageable and the last point that I already touched uh upon is the gas we have this period in which to read some data you potentially read uh two trees

like you go to the vertical tree and then you go to the next tree the problem with this is that we have to double the price of the gas otherwise something gets subsidized and can be attacked so what we can do with this approach if it's short enough we can say well too bad for a month uh the gas like the cost of a read is going to be double what it currently is too bad yeah it's a it's a pain uh but uh that that's how it is so we can have a simple solution like hand wavy solution if um it's longer than this we're gonna have to find something better and I'll get back to this later but that's that's not good news

so were there other options uh yes that we looked at one of them is called the offline conversion that was the previously favored option uh that Julio here excuse me worked on congrats um and what happens in that case is that instead of one fork you really have two you have the like you you have to decide the convert when you start converting because even though the conversion itself is done outside of protocol by some very uh powerful nodes everybody has to agree for some reasons I don't have time to explain

and then you have another Fork that which is when really vertical trees come into existence or official existence so what happens is you have two here you have two chains one of them is going to be stopped for conversion and the other one is going to follow and try to go through the fork so add the conversion height the the chain on the left stops and starts converting the data in in bulk while the other chain continues and then when the conversion ends we have a state vertical state that is a translation of the other um but it's kind of a counterfactual history so there's a few uh a few folks that were I that were not activated so

it's it's a beard it's a bit of a weird State and it's a source of a lot of bugs um and then so one when the data has been downloaded by uh by everybody else on the network they replay the blocks to make it uh to to catch up with the head and they have to do this before they reach the the actual for height because when that happens the vocal tree uh chain becomes the official one so even though it's been kind of like there's been some kind of of cheating like there's been a translation that is not really a really kosher um we we have to continue with this and we give up like with the the MPT chain

dies out so of course there's a lot of problems with this approach one of them is you start downloading the data yeah I don't know if you guys can read it so it's a bit difficult but you start you have to download 600 gigabytes of data for example you start replaying blocks past the final finalization point and then someone tells you oh by the way I converted uh I you know I stole all your board apps or whatever what do you do either you know if it's uh if it's just the Apes I would say too bad we we find a social way to compensate for the for the mishap if everything uh if all the funds of everybody have been stolen we we have a problem and uh uh yeah we

probably have to make a very painful reorganize reorg manual reorg and everything in between is basically uh Dao hack style uh you know social Fork uh yeah like this is a situation we don't want to be in basically and the other problem is indeed that all the code that gets written it's it's written once and then we need to invent a new sync we need to to uh to create special code again so um given how much time I have I'm going to skip on this one but basically it's the same thing except everybody does their own offline translation so it's the worst of Both Worlds and I'll finish with the state expiry

and the state expiry uh it's exactly like the overlay tree but uh you don't translate any leaves um during uh during the block so you keep the MPT forever well supposedly Forever Until hopefully someone in the future comes up with a plan to implement State expiry at which pla at which point you forget about the the MPT and if someone needs something that was in that MPT they need to implement that they need to provide some proof that it was there uh but like I said this um this protocol this uh this feature does not exist yet so we're basically kicking the can down

the road and like I was saying uh there's the problem that if it fits for a month we've been we've had months where gas was expensive so if storage uh if the storage price is twice as expensive for a month it's okay I mean it's not great but it's okay if it's for potentially two years with no or even more like if there's no end in sight we definitely make something we need to make something that is a bit more fair so that means we need to make sure that if you hit the vocal tree you only pay the price for the vertical tree if you hit the MPT on top of that you need to pay more but that means that the gas accounting layer and and the three layer need to be integrated more tightly

and that is going to be an implementation nightmare so that would basically be the the Doom of this of this method I think and uh with this I will invite you to visit vocal.info and I think we do have some time for questions [Applause] oh okay I can only do like two questions so we've overlay method you present it first that is your favorite one for now unless you turn on the specific flag you

mentioned we would have to keep this entire Miracle partition tree until the translation is over and when the elephant finally lands we would drop this entire Market Park trick or treat just in one one apoc basically one slot uh well no probably not in one slot because they would kill the database performance but it will uh yeah there will be there will be some cleanup process okay my question was about the cleanup process yeah affecting the node basically well I mean it's not it's not actually that hard because we I guess we could just delete the entire directory um yeah I'm gonna say uh probably probably not but that's yeah that's a that's still an open question I guess yeah did you consider to use ZK tools

for the synchronization because you would have a logarithmaker time of verification of the node yeah or may not could do the proof and then the very flying nod just uh synchronized by a verifying the proof in local Richmond which would solve the fact that okay one one that could perform it and the others are just yeah absolutely so did we consider using ZK tools yet absolutely uh there are a few problems with this um the pro the first problem is that uh the currents the current uh MPT is catch Shack it's a horrible uh right um okay now maybe I misunderstood you have to switch

right uh but yeah but you still need to to prove the the source to prove that the the result is correct so that's the first thing and basically the whole point of vertical three is to make it is to make the tree vocal friendly sorry uh ZK friendly but because we don't have the translation yet that would kind of if if we made that translation if we made wrote that proof might as well make it uh ZK directly not not bother with the vocal tree okay that's it well thanks [Applause]