How Ethereum client can provide the state of contract variables with Merkle Trees

Question

I'm struggling to understand the whole flow of how retrieving data from the Eth client db(LevelDb/RocksDb) works. So for example, I trigger contract to return value of some field -> what are the detailed steps made by eth client?

1. Go to the latest block? Is state copies preserved for each block?
2. Iterate the world state tree leaves to find contract's address hash
3. The leaf will contain account storage root hashes?
4. Using the hash from storage root eth client will get another tree with contracts storage tree?
5. Iterate the leaves of account storage tree to find variable's name hash?
6. take this hash and retrieve its value?

All these data should be formatted and stored in LevelDb/RocksDb, where each hash will be a key and value will contain another tree of hashes or value, correct?

Answer 1

This is a very broad question because different clients may have different implementations (e.g. Erigon). I will use the go-ethereum(Geth) client's database to walk through step by step with python code. In summary the steps:

1. Use block_number -> encode it to become the key to get blockhash (can be skipped if blockhash is known by you). Follow go-ethereum Source
2. Use block_number + block_hash -> encode them to become the key to get the required block header. Follow go-ethereum Source
3. Get the state_root as the 4th element in the block header. I think most clients can skip to this step if you query recent blocks since they should cache recent block headers in memory. OP refers to "trigger contract" so it should be the latest block header and skipping steps 1 and 2.
4. From state_root, find address's state by traversing the state Merkle Patricia Trie with the path to be the keccak256(address)
5. At leaf node, rlp.decode the node value to get: (nonce,balance,storageRoot,codeHash)
6. Understand the contract storage layout to know which storage slot number to retrieve with a certain variable. In bytecode SLOAD, everything is just slot number. This step is simplified and we do it manually here. Note that, it will be trickier to manually compute the slot number of variables being dynamic array or mapping. In reality, when you call test_var() to read test_var or to execute a contract function, the ETH node will load bytecode of the contract and execute it to eventually reach an opcode SLOAD slot_numer. This is the slot number we talk about. Besides, eth_getStorageAt can also be used to retrieve the stored value directly from eth node without running any bytecode.
7. Traverse the storage trie (another Merkle Patricia Trie) from storageRoot, this time the path is keccak256(uint256 slot_number)
8. Decode the rlp encoded stored value at the leaf node and use that to decode the variable's value (everything is 256-bit binary, you must decode it according to your data)

The below illustration shows how the steps are performed just by key-value query on the same database. I also uploaded the snapshot jupyter notebook link of the below code

---

==== TLDR with python code: skip this step if you don't want to try it from scratch.

First, set up testing environment:

• Start geth dev mode: geth --dev --http --http.api eth,web3,net --http.corsdomain "https://remix.ethereum.org" --datadir data
• Deploy a test contract

contract Test {
    uint public test_int = 123; string public test_str = "mystring";
    function set_new_value() public {
        test_int = 456; test_str = "newstring";
    }
}
// storage layout:[{...,"label": "test_int", "slot": "0"},
//                 {...,"label": "test_str", "slot": "1"}],

At the start block 0, we deploy contract -> block 1 , the contract address is 0x568B6B552311415cb5a4139324F8d2Ef43F06086 , we call set_new_value -> block 2. This means block1's test_int will be 123 and block2's test_int will be 456. Our objective is to get storage slot 0 of account 0x568B... at a specific block number from levelDB.

---

==== The steps to get storage slot of specific account at specific block: Let's stop geth and use python to read the levelDB stored at ./data/geth/chaindata

Step 1-2: from block number retrieve block hash and the key to get blockheader, it's encoded following the convention in go-ethereum/core/rawdb/schema.go: key to get block header = 'h' + block_number(uint64 big endian) + block_hash.

import plyvel
db = plyvel.DB('./data/geth/chaindata')
BLOCK_NUMBER = 2
block_hash_key = bytes('h','ascii') + (BLOCK_NUMBER).to_bytes(8, byteorder='big') + bytes('n','ascii')
print(f"key to retrieve blockhash {block_hash_key.hex()}")
# To save space I wont include printing code, basically all the printing is to print hex() from python bytes data.
block_hash = db.get(block_hash_key)
block_header_key = bytes('h','ascii') + (BLOCK_NUMBER).to_bytes(8, byteorder='big') + block_hash

Output: blockhash: ddcad...e6 => key to get block header : 680000000000000002ddcad2...e6

---

Step 3. Get state. Note that from now on, we will always use rlp.decode to decode data. Block header in go-ethereum code currently has 16 fields and field index 3 is our state_root:

from rlp import decode
encoded_block_header = db.get(block_header_key)
decoded_block_header = decode(encoded_block_header)
state_root_key = decoded_block_header[3]

Output : state_root_key: 8182c...b280e00

OP's question about historical state: depends on the node type. If you have an archive node it's preserved, otherwise it may be pruned

---

Step 4-5: Get state trie and traverse to the leaf node. Here the path to get state of an address is the hash of it, not the address itself For example, we want to get state of address 0x568B6B552..., we hash it to become 0xcad521f13bc... and use it as the path for traversing the Trie

state_root = db.get(state_root_key)
contract = '568B6B552311415cb5a4139324F8d2Ef43F06086'
contract_bytes = bytes.fromhex(contract)
from Crypto.Hash import keccak
k = keccak.new(digest_bits=256)
k.update(contract_bytes)
k.hexdigest()
# cad521f13bc426efce4df4d4415fd22e6b1a3944184ef7e5b927f91adf4d1a5e # the path for looking up account state

Now you can use Merkel Partricia Tree library to traverse this path to find the value of the leaf node. However I used python and I cant find any well-maintained library for this available, so I traverse it on my own. Luckily the leaf node and it's value is just 1 node from the root:

new_node_key = decode(state_root)[int('c',16)]
new_node = decode(db.get(new_node_key))
decoded_node_value = decode(new_node[1])
storage_root_key = decoded_node_value[2]

rlp decoded leaf node of the state trie ['3ad521f13bc426efce4df4d4415fd22e6b1a3944184ef7e5b927f91adf4d1a5e', 'f8440180a08aae69e49c0f1ba27321eb22c5bdde654bcf9024eb0b9ec3edd1ad5a1512bdd2a074e425048bf866ebdf6ea6a79dc2164850cfba9a234de6403283966afbb06f28'] 
decoded leaf node value  ['01', '', '8aae6.....512bdd2', '74e425...28']

With OP's attached image, we know that this tuple is (nonce,balance,storageRoot,codeHash).

---

Step 6,7,8: Get storage slot from traversing another Trie with root retrieved from previous step. Interestingly, in this Trie, the key to get the value is not the slot number but the hash of it.

# You have to pad-left the value to 256 bit for this hash
# keccak256(0) = 290decd9548b62a8d....3e563
# keccak256(1) = b10e2d5276....b7fa0cf6
storage_root_node = decode(db.get(storage_root_key))

Next, we get the test_int var: slot 0, path for the trie 290decd9548b62a8d....3e563

# Traverse the Trie we get the leaf (also 1 node away from root because our test chain is simple)
new_storage_node = decode(db.get(storage_root_node[2]))
print ("leaf storage node ", [item.hex() for item in new_storage_node])
print ("storage value : ", int.from_bytes(decode(new_storage_node[1]), "big"))

Output:

• Leaf storage node ['390decd9548b62a8d60...563', '8201c8']
• Storage value : 456

Here, to construct value 456 you have to rlp.decode the leaf node value 8201c8 first, then you convert it to int.

The same thing can be done for other contract addresses, other storage slots and other block number (The trie traversal may not be simple as I showed you where the leaf node is just 1 step away from root node).

Notes: There are definitely other mechanisms that were not covered in this example, they can be client-dependent (caching, other DBs), contract-dependent (e.g. immutable constant variable are stored in code, not in storage) or node-dependent (light client, full-node,...)