目次
チェーン間メッセージング
ICMP キュー ルーティング用のシンプルなゴシップ プロトコル
新しいツリー構造 (葉) B について
ノード (ピア) k の新しいチェーン ブロック ヘッダー宣言
モジュール t からの k がキュー メッセージ m にあります
ピア層ノード (peer) k on 〖allowed〗_k (m) の定義
定期的に
今後の改善
XCMPクロスチェーンメッセージング
Polkadot ネットワークでは、いくつかのエンティティに情報を送信する必要があります。まず、これらのエンティティの種類を簡単に整理します: (1) ユーザー、(2) コレクター、(3) 検証者
Polkadot ネットワークでは、いくつかのエンティティに情報を送信する必要があります。まず、これらのエンティティの種類を簡単に整理します: (1) ユーザー、(2) コレクター、(3) 検証者
1. ユーザー - トランザクションを作成し、パラチェーンまたはリレー チェーンに情報を提供します。
2. Collator - 特定のパラチェーンに所属します。これらは、パラチェーンのトランザクション データを整理してブロックにパッケージ化して有効な証明書を生成し、次のブロックの一部としてパラチェーン上のバリデーターに送信する責任を負います。有効性に関連する次の 2 つのリンクは、Polkadot ネットワークの基本ルールの一部ですが、特定の並べ替え操作を実行する方法はパラチェーンによって独立して選択されます。
3. バリデーター - リレーチェーンに属し、Polkadot ネットワークのルールに従います。バリデーターの異なるサブセットは、それらのチェーンを検証するために異なるパラチェーンに割り当てられるため、これらのサブセットを「パラチェーンバリデーター」と呼びます。また、トランザクション情報を整理してリレーチェーンに送信します。
次に、これらのエンティティ間のいくつかのサブプロトコルを理解する必要があります。各サブプロトコルは、トランザクション実行の対応する抽象化を提供します。
1. トランザクションの送信
関連エンティティへのアクセスが利用可能な場合、ユーザーはトランザクションを送信するために関連エンティティを見つける必要があります。
2.パラチェーン照合
並列チェーンのコレクターはトランザクション情報を収集してブロックにパッケージ化し、ブロック内のデータは各並列チェーンによって選択された Polkadot ネットワークの範囲外の外部チェーンから取得されます。
3. パラチェーンブロック認証
照合者は他の認証データも生成し、それをパラチェーンのバリデーターに送信します。この最終的な目標は、パラチェーンバリデーターが各パラチェーンブロックがオンチェーン検証機能を満たしていることを効果的にチェックすることです。証明データを生成するために、照合者は、リレー チェーンの早い段階でパラチェーン バリデーターによって送り返されるデータも必要とします。
4. リレーチェーンプロトコル
パラチェーンバリデーターは、送信されたパラチェーンブロックの有効性を証明し、合意を得るためこれらの証明を他のバリデーターに配布します。次に、すべてのバリデーターは、実証済みのブロックとリレー チェーン上のトランザクション情報を整理してリレー チェーン ブロックにパッケージ化し、ブロックを完成させます。
5. チェーン間メッセージング
リレーチェーンブロックが完了し、この事実がパラチェーンにコミットされた後、パラチェーンはこれらのブロックに他のパラチェーンからの新しい情報が含まれているかどうかをチェックし、含まれている場合は修正して反応します。
（Parachain synchronisation）
6. パラチェーンの情報統合
コレーターは、初めて接続した場合や長時間切断した場合、接続が回復した後にパラチェーンの最新状態を再取得して検証する必要があり、検証内容には一時的に送信されたトランザクション情報やパラチェーンの最新状態に関する情報が含まれます。リレーチェーン。
7. リレーチェーンの情報統合
上記の説明では、関連する詳細を要約で説明し、これらの詳細が変更された場合でも有効に保つよう努めました。プログラムを作成する際、Polkadot ネットワーク層が提供する必要があるサービスの中で、サブプロトコル (3 ～ 5) と 7 が依然として最も需要が高く、最も複雑なコンポーネントであり、維持されることが予想されることがわかりました。
XCMP
副題
チェーン間情報転送：Egress Queueデータ取得
Polkadot のすべてのパラチェーン ブロックは、他のすべてのブロックへのメッセージの空のリストを生成します。これらは「出力キュー」と呼ばれます。 E_(x,y)^B は、ブロック B のチェーン x からチェーン y への出力キューを表すために使用されます。 R(E_(x,y)^B) これは、マークル パトリシア trie[] のハッシュ ルートであり、メッセージ データ内の E_(x,y)^B の樹状図を描画することによって取得されます。
チェーンに配信された未処理の保留中のメッセージは、そのチェーンの次のブロックで処理される必要があります。一定期間チェーン上で新しいブロックが生成されないと、メッセージが蓄積され始める可能性があります。
パラチェーン p 上のコレーター ノードとフル ノードは、そのパラチェーン上のすべてのブロックを実行しており、チェーン x 内のすべての B ブロックと E_(p,y)^B を知っている必要があります。
ブロック B の並列チェーン p 上のブロック出力のアクセス ポイントのセットは次のとおりです。
ブロックのイングレスコレクションルートは次のとおりです。
パラチェーン p 上のブロック B の合計累積エントリ (入口) は、再帰関数によって定義できます。
これは、ブロック B から各並列チェーン、p チェーン内の各ブロックへのすべてのイングレスを含むブロックです。
パラチェーンは 〖ingress〗_(parent(B),p) の後に 〖Ingress〗_(B,P) を実行する必要があり、〖Ingress〗_(B,P) からのデータと命令はすべて実行する必要があります。
各パラチェーンには、リレー チェーンによって生成されたウォーターマーク値 p があり、最近実行されたイングレス操作が反映されます。最初は Genesis として設定され、すべての未処理のメッセージを含む構造をパラチェーンとして定義するために、再帰関数によって定義される保留中のイングレスを導入します。
これらの保留中のルート R(P_INGRESS (B,P)) は、R(T_INGRESS (B,P)) として近似することもできます。パラチェーン候補チェーンを使用すると、任意のプレフィックスを使用して P_INGRESS (B,P ) を構築できます。
実行時のパラチェーンに関するすべての情報は、
この候補ソースは、パラチェーン候補ブロックを検証することによって生成され、リレー チェーン ブロックに含まれます。候補者には多くの分野があります。関連するものをいくつか示します。
Vec<(ParaId, Hash)>
出力ルート:
リレーチェーンブロック B がパラチェーン p に含まれる場合、一意のパラチェーン y とペアになる各ハッシュ値は R(E_(p,y)^B) となります。
watermark p
受信したデータがパラチェーン 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) より小さく、同じチェーン内のブロックを指します。
fn ingress(B, p) -> Vec<(BlockNumber, Vec<(ParaId, Hash)>)>
RUST の疑似コード (TODO: LaTeX への転写)
fn egress(B, p) -> Vec<(BlockNumber, Vec<(ParaId, Hash)>)>
特定の B および p の出力キューからのデータは、実行時に引き続き使用できますが、空のリストの順序付けや省略に関して入力リストと同じ制約が適用されます。ここでの ParaId は受信チェーンであり、エントリ (イングレス) 関数では送信チェーンです。
ツリー構造がそのブロックをリレーチェーン内の最新のパラチェーンブロックとして残すと仮定しましょう。
ノードについては次のことを前提としています。
1. ツリー構造の末端の葉のブロック状態は取得可能ですが、古いブロックの状態は保証できません
2. パラチェーン上のコレーターとフルノードは、パラチェーン上で実行されたすべてのブロックを保持すると予想されます。
3. バリデーターはブロックを保持する必要はありません。また、バリデーターによって保存された消去コード化されたスニペットから情報を復元できることにも注意してください。
ゴシッププロトコルを許可するシステム上に構築すると仮定すると、ピアはどのツリー構造のエンドポイント（リーフ）が最適であると考えるかを互いに通信できます。
この章では、ICMP メッセージのキューを伝播するための限定的なゴシップ プロトコルについて説明します (定義については「概要」を参照)。
fn ingress(B, p) -> Vec<(BlockNumber, Vec<(ParaId, Hash)>)>
そして
fn egress(B, p) -> Vec<(BlockNumber, Vec<(ParaId, Hash)>)>
そして
BlockNumber -> BlockHash
ingress はブロック B で呼び出されているため、簡単に
変換する
メッセージは非ルーティング状態で開始され、ルーティング状態で終了します。
ゴシップ伝播システムを定義することを提案します
struct Queue { root: Hash, messages: Vec
, }
このモジュールに関するメッセージの形式は次のとおりです。
私たちはローカル情報を次のように保管します。
MAX_CHAIN_HEADS
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 にあります
good(m)
関数を定義します
ローカルなローカル信頼基準 (ローカルな許容基準) として。
root
メッセージのハッシュルート
定義された関数 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. ある種のスマートなセットアップ調整を使用します (例:
) ゴシップ伝播帯域幅を最小限に抑えます。
5. 確率論的なマイクロペイメントと同様の方法で配布を奨励します。
6. パラチェーン検証ノードは、メッセージが含まれていることが確認されるまで出力キューを保持します。これは、2 つのパラチェーン ネットワークに同一のフル ノードがなく、メッセージがチャット経由で到着しない場合のロールバックです。受信パラチェーンのパラチェーン検証ノードはメッセージの欠落に気づき、送信チェーンのパラチェーン検証ノードにメッセージを要求します。リクエストを受信すると、そのリクエストは受信者のパラチェーン ネットワークを通じて伝播します。
ブロックチェーンがビジネス ロジックに持つすべての情報は、CandidateReceipts の形式です。ブロック署名者は、ブロック内の各パラチェーンから最大 1 つの CandidateReceipt を送信できます (実際には、複数のバリデーターによって証明されたチェーンのみですが、この前提はここでは関係ありません)。
編集 / ステルスヤオ
IOS
Android