Instant Auditing? Meet The Merkle-Patricia-Tree
Instant Auditing? Meet The Merkle-Patricia-Tree
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 complete picture over time and would see exactly when all the transactions were made and who was involved. If we wanted, we could anonymise the transaction data too.
It would be a world where we could audit at any point in time, and get an instant record of the current state, and also get snapshots 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.
Merkle Patricia Tree
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 as the string at that node, and the root of the tree is then an empty string [here].
So let’s take an example with five words to index: flower, flows, far, pitching and pitches. We can now draw a tree that 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 fourth 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 [here] — in order to create a trie that contains all the transactions. In this way, we can generate a complete worldview of all the transactions that have ever been made.
As we are dealing with transaction IDs, each of the keys has X hexadecimal characters. Every node in the trie can then have 16 possible children. The maximum depth of the trie will be X.
Each node can then be an extension, a branch or a leaf. A leaf is an endpoint 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 which 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.
In the following, we have the Top 2,500 Web sites in the world and implemented with a Radix Trie (aka PATRICIA trie) [here]:
Conclusions
And there you go. A complete world model of our financial system. Sometime soon, we need to adopt these methods, either within each of our banks or within our complete financial infrastructure, and create a new system that is completely auditable at any point in time, and where we see every single transaction. This will be a more trustworthy financial world. Our challenge, just now, is to make this world as open and transparent to all, but respect privacy and consent.
With zero-knowledge proof and homomorphic encryption, we are getting there, and Ethereum is just one example of a new world being created. Blockchain and DLTs will be the greatest machine that humankind has ever created, and we are just at the start of this journey.
Forget cryptocurrencies, and just think of transactions, and you have our new digital world. Our old ledgers are finished … meet the new world.