Storage variables are allocated statically and I understand that. I am curious then how dynamic data structures (like mappings) works if they can grow and shrink during contract's life-cycle but memory for them is allocated only once (when contract was deployed)?

(Feel free to correct me if I misunderstood something.)

  • So what I found til now here that says "all values to all possible keys are set by default". Does it means that all memory for mapping data structure is pre-allocated? Then how many keys this structure is capable to hold? Aug 18 '16 at 15:11
  • This is relevant: ethereum.stackexchange.com/questions/1038/… Dec 7 '16 at 15:42

Rewording of Layout of State Variables in Storage.

You need to think in terms of Merkle (or is it Patricia) trie. All stored data is stored under a trie. I understand that branches that have only 0 in their values have a truncated look. This way, this giant trie is not calculated in full. Only the branches that lead to non-zero values are calculated and stored.

You mention that "all values to all possible keys are set by default", it is the same tidbit that reading unset data always returns 0? Well there it is, all because of the truncated trie.

You perhaps know this other tidbit that setting a stored value from 0 to something non-zero costs more in gas than changing an existing non-zero value? That's because the branches down to the value suddenly have to be created. When you change the value, the branches are there, although the hashes change.

This trie is such that each storage slot at the bottom is 256 bits (32 bytes) long. And I understand (prove me wrong) that there are 2^256 such slots.

So, static size data is first packed one after the other from position zero, as per the rules explained in the link. I believe the sequence is determined at compilation. For dynamically sized data, the elements will have to go elsewhere, with a single slot (at position p) the pointer to this elsewhere.

For an array, the first slot (actually, the length field) of this elsewhere is sha3(p), whence static size (and other) data rules apply again.

For a mapping, the value of a k key is stored at sha3(concat(k, p)), whence...

So we end up with a gigantic storage of 32 * 2^256 bytes = 3 * 10^66 Terabytes full of zeroes except at the beginning and some other random places.

This size, plus the nature of sha3 make it unlikely that 2 dynamically sized data will tread on each other, and on position zero. Not theoretically impossible, though, for a smart contract with a giant storage need.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.