イーサリアム技術解説：Ethereumにおける真の分散化を目指す、ステートレスクライアントとVerkle Trees（第4回）

現在のEthereumでは、ステートを保存するためのデータ構造として「Merkle Patricia Trie」というMerkle Treesの一種を用いています。Verkle TreesはこのMerkle Treesが元になっているデータ構造であるため、まずはMerkle Treesについて理解を深めておく必要があります。

Merkle Treesを作成するためには、まず大量にあるデータをいくつかのファイルに分けた上で、1個ずつハッシュ化していく必要があります。こうしてハッシュ化されたデータのことを「Leaf Node」と呼びます。ここで登場する「Node」は、「データ構造の基本単位」のような意味を持った単語として使用されています。

次に、複数（基本的には2個）のLeaf Nodeをまとめた上で再度ハッシュ化を行います。このようにしてハッシュ化されたデータのことを「Branch Node」と呼びます。この作業を1個のハッシュ化されたデータになるまで繰り返します。最終的に作成される、1個のハッシュ化されたデータのことを「Root Hash」と呼びます。

このようにして作成したLeaf Node、Branch Node、Root Hashの集合体がMerkle Treesと呼ばれるデータ構造です。「Trees」という名称が付いているのは、Root HashからBranch Node、Leaf Nodeまでの形が木のようになっているためです。

Merkle Treesの利点のひとつとして、データ全体の整合性を保証できるということが挙げられます。これは、データの一部分が改ざんされた場合、Root Hash自体が変化するような構造となっているためです。これにより、Root Hashを確認するだけでデータ全体が改ざんされていないかどうかを確認することができます。このような利点から、EthereumだけでなくBitcoinなどの様々なブロックチェーンにMerkle Treesは利用されています。

Ethereumに用いられている「Merkle Patricia Trie」は、Merkle Treesに用いられているLeaf Node、Branch Nodeの2種類のNodeに加えて「NULL」「Extension Node」という2種類のNodeを追加したものとなっています。また、Branch Nodeについては16個のNodeをまとめてハッシュ化するような仕様となっています。このような変更を加えることで、オリジナルのMerkle Treesよりも効率的にRoot HashからLeaf Nodeの検索を行うことができるようになっています。

Ethereumは合計で4つのMerkle Patricia Trieを利用しています。それぞれの名称と、保存されているデータは以下の通りです。

• State Trie
  • アドレスごとのETH残高やトランザクション数、スマートコントラクトコードやstorageRoot（後述するStorage TrieのRoot Hash）が保存されたMerkle Patricia Trie
• Transaction Trie
  • トランザクションに関するデータ（送信元や送信先、ガス代など）が保存されたMerkle Patricia Trie
• Receipts Trie
  • トランザクションの実行に関する詳細データ（イベントログや実行ステータスなど）が保存されたMerkle Patricia Trie
• Storage Trie
  • スマートコントラクトのデータが保存されたMerkle Patricia Trie

ここまではMerkle Patricia Trieの仕組みや利点について解説してきましたが、Merkle Patricia Trieの持つ欠点についてはまだ紹介していませんでした。実は、この欠点がWeak statelessnessの実現を阻むものとなっています。

ブロック生成者以外のクライアントがステートを持たずに検証を行えるようにするWeak statelessnessを実現するためには、すべてのLeaf Nodeの検証に必要となる情報をブロック内に含めておく必要があります。

Leaf Nodeの検証に必要となる情報は、Merkle Treesにおいて「Proof」と呼ばれています。Proofには、Leaf NodeからRoot Hashに至るまでに使用したすべてのNodeが含まれます。

しかし前述したように、Merkle Patricia TrieはBranch Nodeで16個のNodeをまとめてハッシュ化するような仕様となっています。このため、1個のBranch Nodeあたり最大15個のNodeをProofに含める必要があり、ブロック内に含めることができないほどにProofのサイズが大きくなってしまうという欠点があります。

このような欠点から、Merkle Patricia TrieのままではProofをブロック内に含めることができないため、Weak statelessnessについても実現することができません。

ここで必要となるのがVerkle Treesです。Leaf Nodeの検証に必要となる情報は、Verkle Treesにおいて「Witness」と呼ばれており、WitnessはProofよりもサイズが小さいことが特徴となっています。

今回はVerkle Treesを解説する前に、前提となるMerkle Patricia Trieの仕組みや利点、そして欠点について説明しました。次回はいよいよ最終回として、Verkle Treesの詳細について見ていきたいと思います。

過去のイーサリアム技術解説

アカウント・アブストラクション（AA）特集

・ウォレットのUXを向上させる、Account Abstractionとその近況（第1回）

・ウォレットのUXを向上させる、Account Abstractionとその近況（第2回）

・ウォレットのUXを向上させる、Account Abstractionとその近況（第3回）

・ウォレットのUXを向上させる、Account Abstractionとその近況（第4回）

ダンクシャーディング特集

・レイヤー2のガス代を減少させる、ダンクシャーディングとData Availability（第1回）

・レイヤー2のガス代を減少させる、ダンクシャーディングとData Availability（第2回）

・レイヤー2のガス代を減少させる、ダンクシャーディングとData Availability（第3回）

ステートレスクライアント特集

・Ethereumにおける真の分散化を目指す、ステートレスクライアントとVerkle Trees（第1回）

・Ethereumにおける真の分散化を目指す、ステートレスクライアントとVerkle Trees（第2回）

・Ethereumにおける真の分散化を目指す、ステートレスクライアントとVerkle Trees（第3回）