Typo in the MPT blog post

[hidenori-shinohara]

Describe the bug

The blog post on MPT seems to have a few typos.

typo 1

When one node is referenced inside another node, what is included is H(rlp.encode(x)), where H(x) = keccak256(x) if len(x) >= 32 else x and rlp.encode is the RLP encoding function.

Appendix D of the yellow paper states that we need to check len(rlp.encoding(x)) >= 32 instead of len(x) >= 32. I find this problematic since len(x) is not well-defined and confusing.

Here's the quote from the yellow paper:

As a means of reducing storage complexity, we store nodes whose composed RLP is fewer than 32 bytes directly; for those larger we assert prescience of the byte array whose Keccak-256 hash evaluates to our reference.

typo 2

Some branch nodes in the example trie containing ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion') seem incorrect.

    rootHash: [ <16>, hashA ]
    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
    hashB:    [ <00 6f>, hashD ]
    hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
    hashE:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coin' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

HashD and the referenced node in HashE are both branch nodes with one non-zero entry. However, this is explicitly prohibited in the yellow paper.

A branch is then only used when necessary; no branch nodes may exist that contain only a single non-zero entry.

To reproduce

Go to https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/

Expected behavior

For the first one, one needs to replace len(x) with len(rlp.encoding(x)). For the second one, one would have to recalculate what the trie would look like without a branch node with one branch.

Screenshots

No response

Desktop (please complete the following information)

No response

Smartphone (please complete the following information)

No response

Additional context

No response

Would you like to work on this issue?

• Yes
• No

[github-actions]

This issue is stale because it has been open 45 days with no activity.

[wackerow]

Looks like this content as since been updated. I'm going to close this out as I believe it's been resolved, but @hidenori-shinohara please feel free to re-open if I've missed anything. Thanks!