Ethereum under the hood: Part 4 (The Trie)
Tags: trie, ethereum, blockchain, cryptocurrency
Published: 2021-03-10 13:36:44

---
title: Ethereum under the hood: Part 4 (The Trie)
published: true
date: 2021-03-09 05:15:03 UTC
tags: trie,ethereum,blockchain,cryptocurrency
canonical_url: https://medium.com/coinmonks/ethereum-under-the-hood-part-4-the-trie-fc029e25ed04
---

 **Updates: Grammer fix**

This episode assumes that you have gone through [Part-1](https://medium.com/coinmonks/ethereum-under-the-hood-part-i-ver-0-1-4f2fb24b3d68), Part-2, [Part -3](https://medium.com/coinmonks/ethereum-under-the-hood-part-3-rlp-decoding-c0c07f5c0714)of this series, if you have not done so please do before you go through this article. The title of this episode is “The Trie” and not “Patricia Merkle Trie” (PMT). I feel it’s essential to understand about Tries first instead of jumping right into PMT. Let’s dive right in:

We are going to talk about:

1. Trie and its applications?
2. A more in-depth look into Trie’s
3. How Ethereum relates to Trie
4. A sample implementation
5. What next?

_Tip: I marked some words in_ **_bold_** _to emphasize important points or get your attention._

#### Trie and its application?:

We start with Tries; there are numerous articles on [Trie](https://medium.com/basecs/trying-to-understand-tries-3ec6bede0014), feel free to wiki it. Trie is a data structure which is meant for fast re **trie** val and hence the word “trie”. A real-life use case for using a trie data structure is the [**auto-complete**](https://www.youtube.com/watch?v=Wqzp0KC6DfE) or **auto correct** feature while having chat session, not exactly like the one below :-)

![](https://cdn-images-1.medium.com/max/320/1*MVnGfQxKDmaLkV1gLqrtYg.jpeg)<figcaption>Source:AutocorrectEpicFail.com</figcaption>

For the Auto-Fill or Auto-Correct, we need a quick lookup with multiple possibilities, storing and retrieving values for a given **Prefix** should be fast and this is why Trie is a useful data structure for these use cases.

#### A more in-depth look into Tries:

Have a look at the picture below which maps a given **set of characters** into a simplified Trie Data Structure for a given **set of words**.

![](https://cdn-images-1.medium.com/max/1024/1*FkU8dLdteF5B-8ijDdisrw.png)<figcaption>Basic Trie</figcaption>

In our simplified Trie, each one of those circles can be considered a **node with some properties.** In our simplified trie, there are three kinds of nodes 1)The **Root** node(green) 2) Character node (blue) 3)Nil node (orange). Now lets circle back and add some properties we are familiar with from the world of Ethereum.

All of the node types (blue, green, orange) may have value(s) for one of the three fundamental properties:

1. **_A Unique Id._**
2. **_Individual character and pointer[s] to children(s) and parent(s) node(s)._**
3. **_State id(s)._**

The first two properties are self-evident, but property #3: **_State Id_** is an exciting and essential property, think of this as a marker in time, or simply put an ordering system which maintains a global state id, for e:g: **State -> 0** is the initial state and the next **State -> 1**.

So let’s say the **first** word we want to add is **“abba”** and the **second** word we want to add is “abs” the data structure might look something like this:

{ word = “ **abba** ”, **state\_id = 1 ** }

{ word = “ **abs** ” , **state\_id = 2 ** }

_Who decides what goes_ **_first_** _and what goes_ **_next_** _is a story for another day_, we will come to that in later series, but hold on to that thought. With this in mind, we can have now had a simple data structure, something like the one below. For our simple trie. We are going to send three parameters to our simplified trie function.

Basic Trie

_note: If you want to know more about trie, check out this excellent_ [_article_](https://medium.com/basecs/trying-to-understand-tries-3ec6bede0014)_._

#### How does Ethereum relate to Trie? :

If you recall RLP from the last two [episodes](https://medium.com/coinmonks/ethereum-under-the-hood-part-ii-i-933411deebe1) Ethereum uses **RLP** to encode/decode values, e.g., a string _“dog”_ encoded as [**83** 64 6f 67] and **“dig”** will be encoded as [**83** 64 69 67]. This encoded value search needs to be accessed quickly.

_Note: “dog” converted to hex is 64 6f 67._

![](https://cdn-images-1.medium.com/max/1024/1*15187gUyVZJkfUQX1-f3wA.png)<figcaption>“dog” and “dig” depicted as our Simplified Trie</figcaption>

Looking at the above trie we can figure out about the data types, and we can determine the Data types, and how many of them are thereby looking at the left side of the trie, the number **“83”** represents data type **String** as specified by RLP encoding specification and there are  **two.**

There are three primary functions applied to our Simplified Trie: 1) Add 2) Delete 3) Search a node. Check out the skeleton code for the Trie:

**_Trie_ Add _function skeleton code:_**

```
_function_ **trie\_add** (trie, word, state_id){

//traverse through trie
     //add whatever character node not available in the trie
     //provide parent node id to child idto the new child node.
     //add 'nil' node if applicable and map it to state_id

return status;

}
```

**_Trie_ search _function skeleton code:_**

```
_function_ **trie\_search** (trie, word){

//Start from Root "/"
     //Retrieve all child nodes from "/"
     //verify if there is a match   
     //repeat until match completes

return status;

}
```

Coming back to Ethereum, If you recall we talked about Ethereum World State, it is essentially hash of a key-value pair. Something like what you see below:

![](https://cdn-images-1.medium.com/max/952/1*cALs6LQJ86o9GVR5Ao3CDg.png)<figcaption>Source: <a href="https://ethereum.stackexchange.com/questions/39915/ethereum-merkle-patricia-trie-extension-node">Stack exchange</a></figcaption>

Imagine those **_nil_** nodes which acts as a terminator has a number like **“45”** , I am oversimplifying here, but you get the picture and when a lookup on the Ethereum Global State [**_σ_**](https://ethereum.github.io/yellowpaper/paper.pdf) for key prefix: **“a77d”** , we get the values: **_{1.00 ETH, 0.12 ETH}_**. We can express this as follows:

**_[{ “a77d337”: “1.00 WEI” }, {“a77d397”: “0.12 ETH”} ]_**

The [yellow paper](https://ethereum.github.io/yellowpaper/paper.pdf) defines this access as:

![](https://cdn-images-1.medium.com/max/526/1*Tiro4hq931RuotiMTRnTuw.png)<figcaption>Section 4.1 From the yellow Paper, where <strong>a</strong> is the address, <strong>b</strong> is the balance</figcaption>

#### A sample implementation:

Below is a code snippet of Trie in Python (Thanks to [Vijay](https://medium.com/u/bfc1fe602830)), I would encourage you to make a simple application on your own.

![](https://cdn-images-1.medium.com/max/1024/1*U5-ShxFx6pB_qRHBdvs0dg.png)<figcaption><strong>Source: GitHub: @coolcalbeans</strong></figcaption>

**Output, Github: @coolcalbeans**

Let’s stop here and take a breather.

#### What’s Next? :

I would recommend you to go through the references and get a sense of how Tries. In the next section, we will be talking about an upgraded version of the Trie called the **Patrica Merkle Trie** and its how it relates to Ethereum, till then keep on learning.

### References:

- [Trying to Understand Tries](https://medium.com/basecs/trying-to-understand-tries-3ec6bede0014)
- [What is the difference between trie and radix trie data structures?](https://stackoverflow.com/questions/14708134/what-is-the-difference-between-trie-and-radix-trie-data-structures#14708989)
- [ethereum/wiki](https://github.com/ethereum/wiki/wiki/Patricia-Tree#preamble-basic-radix-tries)

Source: [https://www.youtube.com/watch?v=sAErv97lfIM&t=276s](https://www.youtube.com/watch?v=sAErv97lfIM&t=276s)

* * *