ゼロ知識証明（ZKP）の原理と zk-SNARK の構成

解きたい問題：根拠を見せずに正しさを納得させる

通常、何かを証明するには根拠を提示します。残高があることを示すには口座を見せ、鍵を持つことを示すには鍵そのものを使います。しかしこれは秘密を相手に渡してしまう。パスワードを送れば、検証側はそれを保存・流用・漏洩できてしまいます。

ゼロ知識証明（Zero-Knowledge Proof, ZKP）が解くのはこの矛盾です。「ある主張が真である」という一点だけを相手に確信させ、その根拠となる秘密（証人 witness）は一切明かさない。証明者（prover）は「私はこの問題の解を知っている」と示すが、検証者（verifier）はその解を学習できない。これが ZKP の核心です。

古典的なたとえが「洞窟の問題」です。輪状の通路の奥に合言葉付きの扉があり、証明者は合言葉を知っていると主張します。検証者は分岐点で待ち、証明者が奥へ入った後で「右から戻れ」「左から戻れ」とランダムに指定する。合言葉を知っていればどちらからも戻れ、知らなければ運任せで半分しか成功しません。これを何度も繰り返せば、検証者は合言葉自体を聞かずに「証明者は知っている」と確信できます。

ZKP を成立させる三つの性質

ZKP が正しく機能するには、次の三性質を同時に満たす必要があります。一つでも欠ければ証明として無意味です。

ゼロ知識性の厳密な定義が興味深い点です。「検証者が何も学ばない」をどう数学で表すか。答えがシミュレータ論法です。秘密を全く知らないシミュレータが、本物のやり取り（トランスクリプト）と区別できない偽のトランスクリプトを作れるなら、そのやり取りには秘密の情報が含まれていない、と論証します。本物と偽物が見分けられない以上、本物を見ても秘密は得られないからです。

対話型から非対話型へ：Fiat-Shamir 変換

洞窟の例は対話型でした。検証者が毎回ランダムなチャレンジ（「右」「左」）を投げ、証明者が応答する往復が必要です。しかし実務では、証明者が一度証明を作って公開し、誰でも後から検証できる形が望ましい。ブロックチェーンのように検証者が一人に決まらない場面では対話は成立しません。

この非対話化を実現する古典的な手法が Fiat-Shamir 変換です。発想は単純で強力です。検証者が選ぶはずだったランダムなチャレンジを、それまでのメッセージ全体のハッシュ値で置き換えるのです。

対話型:
  Prover  → コミットメント c
  Verifier→ ランダムなチャレンジ e   ← 検証者が選ぶ
  Prover  → 応答 r
  Verifier: (c, e, r) を検証

非対話型 (Fiat-Shamir):
  Prover  → コミットメント c
  Prover  : e = Hash(公開情報 || c)   ← ハッシュで「自分で」生成
  Prover  → 応答 r
  検証者  : e = Hash(...) を再計算し (c, e, r) を検証

なぜこれで健全性が保たれるのか。チャレンジ e を証明者が自由に選べると不正の余地が生まれますが、e をコミットメント c を含むハッシュで決めると、証明者は c を出した後でしか e を知れません。ハッシュの一方向性により e を狙って c を逆算することもできない。結果として、検証者がランダムに選んだのと実質的に同じ予測不可能性が得られます。これは安全性証明でランダムオラクルモデルを前提として正当化されます。

zk-SNARK の構成：計算を多項式に変換する

zk-SNARK（Zero-Knowledge Succinct Non-interactive ARgument of Knowledge）は、ZKP に二つの強力な性質を加えたものです。Succinct（簡潔）＝証明サイズが極小（数百バイト）で検証が高速、Non-interactive（非対話）＝一往復で済む。任意の計算について「私はこの計算を正しく実行する入力を知っている」を、入力を明かさず証明できます。

核心は、証明したい計算を多項式の等式チェックに変換することです。変換は段階的に進みます。

① 計算（プログラム）
   例: 「ハッシュ H(x) = y となる x を知っている」

② 算術回路 (Arithmetic Circuit)
   計算を加算ゲートと乗算ゲートだけの回路に展開する

③ R1CS (Rank-1 Constraint System)
   各ゲートを a・b = c 形式の制約に変換し、制約の集合にする

④ QAP (Quadratic Arithmetic Program)
   R1CS の制約群を一本の多項式の等式に圧縮する
   → 「全制約を満たす ⇔ ある多項式が目標多項式で割り切れる」

最後の QAP が鍵です。R1CS の数千個の制約を満たすかどうかの判定が、「証明者の多項式 P(x) が、既知の目標多項式 T(x) で割り切れるか」というたった一つの多項式の整除性チェックに帰着します。割り切れること、すなわち P(x) = T(x)・H(x) となる商 H(x) が存在することが、計算が正しく実行された証拠になります。

ここでなぜ証明が簡潔になるのか。多項式の等式 P = T・H が成り立つかを全ての x で確かめる必要はありません。ランダムに選んだ一点 s で P(s) = T(s)・H(s) を確認すれば十分です。次数 d 未満の相異なる二つの多項式が一致する点はたかだか d 個しかないため、不正な証明者がランダムな一点 s でたまたま等式を成立させられる確率は無視できるほど小さい（シュワルツ-ジッペルの補題）。1 点での評価値だけを検証すればよいので、証明が極小化されます。

zk-STARK との対比とブロックチェーン応用

zk-SNARK の Trusted Setup と楕円曲線依存を嫌い、別構成を取るのが zk-STARK（Scalable Transparent ARgument of Knowledge）です。違いは設計思想に表れます。

zk-STARK がハッシュ関数の安全性だけに依拠する点は重要です。楕円曲線の離散対数は量子計算機（Shor のアルゴリズム）で破れますが、ハッシュは Grover で強度が半減する程度なので、STARK は原理的に量子耐性を持ちます。Setup も不要なため信頼の前提が一つ減ります。

ブロックチェーンが ZKP の主要な応用先になったのには明確な理由があります。第一がプライバシーで、匿名通貨 Zcash は zk-SNARK により「送金額と送受信者を隠したまま、二重支払いがない正当な取引である」ことを証明します。第二がスケーラビリティで、ZK-Rollup は数千件の取引をオフチェーンで実行し、その正しさを一つの簡潔な証明にまとめてオンチェーンに提出します。検証側（メインチェーン）は全取引を再実行せず、小さな証明を検証するだけで全体の正当性を確認できる。「重い計算を一度だけ行い、その正しさを誰でも安く検証できる」という zk-SNARK の簡潔性が、そのままスループット向上に直結します。

まとめ

ゼロ知識証明は、主張が真であること以外を一切漏らさずに正しさを納得させる仕組みで、完全性・健全性・ゼロ知識性の三性質を同時に満たして初めて成立します。健全性は確率的に保証され、繰り返しで誤り確率を指数的に潰します。Fiat-Shamir 変換は検証者のランダムチャレンジをメッセージのハッシュで置き換え、対話型証明を一往復・公開検証可能な非対話型に変えます。

zk-SNARK は計算を算術回路→R1CS→QAP と変換し、最終的に多項式の整除性をランダムな一点で確認することで、数百バイトの極小な証明と高速検証を実現します。その代償が Trusted Setup と楕円曲線への依存で、これを排して透明性と量子耐性を得るのが zk-STARK です。Zcash のプライバシー保護や ZK-Rollup のスケーリングなど、ブロックチェーンが主戦場になっています。土台となるハッシュの一方向性は ハッシュ関数の構成、楕円曲線とペアリングの数理は 楕円曲線暗号の内部、量子耐性の議論は ポスト量子暗号、公開鍵と署名の基礎は 暗号の基礎 と併せて押さえると理解が深まります。