Starknet の最新アップグレード (v0.13.2) Boltには、並列実行とブロック パッキングという 2 つの大きな変更点があります。それぞれ独立していますが、どちらの機能も、Ethereum によって暗号化され保護された高速で安価なブロック空間という目標に向けた推進力となっています。
並列実行により、競合のないトランザクション (つまり、同じ状態に触れないトランザクション) を同時に実行できます。並列実行を実装することで、Starknet などの L2 はリソース使用量を増やすことなく実行時間を短縮できます。つまり、ユーザーのトランザクション手数料が下がり、トランザクションの確認時間が大幅に改善されます。
ブロック パッキングにより、Ethereum L1 上の Starknet の blobspace の使用が最適化されます。ブロック パッキングにより、シーケンサーは 1 つの証明を生成して、複数の Starknet L2 ブロックを同時に検証できます。これにより、blobspace の使用が L2 ブロック生成の頻度から切り離され、証明検証コストが償却されます。どちらも Starknet シーケンサーの運用コストを削減し、ユーザーがトランザクションごとに支払う金額が少なくなります。
前述したように、Bolt により Starknet はより安価で高速になります。このレポートでは、並列実行とブロック パッキングに焦点を当てて Bolt アップグレードの詳細な分析を提供し、Starknet のパフォーマンスへの影響を探ります。
ロールアップは、計算をオフチェーンに移動することで、基盤となるレイヤー 1 (L1) ブロックチェーンをスケーリングすることを目的としたレイヤー 2 (L2) スケーリング ソリューションです。実行をオフチェーンに移動することで、ロールアップはスケーラビリティ (安価で高速なトランザクション) を最適化でき、L1 は L2 トランザクションのセキュリティを提供します。
ロールアップは「L1 からセキュリティを継承する」とよく言われます。これは基本的に、L1 によって提供されるコンセンサスとデータ可用性の保証を継承することを意味します。これに加えて、L1 はロールアップと L1 間の安全なブリッジという形でセキュリティ保証も提供します。
シーケンサーが L2 ブロックを L1 に公開すると、L1 はこの情報の可用性と順序付けを保証します。ここから、L2 ノードは、ノード実装によって記述されたチェーン導出と状態遷移に関するロールアップのルールとともに、この情報を使用して、信頼できる方法で正規の L2 チェーンを計算できます。
L1 と L2 間の安全なブリッジングを容易にするために、L1 は現在従っている L2 チェーンが正しく、不正な状態変更 (二重支払いなど) が含まれていないことの証明を必要とします。ロールアップで状態変更の有効性を証明する必要があるため、L1 は不正な状態に基づいてロールアップからの引き出しを承認しません。
ロールアップは、L1 への状態変更の有効性を証明する方法によって異なります。
ロールアップは、ベース レイヤーに、関係者が L2 状態を再構築するのに十分なデータも提供します。楽観的ロールアップでは、チャレンジャーが不正証明を計算できるように完全なトランザクション データを公開する必要がありますが、有効性ロールアップにはそのような要件はありません (有効性証明は正しい実行を保証します)。ただし、L1 に完全なトランザクション データを投稿することは、信頼の最小化の観点からは依然として有用です (信頼のない状態の再構築と許可のない引き出し)。
Starknet は、スケーラブルで透過的な知識の集合(STARK) を使用して状態変更の有効性を証明する有効性ロールアップです。Starknet の最新のアップグレード (コード名 Bolt) では、並列実行とブロック パッキングが追加されています。以降のセクションでは、この 2 つの機能の仕組みと、Starknet ユーザーにどのような改善をもたらすかについて説明します。
大まかに言えば、Bolt のアップグレードにより、Starknet の実行、証明、およびデータ可用性のメカニズムが変更されました。
Bolt のアップグレード前は、Starknet トランザクションはシーケンサーによって順番に (1 つずつ) 実行されていました。シーケンシャル実行はシンプルですが、非常に非効率的です。非効率的なのは、現代のコンピューターが提供する複数の独立した処理ユニットと、一連のトランザクションの並列化の可能性を活用していないためです。
並列化可能性は、特定のセット内のトランザクションがどれだけ独立しているかを示す尺度です。たとえば、次の 3 つのトランザクションのセットを考えてみましょう。
トランザクション1: アリスはボブに1 STRKを送りたい
トランザクション2: ケイトリンはダニーに100 ETHを送りたい
トランザクション3: ケイトリンはエラに100 ETHを送りたい
トランザクション 1 は、状態の別の部分 (アリスの残高) にアクセスしているため、トランザクション 2 および 3 から完全に独立しており、同時に実行できます。ただし、トランザクション 2 と 3 は同じ状態 (ケイトリンの ETH 残高) にアクセスしようとしているため、競合しています。これらのトランザクションを同時に実行すると、結果が競合することになります。
例を挙げると:
こうしたタイプの競合 (および緩和メカニズムの複雑な性質) を回避するために、Ethereum は順次実行を選択しました。ただし、順次実行によって複雑さが軽減され、セキュリティが向上する一方で、ハードウェアの使用効率が低下します。さらに悪いことに、ハードウェア設計の傾向から、今後数年間で順次実行の効率がますます低下することが予想されます。
図 4 は、過去 50 年間のハードウェア設計の傾向を示しています。重要なポイントは、シングルスレッド パフォーマンス (紫色の円) は 2000 年代半ばから横ばい状態にあるのに対し、論理コアの数はほぼ同時期に増加しているということです。このデータに基づいて、次の 2 つの結論を導き出すことができます。
ハードウェア設計者は、単一のユニットのパフォーマンスを向上させるのではなく、独立した処理ユニットを追加することでコンピュータ チップを拡張しています。
単一の処理ユニットのパフォーマンス向上に依存し続けるシステムでは、新しいハードウェアであってもパフォーマンスの向上が停滞します。
近年、トランザクションの競合を管理し、並列実行の正確性を保証するための洗練されたアルゴリズムが登場しています。Block-STM (Fikunmi らの論文に基づく) はそのようなアルゴリズムの 1 つであり、Starknet の新しい並列実行エンジンの中核部分を形成します。Block-STM アルゴリズムについては、後のセクションで分析します。
Starknet の SHARP (Shared Prover の略) は、検証コストを可能な限り削減するために、常に再帰証明を活用してきました。再帰証明は、本質的には「証明の証明」であり、1 つの証明が 1 つ以上の証明が正しいことを検証します。以下は、SHARP が再帰証明を生成する方法の概略です。
SHARP システムは、実行する一連のプログラム (「ジョブ」) を入力として受け取り、ジョブの実行証明を生成します。これらの「プログラム」は L2 ブロックであり、証明はトランザクションの正しさを証明します。
証明は別のプログラムに送信され、そのプログラムで証明が検証され、証明検証プログラムがジョブに変換されます。SHARP は新しいジョブを入力として受け取り、別の証明を生成します (この証明は、以前の証明の有効性を確認します)。
プロセス(証明→ジョブ→証明)は再開され、目標に到達するまで継続され、最終証明(元の証明の高度に圧縮されたバージョン)がL1に投稿される。
この設計では、主に次の 2 つの理由によりコストが大幅に削減されます。
証明システムは優れていましたが、コストをさらに節約する機会を逃していました。たとえば、各ジョブは単一の Starknet ブロックであり、これらのブロックはそれぞれ L1 で 1 つのブロブを占めるように設計されていました。その結果、以下に説明するように、特定の非効率性が生じました。
ブロック パッキングは、再帰証明のバイナリ ツリーを使用してこれらの問題に対処します。ブロック パッキングについては、この記事の後半で説明します。
前述のように、順次実行は非効率的であり (時間が経つにつれて非効率的になるだけです)、単純な並列実行では無効な結果が生成されます。ただし、実稼働の並列実行エンジンでは、一貫性のない結果を防ぐように配慮されています。
並列実行に対処するには、悲観的同時実行制御 (PCC)と楽観的同時実行制御 (OCC) という2 つのアプローチがあります。PCC と OCC はトランザクション処理ユニット (TPU) です。以下は、Block-STM と SVM: 並列実行エンジンの比較からのトランザクション処理ユニットの定義です。
TPU は通常、仮想マシン (VM) と連動していますが、VM とは別物です。EVM、SVM、MoveVM などのブロックチェーン VM は、高水準言語 VM です。通常、関心の対象となる TPU は、VM を包含します。TPU は、VM のインスタンスの作成と管理を含む、トランザクション実行パイプライン全体の管理を担当します。
悲観的同時実行制御は、実行されるトランザクション セット内の多くのトランザクションが競合する、つまり同じ状態になるという仮定に基づいて設計されています。PCC はこれらの競合を防止します。
競合を防ぐために、PCC では、トランザクションが読み取り/書き込み操作中にアクセスする状態の部分を事前に宣言する必要があります。トランザクション処理ユニットはこの情報を使用して、競合するトランザクションが (同時にではなく) 順番に実行されるようにトランザクションをスケジュールできます。一部の TPU では、この動作を強制するためにロックも使用されます (ロック (別名、ミューテックス) は、メモリ位置への同時アクセスを防ぐために使用されるメカニズムです)。
とはいえ、PCC ベースの実行には一定のトレードオフがあります。まず、アクセス リスト (トランザクションがアクセスするメモリ スロットを識別する) を提供する必要があるため、開発者のエクスペリエンスが低下し、適用可能な範囲が狭まります。次に、トランザクションのスケジュール設定によって、特に競合がない場合に、不要なオーバーヘッドが発生する可能性があります。
楽観的同時実行制御は、特定のセット内のトランザクションの多くは競合しない、つまり同じ状態に書き込まれないという前提で設計されています。そのため、OCC TPU は利用可能なすべてのリソースを使用してトランザクション セットを実行し、競合の検出のみを試みます。競合が検出されると、競合するトランザクションが実行され、セット全体が合格してコミットできるようになるまで再検証されます。
OCC TPU はスケジューリングによるオーバーヘッドが発生しないため、競合が少ない場合にパフォーマンスが向上する傾向があります。また、OCC ベースのトランザクション処理ユニットは、状態の依存関係を事前に知る必要がないため、開発者のエクスペリエンスが向上し、ユースケースの範囲が広がります。
ただし、一連のトランザクションの競合が非常に多い場合、OCC のパフォーマンスは PCC よりも悪くなります。並列実行に関する記事では、TPU 設計について (より詳細に) 取り上げ、OCC と PCC のアプローチを比較しています。
Starknet の新しい TPU は OCC アプローチを採用しています。具体的には、Block-STM アルゴリズムの実装です。Block-STM は、競合がないと仮定して、利用可能なすべてのリソースを使用してトランザクションを楽観的に実行し、実行後に競合するトランザクションが同時に実行されていないことを確認します。Starknet の新しいアーキテクチャについて詳しく説明する前に、いくつかの重要な定義を確認することが重要です。
txj
、両方のトランザクションが同じメモリ位置に書き込み、シリアル順序でtxj
がtxi
後にある場合にのみ、トランザクションtxi
に依存している (または依存している) と言われます。 txi
がtxj
の後にある場合、 txi
txj
に依存します。定義が終わったので、Block-STM がどのように機能するかについて説明します。
Block-STM への入力はトランザクションのキュー (順序付けられたリスト) であり、このリストは BLOCK と呼ばれることがよくあります。このリストは任意の順序で並べることができます。唯一の要件は、明確に定義された順序があることです。したがって、トランザクション{t0…tn}
を含むトランザクション セット T が与えられた場合、トランザクションは{t0 > t1 > t2 … > tn}
のように並べ替えられます (つまり、 t0
t1
よりも優先度が高く、 t1
はt2
よりも優先度が高いなど)。
実行プロセスの開始時に、実行セット E と検証セット V の 2 つのセットが作成されます。E はまだ実行されていないトランザクションを追跡し、V は実行されたがまだ検証されていないトランザクションを追跡します。各トランザクションには、実行回数 (および再実行回数) を追跡するためのインカネーション番号 n も関連付けられています。セットの初期状態は、E にすべてのトランザクションが含まれ、V は空です。つまり、 E = {t0,1 > t1,1 > t2,1 > … > tn,1}
かつV = {}
です。
これらの順序付けられたトランザクション セットでは、実行に使用される各スレッドが 3 段階のループを繰り返し実行します。
このステップでは、スレッドは V と E の両方をチェックします。両方が空で、トランザクションが実行されていない場合は、現在のトランザクション バッチは完全に実行されており、結果をストレージにコミットできます。
V または E のいずれかにトランザクションが含まれている場合、Block-STM は両方のトランザクション セットからインデックス (インカネーション番号ではない) が最も低いトランザクションを選択します。つまり、E に{t1,3 , t3,1 and t5,2}
が含まれ、V に{t0,1, t2,4, t4,3}
が含まれている場合、トランザクションt0
の検証タスクが次のタスクとして選択されます。
次のタスクが識別され選択されると、それが実行されます。このステップの最後に、アルゴリズムは Check Done に戻ります。このプロセスは、両方のトランザクション セットが空になるまで継続されます。
実行と検証中に何が起こるかを見てみましょう。
トランザクションの実行中、Block-STM アルゴリズムは、トランザクションごとに 2 つのセット (読み取りセット ( Ri,n
) と書き込みセット ( Wn,i
)) を作成します。読み取りセットには、トランザクションが実行中に読み取ったすべてのメモリ位置が含まれ、書き込みセットには、トランザクションが書き込んだすべてのメモリ位置が含まれます。実行中、トランザクションはマルチバージョン データ構造に書き込みを適用しますが、読み取りは少し微妙です。
Block-STM では、トランザクションがデータ構造から読み取る場合、優先度が最も低いトランザクションによって書き込まれた値のうち、優先度が高いものをチェックします。たとえば、 tx1
、 tx2
、およびtx7
すべてメモリ位置に書き込まれていて、 tx5
この位置から読み取る場合、 tx2
に対応するデータ構造のバージョンが読み取られます。
これは直列化可能性を強制するために行われます。 tx5
tx2
後、 tx7
前に実行されるため、 tx7 ではなくtx2
によって書き込まれた値を使用する必要があります。 この例では、 tx7
tx7
またはより優先度の高いトランザクションではなくtx5
tx2
書き込まれた値を読み取る必要があるため、再実行する必要があります。 単一バージョンのデータ構造が使用された場合、 tx2
によって書き込まれた値は使用できず、競合が確実に発生します。
検証タスクの場合、トランザクションの読み取りセットは、実行中に読み取られたメモリ位置の現在の値と比較されます。たとえば、 tx2
実行中にアカウント B を読み取る場合、検証中にアカウント B のメモリ位置が読み取られます (前に確立した読み取りの定義を念頭に置いてください)。2 つの値が同じである場合、 tx2
の実行中に、より優先度の高いトランザクション (たとえばtx0
またはtx1
) がその位置に書き込んでいないことを意味します。この結果、 tx2
は検証済みとしてマークされますが、コミットするのは安全ではありません。
トランザクションが検証された後に、さまざまな理由により優先度の低いトランザクションが実行される可能性があるため、トランザクションをコミットしても安全ではないと考えられます。実行中の例では、 tx1
アカウント B にアクセスし、その後でのみアクセスし、 tx2
検証に合格すると、 tx2
再実行する必要があります。
これに対処するために、トランザクションの実行が完了するたびに、検証に合格した優先度の低いトランザクションはすべて再検証され、トランザクションと競合しないことを確認します。たとえば、 tx1
、 tx3
、 tx4
が検証され、 tx2
実行が完了した場合、 tx3
とtx4
tx2
と競合しない (依存関係も競合しない) ことを確認するために再検証する必要があります。
トランザクションが検証に失敗した場合、つまり、同じ状態に書き込む優先度の高いトランザクションが同時に実行された場合、トランザクションが行った書き込みはダーティになります (値が間違っているため)。ただし、これらの値はデータベースから完全に削除されるのではなく、ESTIMATE フラグが付けられます。
ESTIMATE フラグは、そのメモリ位置を読み取るすべてのトランザクションに、そこにある値が正しくないことを伝え、トランザクションの実行を一時停止します。検証に失敗したトランザクションを再実行すると、前回の実行と同じメモリ位置に書き込まれる可能性が高いため、削除の代わりにこれが実行されます。
メモリ位置を削除するのではなく推定値としてマークすることで、再実行前であっても(検証に失敗したトランザクションの)依存関係を捕捉し、不要な再実行を防ぐことができます。このヒューリスティックにより、無駄な作業が大幅に削減されます。
Block-STM が並列化にどのようにアプローチするかの完全な概要は、次のように要約できます。
BLOCK
、明確に定義されたシリアル順序を持つ順序付きリストとして開始されます。これらのトランザクションは、利用可能なすべてのリソースに対して優先順位に従って実行されます。
以下に例を示します。
以上が Block-STM の仕組みの概要です。詳細については、こちらのレポートとこちらのオリジナルの Block-STM 論文をご覧ください。
Block-STM を追加することの重要性を定量化するために、いくつかのベンチマークを実行して、順次実行に比べて提供されるパフォーマンスの向上を評価しました。結果を以下に示します。
結果から、使用されるスレッド数 (独立した処理ユニットに相当) が増えると、パフォーマンスも向上することが分かります。改善はブロックが大きいほど顕著で、16 スレッドのみでの順次実行に比べて最大 9 倍のパフォーマンス向上が見られます。ブロックが大きいほど、結果が顕著であることがわかりました。
当社のテストでは、競合の激しい負荷がかかると Block-STM のパフォーマンスが大幅に低下することが示されていますが、業界標準の慣行では、そのような期間中は順次実行にフォールバックします。競合の激しいワークロードでスループットを維持するために、Starknet にも同じメカニズムを推奨します。しかし、全体的には、Block-STM の追加により Starknet が大幅に改善され、将来も使い続けられるようになります。
v0.13.2 アップグレードにバンドルされている 2 番目の主要な変更はブロック パッキングです。これについては次に説明します。
前述のように、Bolt 以前は、各 Starknet ブロックは独自のジョブであり、ブロックごとに固定のブロック コストが発生していました。さらに、システムは、ブロックによって実際に消費されるデータの量に関係なく、各ブロックに独自の BLOB が必要になるように設計されていました。
需要が常に高い世界では、これは問題にはなりませんが、Starknet は現在、需要よりも多くのブロックスペースを提供しているため、無駄なリソースが多く、1 か月の間に数百 ETH が失われる可能性があります。Bolt 以前の状況の深刻さをさらに理解するために、L1 にブロックを投稿することに関連するコストは次のとおりです。
合計すると、ブロックあたり 215k GAS となり、このコストは一定です。つまり、各ブロックに含まれるデータ量に関係なく同じであり、ブロック数と $Cost = num blocks * 215000$ で関連しています。この問題の理想的な解決策は、コストがブロック数ではなく投稿されたデータ量に関連していることです。そして、これはまさに、SNAR ツリーを介してブロック パッキングが実現するものです。
Starknet Applicative Recursive (SNAR) ツリーは、上記の問題に対処するために Bolt で導入された新しいタイプのバイナリ ツリーです。SNAR ツリーの構造は次のとおりです。各リーフは Starknet ブロックであり、他のすべてのレベルのノードは子の再帰証明です。他のすべての証明の再帰証明であるルート ノードは、SHARed Prover (SHARP) に送信される最終ジョブです。
SNAR ツリーの主な利点は、証明ごとに 1 つのブロックを投稿するのではなく、多くの Starknet ブロックを同じ L1 更新に分割できることです。SNAR ツリーのルートは、DA 制限 (6 ブロブ分のデータ) またはツリーに一定数のリーフが追加された後 (リーフはブロック) のいずれかの設定可能な制限に達した場合にのみ、L1 に投稿されるようになりました。
この設計により、トランザクションのコストがブロック数から切り離されます。現在でも、各ブロックで StarkNet OS (SNOS) を実行することで発生する固定コストはブロックごとに発生しますが、コストは大体切り離されています。現在の数値は次のとおりです。
下の図 11 のグラフは、以前の設計と現在 (Bolt 下) でガス コストがブロック番号によってどのように変化するかを示しています。
ブロック パッキングによって L1 での検証コストが大幅に削減され、Starknet ユーザーのガス価格が下がることは間違いありません。
Bolt に加えられた変更の効果、つまり Block-STM による楽観的並列実行と独自の SNAR によるブロック パッキングは、より高速でより安価であると要約できます。
並列実行により実行時間が短縮され、その結果として混雑が緩和されるため、トラフィックが多い期間のガス料金が削減されます。一方、SNAR ツリーは関連する DA と証明コストに対処します。興味深いことに、このアップグレードにより、Starknet は並列実行を備えた最初の L2 となり、L2 分野での主要な候補となる準備が整いました。これらの変更、特に並列実行の効果がすぐに明らかになる可能性は低いことに注意することが重要ですが、Starknet と Ethereum エコシステム全体の将来を保証するために重要です。
著者注: この記事のバージョンは以前こちらで公開されていました。