Rethinking Storage Layouts: Page-Aware Data Structures in EVMs - Dorde Mijovic

Transcript

[music] >> Hello everyone. My name is George. I'm currently protocol engineering team lead at Monad Foundation. Uh before that I was a co-founder in the fire and prior to that I was part of the core solidity compiler team. You can find me on X. I'm the most active there. Uh about Monad, Monad is EVM compatible uh decentralized high throughput L1.

Uh it has some small differences and it has some significant improvements to the EVM including asynchronous execution uh different BFT and uh customized DB. Uh currently there is uh 200 active set of validators which will increase to 300 soon. Uh it has 400 millisecond block block times which will uh decrease even further soon and 200 million block gas limit. So it can achieve up to 10K TPS.

Uh some significant improvements that are coming soon is paid if I the Merkle Patricia try which is the topic I will be discussing today. Uh encrypted transactions because of asynchronous execution you can keep transactions encrypted until they are executed. So uh some parts of MEV will be uh wiped out. Uh and as I said we will be increasing active validator set further. So I'm going to use this contract as an example for storage across the presentation.

So, it has a couple of state variables and one array. Uh what does compiler do in this case? So, uh slot zero is first variable, slot one is packed with uh the second two variables, and there is some empty space there. Slot the third slot holds the length of the array. And the data of the array is located at Keccak of two, which is uh somewhere further away. And this was uh done mainly to reduce the chances of uh clashes in

uh in So, yeah. What is Merkle Patricia trie? So, every Ethereum account has uh these four things. Uh nonce, balance, code hash, and the storage sub trie root. Uh what we will be talking here is uh the fourth part. Uh it's uh it's basically the root of Merkle Patricia trie where slots are actual leaves in the trie. Uh and the database itself is key-value pair.

Uh these slots the keys are calculated basically with the hashing of the contract address and the slot. So, what it does actually what happens is the database is having uh slots that are next to each other in a very different places because they end up with a completely different key. And uh this is how for this contract the trie trie would look like this, and you can see that there's no any uh kind of sorting based on what compiler is doing with the slots. So, it's basically random.

Uh So, that led us to And the the the main reason uh we thought about MIP 8 was uh uh that localized data is why it is important. First of all, every uh new modern hardware when you load one storage slot it loads 4 kilobytes of data because that's how hardware actually works. So, it loads additional 127 slots that are probably completely random based on your implementation of the database.

So, in order to improve that we we designed MIP 8. Uh You can uh Yeah. You can check the Yeah.

Okay. Okay. So, you can find the implementation or the details about the MIP including uh uh like all the gas costs related to it and uh the plan for like uh how do we migrate the whole database. Uh So, what it does is it packs 128 slots into single page and keeps that page as a leaf in America Patricia try. So, whenever you load one slot from that page, every other slot is going to be warm.

So, whenever you access slots that are next to each other, you are getting warm uh S loads. Uh this effectively means that uh like whenever you have localized data, you get uh everything else with no additional cost. Uh and that's how hardware operates, and this is now aligning more closer to that. Uh so, you can get the page index by shifting the slot to the right by seven, and the offset is basically uh uh what uh exact slot you are having in the in the actual page.

Uh So, since this change introduces uh quite a nice tool to optimize contracts, it would be very nice to design storage with this in mind. So, I'm going to show now how what how does page look like for the same example we had. So, first page would uh contain uh first three slots from the contract, and the and array was uh basically is ending up in the page where 78 slots are empty at the beginning, and then uh there are elements of the array.

Uh this is not so efficient uh because uh you're wasting basically these 78 slots, and uh you can only fit 50 elements in the first page. So, whenever you go over 50, your excess, like if you're iterating over an array with a load more pages. And there's one more thing as well. The length itself is uh disconnected to an array, and most of the times you access both length and the data at the same time.

Uh So, this is how it looks like uh for push and pop, it's two cold storage access. And for iterating over 127 in this particular case is three pages because one for length, second one for first 50 elements, and the third one for the rest. And yeah, this is still better than uh compared to like 127 plus uh one, which is 128 cold storage reads.

So, uh what can developers do to optimize this even further is place the length together with the data, and align the starting slot of that data to be page aligned. Uh So, how does it look in that case? It's push and pop are always one or two, depending on the array length. Whenever array goes over the first page, it will be two cold. Uh uh storage access. And iterating over 127 elements is one cold SLOAD because the whole array fits one page.

And uh implementation of this particular array can be found in uh Monad STD library, and we are going to follow up with more data structures uh along. So yeah. What I just explained, it looks like this now. So, on the right side you can see the arrays being uh page aligned and all the data is uh together. So, there's one other example that I've seen across many contracts.

And that's uh people are used to having uh a lot of mappings that are mapping from the same same value to to some different like in this case, let's say there is uh balances mapping and available mapping. What compiler does under the hood, it uses get track of the slot where mapping is reserved and the key it hashes it together and places the value in that particular slot. So, basically these two things would end up very far away.

And the if you are accessing both at the same time, you are getting to cold S loads. So, how to fix it is use a struct, pack the data and map only once. Then, you are getting uh data that is localized. Probabilistically, depends like how big your data is, but there is a chance that it can end up in the same page. And we are also going to write a custom library for mappings as well, so they are also page aligned.

Uh some benefits and unlocks of this. There was a team in the ecosystem, an order book that uh updated uh their contract logic to be page aligned, and they got around 10x improvement for gas costs in order settlement. Uh so, that's quite a lot, and it's uh it's it means a lot for market makers that are going to do place and cancel a lot of orders at the same time. Uh basically contracts that use large chunks of data like met- matrices or arrays, which is basically it unlocks on-chain inference where you can store an AI

model in storage directly, load it, and uh do some inference on on this data, which is uh uh interesting use case. We will see how it uh is going to be used by the ecosystem. And basically any contract, if you use normally, like if you have a couple of storage variables at the beginning of the contract, they will all be in the same page. So, if you of course if you design the storage for uh MIP-8, you're going to get additional benefits, but any contract today will get uh improvements.

So, next steps for this work would be implementing more data structures like linked lists. Currently, I've seen an implement- different implementations of linked lists, but most of them are using mappings, which scatters all the all the nodes across. So, we're going to try to make it localized. Uh queues, trees. Trees are very interesting because a lot of order books are actually using trees.

Uh And uh I'm currently working on designing syntax for custom storage layout in Solidity. And uh yeah, I'm trying to find the proposal that's is going to work together with what was already uh explored by the team. And potentially, this will be contribution from us back to the compiler. uh which is one of the uh goals of uh our team, protocol engineering team at Wan also to contribute back to Ethereum research.

And that's about it. We have 10 minutes for the questions. I planned it. Yes. >> Hi. Hi. Hello. Um so, regarding the gas cost, actually, my question is. So, it exists for a reason, and I assume when you say that there is a 10x gas cost improvements, so on the side of the EVM, the performance increase should be like pretty much the same. So, is it true or not?

>> Wha- The question is is performance is it like if I didn't get what what was the question. >> I mean, um basically, we the gas cost exists uh to limit like the amount of transaction, basically. No, we can uh think about in this way. So, uh you and when you increase the throughput basically by decreasing the gas cost required, you mean that you have to increase your um power of the computation power, basically.

>> Yeah, but uh the the the main unlock here is when you load the data from hardware, you're you're loading 4 kilobytes of data, and everything inside the data is already inside that block is loaded. So, if you localize the data to use it like that, gas costs are the way to like they should be uh showing how much effort does a validator need to execute something. So, if it's warm load or cold load. There's They are there for a reason because if it's warm, it's already loaded. If it's cold, you need to to get it from the disk.

>> Yes, so basically this paging page load is basically more efficient on the validator side on the like uh >> Yeah, it's how hardware works. Basically, you cannot get the one uh 32 bytes >> Mhm. I see. >> or whatever else you you are getting 4 kilobytes. >> All right. And when we speak about the existing contract, so if we do implement the thing, for example, for Ethereum, so um this loading of whole chunks of data, will it be still like feasible on the large existing contracts?

With existing storage layout structure. >> Well, the existing contracts will still work. They uh They They if they didn't use any optimization that that would localize the data, then they will not get the optimization, but what I was saying is if you have like uh uint ABC, when you load A, you you loaded everything else for the for your uh uh contract, but if you have used quite a lot of mappings that are mapping from the same value to few different values, you're getting nothing. So, all of the excess will be warm

uh cold, sorry. >> Yeah, uh I I see it. But will be the will it be cost hardware-wise like the same? So meaning >> It will stay the same for the old contracts. It's a little bit cheaper when you have uh some parts that are already preloaded, but it will be kind of similar, but the costs are going to stay also similar for >> Mhm. >> without optimizations. [snorts] >> Nice. Okay, good. Thank you very much. >> So, I want to ask about contracts that are already deployed. So, let's say that going to Monad right now and deploy a smart contract and you finalize

this proposal. Is it possible to recompile um the Solidity smart contract that I have already deployed and then get the optimization uh after that or is the actual data use uh are going to break the contract because I I change how how things are stored? Is it possible to retroactively use it or not? That's the question. >> a good question, but unfortunately, it's not because uh that would require uh some mechanism for upgrading the contracts with a different code and I'm not sure that's something

>> Okay, but that if if that's available somehow, is it is it possible to do it technically? >> Technically, probably it would be possible that you migrate the data uh somehow, but I don't think uh this will this will happen in any time >> Okay. >> soon. >> Thank you. >> Thank you all for your question. I'm sorry we have to cut it here. Uh give a round of applause to Georgi and let's get ready for our next speaker.

>> [applause and music] [music]