State Trie

Merkle-Patricia Trie

Merkle-Patricia trie is combination of two tree data structures:

• Merkle tree – tree that uses child hash instead pointer
• Patricia trie – optimized dictionary tree

Patricia trie

Main difference between Patricia trie and regular dictionary tree is algorithm to compress long one-child branches into single node.

Different implementations contain between 2 and 3 types of different nodes, but there are 2 important types:

• Branch node – has more that 1 child – contains Children[ALPHABEIT_SIZE] list of children pointers.
• Extension node – non leaf node represent sequence of nodes that has only one child, contains Key that represents all these nodes as one.
• Optional third type is Value node - leaf node, similar to Extension node, but instead pointer to next node, it contains value.
  • Some implementations combine Extension and Value nodes into one node type.

Trie example

Following figure shows most possible of inter-trie connections, and it contains following data:

• 5 -> A
• A123 -> B
• FAB23 -> C
• DA1F -> D
• DA1F4 -> E
• DA1F111 -> F
• 50FF1 -> G
• 50FFC561 -> H
• DA1F48A -> I

Trie update algorithm

• If node with updated key exist, just update Value and all Hash pointers up to root.
• If such a node doesn't exist, traverse trie for all key matching nodes.
  • If last matching node is Value node:
    • Convert it to an ExtensionNode followed by BranchNode and add new ValueNode with the remaining path without first character
  • If last matching node is Branch node, find next node - pointed by node.Children[nibble]:
    • When next node is an NIL, replace it with a new ValueNode with the remaining path.
    • When next node is a ValueNode, add ExtensionNode with matching path, followed by BranchNode, and make new BranchNode point to original ValueNode with rest of its path and new ValueNode.
    • When next node is an ExtensionNode, add another ExtensionNode with common path and create a new BranchNode points to the original ExtensionNode and new ValueNode.
  • Update all Hashes up to root

Trie update example

THis example illustrates how one update can affect multiple nodes in trie, not mention hashes in whole branch

We start from trie that contains only 3 Value nodes, with three values

• A123 -> B
• DA1F -> D
• 50FF1A -> G

After the insert of (DA1FE111 -> F) we see 3 new nodes - one Extension node, one Branch node that replaced Value node holding value (D), and one Value node that holds new value (F)