メインコンテンツへスキップ

ページの最終更新日時: 2024年2月12日

バークルツリー

バークルツリーはデータ構造であり、「ベクトルコミットメント」と「マークルツリー」を組み合わせた造語です。イーサリアムノードでは、アップグレードにより導入される予定です。バークルツリーを採用することで、ブロックの検証機能はそのままに、大量の状態データを保存する必要がなくなります。

ステートレス

バークルツリーは、ステートレスなイーサリアムクライアントの実現に欠かせない重要なステップです。 ステートレスクライアントは、受信したブロックを検証するために、状態データベース全体を格納する必要がありません。 クライアントがローカルに保存しているイーサリアムの状態のコピーを使用してブロックを検証する代わりに、ブロックに含まれる状態データの「ウィットネス」を使用します。 この「ウィットネス」は、特定の一連のトランザクションを実行するために必要な状態データの個々の部分を集めたもので、データ全体の一部であることを示す暗号学的証明になります。 このウィットネスを、状態データベースの代わりに使用します。 ネットワーク全体に安全にブロードキャストするには、バリデータが12秒のスロット内に処理できる必要があります。そのためには、ウィットネスが非常に小さくなければなりません。 しかし、現在の状態データの構造では、ウィットネスが大きすぎるため、適していません。 バークルツリーは、小さなウィットネスを可能にすることで、この問題を解決します。これにより、ステートレスクライアントを実現するための、1つの大きな障害を克服することができます。

ウィットネスの説明とその必要性

ブロックの検証では、ブロックに含まれるトランザクションを再実行し、その変更をイーサリアムの状態ツリーに適用することで、新しいルートハッシュを計算します。 検証されたブロックでは、その計算された状態ルートのハッシュがブロックで提供されたものと一致します。つまり、ブロックの提案者が本当にルートハッシュの計算を行ったことが確認できます。 現状のイーサリアムクライアントで状態を更新するには、状態ツリー全体にアクセスする必要があり、この巨大なデータ構造がローカルに保存されていなければなりません。 ウィットネスは、ブロック内のトランザクションを実行するために必要な状態データのフラグメントのみを含みます。 バリデータは、このフラグメントを使用して、ブロック提案者がブロックトランザクションを正しく実行し、状態が正常に更新されたかどうかを検証できます。 ただし、ウィットネスが各ノードにおいて12秒間のスロット内で安全に受信、処理されるためには、イーサリアムネットワーク上のピア間で十分な速度で転送する必要があります。 ウィットネスが大きすぎると、一部のノードにおいて、それをダウンロードしてチェーンを最新の状態を維持するのに時間がかかりすぎる可能性があります。 これでは、高速インターネット接続を持つノードのみがブロックの検証に参加できることになり、中央集権的な影響力を高めてしまいます。 バークルツリーを使用することで、状態をハードウェアドライブに保存する必要がなくなります。 つまり、ブロックを検証するために必要なすべてがブロック内に含まれます。 残念ながら、マークルツリーから生成されるウィットネスは大きすぎるため、ステートレスクライアントをサポートできません。

バークルツリーが小さなウィットネスを可能にする仕組み

マークルツリーの構造では、ウィットネスのサイズが非常に大きくなるため、12秒間のスロット内では、ピア間で安全にブロードキャストすることができません。 これは、ウィットネスがリーフが持つデータからルートハッシュへ接続するパスであるためです。 データを確認するには、各リーフからルートに接続するための全ての中間ハッシュだけでなく、全ての「兄弟」ノードのハッシュを持っている必要があります。 証明内にある各ノードには、ツリーの一段階上へのハッシュを作成するためにハッシュされる兄弟ノードがあります。 これは非常に大きなデータになります。 バークルツリーは、ツリーのリーフとルートの距離を短縮し、ルートハッシュを検証するために兄弟ノードを提供する必要性をなくすことで、ウィットネスのサイズを削減します。 また、ハッシュ形式のベクトルコミットメントの代わりに強力な多項式コミットメント機構を利用することで、スペース効率がさらに向上します。 多項式コミットメントにより、ウィットネスが証明するリーフの数に関係なく、サイズを固定にすることができます。

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

バークルツリーの構造

バークルツリーは、(key,value)のペアで構成されたデータ構造です。キーは、31バイトのステムと1バイトのサフィックスで構成されています。 これらのキーは、拡張ノードと内部ノードに編成されます。 拡張ノードは、1つのステムを表すノードです。256個の子ノードがあり、それぞれ異なるサフィックスを持っています。 内部ノードも256個の子ノードを持っていますが、他の拡張ノードになることもあります。 バークルツリーとマークルツリー構造の主な違いは、バークルツリーの方がはるかにフラットなことです。 つまり、リーフとルートを結ぶ中間ノードが少ないため、証明を生成するために必要なデータが小さくなります。

バークルツリーの構造についての詳細(opens in a new tab)

現在の進行状況

バークルツリーのテストネットはすでに稼働していますが、バークルツリーをサポートするために必要なクライアントの更新はまだたくさん残っています。 コントラクトをテストネットにデプロイしたり、テストネットでクライアントを実行したりすることで、開発を進めるお手伝いができます。

ビバリーヒルズ・バークルテストネットの探索(opens in a new tab)

Guillaume BalletによるCondrieuバークルテストネットの説明をご覧ください(opens in a new tab) (Condrieuテストネットはプルーフ・オブ・ワークでしたが、現在はKaustinenテストネット(opens in a new tab)に置き換えらていることにご注意ください)。

参考文献

この記事は役に立ちましたか?