オーバーレイを使用してイーサリアム状態ツリーの形式を変更する

編集者注: この記事は以下から引用しましたイーサリアム愛好家 (ID: ethfa​​ns)編集者注: この記事は以下から引用しました

イーサリアム愛好家 (ID: ethfa​​ns)

アカウントとコントラクトがデータを保存する方法は、イーサリアムに影響を与える多くの問題の 1 つです。イーサリアム プロトコルは、マークル パトリシア ツリー (MPT、マークル パトリシア ツリー) を使用してアカウントと契約データを整理します。このデータ構造は理論上はうまく機能しますが、実際には解決するよりも多くの問題が発生します。コア開発者たちは、このデータ構造をバイナリ ツリーに置き換えたいと何年も議論してきましたが、この記事では、この問題に対する私の見解と、この変換を実現する方法について説明します。

背景

私が提案するアプローチには、ネットワークが両方のツリー構造を維持する移行期間が含まれます。この利点は、ツリー構造の変換プロセスがチェーンの動作に影響を与えず、すべてのアカウントが確実にバイナリ形式に変換されることです。

背景

現在、イーサリアムの状態ツリーは 16 進数です。 Hex は、各ノードに 16 個の子ノードがあることを意味します。理論的には、これは問題ありません。子が増えると、すべてのデータを保存するために必要な「レベル」（つまり、木の高さ）が少なくなるからです。

画像の説明

- 図 1. 値 v が対応するキー 0xaa にどのように格納されるかを示す 16 進ツリーの例。このツリーのキーの長さはわずか 2 バイトで、0xaa に沿ったサブツリーのみが表されます。簡潔にするために、無関係なサブツリーは「...」に置き換えられます-

上の写真の木は非常に短く、幅が広いことがわかります。同じキーと値のペアが与えられた場合、次の図はバイナリ ツリーの格納状況を示しています。 170 は二分木では 10101010 として表されます。

画像の説明

図からわかるように、バイナリ ツリーはより深く、より狭くなります。

イーサリアムでは、各ブロックには stateRoot フィールドが含まれます。これは、ブロックが処理された後のイーサリアムのグローバル状態を表す MPT のルート ハッシュ値です。一般に、このハッシュ値は、ルートノードの16個の子ノードのハッシュ値のリストをハッシュすることによって取得されます。これらの子ノードのハッシュ値は、子の 16 個の子ノードのハッシュ値のリストをハッシュするなどして取得されます。

パッケージ化されたトランザクションが新しいブロックを生成するたびに、マイナーはアカウント ツリーを更新し、ルート ハッシュを再計算します。ルート ハッシュは新しいブロックの stateRoot フィールドに保存され、新しいブロックが合意されます。

画像の説明

ここに問題があります。すべてのノードをハッシュする場合、ルート ハッシュの再計算に時間がかかりすぎるため、ルート ノードのハッシュを計算するために、マイナーはデータベースから兄弟ハッシュ (兄弟ハッシュ) を取得します。後者 (マイナーがデータベースから兄弟ハッシュを取得する) は前者 (マイナーがデータベースからすべてのリーフ ノードを取得してハッシュする) ほど時間はかかりませんが、この操作には依然として時間がかかります。各ハッシュをデータベースから取得する必要があるためです。

16 進ツリーでは、通常、各レベルで 15 個の兄弟ハッシュ値を取り出す必要があります。上記で構築した例 (図 1) では、(ルート ハッシュの再計算に) 30 個のハッシュが必要になります。

バイナリ ツリーは少し深くなりますが、各レベルで必要な兄弟ハッシュは 1 つだけです。上の例 (図 2) では、必要なハッシュは 8 つだけです。実際にはバイナリ ツリーの方が優れているのはこのためです。

最初のレベルのタイトル

残念ながら、バイナリ ツリーへの変換は簡単ではありません。変換するデータが多すぎるため、変換の実行には 15 秒のブロック生成時間以上かかります。

さらに、あなたが 5000 ページの本を翻訳していると想像してください。著者はストーリーにいくつかの変更を加え、その変更はあなたがすでに翻訳したページに影響を与えると言い続けます。その場合、プロセスは終わりがありません。ステート ツリーの形式の変換も同じ問題です。おそらく、アドレスの形式変換が完了したばかりで、ユーザーがそのアドレスを使用する (つまり、アドレスの状態が更新される) 場合、最初から変換し直す必要があります。 (アドレス更新の状態は状態ツリー全体にも影響するため)。

副題

ステップ 1 - 変換

この方法では、ブロックの高さが H1 の場合、状態ルートが 2 つ存在する必要があります。1 つは「基本層」の 16 進状態ルート、もう 1 つは「オーバーレイ層」の 2 進ツリー状態ルートです。

画像の説明

16 進ツリーは読み取り専用になるため、状態の更新はオーバーレイ ツリー上で行われます。

トランザクションがアカウントを読み取るか更新するとき、システムは最初にオーバーレイ ツリーを検索します。アカウントがオーバーレイ ツリーで見つからない場合は、古い 16 進ツリーで値が検索されます。

副題

ステップ 2 - ベースツリーの切り替え

画像の説明

- 図 5. 変換の第 2 段階では、マイナーはブロック ヘッダー内の 16 進ルートを変換されたバイナリ ツリーのルートに置き換え、準備ができていることをネットワークに通知します -

十分な数のブロックが変換されたバイナリベースツリーのルートに同じ値を与える場合、ほとんどのマイナーが変換を完了し、変換されたツリーを承認したことを意味します。その後、結合プロセスが開始されます。 (翻訳者注: 今回のマージは、読み取り専用のバイナリ ベース ツリーと読み取り/書き込み可能なバイナリ カバー ツリーに対するものです)

マージ プロセスは継続的に進行します。新しいブロックが生成されるたびに、n 個のキーがオーバーレイ ツリーから削除され、バイナリ ベース ツリーに再挿入されます。このプロセスは、すべてのキーがオーバーレイ ツリーから削除されるまで続きます。このステップに到達すると、ブロック ヘッダーはオーバーレイ ステート ツリーのルートを保持しなくなります。

次のステップ

副題

次のステップ