Ethereum storage trie draft

Abstract (TLDR):

Everyone knows that Ethereum uses trie to store its data. However, there are several key points that need to be explored further as followed:

• The tries datas mostly lives in memories. Once it’s written onto the Storage, it is no longer tries, but the Key-value of hash-EncodedData tries’s nodes.
• Tries Structures are quite complex, a small change in the data might lead to the whole tries structure changes.

Prerequisites:

1. Tries structure:

https://www.geeksforgeeks.org/trie-insert-and-search/

2. Modified Merkle Patricia Trie:

https://eth.wiki/en/fundamentals/patricia-tree

Notice that in ethereum implementation, these node types are exchanged to different terms:

• Branch: Full node.
• Leaf: can be either hash/value node.
• Extension: short node.

3. Secured trie:

Ethereum has a wrapped version of trie, which hides the actual key of the object we’re looking for. The secure tries will hash the key, and store the preimage-hash in its Database for subsequent lookup.

For example, the key to the account 0x560089ab68dc224b250f9588b3db540d87a66b7a will be:

keccak256(HexToBytes(0x560089ab68dc224b250f9588b3db540d87a66b7a)) = 39350b18cff4c3c8237915f37ce2ac9b747cba78cda69736c0cb939e7e66cc15

The code document says:

// SecureTrie wraps a trie with key hashing. In a secure trie, all access operations hash the key using keccak256. This prevents calling code from creating long chains of nodes that increase the access time.

However it is unsure how using the keccak256 of the key instead of the key itself will prevent that. This leaves room for future finding.

4. Tries Nodes in implementation:

There are 4 types of nodes as section 2 introduced. The detailed implementation can be seen here.

DO NOT CONFUSE Node’s Key with Node’s hash:

• Each node is identified by its own hash. Hash will help the database lookup (if a particular node is in the database).
• Each node will have its key, which helps the trie-path lookup: if a particular trie contains a particular node.
• An example, to find an account with address 0x560abc in a trie, the key is 560abc. The hash is the keccak256(nodeData). The key will be used to look up the node’s hash. From node’s hash, the data can be retrieved from the Database.

Summary of different node types:

• With a full node, it will have 17 single byte sub keys (as explained in section 2). Each subkey will point to a nil or another node.
• A short node will have a full-encoded path as key. The data from this key is another node.
• Value node is where the data is stored.
• Hash node is where the hash of a node is stored. This hash will serve as the identification to retrieve the node from the Database(since database will store nodes as map[hash]Data)

5. THERE IS NO TRIES, ONLY NODES:

All tries are abstract. Let’s look at the trie.New() implementation:

// New creates a trie with an existing root node from db.

// If root is the zero hash or the sha3 hash of an empty string, the

// trie is initially empty and does not require a database. Otherwise,

// New will panic if db is nil and returns a MissingNodeError if root does

// not exist in the database. Accessing the trie loads nodes from db on demand.

The trie is actually a root, and to “get” a trie, we simply receive the root node. As we move along the key, it will point to different nodes along the way. Hence, the tries structure is not actually available as a separate entity on memory.

Because most of the nodes are in memory, the cost of retrieving a node is neglectable. Some nodes; however, are flushed down to the disk storage, which is costly to retrieve.

Further understanding of this concept can be viewed in the following diagram:

• The Database contain all the nodes (with different colour)
• A new trie with root as the red node, is actually the abstract reference to the red node. It refers to green and purple nodes, as the same concept: All the tries are just reference. They do not actually exist (mark with dash line).
• More brainfuck: A node can be referenced by different tries. Tries 2 with yellow root can as well point to the blue node, which is also a node of trie 1.

Figure 0.1: Database and tries.

Implemented Entities Explanation:

Previous to this section, reader are expected to be familiar with:

• What is a trie?
• What is a hash?
• What is a node in a trie?
• How many node types are there in Partricia Merkle trie?

1. StateDB:

• Each Block comes with a separated StateDB, which is the state trie of that block. It is constructed from a root (which is the stateRoot in block header).
• Each root will have its list of sub-key linking to different accounts. Since Ethereum’s architecture is account-based, a stateDB is actually a list of all active accounts in that block.
• ****To find an account’s data in the stateDB, for example, 0x560089ab68dc224b250f9588b3db540d87a66b7a we must:
• Hash the key: 0x560089ab68dc224b250f9588b3db540d87a66b7a will hashed to 39350b18cff4c3c8237915f37ce2ac9b747cba78cda69736c0cb939e7e66cc15
• Start from the root node, follow the key index to find the next node. Repeat until we data value node.
• The account storage node is always a value node, storing data as the RLP-encoded format: [nonce][balance][storage_root][code_hash]
• From this, the nonce and balance can be extracted. If the account is a contract, then its data will be loaded from the storage root and its codeHash can be checked from integrity.

Example by diagram:

Figure 1.1: StateRoot to AccountData (Simplified). Please be aware that this diagram is simplified. In fact the data of each key in a full node is another hash node. The Data of each short node is another value node.

• Given a state trie consist of 2 account:
• 0x560089aB68dc224b250f9588b3DB540D87A66b7a
• 0x14229bC33F417cd5470e09b41DF41ce23dE0D06b.
• The hashed key for each account is
• 39350b18cff4c3c8237915f37ce2ac9b747cba78cda69736c0cb939e7e66cc15
• 133d04b3fb50108e6a25bd9c80b9efc4401f8ba7b9a6747eaa9931b50073024e
• The state root of block 1 will be:
• a full node (meaning it content 17 sub-key for each path).
• has a hash of 0x3fb2ce6fe574016bb9e24fa0ed163865325c138431a622329db6d7a5328e7413
• Notice that we only have 2 paths with key suffix 1( from 133d04..) and 3 (from 39950…), hence the rest of the key has nil as value.
• To look for account 0x560089aB68dc224b250f9588b3DB540D87A66b7a data at block 1 (Please refer to the underneath diagram):
• First look for the block state root of block 1 (Node Hash: 0x3fb2ce).
• Find the hash key of 0x560089aB68dc224b250f9588b3DB540D87A66b7al, which starts with 3. Look for key 3 in the state root node, it points to another hash node with hash 0x2a513e…
• Resolve this hash, it points to a short node with key 9350b18cff4c3c8237915f37ce2ac9b747cba78cda69736c0cb939e7e66cc15. Note that this key matches the remaining of our key string (after taken out key 3 at the beginning).
• Following the short node key to the value node, which is

f86401a00200000000000000000000000000000000000000000000001bc16d674ec80000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470.

RlP Decode this data here [https://codechain-io.github.io/rlp-debugger/](https://codechain-io.github.io/rlp-debugger/) and draw the conclusion for yourself. Remember the data is in the form of [nonce][balance][storage_root][code_hash].

2. Storage tries:

• Storage tries are similar to the state trie, but are specific to each contract and block.

• Similarly, It is constructed from a storage root. Refer back to the data format of account storage, the storage root is stored in stateDB.

• For smartcontract’s data storage, there is a rule to identify the key to each prime-type data: https://solidity.readthedocs.io/en/v0.6.7/internals/layout_in_storage.html

• Each contract storage will consist of multiple nodes storing each prime-type data. This whole structure will collapse(Hash from the leaf back to its root). To do this, the data has to be inserted first, and the hash is computed later.

Example:

To write a specific data in the contract, for example, contract simple storage deployed at address 0x14229bC33F417cd5470e09b41DF41ce23dE0D06b, and we’re writing data[1]=1 into the contract, we must:

• Find the storage root of 0x14229bC33F417cd5470e09b41DF41ce23dE0D06b. The contract is newly created, its storage root is a hash of nil trie.
• Find the hashed position of testData[1]. testData is the first (and only struct data of contract). Its position in the contract is 0. The key we’re looking at is 1. So, testData[1] has the position of keccak256(uint256(1).uint256(0))= ada5013122d395ba3c54772283fb069b10426056ef8ca54750cb9bb552a59e7d.
• Hash the key for Secure trie, which result in 0x3f9553dc324cd1fd24b54243720c42e18e5c20165bc5e523e42b440a8654abd1
• Insert the key-value pair which is 0x3f9553dc324cd1fd24b54243720c42e18e5c20165bc5e523e42b440a8654abd1:1 into testData[1] into storage trie of 0x14229bC33F417cd5470e09b41DF41ce23dE0D06b,which is a nil trie.
• Collapse the tries to compute the new root, which is 0xcbbbf16ae54eaa34555ac83b610f28e615cc465d358c30aa210799f1f4ef4d4e
• Update the Account Data of 0x14229bC33F417cd5470e09b41DF41ce23dE0D06b to reflect this new root as storage root.
• ****To read a specific data in the contract, for example, contract simple storage deployed at address 0x14229bC33F417cd5470e09b41DF41ce23dE0D06b we must:
• Find the account data of 0x14229bC33F417cd5470e09b41DF41ce23dE0D06b similar to section stateDB. Get its storage root, which is 0xcbbbf16ae54eaa34555ac83b610f28e615cc465d358c30aa210799f1f4ef4d4e
• Create new trie from this root. It has only one node which is itself.
• Find the hashed position of testData[1]. testData is the first (and only struct data of contract). Its position in the contract is 0. The key we’re looking at is 1. So, testData[1] has the position of keccak256(uint256(1).uint256(0))= ada5013122d395ba3c54772283fb069b10426056ef8ca54750cb9bb552a59e7d.
• Hash the key for Secure trie, which result in 0x3f9553dc324cd1fd24b54243720c42e18e5c20165bc5e523e42b440a8654abd1
• Lookup this key in the trie, it linked to the value node 01. Return it.

QUESTION FOR YOUR OWN THINKING:

• Imagine there are 2 contracts, A and B, deployed from the same code, to different address 0x

3. Database:

• This is the implementation to contain the whole’s Ethereum data operation. It contains both memory DB and disk DB.
• Different from StateDB, it is a map[Hash]Node. It doesn’t care about tries, rather, it keeps track of all the Hash there are and the associated nodes. The different tries (block 0’s State trie, block 1’s State trie, Contract 0x11’s storage trie at block 1 etc…) will lookup these nodes and construct its own tries.
• Think of Database like a LEGO store, with a lot of different pieces (nodes). To construct a specific toy (tries), you have to collect different pieces from Database (LEGO store) and construct it.
• The memoryDB is simplified as dirties. Dirties in this sense meaning that it is changed in the current context. A database limit is memory usage by its dirties-Size. Anything beyond that will be Garbage collected.
• Garbage collection, or state pruning, is done by Reference counting. The process is described as follow:
• Each instance of go-etherum will have a predefined number of stateDB tries in mem, which is X. Refer to the previous section, each Block will have a stateDB. In the case of a non-tx block, the stateDB of the previous and new block will be the same.
• At block N, keep track of all nodes in state trie, tx and receipts tries as well as Storage trie. All the nodes will be put into a queue, and mark for Delete at a feature block N+X.
• Any account change at a Block M>N, the reference reset, and the particular node will be deleted at M+X.
• Further details are explained here. However, you can skip it if you haven’t the time for now. The article is confusing anyway.
• The reference implementation set X to 128 only references accounts data and to its stateDB root. Account’s storage, however, are not referenced by DB implementation. This meant that after 128 blocks, if the data is not changed, it will not be in the memory database.
• There is a special flag to set the node to either “full” or “archive node as follow:

—gcmode value Blockchain garbage collection mode (“full”, “archive”) (default: “full”)

If the node is set to archive node, it will still be able to serve the contract’s call after 128 blocks as the “pruned” node will still be available from disk storage. If it is in the default mode, as full mode, if the data is not referenced to, after 128 blocks it is lost.

Example by diagram:

Figure 1.2: Reference example. The manual reference is noted by a dashed line. The automatic reference (trie’s connection) is noted by a solid line.

• The example is the nodes and its reference in block 1 (latest block).
• The SC bytecode data node (be3b27d) is not directly linked to the **Smart contract account. I.e, there is no direct reference between smart contract and its bytecode storage. Hence, there must be a manual reference between Smartcontract account and its bytecode data.
• The metaroot, i.e, 0x0000, is the starting point of all reference tracing. Block 1 state root, being the most recent block, will be manually referenced to this metarrot.
• The SmartContract account node and the EtherbaseNode, being a leaf of the block1’s state root, hence it is referenced automatically via StateDB.Commit().