Trie Another Way: The new state trie and Ethereum’s State Migration

Transcript

Thank you. Um so um how how do you change the data structure behind every balance on Ethereum while Ethereum keeps uh using it and accessing it? Um in this talk I will explain uh the new state try we are proposing called the PBT and how we actually plan to migrate to it uh without stopping the chain. Um also I would like to make a shout out to C Paris uh from the EF uh who has been working um with me on on this project.

But before we dive in, I want to make a quick refresher on Ethereum state so we all have the right context. Um, you can think of uh state as Ethereum's database. It holds the current balance and nons of every account, the code and the storage of every contract. Every transaction reads from it and writes to it. And all of this is committed by one hash in the block header, the state route. um if anything in the state changes then this route changes and this allows validators to make sure that they observing the same state um as the rest of of of the network.

It also allows users to check a single piece of state against the root without downloading the rest. And we will see exactly how um this works in a moment. And this is used by some applications on Ethereum today. So the way that we organize state matters a lot. Um it decides how big um these proofs so these um checks that users can can can do to make sure that the state they are seeing is correct. How big these proofs are and how expensive it is to then uh update these this route.

So let's start with the first question. um what changes in this uh new proposal. So let's start with the MPT. The MPT is the current way um that we um commit to the state. Um it is an account try and then um the storage try per account um and the code is stored outside. So you can think of it as like a a tree of trees. Um in the new try is called the partition binary try or PBT. Um a big difference is that it's binary. So each branch has exactly two children and it's a single try. So all the accounts code

and storage live under a single route. The key space uh is split into regions. Um, so we have account headers, code, and storage. And you can think of them as like neighborhoods within the same try, not separate tries. And so let's follow now an account in the new scheme we have with the with a try. Um, we have a header. A header uh for an account accounts the balance, the nodes, and the code hash that identifies the codes that that account holds. um it sits right next to its uh 64 storage slots. Um so one short proofs covers all of this. So you can think of it as like

you are loading some information for your contract and by default it already comes with some preset uh storage slots. So you can hold there the slots that are most used by your contract. And then uh we have uh the storage key. So all the remaining storage keys after the 64th they go into the storage region of of the try and so first they are also organized by the account. So you have the account within the storage um neighborhood and then within that account you hold all the storage in its own um bucket and then additionally code is split into

chunks and is stored on the code zone which is different from today. So if you recall today we store the code outside of the of the try and this is also uh essentially addressed by the code hash. So if account A has the exact same bite code as account B, uh you are not duplicating the code. They essentially get mapped to the exact same code chunks. Okay, this is a lot of changes. Uh but how do we actually why do we even want to change it? Like isn't the current try working and good enough?

So to explain this, let's zoom in on how state proofs work today. So um let's say that I want to convince you that um account A has some balance. I send you the value and a proof. The proof essentially is a path between the account A up to the root. And uh not only it stores the each intermediate node but it needs to store also all the sibling hashes along the way. So that's essentially from that information you can reconstruct the root to verify that the balance is correct.

You recomputee the root from these hashes. If it matches the state route in the block heather which you already trust because you you you are observing the chain then the claim is true. Wallets, light clients, bridges, zk provers, they all rely on this and so the size of these proofs really matters. Today Ethereum uses the Merkel Puppet try or the MPT and in this design each branch has 16 children. So essentially we have uh to to prove one path you essentially need to also carry all the hashes of its 15 siblings at each level.

And that's a lot of hashes for a single balance. And it gets worse for storage as we'll see next. The account leaf holds the balance and the ns plus two pointers. The first pointer is the storage route. It points to a separate storage try for that account. So if it's a try of tries, proving a storage slot means chaining two proofs. And the second pointer is the call hash. If it points to essentially the contract code which lives outside the try. So if you want to prove a piece of code, you essentially need to prove the entire contract.

And so to summarize, there are two main reasons to switch. The first one and the big lock is smaller proofs. With a binary try, you only need one sibling hash per level. And so instead of having 15 at each level, you just have two. And uh also related data shares the same path. And we are designing the structure of the try. So things that usually would be used together are stored in the same place. Um and also we want to make this without making block execution slower. Um and so when while we are designing the try we want to make sure that actually benchmarking performance of writing to this new commitment scheme is as good as

MPT and we are but this is still being being benchmarked. Uh second, the new try is built to grow. So the key space is partitioned. That's where the partition part comes from. Um the first bite of every key says which zone it lives in. This is what defines that neighborhood. Today we only have three zones, account, storage and cold, and the rest is empty space. So future upgrades can actually use these new regions to introduce new types of state as um Mark in the previous uh presentation pointed to. And this opens the door to things like state expiry where state is grouped by when it was last touched. So old state can be expired and later revived. Also things

like state taring with um hot and cold state separation and they can be stored separately. Um there's a bunch of of of of future things we can we can do. Um we now have a new try but how do we move all of Ethereum state into it? Ethereum can stop for maintenance. So blocks keep coming every 12 seconds and the migration needs to happen while the chain is running. So what we do first we pick a finalized block which we call the anchor and we convert a state at that block into the new try.

Nodes can get the converted try in two ways. They can either download a snapshot or they can convert them themselves locally. Then everyone follows the same path. they verify that uh the snapshot is correct and catch up to the they catch up the PBT to the chain tip. So between the time that the anchor block was set and you actually loaded and verified everything some time has gone by. So we need to then update the PBT um to keep it um to bring it up to the tip of the chain. Um during this time the MPT route is still the same and is still being used as the main commitment scheme. So during the migration validators need to

maintain both the MPT and the PBT. And finally at the fork the MPT route is swapped with the PBT and as you can see the conversion happens outside of consensus and that's why we call it the offline migration. Um so uh what does all of these mean to you? And I will start going fast because I'm um oh no I'm still with some time. Okay. Um so first if you are a user there is nothing to do essentially same address same B balance same contract same history you don't notice if you run a node or if you are a validator you need to make sure you have some spare disk since for a while I would say a couple of weeks you need to

keep both the MPT and the PBT and you can use uh history expiry to free up some space if you if you need to and then you need to decide whether you want to download a snapshot or self migrate and then your client will do the verification and catch up for you. If you build dabs, your contracts keep working. The thing to check is whether you are using Ethereum state proofs. For example, light clients um oracles or anything using um ETH get proof. They need to switch to a new proof format at the fork.

And because the migration is offline, there is no period with a hybrid MPT and PBT. So verifiers just switch once at the fork. And um another thing to note is that currently we don't plan to have any gas repricings from from this uh because we want the performance of PBT and MPT to be or the PBT to be as good as the MPT. But we still need to do run we still need to run benchmarks and make sure that this is true. If there's some new worst case that pops up then we may need to do some gas repricings as we are doing in Glamsterdam.

Um and so to summarize for most users the migration will be very easy validators will be um a bit u more worried and I would say core devs as well. Okay. And uh just to summarize what you get out of it. So as users wallets can now verify instead of trust. So because state proofs are smaller it states proof state proofs can become a first class citizen in Ethereum. Light clients can check RPC uh answers with smaller proofs. So there's less bandwidth. Um and there's also some research on private reads where uh proof size matters a lot

for validators. This is a step towards lighter nodes. Stateless nodes and zk provers both need need weaknesses and smaller junctes help a lot. So this is also um a sort of path for partial statelessness for DAP developers. Anything built on storage proofs like Dow voting L1 data on L2s or crosschain reads they get cheaper to verify and but the exact savings depend on the query and this is still um TBD. So when is this happening? So if you know um Ethereum has or the EF has this straw map which is a a sort of uh plan of how do we think the next uh forks

could could look like. Um and um at this moment PBT is planned for AR. So this is we have currently we are working on the Glamsterdam fork which is planned to ship early next year. Then we are working on Egot and then Aar is the fork after that one. Um, of course the date is still TBD. Um, and even though we don't have a date, the work is already underway. So we have specs for both parts. So we have EIP 8297 for the try itself and we have EIP 8347 for the migration.

We also have already tests for the new try and test for the offline migration and we have a devet already with four clients GU Aragon nethermind and bezu they are running with a new try and we've already practiced the migration um with with these four clients um as I was saying we we run a a sort of migration rehearsal with these clients and we successfully migrated on a mainet shadow fork um with these clients and it was uh using uh hardware that was a bit below what the actual specs uh require. So it it was a real um let's say u proof that this can can be done.

Uh thank you so much. I think we uh have time for questions. Also, if you want to dig deeper, please you can refer to the two um EIPs and yeah, happy to answer any question. Okay, thank you Maria. Uh I guess we have some time for questions. Feel free to add more questions using the QR code. So the first question is uh why isn't the storage zone not hanging off of the account in the PBT3?

>> Okay. So if I understand correctly this question so if I don't answer to this please make another question. So if I'm understanding correctly it's like today the MPT you have the the account try and then the header of the account try has a storage root and the storage route is a new try. um in PBT there's a single try and then there's this storage neighborhood. The reason for this is that uh we uh figure out that this is actually um better from a commitment perspective to have a single proof. Again we are trying to reduce the proof size um and having this coupling between the account and the storage essentially means that we cannot process the the two

parts in parallel. Right? So if because of this coupling if you change something on the storage then you also need to update the account because now the storage route on the account um changes and so you kind of have to update the try for the storage and then also update the try for the account. With this decoupling then you don't have this issue. If you update something on the storage you just update the storage and that's it. >> Okay. So the next question is about the hash function. Uh what are your thoughts on Blake 2 versus Sketchak or any other uh alternatives?

>> That's a great question. So I would say currently the current spec is using Blake. Um the reason for that is that early experiments on uh ZKVM pointed that Khak was not uh fast enough to prove on ZKVMs. And this was one of the reasons why we were starting with Blake. But there's been recent developments and we actually now can prove catchak efficiently enough. And so we are actually planning on switching to a catchak hash um at at the beginning or in a very short time. uh the the reason why we haven't switched yet is that the cryptographers at the EF are finishing

their analysis and once they do finish their analysis and say okay catch will be the standard for Ethereum then that's um the hash we'll we'll use >> okay so the next question is uh what happened to veral tries >> right so veral was as just for context was a um an early iteration of this like trying to have a state commitment um tree for Ethereum. The reason why it was eventually uh let go was because of concerns from PQ. So essentially the design itself was not PQ resistance and so it really didn't work.

So it was great for it. This was a design that was really focused on state expiry. Um but then we realized that was not safe for PQ and so we we dropped and started to explore other designs. So the next question is is it possible to derive the PBT root from the MPT root? You can. So the only thing you need is you so with just a root no you need to have both the um let's say you need to have so essentially to to get to the PBT you

need to have all the data in the try. So you need to know account A has balance X and Y so that we you can rehash everything and calculate the root. Um so essentially just from the state root of the MPT you can't even derive the MPT itself right like you need to have the underlying data. What you can do is with the underlying data you can rehash everything and verify that the root is matches the data you have. Does these make Wait, does these make sense?

>> Yeah. >> Yeah. >> Okay. >> Okay.