Ethereumのステートを管理する上で重要な構成要素の1つがMerkle Patricia Trie。ビットコイナーならマークルツリーはお馴染みだが、Merkle Patricia Trieはマークルツリーとはだいぶ勝手が違うデータ構造なので、どんな仕組みで構築されて、特定のアイテムがそれに含まれていることをどう探索、検証しているのか、またそのボトルネックについてまとめておく。 ステートの種類 Ethereumのブロックヘッダーには、以下の3つのステートツリーのルートハッシュが記録されてる。 ステートルート: 俗にワールドステートと呼ばれる、各アカウントのステートで構成されるツリーのルートハッシュ。 トランザクションルート: ブロックに含まれるトランザクションで構成されるツリーのルートハッシュ。 レシートルート: トランザクションレシートで構成されるツリーのルートハッシュ。 ステートルー