前回は現在のEthereumが用いているデータ構造である、「Merkle Patricia Trie」について解説しました。今回は最終回として、ステートレスクライアントを実現する新しいデータ構造「Verkle Trees」について詳しく見ていきたいと思います。
Verkle Treesは、前回解説したMerkle Patricia Trieに似たデータ構造の一種です。Merkle Patricia Trieとの主な違いとして、各Nodeについて、ベクトルコミットメントと呼ばれる特別なタイプのハッシュ化を行うという点が挙げられます。ベクトルコミットメントを用いる最大の利点は、Leaf Nodeの検証に必要となる情報のサイズが非常に小さくなるということです。
Merkle Patricia TrieにおいてLeaf Nodeの検証に必要となるのは「Proof」という情報でしたが、このProofには検証したいLeaf NodeとRoot Hashの間にあるすべてのNodeに加えて、通過するBranch Node内におけるすべてのNodeを含める必要があります。少し複雑なので、図による例を見てみましょう。
青色の枠で囲まれた部分がRoot Hash、黄色の枠で囲まれた部分がExtension Node、緑色の枠で囲まれた部分がLeaf Nodeを示しています。また、点線で囲まれた16個のNodeの集合がBranch Node、Branch Node内の0がNULLを示しています。
ここで最下段中央に位置する、HORSEという値を持つLeaf Nodeを検証する場合を考えてみましょう。このLeaf Nodeを検証するために必要なProofは、以下の図において赤枠で強調されたNodeすべてになります。
このように、非常に多くのNodeがProofに含まれる必要があることが分かります。これによってProofはブロック内に含めることができないほどにサイズが大きくなってしまうため、Merkle Patricia Trieのままではステートレスクライアントを実現することができません。
次に、ベクトルコミットメントを用いて同じLeaf Nodeを検証する場合を見てみましょう。ベクトルコミットメントを用いる場合は、通過するBranch Node内におけるNodeを含める必要がなくなります。したがって、必要となるのは以下の図において赤枠で強調されたNodeのみです。
このように、Merkle Patricia Trieと比べて必要なNodeの数が大幅に減少したことが分かります。図ではNodeに加えて3つの証明が必要であることが示されていますが、この証明の数についても用いるベクトルコミットメントを工夫することによってさらに減らすことができます。
現時点でVerkle Treesに採用されると考えられているベクトルコミットメントは、「Pedersen Commitment」に「IPA（Inner Product Arguments）」を統合したものとなっています。このベクトルコミットメントを用いることで証明の数を1つにまとめることが可能です。さらに、この1つの証明を用いることで、すべてのLeaf Nodeの検証を行うことが可能となっています。図で示すと、以下のような形です。
上記の図では、これまで見てきたHORSEという値を持つLeaf Nodeだけでなく、SHEEPという値を持つ別のLeaf Nodeについても1つの証明を用いることで検証可能となっていることが示されています。このように、すべてのLeaf Nodeに対する検証を行えるような1つの証明を作成することができ、Verkle Treesではこの証明のことを「Witness」と呼んでいます。
WitnessはProofに比べてサイズが大幅に小さくなっており、20～30分の1に収まるとされています。これらの特性によって、ブロック内にWitnessとRoot Hashを含めることができるようになり、バリデーターノードはWitnessとRoot Hashというブロック内に含まれるデータだけで検証を行うことができるようになります。また、クライアント側で検証のためにデータ構造全体、つまりステートを持つ必要がなくなるため、ステートレスクライアントが実現されることになります。
Verkle Treesの実装時期については、当初は2025年初頭のリリースを目指している次期大型アップグレード「Pectra」における実装が検討されていました。しかし、このPectraではAccount AbstractionやPeerDASなどの別の技術の実装に注力されることが決まったため、Verkle Treesの実装は延期されることになりました。
その一方で、EIP-2935などといったステートレスクライアントの実現に必要となる周辺技術の実装はPectraアップグレードにおいても着々と行われることが予定されています。Verkle Treesについても、まだ未定ではありますが、Pectraの次の大型アップグレードである「Fulu-Osaka」アップグレードにて実装されるかもしれません。
PCだけでなく、スマートフォンなどの携帯端末やRaspberry Piなどのマイクロコンピューターでノードを動かせるようになるような、Ethereumにおける真の分散化はそう遠くない未来に実現されそうです。
過去のイーサリアム技術解説
アカウント・アブストラクション（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回）
web3ニュースレター
