証明システムを 3 つの部品に分ける――GKR・STARK・PLONK と、嘘がすり抜ける確率
zk-tokyo Advanced Cryptography Program 2026 の Week 4 は「証明」と「ゼロ知識性」でした。NP から IP・PCP・IOP へ、そして GKR・STARK・PLONK を算術化・コミットメント・証明システムの 3 部品で並べます。同じトイ計算を 3 通りに翻訳し、嘘の証明者が何回に 1 回すり抜けるかを数えました。
zk-tokyo のAdvanced Cryptography Program 2026を受講しています。Week 4 のテーマは「証明」と「ゼロ知識性」で、講義はまず「そもそも証明とは何か」を日常の証明から分解し、計算複雑性の言葉で置き直したうえで、GKR・STARK・PLONK の 3 スキームを毎回同じ 3 つの箱で説明していました。
今回の収穫は、どのスキームも「算術化・コミットメント・証明システム」の 3 部品でできていて、違うのは箱の中身だけだと分かったことです。
- 自習ノート: 証明システムを 3 つの部品に分ける
- 週ごとの目次: Advanced Cryptography 2026 自習ノート
- リポジトリ: susumutomita/advanced-cryptography-note
証明を 5 つに分ける
講義の入り口は数学ではなく、身分証や領収書でした。証明という行為は、証明者・証明方法・証明対象・検証方法・検証者の 5 パートに分けられます。身分証は発行元を、領収書は紙を、アリバイは証言者を信頼している。数学的証明が違うのは、検証方法が機械的で、証明者を信頼する必要がないことです。
ただし 1 つ弱点が残ります。証明が長ければ検証も長い。1 万行の計算を確かめるのに 1 万行読み直すなら、証明者と検証者の手間は同じです。「弱い検証者が、強い証明者の主張を、短い時間で確かめる」には、読まずに納得できる仕掛けが要ります。
NP は、最も標準的な証明システム
その仕掛けの土台が計算複雑性です。NP は「答えの候補を渡されれば、多項式時間で正しいと確かめられる」問題の集まりでした。講義のグラフ 3 彩色を実際に数えると、こうなります。
総当たりで試した塗り方 : 59049 通り（3^10）
そのうち条件を満たすもの : 120 通り
1 つの塗り方を検証する手数 : 15 回（辺ごとに両端の色を見比べるだけ）見つけるのは大変で、確かめるのは楽。この非対称がそのまま「証明者は強くてよい、検証者は弱くてよい」という証明システムの形です。ここに対話・ランダム性・オラクルアクセスの 3 つを足していくと IP・PCP・IOP になり、現代のゼロ知識証明の主流は IOP でした。オラクルの実体がコミットメントで、先週の commitment はここで使うために出てきたのだと繋がりました。
同じ計算を 3 通りに翻訳する
講義はf = (x1 + x2) + (x3·x4)という 1 つのトイ計算を、3 スキームそれぞれで翻訳していました。ノートでは全部の数値を自分で計算し直しています。
| GKR | STARK | PLONK | |
|---|---|---|---|
| 算術化 | レイヤー付き回路 → 多重線形多項式 | 実行トレース → AIR | ゲート表 → 11 本の一変数多項式 |
| コミットメント | 元論文ではなし | Merkle 木 | KZG（ペアリング） |
| 証明システム | SumCheck | FRI | KZG の開示 + ゼロテスト + 大積 |
面白いのは、3 つとも同じ道具を使い回していることです。表を多項式にするラグランジュ補間、「H の全点で 0」を「消滅多項式で割り切れる」に変える因数定理、違う多項式はランダムな点でほぼ違う値になる Schwartz–Zippel、複数の検査をランダムな係数で 1 本にまとめる線形結合。道具は 4 つ、並べ方が 3 通りでした。
嘘の証明者は、何回に 1 回すり抜けるか
健全性は「絶対に落ちる」ではなく「ランダムな点で聞くから、ほぼ落ちる」です。ノートでは体を小さくして、その「ほぼ」を数えました。
SumCheck（GKR）。本当の値は 1 なのに「5 だ」と主張し、和だけ合わせた偽の多項式を送る証明者を用意して、検証者の乱数の組を 11 × 11 通り全部試した結果です。
受理されてしまう組 : 21 通り（r1 = 1 または r2 = 1 のとき）
嘘が露見する組 : 100 通り
すり抜ける確率 : 21 / 121 ≈ 17%（254 ビットの体なら ≈ 0）STARK。トレースの最終結果を 12 から 13 に 1 マス書き換えると、制約多項式が評価ドメインの上で 0 にならず、消滅多項式で割った余りが残ります。それでも点ごとに割った値を無理に補間すると、次数が 2 から 7 に跳ね上がる。低次数テストが落とす形です。
PLONK。gate 2 の左入力を 4 から 5 に、出力を 12 から 13 に変えると、3 行のゲート方程式はすべて通ります。落とすのは配線を見るコピー制約で、大積は88 ≠ 75と不一致になる。行の中を見る制約と、行をまたぐ制約は別の目でした。
ゼロ知識性は、あとから足す
ここまでのスキームは、実はゼロ知識ではありません。開示される多項式の値は witness から作られているので、集めれば情報が漏れます。講義の後半はそれを塞ぐ手で、要はf + Z_H·Rという形でランダムな多項式を足す。消滅多項式Z_Hは評価ドメインの上で 0 なので制約の検査は壊れず、検証者が値を聞くドメインの外ではランダムになる。先週のs = r + e·xで秘密を乱数rが覆っていたのと同じ構図で、覆う量が数 1 個から多項式 1 本に増えただけでした。
自習ノートを公開しました
単一の HTML ファイルで、外部への通信はありません。検証者として乱数を選んで嘘の証明者を追い詰める SumCheck ラボ（121 通りの受理地図つき）、トレースのマスを書き換えて商多項式が消えるのを見る STARK ラボ、ゲート表を書き換えてゲート制約と大積を同時に見る PLONK ラボが付いています。検問クイズは証明システム・SumCheck・AIR/商・FRI・PLONK・原理の 6 分野から毎回その場で出題され、判定はラボと同じ計算器が行います。