原文
SPREAD: Extending GossipSub with Efficient Anonymous Dissemination — MatheusFranco99 (2026-07-02)
著者: Diogo Cardoso, Matheus Franco, Rodrigo Rodrigues
謝辞: この研究は、リスボン大学に授与された SSV Network DAO からの助成金によって支援されました。
ドラフト仕様は libp2p/specs に提案されました (PR #726)。
参照実装は go-libp2p-pubsub で公開されています (PR #717)。
概要
GossipSubは、イーサリアムのようなエコシステムにおける社会的に重要なプロトコルの基盤となる主要な通信インフラです。ゴシッププロトコルのいくつかの特性、すなわち堅牢性、スケーラビリティ、シンプルさは、これを興味深い通信基盤にしています。しかし、匿名性（メッセージの真の送信元を隠すこと）という重要な特性は、送信者に対する標的型攻撃を避けるために望ましいと時々言及されますが、実際にはGossipSubでは達成できないことがよく知られており、標的型サービス拒否（denial-of-service）の道を開いています。Dandelion++のようにランダムウォークで伝播を開始するという自然な防御策は、匿名性を獲得しますが、イーサリアムコミュニティがコンセンサス層には実行不可能とすでに判断したレイテンシコストを伴います。スロット時間が12秒から6秒に短縮される予定は、その予算をさらに厳しくするだけです。
私たちは、両方の長所を目指すGossipSubの拡張であるSPREAD（Secure Peer-to-Peer Relay for Efficient Anonymous Dissemination）を提案します。これは、送信者の匿名化解除に対するハードルを上げると同時に、伝播効率を実際に向上させます。SPREADは2つのメカニズムを組み合わせています。1つは、パフォーマンスに大きなペナルティを与えることなくメッセージの送信元を不明瞭にするローカルなランダムウォーク、もう1つは、コストのかかる長距離ホップを避けるために近くのノードを足がかりとして使用することで、低レイテンシで世界中に到達する地理的に指向された伝播です。私たちはこれをgo-libp2p-pubsubのフォーク上でオプトインで後方互換性のある拡張として実装し、GossipSubおよびDandelion++と比較して、実際の実装を用いて評価しました。私たちの目標は、送信元の区別不能性が敵対者の観測能力に依存する定量的な特性であり、絶対的な保証ではないため、匿名化解除を完全に防ぐことではなく、そのハードルを上げることであることに注意してください。
用語と定義
Curious Nodes (Honest-but-Curious Observers) - プロトコルを正しく実行するが、観測されたトラフィックパターンから追加情報（例：特定のメッセージの送信元）を推測しようとするノード。
Fanout - ノードが伝播ステップ中にメッセージを転送するピアの数。
Random Walk - 各ノードがメッセージを単一のランダムに選択されたピアに転送する（確率的な分岐を伴う可能性のある）転送戦略。
Virtual Coordinates - 合成幾何学的空間のノードに割り当てられたレイテンシ推定座標で、直接測定せずにネットワーク距離を推定できる。
Bernoulli Trial - それぞれの確率値によってパラメータ化された2つの結果（成功/失敗）を持つ確率的決定メカニズム。
Stretch - 実際のエンドツーエンド配信レイテンシと、送信者と受信者の間の直接的（通常は最適）な通信レイテンシの比率として定義されるパフォーマンス指標。
Deanonymization Accuracy - 敵対者が、攻撃者によって制御されるノード間のタイミング観測に基づいて、メッセージの元の送信者を正しく推測する割合。
Cluster - 近くのノードのグループ。つまり、仮想座標空間で互いに近く、したがって低レイテンシで通信するノード。
Cobra Walk (Coalescing-Branching Random Walk) - 各ノードが分岐係数で与えられた数のランダムな隣接ノードにメッセージを転送するランダムウォークのバリアントで、常に単一のピアに転送するのではなく、ウォークが時折分岐することを可能にする。
Voronoi Diagram (Dirichlet Tessellation) - 参照点（重心）のセットに従って空間を領域に分割するもので、各領域はその重心に他のどの重心よりも近い空間の部分を含む。
動機
ゴシッププロトコルが特定のメッセージの元の送信者の匿名性を保護するのに役立つという一般的な理解にもかかわらず、GossipSubの開発者や多くのユーザーは、それがそのような保証を提供するように設計されておらず、また提供できないことを知っています。特に、少数のリスナーノードでメッセージのタイミングを観察することで、GossipSubレイヤーに対する単純な攻撃が可能であり、集中型コーディネーターがタイミングを相関させてゴシップメッセージの真の送信元を推測することができます。この種の受動的、タイミングベースの攻撃は、最初にBitcoinで実証され、少数のスーパーノードから発信されたトランザクションがIPアドレスにリンクされました（Biryukov et al.、Fanti and Viswanath）。その後、数エポックにわたるアテステーション（証明）の伝播を監視することで、イーサリアムバリデータをそのピアIDとIPアドレスにマッピングできることが示されました（Sharma et al.; Heimbach et al.; Rhea）。これは、GossipSubがメッセージパスを不明瞭にするためにランダム化された転送を使用しているにもかかわらず可能です。なぜなら、バリデータの直接のピア（つまり、ゴシップオーバーレイにおけるバリデータの直接のピア）は、他のノードよりも著しく早くメッセージを一貫して受信し伝播するからです。そのため、数十個のリスナーノードを展開することで、数エポック後にはリスナーノードの1つが直接のピアになり（そしてその後数エポックにわたってそうあり続ける）、その可能性が非常に高くなります。したがって、複数のコンセンサス層エポックにわたってメッセージを最初に受信したリスナーノード（およびそのメッセージがどのネットワークアドレスから来たか）を追跡することで、コーディネーターは最終的に高い信頼度でバリデータをそのネットワークIDに確実にマッピングできるようになります。一度特定されると、バリデータは選択的に標的とされ（例：サービス拒否（DoS）を介して）、職務の欠落によるスラッシングや経済的攻撃につながる可能性があります。決定的に重要なのは、この匿名化解除がいかなる特権アクセスにも依存せず、少数の行儀の良い（正直だが好奇心旺盛な）オブザーバーでトラフィックを傍受するだけで実行できることです。
この問題は、ゴシッププロトコルの設計における決定的な緊張関係に根ざしています。ファンアウトを増やし、より一般的に伝播速度を向上させることは匿名性を低下させ、一方、低いファンアウトで露出を制限することは、伝播速度を犠牲にしてプライバシーを向上させます。残念ながら、GossipSubは適切なバランスを取ることができません。匿名化解除を可能にするのに十分な構造情報を漏洩させながら、遅延とオーバーヘッドを増幅するレイテンシに鈍感なパスのために非効率なままです。
この種の攻撃に対する防御策として、これまでの研究では、特にDandelionとDandelion++が提案されています。これらは、ランダムウォークベースの匿名化フェーズで伝播を開始することで、より強力で形式的に分析された送信者匿名性保証を提供します。しかし、これらの保証はかなりのレイテンシコストを伴い、レイテンシに敏感な設定での採用に対する根本的な障壁となっています。実際、イーサリアムコミュニティは、「レイテンシの制約のため[…]この提案Dandelion++はイーサリアムのコンセンサス層には実行不可能である（少なくとも強力な匿名性保証のためには）」と結論付けました（EthResearch discussion）。この緊張関係はさらに激化するでしょう。イーサリアムのEIP-7782でスロット時間が12秒から6秒に短縮される計画があるため、ゴシップ層はさらに厳しいパフォーマンス要件に直面し、今日のデプロイメントでは必要なパフォーマンスと望ましい送信者匿名性防御の両方を提供しなければならないという複合的な課題が生じています。
この課題に対処するため、私たちはプロトコル拡張として実装される新しいゴシッププロトコルであるSPREADを提案します。これは、GossipSubと比較して送信者の匿名化解除に対するハードルを上げると同時に、より効率的な伝播を提供します。私たちのアプローチは2つの原則に基づいています。1つは、メッセージの送信元を不明瞭にするランダムウォークによる匿名性、もう1つは、トポロジー認識型ホップ選択による低レイテンシです。私たちは、低レイテンシを優先するランダムウォークホップと、コストのかかる長距離パスを避けるために、可能な限り近くのノードを足がかりとして通信しようとする広域ホップを分離します。この設計は、ブロックチェーンバリデータメッセージング、匿名通信システム、検閲耐性プラットフォームなど、低レイテンシと送信者プライバシーの両方を必要とするアプリケーションに適しています。
SPREADの設計：洞察と概要
Guerraoui et al.による最近の形式的な研究は、匿名性のために設計されたゴシッププロトコルが強力なランダムウォークコンポーネントを含む必要があることを示しました。そこでは、各ノードがメッセージを単一のオーバーレイ隣接ノードに頻繁に転送し、送信元の特定を困難にします。この技術は、例えばDandelionプロトコルファミリーで採用されており、ランダムウォークベースの匿名化フェーズから始まり、その後確率的に高いファンアウトを持つ伝播フェーズに切り替わります。
しかし、これにより問題が生じます。ランダムウォークフェーズでは、メッセージは時間ステップごとに最大1つのピアに送信されるため、個々のステップが不運にも遅いパスや遠いパスを横断する可能性があります。これは、単一の遅いホップが平均的なエンドツーエンドパフォーマンス（ストレッチ、つまりオーバーレイと直接メッセージ接続の比率で測定）を著しく損なうのに十分であるため問題です。この問題は、イーサリアムのようなブロックチェーンがゴシップ基盤の上に多段階プロトコルを重ねているという事実によってさらに増幅されます。さらに、パフォーマンスを向上させるための対策、すなわちメッセージが複数のピアに並行して送信されるより効率的なモードへの切り替えを早めることは、初期フェーズでの単一の長いホップに対して依然として脆弱であるだけでなく、意図された匿名性保証と直接的な緊張関係にあります。
このトレードオフを効果的に乗り切るため、私たちはノードの地理的分布が、世界の最も人口密度が高く経済的に発展した地域（例：米国東海岸と西海岸、ヨーロッパ、アジアなど）に対応するクラスターを自然に形成するという洞察を活用します。これにより、SPREADの設計ではノードをクラスターに編成し、同じクラスター内のノード間のネットワークレイテンシが低いという特性を持たせ、クラスター内での高速なマルチホップ伝播を可能にします。この設計決定がなされると、クラスター内通信を活用して、パフォーマンスに大きなペナルティを与えることなくプライバシーを構築できるランダムウォークを実行し、時折クラスター間通信に切り替えてグローバルな伝播を行うことができます。
2つ目の課題は、クラスター間メッセージステップも、慎重に管理しないとエンドツーエンドのパフォーマンスに非常に大きなペナルティを与える可能性があることです。例えば、ヨーロッパから米国東海岸へのメッセージを、アジアや中東を経由するオーバーレイホップで送信することは避けたいでしょう。これを避けるためには、効率的な広域伝播を考案する必要があります。このステップはパフォーマンスにとって非常に重要であり、私たちのプロトコルはすでにクラスター内通信を通じて匿名性を達成しているからです。この目的のために、SPREADはクラスター間メッセージホップが隣接するクラスター内のノードと行われるように試み、それらがより遠いクラスターに到達するための足がかりとして使用できるようにします。理想的なルーティングシナリオでは、クラスターとそれらが高レベルのオーバーレイを通じてどのように接続されているかについて、単一のグローバルビューが存在します。これはディリクレテッセレーションに対応し、空間をクラスターの重心のセットに従って領域に分割します。これにより、理想的なルーティングは、ディリクレテッセレーションに従って隣接するクラスター内のオーバーレイピアにのみクラスター間メッセージを送信します。
図1：インターネットホストのデータセットの地理座標。クラスタリング情報とボロノイセルが追加されています。理想的な広域ゴシップステップは隣接するセル間でのみ発生しますが、これにはセル分割のグローバルに調整されたビューが必要となります。
しかし、私たちの目標は、これらのクラスターとその高レベルの接続のためのグローバルビューに依存しない、完全に分散化されたプロトコルを持つことです。この目的のために、私たちは代わりに、各ノードが自身のクラスターのローカルビューを構築することで、理想的なルーティングを近似することにしました。私たちの主な洞察は、各ノードにユークリッド座標のセットを安全に割り当てる仮想座標スキーム（Vivaldi、Newton）を使用して、理想的なルーティングを近似することです。このような座標が配置されると、各ノードは、仮想座標空間で最も近いt%のオーバーレイ隣接ノードとして、自身のクラスターのビューを定義します。これにより、各ノードは、自身のクラスターの隣接メンバーを構成するピアのサブセットをローカルに決定できます。さらに、仮想座標を活用して、理想的なクラスター間ルーティングを完全に分散化された方法で近似することが可能です。このアイデアは、自然なナビゲーションに触発されたもので、遠いノードと合理的にうまく整合している非クラスターノードのセット内に、より近い隣接ノードが存在する場合、より遠い隣接ノードへの直接ジャンプを常に避けるというものです（直感的には、足がかりとして機能するより近い目的地があることを意味します）。この場合、「うまく整合している」とは、より近いノードへの角度が、遠いノードへの角度の構成可能な角度間隔内にあることを意味します（この角度はユークリッド空間の仮想座標によって与えられます）。これにより、各ノードは、非クラスターオーバーレイピアのセットを2つのグループにローカルに分割できます。1つは、より近い「足がかり」メンバーを持つため、クラスター間またはあらゆる種類の転送に使用すべきではないもの（occluded_remoteと表記）、もう1つは、そうではないため、クラスター間ホップに適格なもの（unobstructed_remote）です。
プロトコルの概要
プロトコルには、並行して実行される2つのコンポーネントがあります。1つはオーバーレイピアとそのセキュアな仮想座標のセットを維持するためのアルゴリズム、もう1つはゴシップメッセージを送受信するための主要プロトコルです。ノードiのオーバーレイ隣接ノードは、前述の基準に従って、cluster_i、occluded_remote_i、unobstructed_remote_iの3つのサブセットに自動的に分割されます。
このオーバーレイ状態が整ったところで、クラスター内ランダムウォークを匿名性確保のために、unobstructed_remote隣接ノードを介したクラスター間効率的伝播と組み合わせるという直感に基づいて、メッセージをブロードキャストするプロトコルを簡単に定義できます。これらの2つの選択肢のいずれかを実行するかどうかの決定は、伝播すべきメッセージを受信した際に、システムパラメータに従ってバイアスされたコインを投げるだけで行われます。プロトコルの擬似コードを次に説明します。クラスター情報とオーバーレイ隣接ノードの形成が完了した後のメッセージのブロードキャスト方法に焦点を当てます。
1: # constants:
2: ρintra # Branching probability (intra-cluster)
3: ρinter # Inter-cluster dissemination probability
4: fanoutintra # Number of intra-cluster peers when branching
5: fanoutinter # Number of peers for inter-cluster dissemination
6: # state variables:
7: neighbors_i # Set of overlay neighbors, partitioned into:
8: cluster_i # Subset of closeby neighbors in Pi’s cluster
9: unobstructed_remote_i # Subset of remote neighbors that are not efficiently reachable via another neighbor
10: occluded_remote_i # Subset of remote neighbors that may be reachable via another neighbor
11: upon receiving or publishing message m do
12: INTRACLUSTERSPREAD(m)
13: INTERCLUSTERSPREAD(m)
14: procedure INTRACLUSTERSPREAD(m)
15: if Bernoulli(ρintra) = 0 then
16: send m to 1 peer in cluster_i selected uniformly at random
17: else
18: send m to fanoutintra peers in cluster_i selected uniformly at random
19: procedure INTERCLUSTERSPREAD(m)
20: if Bernoulli(ρinter) = 1 then
21: send m to fanoutinter peers in unobstructed_remote_i selected uniformly at random
プロトコルのイテレーションには、クラスター内伝播とクラスター間伝播の2つのステップが含まれます（10行目から11行目）。クラスター内伝播は、コブラウォーク（Coalescing-Branching Random Walk）アルゴリズム（Dutta et al.）に触発されたもので、ローカルなベルヌーイ試行の出力に応じて分岐する可能性のあるランダムウォークで構成されます（15行目）。分岐する確率はρintraで表されます。出力がゼロの場合（16行目）、ノードは単にクラスター内のランダムなピアを均一に選択し、ランダムウォークフェーズを表します。それ以外の場合、出力が1の場合（17行目）、ノードは自身のクラスター内で均一にランダムに選択されたfanoutintra個のピアにメッセージを拡散し、より高速なクラスター内伝播を実現します。クラスター間伝播はグローバルな伝播を担当し、別のローカルなベルヌーイ試行（20行目）に従って時折発生します。この試行のパラメータはρinterです。試行の出力がゼロの場合、ノードは他のクラスターと相互作用せず、すべての通信を自身のクラスター内に保ちます。出力が1の場合（21行目）、ノードは遠すぎない（つまり、足がかりとして機能できるより近いノードによって座標空間で「隠されていない」）隣接ノードにメッセージを拡散し、合計でfanoutinter個のピアを均一な方法でランダムに選択します。ピアが同じメッセージを複数回伝播することに注意してください。アルゴリズムがこのような重複した動作を停止するロジックを含まない理由は、匿名性を保証するためです。特に、ノードがメッセージを一度だけ伝播するプロトコルでは、Bellet et al.は、攻撃者が通信タイムスタンプを追跡することで送信元を特定する可能性が高いことを示しています。しかし、新しいメッセージを継続的に生成する実際のアプリケーションでは、ネットワーク輻輳を避けるために終了メカニズムを提供する必要があります。Kermarrec et al.が説明しているように、通常、このパラメータはプロトコルの信頼性を制御し、実際のネットワークサイズでは小さな値で十分です。それでも、追加の信頼性メカニズムを追加することができ、実際、GossipSubのようなフレームワークには、既に見られたメッセージのリストをアドバタイズするハートビートメッセージや、欠落したメッセージを取得するための「プル」プロトコルリクエストなどが存在します。
このメッセージプルメカニズムは、さらに2つのシナリオで堅牢性を高めるのに役立ちます。第一に、チャーン（ノードの頻繁な参加・離脱）の下では、ノード障害や離脱の連続が直接伝播を効果的に妨げる可能性があり、ハートビートとプルメカニズムによってノードは失われたメッセージを回復できます。第二に、ビザンチンノードに対する防御に役立ちます。単純な暗号化は、そのようなノードがメッセージの内容を改ざんするのを防ぎますが、彼らは意図的にメッセージを遅延させたり、転送を拒否したりして、進行を危険にさらす可能性がありますが、ハートビートとプルがこれに対抗します。
プロトコル拡張の使用とGossipSubピアとの共存
SPREADは、GossipSubのオプトインで後方互換性のある拡張です。GossipSubの既存のハンドシェイクフィールドを通じてアドバタイズされ、両方のピアがそれをサポートしている場合にのみ接続でアクティブになります。SPREADメッセージは、標準のRPCエンベロープ内の追加フィールドでフラグ付けされるため、拡張をサポートしないピアはマーカーを単に無視し、標準のGossipSubにフォールバックします。これにより、混在デプロイメントが可能になり、ネットワーク全体がアップグレードされる前に部分的な匿名性とパフォーマンス上の利点が得られる段階的な採用パスが可能になります。クラスター構築は、Vivaldiプロセス（Newtonチェックで保護）によって維持される仮想座標に依存しており、これがSPREADがノードの通信プロファイルに加える唯一の追加です。
評価
私たちはSPREADを、匿名化解除攻撃に対する耐性と、広域ネットワークでのメッセージ伝播効率という2つの補完的な側面から評価します。イーサリアムにデプロイされているGossipSubと、匿名性向上を目的とした研究提案であるDandelion++と比較します。SPREADはgo-libp2p-pubsubの拡張として実装されているため、実際のプロダクションコードを評価できます。設定可能なレイテンシと帯域幅を持つ仮想リンクを通じて実際のインプリメンテーションを接続するパケットレベルシミュレーターであるsimnet上で実行します。現実的なデプロイメントを反映するため、地理的に分散したノード間の実際のラウンドトリップ時間測定値を含むグローバルインターネットデータセットからネットワークトポロジーを抽出し、複数のトポロジーをサンプリングして結果を集計します。Dandelion++も同じスタック上に実装されているため、3つのプロトコルすべてが同じ実装を共有し、伝播戦略のみが異なります。
公平な比較のため、3つのプロトコルを、各ノードが期待値として同じ数のピアにメッセージを転送するように設定します。つまり、同じノードあたりの帯域幅予算を共有します。GossipSubのデフォルトメッシュサイズである6を目標の期待ファンアウトとして使用し、SPREADの4つのパラメータとDandelion++のパラメータをそれに合わせて調整します。匿名性は、最初のタイムスタンプ推定器の下での匿名化解除精度メトリックを通じて測定します。特定の割合のCurious Nodesに対して、多くの攻撃者の配置をサンプリングし、各メッセージについて、Curious Nodeに最も早いタイムスタンプで配信したノードを送信者として推測します。精度は、正しい推測の割合です。パフォーマンスは、メッセージの実際のエンドツーエンド配信時間と、その送信者と受信者の間の直接通信レイテンシの比率として定義される、絶対的な配信レイテンシとストレッチメトリックの両方を通じて測定します。
匿名性
すべてのプロトコルは、敵対者がネットワークのより大きなシェアを制御するにつれて脆弱になりますが、その程度は著しく異なります。GossipSubが最も露出しています。Curious Nodesがわずか5%の場合でも、攻撃者はすでに35%以上のケースで成功し、20%では54%に上昇します。Dandelion++は最も強力な匿名性を達成し、Curious Nodesが5%の場合で10%未満、20%の場合でも約20%にとどまります。これは、そのランダムウォークによる難読化フェーズによるものです。SPREADはその中間に位置します。Curious Nodesが5%の場合、その精度は20%台前半であり、20%では約45%に達します。したがって、GossipSubと比較して敵対者の成功率を低下させながら、Dandelion++に対するわずかな匿名性ギャップを、著しく優れた伝播効率と引き換えに受け入れています。
図2: GossipSub、Dandelion++、SPREADにおける、Curious Nodesの割合の関数としての匿名化解除（攻撃）精度。
パフォーマンス
SPREADは、3つのプロトコルの中で最も効率的な伝播を達成します。ストレッチ閾値が3の場合、SPREADでは90%以上の配信が完了しますが、GossipSubでは約83%、Dandelion++ではわずか50%です。このギャップはテール部分にも持続し、SPREADとGossipSubはDandelion++よりもかなり早く完全なカバレッジに近づきます。全体として、SPREADはGossipSubと比較して平均ストレッチを約23%削減し、Dandelion++と比較して約67%削減します。また、重いテールをさらに著しく縮小し、99パーセンタイルのストレッチをそれぞれ約39%と74%削減します。絶対レイテンシについても同じ順序が成り立ちます。SPREADの配信の半分は100ミリ秒未満で完了しますが、GossipSubでは40%、Dandelion++では10%です。このテール挙動は、イーサリアムのように多段階プロトコルがゴシップの上に重ねられている場合、各追加ステップが単一ホップのレイテンシペナルティを増幅するため、特に重要です。
図3: 3つのプロトコルにおける、すべての送信者-受信者ペア間のストレッチの累積分布。
図4: すべての送信者-受信者ペア間の絶対配信レイテンシの累積分布。
チューニング
最後に、SPREADの4つのパラメータが匿名性とパフォーマンスをどのようにトレードオフするかを研究します。すべてのパラメータにおいて、ファンアウトまたは分岐確率を増やすとストレッチは低下しますが、同時に攻撃精度は上昇し、その逆もまた然りです。これは、SPREADが連続的に調整可能であることを確認します。低い値はプライバシーを最大化し、高い値はパフォーマンスにバランスを傾けます。クラスター内パラメータはストレッチプロファイルを支配し、クラスター間確率は主に匿名性調整ノブとして機能し、パフォーマンスに対する効果は逓減します。上記の比較で使用された設定は、このスペクトラムの両極端ではなく、意図的にバランスの取れた点を目標としています。
図5: SPREADの単一パラメータ変更における平均ストレッチと匿名化解除精度の関係（Curious Nodes 10%の場合）。各線は1つのパラメータの連続する値を結んでいます。
全体として、これらの結果は、イーサリアムの現在の設計の2つの側面が同時に改善できることを示しています。SPREADに切り替えることで、GossipSubと比較して匿名化解除精度が低下し、平均およびテールストレッチも改善されます。Dandelion++と比較すると、SPREADは匿名性の一部を犠牲にしますが、イーサリアムのコンセンサス層のようなレイテンシに敏感な設定では強力な匿名性提案を非実用的にするレイテンシオーバーヘッドを回避します。
1投稿 - 1参加者