2

I am currently trying to implement Ethereum's Merkle Patricia Trie using Python 3.6 and I am having some troubles and honestly I am frustrated.

I am using the following sources:

I do get the concept of the Merkle Patricia Trie (MPT) and how it works. Yet, I am having problems implementing it.

First I would like to know of the example trie is given in Ethereum Witi is correct or not. I feel that it is not correct.

A trie which contains the following key/values pairs: ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion')

Their result:

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' ]

My result:

rootHash: [ <16>, hashA ]
hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]  
hashB:    [ <00 6f>, hashD ]
hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
hashE:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coin' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

Why does it look so different? Right under the example is the following sentence:

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.

Furthermore, I tried to compare the results from my code with the JS MPT implementation and this gives a completely different root hash.

I am wondering, what is correct? Do I misunderstand the example? Are there any other "better" documentation? I appreciate any help.

Improve this question
4
  • For me your result appear to match, if you extract the inner [] to a separate hash. For example if you extract [ <20 6f 72 73 65>, 'stallion' ] as hashC then hashA will match the expected output.
    – Ismael ♦
    Commented May 8, 2019 at 18:02
  • Really? Have you tried it out?
    – Donut
    Commented May 9, 2019 at 14:49
  • Unless I missed it, you didn't share your code, so it's going to be hard for anyone to help you. I do agree with you that the example from the Ethereum wiki looks wrong in the details. E.g. they don't show the RLP encoding and seem to use hashes everywhere instead of directly embedding results that have a length less than 32. The other sources you cite seem to have more realistic results for you to compare to. If you want help beyond that, please share your code.
    – user19510
    Commented May 10, 2019 at 5:46
  • You right, I haven't shared my code in the first place. I just uploaded it on github.com/jacekv/merklePatriciaTree Currently, I get the correct hash, which leaves me to conclude, that the given example on the Ethereum Wiki is not correct. Yet, my code is still having problems when it comes to hex data, as given in github.com/ethereum/tests/blob/develop/TrieTests/… the very last test case. It is frustrating because there is not much good documentation about it :(
    – Donut
    Commented May 10, 2019 at 9:57

1 Answer 1

Reset to default
0

Alright, after spending time to figure out how it works, I finally made it. Yay :D

I believe that the given example in the Ethereum Wiki is not correct! My code generates my given result and it returns the correct hash!

In case you are are interested in order to figure out who it works, the code is on github (I still have to clean it up a bit and write a few more comments).

In the comments, I also found a way to work with hex values as given in the test cases. Everything is within the repo :)

I am going to try to update the Wiki example so that people are not as confused as I have been...

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.