ICMP キュー ルーティング用のシンプルなゴシップ プロトコル

新しいツリー構造 (葉) B について

ノード (ピア) k の新しいチェーン ブロック ヘッダー宣言

モジュール t からの k がキュー メッセージ m にあります

ピア層ノード (peer) k on 〖allowed〗_k (m) の定義

• 定期的に

• 今後の改善

Polkadot ネットワークでは、いくつかのエンティティに情報を送信する必要があります。まず、これらのエンティティの種類を簡単に整理します: (1) ユーザー、(2) コレクター、(3) 検証者

実行時のパラチェーンに関するすべての情報は、

この候補ソースは、パラチェーン候補ブロックを検証することによって生成され、リレー チェーン ブロックに含まれます。候補者には多くの分野があります。関連するものをいくつか示します。

出力ルート:

リレーチェーンブロック B がパラチェーン p に含まれる場合、一意のパラチェーン y とペアになる各ハッシュ値は R(E_(p,y)^B) となります。

受信したデータがパラチェーン p のものである場合、新しい

価値。ランタイムは、最も近いパラチェーンの候補チェーンから受け取った値を現在の値とみなします。候補を含むブロック内の B の元の値は、少なくともウォーターマーク p の前の値と同じくらい大きくなければなりません。

(rob: 空のリストでの空でない保留中の出力は許可されません)

検証者とコレクターの両方がブロック B のブロック キュー情報を収集しようとするか、検証者が単に 〖Ingress〗_(B,P) を呼び出して伝播プール内の関連メッセージを検索し、まだリリースされていないメッセージを待ちます。 P 上の照合子の目的は、リレー チェーンの親 B を基にして、P_INGRESS (B,P) のプレフィックスをできるだけ取得することです。

R(P_INGRESS (B,最も簡単な方法は を使用することです。メッセージはパラチェーン ネットワーク間で噂されます。メッセージをブロードキャストするこれら 2 つのネットワーク間に共通のノードがある場合、メッセージを受信して​​いる並列リンクがそのメッセージを受信することになります。ただし、ターゲット パラチェーンのバリデーターが、メッセージがパラチェーンの受信側に伝播されなかったことを認識した場合、メッセージを送信したパラチェーンのバリデーター ノードからメッセージを再リクエストし、そのメッセージをパラチェーンで受信します。パラチェーン自体を伝播するデバイス。

P)) は、実行時にすべてのブロック B およびパラチェーン p で使用できます。

パラチェーン p とブロック B が利用できるのは、p と B がブロックの保留中のイングレス ルートのイングレス リストであり、各リストとルートが最初にルーティングされたブロック番号とペアになっているという事実によるものです。入力リストから R(∅) を省略し、空のリストを省略してブロック番号の昇順に並べ替えます。ここで、すべてのブロック番号は num(B) より小さく、同じチェーン内のブロックを指します。

RUST の疑似コード (TODO: LaTeX への転写)

特定の B および p の出力キューからのデータは、実行時に引き続き使用できますが、空のリストの順序付けや省略に関して入力リストと同じ制約が適用されます。ここでの ParaId は受信チェーンであり、エントリ (イングレス) 関数では送信チェーンです。

ツリー構造がそのブロックをリレーチェーン内の最新のパラチェーンブロックとして残すと仮定しましょう。

ノードについては次のことを前提としています。

1. ツリー構造の末端の葉のブロック状態は取得可能ですが、古いブロックの状態は保証できません

2. パラチェーン上のコレーターとフルノードは、パラチェーン上で実行されたすべてのブロックを保持すると予想されます。

3. バリデーターはブロックを保持する必要はありません。また、バリデーターによって保存された消去コード化されたスニペットから情報を復元できることにも注意してください。

この章では、ICMP メッセージのキューを伝播するための限定的なゴシップ プロトコルについて説明します (定義については「概要」を参照)。

そして

そして

ingress はブロック B で呼び出されているため、簡単に

変換する

メッセージは非ルーティング状態で開始され、ルーティング状態で終了します。

ゴシップ伝播システムを定義することを提案します

このモジュールに関するメッセージの形式は次のとおりです。

私たちはローカル情報を次のように保管します。

1. 〖葉〗_k は、コードを実行する必要がある DAG ブロック ツリー構造のエンドポイント (葉) に最適なハッシュ関数のリストです。

2. 〖葉〗_k、ピア k ごとに、ブロックの MAX_CHAIN_HEADSDAG ハッシュ値 (送信された内容に基づく) コードを実行するために最適な最新リストが必要です。

3.leafTopics(l)→{queueTopic(h)} は、すべてのツリー構造 (葉) 上のツリー ノード l 上の並列チェーン上の展開されていないルート h を意味します。

4. ExpectedQueues(t)→H は、すべての呼び出しモジュールの対応するハッシュ ルートの導出プロセスを示し、すべてのエントリの t∈∪l_(∈leaves)leafTopics(l)

新しいツリー構造 (葉) B について

1. ツリー構造 (リーフ)、ツリー モジュール (リーフトピックス)、および予想されるキューをアップグレードします (ベンチマーク テストは実行されていませんが、控えめに見積もっても実行時間は 100 ミリ秒となります)

2. 同じ階層の新しいツリー構造（葉）を送信します

3. 並列チェーン p のコレクターがコード egress(B,p) をオンラインで実行する場合、伝播されていない既知のメッセージ キュー ルートについては、対応するキュー メッセージを伝播プールに置きます。

ノード (ピア) k の新しいチェーン ブロック ヘッダー宣言

1. ツリー構造(葉) 〖葉〗_kのアップグレード

2. ∀H∈leaves ∩ 〖leaves〗_k の要件を満たすために、broadcastTopic(k,t) の各 t は、leafTopics(H) にマッピングされます。

モジュール t からの k がキュー メッセージ m にあります

関数を定義します

ローカルなローカル信頼基準 (ローカルな許容基準) として。

メッセージのハッシュルート

定義された関数 ExpectedQueues(t) では、指定されたメッセージの実際のルートはルートと等しくなります。

関数 Good(m) が k が正であることを証明する場合は、m を伝播プールに入れます。そうでない場合は、m が利用できないことを証明します。これは、ピアセットの育成に役立ちます。

〖allowed〗_k (m) 上のピア層ノード (peer) k の定義、およびモジュール t 上のキュー メッセージ メート​​ル

メッセージの送信が完了する前にメッセージ k が送信された場合、メッセージ k は拒否される必要があります。逆に、次のような場合は、

∃l∈leaves∩〖〖leaves〗_k|t∈leafTopics(l)∃l∈leaves∩〖leaves〗_k | t∈leafTopics(l) の場合、メッセージ k が許可され、他のメソッドは禁止されます。

定期的に

ExpectedQueues を除いて、すべてのモジュールを期限切れモジュールとしてマークし、伝播プール内でクリアする必要があります。実際、このような操作は数秒ごとに実行されます。これにより、伝播プールが無制限に増大することがなくなります。

現在の MOD の同じビューを共有するピアにのみルーティングされていないメッセージを伝播するという決定は物議を醸すかもしれませんが、私たちが考え出した前提条件のいくつかはこの点を非常によく示しています。

まず、ノードが無限の数のメッセージを処理する必要がないようにします。これは、そのような H が無限に存在するため、queueTopic(H) の H がノードにとって未知であることを意味します。第 2 に、ノードはメッセージを特定のピアに伝播するかどうかを決定するために多くの作業を行う必要がありません。葉∩〖葉〗_k=∅としますが、〖葉〗_kの一部のエントリは葉のソースコードです

（祖先）。証明するには、O(n) 内のすべての l ∈ 〖leaves〗_k を実行する必要があります。次に、特定のメッセージが前のブロックでルーティングされなかったかどうかを判断する必要があります。私たちは、メッセージが前のチェーンでルーティングされるのではなく、同じチェーン内の後のブロックでまだルーティングされていない場合、その可能性は低いですが、チェーンの状態が人間のノードでのフィッシング ロールバックである可能性があると素朴に考えます。

想定されるチェーン状態は前のブロックからは利用できないため、その前のブロックのピアに出力を実際に送信するかどうかを判断する適切な方法がありません。今後の改善セクションでは、オリジン (祖先) の固定数にスケールすることでこの制限を緩和することについて説明します。

それにもかかわらず、次のことを前提として、同じチェーンに同期されているノード (ピア) に伝播することは合理的です (一部は経験的ですが合理的ですが、過大評価される可能性もあります)。

1. 新しい有効なブロックは平均少なくとも 5 秒の間隔で発行されます (実際の目標は 10 ～ 15 秒です)。

2. ゴシップ伝播構造の「有用な」部分のブロックの伝播時間は 2 秒以内です。

3. ゴシップ伝播構造内の隣接する主題の遅延は 500 ミリ秒以下です

4. DAG のヘッドと同期する前にメッセージを有意義に伝播することには価値がない可能性があります

実際の値はほぼ確実にこれより優れています。良いニュースは、1 ブロック時間内にすべてのブロックを伝播する必要があるわけではないということです。時間が経つにつれて、参加者がより早いメッセージを取得できるようになります。これは、すべてのメッセージが参加者全員に表示されるスキームです。ほぼ確実に、少数の初期チェーンを超えて拡張することはありませんが、代わりにスターター プロトコルとして機能します。

副題

XCMP ルーティングの概要

設定に従って、あるパラチェーン（送信側パラチェーン）から別のパラチェーン（受信側パラチェーン）にメッセージを送信するには、次の手順を実行します。

送信パラチェーンの完全なノードが受信パラチェーンのドメインの一部でもある場合、メッセージは十分です。

受信側パラチェーンのパラチェーンバリデーターはメッセージが伝播されたことを発見できず、送信側パラチェーン（送信側リアルタイムPV）のパラチェーンバリデーターにメッセージを直接リクエストします。送信パラチェーンの PV は、メッセージを利用可能な状態に保つ責任があります。パラチェーンを送信するパラチェーン検証者は、受信側パラチェーンのPoVにメッセージを直接送信し、最終的に受信側パラチェーンのPVが受信側パラチェーンネットワーク内でメッセージに関するゴシップ（噂話）を広めます。

副題

今後の改善

1. 上のセクションでは、出力キューをピア層まで恣意的に伝播することがなぜ悪い考えであるかを説明しましたが、一旦同期して通常のブロック生成に従えば、すべてのツリーを合理的に追跡できます。構造（葉）。 α の初期の妥当な値は親の値と一致する必要があり、1 をとります。これにより、必要なゲインの 90% が得られる可能性があります。これは、ツリーセットの交差が必要なときに「スタッター」が発生し、2 つのピアが新しいサブキーに関する情報を互いに更新する必要があるためです。

2. E_(x,y)^B の定義を拡張すると、チェーン間の相互検査が可能になります。たとえば、パラチェーン y は、ブロック B で x からのメッセージをルーティングしないようにリレー チェーンに指示できます (その後、ブロック B' でルーティングを再開するように指示できます)。 B と B' の間のブロックでは、CandidateReceipt の b の x を無視すると、実行時間は E_(x,y)^b=∅ になります。実際、ランタイムはハッシュ ルート ハッシュのみを処理するため、実際には候補レシートからの R(E_(x,y)^b) を無視し、それを R(∅) に設定します。

3. 誰もがすべてを確認できるわけではない、よりスマートなトポロジをサポートするために拡張します。おそらく、(B,(B,〖chain〗_from))ベースのトピック配列(Topics)と(B,〖chain〗_to)ベースのMODの2種類のトピック配列(Topics)を用意すると、このMODの使いやすさが向上するかもしれません。https://github.com/sipa/minisketch4. ある種のスマートなセットアップ調整を使用します (例: