A Complexity-Theoretic Approach to Proofs of Space

大いなるデジタル・ストレージ強奪事件

一冊のページも見せることなく、自分が膨大な図書ライブラリを所有していることを証明できる世界を想像してみてください。これが、暗号学とコンピュータサイエンスの分野における概念である「プルーフ・オブ・スペース（空間証明）」の核心です。これは、デジタル上の大家が、店借人が単に「家具がある」という巧妙な絵を描いているのではなく、実際に家具で満たされた倉庫を持っていることを確認したいと考えているようなものです。大家（検証者）は、店借人（証明者）が、単に「家具があります」という短いメモを保持し、要求された時にだけ魔法のように家具を出現させているのではなく、大量の永続的なメモリを使用してデータを保存していることを確信する必要があります。

長年、これらのデジタル倉庫を構築する唯一の方法は、「ランダム・オラクル」と呼ばれる魔法の、架空のツールに依存していました。これは、質問をするたびに、完全にランダムで予測不可能な答えを吐き出す魔法のブラックボックスのようなものです。理論としては有用ですが、それは純粋な魔法の土台の上に家を建てるようなものであり、現実の世界でそれが機能するかどうかは分かりません。科学者たちの大きな疑問は、「魔法の箱に頼ることなく、計算の現実的な物理法則のみを用いて、安全なプルーフ・オブ・スペースを構築できるか？」という点でした。本論文は、複雑性理論（問題がいかに解くのが難しいかを研究する学問）の道具を用いて、ゼロからこれらの証明を構築できるかどうかを探ることで、その問いに深く切り込んでいます。

論文の核心的アイデア：「深い」文字列

著者であるマーシャル・ボールとジアシン・グアンは、魔法を使わずにプルーフ・オブ・スペースを構築するための、新しい初等的なフレームワークを提示しています。彼らの主な発見は、2つの特定の材料、すなわち「暗号学的仮定」（衝突耐性ハッシュ関数など）と「脱ランダム化の仮定」（強力な非決定性マシンにとって特定のコンピュータ問題がいかに難しいかという信念）があれば、これらの証明を作成できるということです。

彼らのトリックを理解するために、あなたが巨大で乱雑な砂の山（データ）を持っていることを証明する必要があると想像してください。従来の方法では、砂が圧縮不可能であることを保証するために魔法の箱が必要でした。著者たちは、現実の世界では、砂を「圧縮不可能」にする必要はないことに気づきました。ただ、**「素早く圧縮するのが難しい」**状態にすればよいのです。

彼らは**「計算的深度（Computational Depth）」**という概念を導入しています。データの文字列を一つの物語だと考えてください。

1. セットアップ： 証明者は、小さなシード（短い物語の要約）を取り、長い時間（フェーズ1）をかけて、それを巨大で詳細な小説（データ）へと拡張します。
2. 仕掛け： その後、検証者はその小説の特定のページを要求します。
3. 罠： もし証明者が小説全体を実際に書いておらず、単に短い要約だけを保持していた場合、彼らはそのページを最初から書き直さなければなりません。しかし、検証者は彼らに与えられる時間（フェーズ2）を極めてわずかに設定します。

著者らは、もし特定の困難な問題が存在すると仮定するならば（具体的には、ある問題が「非決定性」回路にとって解くのが速すぎて困難であると仮定する場合）、短いシードから長い文字列を生成する関数を作成できることを示しています。この文字列は「深い」ものです。つまり、十分な時間があれば短いシードから生成できますが、急いでいる場合には短いシードから再構築することができません。それは、解くのに1年かかるが、チェックするのに1分で済むパズルのようなものです。もし1分間で解こうとしても、到底不可能です。

証明の仕組み：「メルクルツリー」と「魔法の呪文」

論文では、この「深度」をテストするための2段階のプロトコルを概説しています。

フェーズ1：セットアップ（長い待ち時間）
検証者はランダムなシードを証明者に送ります。証明者は、自身の特別な「深い」関数を使用して、そのシードを巨大なファイルへと変換するために、長い時間（例えば数時間）を費やします。その後、彼らはそのデータの上に**メルクルツリー（Merkle Tree）**を構築します。メルクルツリーは、データ全体のデジタル指紋のようなものだと想像してください。それは、各葉がデータの断片であり、各枝がその下の2つの枝のハッシュ（ユニークなデジタル指紋）である家系図のようなものです。その最頂部には、ファイル全体を表す単一の「ルート（根）」となるハッシュが存在します。証明者は、この巨大なファイルとルートを保存します。

フェーズ2：チェック（クイック・クイズ）
検証者は突然、ファイル内の特定のページ（ランダムなインデックス）を要求します。証明者は、それらのページと、それらのページが元のファイルに属していることを証明するためのメルクルツリー内の「パス」を迅速に提供しなければなりません。

ここで著者たちの巧妙さが光ります。証明者がプロトコルを回避しようとする（単に短いシードを保持し、ページを推測しようとする）のを防ぐために、彼らは**「簡潔な引数（Succinct Argument）」**（短い証明）を追加します。

• オプションA（より強い仮定）： 彼らは「SNARG」（非常に短く、非対話的な証明）を使用し、彼らが送ったルート・ハッシュが、実際にシードから生成されたファイルに由来することを証明します。これには、特定の暗号ツールの存在に関する強い仮定が必要ですが、ストレージのオーバーヘッドを低く抑えることができます。
• オプションB（より弱い仮定）： 彼らは、衝突耐性ハッシュ関数に基づいた「キリアン型（Kilian-style）」の引数を使用します。これはより標準的で「安全な」仮定ですが、正直な証明者がメルクルツリーが正しく構築されたことを証明するために、より多くのデータ（PCP文字列）を保存することを強いることになります。

彼らが否定したもの、そして証明したもの

本論文は、プルーフ・オブ・スペースがランダム・オラクル・モデルに依存しなければならないという考えに対して、明確に反論しています。彼らは、「魔法の箱」は必要ないことを示しています。代わりに、もし私たちが「脱ランダム化の仮定」（ある問題が非決定性回路にとって困難であるということ）を受け入れるならば、プルーフ・オブ・スペースは可能であることを証明しています。

また、プロトコルを回避しようとする特定の手法についても言及しています。例えば、証明者がごくわずかなデータのみを保存し、巨大なファイルをその場で「圧縮」しようとしたらどうなるでしょうか？ 著者らは、もし証明者が検証者に受理されるならば、その証明者はかなりの量のデータを保存していなければならないことを証明しています。具体的には、証明者がプロトコルを回避しようとする場合、正直な証明者が保持するデータ量よりも大幅に少ないデータを保持して逃げ切ることはできない（正直な証明者が$N$ビットを保持する場合、回避を試みる証明者は、使用される具体的な構成に応じて、$N$ビットより大幅に少ない量を保持して成功することはない）ことを示しています。

結論

この論文は、今日あなたのスマートフォンですぐに使えるような商業製品を作ったと主張しているわけではありません。むしろ、それは理論的な設計図を提供しています。それは、「魔法なしで、自分がデータの倉庫を持っていることを証明する」という不可能に見えるタスクが、計算問題の困難さに関する標準的な仮定を受け入れる限り、実は可能であることを示しています。

彼らは以下のことを示しました：

1. それは機能する： 魔法の代わりに「計算的深度」を用いることで、これらの証明を構築できます。
2. それは効率的である： 正直なユーザーは、極端に過酷な作業を行う必要はありませんが、データを保存する必要はあります。
3. それは安全である： もし誰かが、より少ないデータを保存することでプロトコルを回避しようとしても、基礎となる問題が困難であり続ける限り、数学的にほぼ確実に捕まることになります。

要するに、ボールとグアンは、プルーフ・オブ・スペースを「魔法のブラックボックス」の領域から連れ出し、複雑性理論の土壌へとしっかりと植え付けました。適切な仮定があれば、計算の法則が許容する限り、デジタル・ウェアハウスを構築できることを示したのです。