レッスン6 — Merkle Patricia Trie & 状態証明
問い
スマホ大のデバイスが「Alice のアカウントは 1 ETH 持っているか？」を知りたい — ただし Ethereum の 500GB 状態は持てない。だからフルノードに問い合わせると、返ってくるのは 数百バイト。デバイスはハッシュループを回し、結果を 手元の信頼済み 32 バイト と比較する。手元の 32 バイトは何で、ハッシュループは何を証明するか？
原理（最小モデル）
- MPT = Trie + Patricia + Merkle. Trie（経路がキーを綴る木）+ Patricia（単一子ノードを潰す経路圧縮）+ Merkle（各ノードが子のハッシュを保持）。
- stateRoot = 256 ビットの世界状態識別子. 1 バイトでも変わればルートが変わる。
- 3 ノード種. Branch（16 子 + 値、分岐点）+ Extension（共有プレフィックス、「次の N ニブルは全員で共通」）+ Leaf（最終値）。キーはニブル（4 ビット）単位。
- 包含証明 6 ステップ. ルートから経路ノード収集 → リーフを再ハッシュ → 親を上に再ハッシュ → 結果ルートと信頼済み stateRoot を比較。
- Witness = ブロック再実行に必要な trie ノード束. 「触った部分だけ」、数百 KB - 数 MB。
- 2 層 MPT. stateRoot → アカウントリーフ → storage_root → スロットリーフ。各コントラクトが独立ストレージ trie を持つ。
具体例
trie 構造:
graph TD
R[Branch — ルート<br/>16 子スロット]
R -->|nibble| E[Extension<br/>共通プレフィックス]
R -->|nibble| L1[Leaf<br/>アカウント → 値]
E --> B[Branch]
B -->|nibble| L2[Leaf<br/>アカウント → 値]
B -->|nibble| L3[Leaf<br/>アカウント → 値]
包含証明の流れ（6 ステップ）:
- ルートから X のキーへ向かって辿り、経路のノードを集める
- 各ノードは子を ハッシュ で参照（ポインタではない）
- 検証側に必要なのは経路ノードだけ。trie 全体は不要
- リーフを再ハッシュし、上に向かって親を再ハッシュ
- 結果のルートを 信頼済み
stateRootと比較 - 一致 → X の残高が本当に Y だと確認
Reth の本物の証明型（crates/trie/common/src/proofs.rs）:
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct AccountProof {
pub address: Address,
pub info: Option<Account>,
pub proof: Vec<Bytes>,
pub storage_root: B256,
pub storage_proofs: Vec<StorageProof>,
}
impl AccountProof {
pub const fn new(address: Address) -> Self;
pub fn verify(&self, root: B256) -> Result<(), ProofVerificationError>;
}
#[derive(Clone, PartialEq, Eq, Default, Debug)]
pub struct StorageProof {
pub key: B256,
pub nibbles: Nibbles,
pub value: U256,
pub proof: Vec<Bytes>,
}
impl StorageProof {
pub fn verify(&self, root: B256) -> Result<(), ProofVerificationError>;
}
2 層 MPT:
stateRoot
└── アカウントリーフ（AccountProof.proof が返す）
└── storage_root（AccountProof.info.storage_root にも保存）
└── スロットリーフ群（StorageProof.proof で証明）
trie crate 構造:
crates/trie/
├── common/src/proofs.rs ← AccountProof, StorageProof（上記）
├── trie/ ← trieデータ構造そのもの
├── parallel/ ← 並列trie計算
├── sparse/ ← witness/proof生成用のsparse trie
└── db/ ← MDBXバックエンドのtrie
失敗例（誤解）
「ストレージ証明は stateRoot に対して検証」— 間違い。2 層 MPT なので: ストレージ証明は storage_root に対して、アカウント証明（storage_root を含む）が stateRoot に対して。これを忘れるのが「state proof 検証器が動かない」最大の理由。
「Patricia 圧縮は最適化」— 半分正しい。圧縮なしだと 64 ニブルのキーで 64 ノード経路、ほぼ空の trie でも巨大。Patricia は 必須（最適化ではなく実装可能性）。
「非包含証明は補助的」— 間違い。info: Option<Account> が None → 非包含証明。「このアドレスにアカウントがない」を証明することは残高証明と同じくらい重要（airdrop、シビル耐性、slashing 適格性）。
🛑 予測。 ライトクライアントが witness（trie ノードバイトリスト）を受け取り、ルートまでハッシュアップ。検証者が必要だが witness にないものは何？（答え: 信頼済み stateRoot（過去に何らかの方法で信頼済み — consensus client から、他の検証済みヘッダから、created at genesis から）。これがあるからこそ証明は 暗号学的 — 「あなたが送ったバイトを信用する」ではなく「あなたが送ったバイトをハッシュした結果が、私が独立に信頼している 32 バイトと一致する」。）
ステップで組み立てる
Step 1: 3 ノード種を即答
Branch（分岐 + 16 子）/ Extension（共有プレフィックス）/ Leaf（最終値）。キーはニブル単位。
Step 2: 包含証明 6 ステップを暗唱
経路収集 → ハッシュ参照 → witness 経路のみ → リーフ再ハッシュ → 上に向かって再ハッシュ → 信頼済み stateRoot と比較。
Step 3: AccountProof フィールドを読める
address: 対象info:Option<Account>— None なら非包含証明proof: ルートからアカウントリーフまでの RLP ノード列storage_root: コントラクトストレージ trie のルート（stateRoot ではない）storage_proofs: 各スロットの証明（storage_rootに対して検証）
Step 4: 2 層構造を意識
ストレージ証明は storage_root に対して、アカウント証明は stateRoot に対して。親ハッシュが違う。
Step 5: Reth の trie crate を辿る
順序: common（型）→ trie（データ構造）→ db（本番グルー）+ parallel / sparse は MEV / witness 用途で別途。
答え合わせ
- stateRoot が世界状態を一意識別する仕組み: Merkle ハッシュが下にある全バイトに依存。1 スロット変えれば → 上位の親全部を再ハッシュ → ルートが変わる。
- 非包含証明の実用: airdrop（「このアドレスは過去 X トークンを保有していない」を証明 = 受給資格）/ slashing 適格性（「この validator はこの slot で signature を出していない」）/ シビル耐性（「このアドレスは新規」）。
- 各コントラクトに独立ストレージ trie の理由: ① コントラクト独立性（コントラクト A の更新がコントラクト B の ストレージ証明に影響しない）+ ② ローカル更新コスト最小化（コントラクトを 1 つ更新 = そのストレージ trie のルートだけ + アカウントリーフ 1 つ更新、巨大なグローバル trie 全部触らない）+ ③ ライトクライアントが特定コントラクトの全状態証明をコンパクトに得られる。
合格基準
- 3 ノード種を即答できる。
- 包含証明 6 ステップを暗唱できる。
AccountProofの 5 フィールドを役割で言える。- 2 層 MPT（stateRoot → storage_root → スロット）を絵で書ける。
- 非包含証明の実用例を 2 つ言える。
まとめ（3行）
- MPT = Trie + Patricia 経路圧縮 + Merkle ハッシュ。stateRoot が世界状態を 256 ビットで一意識別。
- 包含証明 = ルートから経路ノードを束ねて送る → 検証者が手元の信頼済み stateRoot と再ハッシュ結果を比較。witness は触ったノードだけ、数百 KB-数 MB。
- 2 層 MPT（コントラクトごと独立ストレージ trie）が独立性 + 効率 + ライトクライアント用途を成立させる。