Modifying the Merkle Patricia Trie

My focus the last couple of months has been entirely on the migration of the Hycon codebase to rust, which has led to a deep dive into various aspects of the system that I have not necessarily had much input to. My current area of work is the world state. A previous post mentioned a new, high performance, state trie that we hope to use, however backwards compatibility has forced me to also implement our current state tree to allow for that transition to be handled correctly.

What is a Merkle Patricia Trie?

This structure will be familiar to anyone who has worked with Ethereum, and in essence it is a hashed radix tree. The simplest way to explain it is visually, using words as our keys. Let’s say we limit our words to lower-case English characters. This gives each node in the tree a divergence factor of 26, or in plainer terms, there are 26 possible options for the next letter in a word. Lets start by building a simple tree with 4 words in it. The words we will use are ant, apple, cat, and dog, with data 1,2,3 and 4.

Naive Tree with 4 Keys

In order to extract the relevant data from this tree, it is necessary to read each letter in the key word and travel down the corresponding path. This layout actually represents the worst possible case for this structure, where every layer is saturated and it is necessary to read the entire key to extract the data. Fortunately there are some optimisations we can make for a more sparse problem space.

Optimising The Tree

The primary optimisation that can be made in this case is branch compression. In the case above it is clear that there is only one data point at the end of certain branches, specifically AN-, AP-, C-, and D-. We can compress these branches so that only one database lookup us required to reach the data after the unique branching point. The resulting tree looks a little bit like this.

Compressed Tree

As can be seen from the above, in order to retrieve the data stored at the address “APPLE”, only 3 database lookups are required (ROOT, A, PPLE), instead of 6.

Insertion

In order to insert into the tree, we need to traverse until we reach an empty node along the keys path, and then insert a new node representing the remainder of that key and its data at that location. Let’s say we are inserting a node with key CAR and value 5. From the root node we will travel down the “C” branch, which currently only contains “CAT”. After comparing the keys, we can see that two new nodes will be required, one representing the traversal to the location CA and another representing the “R” branch from car. We have to split the CAT node into a new CA node and the move the data from the CAT node into the “T” location of the new CA node. We then add a new node containing the value 5 at location “R” in the CA node. The root node then has three children — A,CA, and DOG.

Updated Tree with CAR

Reading From a Tree

In order to read from a tree we need two pieces of information — our current location, and the database location of the next node we would like to traverse to. Supposing we want to get the data for “APPLE”, we first need to read the root node from out database to give us our starting point. We then slice off the first character and check the root node at the “A” location. This will give us a DB reference for the next node, allowing us to move down the tree. We keep traversing in this manner until we reach the end of our key. In the case of compressed branches, we can step along the key while the key matches the branch address. Upon reading the “A” node, the remainder of our key is “PPLE”, so we look for the “P” node. The “P” node is a compressed node containing “PPLE”, which means that our operation is finished and the data contained in the “P” node is the data we are attempting to retrieve. In the case of multiple reads it doesn’t make sense to keep traversing the tree from the root, so we can cache the paths we have already taken and start from the point where our current key splits from the path we have already taken.

To extend the example above, let’s say we want to retrieve the data for ANT and APPLE. For ANT we retrieve the root node, the “A” node, and the “NT” node. To retrieve APPLE, we can start our traversal from the “A” node, which we have already visited and so now retrieving APPLE requires a single extra DB lookup in this case.

Updating an Entry

In this case, the APPLE address is being updated to have a value of 6. First we would need to retrieve APPLE from the tree. As part of this process we will retrieve the nodes root, A, and PPLE. The physical location in the tree for these nodes will not change, however due to us updating the information, the DB entries will be different. PPLE will now contain a value of 6. A will now contain the existing data for NT, and also the new PPLE node. The root node will contain the updated A node, the CA node and the DOG node.

Deleting A Root — Reference Counting

The mechanism that allows for safe deletion and maintenance of our DB is called reference counting. As part of any of our operations, we can keep track of nodes which are not changed as part of the operation. Let’s step through this operation referring to the examples above.

Our initial state contains 6 nodes: the root node, A, NT, PPLE, CAT, and DOG. Each of these nodes are initialised with a reference count of 1 as well as the data entries for 1–4. When we mutate our tree by inserting “CAR”, our references are adjusted as follows.

Updated Reference Count after CAR Insertion

Now we can look at what happens when we perform our update operation on APPLE.

Reference Count After Update to APPLE

As can be seen above, we have added some new nodes (Updated Root, New A, New PPLE, and 6) and we have updated the reference count for the unchanged nodes.

In order to keep our DB size smaller we have decided that we will delete older roots. In order to do this safely we can check the references of the nodes referenced by that root and decide whether we can delete those entries from our DB. To refresh our memory let’s look back at our original tree, this time with references annotated.

Reference Counts for Original Root

When we delete a root, we have to traverse the tree and decrement the reference count for the sub trees. If the ref count for any node goes to zero, we traverse to its sub-nodes and decrement the ref count.

Updated Ref Counts for Delete Operation

Looking at the table above we can see that after this operation it is safe to delete the DB entries for Root and CAT, as they are no longer referenced anywhere.

HYCON Merkle Patricia Trie

The examples above use letters as branching metrics, the HYCON tree branches at the byte level — meaning that each node has a possible 256 branches. In practice this means that we have a short fat tree, a Merkle Patricia Bush as it were. With approximately 11000 accounts in the Hycon tree it turns out that only a maximum of 3–4 database lookups are required per account to retrieve a balance.

In Summary

The point of this post was actually to delve into the implementation specific details of the HYCON tree in rust, however it got a little bit wordy so I’ll save that for my next post and keep this one as a Merkle Patricia Tree primer.


Modifying the Merkle Patricia Trie was originally published in Data Driven Investor on Medium, where people are continuing the conversation by highlighting and responding to this story.