Everything you need to know about state expiry - Wei Han Ng

all right so um just to introduce myself I'm Han I'm working for nine so for today's topic this topic is going to be more on call protocol like the technical stuff on ethereum so um hopefully it's not very boring to you guys who are not might not be te non-technical but I'm going to try this um make make this session as beginner friendly as possible so I'm going to talk about everything you need to know about state asiry with the problem that is trying to solve the different solutions that we that we have had throughout the years and also the evaluation of different those Solutions so without further ad do let's start right away with like just understand um huh what is the state so when we talk about State on ethereum uh we are referring to the uh MPT uh of the world State on ethereum right which is a MCO P try so on interum a state is represented by two layer MPT so the first layer is account try and down down there the second layer is the so-called storage try or the contract try so let's start with the account try so at the leaf note of the M try which is the data structure you have the account object so on ethereum you have two types of account the first type of account is called EA acally own account and the second type of account is called contract account so um now um let's move on to the second layer um so yeah so for each contract account it will also have has his own um M try so uh it's the same try as well just um the leaf note here will represent the value to the slot of the contract so one key thing here that um U you have to understand is that the number of slots can So-Cal infinitely expand up to 2 to^ 256 so to give you an example of how large 2 to the^ 256 is basically is almost the number of atoms if not more than number of atoms in the universe so that's why I say it's infinitely expanding and um at the same time the number of accounts can also infinitely expand up to two to^ 256 so when you combine this two information together basically just states that the state on ethereum can grow infinitely just keep growing growing without stopping and under the hood when we talk about um software implementation basically the clients like go ethereum or like NE mine um everything is represented in the database as key value pass usually so um for example here just a very simp for example the you will have the account hash which which will map to the account object or you will have a SL slot hash which will map to the storage slot value so you can think of a key value pair as a um data representational unit um in the like a software level yep so when ethereum started with the Genesis block block zero it has a set of key value pass as time goes on even now when we are talking the key value pades number of key value P just increases es and right now I think um ethereum has about 1.2 billion to 1.5 billion key value pass which is which is still going to increase in the next few years and this phenomenon of like State being um keeping keep increasing and the number of um key value PS increasing is known as the state bloat issue or the state growth issue um so why state blo is bad right so let's say the state of ethereum or not just ethereum any other blockchains grows larger it will cost more to operate a node right right now let's say I'm a home Staker the recommended Hardware requirement to run a node is uh about 2 terab SSD next year or two years later it might increase up to 2.5 or two or three terabytes um and down like a decade later you could be like 10 terabytes who knows right so as a home Staker you would naturally feel less incentivized to run a note because you have to keep upgrading your software from time to time right so it's just not feasible and when there's when when um people like less people want to run a note eventually it will lead to like centralization because those people who who will run a note are the ones that has the financial capability Financial incentive to do so and it's not just about this scenario of like centralization or less people running notes it's also about performance of the chain so to quote um Peter from go ethereum um ethereum isn't slow because of Gap ethereum is slow because the state grows like crazy so um even no matter how much the client um the client teams optimizes their software the state of ethereum puts a bottleneck or a cap on how fast the um software can be right so um if we want um ethereum to be a super performance chain this is the problem that we need to solve first so um let's look at a few solutions that um clients have done to optimize their software in order to tackle this so-call State issue um the first um feature that I'm going to talk about is by go ethereum so again it's it's going to be very technical but um I'm going to simplify this so they have released a feature called path based State scheme and previously um the state scheme that they use is called hash base what's the difference between hash Bas and path base to put it simply when we have the hash Bas State scheme if you're running a note you will have to do something called offline pruning offline pruning means that U let's say you run a note for a few months continuously you have to stop your note and execute a certain command to do offline pruning after after that you have to start a note again so this operation is called offline pruning right so in terms of user experience it's um it's really bad because you don't expect um um we shouldn't expect users to um stop the node and execute a certain command to do something um and restart it again every certain interval ideally um users should um let the software keep running until for example uh perhaps if the client releases a new soft new version that's better then it makes sense for to upgrade the node or if maybe that's hard frog right then it makes sense to restart the note again my this case it's not so for path base um it solve it solves this um issue of like having to restart the node to do offline pruning and it's also per uh improves the performance a little bit um so that's go ethereum next uh we will go to neine oops yeah neine um n has three approaches that they have tried right or we have tried um so you can scan the QR code to read the article to to learn more about it but I'm going to go through like each of them just as a summary so the first approach is called paprika so paprika is an experimentation storage engine specifically for ethereum state so right now the client teams are using um um for the databases is always going to be key value pair database um so for example levels DB rocks DB or kosb um but why use a generic key value database when you can just rebuild one specifically for ethereum it's going to be more performant so that's paa the second approach is called a path-based storage so um it's exactly the same as gum one and the third one is called half PA so a half path is an approach that is in between um hash based State scheme and um PA based State scheme that's why it's called half paff and it's more like a database optimization technique uh where how it works is basically um when we talk about try Noe MPT node uh in the database level you are representing the node as key value pair so you map the hash of the trode to the actual trode object so instead of you um using just the trode hash as the key you Preen the um trode hash with the path to the TR so by doing this um because of how the inner workings of the databases um work you can actually compress the database right so it's really like a database optimization technique so yeah um these are the approaches that NE mind took but you know nonetheless optimizations are great but they don't solve the root CA which is State blow right so um no matter how much they optimize it um we if we want to solve it we have to solve it at a protocol level and when we want to solve it at a protocol level let's go back to the first principle and really ask ourself when we look at the number of key value PS right so that you have a bunch of like key value pads right now on ethereum is going to keep growing but how many key value PS are actually being accessed like in the past 6 months or past one year or two years so I asked myself this question about last year and I did an analysis and the result is that only 20% will access in the past one year and the 80% was left untouched and it makes sense let's say um 5 years ago you were just orted on ethereum um as a junior or as a beginner you were excited to deploy your first contract on chain and you deploy it but what's next the the contract the data is kept on chain but you you no longer using you're no longer using it and it's just dummy just dummy data is useless data and it doesn't make sense for us or for the no operators or for the stakers to continue to store this data and we want to find a way to remove them but at the same time if few years down the road you remember hey I want to access back my contract that I've just deployed 10 years ago can I do that and the answer it should be yes and actually it must be yes and so all this things converges to a single goal which is to how can we remove unnecessary state but provide access when needed so when we think about this goal um there were a few Solutions um that come out to solve State blow and also to achieve this goal so we're just going to talk them through one by one so the first solution is called State rent or blockchain rent as quoted by vitalik about um 8 years ago so how it works is um simple right now when you are submitting a transaction um you are paying a onetime fee to put your data on chain um after the state Ram model if you ever implement the state Ram model you not just you have to pay the onetime fee but you also have to pay a rental fee right to keep your data on chain um for a longer time right so this particular State model uh has already been introduced by um Solana so yeah and let's look at Advantage right so the advantages are okay feral cost distribution because right now yes we have still have state blow but um it makes more sense for the validators to keep the data because they are getting paid for it and it also improv like Resource Management because right now contract developers you have you have to um think about this rental fee model and for the cons right in terms of ethereum it I would say is um very difficult or close to impossible to implement such a model because um for example EIP 1559 has already caused such a controversy for the entire ethereum Community even though I believe is beneficial um if you ever want to change the cost model again for ethereum is going to cause another round of controversy and at the same time this particular um cost model is um is like a taxation additional taxation for the contracts so I personally believe that the community wouldn't uh support this um even though it might be beneficial for like solving the stable issue um and if we ever implement this as well um there are certain there are many things that we have to take care of like um when Legacy I mean for for legacy contracts or when contract developers develop their contract they never account for this top of State Rand model in the future right so how are we going to deal with this um situations so just overall is um going to be a very bad um user experience issues especially for um contract Developers then next we're going to look at another um solution called Regenesis so this was raised about four years ago how it works is that um we will delete the entire State and we only Remain the root hash of the um the state which is the MPT and then we do this every certain interval so I'm going to illustrate this with an example you have the state right with the root and the root hash uh after Regenesis you'll Wipe Out the entire State and you only Remain the root hash and let's say if there's a transaction you want to uh access the um State again and you want to do something with it a transaction right now should contain the operation to change a to something else and also the witness so the witness here I'm referring to an MPT proof a proof that states that um this particular value exists in the pre- Regenesis state so with this um after validation um that the witness is correct then um you can append this state back to the um the current state and do the operation with it so we repeat this every certain interval so the advantage here is that it's super clean right so um we know we we know that there's a certain limit that ethereum state can grow up until right and every year it's going to just restart the con here is that um the state needs to be stoed somewhere um for whether it's a centralized solution or decentralized solution like ipfs or portal Network um um why it's because people still have to access those pre-re state in order to create a weakness and the second most important one is large witness size so when we think about MP proof the size could be up to megabytes in size that's the worst case scenario but even in the worst case scenario um it's still not feasible right I mean um if a transaction can already contain few megab bytes in size of like witness uh witness then how about like 100 transactions then if you think about implementing this in at a protocol level is impossible um that's why we need tree which I'll explain more later um next is um statelessness so this is the current um direction that e heading towards not just to solve State blood but also for other Ben uh benefits as well um this particular scenario is aiming Target towards like how it might be able to solve State BL so how it works is that let's say you have epbs which stands for andrine proposal Builder separation you basically separate the validators into block Builders and block validators block builders will require the full state for witness creation and block validators can validate block seatless which is what we want so how it works is something like this you have the Builder with the fill State this Builder the only job for this Builder is to create block and also create the witness right so when you have this two information it can be sent over to the block validator and only um with the block and the witness without the full state it can validate that okay this is correct and it can um append this block to the canonical chain right so you can see here the advantage is very straightforward block validators have lower Hardware requirement because all the heavy lifting work has been done by um the block Builder right so um we can even reach a point where um if you are a block validator you can run the software with your phone right so this would um encourage everyone to you know be a home Staker or home validator um then for the con here is that it actually doesn't really solve State blow um because if you think about the full State it's it's we're still going to have like the state blow issue it's just that only block Builder have to deal with this issue and um eventually this will relate to centralization because not the number of um validators block validators and the number of block Builders doesn't match and only a few would want to become block Builders um in in the future yeah and also it requires epbs which is a research direction that uh has been taken seriously in the past few years but um we still is it is still a prerequisite and finally we move to state asiry so this is what I think is the most feasible solution when it comes to solving State blow at least for now and even Under the Umbrella of State expiry there are a few variations which are talk about it so um the first St aspir proposal was raised by ralic about 3 years ago so how it works pull it very briefly is that you create a new state try at fix Epoch so right now you are shifting from a single um world State into multiple Epoch based World state or multiple Epoch based try so um a state is considered as expired if it doesn't exist in the two most recent Epoch right and if you want to resurrect or access the expired State again you have to provide Witnesses for it so this is the very brief summary on how it works so um the pro here is that yeah um if you have this such a model you are guaranteed to remove still state but the con here is that it's extremely complex first um you require something called address Bas extension which is a research direction that hasn't been has been stagnant for quite a few years uh and it's also going to cause some level of controversy um um for like the ethereum community because you are doing breaking changes right it's going to affect um user experience in terms of like I think wallet um so that's one and the second thing is that when you are shifting from like a single tree approach to multiple tree approach um how clients are going to modify their software in order to deal with this um it's going to be a huge refractor when it comes to like their state modules for all clients I believe and the third thing is that uh the resurrection Logic for this particular proposal is extremely complex in the previous like solution that I mentioned the witness here usually refers to like just a single M Petra proof or mer proof right but here you are not just going to proof like um one thing you you also have to prove like different things perhaps you have to also combine the proofs together so if you check out the original article is actually extremely complicated and that's why I believe like this proposal has been stagnant um for the past few years as well but nonetheless it still um inspir us to create some other proposals um yeah the next solution is by BMB smart chain or more commonly known as binance smart chain um last year so I was involved in this project when I work with them um how works is that uh we introduced an overlay tree mechanism called Shadow Tree Shadow tree so this Shadow tree is like um a metadata layer for the current MPT so this Shadow tree the only purpose for this Shadow tree is to determine if a state is expired or not um yeah so for the pros it's a sing Tre approach as compared to the previous one and it's also guaranteed to remove the stale state but the con here is that it's very very straightforward and why BMB doesn't implement this is because large MPT witness size um so if that yeah that's why um the BMB Shain team uh would never put this um on chain um next we finally reached a point where um um this is I think the most suitable Solutions as of right now when it comes to like um state aspir or tackling State bu in my opinion um yeah so EIP 7736 so this was written by me and um gum from um the EF team or go ethereum so he's leading the state um stateless team and also vry on um on ethereum so um just going to go through how this a proposal will work and why it why it makes sense right so um first thing here is that um there's this new concept of State Epoch that we introduce um for for this um state asiry so you can think of a state Epoch as the measurement unit when it comes to determining how um how long a state is considered as active right so um in our proposal we consider a state as active for as long as a year or two State Depo right so that's the only thing that you have to remember and we are also going to um implement this during or after voal tree if we ever want to be uh enshrining this into the ethereum's protocol and there are bunch of like good resources out there about V Tree on why we want to shift from MPT to veral tree you can check out uh veral doino on your browser to access more resources but to give a brief summary on why we need veral trade is first um smaller winess size much smaller winess size just now I mentioned that MPT proof size could be as large as like in megabytes but in um voal tree it could be just like kilobytes right which is much more feasible to implement it for the protocol and um he also enables like different features like stess clients on like um vocal sync which is like very fast sync right so you can check out the resources for to learn more about vot tree but here here just going to go through how veral tree structure look like you have the internal node which is the which is um similar to mpt's Branch node and you will also have a new note type called like extension Noe and leaf node right so you don't have to care about like how voal tree work but one thing I'll like I'll place your attention to is how the values are being placed together right so in veral tree u values are actually grouped together in leaf noes right you can um see the green ones so this is different from any other structures out there even in binary try or like in MPT um so voal try or voal tree has this grouping property so how can we utilize this grouping property to implement the asiry and the answer is fairly straightforward right the only thing that we do um that that we change um in terms of like the vocal tree structure in this proposal is basically to add something called last Epoch to the extension node and that's literally it like that's literally the only change that we make to the vry structure and this last art is going to be the metadata to determine if a state is expired or not and we'll see how the state aspir logic work in the um next slide so how it works is that for every right event the this last Epoch field is going to be updated with the value of the current Epoch and for any read/ WR events if the current Epoch is greater than or equals to the last Epoch plus nonactive EPO in our case is two um a read right event is reverted because the trode is deem as expired so to put it uh with an example so let's say the current EO is three and one and for this example the extension note for the extension note the last EO value is one so that means um this particular group of value U group of values weren accessed in the past one year right so um what we can do is to mark it expired and prune them or delete them from the software or from the client right so after expiry what uh is left is only the commitment of the expired extension node so commitment is basically like a hash right so just looking at this illustration you can really see the effect of the state asiry because we are deleting data in this case um so to in order to resurrect um the value uh we introduce a new transaction type called um resurrect TX type so this new transaction when you are trying to resurrect um a a value an expired State you should provide um the path to the expired note the last EO value and also the values in the uh Leaf nodes so because you are trying to resurrect something that has been expired so you should also been uh get charged for it in terms of gas and to um validate the transaction is also fairly straightforward you can reconstruct the expired note from the resurrect transaction you then calculate the commitment of the reconstructed node then you compare the commitment with the one in the vco tree and if it's the same then it's valid then Resurrection is completed and in terms of like proos and cons um the pro is that again it's very simple to implement um no no ASC is required smaller WIS sizes um Single Tree instead of multiple perries comparing to the previous proposal smaller res reaction proves as well because you are just going to provide the necessary data um clear gas cost and is also forward compatible um because ASE or if you want to ever have like ASE or like um multiple traes they are still possible and but the con here is that not all steel data is being removed because there will be a certain case where if you have a group of values um let's say only one of the value is being accessed um actively but the others uh weren't access at all so uh in this scenario this group of value is still will not be um considered as expired so yeah not 100% effective but we have to do an analysis on um how effective it is on real minet data but yeah um a summary right um so we are sort of at a point where everything is kind of fine even though the state is growing like crazy but we might be eventually reaching a point where um the um things might get a little bit shaky and home stakers might not be able to deal with this the the state growth anymore so um and we have also look at like different solutions from like Regenesis um State rent statelessness and different variations of State asiry um each solution um it has it own tradeoff right the they are not perfect at all um some would not be very effective some would be very complex with Implement some would also affect user experience but nonetheless I think um why I wanted to have this um talk to illustrate all of the solutions is to raise an awareness because I believe not many people is working on this research area so yeah hopefully um it spark some idea on how to like tackle State bu and state growth in general and I guess the final code is you know less work towards making ethereum more sustainable and enduring for Generations all right thank you all right thanks very much are there any questions now I wanted to ask about your opinion on a like very simple solution right so you said 80% of blocks or transactions were not recently used right I imagine most of those are probably in old blocks correct me if I wrong so you I would imagine that just light notes right is synchronizing uh recent some portion of the recent blocks right and then perhaps some offchain service kind of load balancer that uh is delegating you either to light note or the full node based on the uh based on the thing that you want to interact with what do you think about this yeah I think the concept of light notes um they it exists but it only exists I mean they are good for like a very specific purpose here but um when we talk about like solving State Lo completely we want to solve it for validators so that means that um if we let's say can reach a scenario where light notes can also validate blocks and and transactions then that would be an ideal scenario but to do that for now you would require the full state right so it's not possible to have light notes to be able to validate or even though they are good for other purpos right um but that's why um I say that there's no choice but to actually deal with the full at the protocol level yeah all right thank you very much and one more round of applause please [Applause]