86

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?

Improve this question
1

2 Answers 2

Reset to default
89

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

enter image description here

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.

enter image description here Source: https://en.wikipedia.org/wiki/File:An_example_of_how_to_find_a_string_in_a_Patricia_trie.png

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:

enter image description here

Improve this answer
6
  • 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
    – alper
    Commented 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...
    – Lee
    Commented Mar 12, 2018 at 12:56
  • 1
    What do the leaf node and extension nodes of the trie do?
    – jamarcus_13
    Commented 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?
    – Helin Wang
    Commented 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...
    – Lee
    Commented May 26, 2018 at 22:24
11

'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.

Diagram from wikipedia

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

https://stackoverflow.com/questions/14708134/what-is-the-difference-between-trie-and-radix-trie-data-structures

More specifications of the Merkle Patricia tree that Ethereum uses can be found on the ethereum blog

https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.