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.