# ELI5 How does a Merkle-Patricia-trie tree work?

I understand that Merkle tree are Hashes of Hashes, they have the advantage that you can verify only a subtree. But what about Patricia? What does a trie mean? And how is it used in Ethereum?

Trie (also called digital tree, prefix trie or radix trie)

An ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. A node's position in the tree defines the key with which it is associated. https://en.wikipedia.org/wiki/Trie

A trie for keys "A","to", "tea", "ted", "ten", "i", "in", and "inn".

Patricia - Practical Algorithm To Retrieve Information Coded In Alphanumeric (source)(orginial paper by Donald R. Morrison). A Patricia trie is a binary radix trie - binary choice at each node when traversing the trie; this is modified in Ethereum.

In ethereum, hexadecimal is used - X characters from an 16 character "alphabet". Hence nodes in the trie have 16 child nodes (the 16 character hex "alphabet") and a maximum depth of X. Note a hex character is referred to as a "nibble".

Merkle Patricia Trie

As described here, the term Merkle implies that

the root node becomes a cryptographic fingerprint of the entire data structure

Ethereum Modified Merkle Patricia Trie

The yellow paper describes a modified merkle patricia trie. This defines three different node types; extension, branch and leaf. These are descibed, using a simplified world state, in the diagram below:

• Shouldn't a key under `world-state` contain 8 nibble (32 bytes)? In your example(latest image) it contains 7 nibbles, which is 28 bytes. @atomh33ls Dec 15, 2017 at 6:57
• @Alper thanks... I shortened it to make it more concise. I think 8 nibbles is just 4 bytes... and 7 is 3.5 bytes. I'd need 64 hex chars for 32 bytes... Mar 12, 2018 at 12:56
• What do the leaf node and extension nodes of the trie do? Apr 6, 2018 at 16:46
• Thanks! How does a stale tree synchronize to an up-to-date tree? (e.g., when a client gets online after one day). Does it just download the entire up-to-date tree, or some kind of "diff" is received for the synchronization? May 26, 2018 at 22:17
• @HelinWang No problem, I think this depends on the implementation so would be better posed as a new question... May 26, 2018 at 22:24

'Trie' comes from the word retrieval, since it only uses the prefix of a word to find it in a dictionary. It is an ordered tree where the keys are usually strings ending with a terminal symbol, and each vertex represents a prefix. The root of a trie is usually an empty string, as we can see in the diagram taken from wikipedia.

For more information about the difference between a trie and a radix (Patricia) tree.