イーサリアムコア開発者：MPT 16進ツリーは置き換えられる

前面に書かれている内容:

5,000 ページの本を翻訳していると想像してください。著者が何度も電話をかけてきて、すでに翻訳したページに影響するストーリーの調整を行ったと伝えてきます。このようなことが延々と続く可能性があります。これは、現在使用されている MPT 16 進ツリーからバイナリ ツリー構造への移行において Ethereum が直面しているジレンマと似ています。これに対して、イーサリアムのコア開発者であるギヨーム・バレ氏は、3つのステップを経て、この変換作業を数日程度で完了できるソリューションを提案しました。

(写真提供: tuchong.com)

この提案に関して、イーサリアムの共同創設者であるヴィタリック氏は次のようにコメントした。

「これは Ballet による重要な研究基盤であり、イーサリアムをステートレスフレンドリーにすると同時に、プロトコルを大幅に簡素化する機会を創出します。今後数か月でイーサリアム 1.x 開発者によるさらに素晴らしい仕事と成果が期待されます。」

翻訳は次のとおりです。

イーサリアムに影響を与える多くの問題の 1 つは、アカウントと契約データの保存方法であり、イーサリアムが現在選択している構造は、マークル パトリシア ツリー (略して MPT) と呼ばれます。理論的には非常に理にかなっていますが、実際には解決するよりも多くの問題を生み出します。何年もの間、コア開発者はバイナリツリーへの移行について議論してきました。この記事では、この問題についての私の考えを説明し、解決策を提示します。

提案されたプロセスでは、両方のツリー構造が存在する移行期間が導入されます。これの利点は、ツリー構造の変換中にメイン チェーンが動作し続けることができ、すべてのアカウントがバイナリ ツリー形式に変換されることが保証されることです。

背景

現在、Ethereum アカウントは 16 進ツリーに保存されています。いわゆる 16 進数は、ノードに 16 個の子ノードがあることを意味します。これは、すべてのデータを保存するために必要な「ステージ」が少なくなることを意味するため、理論的には良いことです。

たとえば、キーと値のペア (170, v) を 16 進ツリーの形式で表すと次のようになります。 16 進数では、170 は 0xaa として表されるため、必要なレイヤーは 2 つだけです。1 つは最初の a 用、もう 1 つは 2 番目の a 用です。

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

この木は非常に浅く、幅が広いことに注意してください。次に、同じキーと値のペアの次のバイナリ ツリー表現と比較されます。 2進数では、170 は 10101010 と表されます。

図 2: 図 1 と同じキーと値のペアがバイナリ ツリーとして保存されています。簡潔にするために、無関係なサブツリーは「...」と表記されます。

この木ははるかに深くて狭いことがわかります。

Ethereum では、各ブロックに MPT ルートのハッシュである stateRoot フィールドが含まれています。要約すると、このハッシュは、ルートの 16 個の子のハッシュ リストをハッシュすることによって取得されます。これらのサブハッシュ リストはそれぞれ、そのサブハッシュ リストのハッシュであり、以下同様に続きます。

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

図 3 ブロック ヘッダーの状態ルート フィールドは、16 進ツリーのルートを指します。

ここで問題が発生します。すべてのノードをハッシュしてハッシュ ルートを再計算すると時間がかかりすぎるため、ルート ノードを計算するために、マイナーはデータベースから兄弟ハッシュを取得します。データベースからすべてのサブリーフを取得してツリー全体をハッシュするのにそれほど時間はかかりませんが、この操作には依然としてかなりの時間がかかります。これは、各ハッシュをデータベースから取得する必要があるためです。

16 進ツリーでは、通常、各ステージで 15 個の兄弟ハッシュが取得されます。上記の例では、ハッシュは 30 個になります。

さらに深く考えると、バイナリ ツリーではステージごとに 1 つの兄弟ハッシュのみが必要です。上記の例では、ハッシュは 8 つだけです。これが、実際にはバイナリ ツリーの方が優れている理由です。

被覆変換法

残念ながら、Ethereum を 16 進ツリーからバイナリ ツリーに切り替えるのは簡単な作業ではありません。変換する必要があるデータが大量にあるため、変更を実行するのに 15 秒のブロック時間よりも長い時間がかかります。

さらに、5,000 ページの本を翻訳していると想像してください。著者が何度も電話をかけてきて、すでに翻訳したページに影響するストーリーの調整を行ったと伝えてきます。このような状況は延々と続く可能性があります。

これは、ユーザーがすでに変換されたアドレスを更新できるため、変換プロセスを最初からやり直す必要があるという、Ethereum が現在抱えている問題です。

この問題に対する提案された解決策は、ベースツリーがバイナリツリーに変換されるまで、状態に対するすべての変更を格納するオーバーレイバイナリツリーを 16 進ツリーの上に配置する移行期間を設けることです。

この移行は次の 3 つのステップで行われます。

ステップ1 - 変換

このアプローチでは、ブロックの高さ H1 で、ブロックに 2 つの stateRoots (「ベース」16 進ツリー用と「カバー」バイナリ ツリー用) があることが決定されます。

図 4: 遷移中、ブロックには 2 つの状態ルートがあります。1 つは従来の 16 進ツリーの読み取り専用ルートであり、もう 1 つは「オーバーレイ」バイナリ ツリーのルートです。

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

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

同時に、バックグラウンドで 16 進ツリーが変換されています。すべての変更はトップツリーに保存されるため、心配することなく挿入できます。

ステップ2 - 基底変換

バックグラウンド変換プロセスが完了すると、マイナーは読み取り専用の 6 進木ベース ルートを変換結果に置き換えることで、切り替えの準備ができたことを通知します。ステータスの読み取りおよび書き込み操作は手順 1 と同じです。

図 5: 変換の第 2 フェーズでは、ブロック ヘッダーは 16 進数のベース ルートを 2 進数の変換ベース ルートに置き換えて、準備が完了したことをネットワークに通知します。

十分に大きなブロックのシーケンスが変換されたベースルートに対して同じ値を持つ場合、大多数のマイナーが変換を完了し、変換されたツリーがどのようになるかについて合意に達したことを意味します。次に、マージプロセスに入ります。

ステップ3 - 2つのツリーを結合する

マージ プロセスは段階的に実行されます。新しいブロックが生成されるたびに、n 個のキーがオーバーレイから削除され、ベース ツリーに再挿入されます。このプロセスは、オーバーレイからすべてのキーが削除されるまで続きます。この段階で、オーバーレイ状態ルートはブロック ヘッダーから削除されます。

さらに、トランザクションがオーバーレイ ツリーにあるキーへの書き込みを実行すると、そのキーはオーバーレイ ツリーから削除され、ベース ツリーに直接書き込まれます。

次のステップ

変換を完了するのに必要な時間を見積もるために、予備的なプロトタイプを作成しました。全体のプロセスは妥当な時間（およそ数日）内に完了できると考えています。アルゴリズムが改善されたら、詳細を投稿します。

謝辞

この提案は、Alexey Akhunov、Vitalik Buterin、Anna George、Sina Mahmoodi、Tomasz Stanczak、Martin H. Swende からの貴重なコメントの恩恵を受けました。

関連ディスカッション: https://ethresear.ch/t/overlay-method-for-hex-bin-tree-conversion/7104