EL Data structures | Gary and Karim

Let's let's get into it. So, thank you so much for joining everyone, especially U Gary Karim, thank you so much for being here. I really appreciate you joining us today for our last week of the study group. This is the very last week. We have a last two sessions this week and this is the first one.

Uh we had uh Michael from Lighthouse uh speaking about the consensus layer data structure last week and we follow up on the talk with the execution layer data structures today and um we have real experts here today uh Gary and K from Bessu who've been working on um uh the bonsai and their implementation of the merricia tree. So um I'm excited to learn from you guys the overview of the of the data structures and all kinds of different structures and the different kinds of clients. So yeah, thanks so much for being here. Um Gary or if you want to start uh feel free to go ahead, feel free to share your screen if you're ready. Yeah, sure.

Um, so I put together a uh see. Oh, we got a grant grant permission. I think that should work. Okay. Yeah, it looks like that is working.

Um, yeah. So um we're going to uh explore the Ethereum execution client state uh and kind of the different uh solutions and implementations that have evolved over time through the different clients. Um as Mario said, I'm Gary. Um I work on Basu as a core dev and uh Kareem is joining us as well. He's uh really our deepest subject matter expert on state.

So he's here to make sure I don't make too many errors. Uh and with that uh I think we can start. So um the Ethereum state has remained largely unchanged since it was originally specified in the white paper in 2016. Um but the that's to say that um the Patricia Merkel tree has remained largely unchanged. There's work a foot right now to uh to move to veral trees or some other vector commitment strategy.

Uh but what we're going to talk about right now is the the current mainet uh Patricia Merkel tree implementation and how the different clients implement that. Uh and you know despite the fact that the state implementation spec hasn't you know changed since 2016 the the implementations in different clients definitely have evolved over time and really different today the execution clients really differentiate themselves uh by their state implementation. Um I'm I'm viewing the uh presentation here that I'm sharing. So if there's any questions or chat, you know, feel free to u Mario just to interrupt me or or if we want to feel free to interrupt along the way if there's something you want to ask. Um but yeah, I can't I can't see any questions, so just let me know.

Great. Um yeah, so I think what we want to do is start with an overview of Patricia Merkel trees. You know, since this is they've been around in Ethereum since 2016, there's a lot of resources on the internet that talk about how the tree is structured, how the hash commitments work, uh and so forth. They're, you know, varying degrees of depth and quality. So I don't want to like belabor that point too much.

Uh so but what I do want to do is just kind of give you a um at least a primer if you're not already aware of how the Patricia Merkel tree uh is specified and works. I want to give you an overview of how it works so you can understand uh the different implementations and why why they are the way they are in these different clients. So um just quickly um a patricia tree is a prefix tree uh and that means it's compressing the edges of the tree to try to minimize the depth of the tree as much as possible. You want to keep the tree as as shallow as possible. Uh you might have seen prefix trees like um a good example is like uh how to store all the words of the dictionary in in a single tree structure.

It's kind of like one of those classic interview questions. You might be familiar with it in that regard. Um Ethereum's Patricia Merkel tree also has you know the Merkel aspect where uh Merkel trees are a type of hash trees hash tree that allows you to commit to the contents of the tree in a in a secure verifiable and succinct way. Um and lastly, the Ethereum Patricia Merkel trees are hexary, which means they have a branching factor of 16. For for each node of the tree, it can have as many as 16 child nodes below that in the tree.

So when we when we put all that together, we have a hexary b uh prefix hash tree. And I think a good way to uh intro to you know overview what the how the tree is structured is to look at the different data nodes themselves. The nodes that are involved within the tree. Um we can add the kind of cryptographic hash commitment stuff on the examples as we go through this. But you know since we're doing an overview I think it's good to just kind of look at the the three different types of nodes you'll you know encounter in a Patricia Merkel tree.

Um you have branch nodes. Those are the you know intermediate nodes within the tree. They don't store data directly. Instead they are like a the branching factor. This is the the hexary portion of the Patricia Merkel tree.

Um there are extension nodes. Uh they compress like in this diagram these are the extension nodes. They compress some portion of the key space. like if you have a deep section of the tree that doesn't have any branches until you get some significant depth into the tree and then you get the path differentiated for for these leaf nodes that are in there. Uh what that's going to do is it will compress that path space so that you don't end up with an unnecessarily deep tree.

That's kind of the patricia portion of the Patricia Merkel tree. And then you have the leaf nodes. These are the things you actually are storing in the tree. this is the data that you really want to store in the tree. These these other two node types are really just there to facilitate um you know tree traversal and uh the the proving of the state.

Yeah. So again the the tree provides succinct verification of state uh and it allows you to prove some subset of the state. That's the really the Merkel portion of the Patricia Merkel tree. So looking at branch nodes to start. Um branch nodes as I said those are those intermediate nodes that link the keys and paths and they contain hash references of their child nodes.

U they're hexary. This is the hexary portion. There's they have as many as 16 child nodes. What the actual data node data that's stored in a branch node is an array of child node hashes. It's not like pointers to the nodes.

It's actually the hash of the value of the child nodes. So when you look at this branch node uh in a logical fashion, you can think of it as like a an array with 16 slots. So it's hexary. So 0 1 2 3 4 5 6 7 8 9 abcd. You can think about those those addresses in the array as u indexed by a hex digit.

um they provide uh they actually kind of define the path through the tree. So as you're branching through the tree, you will go to like the A slot or the zero slot and you know traverse through the tree in that manner. Okay, that said back to extension nodes. These nodes uh they as I said compress the access through the tree. They collapse some portion of the prefix that doesn't have any branches.

Um they minimize the tree depth. that keep the tree um as succinct as possible and as shallow as possible and it reduces you know effectively reduces the read and write amplification. So if you had to have a node that was I don't know say 16 layers deep but you could express it as just an extension node to just a couple of leaf nodes you can minimize dramatically the amount of read and write that you're doing to that tree. So these are all these are all just specified in uh the Ethereum white paper for how the Patricia Merkel tree works. Uh and then finally uh the leaf node itself.

This is the the data element that we're actually storing in the tree. It's um referenced by its branch. The branch nodes reference its by its hash the hash of its value. Like say this is an account leaf. um you're going to hash the contents of the account like it's nons balance uh storage root and code hash and you you would hash that data structure and that's the reference that would be in the branch node but when you locate this this tree sorry this node in the tree you're actually locating it by its address.

Uh so if you think about that same leaf node account type say it's account was like um 00 ABCD EF um when you go to insert that in the tree you don't insert it with its actual address. You insert it with the hash of its address. Uh this is a little for me when I first looked at this I I was thought that was a little unintuitive. I didn't really understand why you wouldn't just store it by its address. And then I thought about it a bit more.

Um, and the reason that we do it this way is so that we can't uh attack via like a depth attack the tree. If you were to a able to write, you know, arbitr arbitrary entries into the tree, you could create an arbitrarily deep portion of tree. you can kind of attack uh grief Ethereum by allowing the the tree to um have unnecessarily deep nodes. Like at the at its worst, you could get or not at its worst, but at its fullest, the uh state tree as it's defined currently could have a depth of 64. You might have a 64 deep node.

And if somebody wanted to grief Ethereum, they could just, you know, create two accounts that's that are one leaf off or two storage slots that are just one uh one uh portion of path away from each other. So you could force like this really deep uh tree branch that you would always have to an Ethereum node would have to traverse when you're uh interacting with it with transactions. So, you know, in order to get away from that, in order to mitigate that attack, uh it's specified in the in the white paper that we insert via the hash of the key. So, we end up with a with a balanced tree, you know, because the hash function is going to be, you know, seemingly random. Uh it's going to be well distributed and seemingly random uh when you when you hash the uh the account path.

So, you end up with this, you know, nice balanced tree. Uh it's difficult to attack because uh you know like you can't predict what uh if you're trying to craft a specific uh address or a specific slot that will attack the tree at a certain depth it's it's certainly more difficult. You've got to use a lot of computational resources to do that. It's it's basically infeasible uh to to attack the the state in this way. So that is the reason why we uh index by hashed values in the tree.

Okay. So that said um let's look at the anatomy of a tree hash key. Since they're stored since uh elements are stored by the hash of their key the tree keys are 32 byt hashes. Um so if we consider an example like uh the mock uh dead beef account. So dead beef, dead beef, dead beef, dead beef.

Uh, when we hash that account address, it's going to hash to 3D, 7F, 32, B5, etc., etc., etc. So, this is the key you would use to locate the account. Dead beef, dead beef, dead beef, dead beef in the tree.

Um, to store the node in the tree, to find the path through the tree where we actually insert these values, we break that hash key up into fourbit nibbles. uh it's a you know uh it's the Ethereum tree is hexary so there's 16 values each each branch can represent 16 children so it's just convenient that four bits uh defines u it's not convenience by design that four bits um determine 16 different potential values so what's convenient though is the hex view of that hash happens to present as nibbles like the first four bits of this address is three and the second nibble the second four bits is D and seven and the fourth is F etc. So when you go to insert in the tree, when you're trying to find an unused uh location in the tree to insert this value, you're going to traverse down the tree first at the D location. And if there's, you know, a branch node there or a conflict, you're going to go down to the next depth and you're going to be looking for the D slot, see if that's unoccupied, the seven slot, the F slot, you know, etc. Um, so that's really that's really convenient.

So you can look at any hash in hex and just intuitively know what its path through the tree is going to be. Okay. So to bring the Merkel portion of this in to bring the hashing in uh the cryptographic commitments uh let's look at some examples. This is a really simple two-leaf example. Uh so we have uh an EOA1 and EOA2.

And you know this is a toy example. So I just did this for for fun because it's easy to easy to type in and remember. But let's say that the hash of the EO1 say the hash of its account is 00 ABCD EF coffee coffee coffee coffee. And similarly let's say leaf node two uh it's add its value hashes to uh FF abcde F dead beef dead beef dead beef dead beef. So when we insert these into the tree, uh the root node is going to be a branch node and the first nibble of this leaf address will be zero.

So the hashed value of this leaf node will go into location zero of this root node and the first nibble of the second EOA uh is F. So that's going to go in the F location. So at the at the end of this tree we have a root node with it's 16 uh an array of 16 slots basically for hashed references. Uh the zero would be occupied and f would be occupied and we take that array and we hash that array and we get the state route. So this state route ends up being 8 a 31 eB66 etc.

Uh what's what's great about that is this is a a really succinct commitment to the state of the tree if um there's no configuration of the tree that would also hash to this value. So if when you insert these values into the tree and you do all of the hashing at each level, you know that the state route represents exactly this state. So just this value here you can use to commit to uh the entire state of the tree across all of the different nodes. Granted this is a toy example because it's only a three three node tree. So if we go a little bit deeper and we add a branch node, we can fiddle with these uh you know toy hashes uh address hashes here uh and say instead now we're using 00 ABCDEF coffee coffee and in this one UA2 is doing 0F ABCD F dead beef dead beef dead beef.

So when we insert these into the tree, uh nibble zero is the same for leaf node one and two. EA1 and two have the same first nibble. So we're not this is not an unoccupied uh spot. We need to have a branch node here. So when we insert EOA 1 and two at the next depth, we check their next nibble.

So this one is uh EOA1's nibble is zero and EOA 2's note uh second nibble is F. So there's no no conflict there. We can now just directly um take the hash of this leaf node, insert it into the zero position of this branch nodes array of child hashes. And same over here, we take this the hash of this leaf nodes, this account value, and put it into the f location of this branch node. So again, we have a an array of 16 elements with two elements populated.

We hash that value. we get 54, 509, etc. And we put that hash value into location zero since we this is the zero nibble path still. Uh we put that into location zero of the root node. And when we hash this root node, we get the state route F5 5C etc.

So again this state route commits to this and only this configuration of state. It's a again super succinct way and secure way to verify consensus of state across different nodes. Okay. Lastly, um extension nodes. I I don't know that we really need to think too hard about extension.

Is that a question or a loop? Yeah. Um maybe just the question about how the elements are are stored in the array uh for the unoccupied slots. Are they just undefined or are the elements set to zero? They are null elements and like the an implementation detail is that this is going to be an RLP encoding of this particular array.

So those null elements will have a specific encoding in RLP. And then what you're going to do is hash the RLP representation of that array. I I didn't want to go too deep into that, but that's functionally that's how those those elements will be represented and how they'll be hashed. RLP is a RLP is run length prefix encoding if that if uh there's a lot of talk about the RLP on on the net as well. It's a just it's just an encoding style encoding uh algorithm.

Okay. Um back to extension nodes. Um again I don't think we need to think too hard about extension nodes to uh to really um understand the differences in state implementations across different clients. But just to kind of you know close the loop um an extension node as you recall compresses some portion of keyspace. So if we fiddle again with our toy hashes here and say that the hash of this address is 00 ABCD F-f00 0 coffee coffee and this one 00 ABCD EF dead beef dead beef dead beef um they have eight nibbles of common prefix.

When we go to insert this in the tree we would have to go we would have a conflict at depth zero a conflict at depth 2 3 four five six seven and eight. it would be the ninth nibble before we actually get to some portion of the path that's differentiating these two nodes. So if we didn't have an extension node then we would have to have a tree that was like nine or 10 nodes deep depending on how you think about it. Um an extension node compresses that bit of common key space. It compresses all of 00 ABCD EF.

So we don't need to create this unnecessarily deep tree structure. Um, the extension node points to the branch node. Like the prior example, the branch node points to the two leaf nodes. We hash these two leaf node values, pop them into the array for the branch node, and uh then take the hash of the branch node and put that into the extension node. And in this toy example, the extension node actually becomes the state root.

It becomes the root node. It's it's a toy example. You wouldn't actually see that in practice, but it helps to fit the example on the slide. So, uh, just keep that in mind. Extension nodes are typically going to be found deeper in the tree.

Okay. So, that said, I think that gives us enough understanding of how the state is represented in the tree. Um, it's going to be useful to look at a state. Oh, sorry. So, I didn't talk about the leaf types themselves.

So in the Ethereum uh Merkel Patricia tree, you're going to find uh two leaf types. There's going to be an account leaf, which would be in the account tree, and you'll found find a storage slot, which would be a leaf in contract storage. Um, the account leaf types are going to be either an externally owned account like what you would typically use to as a user to interact with Ethereum u at least historically uh or a smart contract account. And regardless of whether it's an EOA or whether it's a smart contract, you're going to have the same data structure. You're going to have a balance in ETH, you're going to have the nons, you're going to have a code hash, and you're going to have a storage route.

So in u uh on an EOA uh you know historically code hash and storage route are not used. An EOA doesn't have code. An EOA doesn't have a it doesn't have storage. So you end up with the empty hash for code and the empty tree hash for storage route. Uh just an interesting tangent in EIP7702 um EOA code hashes gets repurposed.

There's a it's a a special delegation mechanism that points to a smart contract that an EO can delegate to and go check out EIP7702 if you want to know a little bit more about that uh because that's you know just a a change that's coming about uh at least in how EOA is uh EOS are encoding their their account state. Okay, the second type of leaf you're going to encounter is storage. contracts. Contracts need storage. Contracts need code.

Um the code hash I mentioned earlier code hash is an attribute of the account itself the the account storage. So the code hash is kind of an implementation detail but um the code that's deployed will hash to a specific hash. It's going to be you know deterministic. It's going to be uh distinct. There's no reason really not to just use the code hash as a key to look up the code in the key value store.

Uh it's an implementation detail. There's maybe reasons to implement it one way or another. Uh but the simplest way to think about code is just a blob that gets stored in a database by its code hash. Um the storage however uh it is its own Merkel Patricia tree. storage has uh contracts have storage that kind of present as a map of UN 256 to UN 256.

Um so the a 256-bit value maps or key maps to a 256 bit value. Uh but essentially this is all uh like kind of like Merkel tree inception and that uh each contract is going to have its own Merkel tree and its own uh root root hash and that root hash uh when you change storage this gets mutated and it will get stored in this storage route for the smart contract account. Okay, now with that, uh, we've kind of covered all of the bases at a high level about how you can represent state. Um, but let's look at how you might mutate this state because the state transition is an a maybe not a confounding but a complicating factor about how you would represent state. Um, so we have another toy example where we can have EOA for account A wants to send two ETH to EOA for account B.

So um in this state we have EOA A is here. It's got a branch node X and the root node up here. Our tree depth is three. We've got EOA2 which is B here and its branch node is XN and that uh you know propagates up to the root node. So let's say EOA1 wants to send two ETH to EOA2.

What we're going to do uh in the EVM is we're going to decrement EOA EOA1's balance by two ETH and we're going to send or sorry increment to ETH to EOA2. Uh since EOA1 is kind of originating the transaction as well, its knots is going to change. So this the value of this account its account state is going to change. So it's its hash is going to change. Its path won't change to get to this node.

the path will not change but the hash value of its account state will change. So therefore we're going to update the hash value in its branch node and then we'll update we'll send this the hash you know this obviously its value is going to change because it's array of child hashes will change we'll hash that and push that up to the root node. Same with ea 2 only its balance changes but still its hash will change. So uh propagate that change up to the XN branch node. Propagate that change list of hashes hash of the array of hashes up to the root node.

So uh as I said you know we are rehashing A we rehashing B we push those hashes up into XN and X and then subsequently we will push the hashes of X and XN up into the root node and we will rehash the root node to give us our new state route. And I think that gives us a enough um if there's any questions this now is a great time because we're going to start talking about how BESU implements this and has implemented this since uh since we started since there has been some evolution there. So if you've got any questions you want to ask before we get into implementation details now is a great time for that. I'm going to stop sharing Mario because this is the point at which we're going to use Kareem's recording. So be before starting the the video.

So in this video we will talk about the difference between forest and bonsai and why we decided to move from forest to bonsai. So in this part I will mainly focus on the modification we are doing in bonsai that are related to the state bonsai it's not only state modification it's also a lot of optimization it's a lot of improvements but I will mainly focus on the state part because bonsai it's a really big subject we added also a lot of feature on bonsai so we have some blog uh we are trying as soon as we are some new features available or some new information. We are trying to publish some blog. So maybe after the meeting I will see if we can share more blog like that. If you want to understand more bonsai what we can do with bonsai you will have all of the information you need.

In Bizu we have two kind of way to manage the state. We have the legacy implementation. This is forest and we have a new implementation bonsai and bonsai is today used by default in bizu. So why we decided to implement a new way to manage the state is because we found that with forest there are a lot of issues regarding performance regarding the size of the database. So we tried to find a new solution in order to fix all of these issues.

So forest is a hash based merry implementation. So n are stored and accessing by the hash. It seems to be normal to do that because when you want to compute a state root you need to use the ash of the different tree node and also a parent will have the ash of the children. So yeah it seems to be normal and it's why also all of the client before were using an implementation similar to forest but as the state was growing as we had more and more transaction in the block we found that the state management so accessing the state and updating the state was taking more and more time during a block processing. So I will try to show you what kind of issues we had with forest.

So for example, if I want to read an account in order to retrieve the balance or the nons. So what I will have to do is to take my address, I will ash this address and the ash of this address will give me the path to follow in the tree in order to retrieve the leaf that contain this account. So in my example, I will start by reading the stage root node and I will find that it is a branch. So if it's a branch, you can have 16 children. If you look at the path, so the first nibble it's zero.

So I will take the ash in the index zero and this ash will give me the ash of the next tree node to read in the database. So at this moment I had to read the database one time. So I will read the new tree node and I will detect that it is a branch. So as before this branch can have 16 children. I will take the ash the next nibble and it's one.

So I have to take the element at the position one in this branch. So at this moment I had to read the database two times. I will read the next three node and yeah it's a leaf not we found the account just by reading three times the database in a block you don't have to read only one account you have to read a lot of account a lot of slots and if you have every time to read three times or maybe more it will impact a lot the performance. We have another issue with forest is how we are generating the keys. So in forest it is ash and ash is a access pattern that is completely random.

So in the database our keys are sorted. So if our access pattern is random we cannot benefit from block based caching system. So it's another problem regarding performance when we want to access the disk. In forest we have another issue when we want to build the state. I will give you an example with two accounts account a and account b.

So in this example we'll have seven entries in the database. So for the intermediate node and also for the account definition I want to transfer to it from the account A to the account B. So what I will do is to modify the leaf that contains account A because the balance will be updated and I will also update the leaf that contains account B as X depend on A and Xn depend on B. Ash of X will also be updated and it will be the same for XN and it will be the same for the root node because the root node depend on X and XN. So as we are saving by ash this modification will create five new entries in the database.

So it's only a transfer between two account and the state is very small. But in the mainet the block are more complex. We have more state modification and the state is bigger with more intermediate node. So each block will add a huge amount of new entries in the database. This is the kind of problem we can have with forest.

The size of the database that is growing too much and also very fast. And we have also the performance when you want to read the state because of the number of disk accesses and also because we are using ash for the key. So we decided to change how we are managing the state. Bonsai it's a location based market implementation. So node are stored and accessing by their location and not by their passion.

And with bonsai we have also a flat D. So I will take the same example as before but with bonsai. So to begin I will want to read an account in order to have a balance. So as for rest I will take the address and I will compute the ash of this address. But instead of climbing the tree, I will directly ask the flat database.

Flat database, it's a key value database where the keys are the ash of the address and the ash of the slot key. You can have directly the balance of the account or your slot value. The second example is when you want to update the state. So as we are saving by location, so the key in the tree database will be 0x for the root node, 0x 0 for the first children of the root node, etc. And we'll have also the flat database with as a key ash of the address and as a values the account definition.

So we'll have seven entries in the tree database and two entries in the flat database. If the account A want to send to it to the account B, this modification will update the leaf and the leaf will have a new ash. As the leaf will have a new ash, the parent will also have a new ash. So we will still create this cascade of modification. But as we are not saving by ash, we are saving by location.

It will not create new entries because even if the ash is different, the location is still the same. So instead of adding new keys, we will replace the old keys by the new one. So in this case, we will update the two entries on the flat database and we will also update five entries in the tree database. No new entries will be added. We are just adding new entries when the structure of the tree is modified.

So when we are adding for example a new account or when we are adding a new branch or something but how we can retrieve a new version of the state with forest it's not really complex because we keep all of the tree node and all of their version so we can always retrieve the state of a previous block everything is in the database but with bonsai as I said before we are replacing the tree node every time so we don't maintain the history we only have the current state so the head in bonsai In order to fix that, we implemented a trialog mechanism. So what is a trialog mechanism? In order to explain that I will use example of g. So when you develop something and you have different commit in g every commit is not a full copy of the code. Instead of duplicating the code for each commit, what you are doing is to create a diff between the two commits.

So the div is what kind of line you removed, what kind of line you added. And thanks to this div you can regenerate the code as it was for the commit you want. So we are doing something similar with bonsai. We are generating every time a new trial log and the new trial log will be a diff between two block. So it's a flat representation in the trilog.

We are just adding in this trial log all of the leaf that we are modifying. So the account we are updating the previous value and the new value. the slot that we are modifying the old value and the new value and like that we have the modification we are doing between two block and if I want to go back to an old version of the state I just have to apply this div and like that I will have the balance of my account in in an old block or something like that I don't have to keep in the trailer all of the intermediate mode because when I will modify the leaf I will be able to regenerate all of the intermediate mode so it's not needed to keep everything in the trailer just a flat presentation. So you can see an example of what kind of information you can have in the trailer. So as I said before account modification so you will have a count a b with the previous value and the next value slot modification code modification etc.

So for example when I want to transfer some it from a to b I will generate a trial log like that. So you will have account a with the previous value. We can say for example the balance before was 100 and after the transfer the balance was 98 and the nons was increased by one. For example for the B we can say maybe the balance was zero before and after receiving the transfer the balance was two. If I want to roll back to an old state I just have to take the trial log and revert all of the modifications that I find in this trial log.

So for example, I know that this account balance is 98. So I will go back to 100. For account B, it's two. I just have to go back to zero. So I will modify the leaf and all of the intermediate node will be recreated.

And like that I can retrieve the state as it was before in a specific block have two kind of way to manage the state. We have the legacy implementation. Yeah, it's it's all possibility. Cool. That was that was definitely a whirlwind uh like definition of differentiation for forest and and bonsai strategies.

It's really a a the difference between using a hash key for uh storing your triodes and using a path-based key. Um, so if you does anybody have any any questions or want some clarifications about like hash versus pathbased trees? Yeah, I was just curious since you still need um the Merkel Patricia tree, you know, creating the state root hash for consensus. Uh, how do you consolidate your bonsai tree with the MP tree? think um we consolidate it with with bonsai we consolidate it by implicitly pruning like because we only keep one version of the tree on disk at any time.

It's uh we just keep this single that's why it's called bonsai because we keep this single manicured tree. Uh and the trilogs will allow you to mutate that single tree forward or backward. So if you need to see historical views of state, you can mutate in the case of bonsai, you can mutate it in memory um to have some historical perspective of what state was. Um but functionally the tree and the hashing remain the same. What's really different is how we address those nodes in the database because we're we're using the path to the node as the key then when we're storing in the database rather than the hash of the node as the key in the database.

So that that's really the big differentiator in terms of like autop pruning between a hashbased and a path-based tree. Yeah. Instead of using the ash we are finding in the branch in order to get the next key, we will know directly what is the location of the next node because we have the path directly thanks to the flash of the address. So yeah just how we are climbing the tree but the content of the tree node in the database of each node will not be modified will still be the same and we are computing computing the stage it's also the same so yeah and these tree logs are also useful for handling um like reorgs things like that definitely yeah it's also something we are using for for the Okay. Yeah, there's some neat features.

Um, tree logs are almost like um a block witness because they have pre-image and post image uh values. It's it's kind of like a um it's not a cryptographically. It's not a it's not a commitment, but it's kind of like a succinct uh witness to what occurred on a block. It's it's similar to what we will have with stateless, but as Gary said, we don't have any proof with this trial. So the track should be uh should stay in the instance of baso.

So it will not be go outside of bizo but uh it's completely similar to what we'll have with stateless. So the prior value and the new value just for stateless we'll have proof like that we'll be able to share this um this div to another client. Yeah, I know you guys mentioned um like that you do have the flat DB for the key value pairs and I know that other clients like Aragon will use flat DBs. I'm just curious on um you know, how would you say like pros and cons of having just like a pure flat DB versus you guys' kind of like hybrid approach. You know, the the next section of this is going to talk about how different clients implement uh their own different strategies.

And we're not we're not experts on other client code bases, but I think we have a pretty reasonable understanding of their schema. So, we can probably address that here in just a minute if you're if you hang on just a moment. Great. Sounds good. Yeah, just to confirm I'm also not getting comments in the chat.

So if people are trying to comment, please do so in Discord or raise your hand. I'm going to go ahead and Okay, I'm I'm not sure where I left off in the presentation that I was screen sharing, so I might have to jump through or I might just work. Let's see. No, no, it's in the right spot. So, uh, what Shane was alluding to, uh, var variations on state schemas and different clients.

Um, and I'm going to say it again, uh, we're not experts on other client implementations. Um I what I think of this as this portion of the presentation is like a starting point for you to go um start uh exploring other client implementations like if you if you want to have just an a high level understanding of what these clients offer what their benefits or trade-offs are or fundamentally how their their schema is working. Um so that said um other execution clients have uh kind of a grabag of different strategies. Um, some have the hashbased tree still. Um, some have a path-based tree.

Um, some have both hash and path. Um, some implementations u flatten the tree. Uh, there's some interesting uh development in that regard so that it's not hexary at least on disk. Uh, and then there's like a a history tracking strategy that uh is uh beneficial for archive nodes. Um, I think we should start with GU.

And the reason I think we should start with GE is because um, GE has evolved kind of separately from BESU, but um, we've both sort of arrived in a very similar place with regard to our path-based implementation. Um, GE when it started, like most clients, uh, all clients probably, um, originally had a a hashbased state tree implementation just just like Forest, uh, and Basu had all the same problems that Basu had with with Forest. Um, in 2020, GE implemented uh, snapshots. snapshots are effectively um a flat database uh of all of the different uh block change. This a single state tree that's kept on disk similar to Basu's Bonsai.

However, it's a hash tree still and the changes accumulated in memory uh for up to 128 blocks and every time the head of the chain goes beyond 128 blocks, they would collapse. They would compress how do you call that? They they commit that uh 129th block diff to disk. So they they keep this running 128 uh block behind state implementation state tree on disk just a single hash tree. Uh but because it's a hash tree uh pruning is still a challenge because uh you have to track all of these hash nodes that may or may not be updated.

Uh they might be part of some prior reader. They might be so part of uh some prior state that's still necessary and it's it's difficult to to track those changes. So if you recall like older versions of GE, you might have to shut it down so that you could do offline pruning so you could regain that storage. Um, but that's a that's a problem that GU fixed in 2023 um by introducing a path-based state scheme like like Bonsai. It's a path-based single tree on disk.

So it's implicitly pruned. I think it's probably best to characterize um GU's implementation um in how it differs from BESU because they have like this my understanding like I said we're not experts but my understanding is that GU maintains a a snapshot a single tree that's like a fixed distance behind head whereas BESU typically has a more fluid uh relationship with what state is stored on disk and we typically um will commit the most recent and finalized block as the the state route that's on disk. Um, so that's kind of an operational difference. U, but I mean they're very very similar. They they took a different route to get where they are, but they're both very similar in their state implementation for for path and other mind has some very interesting uh solutions.

Um, they have what's the production code right now is half path. Um and they have a kind of new more aggressive rethink of state which is paprika. Um halfpath is kind of an evolution of the hashbased model. Um it's still a hashbased tree and there's uh multiple like a forest of hash trees that exist on disk. U but the keys are prefixed with a portion of the path.

when they save the nodes of their tree, they have uh some partitioning that ends up um let's look at my next slide. I don't want to front run my next slide. Yeah. So, there's a section bite. There's eight bytes up to eight bytes of the path prefix that's going to go into the tree key.

There's the length of the path like this is like I said, this is up to eight bytes. The path length is going to specify how much of that eight byt path is uh relevant in the in the prefix there. and then the 32 byte hash that normally would be the hash key for a uh a hashbased tree and similar um let's go ahead and maybe skip to the next slide um I should probably say the benefits here like the the benefits because like Basu Nethermind currently is using Rox DB and Rox DB is a log structured merge tree implementation of a database which means that um everything is stored as sorted strings. Uh the the files that make up uh a Rox DB database are sorted string tables. So you'll have these sections of the key space that end up getting uh lumped together, partitioned together in these individual sorted string tables.

It it's it gets more complicated than that with the log structure, the merge tree stuff, but fundamentally uh all of the files on database are sorted. So when you sort by the path, say you've got this section bite and this path prefix, you're going to have all of the elements or you know most of the elements that are relevant to descending down a path uh stored next to each other on disk. Um so you you get improved data locality. So when you are reading off disk, when you're reading from cache, it's going to uh be more performant. Cache is going to be more effective.

compression is going to work better because they're they're stored together when you keep data close together, the individual compression is gonna going to work a lot better. So even though um they're storing more data in their keys, they're adding 10 bytes uh to the tree keys here and 10 bytes to the storage tree key here. This actually ends up a net reduction in the size on disk because of the way uh the Rox DB is able to compress that sorted data. So just a quick bit about the section. Uh there's it's a bite but there's only three different values as I believe.

Again not an expert but uh if there's like a a hot section of the tree like near the top of the tree where you're going to constantly be getting uh changed hashes, changed values and so forth that path length would be less than five. So that would be like what um 10 or fewer nibbles worth of path would be stored in it's partitioned off in section zero. So you can Oops. So that's going to be like the hot part of the tree. One would be the less hot part of the tree and it's going to be storing more of the path prefix.

uh the path prefix would be up to 16 nibbles because it's eight bytes of path prefix and all of those are going to be stored together on disk. So you can kind of see how this access pattern is going to make it where the hot portion has its own usage uh profile and the deeper portion will have its own usage profile and the section bite value of two means that it's account storage sorry uh yeah storage contract storage. So that is partitioned off differently. Um it just kind of creates a good usage profile for sectioning partitioning this stuff by where it exists in the tree. And um again this is the path prefix stuff that's eight bytes up to eight bytes.

There's the path length and then finally there's the actual 32-bit byte 3 32 byt hash value u that is the key uh for the uh for the tree. So it's kind of a a clever way of incorporating uh path to to gain the advantage of path locality and the advantage of um attribution really because this also helps I understand with uh with pruning because since nethermind's halfpath is still using a hashbased tree all of these keys um have dduplication issues like you don't know which one needs to be removed uh when you're when you're moving state like when you're expiring or pruning a tree, it's it's pretty challenging to do that with a hashbased tree. So my understanding is that this uh prefix makes that pruning somewhat easier. So um I think halfpath is like a kind of a gateway to um a nethermind uh path-based solution which is paprika and I am just kind of coming to terms with what all paprika is and does. So it's in development.

It's not uh it's not production code. Um so this is just what's what's coming in a preview and it's coming from a person who doesn't understand it all that well. So take all this with a grain of salt. Um but my understanding is that Paprika um at its core implements its own page database. So like it's not using Rox DB, it's not using MDBX.

It's using its own invented here page DB. And I think uh it is Ethereum aware. like Ethereum is a first class citizen in page DB and I think the U page DB dependency is is going to be something you could actually incorporate to other clients I believe. So uh if someone were interested in writing a client uh they might be able to use page DB uh and have an Ethereum aware uh you know first class citizen Ethereum database. Um, one of the interesting features of paprika is that it is collapsing the tree.

Um, instead of having this branching factor of 16, um, paprika changes the the tree structure to have a branching factor of by default 256. So each of the pages represent two nibbles of path. Instead of one nibble of path in a 16 uh hex area tree, uh each nibble has it represents or sorry, each page represents two nibbles. Um I got a squeaky dog behind me. Sorry, I don't know if you hear that.

Uh um so what this ends up doing is it reduces the read and write amplification because the tree is a lot more shallow. Uh I was talking with one of the developers and I think they said in the last time that they were testing this on mainet they were able to uh represent the full state tree at a depth of some I think no deeper than five and they were able to represent uh contract storage at storageages at a level no deeper than seven. So it's uh it sounds pretty promising. Um as I said I don't know a whole lot about it yet. So I don't want to I don't want to go too far into the weeds on it.

I do know it's designed to be path-based and commitment agnostic um so that it can be used. This is kind of their gateway into vertical. I don't think that they're going to be using the half path in vertical. They're going to be using paprika for vertical. Um so that's kind of their forwardlooking strategy and it's uh it seems really interesting.

And Kareem and I were talking about maybe borrowing the idea of flattening uh the tree to 256 uh airy uh flattened tree. Um paprika pages the way that the way the the page DB is set up there's a root page uh there data pages there's abandoned pages and prefix pages. Uh data page is kind of like some some segment some natural segment of the tree. um some segment of the of the path in the tree. And an abandoned page, as I understand it, is a data page that is it's it's basically a data page that's been it's no longer current.

It's not the head state. So, it's it's available to be pruned or reused by the database. And uh the prefix page, I believe, is analogous to extension nodes in a hex area tree. Um but yeah, keep an eye on that. It seems like it's pretty interesting.

Um like I said forward compatible with vertical. Uh there is capacity in the design for archive. I don't think that it's implemented but I I think that um the there's design capacity for having an archive node using paprika. And check out the design docs. They've got a good design doc on paprika at the Nethermind uh GitHub repo.

Go to nethermind e paprika under docs design. It's a it's a pretty good pretty good uh primer on that. Okay, so Aragon state implementation. I know not a ton about the Aragon state implementation, but I have a high level understanding of how they're segmenting their schema. Uh what's interesting is that uh the Aragon state representation is used by both Aragon and Ref.

Ref has kind of borrowed that. It has a a shared history with the Acula project from uh from the uh Aragon team. So, um I suspect that's probably why Reth has um at least similar to the Aragon v2 uh state implementation. Um Aragon state storage, it's it's known for being um a very tight archive format and a very quick access to historical information for like RPC uh supporting block explorers and so forth. It's uh uh very good at that particular use case.

Um what's interesting is it maintains both the plain state like it's got flat DBs as Shane alluded to. Uh Aragon has two flat DBs as I understand it. They've got the plain state which is unhashed keys like instead of hashing the account key and hashing the slot keys so you can insert it into the tree. their flat DB, one of their flat DBs is uh uses the unhashed the pre-image uh as a key in that state and it's also got a a hashed state where the keys are hashed. My understanding of the hashed state is that it exists largely to support calculating the state route.

Um, what's interesting about the plain state is that it means that Aragon and Reth are uniquely positioned to be able to provide pre-im images for the entire Ethereum state, which is a problem for all of the other clients like GE and Basu and Nethermind don't maintain pre-im images by default. There's features that you can add pre-im images, but it's not the default. Uh, you can't expect any of those nodes to have unhashed keys for their state. So when you want to migrate to veral or to starkle or to whatever the the the next state iteration is going to be somebody's going to have to provide that those that pre-image store to to GU and to basu to nethermind and in all likelihood that's going to come from an Aragon state implementation whether that's coming from a ref node or from an Aragon node. Um it's very convenient and handy that they happen to have that for Ethereum.

Um the Aragon also it's V3 specifically. Aragon V3 is new. So I don't want to talk too much about it because it's uh it's hot off the presses as I understand it. Um but they have this notion of frozen state data that can uh be imported quickly. It's uh the Aragon an Aragon specific format.

So it kind of plays into their sync strategy, their uh the bit torrent based uh incremental frozen state sync strategy and makes for a really fast sync uh in Aragon 3. Uh it's largely because of the the format that they keep for their for their history. Um logically uh the Aragon state schema is as I said the head state is made up of four tables as I understand it. the plain state, that's the flat flat DB and plain unhashed uh keys. The hashed state, which is the same thing but with hashed keys.

There's a tree of accounts and a tree of storage. And those two are there. They're basically the intermediate nodes, the extension nodes and the branch nodes and the state route that are used to calculate the uh the state route. Um I believe Aragon only keeps a single hashed tree um single single uh single version of the hash tree in the tree of for the tree of accounts and tree of storage. Um that's subject to verification but I I believe that's the case.

Um where Aragon's like archive um use case is served well is these tables down here. the account change set, storage change set, account history and storage history. Uh the storage change set and accounts change set. Anything that's the change set is keyed by the block itself. So like whatever happened at for example block four, you're going to have some storage that was changed in block four and there's some account that was changed in block four.

This table is indexed by the block number and the the you know the account the key that was changed either the account key or the storage key. So when you want to do a historical query say what was the state of block 4 you're going to go to the account change set and see what happened in that in that state. Um if you actually want to see a view sorry if you want to see what happened in that block you would use these tables. If you want to see what the state of an account was at block 4, you would go to the history tables. The account history and the storage history, they're keyed by their account and their account storage slot.

So, if you want to see what, you know, the dead beef account looked like at block four, you're going to go to the account history and say, "Give me the the pre-image uh for this block at its closest time it was changed." Say say uh we want to know what it looked like at block 12 and it was changed in block 4. You can go to this account history table and say give me the most recent version of this account uh based on block, you know, I'm looking at I'm looking at the state at block 12. What's the state of this account? And it's it's stored as a u oh boy, we're running over time a little bit.

Are we okay? Um yeah, so accounts history is good for for looking at accounts and storage at a specific uh point in time whereas these guys are more about seeing the change set for a particular block. And u with that that kind of um is the end of my understanding of the different uh execution client implementations. It'll be interesting to see what um what the Nimbus execution client is going to be doing. Um but yeah, that's the one of the few that I I don't know anything about yet.

And with that, um we can if we have time, I we can talk about the archive solutions. U all of these path-based systems have challenges with with archive since they're implicitly pruned. So, um Kareem has a a bit that's talking about where we're headed with path-based archive. So in in this video yes I will try to explain uh how we are trying to implement the bonsai archive friendly feature. So it doesn't seems to be normal to have bonsai and archive in the same sentence because bonsai is more for near head states but we found different IDs uh in order to to implement that.

So I cannot confirm that in the future uh the bonsai archive implementation will be as I'm describing today but uh yeah this is the main idea we have uh and uh the feature is still in development so it's not yet in production but we hope to have maybe something this year if it's possible um if it would be really nice if we can have something this year yeah very well thank you so much Gary and I the video already before we started. We're good on time. I just wanted to check if there were any questions while I was a lot of information, a lot of different approaches from all the different clients. So folks, if you have any thoughts, any questions maybe about some specific approach started my mic and please let me know if You can hear it again. Recently, we decided to check if we can use bonsai as an archive mode because we added a lot of optimization.

We also reduced the size of the database with bonsai. So yeah, we we tried to see if we can have a solution to use bonsai also for all state and not only for near head. What is an archive mode? An archive mode will help you to retrieve the history of a slot value. So we need to be able to retrieve very old state in order to do that.

So in order to help regarding this partic we could probably talk through it if if you want. I don't think that there's I think there's only a handful of slides. If you do you want to just try and talk through it? Few minutes I can try. Yeah.

Okay. Um, do you have do you have the slides? You want me to share keep sharing it or Hey, Gary, do you want to share the slides? Sure. Yeah, I'll share the slides.

Yeah. Yeah. Okay. Thank you guys. So, as I said, uh, could you hear me?

Yeah. Yeah. So as I said we are trying to implement a bonsai friendly feature. Um today uh in order to provide array feature we are using forest. So uh we still have to duplicate for us.

So, So, in order to Fix. to keep everything we'll have the same database size as forest and it would just be useless to work on that. So in order to fix the issue regarding the flat database, what we decided to do in is instead of having only the last version in the flat database, we will modify the key in order to have as a prefix the hash of the address with a suffix and this suffix will be the block number where we modify the account. For example, in this case, we have an account A and we can say in the block one, the account A was created. In the next block, the block 10, the account A was modified.

And in the block 15, the account A was modified again. So in the flat data B, we will have three different keys and each keys will have a prefix as I said the ash of the address and as a prefix the block number where we had the modification. So we'll still have a lot of duplication but the flat database is still smaller because we don't have all of the inter so it will still be better than forest but how we will be able to retrieve the good version regarding for for example if I want to retrieve an A and where was what was the balance of the comp a in the block Good and seek for pre will help you to retrieve the key that is the closest to a specific key and if it's not equal it will be just the key before. So for example, if I want to retrieve the balance of an account as it was in the block 11. So I will ask Roxb to give me the key where the prefix is the ash of the address of the account a plus with the suffix 11 as the key is not existing in the roxp database.

What we will have is a key with the suffix 10. But as we are not modified the account in the block 11 having the version of the account a in block 10 it's valid. So the the result we will have will be okay and we'll be able like that to retrieve the version we want. But having only a con balance or a continance or slot value is not enough. Normally we should also be able to prove that the data we are finding are valid.

And if you go to the next slide in order to validate that the data we are retrieving is valid we can use something that we are calling Merkel proof. So Merkel proof will help you to be sure that an account B is included in the Merkel tree of a of a specific state. For example, if I want to be sure that the balance of the account A was 10 in the block 10 in the in the block 10, I will have to have a proof that this balance has really this value in the state of the block 10 thanks to the Merkel proof. But as we said, Bonsai is only keeping the head of the state. So if we want to be able to regenerate an old state, we have to do a roll back.

But if we really want for example in in the mainet today, if we really want to have the state of the genesis block, it will be too many roll back and you will not be able to do that. It will consume a lot of memory and the node will not be able to recreate too much data. So we had to find a new way to avoid all of these hold back in order to retrieve the state. So if you can go to the next one. So in order to fix that, we decided to create some checkpoint.

So instead of saving all of the state of each block, we will create a checkpoint of the state after end block. So for example in this case I will create a checkpoint of the state of the block two. I will not save the state of the block three. I will not save the state of the block four. But when we reach the state of the block five I will create another checkpoint.

And like that instead of doing a huge amount of roll back I will just have to take the checkpoint that is the closest to the block I want and I will have to do roll back or roll forward in order to rech. So if you go to the next slide for example. So the the distance between each checkpoint will depend on your need. For example, if you want a longer interval between checkpoints, the size of the state, no, the size of your database will be uh will be smaller. So it will be better if you don't have um if you don't want to have an important database size but the performance will be lower because as your checkpoint distance will be bigger you will have to do more roll back or roll forward in order to recreate your state.

But if your priority is a performance, you will have to decide to use a shorter interval and like that you will have maybe a database that is bigger, but you will have less roll back and roll forward in order to recreate your state. So the performance will be better. So it will depend on the need and it's something we want to to add as a flag. So the user will be able to decide the size of the of the range he wants. So next slide.

Yeah, I think it's interesting to mention that there aren't any path-based databases that uh give you historical proof of the Merkel trees is like even even Aragon's u archive friendly format doesn't have those prior versions of tree. So that it can't provide historical uh get proof unless you have a a large full archive node like a full archive node get or a full archive node basu or a full archive node like a hashbased tree implementation of some of these other clients. So I heard that guest is working on something uh similar. I'm not sure how the guest implementation will work. I'm just heard that they are trying also in a pass based pass based archive feature but I'm not sure if it's already in production or if still something they are trying to implement but yeah clearly as Gary said I don't think a lot of client can provide this kind of feature with a small database size so um just to to explain how we are able to retrieve a state from a checkpoint so as I said if you want to prove an an account that was in the state of the block four.

What you will have to do is to just find the checkpoint that is closest to four. So for in this case it will be five and you just have to do one roll back in order to recreate the state of four and like that you will be able to generate your proof. So if you have only one trial one roll back to do the performance will not be uh will not be bad. it will be something similar to the to to when you want to generate a proof from a near head state or something like that. So the performance will be really good and as I said if you if the size of your database is not something important you can just have a smaller range and the performance will be not not a problem for you.

But it's still in pro it's still in development. So we still have a lot of um uh modification to do in the code. We also have to to do a lot of benchmark to be sure that everything will work correctly. But we still we already have some PR that are ready and yeah the next step will be to finish the test and trying to merge that in the main branch. I think we'll probably deliver the bonsai archive feature incrementally where we have the um the flat DB based um that it solves almost all of the RPC use cases except for get proof.

We'll probably be rolling that out ahead of the checkpoint um feature that gives you uh proof at any arbitrary block in history. So yeah, it's probably going to be delivered incrementally. Yeah, this hopefully this year for the full set. It's also something we want to be optional. So maybe some people don't want to to generate a proof.

They just want to have the historical data of a content slot. So it will be useless for them to create all of this checkpoint and increase the size of the database. So for this user only having the flat database feature will be enough. So with with that they will have a bonsai with a really really small database size and people who want to be able to generate a proof will have to activate this feature and it will take more space but yeah it will still be something smaller than forest. With that, that uh that concludes what we uh have to present and we're pretty close to to time.

So, um if anybody has any questions, now is a great time to ask them. Um I think we're going to probably share the slide deck with Mario. So, uh if you want to refer to this or any of the references in it, that's uh it'll be available after. Wonderful. Thank you so much, guys.

Yeah. Awesome. Yeah. Right to the time. Great timing there.

We still have a couple of minutes for questions. So if there are any thoughts, questions, folks, please go ahead. It's uh one of the last opportunities to to chat with core devs in our study group. So please don't be shy, don't be hesitant. Um okay, we have a question from Tro.

Yes, sorry. Might might be a bit dumb, but I it's it's really hard to think about roll backs um and creating proofs for like a previous uh block being added to the chain. Um, like is it useful to think of what would be applied to the new checkpoint as the inverse of the state transition function? Exactly. Yeah.

Like when you're a roll back is essentially inverting that state transition. Precisely. And and so how how would that work? You you'd take this block and like in the example the checkpoint of the fifth block and do what with it perhaps? Well, we would um at least in Basu, we would take the trial log.

Say if we're trying to get to uh block four, we would start with the checkpoint version of block five and we would take the trial log for block five and we would unapply it. We would revert all of those changes in memory uh so that we could now have a view of all of the uh Merkel tree at block 4. So for example, if you added an account from the block four to the block five, if you want to roll back, you will just have to remove this account. If you incremented the balance of an account in order to go to the block five by two, in order to roll back, you will just have to decrement this account by two. And it's like that.

Uh like that you can recreate the state as it was before because all of the leaf will be recreated. And as all of the leaf will be recreated all of the intermediate node will be recreated as before also and you will have the state of the block four and like that you can generate a proof. Thanks. Thank you very much. And as Gary said we are also creating a lot of copy.

So I didn't really wanted to talk about that because it's really complex and it's not really linked to the state. But with bonsai uh we are trying also to implement something that is thread safe. Uh so for example if you want to generate a proof thanks to an RPC API you will create a copy of the state and you will roll back this copy like that you are not impacting the main state that is used in order to follow the shen and every time you will call an API you will have a new copy. For example, if you have to to respond to two RPC API at the same time, just an example, each RPC request will have its own copy. And like that, we can have really something that is thread safe.

[Applause] Yeah. Um so I think you guys mentioned uh sallessness a little bit and I know one of the key blockers for that is the size of Merkel Patricia tree proofs and we have you know Berkel as a proposition to reduce this overhead pretty significantly. Just curious uh you know from the perspective of new client maintainers what are some of the more main engineering challenges and going from tree to Burke? You guys even started experimenting with that yet or is it just too early stage? So in Bezu we are already working on ver so we have a first implementation we can follow the the current devet and we are also working in the transition from patry to verl but when we implemented bonsai so at the beginning it was doofing so when do implemented bonsai he was also thinking about ver so uh it's also why for example the trial log is similar to the witness we have today in veral we have prior value and next value.

So it was not really hard to modify bonsai in order to implement ver. So today we have a a ver implementation and bonsai implementation but the two implementation are sharing a lot of stuff and like that we can just have the specificities that are in the vertical package for ver and also for bonsai are in a specific package. So it's in the bas side I wanted to I want to say that it was not really hard to implement ver and I think we have also a clean architecture that help to be compatible with different kind of tree and with different kind of storage format. Also for example when we decided to move to forest to bonsai the code was modified in order to be able to manage two kind of storage former so adding another one it's not really complex because we already did the stuff uh the kind of refactor in order to be uh modular uh so yeah in in my opinion uh I I I'm working a lot in burl I didn't so a lot of complexities uh For example, in um in ver we are also implementing a flat database. Uh it's something that is really useless for ver useful sorry for ver and also something that is interesting is as guest is doing a lot of things that are similar to bezu when guess is implementing a it's writing a specification it's matching in general very well with bonsai.

So and with B in general. So yeah, I think um some of the some of the interesting challenges with vertical is um the cryptographic load that's going to be involved with generating those commitments, the vector commitments. Um so that and then there's uh like scheduling and resourcing problems that revolve around you know are we going to try to do um binary trees with starks? Are we going to try to do vertical as it's currently implemented? And uh are we trying to be quantum resistant?

uh some of the challenges are really more about planning and resourcing than they are the actual uh implementation details. And also Verl is adding as you said some cryptographic stuff that are not really performance if we are comparing with sketch but also thanks to bonsai we added some optimization that will help for ver for example we implemented bonsai paralization so bonsai paralization could help to do some stuff in parallel as precomputing um uh yeah doing some disk accesses in parallel in In order to have something faster, we can also maybe some do in parallel some computation or maybe you can catch some compile call and all of this stuff can help also regarding the challenge that we have with ver and u yeah we added also some preload in bonsai in order to um do in par as much as this accesses in background and it's also something that can help for Verl. So it's really interesting that we are sharing the same base of code between bonsai and verkel like that today when we are working on some optimization in bonsai we know that will also help for cool. [Applause] Thank you. Thanks.