0

I am reading this article to understand the storage in Solidity/EVM.

It says that each smart contract has an (independent?) storage and "This storage can be thought of as a very large array, initially full of zeros. Each value in the array is 32-bytes wide, and there are 2^256 such values". Since 2^256 is an enormously high number and each (I suppose only "full") node has to store the same data for each deployed contract I assume only nonzero values are stored. Then how does EVM search for a needed value in the storage? Are the non-zero values ordered increasingly and EVM uses binary search? I probably need a deeper understanding of how computer memory works in low level. If that is the case, is there any accessible article on this topic?

Improve this question
5
  • The article you linked describes how this works :) Read down to the "Locating Fixed-Sized Values" section
    – Carter
    May 22, 2020 at 6:05
  • I have read the whole thing. The problem arises when we locate dynamical sized values though, because we use hash to find the place to store the value. The hash can be very big, so the memory band would be (even astronomically) big.
    – Anh Dũng Lê
    May 22, 2020 at 7:05
  • and there would be a lot of zeros (empty spaces) in between the stored values
    – Anh Dũng Lê
    May 22, 2020 at 7:27
  • You (or article) is mixing up ethereum.stackexchange.com/questions/1232/… Storage is like a hashtable and is not a contiguous array.
    – eth ♦
    May 23, 2020 at 8:33
  • thanks for the answer, but isn't hashtable still an array where the index is hash of the key?
    – Anh Dũng Lê
    May 24, 2020 at 10:17

1 Answer 1

Reset to default
0

Just to be clear, this is about the actual, real implementation of the EVM rather than its more abstract definition. A program running on the EVM just uses the SLOAD/SSTORE instructions as if really had 2^256 words of memory for storage.

Because it is defined by the implementation, in principle, there is no single way that this has to be done. An implementation could use whatever data structure it likes, e.g. hash tables, tries, balanced binary trees... You ultimately just need to map 256-bit keys (addresses) to 256-bit values.

In EVMC, you can find a very simple example implementation for the "host", which handles storage, that uses std::map from the C++ STL (usually implemented as a balanced binary tree). This lives on memory - in reality you probably want something like a database that stores things on disk if you're running a node.

In aleth (now discontinued), you will find they used they used their own database implementation based on a trie structure.

Improve this answer

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.