# Storage Layout for State Network This document attempts to explain a proposed mapping from the Ethereum state trie onto the nodes in a DHT network in such a manner that: - A: Individual nodes store a contigous section of leaf data from the trie along with an accompanying merkle proof anchoring that data to a state root. - B: The data from the trie is evenly distributed among the individual nodes in the DHT - C: DHT nodes can decide how much (or how little) data they wish to store. - D: Leaf data can be retrieved from the network with constant `O(1)` access cost ## Storage Layout Each node in the DHT has a `node_id` which we assume are evenly and randomly distributed across the 32 byte keyspace. For each possible leaf in either the main account trie or an individual contract storage trie, we say it has a `content_id` which dictates it's location within the network. We then define a distance function which determines the proximity between a `node_id` and a `content_id` ```python MODULO = 2**256 MID = 2**255 def distance(node_id: int, content_id: int) -> int: """ Source: https://stackoverflow.com/questions/28036652/finding-the-shortest-distance-between-two-angles A distance function for determining proximity between a node and content. Treats the keyspace as if it wraps around on both ends and returns the minimum distance needed to traverse between two different keys. Examples: >>> assert distance(10, 10) == 0 >>> assert distance(5, 2**256 - 1) == 6 >>> assert distance(2**256 - 1, 6) == 7 >>> assert distance(5, 1) == 4 >>> assert distance(1, 5) == 4 >>> assert distance(0, 2**255) == 2**255 >>> assert distance(0, 2**255 + 1) == 2**255 - 1 """ delta = (node_id - content_id + MID) % MODULO - MID if delta < -MID: return abs(delta + MID) else: return abs(delta) ``` ### Account Trie In the main account trie, an account with address `A` is stored under the key `keccak(A)`. We will refer to this key as `account_trie_key = keccak(A)`. These `account_trie_key` values are randomly and evenly distributed across the 32 byte keyspace. The `content_id` for a leaf node in the account trie is computed as `content_id = account_trie_key`: Nodes in the network would be responsible for storing a contiguous section of account leafs that are closest to their `node_id` along with the accompanying merkle proof data to anchor that data to the latest state root. ### Contract Storage Tries Each contract has its own individual storage trie referenced by `Account.storage_root`. Each of these tries vary in size depending on the contract. Each piece of data in a contract storage trie has a `slot` number which is mapped to the key `storage_trie_key = keccak(slot)`. The data in each individual contract storage trie is randomly and evenly distributed across the 32 byte keyspace. While each contract has a random and evenly distributed set of keys across the 32 byte keyspace, across multiple contracts, commonly used storage slots such as the zero slot will have the same `storage_trie_key` across multiple contracts, meaning that the set of all contract storage keys are **not** evenly distributed aross the keyspace. The `content_id` for a leaf node in a contract storage trie for a contract at address `A` is defined as: ```python MOD = 2**256 def get_content_id(contract_address: int, slot: int) -> int: account_trie_key = keccac(contract_address) storage_trie_key = keccak(slot) content_id = (account_trie_key + storage_trie_key) % MOD ``` By offsetting the `storage_trie_key` by the `account_trie_key` we get the end result that the `content_id` for the set of all contract storage items across all contracts are randomly and evenly distributed across the keyspace. ## What each node stores Each node in the network will store the set of leaves and the accompanying proofs anchoring those leaves to the state root that are closest to their `node_id`. In practice, this means: - All nodes will store a part of the main account trie since it is large. - For contracts with very few occupied storage slots, only a small number of nodes will store that data. - For contracts with a very large amount of used storage slots, many nodes will store the leaf data. The result is that individual nodes in the network will end up storing some section of the main account trie, and some section of the contract storage for a subset of the contracts. For nodes to manage their stored data, they will need to examine the set of all `content_id` values for the data they are storing, and prune the leaf data of the furthest content when their storage is full. ### Satisfying the required conditions Recall that we want this storage scheme to satisfy the conditions - A: Individual nodes store a contigous section of leaf data from the trie along with an accompanying merkle proof anchoring that data to a state root. - B: The data from the trie is randomly and evenly distributed among the individual nodes in the DHT - C: DHT nodes can decide how much (or how little) data they wish to store. - D: Leaf data can be retrieved from the network with constant `O(1)` access cost We know `A` is satisfied because both schemes for deriving `content_id` preserve locality within the individual tries. For both the main account trie and the contract storage tries, the `content_id` values are randomly and evenly distributed. We can also infer that the merged set of these values is also randomly and evenly distributed. This satisfies condition `B`. We know `C` is satisfied because nodes are free to choose how much of the tries they wish to store. We know `D` is satisfied because for any data that someone wishes to access, they are able to immediately identify which nodes in the network should have that data, request it, and verify it using the accompanying proof. ## Nuance for storing data across recent state roots One requirement is that nodes in the network can make multiple requests across disparate peers for the same state root. This can be accomplished by: Nodes would would be storing multiple proofs: - one proof for the section of the account trie they are storing - zero or more proofs for the sections of the various contract storage tries they are storing. For each trie, the node would store a single proof for the latest state root for which they have received data. Each time updated data is received, they would compute a diff against their previous latest HEAD proof, storing a set of reverse diffs allowing them to rewind the latest HEAD proof to a previous state root. Nodes can then choose to discard these revers diffs beyond some recent time horizon such as 256 blocks. Requests for data should come with an accompanying recent state root for which the request is anchored to. Nodes would only respond to requests for data within the range of recent state roots they track. ## Garbage Collection This storage scheme should not need any special functionality added to support garbage collection of data that is no longer part of the trie. ## Data Ingress Pushing data into the network requires generation and distribution of a single proof that contains all leaf data that was touched, modified, or deleted.