Ethereum Patricia trie - Merkle tree, Radix tree, and trie node

Trie is a method to handle and manage data structure, or on the other way, a basic understanding that is the digital tree. It likes another kind of tree that we learned from somewhere.

The type of trie I want to introduce that is mainly “Patricia tree”, a combination of Merkle tree and radix tree.

MERKLE TREE

With Merkle tree, you have to load all of the data into RAM to work with it. Finally, this process’s result is an “authenticated data”- “hash”. “Normal data” will be saved in leaf node and value of parent node will be equal to Hash (child node 1, child node 2, child node 3, …). So, from the bottom to the top of the Merkle tree, you have to calculate the root node, hash of the whole trie, that can be used to match with a hash of another set of data.

Merkle tree

In the Merkle tree, almost of nodes is hashed nodes, and you need to reload all of the data whenever accessing to a value or re-hashing or re-processing if some node is modified. This annoying will be taken a lot of time, CPU, ram and other resources. “Time is precious”

Problem 1 will be solved, the Merkle tree will cover all of the cases that data is modified, just a ‘lil’ bit of change.

Root hash will be changed when some data is modified

RADIX TREE

To make searching faster, you need to know the definition of the Radix tree- a tree that is constructed from many sets of <value-key, value> data. Radix tree has lots of nodes, each node has properties as “path”, “value” or “node-children”.

In Ethereum trie structure

• Some kind of node: short node, full node, value node.
• Node has constructor ( path and node ), so it is called “short node”
• Node has constructor only ( array of node children ), so it is called “full node”
• Node has constructor only ( value ), so it is called “value node”
• If ending path of an short node is a defined terminator [k], that node will contains (path and value node) instead of ( path and node ). (k is maximum children number of full node)
• If path of an short node end without defined terminator [k], that node will contains (path and some kind of node except value node) , so it is called “extension node”

EXAMPLE

An example of datasets — lots of (path-value):

abcf546 : “cauvang”,

abcf : “dareka”,

abcf54 : “cauvang2”,

abcf5 : “cauvang3”,

Terminator: [8] for example,

After handle all of the paths of that datasets, you will get handled datasets — lots of ( handled path-value):

abcf546 [8] : “cauvang”,

abcf [8] : “dareka”,

abcf54 [8] : “cauvang2”,

abcf5 [8] : “cauvang3”,

Create into theRadix tree

With list type of node {

1. fullNode {children [8]node}
2. shortNode {Key string, Value node}
4. valueNode string

You can construct this into this trie with nodes:

• fullNode: { children (2): valueNode( “dareka” ) ( at index [8] ), shortNode( at index “5”) } with path abcf
• shortNode( at index 5): {key: “abcf”, value: fullNode_ } with path abcf5
• fullNode_: { children(2): valueNode(“cauvang3”) ( at index [8] ), shortNode( at index 4) } with path abcf54
• shortNode( at index 4): {key: “abcf5”, value: fullNode__} with path abcf54
• fullNode__: { children(2): valueNode(“cauvang2”) ( at index [8] ), shortNode( at index 6) } with path abcf54
• shortNode( at index 6): {key: “abcf54”, value: valueNode(“cauvang”)}

MISC.

Base on traveling nodes on the Radix tree, you can make searching a key (an address as a key for example) faster and easier than other normal data structure.

Go Ethereum defined some type of nodes

type node interface{}
1. fullNode { Children [17]node , flags}
2. shortNode {Key []byte, Value node}
3. hashNode []byte
4. valueNode []byte

An full node can reach to 17 child nodes, node with index 16 can be equal to value node or null.

Hash node will be generated when Ethereum hashes or commit a node or whole trie. It is the result of hashing full node or short node or value node, and it mainly results of combination with the Merkle tree.

That is it, all of my explaining about the Merkle tree and Radix tree, the basic things to create the next level — Ethereum Patricia trie, that you can read at chapter 2 — more deeper things in Ethereum!