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?
medium.com/@chiqing/merkle-patricia-trie-explained-ae3ac6a7e123– LeeAug 17, 2020 at 15:07
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-statecontain 8 nibble (32 bytes)? In your example(latest image) it contains 7 nibbles, which is 28 bytes. @atomh33ls– alperDec 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...– LeeMar 12, 2018 at 12:56
1What 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...– LeeMay 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.
More specifications of the Merkle Patricia tree that Ethereum uses can be found on the ethereum blog