Ethereum Merkle Patricia Tree Riddle

Question

since I spend some time on diving into the data structures that ethereum is based on, I stumbled upon the following task from a stanford course which i included at the bottom. I am struggling especially with the second and third question.

For the first question my assumption is, that the simple answer is because the kv node "44:" is referring to another diverge node as a stored value instead of beeing a diverge node itself.

But for the second question already I am wondering why the question is asking for a given key "44431337a" while missing out the prefix value of the diverge node "d" (shoudn't it be "444d31337") here as well as in key of "fc" missing out the prefix "b" (shouldnt it be "fbc") but including the complete prefix in "1a3098a" again without missing out any diverse node prefix.

For the third question i dont have any clue at all how to answer.

I would be very happy if any of you guys would have a rough explanation or a recommendation in which way to think to find the correct solution.

Thank you guys so much!!!

---

Following there is the given transaction:

Where:

• empty nodes, represented as all zeroes
• diverge nodes, which are represented by the hash of a 17-member array. The first 16 items in the array are child node identifiers which contain the hashes of up to 16 child nodes (which will be 0 for empty children). Each child node extends the path of its parent by one nibble (4 bits) of key, defined by its place in the array. This is shown as an edge label in the figure below. The 17th item is a data value (which may be 0) which is mapped to the key representing the path to this node. Internal nodes are represented in blue below, with the child array represented by pointers to child nodes.
• kv nodes, which include an arbitrary-length path, plus either the hash of another diverge node or the hash of a data item (making the node a leaf). This path is added to the path built up by this node’s place in the tree. These nodes are shown in pink above.

There are the following tasks to complete:

1. In the following example, 9 keys are present, with 13098a mapped to “c” and 444 to “d”: Explain why in the above example there is no label on the arrow coming out of the intermediate node with the path 44.
2. Which data would you need to supply for a proof that the key “44431337a” has no data mapped to it? How about the keys “fc” and “1a3098a”?
3. Explain why this does not hold for the trees maintaining the long-term storage for each contract (addressable by 256-bit addresses). How might you write a malicious contract which stores k words in memory and then makes a single write which is expensive as possible?

Answer 1

First Question: The reason 44: has a connection to a diverge node without a label is because it has the hash of that node ("d") stored in the kv node (44:). So it is assumed the there is no label because there is only 1 path.

Second Question:

44431337a - There are two ways to answer your confusion, either the data item is included in the path or it is not. Question 1 leads me to believe that it is included in the path. The second question is referring to disproving nodes exist, so you might have just stumbled upon the answer. When you traverse the path "444" you see that 444 maps to a data item "d" which is not 3 and it is not a diverge node so that would be the node to disprove that the key exists.

fc - The first diverge node maps to "b" so that would disprove the key.

1a3098a - Same story as 44431337a

Third Question: The issue with the trees is having to have a whole tree in order to identify one random address. As the tree grows the amount of storage increases and the ease of use decreases. Another issue is the read and writes when updating the tree, you need to traverse and re-map vast amounts of data in order to make minor medications. An attack could target this so make the tree have to remap nodes and change common traversals of the tree. Such as adding the key 444c which would require changing 44 into a diverge node.