ヴァークル・ツリー

ヴァークル・ツリー（「ベクター・コミットメント（Vector commitment）」と「マークル・ツリー（Merkle Trees）」のかばん語）は、ブロックを検証する能力を失うことなく、大量の状態データの保存を停止できるようにイーサリアムノードをアップグレードするために使用できるデータ構造です。

ステートレス性

ヴァークル・ツリーは、ステートレスなイーサリアムクライアントへの道のりにおける重要なステップです。ステートレスクライアントとは、受信したブロックを検証するために状態データベース全体を保存する必要がないクライアントのことです。ステートレスクライアントは、ブロックを検証するためにイーサリアムの状態のローカルコピーを使用する代わりに、ブロックとともに到着する状態データの「ウィットネス」を使用します。ウィットネスとは、特定のトランザクションセットを実行するために必要な状態データの個々の断片の集合であり、そのウィットネスが本当に完全なデータの一部であるという暗号証明です。ウィットネスは、状態データベースの「代わり」に使用されます。これが機能するためには、バリデータが12秒のスロット内で処理するのに間に合うようにネットワーク全体に安全にブロードキャストできるように、ウィットネスが非常に小さくなければなりません。現在の状態データ構造は、ウィットネスが大きすぎるため適していません。ヴァークル・ツリーは、小さなウィットネスを可能にすることでこの問題を解決し、ステートレスクライアントへの主要な障壁の1つを取り除きます。

イーサリアムクライアントは現在、状態データを保存するためにパトリシア・マークル・トライ（Patricia Merkle Trie）として知られるデータ構造を使用しています。個々のアカウントに関する情報はトライの葉（リーフ）として保存され、単一のハッシュが残るまで葉のペアが繰り返しハッシュ化されます。この最後のハッシュは「ルート」と呼ばれます。ブロックを検証するために、イーサリアムクライアントはブロック内のすべてのトランザクションを実行し、ローカルのステート・トライを更新します。ブロック・プロポーザーと検証ノードが行った計算に違いがあれば、ルートハッシュが完全に異なるものになるため、ローカルツリーのルートがブロック・プロポーザーによって提供されたものと同一であれば、ブロックは有効と見なされます。これに関する問題は、ブロックチェーンを検証するために、各クライアントがヘッドブロックといくつかの過去のブロックのステート・トライ全体を保存する必要があることです（Gethのデフォルトでは、ヘッドから128ブロック前までの状態データを保持します）。これにはクライアントが大量のディスク容量にアクセスできる必要があり、安価で低電力のハードウェアでフルノードを実行する際の障壁となります。この解決策は、完全な状態データの代わりに共有できるデータへの小さな「ウィットネス」を使用して要約できる、より効率的な構造（ヴァークル・ツリー）にステート・トライを更新することです。状態データをヴァークル・ツリーに再フォーマットすることは、ステートレスクライアントに移行するための足がかりとなります。

ウィットネスとは何か、なぜ必要なのか？

ブロックを検証するということは、ブロックに含まれるトランザクションを再実行し、イーサリアムのステート・トライに変更を適用し、新しいルートハッシュを計算することを意味します。検証済みのブロックとは、計算された状態ルートハッシュがブロックとともに提供されたものと同じであるブロックのことです（これは、ブロック・プロポーザーが主張通りに計算を本当に実行したことを意味するためです）。現在のイーサリアムクライアントでは、状態を更新するにはステート・トライ全体にアクセスする必要がありますが、これはローカルに保存しなければならない大規模なデータ構造です。ウィットネスには、ブロック内のトランザクションを実行するために必要な状態データの断片のみが含まれています。バリデータは、それらの断片のみを使用して、ブロック・プロポーザーがブロックのトランザクションを実行し、状態を正しく更新したことを検証できます。ただし、これは、各ノードが12秒のスロット内で安全に受信して処理できるように、ウィットネスがイーサリアムネットワーク上のピア間で十分に迅速に転送される必要があることを意味します。ウィットネスが大きすぎると、一部のノードがダウンロードしてチェーンに追いつくのに時間がかかりすぎる可能性があります。これは、高速なインターネット接続を持つノードのみがブロックの検証に参加できることを意味するため、中央集権化の要因となります。ヴァークル・ツリーを使用すれば、ハードドライブに状態を保存する必要はありません。ブロックを検証するために必要な「すべて」がブロック自体に含まれています。残念ながら、マークル・トライから生成できるウィットネスは大きすぎて、ステートレスクライアントをサポートできません。

なぜヴァークル・ツリーはより小さなウィットネスを可能にするのか？

マークル・トライの構造は、ウィットネスのサイズを非常に大きくします。12秒のスロット内でピア間に安全にブロードキャストするには大きすぎます。これは、ウィットネスが、葉に保持されているデータとルートハッシュを接続するパスであるためです。データを検証するには、各葉をルートに接続するすべての中間ハッシュだけでなく、すべての「兄弟（sibling）」ノードも必要です。証明内の各ノードには、トライの1つ上のハッシュを作成するために一緒にハッシュ化される兄弟があります。これは大量のデータです。ヴァークル・ツリーは、ツリーの葉とルートの間の距離を短くし、ルートハッシュを検証するために兄弟ノードを提供する必要性を排除することで、ウィットネスのサイズを縮小します。ハッシュスタイルのベクター・コミットメントの代わりに強力な多項式コミットメントスキームを使用することで、さらに高いスペース効率が得られます。多項式コミットメントにより、証明する葉の数に関係なく、ウィットネスを固定サイズにすることができます。

多項式コミットメントスキームの下では、ウィットネスはピア・ツー・ピアネットワーク上で簡単に転送できる管理可能なサイズになります。これにより、クライアントは最小限のデータ量で各ブロックの状態変化を検証できます。

ウィットネスのサイズは、含まれる葉の数によって異なります。ウィットネスが1000個の葉をカバーすると仮定すると、マークル・トライのウィットネスは約3.5MBになります（トライが7レベルであると仮定）。ヴァークル・ツリー内の同じデータのウィットネス（ツリーが4レベルであると仮定）は約150kBになり、約23分の1のサイズになります。このウィットネスサイズの縮小により、ステートレスクライアントのウィットネスは許容できるほど小さくなります。多項式ウィットネスは、使用される特定の多項式コミットメントに応じて0.128〜1kBになります。