The Consensus Number of Untraceable Cryptocurrencies

デジタル大強奪：目立たないように隠れる技術

想像してみてください。あなたは、誰もが秘密をささやき合っている混雑した部屋にいます。暗号通貨のデジタル世界において、この部屋は「レジャー（台帳）」、つまり誰が誰に送金したかを記録する巨大な公開ノートです。通常、このノートはガラスの壁のようなもので、実名は分からなくても、誰が誰に支払ったのかを正確に目にすることができます。しかし、もしあなたが、誰が実際に現金を渡したのかを誰にも悟られずに支払いたいとしたらどうでしょう？これが「送信者の匿名性（sender untraceability）」という課題です。

これを解決するために、暗号学者は「マスキング・セット（隠蔽集合）」と呼ばれるトリックを使用します。あなたが支払う側だとして、10人の友人のグループの中に立っていると想像してください。あなたたちは全員、見た目が全く同じ封筒を持っています。外部の観察者から見れば、10人の友人のうちの誰かが支払った可能性があるように見えますが、そのうちの誰であるかを特定することはできません。この論文は、これらのグループの仕組みを深く掘り下げています。そして、非常に具体的で、ほとんど哲学的な問いを投げかけています。「もし、送信者をグループの中に隠そうとするなら、その『隠す』という行為は、グループの仕組みそのものを変えてしまうのだろうか？」具体的には、それは「合意形成（コンセンサス）」を難しくするのかどうか、という問いです。著者たちは、物事を進めるためにどれほどの調整が必要かを測るための、高度な指標である「コンセンサス数」について調査しています。これは「交通渋滞メーター」のようなものだと考えてください。数値が低ければ車は互いにスムーズに通り抜けられますが、数値が高ければ、誰が先に進むべきかを話し合い、止まって待たなければなりません。

2つの隠し方：「すべてを保持する」vs「すべてを入れ替える」

この論文では、これら（送信者を隠すための）グループの管理における2つの異なる戦略を比較しています。これらを**リニア戦略（線形戦略）とコンスタント戦略（定数戦略）**と呼びましょう。

リニア戦略（LUAT）：増え続けるゲストリスト
誰かが支払うたびに、単にグループの中に隠れるだけでなく、壁に「このグループの誰かが支払いました！」という永久的なメモを残していくパーティーを想像してください。パーティーはこれらのメモを決して削除しません。「支払った可能性がある人（allow-set）」のリストも、「すでに支払った人（deny-set）」のリストも増え続けます。

• 良いニュース： この方法は驚くほど穏やかです。リストが巨大になっても、「交通渋滞メーター」は非常に低いままです。著者たちは、グループの人数がどれほど大きくなっても、システムは一度に2人分の調整を行うだけで済むことを証明しました。それは、誰もが自由に動けるダンスフロアのようなものです。たとえ誰かとぶつかったとしても、誰が先に動いたかを特定するためにパーティー全体を止める必要はありません。
• 落とし穴： パーティーの壁は、永遠に付箋で覆われてしまいます。誰が支払った可能性があるかを記憶するために必要なストレージ容量は、取引ごとに線形に増加します。これは、たとえ何年も前に立ち去ったとしても、ドアを通ったすべての人のことを記憶しようとするようなものです。

コンスタント戦略（CUAT）：魔法の再ランダム化
さて、別のパーティーを想像してください。誰かが支払うとき、彼らは単にメモを残すだけではありません。代わりに、友人グループの全員が瞬時に服を着替え、名前とアイデンティティを変えます。古いグループは消え、全く新しいグループが現れます。これにより、部屋にいる総人数は一定に保たれ、「壁」が汚れることはありません。これが、Quisquisのようなシステムで使用されている手法です。

• 落とし穴： ここで混沌が生じます。グループ全体が変わるため、もし2人が同時に支払おうとし、それらのグループが重なり合っている場合（たとえ1人でも共通の人がいる場合）、彼らは衝突してしまいます。両者が成功することはありません。
• 結果： 「交通渋河メーター」が爆発的に跳ね上がります。著者たちは、ここでの調整に必要な量は、グループのサイズの二乗で増加することを発見しました。グループが10人であれば、必要な調整はおよそ100になります。100人いれば、10,000が必要になります！これは、もし2つのグループが椅子を1つでも共有していたら、ゲーム全体を止めて誰がどこに座るかを決め直さなければならない、椅子取りゲームのようなものです。

プライバシーと進捗のトレードオフ

この論文の最大の発見は、厳格なトレードオフが存在することです。プライバシーを得るためには、以下のどちらかの通貨で支払わなければなりません：ストレージ（容量）、または**シンクロニゼーション（同期）**です。

1. ストレージで支払う（リニア戦略）： 履歴を永遠に保持します。システムは高速で調整も容易ですが（コンセンサス数2）、ハードドライブが満杯になっていきます。
2. シンクロニゼーションで支払う（コンスタント戦略）： 履歴を小さく清潔に保ちます。しかし、そのためには、システムに膨大な調整を強いることになります。より多くの人々の中に隠れようとすればするほど、出来事の順序について全員の合意を得ることが困難になります。

著者たちはまた、**「強力な匿名性（Strong Untraceability）」**と呼ばれる「スーパー・プライバシー」モードについても調査しました。これは、単一の瞬間だけでなく、パーティーの「全履歴」を見守る探偵がいるようなものです。もし、長い歴史の中で送信者を完璧に隠したいのであれば、友人のグループは非常に特定の数学的パターン（射影平面やプロジェクティブ・プレーンのようなもの）に従って配置されなければならないことに、彼らは気づきました。もし完璧な配置が行われなければ、探偵は「誰が多くのグループに登場しているか」を見ることで、誰が支払ったかを推測できてしまいます。そして、この完璧な配置を強制すると、「交通渋滞メーター」はグループのサイズに基づいた特定の高い天井に達します。

スターベーション（飢餓）問題：平均スケジューラ

最後に、この論文はコンスタント戦略の暗部である**「スターベーション（飢餓）」**について取り上げます。
パーティーに、音楽をコントロールするいじめっ子（敵対的スケジューラ）がいると想像してください。リニア戦略では、たとえいじめっ子があなたを止めようとしても、あなたが支払う準備ができていれば、いつかは必ず支払うことができます。しかし、コンスタント戦略では、グループ全体が変化するため、いじめっ子はあなたの特定のグループに対して「リセット」ボタンを押し続けることができます。
著者たちは、コンスタント戦略においては、いじめっ子が特定の人物を永遠に支払わせ続け、別の人物を永遠に待たせ続けることができることを証明しました。たとえ待たされている人がお金を持っており、支払う準備ができていたとしても、です。待たされている人は何度も試みますが、彼らが完了しようとするたびに、いじめっ子が完了直前でグループをリセットしてしまうのです。これは、システムが状態を小さく保つように設計されている限り、数学的に防ぐことが不可能な「サービス拒否（DoS）」です。

結論

この論文は、単に「どちらが良いか」を述べているのではありません。あなたの選択に伴う正確なコストを明らかにしています。

• もし、容量が尽きず、すべての人に対して公平なシステムを望むなら、過去の取引リストが永遠に増え続けることを受け入れなければなりません（リニア）。
• もし、小さく整然とした履歴を望むなら、人数を増やすほど調整が信じられないほど遅く複雑になり、ユーザーを「飢餓状態」に陥れる可能性があることを受け入れなければなりません（コンスタント）。

著者たちは、これらの限界を数学的な確実性をもって証明しました。つまり、「最高の組み合わせ」は存在しないということです。履歴を小さく整然としたものにしつつ、かつ高速で公平で調整しやすいシステムを同時に持つことはできません。暗号通貨の世界にはプライバシーへの代償が必要であり、この論文は、その代償がいくらであるかを正確に示しているのです。