分散型システムにおけるグループチャットはどのように機能すべきか？

はじめに 最近、分散型P2PメッセンジャーデスクトップアプリであるKiyeovoの初期バージョンをリリースしました。グループチャットについて考えた時間の長さをどれだけ強調しても足りません。私が考案した各モデルには重大な欠陥があり、これがまさに「サーバーなし」という側面が痛いところでした。これには「最善の」方法はないと悟り、アプリを完全に分散型に保つためにはいくつかのトレードオフを選択しなければなりませんでした。 なぜサーバーがあるとグループが簡単になるのか 中央サーバーがあれば、これらの質問に答えてくれる信頼できる権威が存在します。 現在このグループに誰がいますか？ どのキーがメッセージを暗号化し、誰がそれを持つべきですか？ メッセージはどのような順序で発生しましたか？ 私はオフラインでしたが、何を見逃しましたか？ E2E暗号化されたアプリでさえ、メッセージを読むことはできませんが、これらの質問にはサーバーを使用しています。 Signalのサーバーはグループの連絡先リストを保存し（メッセージを転送します） Matrixのホームサーバーはグループの状態を保存し、イベントを順序付けします これらは、新しく追加されたユーザーにグループの状態を渡し、削除されたユーザーが更新やメッセージを受信できないようにします。コンテンツは暗号化されますが、調整（誰が参加しているか、最新の状態は何か、何が最初に来たか、何を見逃したか）は中央で処理されます。 サーバーを削除するとどうなりますか？ 連絡先リストを確実に知っている「場所」はなく、順序付けのためのシーケンサーマシンもなく、オフラインだった人々のための24時間年中無休のメールボックスもありません。 2. 他の分散型システムはどのように処理しているか — そしてなぜ私が別の道を選んだのか アプローチは多岐にわたりますが、以下に検討したものをいくつか挙げます。 (a) コーディネーションサーバーを維持する（Signal、WhatsApp、Matrix） コンテンツはE2E暗号化されますが、サーバー（またはホームサーバー）は依然として上記で説明したすべてを保持しています。ここでのグループキーのスキームは通常次のようになります。 Sender keys：Signal — 送信者ごとに共通鍵があり、メンバーが離脱するとキーがローテーションされます Megolm：Matrix — 送信者ごとにラチェッティングセッションがあり、メンバーの参加/離脱時にローテーションされます なぜダメか：これは中央集権化を含むため、却下しました。これは私の譲れない条件の一つでした。これはサーバーレスアプリの目的を損ないます — ネットワークは「特権的な」ポイントなしで動作し続ける必要があります。 (b) MLS / TreeKEM（RFC 9420） MLSはグループ暗号化の最先端技術です。各メンバーのキーはツリー状に配置されており、誰かを削除または追加すると、ツリーの一部のみが影響を受けます。つまり、非常にスケーラブルで、数千人のグループでも高速に動作します。 なぜダメか：MLSには、キー変更メッセージを配布する「配信サービス」が必要です。これをサーバーなしで、DHT経由で、ピアがオフラインになる可能性がある状況で行うのは大変です。また、ツリーは大規模なグループで真価を発揮しますが、Kiyeovoのグループは10人に制限されています。 (c) リーダーレスメンバーシップ 任意のメンバーが他のメンバーを追加または削除できるようにし、最終的に何らかのマージロジックで収束させます。権限は完全に分散化され、管理者は一切いません。 なぜダメか：2人が同時にメンバーシップを変更すると、ピアは実際には誰がグループにいるかについて異なる見解を持つ可能性があります。これらは最終的にマージできますが、マージルールは複雑になります。例えば、信頼できる時計なしでは順序に関する質問に答える方法がありません。「Xが送信したメッセージの前にキックされたのか、それとも後にキックされたのか？」という質問は、メンバーが「グローバルなイベント順序」に合意しない限り答えられません。プルーフ・オブ・ワーク層を持つことも考えましたが、それは重すぎるように思えました。 (d) 作成時にメンバーシップを固定する（例：Briarスタイルのプライベートグループ） 一部のP2Pアプリは、動的なメンバーシップをサポートしないことで、この問題全体を回避しています。メンバーセットはグループ作成時に固定され、誰も追加または削除しません。 なぜダメか：これは実際には私の最初のアイデアでした。しかし、招待やキックができないのは私にとって大きな欠点でした。これを書いている間、私は自分が参加しているグループのメンバーシップがどれくらいの頻度で変更されるか考えていますが、その答えは「それほど頻繁ではない」です。これにより物事はかなり単純化されたでしょうが、今はそれが完了し、動的なグループが機能しているので、それはかなり良いことです。 3. 実際に行った方法 ルール：サーバーは一切使用しない、収束を単純にする。 3.1 メンバーシップ：単一の作成者 各グループには、Ed25519キーで識別される単一の作成者がいます。他のすべてのメンバーは、作成者のキーを持っており、それを使用して更新が実際に作成者から来たことを確認できます。招待とキックができるのは作成者のみです。離れたいメンバーは署名された離脱リクエストを送信し、作成者がその削除を適用します。 長所：メンバーシップ状態の正当な書き手が一人しかいないため、「2人の管理者がパーティション中に異なる人をキックした」というようなマージすべき状況はありません。単一の作成者がいる場合、収束は単純です — これは実際にはアプローチ(c)の逆です。 短所：作成者は単一障害点です。作成者がデバイス（ID）を紛失したり、単にオンラインでなかったりすると、既存のメンバーは現在のキーで通信を続けることができますが、誰も追加または削除できません（ユーザーは離脱してメッセージを受信しないことはできますが、他のグループメンバーはXがグループを離れたという検証済みの通知を受け取ることはできません）。 3.2 キー：エポックごとのローテーション送信者キー エポックは単なる「グループバージョン」です。各エポックには、グループ全体で共有される単一のランダムな32バイトの共通鍵があります。メッセージは、そのキーを使用してXChaCha20-Poly1305で暗号化されます。それを配布するために、作成者は各メンバーに個別に（各メンバーのキーに対する公開鍵暗号化で）署名された制御メッセージ内にキーを封印し、その後、プライベートインボックスに配信します。 長所：再キーイングはO(n)の封印されたコピーです。グループの制限は10人 — 非常に軽量です。 コスト：エポック内のローテーションがないため、安定したグループ内での継続的な前方秘匿性はありません。 3.3 ローテーション：メンバーシップの変更がキーをローテーションする 参加、離脱、キックは新しいエポックを作成します。新しいメンバーには、参加したエポックのキーのみが送信されるため、古い履歴を読むことはできません。 libp2pでは、トピックは基本的に「チャンネル」です。「cars」という名前のトピックを購読すると、そのトピックからのメッセージを受信します。グループのリアルタイムメッセージはトピックにメッセージを送信することで機能します。もちろん、メッセージは暗号化されているため、誰かがトピックを推測したとしても（基本的に不可能）、メッセージを復号することはできません。 なぜトピックの推測が基本的に不可能だと言うのか？トピック名はグループキーから派生するため、キーをローテーションするとトピックもローテーションされます。削除されたメンバーは、新しいトピックを計算することはおろか、購読することさえできません。 3.4 グループ状態の配布：DHT内の追記型ログ グループメタデータ（メンバーシップ、送信者ごとのシーケンス境界（後述））は、2つのレコードタイプとしてDHTに格納されます。「最新バージョン」ポインタの連鎖（変更不可能なハッシュチェーンで連結された変更不可能なレコード） — 追記型ログであり、各エントリは作成者によって署名され、ハッシュで前のエントリにリンクされています。ペイロード（メンバーシップ更新）は、前述のエポックごとのキーで暗号化されます。 長所：オフラインメンバーにグループの「進化」の検証可能な履歴を提供します。また、DHTバリデーターは、グループを進歩させないものや、作成者によって署名されていないものを拒否します。 コスト：これはラストライターウィン（最後に書いたものが勝つ）ですが、単一のライターがいるため安全です。 3.5 順序付けとオフライン：送信者ごとのシーケンス、送信者ごとのバケット 各送信者は、(グループ、トピック/エポック) ごとにシーケンス番号を保持します — シーケンス番号は基本的に「これが私のN番目のメッセージです」ということです。受信者はその後、送信者からのギャップを検出できます。誰かがオフラインの場合、そのメッセージはDHTに保存されます。ただし、受信者ごとのバケットではなく、送信者ごとのバケットになります — これは珍しいので説明します。各送信は、現在のエポックの送信者自身のバケットに書き込まれます。ユーザーがオンラインになると、オフラインメッセージをすべて取得するために、グループ x メンバー x クローズされていないエポックのバケットをスキャンする必要があります。なぜか？代替案は私の意見ではもっと悪いからです。 受信者ごとのバケットを持つ — メッセージを送信するとき、送信者はグループ x メンバー x クローズされていないエポックのバケットに書き込む必要があります。さらに、送信者ごとのクローズされていないエポックを追跡する必要があり、これはまったく別の問題と非効率性のセットです。 共有バケットを持つ — バケット名には、他のユーザーによる改ざんを防ぐために、その所有者の公開署名が含まれています（DHTバリデーターがこれを強制します）。私が考えたことの一つは、すべての公開署名を含めることでした。 [2]