In previous blog post of the series about Ethereum storage (see full list of posts at the end), we explained how Ethereum storage works for simple contract with fix sized variables.
In this blog post, I will continue explain how dynamic sized variables like map and array works, and we will also walk through real world examples to explain and test cases to verify the formula.
Ethereum storages values in 32 bytes wide slots. Slots are indexed by a uint256 number.
For static sized variables, they are stored sequentially in slots.
Note, the slot index is not a global index, but relative within a smart contract. Each contracts stores variables sequentially from slot 0 (slot index is 0):
However, for dynamic sized data structure like map or array, the storage position of their items can not be stored sequentially in slots. Instead, the slot position for items is calculated using some formulas based on item key in a map or item index in an array.
Let’s go through each of them.
For map, the slot index for each item (key-value pair) is calculated as:
Let’s look at a real world example and verify the above formula.
The USDC contract uses a map variable to store each USDC holder’s balance. The key is the USDC holder’s address, the value is a uint256 value as the holder’s USDC balance:
How to get the storage location for a certain account’s USDC balance? For instance the USDC balance of account 0x467d543e5e4e41aeddf3b6d1997350dd9820a173. Let’s just call this account, account K.
According to the formula, in order to know the slotIndex for the this account, we need to know the map key, which is the account address 0x467d543e5e4e41aeddf3b6d1997350dd9820a173.
And we need to know the slot index for the map variable, which is 9. How do we know that? I will explain later.
With these data, let’s compute the slot index for the account’s USDC balance:
Note that both the key and the slot index for the map variable needs to be 32 bytes long left padded with zeros before passing to the keccak hash function.
The computed slot index for account 0x467d543e5e4e41aeddf3b6d1997350dd9820a173is 0x4065d4ec50c2a4fc400b75cca2760227b773c3e315ed2f2a7784cd505065cb07.
With the slot index, we can query the proof from a full node using eth_getProof method and verify it:
With the Merkle proof, we can verify it by creating a Merkle trie in local and traversing the path from the root node with contract storage root hash, which is included in the proof, all the way to the leaf node. We have explained this in previous blog post. The detail can be found in the source code linked at the end of this blog post.
The storage value is 140080592961691. After verifying the proof, if it’s valid, then we know the USDC balance, which is 140,080,592.961691 USDC token at block 15245000 (0xE89EC8).
OK. Let’s go back to the previous question, how did we know the slot index for the map variable balances is 9?
We could use a brutal force approach to find it.
Since contract variables are stored in each slot sequentially, we could iterate through each slot index starting from 0. For each slot index, we assume the target map variable is stored in that slot, and use the formula to get the slot index for the balance of an account, and then use the eth_getStorageAt method to get the value stored at that position within the contract.
If the slot index is incorrect, then it will return 0, meaning nothing is stored at that location, and we should try another slot index.
If the slot index is correct, then it should return the balance, and we can simply verify it against the balanceOf interface method call.
This is one way to find slot index for a state variable. Although not very efficient, it’s probably enough, since a smart contract can’t define too many variables. And you only need to iterate through once, once you have found the slot index, you can save it to use for next time, since smart contract can’t be updated after deployed.
OK, we’ve explained how dynamic sized variable like map stores its items (key-value pairs). Next let’s take a look another dynamic sized data structure — Array.
For array variable, the slot index for each array item is calculated as:
And the array length is stored at the slot index of the array variable, and then all the array items are stores sequentially from the slot at the hash of the slot index of the array.
Let’s look at another real world example and verify the above formula.
This time, we will dive into the popular NFT contract — CryptoKitties.
CryptoKitties smart contract uses an array variable, called kitties, to store the meta data for each crypto kitty:
We will explain the Kitty data structure later.
The slot index for the kitties variable is 6, which can be found using the same approach I explained earlier.
Now we can query the kitty count, which is the length of the kitties array from slot 6 using eth_getProof.
It returns the storage value as 0x1eb82c, meaning there are a total of 2013228 kitties at block 15244590 (0xE89D2E).
Now let’s look at how to get each kitty data from the kitties array.
Kitty is a struct that takes two words, meaning, each kitty data will take two slots to store. The first slot stores the kitty genes, which is a uint256 number, and the second slot stores the rest of the kitty’s properties:
Since each array item is stored sequentially starting from the first item, we can calculate that Kitty 1, for instance, will be stored at slot index: 1.
So the slot index for Kitty 1 is 111414077815863400510004064629973595961579173665589224203503662149373724986689 , a very big number.
With the slot index, we can request proof for the storage data the same way as for the USDC account balance example explained earlier:
The above query should show the storage value for Kitty 1 at the first slot is 0x5ad2b318e6724ce4b9290146531884721ad18c63298a5308a55ad6b6b58d. This is the hex format of the Kitty 1’s genes — 626837621154801616088980922659877168609154386318304496692374110716999053, which is a uint256 number.
If we use CryptoKitties’ getKitty method to query Kitty 1’s genes on Etherscan, it should return us the same number.
In this tutorial, we explained how dynamic sized variable is stored in smart contract, such as map and array. And how to query the contract variable from storage and how to verify the proof for the storage value.
This is the last blog post of the full series about Ethereum storage. This is the full list of blog posts:
The source code of the above code and test cases are open sourced as below:
The rich text element allows you to create and format headings, paragraphs, blockquotes, images, and video all in one place instead of having to add and format them individually. Just double-click and easily create content.
A rich text element can be used with static or dynamic content. For static content, just drop it into any page and begin editing. For dynamic content, add a rich text field to any collection and then connect a rich text element to that field in the settings panel. Voila!
Headings, paragraphs, blockquotes, figures, images, and figure captions can all be styled after a class is added to the rich text element using the "When inside of" nested selector system.