Sphinxは前例のない匿名の暗号パケットフォーマットで、Lightning NetworkとNymの両方を動かしています。
2009年1月12日、Satoshi Nakamotoは、有名なサイファーパンクであるHal Finneyに10BTCを送り、世界初のビットコイン取引を行いました。その11年後には、Chaos Computer Club、Blockstream、Electric Coin Companyなどの有志が運営するmixnet間でSphinxパケットを送信し、nym mixnetが最初の匿名取引を行いました。

Torよりも強力なネットワークレベルのプライバシーを提供できる機能的なMixnetは、プライバシー擁護者、研究者、サイファーパンクの長い間の夢でした。MixnetはTorよりも古く、これまでで最も効果的な展開は、匿名で電子メールを送信するための「タイプ3」リメーラーであるMixminionでした。

Mixnetの開発が停滞して以来、Mixminionの主要開発者であるNick MathewsonとRoger Dingledineの2人がTorの開発に移ったため、2003年以降オープンソースの研究はほとんど行われておらず、2011年以降はコミットもありません。

PANORAMIXに始まり、Nymに続く努力のおかげで、mixnetは復活しました。

Nymのmixnetは、パケットを互いに受け渡しするmixノードで構成されています。ノードはトランザクションのタイミングメタデータを難読化するためにタイミング遅延を追加し、実際のトラフィックが十分でないときにはダミーのトラフィックを生成します。そのため、Nym mixnetは、メッセージベースのトラフィックに対して、TorやVPN（dVPNを含む）よりも優れたプライバシーを提供します。

Mixnetの本当の秘密兵器は、NymとLightning Networkの両方で使われているSphinxパケットフォーマットです。Sphinxは理解するのが厄介で、Lightning Networkでは匿名性を保証するような方法では使用されていません。そこで、Sphinxを深堀りして、その謎に答えてみましょう！

Sphinxとは？

Sphinx¹は、送信者から受信者へのメッセージを匿名でルーティングします。マルチホップシステムにおける送信者の匿名性に必要ないくつかの特性を提供します：

ビット単位の非連結性：ネットワークを観察している敵が、ミックスに入ってくるパケットを、そのバイナリ表現に基づく送信パケットと相関させることはできません。言い換えれば、パケットは匿名であることを意味します。
完全性：タグ付け攻撃やリプレイ攻撃など、敵がメッセージを改変して再投入し、宛先や内容に関する情報を引き出すような能動的な攻撃への耐性がある。
ルーティング情報の隠蔽： mixnodeは、パケットがこれまでに移動したホップ数や、メッセージの経路の長さを知ることはできません。あるmix-nodeが知っているのは、前任者と後任者のmix-nodeだけです。

Sphinxでは、匿名返信パケットは、ネットワークで前方に送信されたSphinxメッセージと区別がつかないSingle-Use Reply Blocks（SURBs）で受信者の匿名性を提供することができます。

Sphinxの概要

Sphinxのパケットは、2つの独立した部分から構成されています：

1.発信元から目的地までメッセージをルーティングするために必要なすべての情報をカプセル化したヘッダー

2.実際のメッセージの内容が隠されているペイロード

Nakamotoがmix-networkを介してHal Finneyに匿名でメッセージを送りたいと考えている世界を考えてみましょう（nodeはIPアドレスと公開鍵で表現されます）。Nakamotoは、暗号化されたパケットを転送するために必要なルーティング情報を、ルート内の各mixノードが解読できるように鍵を配布する必要があり、残りのルートはまだ隠されています。

まず、Nakamotoはルートを選択し、各mix nodeの公開鍵を調べ、それぞれの共有鍵を計算します。Sphinxヘッダの「鍵」の構成要素は、1つのグループ要素ɑで、ノードの公開鍵と組み合わせることで、Diffie-Hellman鍵交換を介してそれぞれの共有鍵を計算することができます。したがって、ユーザーが選んだルートの最初のノードが次のノードにパケットを転送し、そのmixノードだけがそれを復号することができます。

このエフェメラル共有鍵sにより、ノードは、ヘッダ内の完全性タグɣをチェックすることによってパケットヘッダが変更されていないことを確認し、送信者から指定されたmixノードに、mixノードが何をどこに転送すべきかという一連の指示を伝える、暗号化ルーティング情報βを復号するのに必要な鍵を導出してパケットの処理を行うことができます。

グループ要素ɑは、ユーザーごとのパケット相関を防ぐために、各ミキシングステップで暗号的にブラインドされます。ブラインドされた係数bは共有鍵sから抽出されるため、送信者とそれぞれのmixはパケット転送に必要なすべての操作を実行することができる。Sphinxパケットのペイロードδは、ワイドブロック暗号を使用して計算され、敵対者がペイロードを任意の時点で変更した場合、メッセージコンテンツが回復不能に失われることを保証します。ヘッダーにエンコードされた整合性タグɣは、パケットヘッダも修正されていないかどうかだけをチェックすることができます。すべてのパケットは、各ホップで同じ長さにパディングされる必要があります。

ヘッダーが一定の長さを維持することを保証することは、より複雑です。Sphinxは、一定のパケットサイズを確保するために洗練されたパディング技術を使用し、最小限のオーバーヘッドを導入します。

Sphinxのパケットを作成する

メッセージmをmixノードM₀、M₁、M₂の選択された経路を経由するために、nakamotoは新しい秘密値xを生成し、xとmixノードの公開鍵を使用してすべてのグループ要素ɑ、共有鍵s、ブラインドされた係数bを事前計算する。ヘッダの符号化は、IPアドレスのようなルーティング情報と、ルート内の各mix nodeのヘッダ整合性タグを、最後から最初にレイヤーカプセル化することで開始される。

最も内側のレイヤーは、Finneyのアドレス∆、SURBに使った識別子、パディングのシーケンスを連結して構築され、パスの長さが誤って明らかにならないようにする。これらは次に、共有鍵s₂でシードされた擬似乱数生成器の出力とXORすることによって暗号化される。この結果は、最後にフィラー文字列ɸと結合され、この追加により、暗号化のレイヤーが追加または削除されてもヘッダーパケットのサイズが一定であることが保証されます。最終的に暗号化された経路情報β₂の準備ができたら、NakamotoはそのHMACを完全性タグɣ₂ = HMAC(s₂, β₂) として計算し、この経路情報βに完全性チェックɣを結合して暗号化する。この処理は、以下に示すように、再びβ₁から始まり、次のβへと再帰的に行われる：

そして、Nakamotoは計算した共有鍵を再利用して、ペイロードをレイヤー暗号化します。ヘッダと同様に、ペイロードのカプセル化はmix nodeを通る経路の逆順で実行されるのです。初期δ₂は、メッセージm、Finneyのアドレス∆、および一連のゼロバイトパディングを連結した、鍵s₂を使用するwide block cipherを使用して作成され、本体が転送中に変更されていないことを検証することができます。

Finneyはまだ、追加の既知系列ゼロバイトパディングを使用して、有効なメッセージかランダムな暗号テキストかを区別できる必要があります。δ₂の準備ができたら、Nakamotoは再びs₁とs₀を使って1つずつ暗号化します。

Sphinxパケットの処理

パケットを受信すると、mix nodeはヘッダーからグループ要素ɑを抽出し、自身の秘密鍵と組み合わせて共有鍵sを導出する。
sを用いて、mixは暗号化された経路情報の鍵付きハッシュをHMAC（s, β）として計算し、パケットヘッダに付けられた完全性タグ（integrity tag ）ɣと比較する。ヘッダーが改ざんされているために完全性チェックが失敗した場合、そのパケットはドロップされる。そうでない場合、mix node はステップ 3 に進む。
これで、mix-nodeは暗号化されたβを復号化する準備が整いました。βに付加されるゼロバイトパディングの量は、データの長さの不変性を保持するためにミックスノードが抽出する必要のあるルーティング命令（routing instructions）の長さと等しい。なお、パディングは完全性タグɣの中でハッシュ化されているので、Nakamotoが事前に生成したパディングと同一でなければならない。
mix-nodeは、次の mix-nodeのアドレス（最終ホップの場合は、宛先アドレス∆と識別子I）と、次のホップに転送すべき新しい整合性タグɣとβ'を取得するため、Bからのルーティング命令を解析する。
また、mix-nodeはδのワイドブロック暗号（wide-block cipher）の復号を行い、δ'を生成し、次のホップに転送する。
mix-nodeは、受信したɑを共有鍵sから得られるblinding factorを用いてブラインドし、新しいグループ要素ɑ'を取得する。

ヘッダーとペイロードの両方が暗号化され、グループ要素が見えなくなると、mix-nodeは新しいパケットを（（ɑ', β', δ'）として組み立て、次のアドレスに転送することができます。

Sphinxのパケット形式の原図（Danezis and Goldberg（2014）より引用

NymのSphinxへの攻撃対策について

Sphinxの最も優れた点の1つは、それが証明可能な安全性を持っていることです。元の論文は、それが仮定しているプロパティのセキュリティ証明を提供しています。一般的に、私たちは安全性の証明を求めています。暗号技術者は通常、設計が実際に数学的な仮定のセットから論理的に証明できる特性のセットを持っていることを示すために、手作業で証明します。プライバシーを証明するのはもっと難しく、一般的にはシミュレーションが必要です。

暗号技術者が手作業で安全性の証明をする場合、証明したいことを間違えたり、見落としたりすることがあります。 Kuhnらの研究により、CamenischとLysyanskaya³がオニオンルーティングに基づくシステムに対して定義した形式的特性が不十分であるため、DanezisとGoldbergが提示したセキュリティ証明ではSphinxパケットのオリジナルデザインにおける重要な欠陥が検出されなかったことが示されています。この欠陥が修正されない場合、Sphinxを使用するシステムにおいて、ユーザーのプライバシーが著しく害される可能性があります。

オリジナルのSphinxの設計では、ゼロバイトのパディングを使うことが提案されていましたが、パディングによってパスの最後のmix-nodeがパスの長さに関する情報を推論できるため、ゼロのシーケンスのみを使用することにしました。そのため、Sphinxが約束したセキュリティ特性の1つを破り、ルートや最終目的地に関する重要な情報を推論する可能性があります。

前述したように、ルートの最後のmix-nodeは、受信者アドレス（△）、識別子（I）、0バイトのパディングを暗号化して生成し、フィラーテキスト（filler string）ɸと結合した最内層の暗号化されたルーティング情報βを受信します。

Sphinx論文で使われた表記法に従い、最内部βは次のように作成されます。

ここで、｜ɸ｜＝2（v-1）κ、κ、rはそれぞれセキュリティパラメータと最大パス長、vはパケットが通過するパスの長さである。mix-nodeによる受信βの処理は、以下のように行われる。

では、最後のmix-nodeは、この魔法のような計算から、どのように経路長に関する情報を推論するのでしょうか？

この攻撃の仕組みを説明するために、簡単な例を紹介します。まず、値x = a⊕bが与えられたとき、xもaもbも同じ長さで、さらにxとbをXORすると、x⊕b = a⊕b = aとなることを思い出してください。この例では、ノードv-1の共有鍵を入力とするPRNGの出力が10101010101010...と仮定します。

ここで、最後のミックスで受け取ったβの値を次のように考えてみましょう。

ここで、(2)に従い、出口mixnodeが行うのと同じ操作を行い、βの復号と解析を行います。

設計上、パスの最後のミックスノードは、予想されるβの全長（この例では9ビット）と、宛先アドレス（△）と識別子（I）の連結の後にそれぞれゼロパディングとフィラー文字列の疑似ランダムビットが続くことを知っています。正確な長さ∆とIについての情報があれば、正直で好奇心旺盛な最後のmix-nodeは、識別子の後の最初のビット1がどこにあるかを調べます。なぜなら、フィラーテキスト（filler string）はそこかそれ以前に始まることが分かっているからです。識別子の後の最初の1ビットがどこにあるかを観察することで、最後のミックスがフィラーテキストの長さの下限を決定することができます。ɸの全長は設計上、経路長の2倍にセキュリティパラメータκを乗じたものとして定義されているので、フィラー文字列の長さの下限は、使用する経路の長さの下限に関する情報を漏洩させます。

パスの長さを知ることが有害である理由

研究が示すように（1）、制限された、または疎なトポロジーを使用するネットワーク（例えば、Lightning）では、パス長を知ることで、送信者が隠れることのできる匿名性のセットが減少します。下図の例では、パス長の下限値を知ることで、送信者の匿名性が低下することを表しています。 Dが出口ミックスノードとして働き、Timmyにパケットを転送する場合、パスの長さを知らなくても、ノードA、B、C、E、G、Fのいずれかが送信者になることができます。しかし、Dがパスの長さが3以上であることを推論できれば、ネットワークグラフを見て、AかBのどちらかしか送信者になれないと推論し、送信者候補の数を大幅に減らすことができるのです。

この攻撃を防ぐのは非常に簡単です。(1)でβを作成する際に、ゼロパディングの代わりにランダムビッツパディング（random-bits padding）を使用すればよいのです。実は、George DanezisによるPythonの実装では、すでにこの欠陥を認識しています。

しかし、この攻撃はNymには影響しない

Nymは匿名性を最大化するために階層型トポロジーを採用しており、すべてのパスは等しい長さで、各mix-nodeはパスにおける自分の位置を知っています。Lightningの場合、このようなことはありません。可変長パスを使用するため、Sphinxのオリジナル実装はこの攻撃に対して脆弱でしたが、現在では修正されています。

Sphinxエンコーディングの最後のレイヤーは、（Torのような）出口ミックスではなく、アプリケーション自体によって除去されます。しかし、NymのRustによるSphinx実装は、この攻撃に対して耐性があり（ランダム化されたパディングを使用）、Sphinxベースの設計であれば安全に再利用することができます。

Nymの次なる目標は？

Nymの最初の匿名Sphinxパケットは、私たちの最後のものではありません。 Nymネットワークは、あらゆるインターネットアプリケーションに対応する安定した汎用ミックスネットへと徐々に進化していくでしょう。私たちのテストネットはすでに稼働しており、2020年末には本番を迎える予定です。しかし、ネットワークレベルのプライバシーを必要とする人はいないでしょう。結局のところ、ほとんどすべての人がそうなのです。

Lightning NetworkはすでにSphinxパケットを使用していますが、ただ、2019年11月のLightningカンファレンスでClaudia Diazが示したように、トランザクションにプライバシーを与える機能に違反する方法で使用しています。 Lightningは、SphinxなどのインフラをすでにNymと多く共有しているので、いくつかの変更で、プライバシーを強化することができます。NymとLightningの組み合わせは、ビットコインをプライベート化するための最も現実的な道かもしれません。
https://youtu.be/g55kMhggIBY (Claudia Diaz氏による「SphinxはなぜLightningのプライバシーを保護しないのか、そしてどうすれば修正できるのか」という講演)

プライバシーを強化した暗号通貨やあらゆる暗号通貨のサイドチェーンもネットワークレベルの匿名性を使用すべきです。さもないと、攻撃はタイミングデータを使用してパケットを非匿名化し、zkSNARKSなどのオンチェーンプライバシー技術への攻撃につながることさえあります。多くのコミュニティへのアプローチを行っており、近日中に詳細をお伝えする予定です。

そして、Braveなどによる分散型VPNへの関心も忘れてはいけない。Sphinxのパケットはどれくらい速くなるのでしょうか？Sphinxは、非対称暗号（asymmetric cryptography）やエキゾチックなワイドブロック暗号を多用してアンリンク性を実現していますが、こういったユースケースを実現するためのスピードも、おそらく再設計できるはずです。

Sphinxは、普通のインターネットパケットに匿名の力を与えます。しかし、大きな力には大きな責任が伴います。Nymの上に、どのような新しいサービスやアプリケーションがこれらを制し誕生するのか、楽しみにしています！

論文

https://eprint.iacr.org/2008/475

参考リンク

Nym公式サイト
Nymのミキシングネットワーク - Wikipedia
Nymホワイトペーパー
分散型VPN と中央集権型VPN:違いの全て
ミックスネットとは何か？ VPNによる比類なきオンラインプライバシー
Sphinx暗号-Nymを支える匿名データフォーマット
ココナッツ認証（Coconut Credentials）とは？- プライバシーを保護するゼロ知識証明技術

コミュニティ

参考文献：

¹ George Danezis and Ian Goldberg. Sphinx: A compact and provably secure mix format. In IEEE Symposium on Security and Privacy, pp 269–282. IEEE, 2009.

² Christiane Kuhn, Martin Beck, and Thorsten Strufe. Breaking and (partially) fixing provably secure onion routing. arXiv preprint arXiv:1910.13772, 2019.

³ Jan Camenisch and Anna Lysyanskaya. A formal treatment of onion routing. In Annual International Cryptology Conference, pp 169–187. Springer, 2005.

⁴ George Danezis. Mix-networks with restricted routes. In International Workshop on Privacy Enhancing Technologies, pp 1–17. Springer, 2003.