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?

up vote 56 down vote accepted

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

  • 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 Dec 15 '17 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... – atomh33ls Mar 12 at 12:56
  • What do the leaf node and extension nodes of the trie do? – jamarcus_13 Apr 6 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 May 26 at 22:17
  • @HelinWang No problem, I think this depends on the implementation so would be better posed as a new question... – atomh33ls May 26 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.

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/

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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