ゼロ知識証明（SNARK・STARK）

ゼロ知識性とは何を意味するか

ゼロ知識証明（Zero-Knowledge Proof, ZKP）は、ある命題が真であることを、なぜ真なのかを一切漏らさずに相手へ納得させる暗号プロトコルです。証明する側を証明者（prover）、確かめる側を**検証者（verifier）**と呼びます。古典的な例が「洞窟の問題」です。環状の通路の奥に秘密の扉があり、証明者はその合言葉を知っている。証明者は先に分岐のどちらかへ進み、検証者が「右から出てこい／左から出てこい」と指定する。合言葉を知っていれば扉を通って必ず指定側から出られますが、知らなければ2分の1でしか当たりません。これを何度も繰り返せば、合言葉そのものを口にせずに「知っている」ことだけを高確率で示せます。

ZKPが満たすべき性質は3つです。

ゼロ知識性の厳密な定義はシミュレータで与えられます。証明者と一切やり取りせず、命題が真という情報だけを持つシミュレータが、本物のやり取りと**区別できない偽の記録（トランスクリプト）**を生成できるなら、その記録には証拠の情報が含まれていない、と結論できます。区別不能性の強さに応じて完全・統計的・計算量的ゼロ知識に分かれます。

検証可能計算という枠組み

ブロックチェーンでZKPが強力なのは、「秘密を隠す」用途以上に検証可能計算（verifiable computation）として使えるからです。すなわち「ある関数 f に入力 x を与えたら出力 y になった」という計算の正しさを、検証者が f を再実行せずに確かめられる。証明サイズと検証時間が入力規模に対して劣線形（多くは対数〜定数）になるのが鍵です。証明者の計算は重くても、検証者は軽い——この非対称性がスケーリングの源泉です。

そのために、まず証明したい計算を数学的な制約の集合へ翻訳します。代表的なのが算術回路と、それを1本ずつの掛け算・足し算の制約に落としたR1CS（Rank-1 Constraint System）や、行方向に一様なAIR（Algebraic Intermediate Representation）です。制約が「すべて成り立つ」ことは、対応する多項式が特定の点でゼロになることと同値に変換できます。

計算 → 算術回路 → 制約系(R1CS / AIR) → 多項式の等式
                                          ↓
       「制約を全部満たす代入が存在する」
     = 「ある多項式が消失点の集合で 0 になる」

証明者は「その多項式を確かに知っている」ことを、多項式全体を送らずに示します。ここで使うのが多項式コミットメントです。多項式に短いコミット値を発行し、検証者が指定した点での評価値だけを、コミットと整合することの証明つきで開示します。シュワルツ・ジッペルの補題により、次数が上限未満の相異なる2つの多項式がランダムな1点で一致する確率は極めて低い。ゆえに数点の検査で多項式全体の正しさをほぼ保証できます。SNARKとSTARKの技術的な違いの多くは、この「多項式コミットメントをどう作るか」の違いに帰着します。

zk-SNARK と zk-STARK の違い

SNARKは Succinct Non-interactive ARgument of Knowledge の略で、簡潔（succinct）＝証明が小さく検証が速いことを主眼にします。STARKは Scalable Transparent ARgument of Knowledge で、透明（transparent）＝信頼できるセットアップが不要であることを主眼にします。両者は目的が近く方式が異なる兄弟です。

決定的な差は3点です。第一に信頼できるセットアップ。多くのSNARK（Groth16など）は回路ごとに秘密乱数から公開パラメータ（CRS）を作ります。この乱数は有害廃棄物（toxic waste）と呼ばれ、誰か一人でも破棄せず保持すると、偽の証明を作れてしまう——存在しない残高の証明すら通ってしまうため、健全性が崩れます。実務では多数参加者によるMPC儀式（powers of tau など）を行い、「1人でも正直に廃棄すれば安全」という形に薄めます。PLONK系は汎用（universal）かつ更新可能なセットアップを使い、回路が変わるたびの再儀式を不要にしました。STARKはハッシュの公開値だけで動くため、そもそも秘密が存在せずセットアップが透明です。

第二に耐量子性。SNARKの多くは楕円曲線上の離散対数の困難性に依存し、これはショアのアルゴリズム（/security/ の格子・耐量子暗号の議論とも関わる）で量子計算機に破られます。STARKは衝突耐性ハッシュだけを前提にするため、量子計算機でも安全余裕が大きい（/quantum/ の量子アルゴリズムの文脈で、グローバーによる二次加速はあってもハッシュ長で吸収できる）。

第三に証明サイズと検証コストのトレードオフ。SNARKは証明が数百バイトと極小で検証もほぼ定数時間。STARKは証明が数十〜数百KBと大きい代わりに、透明性と耐量子性を得ています。STARKが依存する多項式コミットメントFRI（Fast Reed–Solomon IOP of Proximity）は、低次多項式への近さをハッシュベースのマークル木で反復的に検査する仕組みで、証明サイズを入力規模の対数に抑えます。

プライバシーとスケーリングへの応用

ブロックチェーンでのZKPは、大きく2つの目的に整理できます。プライバシーとスケーリングで、後者が近年の主戦場です。

プライバシー送金の代表がZcashです。UTXOの金額と宛先をコミットメントで隠したまま、「使おうとしている残高は確かに存在し、まだ使われておらず、入出金の総額が一致する」ことをzk-SNARKで証明します。台帳には暗号化されたコミットメントと無効化子（nullifier）だけが載り、金額は誰にも見えないのに二重支払いは防げます。

ZKロールアップはスケーリングの本命です。L2（レイヤー2）が多数の取引をオフチェーンで実行し、まとめた後の状態遷移が正しいことを示す妥当性証明（validity proof）を1個だけL1（メインチェーン）へ提出します。L1は個々の取引を再実行せず、短い証明を検証するだけで巨大なバッチを受理できる——まさに検証可能計算の非対称性です。ここで簡潔性が本質になります。1万件の取引を処理しても証明サイズと検証コストがほとんど増えないからこそ、スループットを大きく引き上げられます。

まとめ

• ゼロ知識証明は、証拠を明かさず命題の真偽だけを納得させる。完全性・健全性・ゼロ知識性を満たし、ゼロ知識性はシミュレータで厳密化される。Fiat–Shamir変換で非対話化する。
• 実体は検証可能計算。計算を算術回路→制約系（R1CS/AIR）→多項式へ変換し、多項式コミットメントで数点の検査に帰着。証明者は重く検証者は軽い非対称性がスケーリングを生む。
• zk-SNARKは証明が数百バイトと極小で検証も高速だが、多くが信頼セットアップ（有害廃棄物）を要し、ペアリング前提で量子に弱い。zk-STARKはハッシュのみで透明・耐量子だが証明は数十〜数百KBと大きい。
• 応用はプライバシー（Zcashの秘匿送金）とスケーリング（ZKロールアップ）。後者は簡潔性を活かし、大量取引の妥当性を1証明でL1へ即時確定させる点がOptimisticとの本質的な差になる。