Ethereum Primitives #1.2

merkle-patricia-trie.ipynb

{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python_defaultSpec_1598436785924",
   "display_name": "Python 3.8.3 64-bit ('3.8.3': pyenv)"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TRIE | PREFIX TRIE | DIGITAL TRIE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Trie](https://gateway.pinata.cloud/ipfs/QmYVZTtKZGkmmttGJpUs6UB8K5kyT2GdkXocksLri5Z4Cg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "^example of what a **TRIE** may look like\n",
    "\n",
    "- notice how root is empty\n",
    "- all descendants of a node have a common prefix\n",
    "- widely used in autocomplete, spell checkers\n",
    "- can represent a trie with an array or a hashmap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is how you insert into trie. O(N) time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "![insert](https://gateway.pinata.cloud/ipfs/Qmdx5vPgxh2WgzbYGX76EdSC8z5HaJ9UF64NKdbPtJDJQY)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and how you search in a Trie. O(N) time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![search](https://gateway.pinata.cloud/ipfs/QmfJuAncaZVBeGXXeB6afkqykRB9aQC3Sy99QcNr7fTHCU)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Trie** is also sometimes called **prefix tree**, it is a special form **N-ary tree** (meaning each node can have no more than **N** children)\n",
    "\n",
    "Origin of word **trie** is from re**trie**ve"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You use an array or a hashmap to implement a **Trie**. For example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Tuple\n",
    "import json\n",
    "\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self, char: str):\n",
    "        self.char = char\n",
    "        self.children = []          # using an array to store children\n",
    "        self.word_finished = False  # Is it the last character of the word ?\n",
    "        self.counter = 1            # How many times this character appeared in the addition process\n",
    "\n",
    "    # could have used __str__ as well. __repr__ conventional use is to reconstruct\n",
    "    # the instance of a class given a string. For example, if class Foo has a single\n",
    "    # attribute bar, and its value is 'bar', then __repr__ would return\n",
    "    # Foo(bar='bar'). Here we use __repr__ to help us visualize the Trie\n",
    "    def __repr__(self):\n",
    "        return json.dumps(self._json(), indent=4)\n",
    "\n",
    "    def _json(self):\n",
    "        return {\n",
    "            \"char\": self.char,\n",
    "            \"children\": [child._json() for child in self.children],\n",
    "            \"word_finished\": self.word_finished,\n",
    "            \"counter\": self.counter,\n",
    "        }\n",
    "\n",
    "\n",
    "# Adds a word to a TrieNode\n",
    "# 1. current node is root at start\n",
    "# 2. for each character in the word\n",
    "#    - look for the TrieNode whose value (self.char) == this character\n",
    "#    - if can't find, create a TrieNode; else traverse down the found TrieNode\n",
    "#\n",
    "# Time Complexity of this is O(N * M). Meaning very inefficient\n",
    "# N - length of word\n",
    "# M - maximum number of children a TrieNode can have (a Trie is a special form N-ary Trie)\n",
    "#\n",
    "# How could we improve the time complexity of this algo?\n",
    "# We could store pointers to the locations of the nodes separately. For example, given the root (its\n",
    "# hash, or some sort of key), we can look up the pointer to it in a database that would hold this info\n",
    "# for us. We can now get the instance of the root TrieNode, what next? We can now use the first character\n",
    "# of the word as an index, to go to the db to get the pointer to the next TrieNode, and so on.\n",
    "# You will agree that this is much more efficient. We have paid the price of extra storage in return for\n",
    "# the greater performance (time complexity)\n",
    "# Our TrieNode now, would at most take\n",
    "# Time Complexity O(N)\n",
    "# with Space Complexity O(L), where L is the total number of TrieNodes (many of TrieNode)\n",
    "# If you look here: https://eth.wiki/en/fundamentals/patricia-tree\n",
    "# then that is exactly how it is done in Ethereum. The only caveat, Ethereum doesn't use Tries, at least,\n",
    "# not the basic prefix tries. Let's continue exploring to understand why\n",
    "def add(root, word: str):\n",
    "    node = root\n",
    "    for char in word:\n",
    "        found_in_child = False\n",
    "        for child in node.children:\n",
    "            if child.char == char:\n",
    "                child.counter += 1\n",
    "                node = child\n",
    "                found_in_child = True\n",
    "                break\n",
    "\n",
    "        if not found_in_child:\n",
    "            new_node = TrieNode(char)\n",
    "            node.children.append(new_node)\n",
    "            node = new_node\n",
    "\n",
    "    node.word_finished = True\n",
    "\n",
    "\n",
    "# def find_prefix(root, prefix: str) -> Tuple[bool, int]:\n",
    "#     node = root\n",
    "#     if not root.children:\n",
    "#         return False, 0\n",
    "#     for char in prefix:\n",
    "#         char_not_found = True\n",
    "#         for child in node.children:\n",
    "#             if child.char == char:\n",
    "#                 char_not_found = False\n",
    "#                 node = child\n",
    "#                 break\n",
    "#         if char_not_found:\n",
    "#             return False, 0\n",
    "#     return True, node.counter\n",
    "\n",
    "\n",
    "# print(find_prefix(root, 'hac'))\n",
    "# print(find_prefix(root, 'hack'))\n",
    "# print(find_prefix(root, 'hackathon'))\n",
    "# print(find_prefix(root, 'ha'))\n",
    "# print(find_prefix(root, 'hammer'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "root = TrieNode('*')\n",
    "add(root, \"dog\")\n",
    "add(root, \"done\")\n",
    "add(root, \"dope\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "{\n    \"char\": \"*\",\n    \"children\": [\n        {\n            \"char\": \"d\",\n            \"children\": [\n                {\n                    \"char\": \"o\",\n                    \"children\": [\n                        {\n                            \"char\": \"g\",\n                            \"children\": [],\n                            \"word_finished\": true,\n                            \"counter\": 1\n                        },\n                        {\n                            \"char\": \"n\",\n                            \"children\": [\n                                {\n                                    \"char\": \"e\",\n                                    \"children\": [],\n                                    \"word_finished\": true,\n                                    \"counter\": 1\n                                }\n                            ],\n                            \"word_finished\": false,\n                            \"counter\": 1\n                        },\n                        {\n                            \"char\": \"p\",\n                            \"children\": [\n                                {\n                                    \"char\": \"e\",\n                                    \"children\": [],\n                                    \"word_finished\": true,\n                                    \"counter\": 1\n                                }\n                            ],\n                            \"word_finished\": false,\n                            \"counter\": 1\n                        }\n                    ],\n                    \"word_finished\": false,\n                    \"counter\": 3\n                }\n            ],\n            \"word_finished\": false,\n            \"counter\": 3\n        }\n    ],\n    \"word_finished\": false,\n    \"counter\": 1\n}"
     },
     "metadata": {},
     "execution_count": 6
    }
   ],
   "source": [
    "root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## WHY DON'T WE USE TRIE IN ETHEREUM?\n",
    "\n",
    "- awful time complexity\n",
    "- even if improved (like above), wastes space (see radix trie below for comparison)\n",
    "- not useful, because we can't verify the integrity and validity of the data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# RADIX TRIE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![trie-vs-radix](https://gateway.pinata.cloud/ipfs/QmSj8GJDgzd5ddtHXmQpdUQvMQBLU8giedR67gas5ivcKR)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![trie-vs-radix-2](https://gateway.pinata.cloud/ipfs/QmRmwK37mUYCDQngfQVHKyzUvBN19QdfLFw5rrg43yfm15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "i.e. the RADIX TRIE uses the space better. So RADIX TRIE is just like TRIE, but with better space"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Merkle Trie | Patricia Trie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Just like Radix trie, with an addition of being cryptographically verifiable**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "----------------------------------------------------\n",
    "INCOSISTENCY in eth.wiki (I think):\n",
    "\n",
    "From: https://eth.wiki/en/fundamentals/patricia-tree\n",
    "\n",
    "\"\"\"\n",
    "radix tries have one major limitation: they are inefficient. If you want to store just one (path,value) binding where the path is (in the case of the ethereum state trie), 64 characters long (number of nibbles in bytes32), you will need over a kilobyte of extra space to store one level per character, and each lookup or delete will take the full 64 steps\n",
    "\"\"\"\n",
    "\n",
    "^ I believe this explanation is incorrect. It is not radix tries that have this issue, but tries.\n",
    "Radix tries fix this problem, as we have seen from the screenshots above. We do not need to create a 17 item array for each nibble. If we have a single (path, value) binding, then we can just store path and the value in the very first node after root\n",
    "\n",
    "----------------------------------------------------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**LEAF NODE** - a node that doesn't have children\n",
    "\n",
    "\n",
    "---\n",
    "Merkle Trie labels:\n",
    "\n",
    "(i)  leaf nodes  - hash of their data\n",
    "\n",
    "(ii) other nodes - hashed children hashes\n",
    "\n",
    "---\n",
    "\n",
    "Merkle Tries are usually implemented as binary tries\n",
    "\n",
    "Merkle Tries are most useful in:\n",
    "\n",
    "(i) distributed systems, for efficient data verification\n",
    "\n",
    "e.g. in Git, Tor, Bitcoin ANNNND in Ethereum\n",
    "\n",
    "---\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "![merkle trie](https://gateway.pinata.cloud/ipfs/QmPLTiyevouVryjR7EPn5iBdxWL68TRjZrUbYAwBxwxUyn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Modified Merkle Trie is Ethereum's optimized Merkle Trie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Modified Merkle Patricia Trie | Merkle Patricia Trie | Modified Merkle Trie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ethereum's data structure is often called Merkle Patricia Trie, without the Modified prefix\n",
    "\n",
    "It is \"Modified\" because it has been optimised for Ethereum's needs\n",
    "\n",
    "For example, in Modified Merkle Patricia Trie, there are three types of nodes:\n",
    "\n",
    "(i) **branch node**\n",
    "\n",
    "(ii) **extension node**\n",
    "\n",
    "(iii) **leaf node**\n",
    "\n",
    "We need these, to primarily make better use of space\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**MPT** is\n",
    "\n",
    "- CRYPTOGRAPHICALLY AUTHENTICATED\n",
    "\n",
    "- can store all (key, value) bindings (we RLP encode the key)\n",
    "\n",
    "- O(log N) INSERT, LOOKUP, DELETE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note**\n",
    "\n",
    "Due to the introduction of extension and leaf nodes, we may end up having to traverse an odd-length remaining path. This introduces a challenge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All paths are stored as `bytes` type, and a single byte is 2 nibbles (2 hex chars). In this setting, how do you distinguish nibble '1' from a nibble '01'? You can't. Both are represented as `<01>` `bytes` (you cannot create a byte from odd-length nibbles)\n",
    "\n",
    "1 byte = 2 hex\n",
    "\n",
    "So we must do something about this. We can trivially solve this issue with flags. We can prefix all the 2-item nodes (leaf and extension) with the following"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![prefix-flags](https://gateway.pinata.cloud/ipfs/QmcftEUMB4sKUBcz4EuoTD4WKtQLrGiVtM4PLzqauLWQ4E)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "we do not care about the branch node because it does not contain the nibble path, and so does not suffer from this problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I find it very difficult to understand the Merkle Patricia Trie on eth.wiki, their `compact_encode` function is a bit strange too. So we will be implementing our own hex prefix algorithm from the yellow paper. Here is what it should do"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![hex-prefix](https://gateway.pinata.cloud/ipfs/QmdpDtZmsLi1ZnmxcQjXpi2FmfEpkoYh1qKCC9KTfE6CRU)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To be honest with you, even this is a bit confusing. First of all, there is no definition of what $t$ is, except for the fact that it is boolean. We can probably, assume, that $t$ is the node type (extension or leaf). Though, it remains to be determined whether extension === True or leaf === True\n",
    "\n",
    "Then, $||x||$ is the notation that is generally used to denote an $L_2$ norm (i.e. the length of the line /vector in Euclidean space), although, in this particular case, it appears that it is used as the cardinality of the set, where each x[i] is the hex character. It is not clear why we need to do those mathematical operations in any case"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given the above, let's just look at the most popular client out there: geth. And see how they do it"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### the comment section before the hexToCompact implementation:\n",
    "\n",
    "Trie keys are dealt with in three distinct encodings:\n",
    "\n",
    "KEYBYTES encoding contains the actual key and nothing else. This encoding is the\n",
    "input to most API functions.\n",
    "\n",
    "HEX encoding contains one byte for each nibble of the key and an optional trailing\n",
    "'terminator' byte of value 0x10 which indicates whether or not the node at the key\n",
    "contains a value. Hex key encoding is used for nodes loaded in memory because it's\n",
    "convenient to access.\n",
    "\n",
    "COMPACT encoding is defined by the Ethereum Yellow Paper (it's called \"hex prefix\n",
    "encoding\" there) and contains the bytes of the key and a flag. The high nibble of the\n",
    "first byte contains the flag; the lowest bit encoding the oddness of the length and\n",
    "the second-lowest encoding whether the node at the key is a value node. The low nibble\n",
    "of the first byte is zero in the case of an even number of nibbles and the first nibble\n",
    "in the case of an odd number. All remaining nibbles (now an even number) fit properly\n",
    "into the remaining bytes. Compact encoding is used for nodes stored on disk."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "![hexToCompace](https://gateway.pinata.cloud/ipfs/Qmas7HKofdGLVK7mEHYNK1xZ2u3ikjJa2jfLPRaoysRuUX)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and here is the test for the above function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![test-hex-to-compact](https://gateway.pinata.cloud/ipfs/QmUZjgidZzuMDb3eUEPn7mbTti9Tpe13BQN65HjD9Ltf3G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "so, as you can see the distinction between the leaf and extension node is made via an optional terminator flag that is placed at the end of the bytearray. From now on, we shall use geth as our source of truth. It appears to me, that the reason for popularity of geth is perhaps, partly due to the clarity of the code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's conclude on this note. Perhaps we will dive deeper in the near future. For now, this knowledge will suffice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you are interested, there is a nice utility in ethereum/hexbytes repo on GitHub. It will nicely format the Python's ugly bytes to hexadecimal for you, here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "HexBytes('0x03087766bf68e78671d1ea436ae087da74a12761dac0011a9eddc4900bf1')"
     },
     "metadata": {},
     "execution_count": 87
    }
   ],
   "source": [
    "HexBytes(\"\\x03\\x08wf\\xbfh\\xe7\\x86q\\xd1\\xeaCj\\xe0\\x87\\xdat\\xa1'a\\xda\\xc0\\x01\\x1a\\x9e\\xdd\\xc4\\x90\\x0b\\xf1\".encode(\"iso-8859-1\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "# To sum up\n",
    "\n",
    "**Trie** - not very efficient in terms of space and time complexity. Mostly used in spell checkers and auto-complete\n",
    "\n",
    "\n",
    "**Radix Trie** - mostly used in IP routing and associative arrays implementations\n",
    "\n",
    "\n",
    "**Merkle Trie** - cryptographically authenticated data structure, lets you easily and efficiently check if portions or all of the data has been tampered with\n",
    "\n",
    "\n",
    "**Modified Merkle Trie** - a Merkle Trie modification that is optimised for Ethereum. Main difference is in the introduction of three new types of nodes: extension, branch and leaf\n",
    "\n",
    "---\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Correct synnonyms\n",
    "\n",
    "**Trie**, prefix trie, digital trie\n",
    "\n",
    "**Radix Trie** (sometimes branching factor is specified, for example Radix 2 Trie. Meaning each node has up to 2 child nodes)\n",
    "\n",
    "**Merkle Trie**, Patricia Trie, Hash Trie\n",
    "\n",
    "**Modified Merkle Trie**, Modified Merkle Patricia Trie, Merkle Patricia Trie <- ETHEREUM's data structure to store world state\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![patricia-trie-not-radix-trie](https://gateway.pinata.cloud/ipfs/QmWf5u2ja9UusF3qiE1sCV4oyTCA8EQiVXv7HvrmVvuoND)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "source: https://stackoverflow.com/questions/14708134/what-is-the-difference-between-trie-and-radix-trie-data-structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Word origins\n",
    "\n",
    "**Trie** - from re**trie**ve\n",
    "\n",
    "**Patricia** - Practical Algorithm To Retrieve Information Coded In Alphanumeric\n",
    "\n",
    "**Radix** - \"In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers\" <- from Wikipedia\n",
    "\n",
    "**Merkle** - Ralph Merkle patented the Merkle tree in 1979 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Why Modified Merkle Patricia Trie and not XYZ?\n",
    "\n",
    "1. Cryptographically secure and efficiently verifiable, especially useful in the distributed setting\n",
    "2. Optimal insert / lookup / delete time complexities: O(log N)\n",
    "3. Reasonable-ish space complexity\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Better data structure for Ethereum?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I have come across https://arxiv.org/pdf/1909.11590.pdf during my research, that may present itself to be a worthy substitute\n",
    "\n",
    "Authors claim 20k TPS..."
   ]
  }
 ]
}