ICインターナルズ：Xnetプロトコル（和訳）
元記事：https://mmapped.blog/posts/08-ic-xnet.html
前回に引き続き、複製されたステートマシンの群れであるインターネット・コンピュータ（IC）におけるステートマシンの複製について説明します。今回は、独立したステートマシン（サブネットとも呼ばれる）が通信するためのプロトコル、XNetプロトコルを検証することにします。
リンク：
Twitter：https://mobile.twitter.com/c3f_iu
まとめサイト：https://dfinity-c3f.softr.app/
イベント：https://c3f.connpass.com/event/
サブネット
サブネットは、CONSENSUS PROTOCOLの単一のインスタンスに参加しているノードの集 合です。
サブネットは、CONSENSUS PROTOCOLの単一のインスタンスに参加しているノードの集合です。サブネット内のすべてのノードは同じ状態を持ち、同じブロックを適用します。
サブネットのノードは物理的に同じ場所にあると考えたくなるかもしれません。しかし、通常はその逆で、サブネットのノードは独立したデータセンターに地理的に分散していることが多いのです(※1)。目標は可用性を高めること: 1つのデータセンターで災害が発生しても、サブネット全体をダウンさせることはできません。レジストリキャニスターは物理マシンへのノードの割り当てを管理し、NETWORK NERVOUS SYSTEMはレジストリへのすべての変更を管理します。
異なるサブネットのノードが同じデータセンターで生活することができます。この設定は直感に反するかもしれません。異なるサブネットのノードは、同じサブネット内のノードよりもネットワーク接続性が良い場合があります。
※1. データセンター内の複数のノードを同じサブネットに割り当てることには、クエリーコール容量の増加やレプリカ再起動時のリカバリーの高速化など、まだ正当な理由があります。
3つのデータセンターに設置された2つの3ノードサブネット。実線はサブネット内のピアツーピア通信、点線はサブネットをまたぐ通信を表しています。すべてのXNet接続が図に記載されているわけではありません。
XNetのプロトコルはデータセンター間の通信に限らず、あるサブネットのどのノードでも別のサブネットのどのノードとも通信できます。しかし、レプリカはメッセージ配信のレイテンシーを減らすために、より近いピアと接触することを好みます(※2)。
※2. レプリカはネットワーク遅延を近接の尺度として用いる。他のサブネットのノードとランダムに接触し、遅延の小さいノードに高いウェイトを割り当てます。
メッセージストリーム
メッセージは、送信元サブネットにホストされているキャニスターの出力キューから始まります。サブネットはこれらのメッセージを宛先サブネットに基づいてソートし、フラットメッセージストリーム（宛先サブネットごとに1つのストリーム）にインターリーブします。ストリーム内の各メッセージは、一意の単調増加するインデックスを取得します。
サブネット内のメッセージの流れ。キャニスターはメッセージを出力キューに配置します。ストリームビルダーはこれらのメッセージをピックアップし、各サブネットのためのフラットな送信メッセージストリームを構築します。
キューをマージするコンポーネント（ストリームビルダーと呼ぶのが適切）は、いくつかの制約を満たす必要があります。
決定性
サブネット内のすべてのノードが、ストリームの正確な内容に合意しなければならない。ストリームビルダーは、その仕事をするために、キャニスター識別子からサブネット識別子へのマッピング、つまりルーティングテーブルを必要とします。ルーティング・テーブルはレジストリから取得され、時間の経過とともに変更されます。決定性を確保するため、各ブロックは、ステートマシンがメッセージ処理に使用するレジストリ・バージョンをピンします。
順序付け
キャニスタAがキャニスタBにR1とR2という2つのリクエストを送る場合、ストリームではR1がR2の前に表示されるはずです。
公平性
単一のおしゃべりなキャニスターからのメッセージがストリームを支配することは避けたいものです。ストリーム構築者は、各キャニスタが同じ帯域幅を持つようにメッセージをインターリーブすることを試みます。
サブネットXのノードがサブネットYから新しいメッセージを取得することを決定すると、Yからノードを選び（レジストリはネットワーク・トポロジー全体を保存します）、最初の未見メッセージのインデックスと取得するメッセージ数でYのXNetエンドポイントを呼び出します。
ブロックペイロード
コンセンサス・プロトコルの仕事は、外界からのメッセージを集約して、きちんとしたブロックにまとめることである。コンセンサスには、ユーザー入室メッセージ、ビットコイン取引（ビットコイン統合が有効なサブネットの場合）、他のサブネットからのキャニスター間メッセージなど、いくつかのタイプのメッセージがブロックに含まれます。メッセージとその検証に必要なデータのペアをペイロードと呼びます。ネットワークからペイロードを引き出すコンポーネントをペイロードビルダーと呼びます。
コンセンサス・アルゴリズムは、外部からのメッセージをブロックに集約する。
XNetペイロードビルダーは、他のサブネットに割り当てられたノードから、シンプルなHTTPプロトコルを使ってメッセージを取り込みます。XNet エンドポイントは、他のサブネット宛のメッセージを安全なTLS 接続で提供するコンポーネントで、他のノードからの接続のみを受け付けます(※3)。XNetエンドポイントは、ノードの完全なリスト、そのサブネットの割り当て、IPアドレス、および公開キー（TLS接続を確立するために必要）をレジストリから取得します。
※3. 悪意のあるノードがデータにアクセスできるため、この措置はプライバシーを意味しないが、ネットワークプロバイダーがメッセージを読むことができないことを保証する。
XNetプロトコルのデータフロー。サブネットYはサブネットXのためにメッセージの署名付きストリームを生成し、HTTPエンドポイントを介してこのストリームを公開します。サブネットXはサブネットY上のノードの1つからメッセージを引き出します。
ガーベジコレクション
あるサブネットが別のサブネット宛のメッセージをどのように蓄積していくのかがわかりました。この知識はもう一つの疑問を生みます。レプリカはどのようにして宛先サブネットがすでに消費したメッセージを削除するのでしょうか？コンシューマーサブネットがプロデューササブネットに、あるストリームプレフィックスがもう必要ないことを伝えることができるフィードバックメカニズムが必要です。この機構をシグナルと呼ぶ。
シグナルは、送信側サブネットがドロップできる逆方向ストリームの接頭辞を指定するXNetペイロードの一部です。サブネットXのノードがサブネットYのノードからXNetペイロードをフェッチするとき、実際のメッセージに加えて、Yノードはストリームヘッダを含みます。ストリーム・ヘッダはX t> Y通信の状態を記述する。
→フォワードストリームX>Yのメッセージインデックスの全範囲
→ 逆方向ストリーム（Y→X）の信号：
逆方向ストリームの各メッセージインデックスについて、Yはxがメッセージをガベージコレクトできるか（ACK信号）、メッセージを再ルートすべきか（REJECT信号）どうかを伝える。REJECTシグナルは宛先キャニスターが移動したことを示すので、xはメッセージを別のストリームにルーティングすべきです。
シグナルは古くなったメッセージを収集する問題を解決してくれますが、別の問題が発生します。幸いなことに、私たちは必要な情報をすでに持っています。リバース・ストリームにまだ存在するメッセージに対してのみシグナルを保持します。リモートサブネットがそのストリームからメッセージを削除したことに(メッセージインデックスの範囲を見て)気づいたら、対応するシグナルをヘッダーから削除することができる。
私の経験では、メッセージインデックスとシグナルの相互作用は、なかなか理解しにくいので、例を見てみましょう。下図は、XとYという2つのサブネットが通信中に挟まれた状態を表しています。サブネットXはYのストリームのプレフィックスとヘッダーを取得し、Xが新しいメッセージを取り込み、そのメッセージとシグナルをガベージコレクトできるようにします。また、Xは新たに受信したメッセージのシグナルを公開し、それに応じてインデックスを更新するため、Yは次の通信ラウンドでそのメッセージとシグナルを回収することができます。
2つのサブネットXとYがXNetプロトコルで通信しています。これまでの通信で、サブネットYはXのストリームからメッセージ[O, 1O )を消費し、最近メッセージ10と11を受信している。ここで、サブネットXはYのストリームのプレフィックスと一致するヘッダを受信し、Yがもう必要としないので、メッセージ10と11を自分のストリームから削除する。Xはまた、新しく受信したメッセージのシグナルをX->Yストリームヘッダに含め、 以前に消費したメッセージYıの廃止されたシグナルを削除する。
シグナルとストリームメッセージは、AURYNでは蛇が互いの尻尾を食べるようなもので、送信側はシグナルを見てメッセージを落とし、受信側はストリームバウンドが進んでいるのを見てシグナルを落とす。
ストリーム認証
ネットワーク上の2つのノードは互いに盲目的に信頼することができないので、XNetペイロードのコンテンツを検証するメカニズムが必要です。具体的には、ペイロードのストリームプレフィックスが、ストリームを生成したサブネット内のすべての正直なノードで同じであることを証明する必要があります。前回の記事では、ノードがSTATE TREESの閾値署名をコールリプライの信頼性証明として使用する方法について見てきました。XNetプロトコルは、同じトリックに依存している。ノードは、他のサブネットに向けられたストリームをステートツリーに含め、他のサブネットのノードに対する信頼性の証明として、閾値署名を使用する。
STATE TREEにおけるサブネットメッセージストリームのエンコーディング
概念的には、サブネットにメッセージを要求するノードは、応答を要求するク ライアントと異ならない。この類似性により、両方のケースで同じ認証メカニズムを使用することができる(※4)。
※4. 現在，XNetプロトコルとICのHTTPインタフェースでは，証明書の表現方法に若干の違いがある。HTTPインタフェースの証明書は、真正性をチェックするために必要なデータとハッシュをハッシュツリーという1つのデータ構造にまとめています。XNetプロトコルはメッセージの生データとハッシュ（ウィットネスと呼ばれる）を別々のデータ構造に分離しています。このように区別した理由は、純粋に歴史的なものです。XNetプロトコルを実装したのは、レスポンス認証よりもかなり前だったので、JOACHIM BREITNERの才覚の恩恵を受けることができなかったのです。JoachimはXNetの認証方式を出発点として、IC Interface Specificationのためにそれを簡略化しました。
証明書のツリー構造は、受信機でメッセージをバッファリングするのに便利です。受信機は、単一のブロックが収まるよりもわずかに大きなメッセージのプールを維持し、非同期に新しいメッセージをフェッチしてプールに追加し、証明書を適切にマージすることが可能です。この最適化により、サブネットの狭いXNetチャネルをより効率的に使用し、複数のサブネットからのメッセージを1つのブロックに含める場合の公平性を向上させることができます。
制限
XNetプロトコルは工学的に素晴らしいものですが、いくつかの固有の限界があります。
-> すべてのXNetメッセージはコンセンサスブロックを通過しなければならない。この制約により、プロトコルの理論的なスループットはブロックレートとサイズに制限されます。例えば、サブネットが1秒に1ブロック生成し、ブロックサイズが2MiBの場合、このサブネットのXNetスループットは最大でも2MiB/秒となります。
-> メッセージの配信には2ラウンドのコンセンサスが必要です（送信側で1ラウンド、受信側で1ラウンド）。この制約により、プロトコルのレイテンシはブロックレートによって制限される。受信側と送信側のサブネットの両方がブロックを生成するために1秒を必要とする場合、リクエストは宛先に到達するために少なくとも2秒を必要とする。応答を配送するにはさらに2ラウンド必要なので、呼の往復時間は少なくとも4秒になる。
コードリファレンス
この記事で紹介した設計を実装したコードへのポインタをいくつか紹介します。
The routing table.
The stream builder.
The payload builder and the xnet message buffer.
The xnet endpoint and the node proximity metric computation.
The induction of messages into the state machine state.
The mapping of streams to the tree structure, tree encoding, and validation.
謝辞
最後に、このプロトコルの開発において重要な役割を果たした人々に謝意を表する。
-> ALLEN CLEMENTは、XNetプロトコルのほとんどの機能の首謀者です。
-> DAVID DERLERは、Allenのアイデアの多くを改良し、プロトコルの正式な数学的仕様を書き上げました。
-> ALIN SINPALEANはIC REPLICAでプロトコルを実装し、多くの最適化を開発しました。 私の主な貢献はストリーム認証とTLSの統合です。