Modified Merkle Patricia tree of the empty map

[acoglio]

Eq. (194) defines TRIE(map) = KEC(c(map,0)) -- I'm using 'map' for \mathfrak{I}.

Thus TRIE(ø) = KEC(c(ø,0)) -- where ø is the empty map.

However, c(ø,...) is not well-defined:

• The condition ||map|| = 1 for the first case of eq. (196) does not hold if map = ø, so we move to the second case.
• In the second case of eq. (196), the sub-formula [forall I in map : ...] is trivially true when map = ø, so it disappears from the conjunction.
• The definition of j then reduces to j = max {x : exists k : ||k|| = x} -- I'm using 'k' for \mathbf{l}.
• For every x, there surely exists some sequence k of length x, so the set consists of all natural numbers. That is, j = max {x : x is a natural number}, which is not well-defined.

c should not be applied to the empty map. Note that eq. (195) applies c only if map ≠ ø.

So what should eq. (194) say?

One option is TRIE(map) = KEC(n(map,0)), i.e. replace c with n. This avoids the problem above, but since often n(...) = KEC(...), we would often have TRIE(...) = KEC(KEC(...)), which seems a bit strange to me.

Another option is TRIE(map) = n(map,0), which avoids the problem above and the "double-hash" above.

Note also that the first paragraph of Appendix D says that the single value that identifies the map is either a 32-byte sequence or the empty byte sequence. If TRIE(...) = KEC(...), as in the current definition and as in the first option above, then that value is always a 32-byte sequence and never the empty byte sequence. If instead TRIE(...) = n(...), as in the second option above, then the value is a byte sequence whose length may actually vary between 0 and 32.

A third option could be to have the second case of eq. (196) require map ≠ ø, therefore using the third case of eq. (196) when map = ø. In this case, the result would be RLP(((),...,())) because each u(j) = n(ø,i+1) and v = {} as well. But even with this option, eq. (194) would still be TRIE(...) = KEC(...) and thus it would never be the empty byte sequence.

A fourth option is that eq. (194) should really have two cases:

• If map = ø, then TRIE(map) = (), i.e. the empty sequence of bytes.
• If map ≠ ø, then TRIE(map) = KEC(c(map,0)), as the current equation says.
  This way, TRIE(map) is always either empty (first case) or 32 bytes (second case), consistently with what the first paragraph of Appendix D says.

The fourth option seems perhaps the most likely interpretation at this point.

[skbaek]

Just ran into the same issue. Seems like it has not been completely clarified yet?

The informal description of the 'extension' case (not sure if it was added after this issue was opened) says that the common part must be shared by at least two distinct keys, so I guess that settles it, but it would be helpful to include that information in the definition of c as well.

What's even more strange, however, is that actual developer tools don't seem to conform to this definition, even after taking above clarification into account. If we go by the yellow paper definition, then c(ø,0) = ((), (), (), (), (), (), (), (), (), (), (), (), (), (), (), (), ()). But empty trie root according to, say, ethereumjs or Foundry is 0x56e8...B421. This is the value you get when c(ø,0) = (), which is impossible by definition of c.