How does Ethereum fit a mapping into storage?

Question

Probably a silly question, but how does Ethereum fit a mapping into storage? I am used to simple types like arrays, so I don't understand how "Solidity's mapping uses the entire 256-bit addressable memory space." I am guessing its something simple like only non-zero values take up space, but I would like to know what code/algorithm/concept was used to achieve this. Thanks!!!

Answer 1

When you declare a mapping like in the following contract :

contract MappingExample {
    mapping(address => uint256) balances;
}

The variable balances is assigned to storage slot 0 (simply because it is the first one). But the mapped elements are elsewhere.

To compute the storage slot or location of the mapped elements, the following is used :

slot = keccak256([key, mappingSlot]) // concatenate key and mapping slot

The thing is that non allocated storage slots default to the value 0. So every key that was not assigned a value points to a non allocated storage slot for which the EVM can return the value 0 directly. There is no need to actually store 2^256 - 1 slots just because a mapping was declared.

If you are curious about that you can see the implementation of the SLOAD OPCODE in go-ethereum here that calls the evm.StateDB.GetState method defined here:

func (s *StateDB) GetState(addr common.Address, hash common.Hash) common.Hash {
    stateObject := s.getStateObject(addr)
    if stateObject != nil {
        return stateObject.GetState(s.db, hash)
    }
    return common.Hash{}
}

As you can see, if stateObject == nil then common.Hash{} is returned. This is a zeroed 32 bytes array. Basically, a zeroed out storage field that doesn't need to be stored in case the address has not state associated to it.

In turn (not directly) it will call GetCommittedState defied here. This method is pretty big so I'm not pasting it here, the same logic follows if the key cannot be recovered from the state trie a default value of 0 will be returned.

So, refining our example a little:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.10;

contract MappingExample {

    mapping(address => uint256) balances;

    constructor() {
        // Setting balance of an arbitrary address.
        balances[address(0x10)] = 100;
    }

}

You can read balances[address(0x10)] with the following Web3 code:

import Web3 from "web3";

const web3 = new Web3("http://localhost:8545");

// ADDRESS OF OUR CONTRACT (CHANGE IT FOR YOUR OWN)
const contractAddress = "0xd4EC28074b7A66F536D9feCf9b2f81B962215e69";

// STORAGE SLOT OF THE MAPPING
const mappingSlot = '0000000000000000000000000000000000000000000000000000000000000000';

// KEY THAT WE WANT TO READ IN THE MAPPING
const key =         '0000000000000000000000000000000000000000000000000000000000000010';

// COMPUTE THE ACTUAL STORAGE SLOT OF THE VALUE ASSOCIATED WITH THE KEY
const balanceSlot = web3.utils.soliditySha3({t: 'bytes', v: key + mappingSlot});

const balance = await web3.eth.getStorageAt(contractAddress, balanceSlot);
console.log(web3.utils.toNumber(balance));
// DISPLAYS : 100

Because the hash (interpreted as a storage index) is stored in the EVM, any unknown value will return a 256 bit 0 value as shown in the GetState function, this 0 value doesn't need to be stored.

In essence, every value in a mapping is mapped to something. But not all values are stored in the contract storage space, only the values that have been set. Making it a quite efficient structure that doesn't require every node to allocate 2^256 - 1 bits for each mapping in existence.