背景と動機

MPT の改善について話す前に、まずこの調査を実施した背景について話しましょう。

私は博士号取得を目指して勉強しており、パブリックチェーンの設計を行っています。このパブリック チェーンの中核となるコンセンサス アップグレードである有用なプルーフ オブ ワークに加えて、もう 1 つの重要なタスクは、ETH 互換のスマート コントラクト システムを実装することです。現在、Python バイトコードに基づいた仮想マシンを実装し、それをブロックチェーン コントラクト システムに統合し、驚くべきことにイーサリアム RPC と互換性を持たせました。 Python を使用して、テスト用の ERC20 標準に準拠するスマート コントラクトを構築しました。当然、コントラクト実行の下位レベルで数千万のユーザーを伝送できる KV データ メカニズムを実装する必要があります (Solidity のマッピングと同様)。アカウントの下に各トークンの数を保存するために使用されます。そのようなアカウントは数億ある可能性があります)。

次に、パブリックチェーン設計の仕事内容は当然MPTやトライなどの概念に触れます。 Ethereum、Threetrees、trie、MPTなどの設計を参考にしました。

ボトルネックを見つける

幸いなことに、MPT を呼び出すスマート コントラクトを実装する準備が整う前に、AWS サーバー上で単純な MPT ツリー ベンチマーク プログラムを突然実行しました。 Trie と MPT を使用して 1 億 KV のデータ量を挿入しようとした後、MPT ツリーのパフォーマンスが実際には非常に低いという結果が得られ、非常に驚​​きました。

次のコードを実行すると、1,000 万の KV キーと値のペアを Rocksdb に挿入するのに、Trie の場合は数分、MPT の場合は数時間かかることがわかります。テスト データの規模を 1 億件に増やすと、MPT インサーターの実行に数日かかります。これは、ブロックチェーンが MPT データ構造を使用してスマート コントラクトを実行する場合、速度も大幅に制限されることを意味します。

MPT データ構造の使用によって生じるオーバーヘッドは、スマート コントラクトの実行速度を低下させるだけでなく、ブロックチェーン ノードの同期速度も低下させることが実験により証明されています (帯域幅が十分にある場合でも、他のノードからデータをダウンロードして再構築する場合)。ノードの場合も数日かかる必要があります)。しかし、イーサリアムのデータ構造設計は変更が難しいため、たとえ「より高速な」プログラミング言語で書き換えたり最適化したとしても、基礎となるデータ構造が更新されなければ、ブロックチェーンの性能限界を突破することは困難になります。

  test_mpt_write.py

  test_mpt_write.py

私が初めてコードの書き方を学んだとき、教師が「プログラム = アルゴリズム + データ構造」という基本原則を教えてくれたことを今でも覚えています。データ構造を制限すると、必死にアルゴリズムを最適化しても（これには数年間の学術的努力が必要であり、多くの場合、改善はほぼ不可能です）、現在のパフォーマンスの限界を突破することは困難になります。データ構造。したがって、非常に学術的な改善計画であり、よりパフォーマンスの高い MPT 代替アルゴリズムを探し、研究には数年かかる場合があります。この方向に取り組んでいる先駆者として、Verkle Tree は多項式手法を使用してブロックチェーン データ構造を最適化します。さらにユニークでシンプルなアイデアを試してみます。

第一原理思考を使えばMPTは使えないのでしょうか？ MPT をバイパスして Trie 上でスマート コントラクトを直接実装できれば、MPT によって生じるオーバーヘッドはなくなります (馬一龍の第一原則、存在しないものにはパフォーマンスのオーバーヘッドはありません)。

その代償として、新しく設計されたソリューションは既存の MPT と直接互換性がない可能性がありますが、イーサリアム RPC インターフェイスは変更されていないため、Etherjs や MetaMask など、多くの既存のイーサリアム インフラストラクチャを再利用できます。 MPT のバイパスは内部データ構造の最適化に属し、ブロックチェーンのパフォーマンスを自由に探索します。

前提知識

Rocksdb と Trie

Trie 辞書ツリーは、大学の教科書で説明されている高度なツリー データ構造です。Xiao 先生のビデオでは、MPT は Trie 辞書ツリーに基づいて構築されています。 Trieの実装環境はメモリ上にあると考えられます。

ただし、私たちのエンジニアリングでは、ハードディスク上にデータを永続化する必要があるため、Trie を直接使用して製品を実装することはできません。そのため、通常は Rocksdb に基づいて MPT ツリーを実装します。

Rocksdb は、leveldb をベースにした FB のオープンソース フォークであり、底部で LSMT を使用します (論文「ログ構造化マージ ツリー」を参照)。抽象的な観点から見ると、Rocksdb は最適化された永続的な辞書ツリーと考えることができます。

Rocksdb の基本的な使用法は非常に簡単で、主に Get Put と Prefix Iterate という 3 つの基本操作を使用します。

ステートマシン

ステート マシンは、ブロックチェーンをモデル化するためによく使用されるツールです。これは非常に単純です。元の状態に入力を追加して、新しい状態を取得します。

イーサリアムのグローバル状態は、例えばブロック 1 では、すべてのスマート コントラクトの KV 値がグローバル状態として理解され、ブロック内のすべてのトランザクションが EVM によって実行されます。 Mint コントラクト呼び出しなどの入力により、ブロック 2 でユーザーの Balance およびコントラクトの Total 変数が 1000 に変更されます。

見落とされやすいステートマシンの概念は状態遷移関数と呼ばれるもので、入力が不当な場合には入力情報を拒否するというルールが定義されています。たとえば、マイナスの金額を他の人に送金しようとしても、そのようなトランザクションは実行されません（もちろん、バグのあるスマートコントラクトはそのようなトランザクションを受け入れることができます。ETHでは、状態遷移機能がチューリングを通じて自動的に実行できます） -完全な言語の定義)。

MPT の概要

おそらくイーサリアムの 3 つのツリー、つまりトランザクション ツリー、ステータス ツリー、レシート ツリーについて聞いたことがあるでしょう。これらはすべて MPT ツリーであり、フルネームは Merkle Patricia Tries です。その中で、ステート ツリーはおそらく MPT データ構造を使用するための最良の使用例です。詳しくはシャオ先生の動画解説をご覧ください。

MPT ツリーは Trie データ構造に基づいており、マークル ツリーと同様にすべての状態データをルート ハッシュに計算し、それをイーサリアム ブロック ヘッダーに配置できます。 Ethereum ブロック ヘッダーには MPT ツリーの 3 つのルート ハッシュがあり、通常これを 3 つのツリーと呼びます。

グローバル状態のルートをブロックヘッダーに配置しないことはできますか?はい、トランザクションはビットコイン ブロックに配置され、トランザクションのマークル ルートがブロック ヘッダーに配置されます (マークル ツリーが使用されますが、MPT は使用されません)。しかし、ビットコインにはイーサリアムのようなスマートコントラクトがなく、グローバルステートの概念もありません。イーサリアムが最初にスマート コントラクトを使用してブロックチェーンを設計したとき、ビットコインの 1 M ブロック設計と UTXO を放棄し、MPT データ構造とアカウント モデルを選択し、Gas を使用してダウンタイムの問題を解決し、グローバルな運用中のスマート コントラクトの要件を満たしました。州。

では、イーサリアムで MPT を使用する目的は何でしょうか?

  1. ブロック ヘッダーのマークル ルートを通じて、ブロックチェーンの対応する状態を見つけます。

  2. 重複データが占めるスペースを節約します。

  3. 正しい状態はルート ハッシュによって確認できます。

最初の点は厳格な要件です。EVM の実行中にさまざまな状態を読み取る必要があります。ビットコイン UTXO と同様の設計パターンが使用される場合、特定のユーザーのアカウント残高状態を取得するには、多くのブロックをトレースする必要があります。 MPT を使用すると、ニーズを十分に満たすことができます。

ポイント 2、MPT はスペースを節約し、ブロックチェーンの状態は巨大な辞書とみなすことができます。各ブロックでは、キーのごく一部のみが更新され、ほとんどのキーは元の値を維持します。 MPT ツリーを使用すると、各ブロック内の変更されていない状態をコピーすることなく、更新する必要があるキー値のみを更新できます。

ポイント 3: MPT の利点は、ルート ハッシュによってアクセスされる状態キー値を使用してグローバル状態の検証が完了していることです。これは、MPT ツリーの作成に時間がかかる主な理由でもあります。 MPT が使用されない場合でも、ノードはブロック同期中にデータの整合性を検証できます。

MPT を使用せずにポイント 1 と 2 を完了することで、MPT のオーバーヘッドを回避できます。したがって、ブロックチェーンのステータス データを保存するには、Trie (Rocksdb として理解できます) に基づいたソリューションを設計する必要があります。

デザイン

私たちは主に、オンチェーンのステータスを保存するための Trie ベースのソリューションを設計します。第一原則によれば、MPT データ構造がない場合、MPT の実行にシステム オーバーヘッドは必要ありません。 Trie ベースのスマート コントラクト システムが正しく実装され、実行できれば、最適化は完了したことになります。実際には、Rocksdb は Trie として考えることができます。簡単に理解すると、これは高性能の KV データベースです。

KV データベースのキー値として [globalstate as prefix_contract address_variable name_block height_block hash] を次の形式のように使用します。このうち、0x1はコントラクトアドレス、Totalは変数名、1はブロック高さ、ABC1234はブロックハッシュ値です(後述します)

グローバルステート_0x1_合計_1_abc1234

Ethereum Solidity では、変数はメモリ、ストレージ、およびコールデータとして定義できます。ストレージ タイプはグローバルな状態で保存されるため、主にストレージ タイプに焦点を当てます。単純な変数に加えて、マッピングも考慮します。ブロックチェーン上のユーザーの大きさはグローバルであるため、非常に大規模な KV マッピングが存在します。さらに、Array などのデータ型を単純なデータ構造として扱い、Rocksdb の Json に直接格納します。コードを作成するときは、当然のことながら、KV データ構造内の値データの大きさを推定して、適切な保存方法を選択する必要があります。

コントラクトストレージ状態変数

MPT を使用せずに MPT の 1 番目と 2 番目の設計目標を達成するにはどうすればよいでしょうか?

ERC20 コントラクトに変数 Total があるとします。この変数は、トークンの総数が増加する (Mint) か減少する (Burn) 場合にのみ変化しますが、ユーザー A がユーザー B に送金する (Transfer) 場合、Total の値は残ります。絶え間ない。

簡単にするために、コントラクトのアドレスが 0x1 であると仮定します。ブロックの高さが 1 の場合、コントラクトの所有者は Mint 2000 を実行しました。高さ 2 ～ 8 のブロックでは、ユーザーは複数の転送を実行しました。高さは9です。

この時点で必要なのは、[globalstate_0x1_total_] というプレフィックスが付いたキーをデータベースにクエリすることだけです。現在の最新のブロックは 9 ですが、Total 変数はブロック 2 ～ 8 で変更されていないため、上記のクエリの最初の結果は [globalstate_0x1_total_1] の値となるため、Total 変数の最新の値である Total が見つかりました。ブロック 1 で変更された変数。

このとき、ユーザが９ブロック目と１１ブロック目でさらに２回ミントを実行したとする。ここで、次のキーがある場合の Rocksdb の機能を見つけます。

globalstate_0x1_total_1 : 2000

グローバルステート_0x1_total_9 : 4000

グローバル状態_0x1_合計_11: 6000

この場合、最初の検索結果は、最新のブロック 11 ではなく、常にブロック 1 になります。 Rocksdb のドキュメントからは検索結果の順序を変更するパラメーターがまだ見つかっていないため、100 などの大きな数値を使用してブロックの高さ (実際にはさらに大きくなります) を減算し、それをパディングするという小さなトリックを使用しました。ゼロが含まれるため、最新のブロックが検索結果の最初にランク付けされます。

グローバル状態_0x1_合計_089: 6000

グローバルステート_0x1_合計_091: 4000

グローバルステート_0x1_total_099 : 2000

ストレージマッピングタイプ

前に述べたように、マッピング データ構造のキーの大きさは膨大である可能性があるため、マッピング内の数万のキーの辞書 Json を文字列に変換することは不可能です。そうしないと、キーの追加や削除のコストがかかります。 、または値を変更するのは非常に危険です。

ユーザーのアドレスが 0x2 であると仮定して、以前のストレージ キーの形式をわずかに拡張します。

[グローバル状態_0x1_[バランス_0x2]_2] : 2000

ここでは先ほどの[変数名]を[変数名+マッピング辞書のキー]に展開しました。

上記のデータは、ブロック高さ 2 のユーザー 0x2 の残高が 2000 であることを表します。現在の残高をカバーする更新データがない場合、ブロック 2 のユーザーのデータが最新のステータスを表します。

グローバルステート_0x1_バランス_0x2_098 : 2000

グローバルステート_0x1_total_0x1_099 : 2000

ベリファイブロック

マークル ツリー ルートと同様、MPT ツリー ルートもグローバル状態の検証を表します。ブロック データの一貫性を確保できる限り、MPT を使用して Root をブロック ヘッダーに書き込む必要があるかどうかは設計上の選択です。

ブロックの設計にいくつかの改良を加え、ブロック ヘッダーに 2 つの本体が含まれるようにしました。1 つはトランザクション データ ブロック、もう 1 つはステータス更新データ ブロックです。

トランザクション データ ブロックには、すべてのトランザクションのハッシュが含まれています。マイナーまたはノードは、特定のブロック高さのグローバル状態から開始し、トランザクション データ ブロックで指定された順序ですべてのトランザクションを実行し、次のブロックのグローバル状態を取得できます。トランザクション量が多い場合は（トランザクションの順序が崩れるため）並列実行が難しくなるため、世界中のノードにすべてのトランザクションの実行を要求すると時間がかかります。

この目的を達成するために、すべてのトランザクションの実行後に更新されたグローバル状態キー値を含む状態更新データ ブロックを設計しました。多くのブロックの背後にあるノードの場合、仮想マシンを実行してすべてのトランザクションを実行するだけでなく、ステータスに応じてボディの内容を更新し、データベースにキー値を直接挿入して計算能力を節約することもできます。同期時間を短縮します。

もちろん、すべてのトランザクション更新を実行するために使用されるキー値は、ステータス更新ブロックに含まれる Diff とまったく同じである必要があります。そうでない場合、この新しいブロックは不正になります。

世界に 10,000 のノードがあると仮定します。サイコロを振ってトランザクションを実行する確率を 1% に設定すると、約 100 のノードがブロック間トランザクションを実行し、他のノードは接続ステータスの更新の内容に依存します。データブロックを作成すると、この領域がブロックチェーンシステムの多くのノードで繰り返される操作を保存できます。

成し遂げる

前回の設計が完了した後、私たちはすぐにこのアイデアの実装を開始しました。

まず、Python VM をブロックチェーン システムに統合しました。これは Python で実装された Python 仮想マシンであり、現在 PY 3.10 バイトコードと互換性があります。たとえば、スマート コントラクトが Python の構文の一部を使用できることを望んでいます。たとえば、必要なのは関数だけであり、開発者にはクラスを使用してほしくないため、現在すべての PY バイトコードを完全にはサポートしていません。

コンパイラに関しては、Solidity はソースコードを EVM バイトコードに変換するための専用コンパイラを開発する必要があります。 Python を使用すると、30 年の歴史を持つこの優れたインフラストラクチャ言語の助けを借りて、Python ソース コードを PY バイトコードに簡単に変換できます。ユーザーはコンパイル時間をほとんど気にしません。

VM コード リポジトリは次のとおりです。皆様のご意見をお待ちしており、潜在的なセキュリティ問題を修正していただけます。

リンク: https://github.com/EcoPoW/python_stf_vm 2 番目のステップでは、ERC20 の Python バージョンを開発しました。コードは常に更新されます。 Solidity とは異なり、変数の保存方法を識別するためにキーワードを使用しません。すべてのローカル変数はメモリ内にあり、状態の読み取りと書き込みには _get および _put グローバル関数を使用します。 リンク: https://github.com/EcoPoW/BitPoW/blob/master/contract_erc20.py

https://github.com/EcoPoW/BitPoW/blob/master/state.py

実装と改善

質問の提起から設計、コーディングの実装まで約 2 か月かかりました。

夏の間ずっと設計と実際のコーディングを行った後、MPT データ構造に依存せずに辞書ツリー Trie のみを使用する新しいスマート コントラクト システムを実行する準備が整いました (Github クローンを介してローカルでテスト ノードを実行してみることができます)。 MPT ベースのスマート コントラクト ストレージをバイパスするということは、十分な帯域幅があれば、1 億 KV のサイズのノードの同期時間を数日から数分に短縮できることを意味します。スマート コントラクトの実行効率も高速になり、CPU が消費する計算の多くは、マークル ツリーの構築に必要なハッシュ演算ではなく、バイトコードの実行に使用されるようになります。幸運なことに、プロジェクトでスマート コントラクトを実装する際、「業界標準」の設計に直接従うのではなく、最初に最適化と減算を試み、正しい「データ構造」を持つスマート コントラクト ブロックチェーンを取得できました。車の運転中のタイヤ交換にたとえられる Web2 製品とは異なり、Web3 ブロックチェーンはロケットの打ち上げに似ているからです。実行中のブロックチェーンに大幅な構造的な改善を加えるのは難しいため、私たちができるのは「次の」システムを改善し、オンラインに移行する前に十分な準備を整えることだけです。

現在、私たちが設計した BitPoW ブロックチェーンの Testnet 2 テスト ネットワークがデプロイされており、誰もが MetaMask を使用して RPC 経由でこのブロックチェーンに接続し、Python VM に基づく ERC20 転送を試すことができます。同時に、私たちにはまだやるべきことがたくさんあり、この新しいブロックチェーンインフラストラクチャを推進するにはコミュニティに依存する必要があります。

MPT を削除した後のパフォーマンス テストや、新しいスマート コントラクトと新しいチェーンのセキュリティ テストなど、これらの新しいコンセプト主導のテクノロジーの実装について学び、実際にテストすることを皆さんに歓迎します。

要約する

これまでのところ、MPT をバイパスし、Trie に直接基づいてスマート コントラクト ストレージ ソリューションを設計してきました。現在、実現可能性の証明として、この改善を Python vm ベースのブロックチェーンに実装しています。問題を発見して解決策を提案し、それをコードに実装するまでに約 3 か月かかりました。しかし、この研究でより重要なことは、多くの一般の人々と同様に、私たちも教室で MPT の知識を学んだ後、それ以上考えなかったということです。それを改善することです。解決策は複雑ではありませんが、練習と行動が必要です。解決策は複雑ではありませんが、練習と行動が必要です。実際に積極的に考えることによってのみ、インスピレーションを見つけてさらに革新することができます。この研究を支援してくれた LXDAO に非常に感謝しており、ブロックチェーンの最下位層に興味を持つコミュニティでもっと多くの友人に会えることを願っています。この業界はまだ初期段階にあり、インフラストラクチャは成熟には程遠いです。私たちはブロックチェーンの基礎知識の普及を促進し、より多くの人が技術革新の最前線に参加できるようにしたいと考えています。