A Radix Trie (aka PATRICIA trie)
Back In the following, we have the Top 2,500 Web sites in the world, and implemented with a Radix Trie (aka PATRICIA trie) In the following we have the Top 2,000 web sites on the Internet, and which have been indexed using the PATRICIA trie.
This was implemented based on the code [here].
Imagine if we could capture the current state of every financial transaction that was made from every single bank and in the whole of our financial infrastructure. And this would be for the whole history of our financial infrastructure. So at any point in time, we would see the whole of our banking infrastructure and would see exactly when all the transactions were made and who was involved.
It would be a world where we could audit at any point in time, and get an instant record of the current state, and a snapshot of every previous state. In this way, an auditor would be able to see everything and move back and forward through time. Well, what I’ve described is Ethereum, and it uses the Merkle-Patricia-Tree (trie) method to create a full world model of all the transactions.
With the Merkle tree, we create a tree of hashes, and where the root hash provides the overall consistency of the data within the tree. Its core advantage is that we can easily check that data is within the tree by analysing a subtree [here].
A Merkle-Patricia-Tree enhances this by using a key (normally defined as a string) to store associative arrays. Patricia is defined as a Practical Algorithm To Retrieve Information Coded In Alphanumeric — paper. A node is then associated with a key. This is defined as a trie — a digital tree. This differs from a Merkle tree in that the actual key for each node is not stored, but its position in the tree is used to define the key. The nodes which are below a given node are defined with the same prefix of the string at that node, and the root of the tree is then an empty string.
So let’s take an example with five words to index: flower, flows, far, pitching and pitches. We can now draw a tree which will index these strings:
If a user enters "f", we progress to the second level, and then enters "low", and onto the third level. And finally, they enter "s", and we move to the forth level. We can see that the data is now ordered and associated, and where the position in the tree defines the key to which that data element is associated with.
In the Ethereum blockchain, we use a modified Merkle Patricia Trie — as defined in the Yellow [Paper] — in order to create a trie which contains all the transactions. In this way, we can generate a complete worldview of all the transactions that have ever been made. Each of the keys has X hexadecimal characters, and thus every node in the trie can have 16 possible children. The maximum depth we will have is X.
Each node can then be an extension, a branch or a leaf. A leaf is an end point and will contain the transaction value. In the diagram, we see that the root hash is the hash of all of the transactions. We then have an extension to define the top level node, and where we can see that there are four transactions and are defined by the keys of "a711355", "a77d337", "a7f9365" and "a77397". The transaction amounts are for 45.0 ETH, 1.00 WEI, 1.1 ETH and 0.12 ETH, respectively.
We can then follow the tree to find the transactions. We start with the key value of “a7…” (ROOT: extension node). Then we have a leaf at “a7..1355” (and where “1355” is the end part of the key). The transaction value here is 45.0 ETH. We have another leaf node with “a7..9365” (and where “9365” is the end part of the key), and with a transaction value of 1.1 ETH.
Next we have an extension to “a7d3”. Finally, we get to the last two transactions with end leaves (“a7d33..7” and “a7d39..7”), and which have transaction amounts of 1.00 WEI and 0.12 ETH, respectively.