Ethereum Merkle Patricia Trie and Hashes

Question

In Ethereum, there's a hash of all of the 3 tries in each block.

Out of curiosity.

The docs state that the functionality is supposed to just provide a mapping between 160bit keys and values. I find this not clear.

If there's a hash for each trie, the hash depends on a particular order of data etc. So if we implement the trie as a Merkle-Patricia trie with 3 types of nodes then if each of these 3 node types contains a hash of itself (and in case of a Branch-node the hashes of all the nodes below then the hash IS implementation-dependant.

Would you shed some light?

Specific questions:

Which trie nodes contain a hash? In case of a leaf-node, it is clear. it contains a hash of the data it contains. In case of an extension node, it is the same. What about the branch node? does it contain a hash of all of its children located one level below?

Or do maybe the branch nodes just contain a hash of all the leaf nodes below. Even if so, the hash in the root of each of the 3 tries would depend on the order of leaves.

So even if we leave the implementation details omitted, all the implementations would need to come up with the very same hash for each of the 3 tries.

The entire question could be formulated as:

How exactly is the hash for each of the 3 tries computed?

For instance, from a cryptographic point of view, there would be no point for an extension node to contain a hash of itself or even to take such an abstract object under consideration when computing the higher-level (in the-trie) hash what would only matter in the end would be the data stored in the leaves below.

Answer 1

Each node in the trie is identified by it's hash. Suppose there is a leaf with encodedPath 0x01 and a value 0x78 (I omit some things like even/odd coding for simplicity):

leaf [0x01, 0x78]

The hash of this node is calculated as hash1 = sha3(rlp([0x01, 0x78]).

Suppose now there is a root, which is a branch node, where the 2nd nibble points to the leaf hash1 and value 0x56:

branch [<>, hash1, <>,...,<> , 0x56]

The hash of this node is calculated as hash2 = sha3(rlp([<>, hash1, <>, ..., 0x56]). This branch hash doesn't include the leaf data directly, rather, it includes leaf hash. Now, if leaf is changed, then its hash will change. Because its hash is included in the hash of the root, the root hash will also change.

In other words, changing any data in a node would change it's hash. Because this hash is used in the upper level node, its hash will change too, etc. all the way up to the root.

Hope it clarifies things.

---

3 node types contains a hash of itself

I wouldn't say they contain the hash of itself. As I noted above each node is identified by its hash, this hash is included in the upper level node.

the hash in the root of each of the 3 tries would depend on the order of leaves

Any trie that contains the same set of entries will have the same order of leaves and the same hashes of nodes and the root.