Understanding Ethereum From the Ground Up (Data Storage)

Preface: The following article aims to consolidate knowledge, as I learn about Ethereum. If any information is incorrect, partially incorrect, or incomplete, I wholeheartedly welcome your input.

Purpose: I’ve gotten the sense that the information necessary to properly make sense of Ethereum data storage is highly fragmented and lacks illustrative examples. This article aims to remedy that by consolidating and clarifying knowledge on how Ethereum stores data.

Article Structure: In this article, we’ll cover the following concepts:

• What Ethereum data is stored
• Where Ethereum data is stored (distributed databases)
• How Ethereum data is stored (data structures)
• How encoding lays the groundwork for hashing
• A Merkle Patricia Trie example

What Data is Stored?

A blockchain is a “chain” of linked (strictly formatted) groups of data (“blocks”). In the Ethereum blockchain, each new block of data added to the “chain of blocks” is comprised of:

• a block header
• a list of Ethereum transactions
• a list of “ommer” (uncle) block headers, of the same format as the block header mentioned above

For now, let’s focus on the block header, as it is most relevant to the data storage we’re covering. The following diagram in Figure A, taken from Preethi Kasireddy’s article, “How does Ethereum work, anyway?” clearly illustrates the information contained in a block header (I modified it slightly):

Figure A:

Source: https://www.preethikasireddy.com/post/how-does-ethereum-work-anyway

Regarding data storage, the stateRoot, transactionsRoot, and receiptsRoot are important, as they represent Keccak 256-bit hashes of the root nodes of three separate “Merkle Patricia Tries” (an Ethereum-specific data structure). We’ll cover this data structure in detail below. All three tries store key-value pairs, so for our purposes, we’ll express them using the notation, key → value.

• stateRoot: The Keccak 256-bit hash of the World State Trie, σ. This trie contains mappings between addresses, a, and account states, σ[a]. More specifically, the key-value mapping is a mapping between the Keccak 256-bit hash of Ethereum public addresses, keccak(a), to the “RLP” encoded account object, RLP(accountState), which can be expressed as keccak(ethereumAddress) → RLP(accountState). See my previous article on Ethereum accounts, if unclear on what an Ethereum account or account state is. Also, we’ll discuss RLP encoding below. As shown in the Yellow Paper, Figure B depicts a formal representation of world state:

Figure B:

Ethereum Yellow Paper’s World State explained.

• transactionsRoot: The Keccak 256-bit hash of the root node of a trie structure populated with each transaction in the transactions list portion of the block. Each new block has its own transactions trie, in which key-value pairs take the form, RLP(transactionIndex) → RLP(ethereumTransaction), where transactionIndex refers to the index of a transaction within its block and ethereumTransaction is an Ethereum transaction object. Once mined, this trie is immutable.
• receiptsRoot: The Keccak 256-bit hash of the root node of the trie structure populated with the receipts of each transaction in the transactions list portion of the block. Similar to transactions tries, each block has its own receipts trie, in which key-value pairs take the form, RLP(transactionIndex) → RLP(transactionReceipt) where transactionIndex refers to the index of a transaction within its block and transactionReceipt is an Ethereum transaction receipt object. Once mined, this trie is also immutable.

The following diagram in Figure C clearly illustrates the above concepts. Namely, the components that comprise a block and the data that stateRoots, transactionsRoots, and receiptsRoots represent. It’s worth taking some time to digest this image, as it’s information-dense.

Figure C:

Source: https://i.stack.imgur.com/afWDt.jpg

Where’s the Data Stored?

As mentioned in my previous article on Ethereum accounts, Ethereum is a network of computers, which each run software, called an Ethereum client. A client software installation will also install a key-value storage library (a type of database), such as LevelDB or RocksDB. Each node stores its data within its installed key-value storage library, which results in the same data distributed among all nodes of the same type —keep in mind, there are different types of nodes: archive nodes, full nodes, and light nodes. To illustrate this idea, see Figure D below:

Figure D:

A network of nodes, where each node has its own database.

How’s the Data Stored?

Now that we know what data is stored and where it resides, let’s discuss how it’s stored. From above, we know that Ethereum makes use of a key-value storage mechanism. To be clear, a key-value storage library stores key-value pairs. As a high-level example, think of something similar to a Python dictionary or a JavaScript object. This implies that ultimately, whatever data structure is used must fit nicely into a key-value storage structure. Also, since every full node replicates stored data, it’s extremely important to compress data where possible to conserve storage space. To achieve both of the above, Ethereum employs a data structure called, a “Modified Merkle Patricia Trie”.

Merkle Patricia Tries Explained

A Key-Value Structure

The Merkle Patricia Trie is a unique data structure that combines the data-compression elements of a Patricia trie and the deterministic hash properties of a Merkle tree. A “node” in a Merkle Patricia Trie can be thought of as a small data structure that’s within the larger trie structure, and all nodes must fit into a key-value database. To achieve this, each key-value pair takes the form, keccak(RLP(node)) → RLP(node). To be clear, each key is a hash of its corresponding value. That said, from above, we know that stateRoots, transactionsRoots, and receiptsRoots are hashes of tries that store their own key-value pairs — this implies that these three tries’ keys and values must be stored within nodes, themselves. More specifically, they’re stored in sequences of parent and child nodes that comprise the overall Merkle Patricia Trie data structure. In the key-value pair above, RLP stands for “Recursive Length Prefix” encoding. Encoding is used to represent data in a way that is utilizable for some use case. Here, the use case is to transform the node (a sub-data-structure) into a format that can be hashed, as hashing functions need input data in the form of a byte array. The RLP encoding algorithm achieves exactly that: it transforms a structured node into a byte array, such that it can be hashed.

Let’s Make Storage Efficient (Patricia Trie Influence)

Given a large amount of hexadecimal keys (hashes of RLP-encoded nodes), it’s likely that many keys will share common “paths”, which are shared, non-divergent subsets of characters among many keys. For example, the words “car” and “cars” share a common path, “car”. In this sense, a common path is analogous to the trunk of a (organic) tree, while divergent paths are analogous to its branches. If multiple keys share common paths, then storing the whole keys independently is redundant. The common path only needs to be stored once, and divergent branch paths can be handled exclusively at points of divergent characters. Such a storage structure is called a Prefix Trie. That said, storage efficiency can still be improved: if a node only has one child or if a sequence of one-child nodes arises for a given data set, then that sequence of one-child nodes can be condensed into a single node. Such a structure is called a Patricia Trie. A Patricia Trie stipulates that all internal nodes must have at least two children. Figure E, taken from Kamil Jezek’s paper, “Ethereum Data Structures”, depicts both Prefix and Patricia Tries for a given set of binary keys to store. In Ethereum, however, the keys would be hexadecimal characters, not binary digits. It is this data compression technique that accounts for the “Patricia” part of a Merkle Patricia Trie.

Figure E:

Source: https://arxiv.org/pdf/2108.05513.pdf

Merkle Patricia Trie Node Types

To achieve the aforementioned data compression, a Merkle Patrica Trie utilizes three types of nodes. Keep in mind, key-value pairs in a Merkle Patrica Trie take the form, keccak(RLP(node)) → RLP(node).

• Extension node (2-item): node ≡ [encodedPath, key], where key represents, keccak(RLP(node)) and encodedPath represents HP(prefix + path) , where HP is a “Hex Prefix Encoding” function (more on that below). After substitution, an extension node can be expressed as node ≡ [HP(prefix + path), keccak(RLP(node))]. Extension nodes play a large role in data compression, as they are responsible for grouping common paths among keys (before and after branch nodes).
• Branch node (17-item): node ≡ [branchCharacters, value], where branchCharacters are the first 16 elements of the array, and value is the 17th element. The branchCharacters represent the 16 possible hexadecimal characters that a path can take, from one character to the next in a key (0-F); each index (0–15) is either NULL or holds the hash of a child node, keccak(RLP(childNode)) (a new key). The value represents an optional terminating parent extension node’s value, such as RLP(accountState), RLP(ethereumTransaction), or RLP(transactionReceipt) depending on which trie you find yourself in; it’s NULL if its parent node is not a terminating extension node.
• Leaf node (2-item): node ≡ [encodedPath, value], where value represents a key’s terminating RLP-encoded value and encodedPath represents HP(prefix + path). Leaf nodes terminate paths in a trie, and they also contribute to data compression, as they group together single child node sequences (key suffixes) into one node. Such data compression is also Patricia-Trie-influenced.

The following diagram in Figure F, also taken from Kamil Jezek’s paper, “Ethereum Data Structures”, clearly depicts Merkle Patricia Trie node types and their function for a simple key-value storage example:

Figure F:

Source: https://arxiv.org/pdf/2108.05513.pdf

Nodes Are Cryptographically Linked (Merkle Tree Influence)

Notice above that each key: N1, N2, N3, N4, and N5, is the Keccak 265-bit hash of an encoded node. Also, notice that parent nodes, N1 and N2 contain hashed child nodes (N2 and N3, respectively); this is where the Merkle Tree influence comes in. Given that parent nodes are hashes of nodes, which contain the hashes of their child nodes, each parent is deterministically linked to the data that its children hold. Since the root node is effectively the parent node of the entire trie, it is deterministically linked to all of the data that the trie comprises. A change in any node in the trie will result in a different root node hash. This property makes comparing large datasets simple — one could simply compare the root hashes of two data sets, rather than compare each block of data against a block in another data set. Given hashes’ deterministic properties, if the root hashes differ, the datasets are not the same. For reference, Figure G below depicts a binary Merkle Tree, where every non-leaf node has two child nodes. To be clear, a binary Merkle Tree is not directly relevant to a Merkle Patricia Trie, but I’ve included it to better understand its cryptographic influence. The bottom layer: L1, L2, L3, and L4, represent the data that comprise the tree.

Figure G:

Source: https://en.wikipedia.org/wiki/Merkle_tree

Key observations:

• Leaf nodes are cryptographic hashes of chunks of data
• Branch nodes are hashes of their two child nodes, which themselves are hashes
• All leaf nodes are at the same depth
• The tree converges to one root node at the top

Similar to above in a Merkle Patricia Trie, parent nodes, including the root node, are deterministically linked to the data that resides in their children, which allows for efficient comparison of data sets.

How Encoding Lays the Groundwork for Hashing

Recursive Length Prefix (RLP) Encoding

Given keccak(RLP(node)) → RLP(node) as a key-value pair format, we know that each key in a Merkle Patricia Trie is a keccak 256-bit hash of its corresponding value. This implies that that value, itself, must be in a suitable format to be the input of a hashing function. As mentioned above, a hashing function requires that its input is a byte array. This requirement is what gives rise to the use of RLP encoding, as it accomplishes exactly that: it encodes a structured node into a single byte array. This encoding method can take in a set of structured or arbitrarily nested input arrays and serialize them into one output byte array, suitable for hashing. Since values are also RLP encoded (not encrypted), they are easily decodable. The purpose of encoding is to structure data into a particular format for a use case, whereas encryption hides data, only to be made accessible with some sort of secret key.

Hex Prefix (HP) Encoding

Notice above that leaf nodes and extension nodes are both 2-item nodes — they have the same structure. Moreover, the first element in each both take the form, HP(prefix + path). With this in mind, there must be a way to differentiate between the two. We know that both extension nodes and leaf nodes consolidate one-child node sequences into one node, either representing a common path (in the case of an extension node) or a key’s suffix (in the case of a leaf node). Each hexadecimal character in these consolidation sequences is called a “nibble”. To differentiate between an extension node and a leaf node, an extra nibble (hexadecimal character) can be added as a prefix to the node’s current nibbles. Then, depending on this newly-added character’s value, we can derive information about the node, including node type. Remember, hexadecimal characters can be converted to the binary number system, such that each character represents 4 bits.

Prefix Rules: Since 4 bits can be used to represent a hexadecimal character, we can think of such a “node-type-deciphering” prefix nibble as a 4 bit prefix. With this prefix, we can instill the following rules for extension and leaf nodes:

• Even or Odd: The lowest-order (rightmost) bit tells us whether the length of the “single-node character consolidation sequence” (a node’s nibbles) is even or odd, where 0 = even and 1 = odd
• Node Type: The 2nd-lowest-order (2nd rightmost) bit tells us whether the node is an extension node or a leaf node, where 0 = extension and 1 = leaf

With the above rules, we can now decipher between extension nodes and leaf nodes via adding and interpreting a prefix hexadecimal character (nibble). Figure H below illustrates this prefix and its encoded meaning:

Figure H:

Source: https://arxiv.org/pdf/2108.05513.pdf

Byte Arrays Need an Even Number of Nibbles: Curious readers may question the importance of knowing whether path lengths are odd or even. The reason for this is that once again, we need to fit the prefix + path, in HP(prefix + path), into a byte array, as most computers store bytes, not half-bytes (nibbles). The addition of a prefix nibble to a set of nibbles of even length would result in an odd length of nibbles (an even number plus one is an odd number), which cannot fit properly into an array of bytes. Remember, it takes 2 nibbles (4 bits each) to comprise 1 byte (8 bits), implying that a byte array needs an even number of nibbles. For cases such as these (where the total number of nibbles after the addition of a prefix nibble is odd), an additional nibble, 0, is inserted after the first prefix nibble to make the total number of nibbles even, such that a proper byte array can be achieved. Here, these two newly introduced nibbles make up the “prefix byte”. If, on the other hand, the addition of a prefix nibble results in an even-length path (where the total number of nibbles after the addition of a prefix nibble is even), then the node’s first non-prefix nibble is included directly in the prefix byte, following the prefix nibble. See the example in Figure I below:

Figure I:

Source: https://arxiv.org/pdf/2108.05513.pdf

Once keys to extension nodes and leaf nodes have been HP encoded, they, along with their values, can be RLP encoded, making them ready to be hashed. The result? We can hash nodes to make Merkle Patricia Trie keys, and we can also differentiate between leaf nodes and extension nodes (branch nodes are obviously differentiable, as they are 17-item nodes).

Merkle Patricia Trie Example

Now that we have a decent conceptual understanding of the Merkle Patricia Trie data structure, let’s go through a concrete example, which can be found on the Ethereum Wiki, to solidify our knowledge. Suppose we want to store the following key-value pairs: ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion').

• First, both keys and values are converted to bytes (the example only shows keys in bytes for easier comprehension):

<64 6f> : 'verb'
<64 6f 67> : 'puppy'
<64 6f 67 65> : 'coin'
<68 6f 72 73 65> : 'stallion'

• The key-value pairs can then be constructed into a Merkle Patricia Trie, as shown below in Figure J:

Figure J:

Key observations:

• All keys start with a shared path of 6, which is why 6 makes its way into the HP(prefix + path) portion of the extension node associated with the rootHash. Said another way, all keys share a common nibble, 6. Given that the set of common nibbles is of length, 1 (odd), the addition of the prefix nibble, 1, is sufficient for constructing a byte array, so the nibble, 6, is added directly to the prefix byte following the prefix nibble, per HP encoding rules.
• A divergence of paths happens at the second nibble: three keys have a second nibble, 4, and one has 8. For this reason, the 4th and 8th index of the branch node pertaining to hashB are non-null.
• All extension nodes’ values are hashes (keys) to new child nodes.
• There are cases where some nodes contain other nodes, such as nodes with keys, hashA and hashE. When the RLP encoding of a child node is less than 32 bytes, the child node is not hashed and is included directly inside of the parent node — another data compression technique.
• The values, ‘verb’ and ‘puppy’, are values within branch nodes, but they actually represent terminating values to their parent extension nodes, as extension nodes do not contain a “value” field — they contain child node keys instead.

Conclusion

It is my hope that Ethereum data storage makes a bit more sense after reading this article. If you’d like to stay up-to-date with new Ethereum and Web3 learnings, feel free to subscribe to my newsletter! Thank you.