Understanding the use of the Merkle-Patricia tree in Ethereum

Ethereum innovated when designing their blockchain, in many ways when compared to Bitcoin. One of them was my enhancing the kind of Merkle tree used within the blocks and how they are used.

In Ethereum, in contrast to the Bitcoim blockchain, they use three Merkle trees inside each block:

one for transactions
another for receipts (data showing the effects of transactions)
and the third for the State

In this noteboook we will explore using python code how all this merkling works. For that you will need to install the trie package maintained byt the folks at Ethereum:

pip install --user trie



In [3]:

    
from trie import HexaryTrie

Let's start by creating an empty tree (or trie):



In [5]:

    
t = HexaryTrie(db={})
t.root_hash









    Out[5]:





b'V\xe8\x1f\x17\x1b\xccU\xa6\xff\x83E\xe6\x92\xc0\xf8n[H\xe0\x1b\x99l\xad\xc0\x01b/\xb5\xe3c\xb4!'

The Hexary trie stores both keys and values, like a dictionary, and can be accessed like a dictionary.



In [7]:

    
t[b'my-key'] = b'some-value'



In [8]:

    
t[b'my-key']









    Out[8]:





b'some-value'



In [9]:

    
b'another-key' in t









    Out[9]:





False



In [10]:

    
t[b'another-key']  = b'another-value'



In [11]:

    
b'another-key' in t









    Out[11]:





True



In [12]:

    
t.root_hash









    Out[12]:





b'\xe2\xcc\x05\x18\xb4\x86\xc9O\xb0=Q\xeb\x90\x7f\x18\xa6\xa0\x1eh\xeb\x8f\xf0(r\xa1:\xfbn\xeb\xe6\xcd\x05'

But it also has a simple API with methods you can call in the tree



In [14]:

    
[m for m in dir(t) if not m.startswith('_')]









    Out[14]:





['BLANK_NODE',
 'BLANK_NODE_HASH',
 'db',
 'delete',
 'exists',
 'get',
 'get_from_proof',
 'get_node',
 'is_pruning',
 'root_hash',
 'root_node',
 'set',
 'squash_changes']



In [12]:

    
t.set(b'my-key2',b'second value')



In [13]:

    
t.exists(b'my-key2')









    Out[13]:





True



In [14]:

    
t.get(b'my-key2')









    Out[14]:





b'second value'



In [15]:

    
t.









    





Type:        HexaryTrie
String form: <trie.hexary.HexaryTrie object at 0x7f9404480a88>
File:        /usr/local/lib/python3.6/dist-packages/trie/hexary.py
Docstring:   <no docstring>



In [16]:

    
t.db









    Out[16]:





{b'\xeaQI\xc7r\x16\xea?\x95\\\x13\x85]\x97\x8dPJP4-\xd0\xbb6\xcf\x00\xa5J\x01$N3\xea': b'\xd3\x87 my-key\x8asome-value',
 b'\x89;o\xde\xe4\x1b$\x9d\xa8\xbe\xcd1\x02\x98\r\x816\xe1v\x0b\x9d\x04\x13\xfa\x121M\xa5\x15\x82\xa4\xb1': b'\xf8=\x80\xda\x8b nother-key\x8danother-value\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\xd2\x86 y-key\x8asome-value\x80\x80\x80',
 b'\xe2\xcc\x05\x18\xb4\x86\xc9O\xb0=Q\xeb\x90\x7f\x18\xa6\xa0\x1eh\xeb\x8f\xf0(r\xa1:\xfbn\xeb\xe6\xcd\x05': b'\xe2\x16\xa0\x89;o\xde\xe4\x1b$\x9d\xa8\xbe\xcd1\x02\x98\r\x816\xe1v\x0b\x9d\x04\x13\xfa\x121M\xa5\x15\x82\xa4\xb1',
 b'\xe0M\x1f\xfd\xf2\x1a\x13V\xc1\\\xf08\x85\x04\x94\xbf\xe7\xdb\x13\xcea\xc98\xfe\xc5\xe9\x85t\x15\xf5\xaf\r': b'\xe9\x80\x80\x80\xce2\x8csecond value\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x8asome-value',
 b'\x12\xa5H\x8c\x03s\xab\xf9\x13\x87:\x03\xfb\xb4\xca\xb2\x87W\xc6\xbb\x89\xd2\x9b\xe6z\x8a\xc8\xde\xf4\xa8\xd3t': b'\xe8\x86\x00y-key\xa0\xe0M\x1f\xfd\xf2\x1a\x13V\xc1\\\xf08\x85\x04\x94\xbf\xe7\xdb\x13\xcea\xc98\xfe\xc5\xe9\x85t\x15\xf5\xaf\r',
 b'\x1aR,\x98\x88\x84\xa6\x04\xad(AA{\x88\xf1mS\xb1\\\xd1\x08\xad\x96\xaf\xde\x85\xcb@\x89\xac\x82\xf9': b'\xf8K\x80\xda\x8b nother-key\x8danother-value\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\xa0\x12\xa5H\x8c\x03s\xab\xf9\x13\x87:\x03\xfb\xb4\xca\xb2\x87W\xc6\xbb\x89\xd2\x9b\xe6z\x8a\xc8\xde\xf4\xa8\xd3t\x80\x80\x80',
 b'\xe8\xab\x07\x9a\xca\xd6\x98\xc2-w\xa5\x02\xac\xd6\xe4i\x82\xd7\xb1\xfcF\xd6\xf475\xd2\x9117\xdcD|': b'\xe2\x16\xa0\x1aR,\x98\x88\x84\xa6\x04\xad(AA{\x88\xf1mS\xb1\\\xd1\x08\xad\x96\xaf\xde\x85\xcb@\x89\xac\x82\xf9'}



In [ ]: