3/65zkSNARK で実現したいこと
秘密を手元に置いたまま、「条件を満たすものを知っている」という主張だけを相手に納得させたい。
示す側が prover（証明者）、確かめる側が verifier（検証者）。パスワードを伏せたまま「知っている」を示す、取引の中身を伏せたまま「ルールどおり」を示す。
Q. 「知っている」を渡すのに、中身を渡さずに済む例を 1 つ挙げられるか。
Advanced Cryptography Program 2026 / Week 3 自習ノート
このノートは講義スライド「zkSNARK part 1」65 枚と同じ順番で進みます。
1 カード = スライド 1〜2 枚 = 主張 1 つ。宿題 schnorr-from-scratch の 10 個の関数が
スライドのどこに当たるかを、毎回「宿題ではここ」で示します。
講義が飛ばしている 2 歩 — ゼロ知識証明を自分で組み立てる手順（隠す手は 2 つ）と、 制約を多項式にして短い証明にする 1 歩（F₁₇ の数値で最後まで） — を専用のカード群にしました。 宿題は地図の右半分（コミット → 短い証明）だけです。
出発点
1 枚のカードがスライド 1〜2 枚に対応し、主張は 1 つ、式か例は 1 個です。
宿題 schnorr-from-scratch の関数がスライドのどこに当たるかを、
「宿題ではここ」のタグで毎回示します。講義が飛ばしている 2 歩
（ゼロ知識証明を自分で組み立てる手順と、
制約を多項式にして短い証明にする 1 歩）は、専用のカード群として間に挟みました。
読み方
上から順に、1 カードずつ。カード末尾の Q. に自分の言葉で答えられたら次へ。答えは次のカードか、宿題タグの中にあります。章の終わりの「やってみる」は紙と鉛筆で解いてから答えを開いてください。数はすべて 1 桁〜2 桁です。
スライドを横に開いて、同じ番号を見比べながら読むのがいちばん速いです。
宿題は、この地図の右半分だけ
Schnorr は「主張」が P = x·G という 1 本の式なので、計算 → 制約 → 多項式 の左半分が要りません。
宿題で書くのは コミット（R = r·G）→ 短い証明（s） の右半分。左半分は Week 4 の 3 スキームが本番です。
この頁の構成
スライド 3〜11 / 導入
秘密を手元に置いたまま、「条件を満たすものを知っている」という主張だけを相手に納得させたい。
示す側が prover（証明者）、確かめる側が verifier（検証者）。パスワードを伏せたまま「知っている」を示す、取引の中身を伏せたまま「ルールどおり」を示す。
Q. 「知っている」を渡すのに、中身を渡さずに済む例を 1 つ挙げられるか。
大きな紙で絵全体を覆い、ウォーリーだけが見える穴を開けて渡す。
verifier が受け取るのは「確かにいる」という事実だけ。どこにいたかは prover の手元に残る。
隠す手 ①: 聞かれた分だけ見せる（穴）。これが後で「開示」になる。
「出す → 隠す → 答える」の 3 手を 1 回とし、何度も繰り返す。1 回なら偶然 1/2、10 回連続なら 1/1024。
宿題ではここ: 3 手 = sigma_commit（出す）→ 検証者の e（隠す・選ぶ）→ sigma_response（答える）。「偶然で通る確率」が健全性の話。
Q. 3 手のうち、verifier が選ぶのはどれか。
statement（公開の主張）・witness（秘密）・proof（証拠）。枠をまたぐのは proof だけ。
ウォーリー ソムリエ 宿題（Schnorr） statement 群衆の中にいる 2 つを区別できる P = x·G となる x がある witness 位置 見分け方のコツ x（秘密鍵） proof 穴から見える姿 正答の列 (R, s)
宿題ではここ: 検証者に渡るのは statement と proof だけ。schnorr_verify(P, message, (R, s)) の引数がまさにそれで、x は引数に無い。
主張は「∃w : R(y, w) = 1」の形にそろう。R は y と候補 w を受け取り合否を返す関数。
y = 15, R(y, w) = 1 ⇔ w³ + w + 5 = y w = 2 なら 8 + 2 + 5 = 15 → 1
宿題ではここ: R(P, x) = 1 ⇔ x·G = P。証明したいのは「この R を 1 にする x を知っている」。
Q. 数独なら R は何か。（盤面 y と解 w を受け取り、行・列・箱の規則を全部満たせば 1）
zk（漏れない）・S（短い・速い）・N（1 通で完結）・ARK（有効な proof を作れるなら witness を知っている + 正しければ通る）。
宿題ではここ: 宿題の Schnorr は zk と ARK を持ち、Fiat–Shamir で N になる。S（多項式・commitment で短くする）は宿題に無い。だから左半分が要らない。
矢印は 1 本ずつ、「前の箱のままでは困ることが 1 つある」から引かれている。
計算 → 制約 プログラムのままでは数学で真偽を確かめられない → 「= 0 の式の束」にする 制約 → 多項式 式が 1 万本あると全部読む手間 → 1 本の多項式なら「ランダムな 1 点」で確かめられる 多項式 → 封筒 1 点だけ聞くには、証明者が後出しで書き換えられないこと → 先に封筒（commitment） 封筒 → 短い証明 封筒 1 個 + 開示数か所 + 答え合わせ。質問をハッシュに選ばせれば会話も不要
Q. 逆順にできない理由を 1 本ずつ言えるか（式にする前に多項式にはできない、封筒の前に 1 点で聞くと後出しされる）。
スライド 12〜14 / 数の準備
整数を 7 で割った余りだけを見る。7 以上になったら余りへ戻す。計算は 7 個の点を巡る輪の上の移動。
5 + 6 = 11 ≡ 4, 3 · 5 = 15 ≡ 1 (mod 7) 中 1 の「割り算の余り」、時計の 13 時 = 1 時
宿題ではここ: field_add(a,b,p) = (a+b) % p、field_mul = (a·b) % p。p = 1009。負の入力でも Python の % は 0..p−1 を返す。
Q. field_add(−3, 1, 7) は？（−2 の余りは 5）
法が素数 p のときに限り、0 以外のすべての値に「掛けて 1 になる相手（逆元）」がそろい、割り算まで自由にできる。この世界 F_p を有限体と呼ぶ。
合成数だと 2 · 3 = 6 ≡ 0 (mod 6) のように、0 でないのに掛けて 0 になる組が出て、割り算が壊れる。
宿題ではここ: 1009 も secp256k1 の p も素数。field_inv が「0 以外なら必ず答えがある」前提はここから。
a の逆元 a⁻¹ は「掛けると 1 になる値」。割り算は逆元を掛ける操作（小 6 の「割り算 = 逆数を掛ける」）。
F₇: a 1 2 3 4 5 6 例: 3x = 5 を解く → 3⁻¹ = 5、x = 5·5 = 25 ≡ 4。検算 3·4 = 12 ≡ 5 ✓
a⁻¹ 1 4 5 2 3 6
宿題ではここ: field_inv(a, p)。求め方は拡張ユークリッド（Appendix A4、下のカード）。field_inv(3, 11) = 4（3·4 = 12 ≡ 1）。
Q. 0 の逆元が無い理由は？（0 × 何 = 0、1 にならない → 宿題は ValueError）
中 1 の互除法（最大公約数を求める手順）を逆にたどると、a·x + p·y = 1 の x が見つかる。mod p では p·y が消えて a·x ≡ 1。この x が逆元。
F₁₃ で 5⁻¹: 13 = 2·5 + 3, 5 = 1·3 + 2, 3 = 1·2 + 1 ← 1 まで下りる 逆にたどる: 1 = 3 − 2 = 3 − (5 − 3) = 2·3 − 5 = 2·(13 − 2·5) − 5 = 2·13 − 5·5 → 5 · (−5) ≡ 1 (mod 13)。 −5 を 0..12 に直して 8。検算 5·8 = 40 ≡ 1 ✓
宿題ではここ: extended_gcd(a, p) は与えられていて (g, x, y) を返す。extended_gcd(5, 13) = (1, −5, 2)。x が負のことがあるので x % p を忘れない（忘れると採点器「0..p−1 に正規化して返してください」）。
やってみる — 紙と鉛筆で。答えは開くまで隠れる
5 + 6 = 11 = 7 + 4 → 4 3 · 5 = 15 = 14 + 1 → 1 −3 = −7 + 4 → 4 （宿題の field_add(−3, 1, 7) が 5 になるのも同じ理屈）
3·1=3, 3·2=6, 3·3=9≡2, 3·4=12≡5, 3·5=15≡1 ← 見つかった。3⁻¹ = 5 3x = 5 の両辺に 5 を掛けて x = 25 ≡ 4。検算 3·4 = 12 ≡ 5 ✓
4·3 = 12 = 11 + 1 → 4⁻¹ = 3
13 = 4·3 + 1 ← 1 回で余りが 1 逆にたどる: 1 = 13 − 4·3 → 3·(−4) ≡ 1 (mod 13) → −4 を 0..12 に直して 9 検算 3·9 = 27 = 26 + 1 ✓ （宿題: extended_gcd(3, 13) は (1, −4, 1)。x % p を忘れると −4 のまま）
2 · x はいつも偶数。6 で割った余りは 0, 2, 4 のどれかで、1 にはならない → 法が合成数だと逆元を持てない数が出る。だから法は素数（宿題の p = 1009 は素数）
スライド 15〜20 / 多項式の準備
等式を 1 本ずつ確認すると、本数だけ手間が増える。列を 1 本の多項式で表せば、ランダムに選んだ 1 点の値を比べるだけで全体をまとめて確かめられる。
これが「制約 → 多項式」の矢印の理由。講義はここで理由だけ言って、実際の変換は見せない。変換の 1 歩は下の 「制約 → 多項式 → 短い証明」で数値ごと追う。
宿題には出ない（Schnorr は式が 1 本）。Week 4 で本番。
f(X) = 3X² + 2X + 5 は「係数 (5, 2, 3)」でも「点での値 (f(x₀), f(x₁), f(x₂))」でも表せる。次数 d は d + 1 点で一意に決まる。
Q. 2 点で決まるのは何次式か。（1 次 — 中 2 の一次関数）
f(1) = 3, f(2) = 5 なら、傾き (5−3)/(2−1) = 2、切片 1、f(X) = 2X + 1。点が増えても同じ（Lagrange 補間、Appendix）。
宿題ではここ: この「2 点の傾き」の計算が、そのまま ec_add の λ = (y₂−y₁)/(x₂−x₁)。分母の割り算が field_inv。
多項式を係数で持つと、掛け算は n 項 × n 項 = n² 回。「点での値」で持てば点ごとに 1 回で n 回。だから係数 ↔ 値を速く行き来したい。その翻訳機がフーリエ変換。
f = 1 + X, g = 1 + X: 係数で掛ける → 1 + 2X + X²（全部の組を掛けて足す）
値で掛ける → f(2)·g(2) = 3·3 = 9 のように点ごとに 1 回
「時間ごとの音圧の列」⇔「ド・ミ・ソがそれぞれどれだけ」。同じ音の 2 通りの表し方で、情報は増えも減りもしない。「値」⇔「係数」と同じ形。
yⱼ = f(ωʲ) = Σ aᵢ ω^{ij} 普通の版: ω = 単位円を n 等分して回る複素数
有限体版: ω = ωⁿ = 1 になる F_p の元（輪を n 等分する点）
逆: aᵢ = (1/n) Σ yⱼ ω^{−ij} 1/n は F_p の中の n の逆元
「点 ωʲ での値を全部並べる」= 評価表現。ω を取り替えるだけで、式は 1 文字も変わらない。
2⁴ = 16 ≡ 1、冪 1, 2, 4, 3 が全部違う → ω = 2 は位数 4 の 1 の根 f = 1 + X → 係数 (1, 1, 0, 0) 値: f(1)=2, f(2)=3, f(4)=0, f(3)=4 → y = (2, 3, 0, 4) 逆: 1/n = 4（4·4 ≡ 1）, ω⁻¹ = 3 a₀ = 4·(2+3+0+4) = 36 ≡ 1 ✓ a₁ = 4·(2·1 + 3·3 + 0·4 + 4·2) = 4·19 ≡ 1 ✓ 値で掛け算: g = 1 + X も値 (2,3,0,4)。点ごとに掛けて (4,4,0,1)。逆変換 → (1,2,1,0) = 1 + 2X + X² ✓
評価点が ω の冪だと ω^{n/2} = −1 で、点 x と −x が対になる。多項式を偶数次と奇数次に分けて半分ずつ処理でき、半分 → また半分 → … で n·log n。おまけに点集合 H の消滅多項式が Xⁿ − 1 という短い形になる。
Week 4 との接続: FRI の「Q_even(X²) + X·Q_odd(X²)」の分解が FFT の 1 段そのもの。STARK の Z_H = X⁴ − 1 もここから。宿題には出ない。
Q. なぜやるのか、を 1 行で。（証明者は表＝値を持ち、検証は多項式＝係数と割り算でやる。その 2 つを 100 万点でも一瞬で行き来するため）
スライド 21〜30 / 楕円曲線・離散対数
閉じている・単位元・逆元・結合法則、の 4 つで群。1 つの元 g を掛け続けて全体を巡れるなら巡回群、巡って戻るまでの回数が位数。
F₇* は g = 3 で巡る: 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 3 の位数は 6
宿題ではここ: G の位数 n = 967。G を n 回足すと単位元 O に戻る（採点器 test_order_times_generator_is_identity）。だからスカラーは mod n。
曲線 y² = x³ + ax + b の点どうしに「足し算」を定義すると群になる。x·P は P を x 回足す。x·P から x を逆算するのが難しい。無限遠点 O が足し算の 0 の役。
宿題ではここ: トイ曲線 y² = x³ + 11 over F₁₀₀₉、G = (1, 298)、O は None。ec_add が足し算、ec_scalar_mul が x·P。
Q. 「点を足す」は座標を足すことか。（違う。次の 2 枚）
P, Q を通る直線が曲線と 3 つ目に交わる点 R′ を、x 軸で反転した R を P + Q と定める。直線の傾きは λ = (y₂ − y₁)/(x₂ − x₁)。図は実数の直感、暗号では同じ式を mod p で計算する。
宿題ではここ: ec_add の「弦」の場合。λ の分母は field_inv(x_Q − x_P)。
x₃ = λ² − x₁ − x₂（3 次方程式の根と係数の関係: 3 解の和 = λ²）、y₃ = λ(x₁ − x₃) − y₁（直線上の点を反転）。P = Q なら接線 λ = (3x₁² + a)/(2y₁)。y₁ = 0 なら垂直で 2P = O。
宿題ではここ: ec_add の 4 場合分け — (1) どちらかが None → 相手を返す、(2) x が同じで y が符号違い → None、(3) P == Q → 接線 λ、(4) それ以外 → 弦 λ。(2) を (3)(4) より先に（分母 0 を避ける）。y₃ の符号を反転し忘れると点が曲線から落ちる。
講義: y² = x³ + x + 6 (F₁₁, a = 1), P = (2, 7)
λ = (3·4 + 1)/(14) = 13·14⁻¹ ≡ 2·3⁻¹ ≡ 2·4 = 8 x₃ = 64 − 4 = 60 ≡ 5, y₃ = 8·(2−5) − 7 = −31 ≡ 2 → 2P = (5, 2)
宿題: y² = x³ + 11 (F₁₀₀₉, a = 0), G = (1, 298)
λ = 3·1²/(2·298) = 3/596 = 3·601 ≡ 794 x₃ = 794² − 2 ≡ 818, y₃ = 794·(1−818) − 298 ≡ 800 → 2G = (818, 800)
宿題ではここ: 採点器の test_doubling は 2G = (818, 800)、続けて G + 2G = 3G = (851, 516)。
Q. 講義の λ で「14⁻¹ ≡ 3⁻¹」と約分しているのはなぜか。（14 ≡ 3 mod 11）
13 = (1101)₂ = 8 + 4 + 1。P → 2P → 4P → 8P と倍にして、13P = 8P + 4P + P。5 回で届く（定義どおりなら 12 回）。回数は log₂ x に比例。
宿題: 123 = (1111011)₂ → 123·G は 2 倍 6 回 + 足し算 6 回 = 12 回（素直にやると 122 回）
結果 (376, 128) が公開鍵 P。 secp256k1 の 2²⁵⁶ 回は素直にやると終わらない
宿題ではここ: ec_scalar_mul。k, bit = divmod(k, 2) で下の桁から読み、bit が 1 なら足し、毎回 addend を 2 倍。k = 0 なら None。
x → x·P は速い（倍々法）。P と x·P から x を求めるのは難しい。ハッシュと同じ見方（m → H(m) は速く、逆は難しい）。
宿題ではここ: 公開鍵 P = x·G を公開しても x が漏れない理由。R = r·G を公開しても r が漏れない理由。Week 3 の安全性はここに全部乗っている。
やってみる — 紙と鉛筆で。答えは開くまで隠れる
左辺 y² = 49 = 44 + 5 → 5 右辺 x³ + x + 6 = 8 + 2 + 6 = 16 → 5 一致 → 曲線上
λ = (2 − 7)/(5 − 2) = (−5)/3 = 6 · 3⁻¹ = 6 · 4 = 24 ≡ 2 （−5 ≡ 6、3⁻¹ = 4） x₃ = λ² − x₁ − x₂ = 4 − 2 − 5 = −3 ≡ 8 y₃ = λ(x₁ − x₃) − y₁ = 2·(2 − 8) − 7 = −19 ≡ 3 → 3P = (8, 3)。検算: 9 と 512 + 8 + 6 = 526 ≡ 9 ✓（曲線上）
13 = 8 + 4 + 1 = (1101)₂ P → 2P → 4P → 8P で 2 倍算 3 回、8P + 4P + P で足し算 2 回。合計 5 回（素直にやると 12 回）
無限遠点 O。接線の傾き λ = (3x² + a)/(2y) の分母 2y が 0 で割れない = 接線が垂直で 3 つ目の交点が無い （宿題の ec_add では「x が同じで y が符号違い」の場合分けがこれを拾う。y = 0 なら −y = y なので同じ点で成立）
G の位数。G を 967 回足すと単位元に戻る。だから s = r + e·x は mod 967（G を何回足すかの数だから）
スライド 31〜34 / ペアリング
aP と bP から足し算で作れるのは (a+b)P まで。積 abP はその先。ペアリング e は e(aP, bQ) = e(P, Q)^{ab} と、スカラーを指数へ移せる（双線形性）。分かるのは積が一致するかどうかだけで、離散対数の難しさは残る。
宿題には出ない。KZG の検証式（次の節）で「指数の等式をペアリングで確かめる」ために使う。
aP, bQ, cP を受け取った verifier: e(aP, bQ) = e(cP, Q) ⇔ ab ≡ c (mod q) 手に取るのは点だけ。a, b, c は隠れたまま
スライド 35〜42 / Commitment
値 m を短い c に固定して先に渡し、後で中身を見せて開ける。封をした封筒。開けられるのは最初に入れた m だけ（binding）、開けるまで verifier が持つのは c だけ（hiding）。
宿題ではここ: sigma_commit の R = r·G が封筒。hiding は「R から r が出ない」（離散対数）、binding は「同じ R に別の r を後から当てられない」（r·G は一意）。
Q. 封筒を先に渡す理由は？（後出しの防止 — 次の節の simulator が答え）
c = Hash(m)。m の候補が少ないと総当たりで割れるので、十分長い乱数 r を混ぜて c = Hash(r, m)。
隠す手 ②: 乱数で覆う。宿題の s = r + e·x で x を r が覆っているのと同じ役。
秘密 τ を 1 つ選び SRS = (P, τP, τ²P, …, τᵈP; Q, τQ) を公開して τ は捨てる（MPC で作れる）。多項式 f のコミットは C = a₀P + a₁(τP) + … = f(τ)P。τ を知らずに作れ、次数によらず点 1 個。
宿題には出ない。「多項式を封筒に入れる」の実装。Week 4 の PLONK で本番。
f(z) = y なら f(X) − y は X = z で 0 → (X − z) で割り切れる → q(X) = (f(X) − y)/(X − z) proof π = q(τ)P。 verifier: e(C − yP, Q) = e(π, τQ − zQ) ← 「f(τ) − y = q(τ)(τ − z)」を指数で確かめている 例: f = X² + 1, z = 2, y = 5: q = (X² − 4)/(X − 2) = X + 2, π = τP + 2P。 割り切れるのは f(2) = 5 が本当のときだけ
覚える 1 点: 「割り切れる ⇔ 値が本当」。因数定理（数 II）。下の 制約 → 多項式 でも、Week 4 の STARK/PLONK でも同じ道具。
やってみる — 紙と鉛筆で。答えは開くまで隠れる
成り立たない。verifier は Hash(はい) と Hash(いいえ) を自分で計算して c と見比べれば中身が分かる → 十分長い乱数 r を混ぜて c = Hash(r, m) にする。候補が r の分だけ増えて総当たりできなくなる（隠す手 ①）
r → r·G は決まった計算なので、r を決めれば R は 1 つ。同じ R になる別の r′ を見つけるのは「R から r を求める」= 離散対数と同じ難しさ
s を先に適当に選び、R := s·G − e·P と置けば、x を知らなくても s·G = R + e·P が成り立つ（simulator の順番） → 誰でも通る = 健全性が消える。「先に封をする」順番が健全性の全部
スライド 43〜52 / Arithmetization
a + b = c は「c は結果」と読むが、a + b − c = 0 は「与えられた a, b, c が整合しているか」と読む。左辺が 0 になる形にそろえる。掛け算 ab − c = 0、AND なら加えて b(b − 1) = 0。
Week 1 の回路そのもの。方程式を移項して右辺を 0 にしただけ（中 1）。
w³ + w + 5 = y (y = 15) t₁ ← w·w → t₁ − w² = 0
t₂ ← t₁·w → t₂ − t₁w = 0
y ← t₂ + w + 5 → t₂ + w + 5 − y = 0
w = 2 なら t₁ = 4, t₂ = 8, y = 15。 3 本とも 0 なら、提出された w, t₁, t₂ は y と整合
覚える 1 点: 1 ステップ = 1 本の制約。中間値 t₁, t₂ も witness に入る。
1 本の制約に掛け算を 1 個だけ許す: (線形結合) × (線形結合) = (線形結合)。z = (1, y, w, t₁, t₂) に係数の行を並べて (Az) ∘ (Bz) = Cz。
行 1: (w) × (w) = (t₁) A の行 (0,0,1,0,0), B の行 (0,0,1,0,0), C の行 (0,0,0,1,0) 行 2: (t₁) × (w) = (t₂) 行 3: (t₂ + w + 5 − y) × (1) = 0 掛け算の無い制約は右因子を 1 にする
次のカード群でこの 3 行を多項式にする。ここまでが講義。ここから先が講義に無い 1 歩。
AIR は計算を「横に変数、縦に時間」の表（実行トレース）として見る。境界制約（どこから始まるか）と遷移制約（隣の行の関係）。行が増えても式は 1 組のまま。R1CS / AIR / Plonkish / CCS は同じ計算の並べ方違い。
Week 4 の STARK（AIR）と PLONK（Plonkish）がこの続き。
講義が飛ばした 1 歩 — スライド 16 と 47 のあいだ
「プロトコルをどうやって多項式に変換するのか」の答えです。上の R1CS の 3 行を、F₁₇ で最後まで運びます。 道具は 3 つだけ: 補間（3 点で 2 次式が決まる）、因数定理（全点で 0 ⇔ 割り切れる）、 ランダムな 1 点（違う多項式はほぼ違う値）。
witness z = (1, 15, 2, 4, 8) を各行の左因子・右因子・右辺に代入すると、行ごとに 3 つの数が出る。
行 i 左因子 aᵢ 右因子 bᵢ 右辺 cᵢ aᵢ·bᵢ − cᵢ 1 w = 2 w = 2 t₁ = 4 4 − 4 = 0 2 t₁ = 4 w = 2 t₂ = 8 8 − 8 = 0 3 t₂+w+5−y = 0 1 0 0 − 0 = 0 ← 全部 0 = 制約が全部成り立つ
「行番号 X = 1, 2, 3 で、その行の値になる 2 次式」を列ごとに作る（3 点 → 2 次式）。
a(X): (1,2),(2,4),(3,0) を通る → a(X) = 11 + 11X + 14X² 検算 a(1) = 36 ≡ 2 ✓ b(X): (1,2),(2,2),(3,1) を通る → b(X) = 1 + 10X + 8X² c(X): (1,4),(2,8),(3,0) を通る → c(X) = 5 + 5X + 11X² （すべて mod 17）
何をしたか: 3 行 × 3 列 = 9 個の数を、3 本の多項式に「圧縮」した。行が 1 万あっても、多項式は 3 本のまま（次数が上がるだけ）。
P(X) := a(X)·b(X) − c(X) = 6 + 14X + 14X² + 7X³ + 10X⁴ P(1) = P(2) = P(3) = 0 ← 3 本の制約が 1 本に
因数定理: X = 1, 2, 3 で 0 なら (X−1)(X−2)(X−3) で割り切れる。この積が Z_H(X) = X³ + 11X² + 11X + 11（mod 17、= X³ − 6X² + 11X − 6）。
P(X) = Z_H(X) · Q(X), Q(X) = 16 + 10X, 余り 0 ← 「制約が全部成り立つ」⇔「Q が多項式として存在する」
prover は a, b, c, Q を commitment（KZG なら点 4 個）にして渡す。verifier がランダムに z を選び、prover は 4 つの値と開示証明を返す。verifier は 1 本の等式だけ見る。
z = 5: a(5) = 8, b(5) = 13, c(5) = 16, Q(5) = ?, Z_H(5) は verifier が自分で計算
a(5)·b(5) − c(5) = 104 − 16 = 88 ≡ 3 Z_H(5)·Q(5) ≡ 3 一致 → 受理
z = 9: 1 = 1 ✓ z = 11: 8 = 8 ✓ （3 行読まずに、1 点で 3 行分を確かめた）
なぜ 1 点でよいか: 嘘の P′ ≠ Z_H·Q′ は、違う多項式なので次数個の点でしか一致しない。F₁₇ で次数 4 なら 17 点中せいぜい 4 点。実物は 2²⁵⁴ 点中せいぜい数百万点。先に封筒に入れたから z を見てから書き換えられない。
witness を w = 3 に変える（t₁, t₂ はそのまま）: 行の値 aᵢbᵢ − cᵢ = (5, 4, 1) ← 0 でない P′(X) = 10 + 13X + 10X² + 4X³ + 2X⁴, Z_H で割ると余り 4 + 2X + 16X² ← 割り切れない。Q が存在しない 無理に「商だけ」を送っても z = 5: 1 ≠ 12, z = 9: 9 ≠ 0, z = 11: 14 ≠ 7 → 17 点すべてで拒否
覚える 1 点: 健全性は「割り切れない → 商が無い → ランダムな点でずれる」の 3 段。
a(5) = 8 のような開示値は witness から作られた値なので、集めると漏れる。そこで ã(X) = a(X) + Z_H(X)·r（r は乱数）に差し替える。X = 1, 2, 3 では Z_H = 0 なので値は同じ、外ではランダム。
r = 6: ã(X) = 9 + 9X + 12X² + 6X³ ã(1), ã(2), ã(3) = 2, 4, 0（元と同じ） ã(5) = 16（元は 8。r で覆われた）
宿題との対応: s = r + e·x で x を r が覆うのと同じ構図。覆う量が「数 1 個」から「多項式 1 本」に増えただけ。隠す手 ②（乱数で覆う）の多項式版。
Q. なぜ Z_H を掛けた乱数を足すのか。（制約の検査は H の上でしか見ないから、H の上の値を変えなければ検査は壊れない）
STARK : 歩 2 の「行番号」を ω^t にし（FFT）、封筒は Merkle 木、歩 4 の「1 点」の代わりに FRI で次数を確かめる PLONK : 歩 2 を 11 本の多項式で、封筒は KZG、歩 3 のゼロテストに加えて配線の大積 GKR : 歩 2〜4 を SumCheck に置き換える（封筒なしでも対話なら成立） Schnorr: 制約が 1 本なので歩 1〜3 が不要。歩 4 の「封筒 → 乱数 → 開示」だけ = 宿題
やってみる — 紙と鉛筆で。答えは開くまで隠れる
t ← w · w → t − w·w = 0 y ← t + 3 → t + 3 − y = 0 w = 2 なら t = 4, y = 7。2 本とも代入して 0 になる
傾き (4 − 1)/(2 − 1) = 3、切片 1 − 3·1 = −2 ≡ 3 → f(X) = 3X + 3 検算 f(2) = 6 + 3 = 9 ≡ 4 ✓ （2 点で 1 次式が決まる = 中 2 の一次関数）
P(1) = 1 − 3 + 2 = 0、P(2) = 4 − 6 + 2 = 0 因数定理: (X − 1)(X − 2) = X² − 3X + 2 で割り切れる。商は 1（P = Z_H · 1） → 「2 点で 0」が「Z_H で割り切れる」に化けた
差も次数 ≤ 2 の多項式（0 でない）で、根は最大 2 個 → 一致するのは最大 2 点 F₁₇ で verifier がランダムに 1 点選ぶと、嘘の多項式が本物と同じ値を返す確率は 2/17 以下。体を大きくすればほぼ 0
スライド 53〜62 / 対話 ZK・FS（宿題の本体）
公開は g と y = g^x。prover は x を明かさずに、y が g^x の形で作られていることを納得させる。statement: ∃x : g^x = y、witness: x。
講義の記号（乗法） g y = g^x a = g^r b c = r + bx mod q 宿題の記号（加法） G P = x·G R = r·G e s = r + e·x mod n
宿題ではここ: 記号の対応表を手元に置く。g^x と x·G は同じ操作の書き方違い（スライド 30）。
prover（x を持つ） verifier（g, y を知る）
乱数 r を選び a := g^r を送る ── a ──▶
◀── b ── チャレンジ b をランダムに選ぶ
c := r + b·x を返す ── c ──▶ g^c = a·y^b を確認
完全性: y = g^x なら g^c = g^{r+bx} = g^r (g^x)^b = a·y^b
宿題ではここ: sigma_commit(r) = r·G、sigma_response(x, r, e) = (r + e·x) % n、sigma_verify(P, R, e, s): s·G == R + e·P。完全性の 1 行は分配法則（中 1）: (r + e·x)·G = r·G + e·(x·G)。
講義: F₂₃*, g = 2, q = 11, x = 7, y = 2⁷ = 128 ≡ 13. r = 3 → a = 8. b = 5. c = 3 + 35 = 38 ≡ 5 (mod 11)
g^c = 2⁵ = 32 ≡ 9, a·y^b = 8·13⁵ ≡ 8·4 = 32 ≡ 9 → 受理 指数は mod 11、群は mod 23
宿題: 曲線 F₁₀₀₉, n = 967, x = 123, P = 123·G = (376,128). r = 456 → R = (822,106). e = 77.
s = 456 + 77·123 = 9927 = 10·967 + 257 → 257 (mod 967)
s·G = 257·G = (595,110), R + e·P = (822,106) + 77·(376,128) = (595,110) → 受理 座標は mod 1009、s は mod 967
宿題ではここ: 採点器の test_response（257）と test_honest_transcript_accepts。mod を p = 1009 で取ると 846 になって落ちる — 「指数は mod q、群は mod p」の講義の注意そのもの。
「知っている」の定義: 検証に通る prover を巻き戻して、同じ a に別のチャレンジ b′ を投げ、2 つの応答から x を計算できるなら、x は prover の中にあった。
c = r + b·x, c′ = r + b′·x → 引くと r が消える → x = (c − c′)(b − b′)⁻¹ (mod q) 中 2 の連立方程式（未知数 2、式 2）
宿題ではここ: 採点器 test_nonce_reuse_leaks_secret はこの抽出器そのもの。r = 456, e₁ = 77, e₂ = 90 → s₁ = 257, s₂ = 889 → x = (257 − 889)·(77 − 90)⁻¹ = 335·595 mod 967 = 123。安全性の根拠（抽出できる）と攻撃（nonce 再利用）が同じ 1 本の式。
秘密 x を使う本物の記録と、公開情報だけから simulator が作る記録が見分けられないなら、漏れていない。Schnorr なら会話 (a, b, c) を x なしで作れればよい。順番を逆にする: b と c を先に選び、a := g^c · y^{−b} と置く。検証式は定義から成り立つ。
宿題ではここ: 下のラボ 1で simulator モードに切り替えると、x なしの会話が受理される。受理された 1 本は「知っている」証拠にならない。証拠になるのは「先に a を出してから b に答えた」順番だけ。
Q. なぜ本物では a を先に出さなければならないか。（後出しなら simulator と同じ手で誰でも通る）
verifier が選んでいた b を、会話ログの hash b := H(ctx, g, y, a) にする。a は公開なので verifier も同じ b を計算できる。返事を待たずに proof が 1 通で作れる。
宿題ではここ: challenge_hash(R, P, message, n)。引数の順番 (R, P, message) を入れ替えると、自分の verify では通るのに採点器の固定ベクトルだけ落ちる（他人と互換性がない）。
prover: r → a = g^r → b = H(ctx, g, y, a) → c = r + bx → π = (a, c) verifier: b を再計算して g^c = a·y^b
hash にメッセージ m も入れれば π は m への署名。x が秘密鍵、y が公開鍵。BIP-340 / Ed25519 がこの系統
宿題: schnorr_sign(x=123, "week3", nonce=456): R = (822,106), P = (376,128), e = H(R,P,"week3") = 57, s = 456 + 57·123 = 7467 ≡ 698
schnorr_verify(P, "week3", (R, 698)): e を計算し直して 57 → 698·G == R + 57·P → True
メッセージを "week3!" に改ざん → e′ = 723 → False
宿題ではここ: schnorr_sign = sigma_commit → challenge_hash → sigma_response。schnorr_verify = challenge_hash を計算し直して sigma_verify。e を署名に含めて送らない（送ると証明者が e を選べて simulator の順番になる）。
zkSNARK は、公開 statement に対して秘密 witness が存在することを、計算を制約と多項式へ翻訳し、commitment で短く固定して、短い proof として検証する仕組み。
計算 → 制約: R1CS。制約 → 多項式: 補間（上の 6 歩）。多項式 → commitment: KZG。対話 → 短い proof: Fiat–Shamir。宿題は最後の 1 本の矢印の最小形。
やってみる — 紙と鉛筆で。答えは開くまで隠れる
c = r + b·x = 4 + 21 = 25 ≡ 3 (mod 11) ← 指数は mod q = 11 左辺 g^c = 2³ = 8 右辺 a = g^r = 2⁴ = 16、y^b = 13³ = 13·169 ≡ 13·8 = 104 ≡ 12、a·y^b = 16·12 = 192 ≡ 8 ← 群は mod p = 23 一致 → 受理
c′ = 4 + 42 = 46 ≡ 2 (mod 11) x = (c − c′)/(b − b′) = (3 − 2)/(3 − 6) = 1/(−3) = 1/8 (mod 11)。8⁻¹ = 7（56 = 55 + 1）→ x = 7 ✓ → 同じ r で 2 回答えた瞬間、秘密が出る（宿題の nonce 再利用テスト）
a := g^c · y^{−b} = 2⁹ · 13⁻⁵。2⁹ = 512 ≡ 6、13⁵ ≡ 4、4⁻¹ ≡ 6（24 ≡ 1）→ a = 6·6 = 36 ≡ 13
検証: g^c = 6、a·y^b = 13·4 = 52 ≡ 6 → 成り立つ。x = 7 を一度も使っていない
→ 受理された会話 1 本は「知っている」証拠にならないs = 456 + 90·123 = 11526 = 11·967 + 889 → 889 (mod 967) （採点器 test_nonce_reuse_leaks_secret の s₂。s₁ = 257 と合わせて x = 123 が復元される）
講義が飛ばしたもう 1 歩 — 数独のカードから一般へ
ホワイトボードで数独はできた。一般の主張でも同じ 5 手順です。隠したい情報を守る手は 2 つだけで、 3 つの性質（完全性・健全性・ゼロ知識）はそれぞれ「1 つの問い」で確かめられます。
完成した手順ではなく、手順に至るまでに何を問うか。数独で実際にやったはずのことを、問いの列にほどく。
問 0 何を、誰に、何は見せてよくて、何は見せたくない？ → 盤面（公開）／解（秘密）／検査 R = 行・列・箱。この 3 行を書く
問 1 素朴案 A: 解を全部見せる。何が困る？ → 完全性 ○ 健全性 ○ だが秘密が丸見え（ZK ✗）
問 2 素朴案 B: 何も見せず「解けた」と言う。何が困る？ → ZK ○ だが嘘つきも同じ台詞が言える（健全性 ✗）
→ ZK 証明の設計 = A と B の間で「見せる量を最小に、嘘なら見つかる」点を探すこと
問 3 一部だけ見せるなら、どの一部で嘘が見つかる？
→ R は 1 個の大きな条件ではなく、小さな検査の集まり（行 4 + 列 4 + 箱 4 = 12 個）。
1 個の検査「その 4 マスに 1〜4 が 1 回ずつ」は、その 4 マスさえ見れば verifier が自分でできる
→ 検査 1 個ぶんだけ開ければよい。「R を、少ない情報で確かめられる小さな検査に分解できるか」が最初の分かれ道
問 4 開ける場所を prover が選んだら？ → 嘘つきは正しい所だけ見せる → 場所は verifier が乱数で選ぶ（challenge）
鉄則: 「どこを見るか」を prover に決めさせない
問 5 verifier が選んで開けると、その 4 マスの秘密が漏れる。減らせないか？
→ 自問: この検査に本当に必要な情報は何か？ 「4 つが全部違う」だけ。数字そのものは要らない
→ 1〜4 を毎回ランダムに別の記号に置き換えてから見せる。「全部違う」は確かめられるのに元の数字は分からない
= 隠す手 ①「乱数で覆う」
Schnorr でも同じ問い: 検査 s·G = R + e·P に必要なのは s だけで、x の値は要らない
→ x を r で覆って s = r + e·x だけ渡す。s = r + e·x の「形」はこの問いから出る
問 6 置き換えたカードを、聞かれてから作ったら？ → 聞かれた場所だけ辻褄を合わせられる
→ 開ける前に全部を伏せて置く（commit）。伏せたら変えられない（binding）。順番は「伏せる → verifier が選ぶ → その分だけめくる」
= 隠す手 ②「聞かれた分だけ開ける」が成立する条件
①と②は両方要る。①だけ（全部めくる）→ 置き換え表ごと割れる。②だけ（生の数字を一部めくる）→ 秘密がそのまま出る
問 7 1 回で嘘つきが通る確率は？ → 12 か所中 1 か所しか見ない。1 か所だけ間違った嘘は 11/12 で通る
→ 置き換えを毎回変えて繰り返す。20 回で (11/12)²⁰ ≈ 17%、50 回で ≈ 1.3%
Schnorr は e の候補が 967 通り（実物 2²⁵⁶）なので 1 回で十分。「1 回でどれだけ潰せるか」= challenge の候補数
完全性 本当の解を持つ人は、どの場所を聞かれても通るか → 4 つは必ず違う ○
健全性 同じ伏せカードのまま 12 か所全部に答えられる人から、解を取り出せるか
→ 全部通る = 置き換えを戻せば本物の解。「通り続ける人は解を持つ」（抽出器）
ゼロ知識 見せる場所が先に分かっていれば、解なしで同じ見た目が作れるか
→ その 4 マスに違う 4 色を置いたカードを用意すればよい（simulator）。作れる = 漏れていない
→ 健全性もゼロ知識も「順番」の話。本物は「伏せる → 選ぶ」、simulator は「選ぶ → 作る」。この順番を verifier の乱数（対話）かハッシュ（Fiat–Shamir）が強制する
手元に置く 1 行: R を小さな検査に分ける → 1 検査に必要な最小情報を見つける → それ以外を乱数で潰す → 先に伏せる → verifier に選ばせる → 繰り返す。
「20 歳以上」で止まる場所は問 3: 大小比較は「一部を開けて確かめられる小さな検査」に分解できない（何を開けても生年月日そのもの）。ここで初めて左半分（計算 → 制約 → 多項式）が要る。
数独: x = 問題の盤面, w = 解, R = 「行・列・箱に 1〜4 が 1 回ずつ」を全部満たすか Schnorr: x = (G, P), w = 秘密鍵 x, R = 「x·G = P か」 3 彩色: x = グラフ, w = 塗り分け, R = 「隣どうしが違う色か」
R が書けない主張は証明できない。まず「何が公開で、何が秘密で、何を確かめれば真か」を 3 行で書く。
秘密そのものは見せない。乱数を混ぜた「封筒」だけを先に出す。封筒は後から中身を変えられない（binding）ことが必要。
数独: 解の数字を色や記号にランダムに置き換えて、カードを伏せて並べる（毎回置き換えを変える） Schnorr: r をランダムに選び R = r·G を出す（r も x も出さない） 3 彩色: 3 色の名前をランダムに入れ替えてから、各頂点の色を封筒に入れる
verifier が「どこを見るか」をランダムに 1 つ選ぶ。prover はその分だけ開ける。全部は開けない。
数独: 「3 行目を見せて」→ その行のカードだけめくる → 1〜4 が 1 回ずつあるか Schnorr: 「e = 77 で答えて」→ s = r + e·x だけ返す（r と x は個別には出ない） 3 彩色: 「この辺の両端を見せて」→ 2 つの封筒だけ開ける → 色が違うか
ここで秘密が守られる理由: 開けた分は乱数で覆われている（① の置き換え・r）ので、そこから元の秘密は復元できない。①と②を両方やって初めて守れる。①だけなら全部開けたときに置き換え表ごと割れるし、②だけなら開けた場所の秘密がそのまま見える。
1 回の open で嘘が見つかる確率は「開けた場所の割合」程度。3 手を繰り返して確率を潰す。Schnorr は e の候補が n = 967（実物は 2²⁵⁶）通りあるので 1 回で十分。数独は行・列・箱の 12 か所から 1 つなので何十回も。
完全性 「本当の w を持つ正直な prover は、どのチャレンジでも通るか」
→ 検証式に代入して等号が成り立つことを 1 回計算する（Schnorr: s·G = (r+e·x)·G = R + e·P）
健全性 「同じ封筒のまま、2 つの違うチャレンジに答えられる prover から、w を取り出せるか」（抽出器）
→ 取り出せるなら、通る prover は w を持っていた（Schnorr: x = (s₁−s₂)/(e₁−e₂)）
→ 数独なら: 全部の行・列・箱に答えられる = 置き換え表を戻せば本物の解が出る
ゼロ知識 「w を使わずに、verifier に同じに見える記録を作れるか」（simulator）
→ チャレンジを先に決めて封筒を後から作る手が使えれば、漏れていない（Schnorr: R := s·G − e·P）
→ 数独なら: 見せる行が分かっていれば、その行だけ 1〜4 を並べたカードを用意できる
覚える 1 点: 健全性の問いも、ゼロ知識の問いも「順番」の話。本物は封筒が先・チャレンジが後。simulator はチャレンジが先・封筒が後。この順番を守らせるのが verifier の乱数（対話）か hash（Fiat–Shamir）。
手順 1: x = 公開の何か（発行者の署名つき生年月日のコミットメント）, w = 生年月日, R = 「今日 − 生年月日 ≥ 20 年」
手順 2: 生年月日を乱数で覆った封筒（発行者が署名）
手順 3: verifier の質問に「20 歳以上か」の 1 bit 分だけ答える方法が要る → ここが難しい。数字の大小は「開ける」だけでは示せない
→ だから 計算（比較）→ 制約 → 多項式 の左半分が要る。Week 1〜4 はその道具作り
この「開けるだけでは示せない主張」に出会ったとき、左半分（算術化）が必要になる。数独と Schnorr は「開けるだけで示せる」特別に易しい主張。
やってみる — 紙と鉛筆で。答えは開くまで隠れる
検査は行 4 + 列 4 + 箱 4 = 12 か所。間違いのある 1 か所を引かない確率 11/12 30 回連続で見逃す確率 (11/12)³⁰ ≈ 7.4%、50 回で ≈ 1.3%
先に e を当てて simulator の順で作れば通るので 1/2。10 回で (1/2)¹⁰ = 1/1024 宿題の e は 967 通り、実物は 2²⁵⁶ 通りなので 1 回で十分（ソムリエの例と同じ計算）
「2 つの色が違う」ことだけ。色の名前は要らない → 毎回 3 色の名前をランダムに入れ替えてから封筒に入れ、聞かれた辺の両端だけ開ける（問 5 と同じ問い）
大小比較は、生年月日のどの一部を開けても確かめられない（開けたら生年月日そのもの） → 「小さな検査に分解」ができない。だから比較を = 0 の式に翻訳する左半分（算術化 → 多項式）が要る
宿題の 10 関数
| 関数 | スライド | 学校で習ったこと | 採点器の数値 | 落ちやすい所 |
|---|---|---|---|---|
| field_add / field_mul | 13 | 割り算の余り（中 1） | (3+4)%7 = 0、(3·4)%7 = 5 | 負の入力（% で済む） |
| field_inv | 14, A4 | 逆数を掛ける（小 6）、互除法（中 1） | 3⁻¹ mod 11 = 4 | x % p 忘れ、0 の ValueError |
| ec_add | 25〜27 | 2 点の傾き（中 2）、接線＝微分（数 II）、解と係数（数 II） | 2G = (818,800)、3G = (851,516) | y₃ の符号、垂直の場合分けの順番 |
| ec_scalar_mul | 28 | 2 進法（数 A） | 123·G = (376,128)、967·G = None | 素直に k 回足すと終わらない |
| sigma_commit | 55 | 封筒（先に出す） | 456·G = (822,106) | — |
| sigma_response | 55〜56 | 連立方程式（中 2）: 式 1 本では解けない | 456 + 77·123 = 9927 ≡ 257 (mod 967) | mod を p にすると 846 |
| sigma_verify | 55 | 分配法則（中 1） | 257·G = R + 77·P = (595,110) | — |
| schnorr_sign | 61〜62 | ハッシュ = 操れないサイコロ | e = 57, s = 698（"week3"） | challenge_hash の引数順 |
| schnorr_verify | 62 | 答え合わせは自分で計算し直す | 改ざんで e′ = 723 → False | e を受け取らず再計算する |
| （nonce 再利用テスト） | 57〜58 | 連立方程式: 式 2 本なら解ける | x = 335·595 mod 967 = 123 | — |
提出前の自己チェック — 7 問、自分の言葉で
(1) なぜ足したあとにもう一度 % p を取るのか。 (2) なぜ 0 だけ逆元が無く、p は素数でなければならないか。 (3) ec_add で y₃ の符号を反転する理由と、垂直な直線のときの答え。 (4) 123 を 2 進で書いて、ec_add が何回で済むか。 (5) s = r + e·x が x を隠す理由と、同じ r を 2 回使うと漏れる理由。 (6) 検証者が x なしで s·G = R + e·P を確かめられる理由。 (7) e をハッシュにすると何が要らなくなるか。
7 つ言えたら、この宿題は「理解して」出せます。詰まった番号だけ、対応するカードに戻る。
ラボ 1
課題と同じトイ曲線（y² = x³ + 11 over F₁₀₀₉、位数 967、G = (1, 298)）で
3 手を実際に走らせます。モードを切り替えると、秘密鍵を使わずに同じ形の会話を作ります。
どちらも検証に通ることを確かめてください。
画面の計算を読む順番
このラボでは、楕円曲線の点の計算を mod 1009、係数 r・e・s の計算を
mod 967 で行います。2 つの法は別の役割です。
公開設定: x = 123, P = xG = (376,128)
[1] r = 456 を選ぶ
R = rG = 456G = (822,106)
[2] 検証者が e = 77 を選ぶ
[3] s = r + e·x = 456 + 77·123 = 9927 ≡ 257 (mod 967)
[4] 検証者の確認
sG = 257G = (595,110)
R + eP = (822,106) + 77(376,128) = (595,110)
rG や eP は、座標を普通に掛ける計算ではなく、
楕円曲線上の点を何度も足すスカラー倍です。
最後の 2 点が一致するのは、s = r + e·x と P = xG を代入すると
sG = (r + e·x)G = rG + e(xG) = R + eP になるからです。
正直モードの緑は「正しい秘密を持っていれば必ず通る（完全性）」を示します。 simulator モードも後で緑になりますが、それは「受理された 1 本だけでは、秘密を知っているとは言えない」ことを示すためです。
—
—
やりとりと検証の中身
—
ラボ 2
ラボ 1 で、R はチャレンジを受け取る前に決める必要があると分かりました。
ここでは、その R（正確には r）を使い回すと何が起きるかを確かめます。
攻撃者が持っているのは公開鍵と 2 本の署名だけです。
r を共通にしたまま 2 つのチャレンジを選ぶと、秘密鍵が復元されます。
秘密鍵 x = 123 は攻撃者に見えていません。使うのは R, e, s の公開値だけです。
—
攻撃者の計算
—
実測 — 本物の secp256k1 でも同じことが起きる
トイ曲線だからではありません。課題の実装で、Bitcoin と同じ曲線・256 ビットの秘密鍵に対して 同じ攻撃を走らせた結果です。
署名1: R.x = 0xb44cf0c87f8f960c... s1 = 0x28807ada8ee210bd...
署名2: R.x = 0xb44cf0c87f8f960c... s2 = 0x24da65e7523016c0...
R が一致している: True ← 公開情報だけで再利用が見抜ける
復元した x = 0x1b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
本物の x = 0x1b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
一致: True
署名を 2 本公開しただけで、秘密鍵が完全に失われます。
実際に、PlayStation 3 の ECDSA 署名鍵や、初期の Bitcoin ウォレットの一部が、 この形（乱数生成の不備で nonce が重複）で鍵を失っています。 「乱数を毎回変える」は運用上の注意ではなく、安全性の前提そのものです。
検問クイズ
読んだだけでは定着しない。ここではあなたが検証者の席に座り、 有限体の計算・曲線上の点・トランスクリプトの受理を審査する。問題は毎回その場で生成され、 判定は上のラボと同じ計算器が行う。3 回誤判定したら、その回は終了。
検問モードを選ぶ
誤答するとその場で解説が出る。分野を絞って弱点だけ潰すこともできる。
持ち帰り
① 「受理された」は、それ単体では何の証拠でもない。 simulator が秘密なしで受理される会話を作れました。効いているのは中身ではなく、 証明者が先にコミットし、チャレンジを後から受け取るという順番です。
② 抽出器と攻撃は、同じ 1 本の式。
x = (s₁−s₂)(e₁−e₂)⁻¹ は、
「知っていることの証明」でもあり「nonce 再利用で鍵が漏れる理由」でもあります。
安全性の根拠と攻撃手順が表裏一体なのは、この分野でよく出てくる形です。
③ 乱数の条件が 1 つ欠けると壊れる。 Week 2 の Beaver triple は使い回した瞬間に、Week 2 の OT は 範囲から 0 を除いた瞬間に、Week 3 の nonce は再利用した瞬間に壊れました。 3 週連続で同じ教訓です。
④ 2 つの法を混ぜない。 座標は mod p、スカラーは mod n。取り違えても小さい値のケースだけは通ってしまうので、 テストが弱いと気づけません。
⑤ 検算できる不変量を 1 つ持つ。
楕円曲線なら is_on_curve。
「結果が必ず満たすはずの性質」を 1 つ決めておくと、デバッグが探索から確認に変わります。
そして Week 1 からの問いは、今週こう言い換わります —— 「この値を隠しているのは何で、その条件は何本あるか」。 r がランダムであること、毎回違うこと、ハッシュに正しい文脈が入っていること。 1 本でも欠ければ、静かに壊れます。
用語集
読み返して引っかかった語をここで引く。由来が分かると、その言葉が何を約束しているかが分かります。
| 用語 | 意味 | なぜその言葉か | 宿題では |
|---|---|---|---|
| prover / verifier | 示す側／確かめる側 | ただの役名（証明者・検証者） | schnorr_sign を呼ぶ側／schnorr_verify を呼ぶ側 |
| statement | 公開される主張。「〜が存在する」の文 | state = 述べる。数学の「命題」 | 「P = x·G となる x がある」 |
| witness | それを見せれば主張が真だと誰でも確認できる値 | 法廷の「証人」。証人が居れば裁判が決まるように、w があれば R(x,w)=1 が確かめられる | 秘密鍵 x |
| proof | verifier に渡すデータ列 π | 「証明」だが文章ではなくバイト列 | (R, s) |
| transcript | 会話の記録 | transcribe = 書き起こす | (R, e, s) |
| 用語 | 意味 | なぜその言葉か | 宿題では |
|---|---|---|---|
| commitment | 値を先に固定して渡し、後で開ける約束の仕組み。封をした封筒 | commit = 約束する・確定させる（git commit と同じ語）。「一度確定したら取り消せない」が語感 | R = r·G が封筒 |
| commit / open | 封をする／開ける | — | sigma_commit／s を返す |
| binding | 開けられるのは最初に入れた値だけ | bind = 縛る。封筒を差し替えられない | r·G は r を決めれば 1 つ |
| hiding | 開けるまで中身が見えない | hide = 隠す | R から r が出ない（離散対数） |
| challenge / response | verifier が投げるランダムな問い／prover の答え | 挑戦状と応答 | e と s |
| nonce | 一度しか使わない乱数 | "number used once" の縮約。名前が「使い回すな」と言っている | r。使い回すと x が漏れる |
| sigma protocol | 出す → 選ぶ → 答える の 3 手の総称 | 矢印 →←→ が Σ の字に見える | Part 3 の 3 関数 |
| Schnorr | 離散対数でこの 3 手を作った方式 | 人名（Claus-Peter Schnorr、1989） | 課題名 |
| Fiat–Shamir 変換 | verifier の乱数をハッシュで置き換えて対話を消す | 人名 2 人（1986） | challenge_hash |
| 用語 | 意味 | なぜその言葉か | 宿題では |
|---|---|---|---|
| completeness（完全性） | 正しい主張はすべて通る | complete = 欠けがない。通すべきものを取りこぼさない | test_honest_transcript_accepts |
| soundness（健全性） | 通ったなら真。嘘を通さない | sound = 確かな・堅牢な | test_wrong_response_rejects |
| knowledge soundness | 通ったなら「知っている」 | 健全性の強い版 | test_nonce_reuse_leaks_secret |
| zero-knowledge | verifier が得る知識の増分がゼロ。公開情報だけで再現できる | knowledge（知識）が zero | ラボ 1 の simulator モード |
| simulator | 本物そっくりを秘密なしで作る装置 | ゼロ知識の定義に使う道具。作れる = 漏れていない | R := s·G − e·P |
| extractor（抽出器） | prover から秘密を絞り出す装置 | 知識健全性の定義に使う道具。絞り出せる = 知っていた | x = (s₁−s₂)/(e₁−e₂) |
| 用語 | 意味 | なぜその言葉か | 宿題では |
|---|---|---|---|
| mod／法（modulus） | p で割った余りだけ見る | modulus = 尺度・基準 | % p、% n |
| 体（field）／有限体 F_p | 四則が全部できる数の集合／元が有限個のもの | ドイツ語 Körper（体）の直訳。p が素数のときだけ体 | p = 1009 |
| 群（group） | 演算 1 つで閉じた集合 | — | 曲線の点の足し算 |
| 生成元（generator）／位数（order） | 1 個で全員を作れる元／何回で一周するか | generate = 生む。order = 個数 | G と n = 967 |
| 楕円曲線（elliptic curve） | y² = x³ + ax + b の点の集合 + O | 曲線は楕円ではない。楕円の弧の長さの積分（楕円積分）の研究から出た名前が残った | y² = x³ + 11 |
| スカラー（scalar）倍 | 点を x 回足す x·G | scalar = 目盛りの数 = ただの数（点やベクトルに対して） | ec_scalar_mul |
| 離散対数（discrete log） | x·G から x を求める問題（難しい） | log = 何乗したか。連続でない（離散）世界の log | 公開鍵から x が出ない理由 |
| ハッシュ（hash） | 入力を固定長のぐちゃぐちゃな値にする一方向関数 | hash = 細切れにする（ハッシュドポテト） | challenge_hash の中身 |
| 多項式（polynomial） | 係数表現 (5,2,3) と評価表現（点での値）の 2 つの持ち方 | poly = 多い、nomial = 項 | （宿題には出ない） |
| 補間（interpolation） | 点から式を復元する | inter = 間、pole = 点。点と点の間を補う。Lagrange は人名 | 弦の傾きの計算が 1 次の補間 |
| フーリエ変換 | 係数 ↔ 評価値の翻訳機 | 人名（1800 年頃、熱の研究） | （Week 4） |
| 用語 | 意味 | なぜその言葉か | 宿題では |
|---|---|---|---|
| arithmetization（算術化） | 計算を算術の式（制約）に直す工程 | arithmetic = 算術（+ − × ÷） | （Week 1・4） |
| constraint（制約） | = 0 になるべき式 | constrain = 縛る | — |
| R1CS | 各制約が掛け算 1 個の制約系 | Rank-1 Constraint System。行列の階数（rank）が 1 | — |
| AIR | 実行トレースの表と、行のあいだの制約 | Algebraic Intermediate Representation。コンパイラの「中間表現」を借用 | （Week 4 STARK） |
| SNARK | 短く・非対話で・知っていることを論証する方式 | Succinct Non-interactive ARgument of Knowledge。argument は「計算力の限られた prover には破れない」、proof は「無限の計算力でも破れない」の使い分け | — |
| oracle／IOP | 何でも正しく答える仮想の箱／検証者が証明の好きな場所だけ問い合わせる形 | 神託。実物のオラクル ≈ commitment。random oracle = ハッシュを理想の乱数箱と見なす仮定 | Fiat–Shamir の仮定 |
| KZG／SRS／trusted setup | 多項式のコミットメント／皆が参照する公開の点の列／τ を捨てる儀式 | Kate・Zaverucha・Goldberg（人名 3 人、2010）。Structured Reference String | （Week 4 PLONK） |
| Merkle 木 | ハッシュを木にして根 1 個で全体を代表 | Ralph Merkle（人名） | （Week 4 STARK） |
| FRI | 多項式が低次数かを折り畳みで確かめる | Fast Reed–Solomon IOP of Proximity | （Week 4） |
| SumCheck | 和が正しいかを、全部足さずに確かめる | そのまま「和の検査」 | （Week 4 GKR） |
付録
上のカード列で骨組みが入ったあとで、細部を足したいときに開いてください。壊した採点結果、ペアリング・FFT・R1CS/AIR の具体例、数独 ZKP のグループワークはここにあります。
出発点
Week 3 の週 README が言うテーマは楕円曲線と Schnorrで、課題も
schnorr-from-scratch です。ところが配られた講義スライドの表題は
「zkSNARK part 1」で、中身は有限体・多項式・commitment・arithmetization。
一見すると別の話に見えます。
別の話ではありません。スライドと課題は、「秘密を見せずに、計算が正しいと納得させる」 という同じ目的を、別の細かさで扱っています。スライドは計算全体をどう変換するかを説明し、 課題はその中の「楕円曲線上で、秘密を知っていることを示す」部分を実装します。
だからこのノートも 2 つの順番で説明します。前半は課題の計算（有限体 → 楕円曲線 → Schnorr）を、実際に壊した採点結果とともに説明します。後半はスライドの計算 （多項式 → commitment → arithmetization）を、今週の課題と接続して説明します。 後半は Week 4 以降で手を動かす場所です。
前提について
今週から、土台の数学がそのまま実装に出てきます。
mod 演算・群・体・逆元・離散対数に不安があれば、先に 土台編（有限体と楕円曲線） を読んでください。Week 1 の回路も Week 2 のシェアも、この土台の上に乗っています。
特に今週は 「割り算＝逆元の掛け算」が楕円曲線の傾きの計算で、 「0 に逆元はない」が垂直な接線の場合分けで、それぞれ実装として現れます。
この頁の構成
宿題の読み方
課題 solution.py に書く関数は 10 個です。この節は、その 10 個を上から順に、
1 個ずつ、学校で習った数学のどこから来たかを先に言ってから読みます。
他の節は深掘りなので、まずここだけで「自分の解答を自分の言葉で説明できる」状態を作ってください。
この節の使い方
手元で solution.py を開いておいて、関数ごとに次の 5 つを読みます。
① 学校の数学のどこから来たか → ② 課題での役割（何が入って何が出るか） →
③ 数値を 1 組入れて追う → ④ 自分のコードの読み方 → ⑤ 説明できるかの 1 問。
数値はすべて課題のトイ曲線（p = 1009、n = 967、G = (1, 298)、秘密鍵 x = 123）で、
採点器 tests/public.py に出てくる値そのものです。
| 学校で習ったこと | 課題での姿 |
|---|---|
| 割り算の余り（小 5・中 1） | mod p — field_add / field_mul |
| 割り算は逆数を掛けること（小 6） | 逆元 — field_inv |
| 最大公約数の互除法（中 1・高 1） | 拡張ユークリッド — extended_gcd（与えられる） |
| 2 点を通る直線の傾き（中 2） | ec_add の弦の傾き λ |
| 接線の傾きは微分（数 II） | ec_add の 2 倍算の λ |
| 3 次方程式の解と係数の関係（数 II） | x_R = λ² − x_P − x_Q |
| 2 進法（数 A） | double-and-add — ec_scalar_mul |
| 未知数 2 個に式 1 本では解けない（中 2 連立方程式） | s = r + e·x が x を隠す理由 — sigma_response |
| 分配法則（中 1） | s·G = R + e·P — sigma_verify |
| 「同じ r で 2 本」なら解ける（中 2） | nonce 再利用で x が漏れる理由 |
① 学校の数学: 「13 ÷ 7 の余りは 6」。時計は 13 時を 1 時と呼ぶ（12 で割った余り）。 mod p は「p で割った余りだけを見る」という約束で、それ以上のことは何もありません。
② 課題での役割: 整数 a, b, 素数 p を受け取り、(a + b) mod p、(a × b) mod p を
0 以上 p 未満で返す。負の数が来ても、p より大きい数が来ても、余りに直して返す。
③ field_add(3, 4, 7) → 3 + 4 = 7, 7 ÷ 7 = 1 余り 0 → 0 field_mul(3, 4, 7) → 3 × 4 = 12, 12 ÷ 7 = 1 余り 5 → 5 field_add(-3, 1, 7) → -3 + 1 = -2 → 余りは 5（-2 = -1×7 + 5） → 5
④ コード: return (a + b) % p と return (a * b) % p。Python の % は
負の数でも 0..p−1 を返すので、これだけで正規化が済みます。
⑤ 説明できるか: 「なぜ足したあとにもう一度 % p を取るのか」→ 入力が範囲外でも結果を 0..p−1 に揃えるため。
採点器はわざと −3 や 100 を入れてきます。
① 学校の数学: 6 ÷ 5 は 6 × (1/5)。割り算は「逆数を掛ける」でした。 余りの世界には分数がありませんが、「掛けて 1 になる相手」ならいます。 mod 13 で 5 × 8 = 40 = 3×13 + 1、余り 1。だから 8 が 5 の逆数の役（逆元）で、 「÷5」の代わりに「×8」をします。
その相手をどう見つけるか: 中学の互除法（最大公約数を求める、大きい方を小さい方で割って余りを取る手順）を
逆にたどると、「5 × (何か) + 13 × (何か) = 1」の形が作れます。この「何か」が逆元です。
課題ではこの手順が extended_gcd(a, b) として与えられていて、a·x + b·y = g（g は最大公約数）を
満たす (g, x, y) を返します。
③ mod 13 で 5 の逆元 互除法: 13 = 2×5 + 3, 5 = 1×3 + 2, 3 = 1×2 + 1 ← 余りが 1 になった 逆にたどる: 1 = 3 − 2 = 3 − (5 − 3) = 2×3 − 5 = 2×(13 − 2×5) − 5 = 2×13 − 5×5 → 5 × (−5) + 13 × 2 = 1 → extended_gcd(5, 13) は (1, −5, 2) mod 13 で見ると 13×2 は消えて 5 × (−5) ≡ 1。−5 を 0..12 に直して 8。 検算 5×8 = 40 ≡ 1 ✓ 課題の簡易チェック: field_inv(3, 11) → extended_gcd(3, 11) = (1, 4, −1) → 3×4 = 12 ≡ 1 → 4
④ コード: a %= p で範囲に入れ → a == 0 なら ValueError（0 に何を掛けても 1 にならない）
→ g, x, _ = extended_gcd(a, p) → return x % p。
最後の % p を忘れると −5 のまま返して落ちます（採点器: 「逆元は 0..p-1 に正規化して返してください」）。
⑤ 説明できるか: 「なぜ 0 だけ逆元が無いのか」→ 0 × 何 = 0 で、1 にならないから。
「なぜ p は素数でなければならないか」→ 合成数だと 2×3 = 6 ≡ 0（mod 6）のように、0 でないのに逆元を持てない数が出るから（土台編）。
① 学校の数学: 3 つ使います。 (a) 2 点を通る直線の傾きは「y の増分 ÷ x の増分」（中 2 の一次関数）。 (b) 同じ点で 2 回使うときは、直線ではなく接線。接線の傾きは微分（数 II）。 (c) 直線と 3 次曲線は最大 3 点で交わり、3 つの x 座標の和は 解と係数の関係から決まる（数 II）。
② 課題での役割: 曲線 y² = x³ + a·x + b（mod p）の上の点 P, Q を受け取り、
「P と Q を通る直線が曲線と交わる 3 つ目の点を、x 軸で折り返した点」を返す。
これを P + Q と呼ぶことにする。座標を足すのではありません。
座標の計算はぜんぶ mod p で、「÷」はぜんぶ field_inv を掛ける操作です。
傾き λ … 弦（P ≠ Q）: λ = (y_Q − y_P) / (x_Q − x_P) ← (a) 中 2
… 接線（P = Q）: λ = (3·x_P² + a) / (2·y_P) ← (b) y² = x³+ax+b を微分: 2y·y' = 3x²+a
3 つ目の点: x_R = λ² − x_P − x_Q ← (c) 直線 y = λx + c を代入すると
x³ − λ²x² + … = 0 で、3 解の和 = λ²
折り返し: y_R = λ·(x_P − x_R) − y_P ← 直線上の点 y_P + λ(x_R − x_P) の符号を反転
③ 2G（G = (1, 298) を 2 倍。p = 1009, a = 0）
λ = 3·1² / (2·298) = 3 / 596 = 3 × 596⁻¹ = 3 × 601 = 1803 ≡ 794 （596×601 = 358196 ≡ 1 を検算）
x_R = 794² − 1 − 1 = 630436 − 2 = 630434 ≡ 818
y_R = 794 × (1 − 818) − 298 = 794 × (−817) − 298 ≡ 800
→ 2G = (818, 800) ← 採点器の期待値と一致
G + 2G（弦）: λ = (800 − 298)/(818 − 1) = 502/817 = 502 × 762 ≡ 113 → x_R = 113² − 1 − 818 ≡ 851, y_R = 516 → 3G = (851, 516)
④ コードの場合分けは 4 つで、順番が大事です。
(1) どちらかが None（無限遠点 = 足し算の 0 の役）なら、もう片方を返す。
(2) x が同じで y が「符号違い」なら、直線が垂直で 3 つ目の交点が無い → 無限遠点を返す
（y_P = 0 の点を 2 倍するときもここ。分母 2y が 0 で割れないから）。
(3) P == Q なら接線の λ。(4) それ以外は弦の λ。
(2) を先にしないと、(3)(4) で field_inv(0) が例外を投げます。
⑤ 説明できるか: 「なぜ y_R の符号を反転するのか」→ 反転しないと結合法則が成り立たず「足し算」にならない。
反転を忘れると採点器は「点が曲線上にありません」と言います（2G = (818, 622) は曲線に乗らない）。
① 学校の数学: 2 進法（数 A）。13 = 8 + 4 + 1 = 1101₂。 「G を 13 回足す」は「8G + 4G + G」と同じで、8G は G を 2 倍、2 倍、2 倍すれば 3 回で作れる。
② 課題での役割: 整数 k と点 P を受け取り、P を k 回足した点 k·P を返す。
素直に k 回 ec_add すると、k ≈ 2²⁵⁶（secp256k1）では宇宙が終わっても終わらないので、
k を 2 進で下の桁から読み、桁が 1 のときだけ足し、毎回 P を 2 倍する（double-and-add）。
③ 123·G 123 = 1111011₂ （下の桁から 1,1,0,1,1,1,1） 桁 1: 足す addend = G = (1,298) result = (1,298) 桁 1: 足す addend = 2G = (818,800) result = (851,516) 桁 0: 足さない addend = 4G = (357,812) result = (851,516) 桁 1: 足す addend = 8G = (900,790) result = (492,153) 桁 1: 足す addend = 16G = (298,533) result = (932,428) 桁 1: 足す addend = 32G = (637,315) result = (122,173) 桁 1: 足す addend = 64G = (834,807) result = (376,128) ← 123G = (376,128)。これが公開鍵 P ec_add の回数: 足し算 6 回 + 2 倍 6 回 = 12 回（素直にやると 122 回）
④ コード: result = None（0 の役）から始め、while k > 0: k, bit = divmod(k, 2)
で最下位の桁を取り出し、bit が 1 なら result = ec_add(result, addend)、
そのあと addend = ec_add(addend, addend)。divmod(k, 2) は「2 で割った商と余り」で、
余りがその桁、商が「残りの桁」です。
⑤ 説明できるか: 「k = 0 のとき何を返すか」→ 何も足さないので None（無限遠点）。
「n·G はなぜ None になるか」→ n は G の位数（G を n 回足すと 0 の役に戻る）。採点器の
test_order_times_generator_is_identity がこれ。
① 学校の数学: ここは数学というより約束事です。じゃんけんで「先に手を見せた方が負ける」ので、 手を封筒に入れて先に置く。r をそのまま見せず、R = r·G だけを見せます。 R から r を逆算するのが「離散対数問題」で、これが難しいことがこの週の安全性の土台です。
② 課題での役割: 乱数 r を受け取り、R = ec_scalar_mul(r, G) を返す。それだけ。
③ sigma_commit(456) → 456·G = (822, 106)
④ コード: 1 行。⑤ 説明できるか: 「なぜ r を先に固定する必要があるか」→ あとで来るチャレンジ e を見てから r を選べるなら、秘密を持っていなくても辻褄を合わせられる（次の節の simulator）。先に封をするから、あとの s に意味が出る。
① 学校の数学: 中 2 の連立方程式。未知数が 2 個（r と x）あって式が 1 本（s = r + e·x）なら、解けません。 だから s を渡しても x は分からない。ところが同じ r で 2 本目の式が手に入ると、未知数 2 個・式 2 本で解ける。 これが nonce 再利用攻撃の全部です。
② 課題での役割: 秘密鍵 x、乱数 r、検証者のチャレンジ e を受け取り、
s = (r + e·x) mod n を返す。ここだけ mod が n（G の位数）です。
座標の計算は「p で割った余り」の世界、r や x のような「G を何回足すか」の数は「n で割った余り」の世界。
2 つの世界が 1 つの課題に同居しています。
③ sigma_response(x=123, r=456, e=77) s = 456 + 77 × 123 = 456 + 9471 = 9927, 9927 = 10 × 967 + 257 → 257 （mod を p = 1009 で取ってしまうと 846 になり、採点器の期待値 257 と合わない） nonce 再利用（同じ r = 456、e₁ = 77 と e₂ = 90）: s₁ = 257, s₂ = 456 + 90×123 mod 967 = 889 s₁ − s₂ = (e₁ − e₂)·x → x = (s₁ − s₂) × (e₁ − e₂)⁻¹ = 335 × 954⁻¹ = 335 × 595 mod 967 = 123 ← 秘密鍵が出た
④ コード: return (r + e * x) % curve.n。⑤ 説明できるか: 「なぜ p ではなく n か」→
s は「G を何回足すか」の数で、G は n 回で一周するから、n で割った余りだけが意味を持つ。
「なぜ r は毎回変えるのか」→ 上の 2 本の式。
① 学校の数学: 分配法則（中 1）。(r + e·x)·G = r·G + e·(x·G)。
左辺は s·G、右辺は R + e·P。検証者は x を持っていませんが、R と e と P は持っているので右辺が計算できます。
② 課題での役割: 公開鍵 P、封筒 R、チャレンジ e、応答 s を受け取り、
s·G == R + e·P かどうかを True / False で返す。
③ sigma_verify(P=(376,128), R=(822,106), e=77, s=257) 左辺: 257·G = (595, 110) 右辺: 77·P = (345,630), R + 77·P = (822,106) + (345,630) = (595, 110) → 一致。True s を 1 ずらすと 258·G ≠ (595,110) → False（採点器の test_wrong_response_rejects）
④ コード: left = ec_scalar_mul(s, G)、right = ec_add(R, ec_scalar_mul(e, P))、return left == right。
⑤ 説明できるか: 「通ったら x を知っていると言えるか」→ 1 本だけでは言えない（simulator は x なしで通る会話を作れる）。
言えるのは「同じ R で 2 つの e に答えられるなら」（次の節）。
① 学校の数学: 対話では検証者が e を「その場で」選びました。その場にいない相手にも渡せるようにするには、 e を誰にも操れない機械に選ばせればよい。ハッシュ関数 H(R, P, メッセージ) がその機械です （入力を 1 文字変えると出力が全部変わり、出力から入力は逆算できない）。これが Fiat–Shamir 変換で、 出来上がったものが署名です。
② 課題での役割: 秘密鍵 x、メッセージ、乱数 nonce を受け取り、
(1) R = nonce·G、(2) P = x·G、(3) e = challenge_hash(R, P, message, n)、(4) s = nonce + e·x mod n、
(5) (R, s) を返す。3 手の e をハッシュに置き換えただけで、他は sigma_* の再利用です。
③ schnorr_sign(x=123, message=b"week3", nonce=456) R = 456·G = (822, 106) P = 123·G = (376, 128) e = H(R, P, "week3") mod 967 = 57 ← 検証者の代わりにハッシュが選んだ s = 456 + 57 × 123 = 7467 = 7 × 967 + 698 → 698 署名 = ((822, 106), 698)
④ コード: R = sigma_commit(nonce)、pubkey = ec_scalar_mul(x, G)、
e = challenge_hash(R, pubkey, message, curve.n)、s = sigma_response(x, nonce, e)。
引数の順番 (R, pubkey, message) を入れ替えると、自分の verify では通るのに採点器の固定ベクトルだけ落ちます
（自分同士では整合するが、他人と互換性がない）。
⑤ 説明できるか: 「なぜ e にメッセージを入れるのか」→ 入れないと、1 つの署名がどんなメッセージにも使い回せる。
① 学校の数学: 「答え合わせは、相手の言う e を信じず、自分で同じ機械を回す」。それだけです。
② 課題での役割: 公開鍵 P、メッセージ、署名 (R, s) を受け取り、
e = challenge_hash(R, P, message, n) を計算し直して、sigma_verify(P, R, e, s) を返す。
③ schnorr_verify(P, b"week3", ((822,106), 698)) e = H(R, P, "week3") = 57 → 698·G == (822,106) + 57·P ? → True メッセージを "week3!" に改ざん → e' = 723 → 698·G ≠ R + 723·P → False
④ コード: 3 行。⑤ 説明できるか: 「なぜ e を署名に含めて送らないのか」→ 送ると、証明者が都合のよい e を選んで R を逆算できてしまう（simulator の順番）。検証者側で計算し直すから、e は証明者に選べない。
schnorr_verify ─┬─ challenge_hash（与えられる）
└─ sigma_verify ─┬─ ec_scalar_mul ─── ec_add ─┬─ field_add / field_mul
└─ ec_add └─ field_inv ─── extended_gcd（与えられる）
schnorr_sign ───┬─ sigma_commit ─── ec_scalar_mul
├─ challenge_hash
└─ sigma_response（mod n の足し算と掛け算だけ）
下から順に: 余りの計算 → 逆元 → 点の足し算 → 点の k 倍 → 3 手 → 署名
下が壊れると上は全部壊れる（y_R の符号を間違えると 23 テストが落ちた理由）
提出前の自己チェック（答えは各ステップの ⑤）: (1) なぜ % p をもう一度取るのか。 (2) なぜ 0 だけ逆元が無く、p は素数でなければならないか。 (3) ec_add で y_R の符号を反転する理由と、垂直な直線のときの答え。 (4) 123 を 2 進で書いて、ec_add が何回で済むか。 (5) s = r + e·x が x を隠す理由と、同じ r を 2 回使うと漏れる理由。 (6) 検証者が x なしで s·G = R + e·P を確かめられる理由。 (7) e をハッシュにすると誰が得をするか（対話が要らなくなる）。 この 7 つが自分の言葉で言えれば、この宿題は「理解して」出せます。
全体像
「計算を 4 回翻訳する」という言葉だけでは、何のための変換か分かりません。 先に、証明者と検証者が困っていることを固定します。
最初の問い
秘密 w を見せずに、「公開された計算の答えを、本当に作れる秘密を知っている」とどう確認するか。
例として、公開値は y = 15、秘密は w、確認したい条件は
w³ + w + 5 = y とします。w = 2 なら
2³ + 2 + 5 = 15 なので条件を満たします。しかし w をそのまま渡すと、秘密を隠せません。
検証者が欲しいのは w そのものではなく、w が条件を満たすことを確認できる短いデータです。
公開情報（statement）: y = 15
秘密情報（witness）: w = 2
証明したい主張: 「この y に対して、条件を満たす w が存在する」
箱は 5 個ですが、箱と箱の間の矢印が 4 本あります。 「4 回翻訳する」とは、この 4 本の変換を指します。 色が付いた有限体・楕円曲線・右端の対話は今週、 多項式とフーリエ変換は後の週で扱います。
プログラムは「w を 3 乗して足す」という手順ですが、証明システムはプログラム全体を一度に読むのではなく、 各行が正しいかを確認します。そこで中間値を名前付きで保存します。
t₁ = w² （w を 2 回掛けた結果）
t₂ = t₁·w （w³ の結果）
t₂ + w + 5 − y = 0 （最後の足し算の確認）
w = 2, y = 15 を代入すると、t₁ = 4、t₂ = 8 で、3 本とも 0 になります。
これが Week 1 で見た R1CS の考え方です。計算を細かい式へ分ける理由は、検証者が各式を機械的に確認できるからです。
制約が 3 本なら 3 本を確認できますが、実際のプログラムでは何百万本にもなります。 そこで制約の係数や中間値を多項式として並べ、複数の条件が同時に成立することを 多項式の等式として表します。多項式にすれば、ランダムな点で値を比べる検査へ縮められます。
この検査は「1 点が合ったから必ず正しい」という意味ではありません。 異なる多項式が同じ値になる点は限られるため、ランダムな点を使うと、間違いを見逃す確率を非常に小さくできます。 ここで初めて、検証者が全計算をやり直さずに済む理由が生まれます。
検証者が「この点で評価して」と言ってから、多項式を都合よく選べるなら証明になりません。
先に多項式を c という短い commitment にして渡し、あとで必要な値だけを開きます。
先に固定する性質が binding、開くまで中身が分からない性質が hidingです。
commit: 多項式と乱数から c を作り、c だけ渡す
open: 必要な評価値と、その値が同じ多項式から来たことを示す
verify: c と開示値の関係を確認する
検証者が受け取るのは、w や全係数ではありません。commitment と、少数の評価値・等式だけです。 楕円曲線の加法やペアリングを使う方式では、それらの関係を少数の群演算に変えて確認できます。 これが「証明は短く、検証は速くなる」の具体的な意味です。
この順番は、用語を増やすための順番ではありません。秘密を隠したいという最初の条件から出発し、 「全計算を見せずに、局所的な式だけを確認する」ために、制約・多項式・commitment が必要になります。
研究の流れもこの問題意識に沿っています。まず Schnorr のような 3 手の対話で秘密の知識を示し、 Fiat–Shamir で検証者のチャレンジをハッシュに置き換えて 1 通にし、 さらに任意のプログラムを制約と多項式へ変換して、短い証明を作れるようにしました。
今週の位置
Week 3 の課題は、上の第 4 変換を理解するための最小例です。
有限体と楕円曲線の上で、R = rG、s = r + e·x、
sG = R + eP を実際に計算します。
つまり、いきなり zkSNARK 全体を作っているのではなく、 「秘密を持つ人が、秘密を見せずに式の関係を証明する」最小の対話を先に作っています。 次のラボで、その 1 回の会話を数字で追います。
前提 1
課題は Part 1 から Part 3 まで一本につながっていて、 下の Part が間違っていると上の Part は動きません。 その一番下が、逆元です。
有限体で割り算をするとは、逆元を掛けることでした。
a⁻¹ は a·a⁻¹ ≡ 1 (mod p) を満たす値です。
求め方は拡張ユークリッドの互除法。ax + bp = 1 を
満たす整数 x, b を見つける操作で、両辺を mod p で見ると
bp ≡ 0 なので ax ≡ 1。つまり x が a の逆元です。
F₁₃ で 5⁻¹ を求める
13 = 2·5 + 3 5 = 1·3 + 2 3 = 1·2 + 1
↓ 1 まで下りたら、逆に書き戻す
1 = 3 − 1·2 = 2·13 − 5·5
mod 13 で見ると −5·5 ≡ 1、よって 5⁻¹ = −5 = 8
検算: 5·8 = 40 = 39 + 1 ≡ 1 (mod 13) ✓
実測 — 正規化を忘れると、ここで止まる
拡張ユークリッドが返す x は、負の数のことがあります。
上の例でも、素直に出てくるのは 8 ではなく −5 でした。
そのまま返す実装を採点器に通すと、こうなります。
FAIL: test_inv_small (a=10, p=17) FAIL: test_inv_small (a=2, p=1009) FAIL: test_inv_small (a=966, p=1009) AssertionError: False is not true : 逆元は 0..p-1 に正規化して返してください
値としては正しいのに、表現がそろっていないと落ちる。
Week 2 の share でもまったく同じ理由で落ちました
（[70, -2, -71] vs 正解 [3, 65, 63]）。
「体の元は 0..p−1 の代表で持つ」は、週をまたいで効いてくる約束事です。
0 だけは逆元を持たない — これが後で効く
0 に何を掛けても 1 にはならないので、0 の逆元は存在しません。課題では
field_inv(0, p) で ValueError を投げることが要求されます。
この「0 で割れない」が、楕円曲線の場合分けにそのまま姿を変えて現れます。
2 倍算の傾きは λ = (3x² + a) / 2y。y = 0 の点では分母が 0 になり、
傾きが計算できません。幾何的には接線が垂直になる場所で、そのときの
2P は無限遠点 O と定めます。
「割れないから例外」ではなく、「割れない場所には別の答えがある」という形になっています。
前提 2
有限体は「+ と ×」の世界でした。その上に、まったく別の演算を持つ群をもう 1 つ作ります。
曲線 y² = x³ + ax + b は 3 次式なので、直線と最大 3 点で交わります。
そこで 2 点 P, Q を通る直線が曲線と交わる 3 点目を R′ とし、その x 軸反転を
P + Q と定めます。
ここがトリッキー — 「足す」のに座標は足さない
普通のベクトルなら (x₁+x₂, y₁+y₂) を期待しますが、楕円曲線では違います。
P と Q を通る直線を引く → 3 つ目の交点 R′ を取る → 上下反転する、
という 3 手全体を新しい「足し算」と定義しています。
3 つ目の交点: R′ = (x₃, y′)
楕円曲線の和: P + Q := −R′ = (x₃, −y′)
つまり R′ はまだ答えではなく、反転した点が答えです。
この最後の反転を忘れると、後の加法公式では y の符号が逆になり、
群として必要な規則も壊れます。
なぜ反転するのか: 素直に「3 点目」を和にすると、単位元と逆元がうまく定義できません。 反転を入れると、一直線上の 3 点の和が O（無限遠点）という美しい規則になり、 O が単位元、x 軸対称の点どうしが逆元、という群の形が完成します。
直線の傾き λ を求め、交点の座標を解くと、次の式になります。
弦（P ≠ Q）: λ = (y_Q − y_P) / (x_Q − x_P)
接線（P = Q）: λ = (3x_P² + a) / (2y_P)
x_R = λ² − x_P − x_Q
y_R = λ(x_P − x_R) − y_P
P と Q が同じなら、なぜ微分なのか
違う 2 点なら「P と Q を通る直線」が 1 本に決まり、その傾きは
(y_Q−y_P)/(x_Q−x_P) です。ところが P = Q を代入すると
0/0 になり、同じ 1 点だけでは直線を決められません。
そこで「曲線に P でちょうど触れる直線」——接線を、2 点を通る直線の代わりに使います。
微分は、この接線の傾きを求める操作です。曲線
y² = x³ + ax + b の両辺を x で微分すると、
2y · dy/dx = 3x² + a
dy/dx = (3x² + a) / (2y)
P = (x_P, y_P) での傾き λ = (3x_P² + a) / (2y_P)
実数のグラフでは「Q を P に近づけると、P と Q を結ぶ弦が接線へ近づく」と考えられます。 有限体には「少し近づける」という距離はないので、実装では極限を計算せず、 微分で得た最後の代数式を mod p で使うだけです。
さらに y_P = 0 なら: 接線式も分母が 0 になります。このとき接線は垂直で、
曲線上の有限な 3 点目を取れないため 2P = O（無限遠点）とします。
「/」は全部、前段の field_inv です。実数のグラフは計算規則を理解する補助で、 計算は最初から最後まで F_p の中で行います。 グラフに描ける曲線と、実際に計算している有限集合は別物だと区別します。
曲線 y² = x³ + x + 6 over F₁₁、点 P = (2, 7) の 2 倍。
λ = (3·2² + 1) / (2·7) = 13 / 14 ≡ 2 / 3 (mod 11)
3⁻¹ = 4（3·4 = 12 ≡ 1）なので λ = 2·4 = 8
x_R = 8² − 2 − 2 = 60 ≡ 5 （60 = 55 + 5）
y_R = 8·(2 − 5) − 7 = −31 ≡ 2 （−31 + 33 = 2）
2P = (5, 2) 検算: 2² = 4、5³ + 5 + 6 = 136 ≡ 4 (mod 11) ✓
検算の癖をつけると、デバッグが一瞬で終わります。
課題には is_on_curve が用意されていて、
計算結果が曲線に乗っていなければ、公式のどこかが間違っていると即座に分かります。
y_R = λ(x_P − x_R) − y_P の引き算の向きを逆にした実装を、
採点器に通した結果です。
FAIL: test_doubling AssertionError: 2G = (818, 622) が曲線上にありません。 y_R = lam * (x_P - x_R) - y_P の符号や mod の取り忘れを確認してください FAIL: test_scalar_mul_is_homomorphic (k1=3, k2=5) AssertionError: Tuples differ: (951, 492) != (755, 55)
正解は (818, 800)。x 座標は合っていて、y だけがずれます
（800 + 622 = 1422、1009 を引くと 413…と、
単純な符号反転にもなっていない）。
「曲線上にあるか」というたった 1 つの検査が、この種のミスを全部捕まえます。
準同型性 (k₁+k₂)G = k₁G + k₂G のテストも同時に落ちるのは、
群の構造そのものが壊れているからです。
まず言葉を分けます。スカラーは普通の整数 k、スカラー倍
kP は楕円曲線の点 P を k 個足した点です。
(kx, ky) のように座標を k 倍する操作ではありません。
1P = P
2P = P + P
3P = P + P + P
kP = P + ··· + P （P が k 個）
kP を定義どおり計算すると、同じ P を順番に足すため k−1 回かかります。
そこで k を 0 と 1 の二進数へ直します。これがビット分解（bit decomposition）です。
倍にしながら、ビットが 1 のところだけ足すと
log₂k に比例します。
k = b₀·2⁰ + b₁·2¹ + ··· + bₘ·2ᵐ （各 bᵢ は 0 または 1）
kP = b₀·P + b₁·(2P) + ··· + bₘ·(2ᵐP)
各ビットは「対応する点を使うか、使わないか」のスイッチです。
0 なら何も足さず、1 ならその時点の 2ⁱP を足します。
13 なら 1101₂ = 8+4+1 なので、8P、4P、P を選びます。
13P（13 = 1101₂）: P →2P →4P →8P と 3 回倍にして、8P + 4P + P で 2 回足す = 5 回
定義どおりなら 12 回
1101₂ を左から読んで 13P を作る
二進数では、左へ 1 桁進むことは、それまでの数を 2 倍することです。
次のビットが 1 なら、さらに 1 を足します。点でも同じ規則を使い、
数の「2 倍」を点の doubling、「+1」を +P に置き換えます。
13 = 1101₂ 先頭の 1: R = P （いま 1P） 次のビット 1: R = 2R + P = 2P + P = 3P （いま 11₂P） 次のビット 0: R = 2R = 6P （いま 110₂P） 最後のビット 1: R = 2R + P = 12P + P = 13P （いま 1101₂P）
doubling が 3 回、+P が 2 回で合計 5 回です。
「13 回ぶんの情報を省略した」のではなく、すでに作った 3P や 6P を丸ごと倍にして再利用したので速くなります。
なぜ log₂k なのか: k が 2 倍になっても、二進数の桁は 1 桁増えるだけです。
256 ビットの k なら、値そのものは約 2²⁵⁶ でも、読むビットは 256 個しかありません。
各ビットにつき doubling 1 回と、必要なら加算 1 回なので、512 回未満で終わります。
実測（secp256k1、この課題の実装）:
k = 13 ec_add 6 回 / 0.2 ms k = 123 ec_add 12 回 / 0.4 ms k ≈ 2^64 ec_add 100 回 / 3.1 ms k ≈ 2^256 ec_add 446 回 / 12.9 ms 素朴な加算の実測速度: 約 1,231,505 回/秒 → nG（n ≈ 2^256）を素朴に足すと 約 3.0×10^63 年 double-and-add なら 512 回未満で終わる
課題のテストには nG = O（n は位数、約 2²⁵⁶）を確かめるケースがあるので、
素朴な実装だとテストが永遠に返ってきません。
「落ちる」のではなく「終わらない」という失敗の仕方をするのが、この間違いの特徴です。
土台の要
double-and-add のおかげで x から xP は一瞬で計算できます。
では逆に、P と xP から x を求めるには?
効率の良い方法が知られていません。これが楕円曲線上の離散対数問題で、 暗号の一方向性はここから来ています。
なぜ逆向きだけ難しく見えるのか
順方向では、秘密の整数 x のビットを自分で持っているので、
xP = Σ bᵢ(2ⁱP) と必要な点を選べます。逆向きでは結果の点
Q = xP しかなく、どのビット bᵢ を選んだかという履歴は点 Q に書かれていません。
小さい群なら P, 2P, 3P, … と順番に試せますが、約 2²⁵⁶ 個ある群では
全探索できません。足し算の公式が複雑だから自動的に安全なのではなく、
群演算は速いのに、結果からスカラーを戻す効率的な古典アルゴリズムが知られていない
ことを安全性の仮定にしています。
ただし量子計算では — Shor のアルゴリズム
十分に大規模で誤り訂正された量子コンピュータがあれば、Shor のアルゴリズムは
楕円曲線の離散対数を入力ビット数に対して多項式時間で解けます。
つまり P と公開鍵 Q = xP から秘密鍵 x を効率的に復元でき、
Schnorr、ECDSA、ECDH など現在の楕円曲線暗号は破られます。
今すぐ普通に解ける、という意味ではありません。 NIST の耐量子暗号プロジェクトも 「大規模量子コンピュータが実現すれば現在の多くの公開鍵暗号を破る」として 耐量子暗号への移行を進めていますが、その実現時期は不確実です。 量子耐性は、格子・符号・ハッシュなど離散対数とは別の難問に基づく方式へ移して得ます。
ハッシュに似ている — ただし同じものではない
一方向性の見方は似ています。m → Hash(m) は速いが逆算は難しい。
楕円曲線でも x → xP は速いが、P, xP → x は難しい。
公開鍵は、この「順方向だけ計算しやすい」構造を使っています。
hash: m ──速い──▶ H(m) 逆向きは原像探索
scalar multiply: x ──速い──▶ xP 逆向きは離散対数
違い: 固定長ハッシュは巨大な入力を短い出力へ潰すので多対一で、衝突があります。
一方、位数 n の生成点 P では x mod n と xP は部分群内で一対一です。
答え x は一意に存在するが、古典計算では効率よく見つけられない、という難しさです。
資料では乗法記法（g, gˣ）と加法記法（P, xP）が混ざりますが、
同じことの書き方違いです。スライドの Schnorr は乗法記法、
課題の実装は楕円曲線なので加法記法でした。
| 問題 | 乗法記法 | 加法記法 |
|---|---|---|
| 離散対数 | g, gᵃ から a | P, aP から a |
| 計算 Diffie–Hellman | gᵃ, gᵇ から gᵃᵇ | aP, bP から abP |
| 判定 Diffie–Hellman | T = gᵃᵇ か判定 | T = abP か判定 |
3 つの「難しい問題」は、何を答えれば勝ちか
Alice が秘密 a、Bob が秘密 b を選び、公開情報として P, aP, bP を出したとします。
正規の二人は、自分の秘密を相手の公開点へ掛ければ、同じ共有点を作れます。
Alice: a·(bP) = abP
Bob: b·(aP) = abP
盗聴者には aP と bP は見えます。しかし a も b もないため、
普通の点の加算だけで作れるのは (a+b)P までです。
欲しい abP には、秘密どうしの掛け算が必要です。
A = aP, B = bP が公開されているとき
A + B = (a+b)P ← できる
2A = (2a)P ← できる
3A − 5B = (3a−5b)P ← できる
abP ← a, b を知らないまま作る方法がない
点の加算と、公開された整数によるスカラー倍を何回組み合わせても、指数部分に作れるのは
αa + βb のような既知の係数による足し算（線形結合）だけです。
ab は未知数どうしの掛け算なので、この道具だけでは届きません。
どちらか一方、たとえば a を知っていれば aB = a(bP) = abP と一発で作れます。
両方を知らない盗聴者にも作れるかを問うのが CDH です。
DLP: a そのものを当てる問題。
CDH: a や b は答えなくてよいので、共有点 abP だけ作る問題。
DDH: abP を作る必要すらなく、候補 T が本物か Yes/No だけ答える問題。
積を見える場所へ移す — ペアリング
ペアリングは、2 つの点を受け取って別の群 G_T の元を返す写像です。
e: G₁ × G₂ → G_T と書きます。実用では G₁ と G₂ を
別々の楕円曲線部分群として扱い、G_T は有限体の乗法群とする
非対称ペアリングが一般的です。
e(aP, Q) = e(P, Q)ᵃ = e(P, aQ)
e(aP, bQ) = e(P, Q)ᵃᵇ
最初の式が双線形性です。ペアリングの中では、左の点に付いたスカラー a を、
右の点へ付け替えても、出力 G_T の指数として外へ出しても、結果が変わりません。
ここでいう「置き換え」は、点そのものが同じになるという意味ではなく、
ペアリングへ入れた後の値が等しいという意味です。
両側のスカラーをまとめると、a, b を知らなくても指数側に積 ab が現れます。
ただし出力は元の曲線上の abP ではなく、別の群にある
e(P,Q)ᵃᵇです。秘密 a や b が復元できるわけでもありません。
「ヴェイユ（Weil）ペアリング」なの？: ペアリングは、このような双線形写像の総称です。Weil pairing はその具体例の一つで、 Tate pairing や Ate pairing など別の種類もあります。このスライドの式は特定の方式だけでなく、 暗号で使うペアリングに共通する性質を抽象的に書いたものです。実用では高速な Ate 系の ペアリングがよく使われます。
ペアリングに必要な 3 条件:
① 双線形性 — 上のようにスカラーを左右・指数へ移せる。
② 非退化性 — すべての入力が単位元 1 へ潰れない。生成元 P,Q なら e(P,Q) ≠ 1。
③ 効率的計算可能性 — P,Q から e(P,Q) を現実的な時間で計算できる。
何がうれしいか: 候補 T に対して
e(T,Q) = e(aP,bQ) を比べれば、T が abP かを判定できます。
つまり積を直接作れなくても、積の関係が正しいかは検査できる。
KZG commitment が多項式の積・割り算の関係を短く検証できるのは、この性質のおかげです。
具体例 — 秘密を開けずに c = ab を検査する
verifier が受け取るのはスカラー a,b,c ではなく、点
aP、bQ、cP だけだとします。
左辺は「a と b の積」、右辺は「c」を、それぞれ同じ底
e(P,Q) の指数へ移します。
e(aP, bQ) = e(P,Q)ᵃᵇ
e(cP, Q) = e(P,Q)ᶜ
e(aP,bQ) = e(cP,Q) ⇔ ab ≡ c (mod q)
2 つの G_T の元が等しいか比較するだけなので、verifier は
a,b,c を知る必要がありません。これは「積を計算して見せる」のではなく、
隠された値の積の関係だけを等式で確かめる操作です。
したがって「ab を隠したまま、c と同じだと示せる」という理解でよいです。
ただし、ペアリング自体が a,b,c を暗号化したり、これだけで完全なゼロ知識証明になったりする
わけではありません。値が点の後ろに隠れて見えるのは、aP から a を戻す
離散対数問題が難しいと仮定しているためです。
なぜ ⇔ まで言えるか: 群の位数が素数 q で、非退化性により
e(P,Q) が位数 q の元になるため、指数が同じ mod q のときだけ両辺が一致します。
具体的にどこで使うか:
・KZG commitment — 秘密点 τ における多項式の割り算関係を、2 つの pairing 値の等式で検査する。
・BLS 署名 — 公開鍵とメッセージ、署名の間にある同じ秘密鍵 x の関係を検査する。
・pairing-based zkSNARK — 回路から作った多項式の積の関係を、少数の群要素と pairing で検査する。
共通しているのは、verifier が秘密スカラーや巨大な多項式を再計算せず、 公開された点どうしの pairing 等式だけを確認することです。 次の KZG の節では、このうち最初の用途を式まで展開します。
難しさの関係 — 見た目が弱い問題ほど注意
DLP を解いて a を取り出せれば、a·(bP)=abP として CDH も解け、
その結果と T を比べれば DDH も解けます。
DLP が解ける ⇒ CDH が解ける ⇒ DDH が解ける
ただし逆向きは自動ではありません。特にペアリングを持つ群では、 DDH の Yes/No は判定できても CDH は難しい、という設計がありえます。 したがってプロトコルを読むときは、単に「離散対数が難しい」ではなく、 DLP・CDH・DDH のどの仮定を本当に使っているかを確認します。
なぜ「難しさ」に頼れるのか
小さい群なら総当たりで解けます。位数 967 の曲線なら、最悪 967 回試せば当たります。 実用の曲線 secp256k1 は位数が約 2²⁵⁶ で、 総当たりの手数が宇宙の年齢を桁で超えるから安全とみなせる、という話です。
「解けない」ではなく「割に合わない」。暗号の安全性は、たいていこの形をしています。
前提 3
ここで、全体像の最後に出てきた「短い proof」を最小の形で作ります。
公開鍵 P = xG について「x を知っている」ことを、x を見せずに納得させます。
まず検証者が何を受け取り、どの式を確認するのかを固定します。
この 3 手が必要になる理由
公開鍵だけを見せても、誰でも同じ P を見ることができます。
しかし秘密鍵 x を見せると、秘密を守れません。そこで証明者は、毎回変える乱数
r で一度だけ使う点 R = rG を先に送り、検証者のチャレンジを受けてから
s = r + e·x を返します。検証者は x を知らなくても
sG = R + eP を計算できます。
ラボ 1 では、この式を「記号の説明」で終わらせず、r・e・s を実際の数にして両辺が同じ点になることを確認します。
証明者 検証者
r をランダムに選ぶ
R = rG ── R ──▶
◀── e ── e をランダムに選ぶ
s = r + e·x ── s ──▶ sG = R + eP を確認
完全性は 1 行で確かめられます。
sG = (r + e·x)G = rG + e·(xG) = R + eP。
正直に計算した s なら、検証式は必ず成り立ちます。
検証者が受け取る s = r + e·x には秘密 x が入っていますが、
ランダムな r が足されているので、s 単体からは何も分かりません。
Week 2 とまったく同じ構図です。Beaver 乗算で公開した
d = x − a が安全だったのは、a が誰も知らない乱数だったから。
ここでも r が s に含まれる秘密の値を毎回変える役割を持ちます。
そして Week 2 と同じく、使い回した瞬間に壊れます（後述）。
座標の計算は mod p、スカラー（指数）の計算は mod n（G の位数）。
1 つのコードに 2 つの法が同居します。
s = r + e·x の mod を p にした実装の採点結果です。
FAIL: test_honest_transcript_accepts (r=456, e=77) FAIL: test_honest_transcript_accepts (r=966, e=966) FAIL: test_honest_transcript_accepts (r=500, e=123) FAIL: test_nonce_reuse_leaks_secret AssertionError: 786 != 123
面白いのは、4 つのうち (r=1, e=0) のケースだけが通ることです。
e = 0 なら s = r = 1 で、どちらの法で丸めても 1 のまま。
法を間違えていても、値が法より小さければ表面化しません。
そして最後の 1 行——nonce 再利用の「攻撃」までもが失敗しています。
攻撃の式 x = (s₁−s₂)(e₁−e₂)⁻¹ も mod n の世界の話なので、
土台がずれると攻撃側も成立しなくなる。
正しい代数の上でしか、正しい壊し方もできない。
ラボ 1 の結果を言葉にする
ラボ 1 では、正直な証明者の会話も simulator の会話も受理されました。 ここで「通ったから秘密を知っている」と結論すると、論理が飛びます。 何を保証する性質なのかを、完全性・知識健全性・ゼロ知識に分けて確認します。
完全性 — completeness
正しい witness を持つ証明者は、必ず受理される。
sG = R + eP が代数的に恒等式になることで保証されます。
これが崩れると、正直な人が弾かれる（使いものにならない）。
知識健全性 — knowledge soundness
受理される proof を作れる者は、本当に witness を知っている。
証明の道具が抽出器（extractor）です。 証明者を巻き戻して同じ R のまま別のチャレンジ e′ を投げ、 2 つの応答 c, c′ を得られたなら、そこから x を計算して取り出せる—— 取り出せた以上、x は最初から証明者の中にあった、という論法です。
ゼロ知識 — zero-knowledge
記録を見ても、公開情報から説明できる範囲しか分からない。
道具は simulator。秘密を持たない simulator が、本物と見分けのつかない 会話を作れるなら、その会話に秘密由来の情報は入っていない、と言えます。 ラボの simulator モードがまさにこれです。
実測 — simulator の会話は本当に受理される
秘密 x を一度も使わず、順番を逆にして作った会話です
（先に e, s をランダムに選び、R := sG − eP と逆算する）。
x を使わずに作った会話: (R, e, s) = ((146, 214), 190, 284) 検証者はこれを受理するか: True
つまり「受理された会話が 1 本ある」ことは、何の証明にもなっていません。 本物と偽物の違いは中身ではなく順番だけ—— 本物は R を先に出し、そのあとでチャレンジを受け取る。 simulator はチャレンジを知ってから R を作る。
「証明者が先にコミットする」という順番が、健全性の全部を担いでいます。
抽出器と攻撃は、同じ 1 本の式
抽出器 ExtP* は、悪意のある証明者 P* を
その場で巻き戻してもう一度走らせる、知識健全性のための理論上の道具です。
まず同じコミットメント R = gr を受け取った直後にチャレンジ
e を送り、応答 s を記録します。次に、そこまで状態を戻して、
同じ R のまま別のチャレンジ e′ を送り、応答 s′ を記録します。
本物の証明者なら、どちらも次の形です:
s = r + e·x s′ = r + e′·x
s − s′ = (e − e′)·x ← 共通の r が消える
x = (s − s′)·(e − e′)⁻¹ (mod q)
ここで e ≠ e′ だから e−e′ は有限体で逆元を持ちます。
したがって抽出器は、証明者の内部を直接読むことなく x を計算できます。
「同じ R に対して別のチャレンジにも答えられるなら、秘密 x を知っているはずだ」
というのが、単なる“たまたま受理された”ことと知識の証拠を分けるポイントです。
小さな数で確認（mod 11）: r = 4, x = 3, e = 2, e′ = 7 s = 4 + 2·3 = 10 s′ = 4 + 7·3 = 25 ≡ 3 x = (10−3)·(2−7)⁻¹ = 7·6⁻¹ = 7·2 ≡ 3
これが抽出器の中身であり、そのまま nonce 再利用攻撃の中身でもあります。 ただし抽出器は安全性を証明するために巻き戻す仮想的な存在で、 攻撃者は実際の署名で同じ R が偶然再利用されたときにこの計算をします。
仕上げ
ラボ 1 とラボ 2 では、検証者がチャレンジ e を返す 3-way の対話を使いました。 ここでは「検証者が毎回ランダムに e を選ぶ」という役割だけをハッシュに移し、 対話なしで同じ検証式を使えるようにします。
検証者の仕事はランダムなチャレンジ e を選ぶことだけでした。 ならば、ここまでの会話のハッシュで e を作ってしまえばよい。
e := H(ctx, G, P, R)
R は公開されるので、検証者も同じ e を自分で計算できます。往復が消え、 proof は 1 通（R, s）で完結します。
さらにハッシュの入力にメッセージ m を混ぜると、
e = H(ctx, G, P, R, m) となり、
(R, s) はそのまま m への署名になります。これが Schnorr 署名で、
Bitcoin の BIP-340 や Ed25519 がこの系統です。
課題では challenge_hash(R, pubkey, message, n) が与えられ、
署名側と検証側の両方が、同じ引数で e を計算し直す作りになっていました。
実測 — ハッシュの引数の順番を入れ替えただけ
challenge_hash(R, pubkey, ...) を
challenge_hash(pubkey, R, ...) と取り違えた実装です。
FAIL: test_sign_vector AssertionError: 7765...5734 != 9434...3357 : s = nonce + e*x mod n のはずです。e は challenge_hash(R, pubkey, message, curve.n) で計算します。 引数の順番(R が先、pubkey が後)も確認してください FAIL: test_roundtrip
面白いのは、これが「動く」ことです。署名側と検証側が同じ順番で間違えていれば、 自分の署名は自分で検証できてしまう（roundtrip が落ちたのは、 テストが用意した正しい公開鍵と噛み合わなかったため）。 ハッシュへの入力の並びは、相互運用の仕様そのもので、 自己検証だけでは正しさを確認できません。
ctx に何を入れるか
プロトコル名・曲線の種類・証明したい statement といった文脈情報を入れます。
同じ形の署名が、別の文脈で使い回されるのを防ぐためです。
「何をハッシュに入れ忘れたか」が、そのまま脆弱性になります。 メッセージを入れ忘れれば署名は付け替え放題、 公開鍵を入れ忘れれば別人の鍵で通る余地が生まれます。
元の 3-way 会話と、Bitcoin での利用
元の Schnorr は 3-way の対話です。証明者が R を送り、
verifier がランダムなチャレンジ e を返し、証明者が
s = r + e·x を返します。Fiat–Shamir は、この中央の verifier の一手を
e = H(ctx, 公開鍵, R, メッセージ) に置き換え、会話を 1 通の署名にします。
Bitcoin ではこの考え方を使う Schnorr 署名が Taproot の署名方式 （BIP-340）として使われます。つまり Bitcoin が毎回 3-way 通信をしているのではなく、 ハッシュでチャレンジを決めた非対話版を、取引の署名として検証している、という意味です。 同じ R を二度使わないことと、ハッシュの入力順・文脈を全員で一致させることが安全性の前提です。
スライド後半との接続
課題で実装したのは、パイプラインの右端にある「秘密を見せずに関係を検証する」部分です。 残りの箱は Week 4 以降で手を動かします。ここでは、課題の計算がどこへ接続するかを説明します。
f(X) = 3X² + 2X + 5 は、係数の並び (5, 2, 3) としても、
いくつかの点での値の並び (f(x₀), f(x₁), f(x₂)) としても持てます。
次数 d の多項式は、異なる d+1 点での値が決まれば一意に決まるので、
この 2 つは同じ情報です。
なぜ多項式にするのか: 制約が何万本あっても、まとめて 1 本の多項式の等式にできるから。 そしてランダムな 1 点で値を比べるだけで、全体が一致しているかをほぼ確実に判定できる。 検証が「短く」なる仕掛けの中心がこれです。
評価する点を 1 の n 乗根の冪 {1, ω, ω², …} に揃えておくと、
係数表現と評価表現の変換が規則的になります。これが有限体上のフーリエ変換で、
素朴には O(n²)、FFT なら O(n log n)。
速くなる理由は、係数を偶数番目と奇数番目に分けると見えます。
f(X) = 1 + 2X + 3X² + 4X³ なら、
E(Y) = 1 + 3Y O(Y) = 2 + 4Y
f(X) = E(X²) + X·O(X²)
f(−X) = E(X²) − X·O(X²)
X と −X は二乗すると同じなので、
E(X²) と O(X²) を 1 回計算し、足し算と引き算で 2 点の答えを同時に作れる。
この A+B / A−B の合流を butterfly と呼びます。
同じ分割を半分、さらに半分と続けるため、段数は log₂n、
各段の仕事は n 個ぶんになり、全体が O(n log n) になります。
手計算 — F₁₇ の 4 点 FFT
mod 17 では ω = 4 とすると
4² = 16 ≡ −1、4⁴ ≡ 1。
したがって評価点は {1, 4, 16, 13} です。
係数: (1, 2, 3, 4) E(1) = 1 + 3 = 4 O(1) = 2 + 4 = 6 E(−1) = 1 − 3 ≡ 15 O(−1) = 2 − 4 ≡ 15 (mod 17) f(1) = E(1) + 1·O(1) = 4 + 6 = 10 f(16) = E(1) − 1·O(1) = 4 − 6 ≡ 15 f(4) = E(−1) + 4·O(−1) = 15 + 4·15 ≡ 7 f(13) = E(−1) − 4·O(−1) = 15 − 4·15 ≡ 6 評価表現: (10, 7, 15, 6)
直接 4 回代入しても同じ値になります。FFT は答えを変える技法ではなく、 同じ部分計算を使い回して評価する技法です。
Week 3 の土台がここにも効きます。逆変換に出てくる 1/n は
n の逆元、ω は位数 n の元——どちらも土台編の言葉そのままです。
すべての ZKP が FFT を中心にするわけではありません。PLONK や STARK/FRI などは、
主に一変数多項式を {1, ω, ω², …} 上で扱うため FFT/NTT が重要です。
一方、Spartan や Jolt などの系統では、各変数の次数が高々 1 の多重線形多項式と
sumcheckを中心に置きます。
一変数ルート: f(X) の係数 ⇄ FFT ⇄ 評価値
多変数ルート: f(x₁,…,xᵥ) を {0,1}ᵛ 上で持つ → sumcheck で 1 変数ずつ固定
たとえば 8 個の値は、次数 7 の一変数多項式としても、
3 変数の f(x₁,x₂,x₃) としても表せます。後者では
xᵢ ∈ {0,1} の 8 通りが元の表に対応します。
H = Σ[x₁∈{0,1}] ··· Σ[xᵥ∈{0,1}] g(x₁,…,xᵥ)
2ᵛ 点の合計を、ランダムな r₁,…,rᵥ を使って g(r₁,…,rᵥ) 1 点の確認へ縮める
各ラウンドで 1 変数をランダム値へ固定すると、持っている評価表も
2ᵛ → 2ᵛ⁻¹ → … → 1 と半分ずつ畳まれます。
Jolt はこの multilinear extension と sumcheck、lookup を中核にして
RISC-V プログラムの実行を証明する zkVM です。
「最近の ZKP は FFT を使わない」の正確な読み方: FFT が廃れたのではなく、一変数多項式＋FFT とは別に、multilinear＋sumcheck を選ぶ設計が伸びている。 さらに polynomial commitment の選択によっては、sumcheck 系のシステム全体にも FFT 的な符号化処理が入るため、「絶対に FFT がない」とまでは言えません。
大きな対象（多項式や実行トレース）を短い値 c に固定して先に渡し、
後から中身と必要な情報を示す。必要な性質は 2 つ。
binding: 開けるのは最初に入れたものだけ
hiding: 開くまで、相手が持っているのは c だけ
手順は commit → open → verify の 3 段階です。証明者は値 m と、毎回新しく選ぶ
乱数 r から c = Com(m; r) を計算し、まず c だけを渡します。後で全文を開くなら
(m,r) を渡し、検証者が同じ計算をやり直して
Com(m;r) = c になるか確かめます。
commit: m と乱数 r を選ぶ → c = Com(m;r) だけを渡す
open: m,r を渡す
verify: 受け取った m,r から Com(m;r) を再計算し、保存していた c と比較する
たとえばハッシュ型なら、証明者が m = 42、r = 9187… を選び、
c = Hash("42" || r) を先に送ります。開くときに 42 と r を見せれば検証できます。
途中で m を 43 に変更すると同じ c を作れない、というのが binding です。
代表例 — Hash commitment:
c = Hash(m) とすれば、別の m′ ≠ m で同じ c を作るのが難しいという
ハッシュの第二原像困難性・衝突困難性が binding を支えます。
しかし m が「Yes/No」や 4 桁の暗証番号なら、検証者は全候補をハッシュして c と比較できるため、
Hash(m) だけでは hiding になりません。
弱い形: c = Hash(m) 候補が少ない m は総当たりできる
隠す形: c = Hash(domain || r || m) 十分長いランダムな r で候補空間を広げる
open では (m,r) を渡し、検証者は同じ順序・同じ符号化でハッシュを再計算します。
domain は「これは何の commitment か」を表す固定文字列です。値の連結方法が曖昧だと、
(1,23) と (12,3) のような取り違えが起きるので、実装では長さ付き符号化も必要です。
ハッシュなら c = Hash(r, m)（乱数 r を混ぜないと、候補が少ないとき総当たりで中身が割れる）。
Week 1 のノートで出てきた「箱」が、ここで正式な道具として戻ってきます。
注意: open は「封を破ってサーバーから元データを取得する」という操作ではありません。 証明者が、検証に必要な情報を後から渡す操作です。通常の commitment は m 全体を見せますが、 polynomial commitment は多項式全体を見せず、指定した 1 点の値と短い opening proof だけを渡せます。
KZG は、Groth16 や一部の PLONK 系などで使われる多項式 commitmentです。 zkSNARK が作った巨大な多項式を 1 個の曲線上の点へ圧縮し、検証者が多項式全体を 読まなくても、必要な評価値や多項式どうしの関係を短く検査できるようにします。
秘密のスカラー τ に対する SRS = (P, τP, τ²P, …, τᵈP; Q, τQ) を公開しておくと、
係数を掛けて足すだけで C = f(τ)P が作れます（τ を誰も知らないまま）。
setup: 秘密 τ を選ぶ → τ の累乗を掛けた点だけを SRS として公開 → τ 自体は消去
commit: f(X)=a₀+a₁X+…+a_dXᵈ → C=a₀P+a₁(τP)+…+a_d(τᵈP)=f(τ)P
この commit 計算は、係数の列 (a₀,a₁,…,a_d) と SRS の点の列
(P,τP,…,τᵈP) を、同じ位置どうしで掛けて全部足す形です。
そのため「内積のような計算」と説明されます。ただし結果は数ではなく曲線上の点なので、
正確には MSM（multi-scalar multiplication、複数スカラー倍の和）です。
なぜこの組合せなのか: 多項式へ τ を代入する普通の計算を、そのまま点 P の上で行うためです。
SRS の P,τP,τ²P,… は、それぞれ多項式の
1,X,X²,… の代理になっています。
f(X) = 2 + 3X + 4X²
普通に τ を代入: f(τ) = 2 + 3τ + 4τ²
点の代理で計算: C = 2P + 3(τP) + 4(τ²P)
= (2 + 3τ + 4τ²)P = f(τ)P
証明者は τ 自体を知らなくても、公開された点を 2 倍、3 倍、4 倍して足すことはできます。 こうして、何個もある係数を固定サイズの点 C 1個へまとめられます。 内積を使いたいことが出発点なのではなく、多項式への代入を、τを隠したまま実行した結果が この内積の形になる、という順番です。
KZG のすごいところ:
τ の値を知らなくても「f に τ を代入する計算」に対応する点を作れます。
ただし手に入るのは数 f(τ) そのものではなく、点 f(τ)P だけです。
離散対数が難しいため、f(τ)P から f(τ) や τ を読み戻すことはできません。
つまり、秘密の値を読めないまま、その値を使った計算結果を作って検証に利用できるのが核心です。
SRS は「τ は見せず、τ を使った計算だけできる公開部品」です。τ が分かれば偽の opening proof を 作れるため、生成後の τ は toxic waste と呼ばれ、必ず消去する必要があります。 実際には複数人が秘密を順番に混ぜる MPC ceremony を行い、少なくとも 1 人が自分の秘密を 正しく消去すれば、最終的な τ を誰も知らない状態にします。
f(z) = y を示す → q(X) = (f(X) − y)/(X − z) を作り、π = q(τ)P を出す
検証: e(C − yP, Q) = e(π, τQ − zQ)
KZG で「点 z を open する」とき、証明者は多項式 f 全体や秘密 τ を渡しません。
代わりに 評価値 y = f(z) と、割り算の商を圧縮した
opening proof π = q(τ)P を渡します。検証者が受け取るのは
(z,y,π) です。
証明者: f(z) を計算して y とし、q(X) = (f(X)−y)/(X−z) から π を作る
検証者: commitment C、公開点 z、主張された値 y、proof π を上の pairing 式へ入れる
等式が成立 → 「C に固定された多項式は、z で確かに y」を受理する
なぜこれで開けたことになるかというと、f(X)−y が X−z で割り切れるのは
f(z)=y のときだけだからです。π はその割り切れた証拠を 1 個の点へ
圧縮したものです。つまり KZG の open は「中身を全部公開」ではなく、
質問された 1 点だけを、短い証拠つきで公開する操作です。
ここが KZG の中心 — 余りの定理:
多項式 f(X)−y を X−z で割った余りは f(z)−y です。
したがって f(z)=y なら余りは 0 になり、必ず商多項式 q が存在して
f(X)−y=q(X)(X−z) と書けます。逆にこの式が成り立つなら、X=z を代入して
f(z)−y=0 です。
例: f(X)=X²+3X+2、z=2 なら y=f(2)=12
f(X)−12 = X²+3X−10 = (X−2)(X+5)
よって q(X)=X+5。この「割り切れた」という事実が opening proof の材料になる。
検証時には秘密 τ を式へ入れた
f(τ)−y=q(τ)(τ−z) を確認したいのですが、誰も τ や各スカラーを知りません。
左側は commitment から C−yP、商は proof π=q(τ)P、
残りは SRS から τQ−zQ として点のまま作れます。最後にペアリングが
q(τ) と τ−z の積の関係を比較します。
e(C−yP,Q)
= e((f(τ)−y)P,Q)
= e(q(τ)(τ−z)P,Q)
= e(q(τ)P,(τ−z)Q)
= e(π,τQ−zQ)
何がすごいか: verifier は f も q も τ も受け取りません。 commitment C と点 z、答え y、曲線上の点 π だけで確認できます。 f の次数が大きくなっても C と π はそれぞれ点 1 個のままなので、証明が定数サイズになります。
具体例 — f(X)=X²+1 について f(2)=5 を開く
問題: SRS に P,τP,τ²P と Q,τQ があるとします。
f(X)=X²+1 を commit し、z=2 で
y=5 になることを示す commitment C、商 q、proof π を作り、検証式を確かめてください。
Step 1 — commit
C = 1·P + 0·(τP) + 1·(τ²P) = τ²P + P = (τ²+1)P
係数ベクトルは (1,0,1) です。証明者は τ を知らなくても、SRS にある
P と τ²P を足すだけで C を作れます。
Step 2 — 商と opening proof
q(X) = (f(X)−5)/(X−2)
= (X²−4)/(X−2) = (X−2)(X+2)/(X−2) = X+2
π = q(τ)P = (τ+2)P = τP+2P
X²−4 を見たら、平方差の公式
X²−2²=(X−2)(X+2) を使うのが式変形のポイントです。
Step 3 — pairing で検証
左辺 = e(C−5P,Q)
= e((τ²+1−5)P,Q) = e((τ²−4)P,Q)
右辺 = e(π,τQ−2Q)
= e((τ+2)P,(τ−2)Q)
= e(P,Q)^(τ+2)(τ−2) = e(P,Q)^(τ²−4)
左辺も右辺も e(P,Q)^(τ²−4) になったので検証は通ります。
これは単に「式が同じで気持ちよい」という話ではありません。
左辺は最初に固定した f と主張 y から作られ、右辺は割り切れた証拠 π から作られています。
両者の一致により、「後から都合のよい多項式へ変えず、最初の C に固定した f は本当に f(2)=5」
という関係を確認できました。
一致すると何がすごいのか:
verifier は τ の値も、多項式 f の全係数も、商 q の全係数も知りません。
それでも C と π という点 2 個を中心に、巨大な多項式の一点評価を検証できます。
多項式が 2 次から 100 万次になっても、commitment と opening proof の大きさは点 1 個ずつです。
間違った答えなら: たとえば f(2)=6 と嘘をつくと、
X²+1−6=X²−5 は X−2 で割り切れず余りが −1 になります。
正しい商 q が存在しないため、対応する π で左右を一致させることはできません。
割り切れることが、f(z) = y と同値。そして「積の関係」を点だけで確かめるために
ペアリングが要ります。aP と bP から足し算で作れるのは
(a+b)P まで——積 abP には手が届かないので、
スカラーを指数へ移せる双線形写像を持ち込む、という筋道です。
KZG とゼロ知識は同じものではない: KZG の中心的役割は、多項式を短く固定して正しい評価を検査できるようにすることです。 通常の KZG commitment は binding ですが、それだけで多項式を完全に hiding するとは限りません。 zkSNARK では、証明に使う多項式へランダムな blinding 項を加えるなど、別の工夫と組み合わせて witness が漏れないようにします。つまり KZG はゼロ知識証明を支える部品であって、 KZG 単体がゼロ知識証明なのではありません。
ゼロ知識証明で最初にあるのは、公開する statement x と、秘密にする
witness w、そして両者の関係を判定するルール R です。
目標は「w は見せないが、R(x,w)=1 となる w を知っている」と証明することです。
ここでの R は relation（関係）の頭文字で、楕円曲線上の点 R とは別物です。
x: 公開 statement 例「答えは 15」
w: 秘密 witness 例「秘密の入力は 2」
R(x,w): w をプログラムへ入れた結果が x と一致するか判定するルール
しかし検証プロトコルは、一般的なプログラムの if 文やループをそのまま扱えません。
そこで値を有限体 𝔽p の要素に写し、計算途中の値を wire として並べ、
正しい実行ならすべて 0 になる足し算・掛け算の等式へ翻訳します。これが
arithmetization（算術化）です。
ひと言でいうと: arithmetization は、プログラムをゼロ知識証明用の数式へコンパイルすることです。 「入力から答えを計算する手順」を、「入力・途中値・答えが互いに矛盾していないか判定する条件」へ 読み替えます。
「R を有限体で表す」とは:
R そのものを 1 個の数字へ変換するのではありません。
R(x,w)=1 となる条件を、有限体上の制約
constraint₁=0, constraint₂=0, … の集まりとして書くことです。
Week 1 でやったことが、ここに戻ってきます。 制約は「0 になる式」に揃え、掛け算 1 個ずつに分解する（R1CS）。
w³ + w + 5 = y を分解する
t₁ ← w·w t₂ ← t₁·w y ← t₂ + w + 5
↓ 制約として読む
t₁ − w² = 0 t₂ − t₁w = 0 t₂ + w + 5 − y = 0
具体例 — 3 次方程式の解を知っていると証明する。
公開 statement を「w³+w+5=15 を満たす解がある」とし、公開値は
y=15、秘密 witness はその解 w=2 とします。関係は
R(y,w)=1 ⇔ w³+w+5=y です。途中値として
t₁=4、t₂=8 を置きます。
なぜ「制約として読む」のが大事なのか:
普通の計算 c=a+b は、a,b を知っている人が c を作るための命令です。
制約 a+b−c=0 は、すでに並んだ a,b,c が正しい関係にあるかを答え合わせする式です。
ZKP の verifier は秘密 a,b を受け取らず計算を再実行できないので、後者の形が必要です。
計算として読む: a=2, b=3 を入れる → c=5 を作る
制約として読む: (a,b,c)=(2,3,5) を候補として置く → 2+3−5=0 なので整合
(a,b,c)=(2,3,8) なら 2+3−8≠0 なので不正
もちろん verifier が秘密値を直接代入して一本ずつ確認するわけではありません。 prover が「全制約を満たす値を持つ」ことを、多項式 commitment やランダム検査を使って短い proof にします。 しかしその proof の土台は、正しい実行なら全制約が0、不正な実行なら少なくとも一つが0でない という形へ揃えたことです。
① t₁−w·w = 4−2·2 = 0
② t₂−t₁·w = 8−4·2 = 0
③ t₂+w+5−y = 8+2+5−15 = 0
これで何が保証されるか: prover は w を公開しませんが、すべての wire を矛盾なく埋められることを証明します。 verifier は公開値 y=15 と制約、そしてそこから作られた proof を見て、 「この 3 本を同時に成立させる秘密 w を prover が知っている」と確認できます。 逆に途中値を一つでもごまかすと、どれかの等式が 0 になりません。
「解を見せずに」の意味:
実際の ZKP で prover が (w,t₁,t₂)=(2,4,8) を verifier へそのまま送るわけではありません。
これらを witness として証明アルゴリズムへ入力し、「3 制約を同時に満たす」という短い proof だけを渡します。
verifier は解 2 を知らないまま、その解を使えば公開値 15 に到達することを検証します。
不正な例: w=1 とすると t₁=1, t₂=1 までは整合するが、
③ 1+1+5−15 = −8 ≠ 0
途中値を変えて③だけ合わせれば、今度は①か②が壊れる。3 本を同時には満たせない。
R1CS の線形結合 — 係数を並べただけ
R1CS では、使う値を毎回同じ順序のベクトルへ並べます。先頭の 1 は定数項を作るための枠です。
この例では z=(1,y,w,t₁,t₂) とします。正しい witness を入れると
z=(1,15,2,4,8) です。
3 本目の制約 t₂+w+5−y=0 の左辺を作りたいなら、それぞれの枠に掛ける係数を
同じ順番で (5,−1,1,0,1) と並べます。
変数の順番: ( 1, y, w, t₁, t₂ )
係数の順番: ( 5, −1, 1, 0, 1 )
掛けて足す: 5·1 −1·y +1·w +0·t₁ +1·t₂
= 5−15+2+0+8 = 0
「線形結合」とはこれだけ:
各値を定数倍して足した式です。係数 0 は「この変数を使わない」という意味です。
先頭に 1 があるため、定数 5 も 5·1 として同じ形式で扱えます。
R1CS の 1 本は、3 個の線形結合を使って
(A·z)(B·z)=C·z という「左 × 右 = 出力」の形にします。
先ほどの3制約は次のように書けます。
① w·w=t₁ → (w)(w)=t₁
② t₁·w=t₂ → (t₁)(w)=t₂
③ t₂+w+5−y=0 → (t₂+w+5−y)(1)=0
①なら A は w だけを選び、B も w だけを選び、C は t₁ だけを選びます。
③では A が係数列 (5,−1,1,0,1)、B が先頭の 1 だけ、C は全部 0 です。
難しそうな行列 A,B,C は、この係数列を制約の本数だけ縦に並べたものにすぎません。
なぜわざわざベクトルにするのか: すべての制約を同じデータ形式へ揃えると、何万本あっても行列演算として一括処理でき、 その先で多項式へ変換して短い proof に圧縮できるからです。
3 本を行列にまとめる
各制約の「左の係数」を A、「右の係数」を B、「出力の係数」を C の各行へ入れます。
z=(1,y,w,t₁,t₂) の順番を変えないことが重要です。
1 y w t₁ t₂
A = [ 0 0 1 0 0 ] ← ①の左: w
[ 0 0 0 1 0 ] ← ②の左: t₁
[ 5 −1 1 0 1 ] ← ③の左: 5−y+w+t₂
B = [ 0 0 1 0 0 ] ← ①の右: w
[ 0 0 1 0 0 ] ← ②の右: w
[ 1 0 0 0 0 ] ← ③の右: 1
C = [ 0 0 0 1 0 ] ← ①の出力: t₁
[ 0 0 0 0 1 ] ← ②の出力: t₂
[ 0 0 0 0 0 ] ← ③の出力: 0
まず数値を入れず、記号のまま行列を掛けると、各行が元の式の必要な部分を取り出していることが分かります。
Az = (w, t₁, t₂+w+5−y)
Bz = (w, w, 1)
Cz = (t₁, t₂, 0)
(Az)∘(Bz)=Cz
⇔ (w·w, t₁·w, (t₂+w+5−y)·1) = (t₁,t₂,0)
ベクトル等式の各成分を読むと、元の
w·w=t₁、t₁·w=t₂、t₂+w+5−y=0
の3本へそのまま戻ります。行列へ変えても制約の意味は失われていません。
正しい値 z=(1,15,2,4,8) を掛けると、行列の各行が担当する線形結合を
一度に計算できます。
Az = (2, 4, 0) ← 各制約の左側
Bz = (2, 2, 1) ← 各制約の右側
Cz = (4, 8, 0) ← 各制約の出力
最後に同じ位置どうしを掛けます。これは普通の行列積ではなく、Hadamard積
∘（成分ごとの積）です。
(Az) ∘ (Bz) = (2·2, 4·2, 0·1) = (4,8,0) = Cz
これが大事な理由:
第1成分の等式は第1制約、第2成分は第2制約、第3成分は第3制約にそのまま対応します。
したがってベクトル等式 (Az)∘(Bz)=Cz が成り立つことは、
3本すべてが同時に正しいことを意味します。制約が100万本でも形式は同じです。
この規則的な表にできたことで、次は各列を多項式として扱い、大量の制約を少数の
多項式等式へ圧縮できます。
なぜベクトルで扱いたいのか:
① 形式を統一できる — 掛け算、足し算、定数を含む式を、すべて係数の行として保存できる。
② 一括処理できる — 1本ずつ式を解釈せず、全制約を Az,Bz,Cz でまとめて計算できる。
③ 多項式へ渡せる — 各行の計算結果を評価値の表と見なし、補間して多項式へまとめられる。
④ 短い検証へ圧縮できる — 最終的に「全成分が正しい」を少数の多項式関係と commitment で検査できる。
表計算で、列の並びを固定すれば何万行でも同じ式を適用できるのと似ています。 ベクトル化は証明そのものではなく、大量のバラバラな制約を、後段の多項式処理が読める 規則的な表へ変える中間形式です。
「次数下げ」という理解でよい？:
かなり近いです。たとえば w³ を直接扱わず、t₁=w²、
t₂=t₁w と中間変数を増やし、各制約の掛け算を1個にします。
高次数の式を二次の制約へ分解した代わりに、変数と制約の本数は増えます。
元の計算結果を求めること自体が速くなるのではなく、証明システムにとって規則的で扱いやすくなります。
Groth16 とのつながり: Groth16 は算術回路の充足可能性を証明する pairing-based SNARK です。一般的な説明・実装では、 計算を R1CS にし、そこから QAP（多項式の関係）へ変換して証明を作ります。 ここで作った行列形式は、Groth16 が扱う多項式へ進むための入口です。 最終的な proof は3個の群要素という非常に短い形になります。
足し算と掛け算は有限体で直接扱えます。一方、大小比較、ビット演算、範囲、if 文はそのままでは
有限体の演算ではないので、ビット b に b(b−1)=0 を課すなど、
追加の制約へ分解します。したがって、同じ処理でも書き方によって制約数が変わり、
zk アプリケーションの証明時間にも直結します。
AIR — 計算を「時間 × 変数」の表として見る
AIR（Algebraic Intermediate Representation）も arithmetization の一種です。 R1CS が計算を掛け算ゲートの集合として並べるのに対し、AIR は実行の各ステップを1行に記録した execution trace（実行トレース）を作ります。列が状態変数、行が時間です。
なぜわざわざ表にするのか: verifier が長い計算を最初から再実行すると、証明を使う意味がありません。 表にすると正しさを「初期状態は正しいか」と「各行から次の行への1ステップは正しいか」という 局所的で同じ形の検査へ変えられます。実行全体の監査ログを作るイメージです。
例として、初期状態 (a₀,b₀)=(0,1) から
(aᵢ₊₁,bᵢ₊₁)=(bᵢ,aᵢ+bᵢ) と更新する計算を考えます。
step | a | b -----+---+--- 0 | 0 | 1 1 | 1 | 1 2 | 1 | 2 3 | 2 | 3
正しさは、最初の行を縛る境界制約と、隣の行との関係を縛る 遷移制約で表します。すべて「0になる式」にします。
境界制約: a(0)=0、b(0)−1=0
遷移制約: a(i+1)−b(i)=0
b(i+1)−a(i)−b(i)=0
境界制約がないと何が困るか:
遷移制約だけでは、「隣り合う行がフィボナッチの規則に従う」ことしか分かりません。
たとえば (a₀,b₀)=(10,20) から始めた
(10,20)→(20,30)→(30,50) も遷移制約は完全に満たします。
しかし、証明したかった (0,1) から始まる計算ではありません。
開始の境界: 最初の行 = 公開入力
終了の境界: 最後の行の指定セル = 公開出力
遷移制約: その間のすべての隣接行が実行規則に従う
つまり境界制約は、表の両端を検証したいstatementへ固定します。 ここでいう「クエリが正しい」は、たとえば「この入力からこの出力になったか」という 公開statementが、先頭行と最終行へ正しく結び付いていることです。 境界と遷移の両方が揃って初めて、意図した入力から始め、正しい手順を通り、 意図した出力へ到達したといえます。
たとえば step 1 から 2 への遷移は、
a(2)−b(1)=1−1=0、
b(2)−a(1)−b(1)=2−1−1=0 なので正しい。
一箇所を (1,9) のように改ざんすると、前後どちらかの遷移制約が壊れます。
でも全行を調べたら結局重いのでは？: その通りなので、表を作るだけではまだ速くなりません。次に各列を低次数多項式として表し、 表全体をcommitします。commit後にランダムな場所を選ばれるため、prover は検査箇所以外だけを ごまかす準備ができません。少数の問い合わせと低次数検査で、全行が規則に従うことを 高い確率で検査できるところまで進んで、初めてSTARKの短い検証になります。
長い計算をそのまま検証 → verifier も全ステップ再実行して重い
計算を表にする → 同じ局所ルールへ統一できる
表を多項式化・commit → 後からランダムに少数箇所を検査できる
AIR の大事な点: 100万ステップ実行しても、繰り返す遷移規則の記述は同じ2本です。 行数は増えますが、「次の状態は前の状態から正しく作られたか」という同じ局所ルールで 実行全体を縛れます。CPUやVMの長い実行ログを証明するSTARK系と相性がよい理由です。
AIR は STARK で使われる: STARK では、プログラムの実行をまず AIR の表と制約へ翻訳します。次に各列を低次数多項式へ変え、 Merkle tree で commitし、FRIで「本当に低次数か」を検査します。
program
→ execution trace（実行表）
→ AIR（境界制約・遷移制約）
→ trace / constraint polynomials
→ Merkle commitment + FRI
→ STARK proof
AIR が「正しい実行なら満たすべき規則」を定め、FRI が「その規則から作った多項式が 不自然に高い次数ではない」と短く検査する、という役割分担です。 STARK の S は scalable、T は transparent で、KZGのような秘密 τ を使う trusted setup を必要としません。
実際の verifier は表を全部読むの？: 素朴には全行を確認できますが、それでは実行をやり直すのと同程度に重くなります。 実際のSTARKでは各列を多項式へ拡張してcommitし、ランダムに選んだ少数の位置と FRIなどの低次数検査で、表全体が規則に従うことを高い確率で確認します。
R1CS: 計算 → ゲートごとの制約 → 行列 A,B,C
AIR: 計算 → 時系列の表 → 境界制約・遷移制約
共通点: 正しい計算を、有限体上で0になる多項式関係へ翻訳する
Arithmetization は1種類ではない — 4方式の特徴
R1CS、AIR、Plonkish、CCS は、いずれも「正しい計算」を有限体上の制約へ翻訳するための 中間表現です。証明したい内容は同じでも、どこに規則性を見つけて並べるかが違います。 arithmetization と proof system は別レイヤーなので、方式名だけで trusted setup の有無や ゼロ知識性が自動的に決まるわけではありません。
R1CS — 掛け算1個を基本単位にする
1制約: (Aᵢz)(Bᵢz)=Cᵢz
全体: (Az)∘(Bz)=Cz
どんな式も中間変数を入れて「線形結合×線形結合＝線形結合」へ分解します。 定義が単純で、R1CSからQAPへ変換するGroth16系の説明でよく登場します。 一方、ビット演算、範囲検査、ハッシュ、楕円曲線演算などをすべて基本ゲートへ砕くと、 制約数が大きくなることがあります。
得意: 小さな算術回路、単純で固定的な回路、Groth16/QAPへの入力
コストを見る単位: 何本のrank-1制約へ分解したか
AIR — 時間方向に繰り返す状態遷移を見る
各時刻のレジスタを実行トレースの1行にし、開始・終了を境界制約、隣接行の更新を遷移制約で縛ります。 同じ命令規則を長い実行へ繰り返し適用できるため、CPU、VM、反復計算の証明と相性がよく、 STARKで中心的に使われます。コストは主にトレースの幅・長さ、制約の次数に左右されます。
得意: 長い実行ログ、VM/CPU、反復的な状態機械、STARK
コストを見る単位: trace幅 × trace長、遷移制約の数と次数
Plonkish — wire、gate、selectorを表に並べる
各行に wire値 a,b,c を置き、selector
qL,qR,qM,qO,qC が、その行で使うゲートを選びます。基本形は次です。
qL·a + qR·b + qM·a·b + qO·c + qC = 0
足し算行: qL=1,qR=1,qM=0,qO=−1,qC=0
掛け算行: qL=0,qR=0,qM=1,qO=−1,qC=0
selectorを変えるだけで同じ表に異なるゲートを置けます。さらにcustom gateで、頻出する複雑な処理を 1行へまとめたり、lookup argumentで範囲検査や既知の対応表を効率よく確認したりできます。 別の行に現れた同じwireが等しいことはpermutation/copy constraintで保証します。 PLONK、Turbo/UltraPLONK、Halo2などの系統で見られる柔軟な設計です。
得意: custom gate・lookupを多用する回路、回路を頻繁に改善する実装
コストを見る単位: 行数、列数、gate次数、copy制約、lookup数
CCS — 線形結合の積を足し合わせる一般形
CCS（Customizable Constraint Systems）は、複数の行列 Mⱼ から作る線形結合
Mⱼz を、成分ごとに掛け、その結果を係数付きで足して0にする形です。
Σᵢ cᵢ · ( ∘[j∈Sᵢ] Mⱼz ) = 0
R1CSなら「2個の線形結合の積−1個の線形結合」、Plonkishならselector付きの複数項、 AIRなら現在行・次行を含む多項式制約として、この一般形へ埋め込めます。 CCSはR1CS・Plonkish・AIRを共通の記法で扱い、特にHyperNovaのようなfolding/IVC （計算を継続的・再帰的に畳む証明）で使われます。抽象度が高い分、最初の学習や手計算はR1CSより難しくなります。
CCSが「強い」と言われる意味: ここでの強さは主に表現力と一般性です。R1CSのような「積1個」だけでなく、 複数の線形結合の積や、それらの和を1個の制約へ直接書けます。また異なる制約形式を同じCCSの folding手順へ載せられます。ただし、すべての計算でCCSが最速・最小になるという意味ではなく、 専用のPlonkish gateやAIRの方が単純で効率的な場合もあります。
得意: 異なるゲートを共通形式で扱う、folding、IVC、再帰証明
コストを見る単位: 行列の非零要素数、積に含める項数・次数、foldするinstance数
どれを選べばよい？
Groth16で小さく固定した回路を証明 → R1CS/QAP が自然
VMの長い実行をSTARKで証明 → AIR が自然
custom gateやlookupを活用したSNARK → Plonkish が自然
foldingで段階的・再帰的に計算を畳みたい → CCS が有力
「最も強い方式」が一つあるわけではありません。同じ計算でも、ある方式では1個のcustom gate、 別の方式では何十本もの基本制約になることがあります。よいarithmetizationとは、証明したい計算の 繰り返し・表・lookup・再帰といった構造を、少ない制約と低い次数で表せる並べ方です。
R1CS は (Az) ∘ (Bz) = Cz の形にまとまります。
並べ方は他にもあって、AIR は実行トレースの表を「隣り合う行の規則」で縛る方式
（行が増えても制約の記述量は変わらない）。
見た目は違っても、どれも計算の正しさを有限体上の制約として扱っている点は同じです。
一文でまとめると
zkSNARK は、公開 statement に対して秘密 witness が存在することを、 計算を制約と多項式へ翻訳し、commitment で短く固定して、 短い proof として検証できるようにする仕組み。
今週作った Schnorr は、この文の「短い proof」と「対話を消す」部分を、 いちばん小さい形で全部持っている実例でした。
グループワーク — 数独ZKP
課題は、数独の完成盤を見せることではありません。 prover は解を知っているが、verifier には解そのものを見せずに、 正しい解を知っていると納得させる手順を、班で設計します。 最初は暗号計算を使わず、トランプや紙カードだけで実行できる形にします。
まず紙に固定するもの
「相手にプロトコルを紙で渡す」とは、答えを渡すことではなく、 第三者がその紙だけを読んで同じ手順を再現できる仕様書を渡すという意味です。
紙カードでの設計テンプレート
具体的なカードの置き方は班で決めますが、考え方は次の順番です。
これは完成盤を一度に公開しないための骨格です。どの情報を隠し、 どの部分を開けるかを曖昧にすると、ゼロ知識性か健全性のどちらかが壊れます。
3つの性質を紙の実験で問う
完全性 — 本当に完成盤を持つ prover なら、どのチャレンジにも正しく答えられるか。
健全性 — 解を持たない prover が、たまたま一回通るだけでなく、繰り返しごまかせないか。
ゼロ知識性 — verifier が見るカードの開示から、完成盤そのものを復元できないか。
特に大事なのは、「一回通った」だけでは健全性の証明にならないことです。 verifier が毎回違うランダムな検査を選び、同じ隠し方を使い回せないようにする必要があります。
数式への翻訳（時間があれば）
物理プロトコルの次は、数独のルールを有限体上の制約にします。
各マスを変数 xi,j とし、値が 1〜9 に入ること、
同じ行・列・ブロックで数字が重複しないこと、与えられた初期値と一致することを
R(x,w)=1 の形へ分解します。
数字の範囲: (x−1)(x−2)…(x−9)=0
初期値: xi,j − 公開値 = 0
行・列・ブロック: 各数字が一度ずつ現れる制約
ここで初めて、紙で考えた「何を隠し、何を検査するか」が、 R1CSや別のarithmetizationで扱える数学の問題になります。
この課題のゴール
数独を解くことではなく、「秘密の解を見せずに、正しい解を知っている」と言えるよう、 役割・順番・ランダムチャレンジ・開示範囲・受理条件を一つのプロトコルとして書くこと。
縦横チェックからの最適化アイデア
行と列を1組見るのはよい出発点ですが、数独には3×3ブロックも9個あります。
そこで、検査単位を 9行＋9列＋9ブロック＝27個 とまとめ、各ラウンドでverifierが
ランダムに1個を選ぶ設計にします。違反している単位が1個だけなら、1回で見つかる確率は
1/27 なので、同じ手順を何度も繰り返すほど、偽の解が通る確率が下がります。
ただし、選ばれた行をそのまま開くと解の一部が漏れます。proverが毎回1〜9の ランダムな数字置換を全体に適用してから、選ばれた単位だけを開けば、 verifierは「9種類が1回ずつある」ことだけ確認でき、元の数字の意味は分かりません。 初期配置との一致は、別のランダムなマスを選ぶチャレンジとして検査します。
検査回数と開示量のトレードオフ
1回に1単位だけ開けば情報漏えいは少ない一方、必要なラウンド数が増えます。 1回に行・列・ブロックを1つずつ開けば強くなりますが、開示量が増えます。 「何回、どの単位を、どこまで開くか」を比較するのが、プロトコル最適化の中心です。
合計だけでは足りない
ある単位の合計が45でも、1,1,2,5,6,7,7,8,8 のように重複は起こります。
数式化するなら、合計だけでなく積や、ランダムな r を使った
∏(r+vᵢ)=∏(r+1)…(r+9) のような指紋も候補になります。
R1CSでは、各マスを「数字dであるか」の0/1変数にして、セル・行・列・ブロックの
「各数字がちょうど1回」という制約へ分解できます。