84

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?

Community
  • 1
Roland Kofler
  • 11,638
  • 3
  • 44
  • 83

2 Answers2

88

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

Community
  • 1
Lee
  • 8,548
  • 6
  • 46
  • 80
  • 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 06: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 Mar 12 '18 at 12:56
  • 1
    What do the leaf node and extension nodes of the trie do? – jamarcus_13 Apr 06 '18 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 '18 at 22:17
  • @HelinWang No problem, I think this depends on the implementation so would be better posed as a new question... – Lee May 26 '18 at 22:24
  • Thank you @atomh33ls ! I just skimmed through the go eth trie source code, it seems there is another kind of node: hashNode, if my understanding is correct, it's a reference to any kind of node illustrated your graph in the database. Maybe your graph could be improved by pointing that out. – Helin Wang May 28 '18 at 19:11
10

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

Community
  • 1
rupshabagchi
  • 489
  • 2
  • 9