Nym mixnetのプライバシー、スケーラビリティ、レイテンシーに関する実証研究

Nymが採用しているミックスネットワークのデザインであるLoopixの開発に取り組む中で、私たちは、私たちのデザインが提供する匿名性を経験的に測定するために、離散イベントmix networkシミュレータを開発しました。 これは、ネットワークトポロジー、ユーザー数、送信レート、ミキシング遅延などの異なるネットワークパラメータを指定して、匿名性メトリクス（End to End Entropy と送信者と受信者のサードパーティのアンリンカビリティを評価できる初めてのシミュレータである。

このブログ記事では、Nym mixnetのスケーラビリティ、匿名性、レイテンシーの傾向を分析し、固定カスケードトポロジー（fixed cascade topologies）やP2Pネットワークなどの他のアプローチと比較するために行った研究の一部を紹介しています.このシミュレータは現在進行中の研究の一部であり、近日中に完全な公開を予定しています！

# 匿名性のトリレンマ：スケーラビリティ、匿名性、レイテンシー
この分析では、3層のNym mixnetを考え、各ノードが平均して1秒間に1000パケットを処理する能力を持つものとします（この仮定は、現在のNymテストネットの性能と互換性があります）。

# 匿名性の測定方法は？
まずは、匿名性を測るための指標を説明するところから始めましょう。匿名通信ネットワークの目的は、ネットワークのメタデータを隠すことで、誰が誰と通信しているかという情報を隠すことです。 敵の先験的な知識と能力に応じて、異なる指標を使用することができます。 本ブログでは、アプリオリな知識を持たないグローバルなネットワーク盗聴者を考えることにする。このような場合の匿名性の一般的な尺度は、匿名セット( anonymity set)であり、これは、我々のメッセージが攻撃者によって混乱させられる可能性のある、他のパケットのセットの大きさを反映します。しかし、ネットワークとその中のすべてのやり取りを盗聴するグローバルな受動的敵対者は、各発信パケットが観測された受信パケットとリンクしていることに異なる確率を割り当てることができます。匿名集合のメンバーによって確率が異なると、攻撃者に多くの情報を与えてしまいます。そこで、情報理論的な指標である平均情報量（Shannon entropy）の概念を用いて、経験的に匿名性を定量化する[2, 3]。エントロピー（Entropy）とは、ランダム性の尺度であり、言い換えれば、ランダムな変数に含まれる情報の予測不可能性である。事象の可能性が高ければ高いほど、その変数に含まれる情報は少なくなる。一方、エントロピーの増大は不確実性の増大である。 例えば、私が毎日同じ時間に電話をかけているという事実は、ほとんど情報を含んでいないため、エントロピーが高いのです。しかし、もし私が突然弁護士に何度も電話をかけたとしたら、それは私が法的な助言を必要としているという合図かもしれません。したがって、その出来事には多くの情報が含まれることになります（そしてエントロピーは小さくなります）。 匿名ネットワークに関して言えば、パケットを送信元に結びつけるのが難しいほど（つまり、敵の観測が混乱するほど）、エントロピーは高くなります。

また、敵が何らかの先験的な知識を持っている場合の匿名性を測る指標として、送信者と受信者のアンリンク性がある。 

# スケーラビリティ
匿名性は集団を好むので、スケーラビリティはミックスネットワークの重要な特性の1つです。

Nymは、Loopixの設計に基づき、ノードを階層化し、iレイヤーの各ノードが前後のレイヤーの各ノードと接続される階層型トポロジーに配置する。 このようなトポロジーは水平方向に拡張できるため、Nym mixnetは、End to Endのレイテンシーに悪影響を与えることなく、大規模なユーザーベースをサポートするためにノードを用意に追加することができます。 決定的なのは、Nymが提供するプライバシーは、ネットワークが成長するほど、つまり、ネットワークに流入するトラフィックが増えるほど、匿名性が高まるということです：

# Chaumian mixnet
従来のChaumian mixnetは、シングルカスケードトポロジーとbatch-and-reorder mixing技術を使用しているため、トラフィック量が増加すると、非常にスケールが小さく、大きなレイテンシーのオーバーヘッド（latency overhead）が発生する。 従来のChaumian mixnetでは、トラフィック量が多いときだけでなく、少ないときにも、各ノードが処理のためにフルバッチ（full batch ）を収集するのに長い時間待つため、高いレイテンシオーバーヘッドが生じることが分析から分かっています。したがって、ユーザーは自分のパケットのEnd-to-Endの待ち時間を制御したり予測したりすることができない。

![Screenshot 2024-09-02 at 13.11.10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3672851/da2e9dce-d11e-4499-09ca-23245ccea937.png)

シングルカスケードに代わるアプローチとして、複数のパラレルカスケード（Chaumの最新のcmixデザイン）を使用することができます。このようなアプローチにより、ネットワークをスケールさせることができますが、それでも匿名性は常に一定で、バッチの固定サイズに制限されます。 したがって、ユーザー数が増えても、ネットワークの匿名性が高まるわけではありません。 マルチカスケードミックスネットとは対照的に、Nymは大量のユーザーに対してより優れた匿名性を提供し、E2Eレイテンシーを桁違いに低減します¹。

# P2P

一方、HOPRのようなP2Pネットワークは、スケールアップが容易な反面、ユーザー数の増加にもかかわらず、匿名性が非常に低いです。実証実験の結果、同じユーザー数とEnd-to-Endレイテンシであれば、NymはP2Pトポロジーを持つネットワークよりもはるかに大きな匿名性を提供します¹,²。

![Screenshot 2024-09-02 at 13.10.52.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3672851/60db677b-5672-d9ce-acea-d896a0f308c0.png)

# トラフィックのカバー
見たように、Nymネットワークが提供するプライバシーはユーザー数が増えれば増えるのに対し、P2Pネットワークはユーザー数が増えても匿名性が非常に低い（一定である）ことがわかります。

匿名性のレベルを向上させる一つの方法は、カバートラフィックを導入することです。しかし、我々の分析によると、HOPRなどのP2Pネットワークでは、Nymが提供する匿名性のレベルに達するには、膨大な量のカバートラフィックを必要とします：
![Screenshot 2024-09-02 at 13.11.51.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3672851/2fbd4622-f254-d3ac-9571-7cd7650fd9ef.png)

例えば、10万人のユーザーを持つP2Pネットワークにおいて、Nym mixnetが1.6万人のユーザーに対してカバートラフィックを行わず、同じEnd to Endのレイテンシーで同様の匿名性を達成するには、各ユーザーは1つのリアルパケットに対して10のカバーパケットを生成しなければならないことが上記のプロットで示されました！ ネットワークの規模が大きくなるにつれ、P2Pアプローチでは、合理的な匿名性を提供するために、より多くのカバートラフィックが必要になり、ピアは強力なマシンに配置される必要があります。

Nym mixnetでは、ユーザーによって生成されるループカバートラフィックと、mix nodeによって生成されるループカバートラフィックの2種類のカバートラフィックを展開します。 なぜさまざまな種類のカバートラフィックが必要なのかは、こちらをご覧ください。重要なのは、他の設計とは対照的に、Nymは調整可能なカバートラフィックを使用していることです。つまり、少数のユーザーに対しては、カバーパケットの数を増やして望ましい匿名性を達成できるのです。ユーザー数が増え、ネットワークに流れる実際のパケットの量が増えれば、匿名性を犠牲にすることなく、カバートラフィックを任意に調整することができます！

そこで、Nym mixnetのユーザー数を変化させた場合、どの程度のカバートラフィックが必要になるかを、エントロピーが約10であると仮定して解析します。

![Screenshot 2024-09-02 at 13.12.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3672851/55a4efae-58c5-1a41-14b1-1e2f175aca1e.png)
このように、少ないユーザー数では大量のカバートラフィックを必要としますが、ユーザー数の増加に伴い、その量は急速に減少しています。 5000人のユーザーを対象とした実験では、望ましい匿名性を実現するために、すでにカバートラフィックは必要ありませんでした（もちろん、匿名性をさらに高めたり、通信パターンを隠すためにカバートラフィックを使用したい場合もありますが）。ユーザー数が100万人、1000万人と増えていった場合を想像してください！そのため、Nymのネットワークに参加するユーザーが増えれば増えるほど、匿名性が高まり、カバートラフィックが必要なくなるのです。つまり、単純なP2P設計とは異なり、ネットワークはプライバシーを効率的に拡張することができるのです！

# トラフィックを増やすとNymのmixnetが高速化する
先に示したように、Nymは水平方向のスケーラビリティにより、数百万人のユーザーをサポートすることができます。ユーザーが増えれば、新しいサーバーを追加してウェブサイトを拡張するのと同じように、新しいmixnetを追加することでNymを拡張することができます。Nymのユーザー数が増えることで、匿名性を犠牲にすることなく、指数分布の平均パラメータを調整し、End to Endの待ち時間を短縮することができるため、これは非常に重要です。その結果、Nym mixnetは、ノードごとのミキシング遅延が少なくなり、「より速く」なります。つまり、より多くのユーザーがネットワークに参加すればするほど、匿名性が高まるだけでなく、誰もが高速化の恩恵を受けられるのです！

![Screenshot 2024-09-02 at 13.12.52.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3672851/1a4854fd-77a4-080f-858c-7b0f6693f93c.png)

# 結論
本シミュレータにより、様々なネットワークパラメータやユーザベースがNym mixnetの匿名性や性能に与える影響を経験的に測定することができます。これまで示されてきたように、Nymは現時点で最もスケーラブルで匿名性の高いmixnetデザインである。 Nymは、利用者の増加によって生み出される匿名性と高速性という具体的なメリットを得るために、多くのユーザーベースと幅広いアプリケーションやサービスに対応できる汎用的なmixnetを提供します。 P2Pネットワークは、拡張性は高いものの、各ピアが大量のカバートラフィックを生成するか、ミキシング遅延が大きくならない限り、匿名性は非常に低くなります。 しかし、そのため、実世界のネットワークへの適用には大きな制限があります。さらに、P2Pネットワークは、ユーザーのプライバシーを著しく損なういくつかの攻撃に対して脆弱である。

このシミュレータコードにより、研究者はさまざまなmixnet デザインでさまざまなパラメータをテストし、直感を検証したり無効化したりできる実証結果を得ることができ、またエンドユーザーに受け入れられるパラメータを持つ「実世界」のmixnet を作成するために使用することができるという点で画期的です。 Nymテストネットでは、このシミュレータを使って、今後数ヶ月間、ミキシング遅延やカバートラフィックの微調整を行い、エンドユーザーに最高の匿名性とパフォーマンスを提供することを目指します。Loopixの設計に基づくミックスネットでも、シミュレーションでパラメータを正しく設定し、実際のユーザーのトラフィックを考慮しなければ、Katzenpostやそのフォークのようなコードベースでは、ユーザーのプライバシーに疑問符がつく。




# 参考リンク
- [The Loopix Anonymity System“ by A.M. Piotrowska et al/](https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/piotrowska)
- Towards measuring anonymity” by C. Diaz et al.
- Towards an Information Theoretic Metric for Anonymity” by A. Serjantov and G. Danezis
- [Nym公式サイト](https://nymtech.net/)
- [Nymのミキシングネットワーク - Wikipedia](https://ja.wikipedia.org/wiki/Nymミックスネット)
- [Nymホワイトペーパー](https://nymtech.net/nym-whitepaper.pdf)
- [分散型VPN と中央集権型VPN:違いの全て](https://note.com/koko_crypto/n/n71fe7e92b68a)
- [ミックスネットとは何か？ VPNによる比類なきオンラインプライバシー](https://note.com/koko_crypto/n/n302e7516f691?magazine_key=m0129d65e3526)
- [Sphinx暗号-Nymを支える匿名データフォーマット](https://qiita.com/pseudonym2/items/107cf005e9cab0b165b6)
- [ココナッツ認証（Coconut Credentials）とは？- プライバシーを保護するゼロ知識証明技術](https://qiita.com/pseudonym2/items/b2739ae32f4fb29de0b6)

# コミュニティ

- [Nym日本コミュニティ - Telegram](https://t.me/nymjapanese)
- [Nym日本コミュニティ - Discord](https://discord.com/invite/nym)
- [Nym日本コミュニティ - LINEオープンチャット](https://line.me/ti/g2/0YGYYq4EoQZ8fL5FYQmqU4O9SRuE_a6YX19GtA?utm_source=invitation&utm_medium=link_copy&utm_campaign=default)
- [Nym 公式LINE(現在非稼働)](https://line.me/R/ti/p/@986ytsdx?from=page&accountId=986ytsdx)
- [Nymプロジェクト日本語アカウント - X](https://x.com/nymproject_jp)