From Trie to Ethereum MPT

From Trie to Ethereum MPT

Merkle Patricia Trie (MPT for short) is the core ADS (Authenticated Data Structure) of Ethereum. Key data of Ethereum, such as World State, Account Data, Transactions, and Receipts, are all stored in MPT tries. MPT is a combination of Trie and Merkle Tree, embodying the advantages of both.

Although MPT is not difficult to understand, I find myself forgetting it after just one read. Therefore, I plan to write this article to describe MPT in my own words, to deepen my understanding and also to hopefully help other readers. I assume that readers are already familiar with the basic concepts of Ethereum, and have a good knowledge of data structures such as Trie and Merkle Tree. So, I will dive straight into the topic without spending time introducing these basic concepts first.

This article is mainly divided into three parts. In the first part, I will present a simplest implementation of Trie, and then discuss several optimizations, which are exactly what MPT does. In the second part, I will introduce how to persist Trie into KVStore while also merkleizing it, that is, how to obtain a Merkle Trie. In the third part, I will introduce some specific implementation details of MPT, including RLP Serialization and Compact Path Encoding.

Trie

Trie, also known as a Prefix Tree or Dictionary Tree, is an efficient data structure designed for fast retrieval of strings by utilizing their common prefixes to minimize unnecessary comparisons. Note that the term "string" here could refer to a Character string, a Bit string (e.g., TON's Dictionary), or a Byte string (e.g., Ethereum's MPT), etc. However, in this article, we assume that "string" refers to a byte string. Additionally, in this article, we will mainly use TypeScript to write pseudo-code or actual test code. For ease of description, in this article, we will represent byte strings in Hex format, such as 0x1234abcd. Below is the definition of our byte-string type:

type Bytes = string|null;

Simple Trie Map

Imagine that we have a Map (also known as Dictionary, Table, etc.) implemented with a 16-ary Trie, called TrieMap. It has a put(key, val) method that allows us to insert data. Let's write a piece of pseudo-code to construct a concrete Trie:

const trieMap = new TrieMap();
trieMap.put('0xabd147', '0x111111');
trieMap.put('0xabd148', '0x222222');
trieMap.put('0xace259', '0x333333');
trieMap.put('0xacf360', '0x444444');

I guess that you are not very good at imagining such a specific Trie structure in your mind, just like me, so I drew a picture to help us understand this tree. In computer science, we usually draw trees upside down, like in Figure 1-1:

Our TrieMap is very simple; all nodes are identical: they can store data and have references to up to 16 other nodes. If we need to implement this TrieMap, then we will need to use a type to represent the nodes, which we will call TrieNode. Below is the pseudo-code:

type Ref = TrieNode|null;
type RefArray = [
  Ref, Ref, Ref, Ref, Ref, Ref, Ref, Ref,
  Ref, Ref, Ref, Ref, Ref, Ref, Ref, Ref,
];

class TrieNode {
  data: Bytes;
  refs: RefArray;
}

Starting from the Root Node, we can follow a path to reach a Leaf Node. Therefore, sometimes we also refer to a Key as a Path, which in this context is a Nibble string. Clearly, our implementation is somewhat simplistic and not very efficient. Let's discuss two optimizations that can effectively reduce the number of Internal Nodes.

Optimization1: Leaf Node

Let's first look at the two keys 0xace259 and 0xacf360. After branching at e and f, both subtrees have no further branches. In cases like this, where a path from node N to leaf node L has no branches at all, we can compress this path. To adopt this optimization, we introduce a new node type: LeafNode. And rename the original TrieNode to BranchNode. Below is the updated pseudo-code:

type Ref = BranchNode|LeafNode|null;
type RefArray = [
  Ref, Ref, Ref, Ref, Ref, Ref, Ref, Ref,
  Ref, Ref, Ref, Ref, Ref, Ref, Ref, Ref,
];

class BranchNode { data: Bytes; refs: RefArray; }
class LeafNode   { data: Bytes; path: Bytes;    }

We assume that the code for TrieMap has been updated accordingly. With this optimization, we can compress the paths 0x259 and 0x360 from the previous example, which saves us four nodes, as shown in Figure 1-2:

Let's keep moving.

Optimization2: Extension Node

This time, let's look at the keys 0xabd147 and 0xabd148. After branching at b and c, the left subtree passes through 3 nodes without branching, until it reaches 7 and 8 where it branches again. In cases like this, if a path from node N to non-leaf node M has no branching at all, then we can compress this path. To adopt this optimization, we introduce another new node type: ExtensionNode (MPT call it like this). Below is the pseudo-code:

type Ref = BranchNode|ExtensionNode|LeafNode|null;
type RefArray = [
  Ref, Ref, Ref, Ref, Ref, Ref, Ref, Ref,
  Ref, Ref, Ref, Ref, Ref, Ref, Ref, Ref,
];

class BranchNode    { data: Bytes; refs: RefArray; }
class LeafNode      { data: Bytes; path: Bytes;    }
class ExtensionNode { path: Bytes; ref:  Ref;      }

We assume that the code for TrieMap has been updated accordingly. With this optimization, we can compress the path 0xd14 from the previous example, which saves us another two nodes, as shown in Figure 1-3:

Let's pause here and move on to the Merkle Trie.

Merkle Trie

In previous section, we introduced how to implement a simple TrieMap and provided two specific optimization to reduce internal nodes. In this section, we will follow the same steps to think about how to merkleize the previous TrieMap. We still assume that we have implemented this class, named MerkleTrie. We can use it to reconstruct the previous example trie, as shown in the pseudo-code below:

const trieMap = new MerkleTrie();
trieMap.put('0xabd147', '0x111111');
trieMap.put('0xabd148', '0x222222');
trieMap.put('0xace259', '0x333333');
trieMap.put('0xacf360', '0x444444');

Simple Merkle Trie

The TrieMap introduced earlier is a very conventional data structure, with the entire tree stored in memory. To merkleize it, we need to change the implementation approach: we will persist the entire tree into a DB, or more precisely, into a KVStore. Here we don't need to worry about the specific details of the KVStore; even TypeScript's built-in Map can meet our needs:

interface KVStore {
  put(key: Bytes, value: Bytes): void;
}

Because we are using a DB instead of memory to store the Trie, we need to serialize a Trie Node and then write it as a Value into the KVStore. Additionally, we obviously cannot use References (or Pointers) directly to refer to other nodes. To solve this problem, we first calculate the Hash of the serialized node (for example, using SHA-256), and then use it as a Key. Some readers may have already noticed that this way of referencing is called a Hash Pointer. Moreover, due to this change, we incidentally calculate the Merkle Tree of all nodes. That is to say, we have already merkleized it. The hash of the root node is the Merkle Root, which is also seen as a Commitment. For ease of understanding, I modified Figure 1-1 to mark the hash of each node, as shown in Figure 2-1:

Let's start implementing the MerkleTrie. However, before we do that, for ease of serialization and storage, we will represent TrieNode directly through an array, as shown below:

type Data = Bytes;
type Hash = Bytes;
type Ref = Hash|null;

type TrieNode = [
  Ref, Ref, Ref, Ref, Ref, Ref, Ref, Ref,
  Ref, Ref, Ref, Ref, Ref, Ref, Ref, Ref,
  Data,
];

Below is the pseudo-code for the MerkleTrie. Other implementation details are not important; the focus is on the insert() method. It inserts a TrieNode into the MerkleTrie and then returns the corresponding Hash:

class MerkleTrie {
  kvstore: KVStore;

  encode(node: TrieNode): Bytes {...}
  hash32(s: string): Hash {...}
  put(k: Bytes, v: Bytes): Hash {...}
  get(k: Bytes): Bytes|null {...}

  insert(node: TrieNode): Hash {
    const val = this.encode(node);
    const key = this.hash32(val);
    this.kvstore.put(key, val);
    return key;
  }
}

Since the MerkleTrie is persisted in the KVStore, it may not be as intuitive to visualize as a Tree. To aid readers' understanding, I have represented the MerkleTrie from our example in a table format, as shown in Figure 2-2:

A lot of spaces are wasted! Let's do the optimizations.

Optimization1: Leaf Node

Like TrieMap, MerkleTrie can also optimize a path without branching. We already know that this can be divided into two cases: the end of the path is a leaf node or a normal branch node. Let's look at the first case. For ease of understanding, I modified Figure 1-2 to mark the hash of each node, as shown in Figure 2-3:

To optimize the unbranched path ending with a leaf node, we introduce a new type LeafNode, and rename the old type TrieNode to BranchNode. The updated pseudo-code is as follows:

type Data = Bytes;
type Hash = Bytes;
type Path = Bytes;
type Ref = Hash|null;
type Node = BranchNode|LeafNode;

type BranchNode = [
  Ref, Ref, Ref, Ref, Ref, Ref, Ref, Ref,
  Ref, Ref, Ref, Ref, Ref, Ref, Ref, Ref,
  Data,
];

type LeafNode = [
  Path, Data,
];

To assist readers in understanding, I have also represented the optimized MerkleTrie in table form, as illustrated in Figure 2-4:

Let's keep going.

Optimization2: Extension Node

Now let's look at the second case: an unbranched internal path. Similarly, for ease of understanding, I modified Figure 1-3 to mark the hash of each node, as shown in Figure 2-5:

To optimize the unbranched path that does not end with a leaf node, we introduce a new type ExtensionNode, as shown in the following pseudo-code:

type Node = BranchNode|ExtensionNode|LeafNode;
type LeafNode = [ Path, Data ];
type ExtensionNode = [ Path, Ref ];

After adding this optimization, our MerkleTrie will occupy fewer key-value pairs, as shown in Figure 2-6:

Careful readers may have noticed that since Data, Path, and Ref are all byte strings, we cannot distinguish between leaf node and extension node based solely on the encoded data. To solve this problem, Ethereum adds different prefixes to paths of leaf nodes and extension nodes during encoding, which we will introduce in the next subsection.

MPT

Above, we have actually introduced the main concepts and implementation ideas of Ethereum MPT. In this section, we will observe the internal structure of MPT through real code to see some more details. Let's rewrite the previous example using @ethereumjs/mpt library. For ease of observation, we use an in-memory database to persist the merkle trie. Please see the test code below:

import { createMPT } from '@ethereumjs/mpt'
import { DB, MapDB, hexToBytes } from '@ethereumjs/util'

async function testMPT1() {
  let db: DB<string, string | Uint8Array> = new MapDB();
  let mpt = await createMPT({ db: db, useNodePruning: true });
  await mpt.put(hexToBytes("0xabd147"), hexToBytes("0x111111"));
  await mpt.put(hexToBytes("0xabd148"), hexToBytes("0x222222"));
  await mpt.put(hexToBytes("0xace259"), hexToBytes("0x333333"));
  await mpt.put(hexToBytes("0xacf360"), hexToBytes("0x444444"));
  console.log('root:', bytesToHex(mpt.root()));
  console.log('trie:', db);
}

If you execute the above test, it will print out:

root: 0x588ffb7619df7ef99d69646dd792897de83ddffc1c4b9fe0c11ea3b34229308a
trie: MapDB {
  _database: Map(4) {
    'aa6b8c0614b54719c60f20d320ed53e2656e5afd0166150375dbf158685cd156' => 'df821d14db80808080808080c52083111111c520832222228080808080808080',
    '2ba3745cfcb48259529544ef3681b0f1f2e3c8d6ea3aecaf6df5d9e7da93d416' => 'df8080808080808080808080808080c782325983333333c78233608344444480',
    '9981aeffcf4b1c7a7ef4b6c223bd731e859df33f771b39bef05023cd0b9bb688' => 'f8518080808080808080808080a0aa6b8c0614b54719c60f20d320ed53e2656e5afd0166150375dbf158685cd156a02ba3745cfcb48259529544ef3681b0f1f2e3c8d6ea3aecaf6df5d9e7da93d41680808080',
    '588ffb7619df7ef99d69646dd792897de83ddffc1c4b9fe0c11ea3b34229308a' => 'e21aa09981aeffcf4b1c7a7ef4b6c223bd731e859df33f771b39bef05023cd0b9bb688'
  }
}

There are all hexadecimal numbers; let's decode them.

RLP Serialization

As you can see, all keys are 32 bytes long, because MPT uses Keccak256 to calculate the key. In addition, MPT encodes Trie nodes using RLP format. RLP is a relatively simple serialization method, which will not be deeply introduced in this article. If you are not familiar with RLP, please refer to its document, this nice blog, or my article. We can use @ethereumjs/rlp library to decode the value, so let me rewrite the previous test as follows (just one line changed):

async function testMPT2() {
  let db: DB<string, string | Uint8Array> = new MapDB();
  let mpt = await createMPT({ db: db, useNodePruning: true });
  await mpt.put(hexToBytes("0xabd147"), hexToBytes("0x111111"));
  await mpt.put(hexToBytes("0xabd148"), hexToBytes("0x222222"));
  await mpt.put(hexToBytes("0xace259"), hexToBytes("0x333333"));
  await mpt.put(hexToBytes("0xacf360"), hexToBytes("0x444444"));
  console.log('root:', bytesToHex(mpt.root())); // changed line
  console.log('trie:', dbToStr(db));
}

The specific RLP decoding is handled in the dbToStr() function, and the complete code for this function will be provided at the end of the article. If you execute the above test, it will print out:

root: 0x588ffb7619df7ef99d69646dd792897de83ddffc1c4b9fe0c11ea3b34229308a
trie: 0xaa6b8c0614b54719c60f20d320ed53e2656e5afd0166150375dbf158685cd156 => [0x1d14, [0x, 0x, 0x, 0x, 0x, 0x, 0x, [0x20, 0x111111], [0x20, 0x222222], 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x]]
0x2ba3745cfcb48259529544ef3681b0f1f2e3c8d6ea3aecaf6df5d9e7da93d416 => [0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, [0x3259, 0x333333], [0x3360, 0x444444], 0x]
0x9981aeffcf4b1c7a7ef4b6c223bd731e859df33f771b39bef05023cd0b9bb688 => [0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0xaa6b8c0614b54719c60f20d320ed53e2656e5afd0166150375dbf158685cd156, 0x2ba3745cfcb48259529544ef3681b0f1f2e3c8d6ea3aecaf6df5d9e7da93d416, 0x, 0x, 0x, 0x]
0x588ffb7619df7ef99d69646dd792897de83ddffc1c4b9fe0c11ea3b34229308a => [0x1a, 0x9981aeffcf4b1c7a7ef4b6c223bd731e859df33f771b39bef05023cd0b9bb688]

For ease of understanding, I have drawn it as a table, as shown in Figure 3-1:

It looks a bit more understandable now. Let's continue digging it.

Compact Path Encoding

In order to fully understand the above table, we also need to understand the encoding of the path by MPT. Remember what was said earlier? To distinguish between a Leaf node and an Extension node, MPT will add different prefixes to the partial-path during encoding. This process is relatively simple and is called Compact Path Encoding. However, I will not introduce it in detail here; please refer to its documentation or this blog. I will directly explain the above table.

Let's first look at key h4, which is the root hash. After decoding its value, it is an array of length 2, so we know it could be either a Leaf or an Extension node. Since the path is 0x1a, we can tell it is an Extension node. The decoded path is 0xa, and the value is h3.

Now let's look at key h3. After decoding its value, it is an array of length 17, so it is a regular Branch node. It branches at b and c, with the corresponding hash pointers being h1 and h2 respectively.

Let's continue to look at key h2. Its value, upon decoding, is also a regular Branch node. However, interestingly, the positions at d and e do not contain hash pointers but instead directly house Leaf nodes ([0x3XXX, 0xYYYYYY]). This is another optimization of Ethereum MPT.

Finally, let's look at key h1. Its value, upon decoding, is an Extension node and the decoded partial path is 0xd14. However, similarly to h2, it does not directly place a hash pointer but instead houses a complete Branch node. This branch node then directly houses two Leaf nodes at positions 7 ([0x20, 0x222222]) and 8 ([0x20, 0x333333]).

It can be seen that MPT indeed works as we analyzed. Moreover, by directly storing some serialized nodes instead of their hash pointers, MPT further compresses the storage space.

Summary

In this article, I have introduced the basic design and some optimizations of Ethereum MPT (Merkle Patricia Trie). Thanks to the ingenious integration of Trie with Merkle Tree, MPT enables us to realize some very cool features. For example, when faced with two Tries, we can quickly determine whether they are identical by simply comparing their root hash values. Moreover, we inadvertently obtain a Versioned Database—each root hash value represents a specific version number. Additionally, we can prove whether a certain key-value pair exists in a particular version of the Trie, that is, provide existence or non-existence proofs. I will introduce these features in other articles.

Buy me a cup of coffee if this article has been helpful to you:

• EVM: 0x8f7BEE940b9F27E8d12F6a4046b9EC57c940c0FA

Appendix

Here is the complete code for the dbToStr() helper function:

import { RLP, NestedUint8Array } from '@ethereumjs/rlp';
import { DB, MapDB, bytesToHex, hexToBytes } from '@ethereumjs/util'

function dbToStr(db: DB<string, string | Uint8Array>) {
  let _map = (db as any)['_database'] as Map<string, string>;
  let str = '';
  _map.forEach((v, k) => {
    str += '0x' + k + ' => ' + decodeValAndToStr(v) + '\n';
  });
  return str.trim();
}

function decodeValAndToStr(v: string) {
  let decodedV = RLP.decode(hexToBytes('0x' + v)) as NestedUint8Array;
  return nu8aToStr(decodedV);
}

function nu8aToStr(a: NestedUint8Array) {
  let s = '[';
  for (let x of a) {
    if (s != '[') {
      s += ', ';
    }
    if (x instanceof Uint8Array) {
      s += bytesToHex(x);
    } else {
      s += nu8aToStr(x);
    }
  }
  s += ']';
  return s;
}