2

A leaf node is defined as the tuple [encodedPath, value], and encodedPath uses the Hex-Prefix encoding. Is it possible we have a leaf node with encodedPath having only the prefix and no partial path included?

Taking the following data...

<5e 52> : 'val1'
<ac 40> : 'val2'
<ac 4f> : 'val3'

...would the trie look like this or I am wrong?

rootHash: [ <>, <>, <>, <>, <>, hashA, <>, <>, <>, <>, hashB, <>, <>, <>, <>, <>, <> ]
hashA:    [ <3e 52>, 'val1' ]
hashB:    [ <00 c4>, hashC ]
hashC:    [ hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <>, hashE, <> ]
hashD:    [ <20>, 'val2' ]
hashE:    [ <20>, 'val3' ]

Note that rootHash and hashC are branch nodes; hashB is an extension node; and hashA, hashD and hashE are leaf nodes. My doubt is related to hashD and hashE encodedPaths. If I understood it's correct to put 20 as in HP encoding a leaf node with even path length (in these cases 0) should get the prefix 2 and an additional 0 padding nibble.

1 Answer 1

0

I have constructed the trie in the same format as you did (given the information in https://github.com/ethereum/wiki/wiki/Patricia-Tree) and this lead me to the same result. To answer your question: Yes, if a leaf node contains no furthers nibbles in the partial path you end it with the prefix 20 (2 for even nibbles count in path and 0 for padding, as you wrote) and no further path.

The encoded path will be stored as a bytearray. The algorithm works like this: given an encoded path b as a bytearray:

# Python style code
flag = b[0] & 0xF0
nodetype = flag & 0x2
parity = flag & 0x1
partial_path = []

# parity odd?
if parity:
    partial_path.append(b[0] & 0x0F)

# append all other bytes from the encoded path (or do nothing if there is no encoded path)
for item in b[1:]:
    partial_path.append(item)

# extension node
if not nodetype:
    # do stuff ...

# and so on
2
  • Nice, so you really think we are right? Do you think this is a real possible situation or the data is manipulated some way to avoid that? I really need to know for sure this stuff. Please, if you find something in the official documentation or good source that could confirm our test let me know. Cheers Sep 6, 2018 at 18:27
  • Yes, by definition it must be like that. Look in the yellow paper: ethereum.github.io/yellowpaper/paper.pdf as of 06.09.2018 23:34 UTC. Go to Appendix C and check the last sentence before equation 186 and check equation 186 itself. By this definition you know, it's the prefix + every remaining nibble (in the set Y). If the set is empty, only the prefix is left. @EtherswornCanonist
    – sea212
    Sep 6, 2018 at 19:39

Your Answer

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

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