Leaf node with encodedPath containing only Hex-Prefix in Merkle Patricia Trie

Question

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.

Answer 1

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