証明システムを、3 つの部品に分ける — 予習ノート

時間（ステップ数）、空間（メモリ）、それに証明の話で効いてくる通信量と 回路サイズ。n が 2 倍になったとき手数が 2 倍で済むのが O(n)、 2 乗になるのが O(n²)、2 倍ごとに倍々になるのが O(2ⁿ)。

Week 3 の double-and-add がまさにこの話でした。k·G を「G を k 回足す」と O(k)、2 進で見て倍々に作ると O(log k)。secp256k1 の k ≈ 2²⁵⁶ では 前者は終わらず、後者は 10 ms で終わります。同じ答えでも、手数の増え方が違えば 「できる／できない」が変わる。

P は、多項式時間（O(n)、O(n²)、…）で 答えを見つけられる問題の集まり。NP は、答えの候補（証拠、witness）を 渡されたときに、多項式時間で正しいと確かめられる問題の集まりです。

講義の例はグラフの 3 彩色でした。「隣り合う頂点が同じ色にならないように 3 色で塗れるか」。 塗り方を見つけるのは総当たりだと 3ⁿ 通り。 塗り方を確かめるのは辺の数だけ色を見比べればよい。 実際に講義のグラフ（ピーターセングラフ、頂点 10・辺 15）で数えました。

総当たりで試した塗り方   : 59049 通り（3¹⁰）
そのうち条件を満たすもの : 120 通り
1 つの塗り方を検証する手数 : 15 回（辺ごとに「両端が違う色か」を見るだけ）

ここが今週いちばん大事な一文です。NP は「証拠を渡せば、弱い検証者でも速く確かめられる」問題の集まり。 つまり NP は、最も標準的な証明システムそのものです。証明者は無限に強くてよい（塗り方を見つける）。 検証者は多項式時間しか使えない（塗り方を確かめる）。Week 3 の「x を知っている」も、 「回路を正しく実行した」も、全部この形に収まります。

NP のままでは、証拠（塗り方、計算の記録）を丸ごと渡すので、検証は証拠の長さに比例します。 ここに 3 つの材料を足します。

PCP 定理は驚くべき主張です。NP の証拠は、書き方を工夫すれば 「検証者がランダムに数か所だけ読めば十分」な形に書き直せる。1 万行の証明を 1 万行読む必要はない。 ただし証明者があとから書き換えられないことが条件で、それを保証するのが「オラクル」—— 現実にはコミットメント（Merkle 木や KZG）です。先週の commitment は、ここで使うために出てきました。

対話型と非対話型の使い分け（講義の Q）。対話型は「特定の検証者を、その場で」納得させるのに向き、 非対話型（Fiat–Shamir で e をハッシュにしたもの）は「誰でも、あとから、オンチェーンで」検証できる。 先週の Schnorr → 署名の変換と、まったく同じ手です。

L₀ : y  = y₀ + y₁                       出力: 1
L₁ : y₀ = x₁ + x₂ ,  y₁ = x₃ · x₄        値: 4, 8
L₂ : x₁, x₂, x₃, x₄ ∈ F₁₁               入力: 3, 1, 2, 4

ゲートに 2 進の番地をつける:  L₁ の 2 個 → 0, 1   L₂ の 4 個 → 00, 01, 10, 11
f(3,1,2,4) = (3 + 1) + (2 · 4) = 12 ≡ 1 (mod 11)

Week 1 の算術回路そのものです。違いは、レイヤーごとに区切って 「各レイヤーの値の表」と「レイヤー間の配線の表」を別々に扱うこと。 前者は秘密（witness）、後者は公開（回路の形）です。

レイヤー 2 の値の表は「番地 (z₁,z₂) → 値」で 00→3, 01→1, 10→2, 11→4。 これを、0/1 の格子点では表と一致し、格子の外まで滑らかに伸ばした唯一の多項式にします。 各変数について 1 次（線形）なので「多重線形」です。

W̃₂(z₁,z₂) = 3(1−z₁)(1−z₂) + 1(1−z₁)z₂ + 2z₁(1−z₂) + 4z₁z₂
           = 3 − z₁ − 2z₂ + 4z₁z₂            ← 展開して整理（mod 11 で係数は 3, 10, 9, 4）

W̃₁(z) = 4(1−z) + 8z = 4 + 4z                 ← レイヤー 1 の表 {0→4, 1→8}
W̃₀( ) = 1                                     ← レイヤー 0（変数なし）

なぜ 0/1 の外まで伸ばすのか。あとで検証者が 0 でも 1 でもないランダムな点で値を聞くからです。 表のままなら「番地 2」に値はありませんが、多項式にしておけば W̃₁(2) = 4 + 8 = 12 ≡ 1 が定まる。 ランダムな点で聞けるようにすることが、少ない手数で嘘を見つける仕掛けの土台になります。

配線の表も多項式にします。レイヤー 0 のゲートは「レイヤー 1 の番地 0 と番地 1 を足す」でした。 それを式にしたのが g₀ です。

g₀(a, b) = (1−a) · b · ( W̃₁(a) + W̃₁(b) )
             ↑ (a,b) = (0,1) のときだけ 1、それ以外の格子点では 0
W̃₀ = Σ_{a,b∈{0,1}} g₀(a,b) = g₀(0,1) = 1·(4 + 8) = 12 ≡ 1  ✓

ここで主張の形が決まります。「レイヤー 0 の値は 1 である」は 「ある多項式 g₀ を 0/1 の全組み合わせで足すと 1 になる」という形に書き直された。 レイヤーが深くなっても、主張は必ずこの「格子点全部の和」の形になります。 格子点は変数の数を k とすると 2ᵏ 個。検証者はこれを全部足したくない。

変数を 1 つずつ「潰し」ます。各ラウンドで証明者は一変数多項式を送り、 検証者は2 点の値を足すだけで前ラウンドと辻褄が合うか見て、 ランダムな点でその多項式を評価し、それを次ラウンドの「主張」にします。

主張: Σ_{a,b} g₀(a,b) = 1

ラウンド 0（a を潰す）
  証明者 → p₁(x) = Σ_{b∈{0,1}} g₀(x,b) = g₀(x,0) + g₀(x,1)
                = 0 + (1−x)·(W̃₁(x) + W̃₁(1)) = (1−x)(12 + 4x)
                = 12 − 8x − 4x² ≡ 1 + 3x + 7x²  (mod 11)
  検証者:  p₁(0) + p₁(1) = 1 + 11 = 12 ≡ 1  … 主張と一致 ✓
           r₁ = 2 を選ぶ → p₁(2) = 1 + 6 + 28 = 35 ≡ 2   ← 次の主張は「g₀(2, b) の b についての和 = 2」

ラウンド 1（b を潰す）
  証明者 → p₂(y) = g₀(2, y) = (1−2)·y·(W̃₁(2) + W̃₁(y)) = −y(16 + 4y)
                = −5y − 4y² ≡ 6y + 7y²  (mod 11)
  検証者:  p₂(0) + p₂(1) = 0 + 13 = 13 ≡ 2  … 前ラウンドの p₁(2) と一致 ✓
           r₂ = 3 を選ぶ → p₂(3) = 18 + 63 = 81 ≡ 4

最後（自分で 1 点だけ計算する）
  検証者:  g₀(2, 3) = (1−2)·3·(W̃₁(2) + W̃₁(3)) = −3·(1 + 5) = −18 ≡ 4  … p₂(3) と一致 ✓

検証者がやったこと: 各ラウンドで 2 点の値の足し算と 1 点の評価、最後に g₀ を 1 回だけ評価。 4 項の和（本物なら 2ᵏ 項）を一度も足していません。 それで納得できる理由は、嘘をつくなら多項式そのものを変えるしかなく、 違う多項式は 0/1 以外のほとんどの点で値が違うから。ランダムな r で聞けば高い確率でずれが出ます。

ただし最後の 1 行に注意。検証者は g₀(2,3) を計算するのに W̃₁(2) と W̃₁(3) が要ります。 これはレイヤー 1 の値の表（秘密）から作る多項式なので、検証者は自分では計算できません。 そこで証明者が「W̃₁(2) = 1、W̃₁(3) = 5 です」と主張し、その 2 つが次のレイヤーで確かめる新しい主張になります。 「レイヤー 0 の和」が「レイヤー 1 の 2 点の値」に置き換わった——これが「1 段降りる」の正体です。

2 点のまま降りると、次は 4 点、その次は 8 点と倍々に増えます。 そこで2 点を通る直線を引き、W̃₁ をその直線上に制限した一変数多項式 qを証明者に送らせ、 直線上のランダムな 1 点だけを次の主張にします。

2 点 u = 2, v = 3 を通る直線:  l(t) = (1−t)·2 + t·3 = 2 + t
証明者 → q(t) = W̃₁(l(t)) = 4 + 4(2 + t) = 12 + 4t ≡ 1 + 4t
検証者:  q(0) = 1 = 主張された W̃₁(2) ✓,  q(1) = 5 = 主張された W̃₁(3) ✓
         r = 4 を選ぶ → q(4) = 17 ≡ 6 → 新しい主張は「W̃₁(6) = 6」の 1 つだけ

この繰り返しで入力レイヤーまで降りると、最後の主張は「W̃₂(ある点) = ある値」になります。 入力は公開なので、検証者はこれだけは自分で計算して照合できる（入力が秘密ならコミットメントの開示で代える）。 回路の深さぶんだけラウンドを重ねて、最後に 1 回だけ本物の値に触る。これが GKR の全体です。

f(x₁,x₂,x₃,x₄) = (x₁ + x₂) + (x₃·x₄) ∈ F₁₇,   f(3,1,2,4) = 12

 t   a   m   y        ← a: 加算結果, m: 乗算結果, y: 最終結果
 0   0   0   0        初期状態
 1   4   0   0        a ← x₁ + x₂ = 4
 2   4   8   0        m ← x₃ · x₄ = 8
 3   4   8  12        y ← a + m = 12

回路とトレースの違い。回路は「値がどう繋がるか」の図、トレースは「時間ごとに状態がどう変わるか」の表。 CPU の命令実行や VM のように「同じ規則を何万ステップも繰り返す」計算は、トレースのほうが自然に書けます。 制約は「行と次の行の関係」だけで済み、ステップ数が増えても制約の種類は増えない。

行番号 t を、そのまま数字ではなく ω の t 乗に置きます。F₁₇ で ω = 4 は 4⁰=1, 4¹=4, 4²=16, 4³=13, 4⁴=1 と 4 回で 1 に戻る（位数 4）ので、 4 行の表にぴったりです。この 4 点 H = {1, 4, 16, 13} が評価ドメイン。

各列を、H の 4 点を通る 3 次以下の多項式に補間する（ラグランジュ補間）:
  A(X) = 3 − X − X² − X³         A(1)=0, A(4)=4, A(16)=4, A(13)=4  ✓
  M(X) = 4 + 6X + 7X³            M(1)=0, M(4)=0, M(16)=8, M(13)=8  ✓
  Y(X) = 3 + 12X + 14X² + 5X³    Y(1)=0, Y(4)=0, Y(16)=0, Y(13)=12 ✓

なぜ t を ω^t にするのか。「次の行」が X → ωX というただの掛け算になるからです。 A(ωX) は「1 行あとの a の値」を表す多項式になり、行と次の行の関係を A(X) と A(ωX) の式で書けます。 そして H が「ω の冪」であることが、次のステップの消滅多項式を X⁴ − 1 という短い形にします。

規則（遷移制約）:
  X = ω⁰ の行で  A(ωX) − 4 = 0                 （次の a は x₁+x₂ = 4）
  X = ω¹ の行で  M(ωX) − 8 = 0                 （次の m は x₃·x₄ = 8）
  X = ω² の行で  Y(ωX) − A(X) − M(X) = 0       （次の y は a + m）

S_i(X) を「H の中で ω^i でだけ 1、他では 0」の選択多項式として 1 本に足す:
  C(X) = S₀(X)(A(ωX) − 4) + S₁(X)(M(ωX) − 8) + S₂(X)(Y(ωX) − A(X) − M(X))
       = 2 − 5X − 5X² − 2X⁴ + 5X⁵ + 5X⁶      （mod 17 では 2 + 12X + 12X² + 15X⁴ + 5X⁵ + 5X⁶）
  C(1) = C(4) = C(16) = C(13) = 0             ← H の全点で 0。ここが「トレースが正しい」の言い換え

スライドの「= 0」は「多項式として 0」ではなく「H の全点で 0」の意味です。 C(X) 自体は 6 次の立派な多項式で、H の外では 0 になりません。 「H の全点で 0」を検証者がどう確かめるか——4 点なら全部評価すればよいが、 2²⁰ 行のトレースでは無理。次の一手が STARK の要です。

多項式 C が点 h で 0 なら、C は (X − h) で割り切れる（因数定理）。 H の全点で 0 なら、全部の (X − h) の積で割り切れる。 その積が消滅多項式 Z_H(X) = Π_{h∈H}(X − h) = X⁴ − 1 です （H が 1 の 4 乗根の集合だから、こんなに短い）。

Q₀(X) = C(X) / Z_H(X) = C(X) / (X⁴ − 1) = 5X² + 5X − 2      余り 0
検算: (X⁴ − 1)(5X² + 5X − 2) = 5X⁶ + 5X⁵ − 2X⁴ − 5X² − 5X + 2 = C(X) ✓

問いが入れ替わりました。「C は H の全点で 0 か」→「Q₀ = C / Z_H は多項式か（割り切れて余りが出ないか）」。 さらに Q₀ が多項式なら次数は deg C − 4 = 2 以下のはず。 だから検証者が確かめるべきことは 「証明者が持っている Q₀ は、次数 2 以下の多項式か」。 トレースが 1 か所でも間違っていれば、C は H のどこかで 0 にならず、Z_H で割り切れず、 Q₀ は多項式にならない（点ごとに値は作れても、低い次数の多項式にはならない）。

証明者は Q₀ を、H より広い評価ドメイン（例: g = 2 の冪、8 点 {1,2,4,8,16,15,13,9}）で評価し、 その値を葉にした Merkle 木を作り、根だけを検証者に渡します。 検証者があとで「g³ の値を見せて」と言えば、証明者は葉と経路を出す。根が固定されているので値は差し替えられません。

ここが「オラクル ≈ コミットメント」の実体です。PCP の「検証者が証明の一部だけ読む」を実現するには、 証明者が質問を見てから証明を書き換えられないことが必要。Merkle 根がそれを保証する。 ハッシュだけでできるので信頼設定が要らず（透明）、量子計算にも比較的強い。

Q₀ を偶数次と奇数次に分けると Q₀(X) = Q_even(X²) + X·Q_odd(X²)。 検証者がランダムな β を送り、証明者は Q₁(Y) = Q_even(Y) + β·Q_odd(Y) を作ってまたコミット。 次数が半分になるので、繰り返すと定数になります。

Q₀(X) = 5X² + 5X − 2 = (5X² − 2) + X·5      → Q_even(Y) = 5Y − 2,  Q_odd(Y) = 5
β₁ = 3:  Q₁(Y) = (5Y − 2) + 3·5 = 5Y + 13         次数 2 → 1
β₂ = 5:  Q₂    = 13 + 5·5 = 38 ≡ 4                次数 1 → 0（定数。これは平文で送る）

クエリ（検証者が x = 8 を選ぶ）:
  証明者が Q₀(8) = 1 と Q₀(−8) = Q₀(9) = 6 を Merkle 経路つきで開示
  検証者:  Q_even(8²) = (Q₀(8) + Q₀(9)) / 2  = 7·9  ≡ 12
           Q_odd(8²)  = (Q₀(8) − Q₀(9)) / (2·8) = −5·16 ≡ 5
           → Q₁(8²=13) は 12 + 3·5 = 27 ≡ 10 のはず。Q₁ の Merkle 開示 5·13 + 13 = 78 ≡ 10 と一致 ✓

x と −x の 2 点だけで偶奇部分が復元できるのがミソです（x² が同じだから）。 各ラウンドで数か所クエリすれば、「本当に半分の次数の多項式に折り畳まれているか」が Schwartz–Zippel の確率で確かめられる。検証者は Q₀ を丸ごと読まない。

            witness（秘密）      selector（公開: 回路の型）         wiring（公開: 配線）
            L    R    O          Q_L  Q_R  Q_M  Q_O  Q_C           σ_L      σ_R      σ_O
gate 0 (+)  3    1    4           1    1    0   −1    0            ω⁰k₀     ω⁰k₁     ω⁰k₂ →(L,gate2)
gate 1 (×)  2    4    8           0    0    1   −1    0            ω¹k₀     ω¹k₁     ω¹k₂ →(R,gate2)
gate 2 (+)  4    8   12           1    1    0   −1    0            ω²k₀→(O,gate0)  ω²k₁→(O,gate1)  ω²k₂

ゲート方程式（全行で 0 になるべき）:
  Q_L·L + Q_R·R + Q_M·L·R + Q_O·O + Q_C = 0
  gate 0:  3 + 1 + 0 − 4 + 0 = 0 ✓     gate 1:  0 + 0 + 8 − 8 + 0 = 0 ✓     gate 2:  4 + 8 + 0 − 12 + 0 = 0 ✓

1 本の式で足し算も掛け算も表せるのがセレクターの役目です。(Q_L,Q_R,Q_M,Q_O) = (1,1,0,−1) なら L + R − O = 0 で足し算、(0,0,1,−1) なら L·R − O = 0 で掛け算。回路の形はセレクターに、値は witness に分かれる。 11 本のベクトルはそれぞれ、行番号 ω⁰, ω¹, ω² を通る一変数多項式にラグランジュ補間されます。

ゲート方程式は行の中しか見ません。gate 2 の L に 4 でなく 5 を書き、O を 13 にしても、 5 + 8 − 13 = 0 で gate 2 の式は通ってしまう。 行をまたぐ「同じ値であるべき場所」を縛るのがコピー制約です。

各マスに番地 ω^行 · k_列（k₀, k₁, k₂ は列を区別する定数）をつけ、 「同じ値であるべきマス」を巡回置換 σ で入れ替えます。すると 「マスの (値, 番地) の集まり」と「(値, σ(番地)) の集まり」が、集合として同じことが配線の正しさそのもの。

集合の一致を 1 個の数で確かめる（大積 / grand product）:
  検証者がランダムな β, γ を選ぶ
  Π_マス (値 + β·番地 + γ)  と  Π_マス (値 + β·σ(番地) + γ)  が等しいか

F₁₀₁、ω = 10、k = (1,2,3)、β = 5、γ = 7 で計算すると（行ごとの積 f_i / g_i と累積）:
  gate 0:  f = 51,  g = 4    累積 51/4          = 38
  gate 1:  f = 87,  g = 21   累積 38·87/21      = 42
  gate 2:  f = 19,  g = 91   累積 42·19/91      = 1   ← 一周して 1 に戻る = 集合が一致

累算器 p(X) は「p(ω⁰) = 1、p(ω^{i+1}) = p(ω^i)·f_i/g_i」という行ごとの漸化式で、 最後に 1 に戻ることを p(ωX)·g(X) − p(X)·f(X) = 0（H の全点で）というゼロテストにして、 STARK と同じく Z_H で割った商を作ります。「H の全点で 0 ⇔ Z_H で割り切れる」は、ここでも同じ道具です。

Setup（信頼設定）:  秘密の τ を選び、SRS = { τ·g₁, τ²·g₁, …, τᵈ·g₁, g₂, τ·g₂ } を公開して τ は捨てる
Commit:            Com_f = f(τ)·g₁    ← τ を知らなくても Σ cᵢ·(τⁱ·g₁) で作れる（Week 3 の「スカラー倍」）
Open（α で開く）:   q(X) = (f(X) − f(α)) / (X − α)   ← f(α) が本当の値なら割り切れる（また因数定理）
                   Com_q = q(τ)·g₁
Verify:            f(τ) = (τ − α)·q(τ) + f(α) を、ペアリングで「指数の中の掛け算」として確認
                   e(Com_f − f(α)·g₁, g₂) = e(Com_q, τ·g₂ − α·g₂)

証明が短い理由: 多項式が何次でも、コミットメントは楕円曲線の点 1 個（数十バイト）。 信頼設定が要る理由: τ を誰かが覚えていれば偽のコミットメントが作れる。だから MPC 儀式で「誰も τ を知らない」状態にする。 Week 3 ノート後半の「f(X) = X² + 1 について f(2) = 5 を開く」が、この Open の最小例です。

インプット制約:  公開入力に対応するマスの値を KZG の開示証明で見せる
ゲート制約:      f(X) = Q_L(X)L(X) + Q_R(X)R(X) + Q_M(X)L(X)R(X) + Q_O(X)O(X) + Q_C(X)  が H で 0
                 → Q(X) = f(X) / Z_H(X) の存在を、ランダム点での開示で確かめる
コピー制約:      累算器 p(X) について p(ωX)g(X) − p(X)f(X) が H で 0（p(ω⁰) = 1 も）
                 → 同じくゼロテスト → 商多項式 → ランダム点での開示

検証者の仕事は最終的に「数個のランダム点で、数個の多項式の値が等式を満たすか」だけになり、 ペアリングの計算が数回で済む。証明サイズも検証時間も回路の大きさによらない（O(1)）。 そのぶん証明者は 11 本の多項式を作って FFT と MSM を回すので重い。ここがトレードオフです。

f̃(X) := f(X) + Z_H(X)·R(X)        R(X) は証明者が毎回選ぶランダム多項式

例（F₁₇、f = Y(X) = 3 + 12X + 14X² + 5X³、R(X) = 6 + 2X）:
  f̃(X) = 14 + 10X + 14X² + 5X³ + 6X⁴ + 2X⁵
  H の上:   X=1: (0, 0)  X=4: (0, 0)  X=16: (0, 0)  X=13: (12, 12)   ← (f, f̃) 一致。Z_H が 0 だから
  H の外:   X=2: (4, 1)  X=3: (11, 2)  X=5: (1, 6)                    ← 別の値。R によって毎回変わる

検証者が値を聞くのは H の外のランダムな点でした（Schwartz–Zippel のため）。 そこでは f̃ の値は R で覆われていて、f の情報を含まない。 そして制約の検査は H の上でしか見ていないので、f を f̃ に差し替えても「H の全点で 0」は保たれる。 Week 3 の s = r + e·x で x を r が覆っていたのと同じ構図で、 覆う量が数 1 個から多項式 1 本に増えただけです。

STARK: 遷移多項式と制約多項式。FRI で開示する回数ぶんのランダムネスが要り、 Merkle の葉にもソルトを混ぜる（葉のハッシュから値を総当たりされないため）。 PLONK: witness 多項式、配線（累算器）多項式、各商多項式。

講義の Q「なぜセレクター多項式はブラインド化しないのか」。セレクターは回路の型で、 もともと公開情報だから隠す理由がない。それどころかブラインドすると次数が上がって証明者のコストだけ増える。 隠すべきは witness とそれから派生する多項式だけ。「何が秘密で何が公開か」を 11 本のベクトルの段階で 分けておいたことが、ここで効きます。

GKR は SumCheck の途中で p₁(x), p₂(y) を平文で送るので、そのままでは W̃ の情報が漏れます。 そこで (1) 回路の値の多項式をコミットし、(2) マスク用の多変数多項式 R をコミットし、 (3) f + R に対して SumCheck を回し、(4) 終盤に V_original = V_total − V_random と引き算で相殺し、 (5) 多項式評価はコミットメントの開示証明（Merkle + FRI など）で代える。

講義の Q「どちらか片方だけではなぜダメか」。マスキングだけだと、 証明者が R をあとから都合よく選び直せる（相殺の式で辻褄を合わせられる）ので、R は先にコミットして固定する必要がある。 コミットメントだけだと、SumCheck で送る一変数多項式そのものが W̃ の情報を持ったまま。 「隠す」（マスク）と「固定する」（コミット）は別の仕事で、両方が要ります。