対話型証明と計算の委譲 — Epoche C2
場面設定 トロント・フィールズ数学研究所。計算複雑性理論の年次ワークショップのポスターセッションにて。対話型証明やPCP定理の理論的基盤を研究するカナダ人理論計算機科学者トマスと、ゼロ知識証明を用いたブロックチェーン上のスケーラビリティ（SNARKs）を研究するインド人計算量理論家アニルが、証明の「検証可能性」のパラダイムについて議論している。 イントロダクション 1980年代にゴールドワッサー、ミカリ、ラッコフらによって導入された「対話型証明（Interactive Proofs: IP）」は、証明者（Prover）と検証者（Verifier）の間の通信プロセスとして「証明」を再定義し、計算機科学に革命をもたらした。さらに1990年代の「PCPの定理（確率的検証可能証明）」は、証明書のほんの数ビットをランダムにチェックするだけでその正しさを極めて高い確率で保証できることを示した。現在、これらの純粋理論は「zk-SNARKs（ゼロ知識簡潔非対話型知識論証）」として実装され、ブロックチェーンにおけるプライバシー保護と計算の委譲（スケーラビリティ）を支える中核技術となっている。本対話では、理論計算機科学の最も深い結果が、いかにして実社会の暗号プロトコルへと変貌を遂げたかを議論する。 トマス、君の「PCPの定理」の最適化に関するポスターは非常に示唆に富んでいた。クエリ複雑性をどこまで減らせるかという純粋理論の追求が、今や我々が開発しているSNARK（簡潔非対話型知識論証）の効率に直結する時代になったね。 ありがとう、アニル。1990年代にPCPの定理が証明されたとき、それは「近似アルゴリズムの限界（近似困難性）」を示すための理論的ツールだった。証明の検証に要する時間が、元の証明の長さに依存しない（対数サイズ）なんて、当時は純粋数学の魔法だと思われていたよ。 それが今や、イーサリアムのロールアップ（Layer 2）を支えている。何百万ものトランザクションの正当性を証明する重い計算（Proving）をクラウド上の強力な証明者に「委譲」し、ブロックチェーン上の制約された検証者は、そのPCP証明から変換された数バイトのSNARK証明をミリ秒で検証する。 まさに「計算の委譲（Delegation of Computation）」の実用化だ。しかし、純粋理論の立場から言わせてもらえば、PCPを直接使うKilianやMicaliの構成は証明サイズがまだ大きすぎた。君たち応用層がGroth16やPlonkのようなアルゴリズムでそこまで証明を短く（簡潔性に）できたのは、ある種の代数的な「トリック」だよね。 トリックとは人聞きが悪い（笑）。我々は「多項式コミットメント（Polynomial Commitment）」という暗号学的な道具を使ったんだ。計算過程を算術回路（Arithmetic circuit）に変換し、それを巨大な多項式の等式関係（QAP等）で表現する。そして、その多項式の「ランダムな一点」での評価値を検証する。 シュワルツ・ジッペルの補題（Schwartz-Zippel lemma）の応用だね。異なる2つの低次多項式がランダムな点で一致する確率は無視できるほど小さい。対話型証明（IP）のIP=PSPACEの証明や、Sum-checkプロトコルの中核をなす代数的手法だ。 その通り。問題は、その「ランダムな点」を証明者に教えずに、どうやって多項式を評価させるかだ。そこで楕円曲線暗号上の双線形ペアリング（Bilinear pairing）や「信頼できるセットアップ（Trusted Setup）」が必要になる。 そこが理論家として最も気持ち悪い部分だ！ 「知識の健全性（Knowledge Soundness）」を証明するために、非反証可能な暗号学的仮定（Knowledge of Exponent仮定など）を導入せざるを得ない。しかもセットアップ時の秘密情報（Toxic waste）が漏洩すれば、偽の証明が作り放題になる。 我々もそれは認識している。だからこそ、STARKsやFRIプロトコルのような、信頼できるセットアップを必要としない「透明な（Transparent）」証明システムへと移行しつつある。ここでは再びPCP的なアプローチ、つまりハッシュ関数だけを信頼の根拠にするFiat-Shamir変換が主役になっている。 ハッシュ関数に基づくなら量子耐性（Post-Quantum）も備わるね。しかし、完全性（Completeness）と健全性（Soundness）という計算複雑性理論の純粋な概念が、これほど莫大な資本を動かす現実のシステムに直結している状況は、未だに信じがたいよ。 アラン・チューリングやスティーブン・クックが「計算とは何か」を問うたところから始まり、今我々は「その計算が正しく行われたことを、再計算せずにどう証明するか」という次のフェーズにいる。そしてゼロ知識性（Zero-Knowledge）を使えば、その計算の中身（プライバシー）すら明かす必要がない。 まさに「証明の性質」のパラダイムシフトだ。ユークリッド以来、数学的証明とは「すべての行を順に追って確認できる論理の鎖」だった。対話型証明とPCPは、それを「乱択化された確率的な対話」へと変質させた。 そして我々エンジニアが、それを暗号学の力で「非対話型の数バイトの文字列」へと圧縮した。理論と応用、数学と暗号学の美しいキャッチボールだよ。 次はGKRプロトコルのような、対話型証明を並列計算へ適用する方向が実用化されるだろう。証明者（Prover）の計算ボトルネックを解消できれば、SNARKはブロックチェーンの枠を超えて、すべてのクラウド計算の基盤になる。 ええ。「Verify, don't trust（信頼するな、検証せよ）」。サイファーパンクの教義は、君たち理論計算機科学者の定理によって、ついに数学的な真理となったんだよ。さあ、セッションに戻ろうか。我々のこの議論が正しかったか、他の研究者と「対話型証明」をするためにね。 解説 論証の構造: 「証明とはすべてのステップを検証者が追うものである」という古典的見解（正）に対し、「対話と乱択化（PCP定理）」による新しい証明概念（反）を提示し、暗号学的コミットメントと結合することで、実世界のブロックチェーンのスケーラビリティを解決するSNARKs（合）へと至る論証プロセス。 専門用語の解説: 「対話型証明（IP）」は、全能の証明者と多項式時間の検証者が通信を行いながら命題の真偽を確かめるシステム。「PCPの定理」は、すべてのNP問題の証明が、ランダムな数ビットを検証するだけで定数確率で正しさを判定できる形式に変換可能であることを示す定理。「SNARK（簡潔非対話型知識論証）」は、証明のサイズが極めて小さく、かつ検証時間がミリ秒単位で済む暗号技術。「多項式コミットメント」は、多項式の値を明かさずに「私はこの多項式を知っている」ことを暗号学的に誓約（コミット）し、後で特定の一点での評価値だけを証明する技術。 各話者の立場分析: トマスは理論家として、IPやPCP定理の美しさを愛しつつ、応用層の暗号学的仮定（信頼できるセットアップや非反証可能な仮定）の理論的危うさを指摘する。アニルは応用（プロトコル設計）の立場から、理論の制約を代数的トリックで突破し、現実の「計算の委譲」というエンジニアリング上の巨大な問題を解決した実践的価値を強調する。 言語的特徴: "Delegation of Computation"（計算の委譲）、"Soundness"（健全性）、"Polynomial Commitment"（多項式コミットメント）など、計算複雑性理論と現代暗号学を橋渡しする高度な専門用語が対話の軸となっている。 まとめ 得られた知見: 対話型証明やPCPの定理といった1990年代の純粋な計算複雑性理論のブレークスルーは、多項式コミットメントなどの暗号学的手法（SNARKs等）と結合することで、「膨大な計算結果の正当性を、再計算することなく一瞬で検証できる」という実社会の魔法（計算の委譲）を実現した。 残された問い: 極めて短い証明サイズを実現する代償として導入される「信頼できるセットアップ（Trusted Setup）」の運用リスクや、「非反証可能な暗号学的仮定」に依存する現在の証明システムの安全性を、理論的にどこまで強固にできるか。 今後の展望: セットアップを必要としないSTARKsや、ハッシュ関数のみに依存する量子耐性を持つ証明システムへの移行が進んでいる。将来的には、ブロックチェーンの枠を超え、あらゆるクラウドコンピューティングの正当性を担保するインフラストラクチャになることが期待される。 参考文献 S. Arora et al. (1998). "Proof verification and the hardness of approximation problems". Journal of the ACM , 45(3), 501-555. S. Goldwasser, S. Micali, and C. Rackoff (1989). "The knowledge complexity of interactive proof systems". SIAM Journal on Computing , 18(1), 186-208. L. Babai (1985). "Trading group theory for randomness". Proceedings of the seventeenth annual ACM symposium on Theory of computing , 421-429. E. Ben-Sasson et al. (2014). "SNARKs for C: Verifying program executions succinctly and in zero knowledge". CRYPTO 2014 , 90-108. A. Chiesa et al. (2020). "Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS". EUROCRYPT 2020 .