EthereumのMerkle Patricia Trie（第1回/全2回）

Ethereumは時価総額で2番目に大きいブロックチェーンで、数千億ドル規模の価値を保全している。分散型台帳であることは誰もが知っている。しかし、実際にそのデータをどう保存しているのだろうか。数億のアカウント。独自の永続ストレージを持つスマートコントラクト。トークン残高、NFTの所有記録、DeFiのポジション。250 GBを超える状態が世界中の約100万のバリデータに複製され、日々増え続けている。その答えがMerkle Patricia Trieというデータ構造だ。

これはまもなく変わるかもしれない。Ethereumのロードマップは、ステートレスバリデーション（完全な状態を保存せずにブロックを検証すること）を実現するために、この構造を置き換えることを目指している。ジェネシス以来最大の構造的変更になるだろう。その理由を理解するには、まず今日のしくみと、それがなぜ限界に達しつつあるのかを知る必要がある。

ワールドステート

Ethereumはワールドステートを維持している。つまり、各キーがアドレス、各値がアカウントであるキーバリューストアだ。

アカウントには2種類ある。外部所有アカウント（EOA）は秘密鍵によって管理され、トランザクションを開始できる。コントラクトアカウントはコードを保持し、トランザクションによってトリガーされる。どちらも同じ4つのデータフィールドを共有している。

• nonce：トランザクションごとにインクリメントされるカウンタ
• balance：保有するネイティブETH¹
• codeHash：アカウントのバイトコードのハッシュ（EOAでは空）
• storageRoot：コントラクトのストレージを指すハッシュ（EOAでは空）

コントラクトではストレージとコードが分離されている。ストレージ（トークン残高、所有記録、設定など）は独自のキーバリューストアに存在し、storageRootを通じてワールドステートの中にネストされている。コードはオンチェーンに保存されるが、ワールドステートの外にあり、codeHashで参照される。このネストされたストレージについては、Merkle証明のところで改めて取り上げる。

なぜ木構造なのか？

一般的なテック企業でこれを構築するなら、おそらくフラットなキーバリューマッピングを使うだろう。アドレスをキーに、アカウントデータを値にする。ルックアップは高速で、更新も簡単で、ツールも成熟している。なぜEthereumにはもっと複雑なものが必要なのか。

Ethereumは分散システムだ。約100万のバリデータが同じトランザクションを実行し、同一の状態に到達しなければならない。コンセンサスを検証するために、各ノードはコミットメントを生成する。つまり、状態全体を表す短い値だ。現在のEthereumでは32バイトのハッシュがこれにあたる。このコミットメントはブロックヘッダに格納される。自分のものが一致しなければ、状態はネットワークから乖離していることになる。

これにより、フラットなキーバリューマッピングでは満たせない2つの要件が生じる。

1. 効率的なコミットメント

フラットなマッピングからコミットメントを計算するには、すべてのエントリを何らかの決定的な順序でシリアライズし、まとめてハッシュする必要がある。残高を1つ変更するたびに、状態全体を再シリアライズして再ハッシュしなければならない。250 GB以上のデータに対してブロックごとにO(n)の処理だ。

木構造はこれを解決する。各ノードのハッシュは子ノードのハッシュから計算される。リーフを1つ変更すると、ルートまでのパス上のハッシュだけを更新すればよい。O(n)ではなくO(log n)の操作で済む。

2. 部分証明

Aliceは誰も信頼せずに残高を確認したい。250 GB以上の状態を保存することはできない。フラットなキーバリューストアでは、値を検証する唯一の方法はコミットメントを自分で再計算することだが、それには状態全体が必要だ。

木構造はこれも解決する。値の存在を証明するために、証明者はそのリーフからルートまでのパスと、各レベルでハッシュを再計算するのに十分な情報（証明）を提供する。Alice（検証者）はこの小さな証明からルートハッシュを再構築し、既知のルートと照合できる。

トライ：キーをパスとして使う

キーバリューストア（アドレス → アカウント）を木構造に整理する必要があることはわかった。では、どうやって？ トライ（"try"と発音する。retrievalに由来）を使う。

トライではキー自体が木のパスになる。 キーの各文字がどの枝に進むかを決定する。4a7f...のような16進キーの場合、ルートから始めて4で分岐し、次にa、次に7、次にfと進み、格納された値に到達する。キーを明示的に保存する必要はない。パスそのものがキーだ。

Ethereumは16進トライを使う。16進数字（0-F）ごとに1つの子を持ち、最大幅は16だ。深さはキーの長さに依存する。挿入前に各アドレスはkeccak256でハッシュされ、32バイトのキー（16進数字で64桁）が生成される。² コントラクトのストレージキーも同様にハッシュされる。どちらのトライも最大深さは64だ。Ethereumが使うPatricia変種は、子が1つしかないブランチノードをエクステンションノード（上の図の紫色）に圧縮することでトライをコンパクトにする。

Merkle Patricia Trie

トライの構造が整った。次にMerkleの部分を追加する。

プレーンなPatriciaトライでは、各ノードはキーの16進数字を表す。Merkleトライでは、各ノードが子のハッシュから計算されたハッシュも持つ。いずれかのリーフを変更すると、ルートまでのパス上のすべてのノードが新しいハッシュを持つことになる。

各ノードのハッシュはどう計算されるのか。ブランチノードの場合、すべての子への参照を結合し、keccak256でハッシュする。出力は1つの32バイトハッシュだ。

ルートハッシュは状態全体にコミットし、すべてのブロックヘッダに格納される。どのバリデータもブロックのトランザクションを実行した後にステートルートを計算し、一致を検証できる。変更されたリーフからルートまでのパスだけを再ハッシュすればよいので、先ほど約束したO(log n)の更新が得られる。つまり、効率的なコミットメントだ。

これはどの性質に依存しているのか。衝突耐性だ。同じkeccak256ルートを生成する2つの異なる状態を見つけることは計算上実行不可能だ。ルートハッシュは状態を一意に識別する。

実際のEthereumの実装はもっと複雑で、ハッシュ前のノードシリアライズにRLPエンコーディングを使い、ノードタイプ（ブランチ、リーフ、エクステンション）ごとに異なる配列仕様があり、偶数/奇数パス長のフラグもある。

Merkle証明

先ほど、木構造が部分証明（状態全体なしで単一の値を検証する方法）を可能にすると述べた。仕組みはこうだ。

Aliceはスマートフォンのウォレットから自分のEthereum残高を検証したい。完全な状態は250 GB以上で、保存できない。ウォレットは裏でInfuraやAlchemyのようなサードパーティのノードプロバイダにクエリするかもしれないが、そのプロバイダが侵害されていたり、嘘をついていたり、ハッキングされている可能性がある。知る術がない。

Merkle構造なら別の方法がある。Alice（検証者）はブロックヘッダ（各数KB）だけを保存する。任意のフルノード（証明者）に残高と証明を要求する。証明からルートを再計算する。ヘッダ内のステートルートと一致すれば、残高は正しい。数学的に保証される。

証明と検証

深さ $d$ のトライとパス $k = (k_0, k_1, \ldots, k_{d-1})$ を考える。各 $k_i$ はアカウントのハッシュされたキーの16進数字だ。このパスの値を証明するために、証明者は以下を提供する。

• リーフの値 $v$（4つのアカウントフィールドすべて）
• 各深さ $i$ で最大15個の兄弟ハッシュ $S_i = \lbrace h_{i,j} : j \neq k_i \rbrace$

検証はルートをボトムアップで再構築する。リーフをハッシュし、木を上に向かって各レベルで兄弟と結合していく。

$$H_d = \text{hash}(v)$$

$$H_{i-1} = \text{hash}(h_{i,0} | h_{i,1} | \cdots | h_{i,15})$$

$$\text{ただし } h_{i,j} = \left\lbrace \begin{array}{ll} H_i & j = k_{i-1} \text{ のとき} \\ S_i[j] & \text{それ以外} \end{array} \right.$$

$H_0$ がステートルートと一致すれば、証明は有効だ。証明者は完全なアカウントを提供しなければならない（いずれかのフィールドが間違っていればリーフハッシュが変わり、証明は失敗する）。しかし検証者は状態の残りを見ることはない。パスに沿った兄弟ハッシュだけだ。

コントラクトストレージの値についてはどうだろうか。各アカウントには storageRoot があり、これはそのコントラクトのストレージを含む別のトライのルートであることを思い出してほしい。ストレージの値を証明するには、2つの証明が必要だ。ステートルートからアカウントまでの証明（storageRootを含む）と、storageRootからストレージスロットまでの証明だ。同じ検証ロジックが適用されるが、ネストされている。

より小さな証明、より大きな可能性

Aliceは1つの状態値をMerkle証明で検証できる。バリデータもブロックごとに同じようなことを数千回行う。状態を読み取り、トランザクションを実行し、新しいステートルートを計算する。

Ethereumの核心的な理念は分散化だ。Vitalik Buterinが述べたように、「長期的には、完全に検証されたEthereumノードを文字通りスマートフォンで動かせるようにする計画がある」。バリデーションはデータセンターだけでなく、一般的なハードウェアで実行可能であるべきだ。

現在、ワールドステートは週に約1ギガバイトのペースで増加している。増大するにつれて、トライのメモリに収まる部分が減り、ランダムなディスクリードが必要なルックアップが増える。以前の記事で取り上げたように、ディスク上のデータアクセスはボトルネックを生み出しうる。Ethereumの12秒のスロット制約を満たすには、バリデータにはより高速なストレージ（最低でもSSD、ますますNVMeクラス）が必要になり、コストが上昇して分散化の目標に逆行する。

しかし、バリデータが状態をまったく保存しなかったらどうだろう。ディスクから読み取る代わりに、ブロックが触れるすべての値の証明を受け取ることができる。Aliceが使ったのと同じトリックを、スケールアップしたものだ。

問題は証明サイズだ。各証明には各レベルで兄弟ハッシュが必要で、15兄弟 × 64レベル × 32バイト ≈ 30 KBが最悪ケース、平均で約3 KBだ。現在のブロックが約3000万ガスを使い、コールド状態読み取りに2100ガスかかることを考えると、³ 1ブロックが数千の値に容易にアクセスする。平均約3 KBとして、ブロックあたり数MBの追加帯域幅になる。ブロックあたり10 MBの増分は、バリデータ1台あたり月2 TB以上の追加帯域幅になる。個人ステーカーをデータセンターに追いやるようなオーバーヘッドだ。

つまり、証明サイズが律速制約になっている。証明を小さくできれば、ステートレスバリデーションが実現可能になる。

次回予告

証明を縮小する一つのアプローチは、ハッシュベースのコミットメントを多項式コミットメントに置き換えることだ。Verkle木はまさにこれを行い、証明を数KBからそれぞれ150バイト未満に縮小する。Ethereumの状態木は実際には別の方向（耐量子ハッシュベースのコミットメントを用いたバイナリトライ）に進んでいるが、その背後にある暗号技術はきわめて重要だ。多項式コミットメントはゼロ知識証明の基盤であり、ゼロ知識証明は急速に発展中の分野で、Ethereumのスケーリングロードマップをはじめ、その先にも幅広い応用が進んでいる。第2回では、有限体と楕円曲線の上に構築されるVerkle木の仕組みを扱う。

状態の増大はもう一つの問題も引き起こす。ステートレスバリデーションによってバリデータは状態の保存を省略できるかもしれないが、ブロックを構築するためには完全な状態がどこかに存在しなければならない。期限付きストレージやUTXOスタイルのレコードといった新しいストレージプリミティブが現在議論されており、250 GB超の状態が無限に増え続けるのを食い止められる可能性がある。

付録