Correcting Merkle Patricia Trie Example
jacekv opened this issue · 1 comments
Hi everyone, I have been working on implementing my own Merkle Patricia Trie (MPT), in order to gain a better understanding of it. I used the wiki as a source to gather information. Yet, the example given in the wiki is not entirely correct, based on the given specifications.
This is how the example looks like using the following key/value pairs: ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion')
rootHash: [ <16>, hashA ]
hashA: [ <>, <>, <>, <>, hashB, <>, <>, <>, hashC, <>, <>, <>, <>, <>, <>, <>, <> ]
hashC: [ <20 6f 72 73 65>, 'stallion' ]
hashB: [ <00 6f>, hashD ]
hashD: [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
hashE: [ <17>, hashF ]
hashF: [ <>, <>, <>, <>, <>, <>, hashG, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ]
hashG: [ <35>, 'coin' ]
Right under the example the following information is given:
When one node is referenced inside another node, what is included
is H(rlp.encode(x)), where H(x) = sha3(x) if len(x) >= 32 else x and
rlp.encode is the RLP encoding function.
Based on this, the example trie should look more like this:
rootHash: [ <16>, hashA ]
hashA: [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
hashB: [ <00 6f>, hashD ]
hashD: [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
hashE: [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coin' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]
This might be a small issue for some but there are also some others who rather appreciate a 'correct' example which ensures that they understood a concept/algorithm/data structure correctly.