Vitalik: 断片化 + データ可用性サンプリング

著者 | ヴィタリック・ブテリン

著者 | ヴィタリック・ブテリン"Proof of Stake に加えて、eth2 の設計におけるもう 1 つの重要な変更はシャーディングです。この提案は、次のことに基づいて、限定された形式のシャーディングである「データ シャーディング」を導入します。"ロールアップ中心のロードマップ

ノード自体がすべてのデータをダウンロードする負担を回避するために、これら 2 つの手法を相互に重ね合わせて、大量のデータの可用性を検証できます: 1) ランダムにサンプリングされた委員会による証明; 2) データの可用性サンプリング (データの可用性)サンプリング、DAS）。

最初のレベルのタイトル

俗に言う「ランダムサンプリング委員会」

大量のデータ (たとえば 16 MB) があるとします。これは、eth2 チェーンが (少なくとも最初は) スロットごとに処理できる量です。このデータは、それぞれのサイズが 256 KB の 64 個のブロブとして表されます。約 6400 人のバリデーターを備えた PoS システムがあると仮定します。 1) 誰かにすべてのデータをダウンロードさせる必要がなく、2) 少数のバリデータを実行している攻撃者に機会を与えずに、このデータを検証するにはどうすればよいでしょうか?

最初の問題は、分業によって解決できます。検証者 1 ～ 100 は最初の BLOB をダウンロードして検証し、検証者 101 ～ 200 は 2 番目の BLOB をダウンロードして検証する必要があります。各サブセット (委員会) のバリデーターは、対応する BLOB を検証したことを証明するために署名するだけでよく、その後、対応する委員会のバリデーターの過半数の署名を受け取った後、ネットワーク全体が BLOB を受け入れることができます。

しかし、これは問題を引き起こします。攻撃者が連続するバリデーターのセット (例: 1971 ～ 2070) を制御した場合はどうなるでしょうか?この場合、攻撃者がバリデータ セット全体の約 1.5% しか制御していないとしても、単一の委員会を制御できます (上記の場合、コミッティー 20 のバリデータ 2001 ～ 2100 の 70% を制御できます)。攻撃 オペレーターは、無効または使用できない BLOB をチェーンに追加できます。

RNG (乱数ジェネレーター) はバリデーターのデポジット後にシードされ、各バリデーターのインデックスは固定されているため、攻撃者はすべてのバリデーターを同じ委員会に参加させることはできません。攻撃者は幸運に恵まれるかもしれませんが、それは攻撃者がすべてのバリデーターの 1/3 以上を制御している場合に限られます。

最初のレベルのタイトル

俗語「データ可用性サンプリング」

ある点では、データの入手可能性のサンプリングは、ランダムなサンプリング委員会の鏡像です。各ノードは最終的に全データの一部のみをダウンロードするため、サンプリングは引き続き行われますが、サンプリングは BLOB 間ではなく、クライアント内で BLOB ごとに行われます。

各ノード (ステーキングに参加していないクライアント ノードを含む) は、BLOB 全体をダウンロードするのではなく、各 BLOB をチェックし、その中から N 個のランダムなインデックスを非公開で選択し、それらの場所にデータをダウンロードしようとします。

このメカニズムは、クライアントが可用性を確認するために各 BLOB 内のデータのごく一部をダウンロードするだけで済むため、効率的です。また、51% の攻撃者でもクライアントを騙して使用できない BLOB を受け入れることができないため、このメカニズムは安全性も高くなります。

イレージコーディング

文章

攻撃者が利用可能なデータの 50 ～ 99% を提供する状況 (一部のクライアントが BLOB を拒否し、その後他のクライアントに受け入れられる可能性がある) を回避するために、イレイジャー コーディングと呼ばれる技術を使用します。イレイジャー コーディングを使用すると、BLOB 内のデータの半分以上が公開された場合に、ネットワーク内の誰もが残りのデータを再構築して公開できるような方法で BLOB をエンコードできます。

再パブリッシュされたデータがブロードキャストされると、最初に BLOB を拒否したクライアントは受け入れに集中します (BLOB の受け入れに時間制限はないことに注意してください。クライアントは、サンプリングされたすべてのインデックスに対する応答を受信するたびに、使用可能な BLOB を受け入れます)。 。

イレイジャー コーディングを理解するための最も簡単な数学的アナロジーは、「ラインを復元するには常に 2 つの点で十分である」です。 ((1, 4), (2, 7), (3, 10), (4) の形式の 4 つの点があるとします。 , 13)) 「ファイル」を作成するには、各点が直線上にあり、そのうち 2 つの点の座標があれば、直線を再構築して残りの 2 つの点を計算できます (x-座標 1、2、3、4 はシステムの固定パラメータであり、ファイル作成者の選択ではありません)。

高次の多項式を使用すると、このアイデアを拡張して、6 つのファイルのうち 3 つ、8 つのファイルのうち 4 つ、または一般的に言えば、2n ファイルのうち n 個のファイルを作成することができます。ファイルのうち n 個のポイントがある場合は、2n の残りのポイントを計算できます。

データ BLOB のプリンターとしてマークル ルートではなく、多項式コミットメント、具体的には Kate コミットメントを使用します。これは、多項式コミットメントを使用すると、指定された値が実際に特定の次数 n で多項式であることを簡単に証明できるためです。座標での正しい推定が必要です。それ以外の場合は、マークルルートが低次の多項式をエンコードしていることを証明するか（SNARK を使用するなど）、エンコードが間違っている場合は不正証明に頼ってブロードキャストする必要があります（これにより、複雑さが増し、同時性の仮定がさらに増加し​​ます）。

最初のレベルのタイトル

データ可用性サンプリングは委員会メカニズムでも必要ですか?

委員会のみに依存すると、次のようなデメリットが生じる可能性があります。

➤ 51% の攻撃を受けた場合、防御力は低下します。現在の (スケーラブルではない) ブロックチェーンでは、51% 攻撃はトランザクションをロールバックするか検閲することしかできず、無効なブロックをチェーンに追加することはできません。委員会ベースのシステムではこの保証が失われます。

さらに、51% の攻撃者を効果的に罰することは非常に困難です。なぜなら、攻撃者は、悪意のある行為に関連していることが証明され、それに基づいて罰せられる預金 (特定の委員会に参加している預金) が非常に少量しかないからです。

➤ DAS は、委員会メカニズムよりも量子攻撃に抵抗するのがわずかに簡単です (ポスト量子集約署名が必要な場合があります)。

最初のレベルのタイトル

データの入手可能性をサンプリングする委員会メカニズムは依然として必要ですか?

DAS のみを使用すると、次の問題が発生する可能性があります。

➤ DAS はまだテストされていない新しいテクノロジーであり、そのコア (こちらを参照) は実際には昨年開発されたばかりです。したがって、DAS のクラッシュや開発時間の予期せぬ延長が発生した場合に備えて、委員会を利用して保護を提供することをお勧めします。

➤ DAS は委員会よりも待ち時間が長くなります。

➤ DAS には、委員会が支援できるエッジケースが多数あります。一例として、DAS のみのシステムでは、ビーコン ブロック プロポーザーが最初に DAS 要求を開始して BLOB の可用性を確認することを回避することが困難です。

これにより、攻撃者が使用できない BLOB を公開し、提案者の要求にのみ応答するリスクが高まります。これにより、ネットワークの他のノードが使用できない BLOB を受け入れることはありませんが、他の攻撃が容易になり、誠実な提案者によって構築されたビーコン ブロックが拒否され、メイン チェーンからフォークされる可能性があります。委員会はこれを是正することができます。

➤ 委員会メカニズムの上位互換性が強化され、将来的にシャードに実行機能を追加できるようになります。

データの可用性の重要性?課題は何ですか?

これについては他の場所で議論されているため、ここには投稿しませんが、以下を読むことをお勧めします。

➤データの可用性と消去コーディングに関する注意事項（データの可用性についての最初の説明）

➤ Alberto Sonnino、Mustafa Al-Bassam、Vitalik Buterin による論文は、この概念を拡張しています。

➤ ハイブリッド レイヤ 2 プロトコルの夜明けでは、データ可用性におけるゲーム理論について説明しています

➤ 「ベース・レイヤーと機能エスケープ・ベロシティ」では、上記の概念に基づいて、データのスケーラビリティ部分について説明します

➤ データ可用性問題 (イーサリアム シリコン バレー ミートアップ)、データ可用性問題に関するビデオ ディスカッション

明確にしておきますが、BitTorrent や IPFS などのシステムはデータの可用性の問題を解決しません。 BitTorrent は優れたスケーラブルなデータ配信テクノロジーですが、データが利用可能かどうかについて合意に達することができないため、「極端な場合」攻撃の可能性があります。データの一部が解放されると、ノード間で不一致が発生し、ハイブリッド層が形成される可能性があります。 2 プロトコルは無効です。データの可用性について合意に達するには、このドキュメントで説明されているより堅牢な手法を使用する必要があります。

シャーディングは P2P レイヤーでどのように機能しますか?

シャーディングのスケーラビリティの目的を達成するには、すべてのノードがすべてのデータをダウンロードする必要がないように P2P システムが必要です。幸いなことに、フェーズ 0 には P2P レイヤー シャーディングの形式がすでにあります。具体的には、集約を示すために 64 のサブセットが使用されています。各バリデーターは、メインの「グローバル サブネット」と独自の構成証明集約サブネットに存在するだけでよく、他の 63 個の集約構成証明サブセットからデータをフェッチする必要はありません。

委員会 + DAS タイプのシャーディングでは、それを 2048 個の水平サブネット (水平サブネット) を持つ「グリッド」アーキテクチャに拡張します。つまり、各エポックの各シャードとスロットのペアにサブセットがあり、2048 個の垂直サブネット (垂直サブネット) があります。サブネット)、つまり、各 BLOB 内に各インデックスのサブセットが存在します。

各スロットでは、シャードごとに提案者を選出します。各提案者は、BLOB を提案する権利を持っています。BLOB とは、消去符号化拡張機能と追加の証明を備えた、最大 512 KB のデータの任意のブロック (約 512 バイトの「サンプル」のコレクションとして理解できます) であり、BLOB 内の各部分は独自に検証されています。

ブロブの構造 ブロブの構造

BLOB の「本体」構造は、元のデータ、拡張データ、プルーフで構成されます (BLOB を受信する各ノードは比較的迅速に再構築できるため、必要に応じてデータ効率を高めるために拡張データを省略できます)。

BLOB の「ヘッダー」には、他のデータ (スロット、シャード、長さの証明) および提案者の署名とともに、対応する Kate コミットメントが含まれています。

BLOB ブロードキャスト プロセス

BLOB がブロードキャストされると、そのヘッダーはグローバル サブネットにブロードキャストされ、本体はスロットとシャード ID に対応する水平サブネットにブロードキャストされます。

実際には、2048 個の水平サブネットがあり、各エポックのシャードとスロットのペアごとに 1 つの水平サブネットが存在します。これは、各バリデーターが水平サブネットに参加できるようにするために行われ、各バリデーターはその委員会に対応する BLOB のみを受信します (サンプリングに参加する少数の垂直サブネットを除く)。

各バリデータは次のサブネットに参加する必要があります。

➤ グローバルサブネット

➤ 割り当てられているインデックスに対応する垂直サブネット（バリデータごとにプライベート シードを使用して計算）

ブロードキャストブロック

文章

BLOB プロポーザーはサンプルをすべてのサブネットに配布できますが、サブネットの一部である必要はありません。プロセスは次のとおりです。

➤ 公開: 提案者は正しい水平サブネットワークで BLOB を公開します。各サンプルには証明が付属します。

➤ 直接サンプル配布: 水平サブネットの他の参加者が、所属する各垂直サブネットにブロックを公開します。

➤ 間接的なサンプル配布: プロポーザーは、自分が属するいくつかの垂直サブネットをピアにアナウンスします。したがって、水平サブネットワークの各参加者は、そのピアが属する垂直サブネットワークを確認し、対応するブロックをそれらのピアにブロードキャストすることもできます。

データ ブロック サイズが 512 バイト、データ ブロブの最大値が 512 KB (消失コーディングを除く) (消失コーディングが含まれる場合は約 1 MB) と仮定すると、垂直サブネットは 2048 個あります。各ノードが 15 個のプライベート垂直サブネット、5 個のパブリック垂直サブネットに存在し、50 個のピアがある場合、最悪のケースで各水平サブネットに 128 人のメンバーがいると仮定して (委員会のみ)、サブネット メンバーだけが 128 * 20 = 2560 個のサブネット (約) に直接分散されます。冗長パブリッシングを削除した後は 1461)、ピア ノードを追加すると、128 * 4 * 50 = 25600 サブネットに増加します。

理論的には、悪意のあるブロック提案者が完全なブロックを公開せずにサンプルを垂直サブネットに公開することが可能であることに注意してください。この状況に対処するために、不完全に公開されたブロック (50% 以上が利用可能ですが、100% は利用可能ではないことを意味します) が「自己修復」できるプロセスを追加しました。このプロセスは、次の 3 つの基本的な手順で構成されます。

1. 逆分散: 上記と同じ分散プロセスですが、この場合、垂直サブネット上のピアが、サンプルをその垂直サブネットから、サンプルが属する BLOB に対応する水平サブネットに伝播します。

3. 配布: 上記の配布手順を繰り返します。

最初のレベルのタイトル

ビーコンチェーンはどのように機能しますか?

各スロットでは、64 個のシャードごとに提案者をランダムに選択します。プロポーザは、シャード BLOB を作成し、上記のプロセスを通じてブロードキャストし、BLOB の ShardHeader をグローバル サブネットにブロードキャストする権利を持ちます。 ShardHeader は、ビーコン チェーン上の同じスロットにパッケージ化でき、同じ/次のエポックの後続のスロットに含めることもできます。

ビーコン チェーンは、PendingShardHeader オブジェクトのリストを追跡します。 PendingShardHeader には以下が格納されます: 1) ShardHeader 内の重要な情報 (シャードとスロット、BLOB のコミットメントとその長さ); 2) ランダムに選択された委員会のどのバリデーターが BLOB に署名したかを追跡するビットフィールド (実際には、フェーズ 0 ですでに導入された委員会) 。 AttestationData 構造は、バリデーターが投票するために選択される ShardHeader のルート ハッシュである shard_header_root を含むように拡張されています。証明者は、シャードとスロットのペアに割り当てられている有効で使用可能なシャード BLOB が見つからない場合、空のルート ハッシュに投票することもできます。

ShardHeader が委員会のバリデーターの 2/3 によって証明された場合、直ちに確認されます。次のエポックの終わりに、シャードヘッダーが他のシャードヘッダーよりも委員会から多くのサポートを得ている場合、そのエポックの終わりにそれが確認されます。

フォーク選択のルール

フォーク選択ルールが変更され、ブロック内ですべての BLOB またはその祖先が可用性チェックに合格したことが確認された場合にのみブロックが有効となるようになりました。これは密結合と呼ばれます。チェーンが無効な BLOB を指している (確認された) 場合、チェーン全体が無効であると見なされます。これが「サイドチェーン」構造との主な違いです。サイドチェーンでは、メインチェーンが有効なままでもサイドチェーンが失敗する可能性があります。

ここでは、密結合とそれがなぜ価値があるのか​​についてさらに詳しく説明します。

バリデーターの数が少ない場合

バリデーターの数が 262144 未満 (32 スロット * 64 シャード * 128 最小委員会サイズ) の場合、すべてのシャードのプロポーザーを選択する代わりに、限定されたサブセットのプロポーザーを選択し、シャードをループします。たとえば、32 * 128 * 50 のバリデーターがあり、スロット N の開始シャードが 0 の場合、スロット N はプロポーザーをシャード 0 ～ 49 に割り当て、スロット N+1 はプロポーザーをシャード 50- シャードに割り当てます。 63 と 0 ～ 35 はプロポーザーを割り当て、スロット N+2 はシャード 36 ～ 63 と 0 ～ 21 にプロポーザーを割り当てます。これは、参加者が少ない場合でも、委員会の規模が適切なままであることを保証するために行われます。

EIP-1559 と同様のメカニズムを追加し、シャード データをバイト単位で課金し、価格を調整しました。ブロックの平均容量が 50% を超えると料金が増加し、その逆も同様です。したがって、インジケーターは平均ブロック サイズの 50% になります。

最初のレベルのタイトル

セキュリティの前提

データ BLOB のみのシャーディングは、他のシャーディング スキームほど安全性の前提に依存しないため、強力です。特に、正直な多数決の仮定 (DAS は多数派によって発行された使用できない BLOB を検出できるため) とタイミングの仮定 (以前の DAS メカニズムとは異なり、不正証明ではなく Kate コミットメントを使用するため、不正証明に必要な仮定に依存しません) を回避します。非常に早く放送されます）。

主な新しい仮定は「正直な少数派 DAS 仮定」です。つまり、攻撃者がブロックの半分以上を公開しなければならないほど十分に大きなノードのサンプルが存在します。 BLOB 内に 2048 個のサンプルがある場合、1024 個のサンプルを復元する必要があり (一部のクライアントが同じポイントをサンプリングすることを考慮すると、2048 * ln(2) ~= 1419)、各クライアントは 20 個のサンプルを実行すると、システムは次のように考えることができます。シャードあたり約 70 を超えるクライアントがサンプリングされている場合は安全です。

最初のレベルのタイトル

データ BLOB のみをサポートするシャーディング設計は、将来シャーディングでの実行を追加する多くのシナリオと上位互換性があります。特に、BLOB に事前状態ルートと事後状態ルートが含まれるようにスキームを変更できます。また、不正証明や ZK-SNARK を使用して BLOB 内の状態遷移が正しいことを検証することもできます。どのアプローチを選択しても、シャーディング実行の正確性の確保は、正直な多数決の仮定に依存しないことに注意してください。

文章

https://github.com/ethereum/eth2.0-specs/pull/2146

公式アカウント: ETHチャイニーズステーション

Protolambda’s work-in-progress implementation

元のリンク:https://hackmd.io/@HWeNw8hNRimMm2m2GH56Cw/sharding_proposal

ECN の翻訳作業は、中国のイーサリアム コミュニティに高品質の情報と学習リソースを提供することを目的としています。記事の著作権は原著者に帰属し、転載する場合は原文の出典と ETH 中国の Web サイトを表示する必要があります。長期にわたって再版する場合は、eth@ecn.co に連絡して許可を取得してください。

公式アカウント: ETHチャイニーズステーション

ウェブサイト: ethereum.cn