Nymは従来のmixnet設計をどのように改良しているのか？

インターネット上の匿名通信ネットワークが目指すものは、すべてのデータパケットが他のパケットと区別できなくなることです。この目標を実現するためには、ネットワーク全体を監視できる攻撃者に対して防御を行う必要があります。そのために必要な2つの重要な要素について説明します。

まず、すべてのパケットはサイズだけでなく、ビット単位でもリンク不可能でなければなりません。Nymでは、過去の記事で説明したSphinxパケットフォーマットを使って、このリンク不可能性（unlinkability）を実現しています。

さらに重要なのは、パケットがいつ送信されたかというタイミング情報もリンク不可能でなければならない点です。ここで「ミックス（mixing）」という概念が登場します。

## ミックスネットワーク（Mix Network）とは？

最近、ミックスネットワークへの関心が高まる一方で、誤解も生じています。ミックスネットワークは、パケットの送信時刻を隠すことでタイミング攻撃に対する防御を提供します。この技術は、攻撃者がパケットの送信者や内容を特定することを防ぎます。

しかし、多くのプロジェクトはこの「ミックス」という概念を正しく理解していません。例えば、Lokiのようにインターネット上に匿名のオーバーレイネットワークを構築するプロジェクトは、善意であるものの、パケットを効果的に「ミックス」していないのにmixnetと主張しています。さらに、HOPRのようにSphinxパケットフォーマットを使っているものの、パケットをミックスしていないため、強力な敵対者がタイミング情報に基づいてパケットの匿名性を破る可能性があります。

この記事では、mix networkの技術的な要素と、Nymのmixnetが従来の設計とどのように異なるかを深掘りして説明します。

## Chaumian Mix Networksの歴史

1981年、David Chaumは「mix network」という革命的なアイデアを提案しました。このネットワークは、インターネット通信のメタデータを隠すことでリンク不能性を実現する分散型中継ネットワークです。メタデータは膨大な量の機密情報を含んでおり、その漏洩はユーザーのプライバシーを著しく損なう可能性があります。Mix networkは、こうした高度なトラフィック解析技術に対してメタデータを保護する手段として機能します。

「メタデータは、その人の人生すべてを教えてくれる。十分なメタデータがあれば、コンテンツは必要ない。」— Stewart Baker（元NSA顧問弁護士）


# 従来のMix Network設計とその限界 — Nymが採用する新しいアプローチとは？

## 従来のMix Networkの基本構造
![Screenshot 2024-09-03 at 15.17.35.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3672851/8c56e7d3-9038-01fa-f90a-1e83fbdea498.png)

従来のmixネットワークでは、ノードは一定のカスケード状に並んでおり、各パケットは最初のノードから最後のノードまで各ノードを経由してルーティングされます。複数のmixを使用することで、mix間の信頼を分散させ、カスケード内の1つのmixが誠実である限り、匿名性は保たれるのです。

MIXネットワークで中継される各パケットは、公開鍵暗号方式（public-key cryptography）でレイヤー暗号化（言い換えればオニオン暗号化）されています。各パケットを受信すると、mixはシングルレイヤーの暗号化を解除します。これにより、ネットワークを監視している人が、パケットのバイナリ表現を見て、パケットを追跡することはできません。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3672851/33e8d69b-264e-a7c5-58c7-56b03e6da6e7.png)

バイナリパターンを変えても、mixが先入れ先出しで暗号化パケットを転送すれば、盗聴者は異なるリンク上の暗号化パケットのタイミングを相関させることができます。実際、これこそがTorが脆弱な攻撃なのです。そこで、それを防ぐために、各mixは一定数のパケットを集め、解読すると同時に、秘密の順列に従ってパケットを並び替える（mixする！）のです。トランプのシャッフルに似ているので、"ミキシング "の代わりに "シャッフル "という言葉が使われることもありますね。

パケットがシャッフルされると、mixはカスケードの次のノードにパケットを送ります。 バッチ(batch)で受け入れられなかった他のパケットは、その後のラウンドで送信されます。これは、いわゆるバッチアンドリオーダーミキシング手法（batch-and-reorder mixing technique）です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3672851/b7821a45-858a-8923-634d-d122ee6aaea7.png)




## 従来のMix Network設計の限界

長年の研究を通じて、従来のmix networkには以下のような限界があることが判明しました：

- **固定カスケードトポロジーのスケーラビリティの欠如**: 固定されたノード構造は、ネットワークのスケールを小さく制限してしまいます。
- **公開鍵操作の非効率性**: 各クライアントとmixノードで行われるオニオン暗号化の公開鍵操作には多大な計算リソースと時間が必要です。
- **匿名性セットのサイズ制限**: 匿名性は各バッチのサイズによって制限され、十分な匿名性を確保するには大規模なバッチ処理が必要です。
- **不確実なレイテンシ**: パケットがどのバッチに受け入れられるか予測できないため、エンドツーエンドのレイテンシが大きく変動することがあります。
- **攻撃に対する脆弱性**: トラフィック分析攻撃やアクティブ攻撃に対する防御力が弱く、従来の設計では高度な攻撃に対抗するのが難しいことが知られています【3,4】。

そうした制約から、Nymは従来のmix network設計を採用せず、Loopix[2]と呼ばれる最新の低遅延匿名通信システムをベースにしています。では、私たちの設計は、従来のmix networkの上記の問題にどのように取り組んでいるのでしょうか？また、cMixのようなChaumian mix networkに基づく他のデザイン、Elixxirが使用しているデザイン、mixnetと主張されているHOPRのような従来のP2Pデザインとの比較はどうでしょうか？

## Nymが採用する最新の設計-Networkテクノロジー

匿名は集団を好む（Anonymity loves company.）ので、スケーラビリティはmix networkの重要な特性の1つである。 固定カスケードのトポロジーは、スケーラビリティの味方ではありません。カスケードが最大容量に達すると、それ以上のトラフィックをサポートすることができなくなり、信頼性の問題が発生することがよくあります。

スケーラビリティを大幅に向上させるソリューションとして、複数のカスケードを導入して並列に動作させる方法がありますが、まさにElixxirはそれを実現しています。 しかし、このアプローチには1つの制限があります。トラフィックは不連続なカスケード間で分割されるため、大量のトラフィックから匿名性の面で有利になることはありません。

一方、HOPRはノード間でPeer-to-Peer接続を確立するため、非常に優れた拡張性を持っています。 しかし、P2Pトポロジーは、カスケードよりも匿名性が弱いのです。カスケードでは、ノードがすべてのパケットに対して同じパスホップ（path hop）にあるため、同じmixで出会うパケットは常にmixされます。 Peer-to-Peerネットワークでは，パケットのパス上のホップが異なれば，パケットは同じノードを通過してもmixしないことがある [5]のです 。

そのため、Nym mixnetは、研究が示すように、匿名性とスケーラビリティに最適な階層型トポロジー（ stratified topology）を導入しています[5]。階層型トポロジーのミックスノードは層状に配置されます。第i層の各ノードは、前後の層の各ノードと接続されています。

![Screenshot 2024-09-03 at 15.29.04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3672851/e38372cf-1860-5577-c3a1-df22d05a9cb8.png)
Stratified topology

パケットはソース・ルーティング（source-routed）され、送信者が宛先までの全てのパスを選択することを意味します。各パケットは、各レイヤーからランダムに1つのノードを選ぶことで構成される独立したパスで送信されます。パケットは独立したパスで送られますが、階層化されたトポロジーにより、ネットワーク上のある地点で互いに交わるため、最終的にトラフィック全体が混ざり合います。

最も重要なことは、mixをレイヤーに集約することで、トラフィックを少数のリンクに集中させる疎なトポロジーを確保し、Nym mixnetが水平方向に拡張できるようにすることです。というのは、サーバーを少しずつ増やしていくことで、ネットワーク全体の容量を増やすことができるという意味です。

したがって、Nym mixnetのトポロジーは、強力な匿名性とスケーラビリティを両立しています。

# オニオン暗号化（Onion encryption）
従来のmix network設計で必要とされる時間のかかる公開鍵操作は、高いレイテンシーオーバーヘッドを課すため、ほとんどのアプリケーションで実用的ではありません。 一つの解決策として、ElixxirのcMixデザインで使われているprecomputation phaseが考えられます。 このアイデアにより、リアルタイム通信時に計算量の多い暗号演算を回避することができますが、事前計算に必要な時間は匿名性セットのサイズに比例して大きくなり（論文参照）、各リアルタイムフェーズの前に繰り返し実行する必要があります。

一方、Nymは、公開鍵の運用に時間がかかるという問題を解決するために、Sphinxというパケットフォーマット（そう、Lightning Networkで使われているのと同じものです！）を使ってパケットをオニオン暗号化しています。Sphinxがどのような仕組みで、どのようなセキュリティ特性を持つのかについては、先日詳しい記事を書きました。一言で言えば、Sphinxは証明可能安全性（provably secure）を持った暗号パケットフォーマットです。また、オーバーヘッドが数百バイトと最もコンパクトで、これまでに提案されたパケットフォーマットの中で最も計算効率の高いフォーマットです。私たち自身のRust Sphinx実装の基準では、1つのパケットを処理するのに、平均0.157ミリ秒が必要で、1つのパケットを作成するのに、平均0.386ミリ秒が必要です！そして、これはまだ最適化のトリックがない状態です！さらに、本実装はKuhnらによって最近発見された脆弱性にも耐性があります（詳細はこちらを参照）。

SphinxはHOPRでも使用されています。しかし、我々の実装とは対照的に、HOPRによるSphinxの実装は、Kuhnらが示した攻撃に対して脆弱であり、パケットが通過するパス長（path length）に関する情報を漏洩してしまうのです。

# Mixing
しかし、本当のゲームチェンジャーは、Nym mixnetが使用する再配列技術（ reordering technique）です。従来のmix networkやcMixのようなシステムで使われている バッジ処理&再配列技術（batch-and-reorder technique）の手法の代わりに、stop-and-go technique（continues-time mixesとも呼ばれる）を使っています。 つまり、ある閾値のパケットをバッチ処理する代わりに、mixは各パケットを遅延させてから次のホップに転送します。パケットが各mixで待つ必要のある時間は、送信者が指数分布からランダムに選びます。 したがって、送信者はパケットのEnd-to-Endのレイテンシーを推定することができます。

そして、なぜこの技術を使おうと思ったのか？匿名性のためです！

指数分布には、無記憶性（memoryless property）という素晴らしい性質があります。何のことかわからない人は、直感的に宝くじの例で考えてみてください：あなたが普通の宝くじプレイヤーだと想像してください。これまでに、100回遊んで100回負けたとします。しかし、あなたは、"あれだけ負けたのだから、今当たる確率はもっと高いはずだ！"と思っているはずです。しかし、もし宝くじに記録がないのであれば、100回負けても、当選確率は初めて宝くじに挑戦したときと同じということになります。 1000回、10000回、100000回、...と試したとしても同じです（すみません！）。しかし、これがパケットの混ざり具合にどう反映されるのでしょうか？

前述したように、batch-and-reorder techniqueを用いたmix networkでは、バッチサイズが匿名性セット（anonymity set）のサイズとなります。 mixがある一定の数のパケット、例えば100個収集した場合、全体として数千のパケットがmix networkで処理されたとしても、あなたの匿名性セットは100しかありません。

Nym mixnetは、より大きな匿名性セットを提供します。どのように？パケットが次々とmixに到着していく様子を想像してください。今回は、パケットをグループ単位でバッチ処理するのではなく、mixに入った各パケットは、敵にはわからないランダムな時間だけそこに滞留するようにしました。しかし、ミキシングとしての遅延はどのように機能するのでしょうか？直感的に、ランダムな遅延が追加されているけれども、早く入ったパケットは早く出て行くはずだと言うかもしれませんね？いえ、違います。これが無記憶性のマジックなのです。 パケットがある時刻にミックスから離れる確率は、その到着時刻に依存しないのです。つまり、敵がミックスから出るパケットを見たとき、そのパケットがミックスに入るのを観察したことのあるパケットのいずれかである可能性があるということである。その結果、バッチミックス（batch mixes）と比較して、Nymで使用される連続時間ミックス（continuous-time mixes）は、より大きな匿名性セットを持つことになります。 つまり、あなたは他のパケットの小さなグループの中だけでなく、ネットワークに入るすべてのパケットの中でも匿名なのです。敵がどれほど混乱するか、想像してみてください！

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3672851/dd08b25b-b4aa-1a90-fa8d-36872e68a9a8.png)
HOPRはElixxirやNymと異なり、ミキシング技術を実装していないため、トラフィック解析に対する耐性がなく、結果的に匿名性を確保することができない設計となっています。しかし、現在、将来のバージョンにおいて原始的なミキシング技術を追加するよう取り組んでいるそうです。

# トラフィックのカバー

オンラインユーザーは持続的な行動パターンを持っており、時間の経過とともに、あなたのコミュニケーションに関する情報を開示する可能性があります。 例えば、敵がアリスが送信したパケットの突然のバーストと、同時に他のユーザやサービスが受信したパケットの突然のバーストを見た場合、アリスの通信の宛先を推測することができます（トラフィック確認攻撃、traffic confirmation attacks）。

そこで、Nymクライアントは、ユーザーが実際にいつmixnetを利用しているか、どれだけのパケットを送受信しているかを隠すために、ポアソン過程（Poisson process、一種のランダム化）に従ってパケット送信のスケジューリングを行います。 もし、ユーザーがmix networkに転送するパケットを予定していない場合、クライアントは代わりにループカバーパケット、すなわち、最終的な宛先が送信者であるダミーのペイロードのパケットを送信します。 ループカバートラフィックを使用することで、敵の視点から見ると、ユーザーは常にアクティブであるように見えます。つまり、敵はユーザーが実際の通信パケットを送信または受信しているときに区別することはできません。これはしばしば観測不可能性（Unobservability）と呼ばれ、既存の実装されたmixnetのうち、Nym mixnetのみがこの性質を保証しています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3672851/c545b2f2-556e-4039-ac6a-013e134f2e87.png)
また、Mixは、例えばフラッディング攻撃（flooding attacks）などのアクティブな攻撃を検出するために、クライアントのトラフィックと区別がつかないループカバートラフィック（ loop cover traffic）を送信します[5]。 さらに、このようなループカバーパケットによって、ネットワークのサービス品質をチェックし、悪意のある行動を検出することができます（詳しくは次回の記事で説明します）。

Nym mixnetは、連続的な時間のミックスと調整可能なカバートラフィックの組み合わせにより、強力な匿名性を保証するのに十分なトラフィックをネットワーク上に常に確保し、様々な待ち時間や帯域幅の制約があるアプリケーションをサポートすることができます。

# 結論：Nymは匿名性のトリレンマを解決するか？
匿名通信ネットワークの先行研究では、強い匿名性、低遅延、低オーバーヘッドコストの間には自然なトレードオフが存在することが示されています[7]。 もちろん、匿名性は無償ではありえません。常に何らかのトレードオフが存在します。mixnetのデザインについては、どのようなトレードオフを選択するか、そしてその設計が拡張可能かどうかが問題です。Nymは、最先端のデザインを採用しているため、最もスケーラブルで匿名性の高いmixnetデザインだと考えています。

要約すると、Nymはスケーラビリティ、強い匿名性、低レイテンシーを同時に提供する最初の匿名通信システムです：Nymは匿名性のトリレンマのスイートスポットを突いているのです[7]。Chaumによる最初のmix network デザインの導入以来、40年にわたり研究されてきた数々のベストオブブリードテクニックを組み合わせています。

Elixxirは、匿名性とメタデータの排除に関する強力な証明可能な特性を持つ、最高のChaumian batch mixnetです。Elixxirは、伝説的なChaum自身によって設計されたので、これは驚くことではありません！ しかし、Elixxirは独自の量子耐性を持つ暗号通貨を用いたクローズドソースコードをベースとしており、高速性を得るためにはChaumの新しい飛躍的な事前計算フェーズ（precomputation phase）を必要とし、匿名性の面ではそのスケーリングがbatch mixnet cascade設計の限界にぶつかっています。

つまり、ElixxirベースのシステムであればNymを必要としないが、すでに存在するソフトウェアの世界もあるのだ。ElixxirよりもTorのように、継続的なmixとして、Nymはあらゆるブロックチェーンと相互運用し、高度な統計技術によってあらゆるインターネットトラフィックを匿名化できるよう、汎用的でオープンソースの道を選びました。Nymに流入するトラフィックが多ければ多いほど、Nymのスケールは向上し、匿名性を高めることができます。

Nymは、P2Pトポロジーではなく、階層型（stratified）トポロジーを採用しています。P2Pトポロジーは、パケットを均等に「mix」しないため匿名性に劣りますが、NymはNymネットワークに入るすべてのパケットのプライバシーを保証したいためです。 Nymの上にアプリケーションを構築したり、既存のアプリケーションを統合したい場合は、私たちのTelegramチャンネルに連絡してください。

Nymがインターネットトラフィックのスケーラブルな匿名性に焦点を当てていることを考えると、次の明白な疑問は、NymがTorや新興の "分散型VPN "の世界と比較してどうなのかということです。Mixnetは複雑かもしれませんが、NSAのような強力な敵に対して匿名性を確保するための最良のチャンスです。

# 参考リンク

- [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)


# 参考文献

[1] “Untraceable electronic mail, return addresses, and digital pseudonyms”, D. L. Chaum; Communications of the ACM; Link
[2] “The Loopix Anonymity System”, A. M. Piotrowska, J. Hayes, T. Elahi, S. Meiser and G. Danezis; USENIX Security Symposium; Link to the paper and presentation video.
[3] “Statistical disclosure or intersection attacks on anonymity systems”, G. Danezis, A. Serjantov; International Workshop on Information Hiding; Link
[4] “From a trickle to a flood: Active attacks on several mix types”, A. Serjantov, R. Dingledine, P. Syverson; International Workshop on Information Hiding; Link
[5] “Impact of network topology on anonymity and overhead in low-latency anonymity networks”, C. Diaz, S. J. Murdoch and C. Troncoso; Privacy Enhancing Technologies Symposium; Link
[6] “cMix: Mixing with Minimal Real-Time AsymmetricCryptographic Operations”, D. Chaum, D. Das, F. Javani, A. Kate, A. Krasnova, J. De Ruiter, A. T. Sherman; Conference on Applied Cryptography and Network Security; Link
[7] “Anonymity trilemma: Strong anonymity, low bandwidth overhead, low latency-choose two.” , D. Das, S. Meiser, E. Mohammadi, and A. Kate; IEEE Symposium on Security and Privacy (SP); Link