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!!!
- 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:
- 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.
- 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”?
- 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?