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?

tlongeri
  • 13
  • 3
Anh Dũng Lê
  • 243
  • 2
  • 7
  • The article you linked describes how this works :) Read down to the "Locating Fixed-Sized Values" section – Carter May 22 '20 at 06: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 '20 at 07:05
  • and there would be a lot of zeros (empty spaces) in between the stored values – Anh Dũng Lê May 22 '20 at 07:27
  • You (or article) is mixing up https://ethereum.stackexchange.com/questions/1232/difference-between-memory-and-storage Storage is like a hashtable and is not a contiguous array. – eth May 23 '20 at 08: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 '20 at 10:17

1 Answers1

1

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.

tlongeri
  • 13
  • 3