🐡

ゼロ知識証明1(Plonk)

2025/10/28に公開

PLONKゼロ知識証明の実装：徹底解説ガイド

はじめに - ゼロ知識証明とは

洞窟のアナロジー

ゼロ知識証明を理解するために、有名な「アリババの洞窟」の例を使いましょう。

        入口
         |
    A --|-- B
     \     /
      \   /
       \ /
    秘密のドア
   （魔法の呪文で開く）

シナリオ：

あなた（証明者）は魔法の呪文を知っている
友人（検証者）にそれを証明したいが、呪文自体は教えたくない

証明方法：

友人は洞窟の外で待つ
あなたはAまたはB、どちらかのルートから入る（友人には見えない）
友人が「Aから出てきて」または「Bから出てきて」とランダムに指示
呪文を知っていれば、秘密のドアを通ってどちらからでも出られる
これを何度も繰り返す

ポイント：

呪文を知らなければ、正しい側から出られる確率は50%
10回成功すれば、確率は $(0.5)^{10} \approx 0.1\%$ → ほぼ確実に知っている
しかし友人は呪文自体を知ることはない

これがゼロ知識証明の本質です！

PLONKとは

PLONK（Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge）は、2019年に発表された革新的なゼロ知識証明システムです。

日常的な比喩で理解する

PLONKは「万能の証明書発行機」のようなものです。

従来のGroth16（古いシステム）：

運転免許証を発行するには → 運転免許センター
パスポートを発行するには → パスポートセンター
マイナンバーカードを発行するには → 市役所

それぞれ別の場所、別の手続き

PLONK（新しいシステム）：

どんな証明書でも → 同じコンビニの機械で発行可能
（サイズに制限はあるが、基本的に万能）

この「一度のセットアップで多用途」という特性が、PLONKの最大の革新です。

PLONKの主な特徴

1. Universal Trusted Setup（汎用トラステッドセットアップ）

Groth16の問題点：

新しいスマートコントラクトを作るたびに：
1. セレモニーを開催（数百人が参加）
2. 暗号パラメータを生成
3. 参加者全員が秘密を破棄

コスト：時間、労力、信頼の構築

PLONKの解決策：

一度だけセレモニーを開催：
1. 最大サイズ（例：2²⁸ゲート）を決める
2. そのサイズまでの全ての回路で使える
3. 新しい回路を作っても、追加セレモニー不要

例：Ethereumの「Powers of Tau」セレモニー
→ 多くのプロジェクトが共通で使用

2. コンパクトな証明サイズ

具体的なサイズ比較：

計算の複雑さ	証明サイズ	比喩
1,000ゲート	~1KB	テキストメッセージ1通分
100万ゲート	~1KB	同じくテキストメッセージ1通分
10億ゲート	~1KB	同じく！

証明サイズは計算の複雑さに依存しない $O(1)$ です。

イーサリアムでの意味：

トランザクションデータサイズ = ガス代

小さい証明 = 安いガス代 = 実用的

3. 高い汎用性

カスタムゲート（Custom Gates）の威力：

標準ゲート：加算と乗算のみ
SHA256を1回計算 → 約20,000ゲート必要

カスタムゲート：専用の演算を定義可能
SHA256を1回計算 → 約500ゲート（40倍高速！）

なぜ多項式を使うのか

これは初学者が最も混乱する部分です。なぜ単純な計算を、わざわざ多項式に変換するのでしょうか？

理由1: 圧縮

直接的な方法（使えない）：

全ての中間計算値を送る：
x = 3
x² = 9
x³ = 27
x³ + x = 30
x³ + x + 5 = 35

データサイズ = 計算ステップ数に比例（巨大！）

多項式を使う方法：

全ての値を1つの多項式 a(X) に圧縮：
a(1) = 3
a(ω) = 9
a(ω²) = 27
a(ω³) = 30
a(ω⁴) = 35

多項式のコミットメント = 48バイト（固定！）

理由2: ランダムチェック

重要な定理（Schwartz-Zippel Lemma）：

2つの異なる多項式 $f(X)$ と $g(X)$ （次数 $d$ ）がある場合、ランダムな点 $r$ で $f(r) = g(r)$ となる確率は最大 $\frac{d}{|F|}$ である。

直感的な理解：

2つのグラフが完全に同じ
 ↓
全ての点で一致する必要がある
 ↓
1つのランダムな点で一致する確率は極めて低い

例：

# 次数100の多項式
# 有限体のサイズ = 2²⁵⁶

一致する確率 = 100 / 2²⁵⁶ ≈ 10⁻⁷⁵

これは宇宙の原子の数よりも小さい！

理由3: 簡潔性

多項式の性質：

多項式 f(X) = c₀ + c₁X + c₂X² + ... + cₙXⁿ

情報量：
- 係数：n+1個の値（秘密）
- 評価値 f(r)：1つの値（公開）

比率 = 1 : (n+1)  → 極めて圧縮されている

実装の詳細解説（ステップバイステップ）

問題設定

証明したいこと：

私は x を知っている
そして x³ + x + 5 = 35 が成り立つ
でも x の値は教えない

答え： $x = 3$ （これを秘密にする）

ステップ0: なぜこのステップが必要か

各ステップの目的を先に理解しましょう：

ステップ	目的	比喩
1. 回路分解	計算を標準化	レシピを基本手順に分解
2. トレース作成	実行記録	料理の各ステップを記録
3. コピー制約	一貫性の保証	同じ材料を使っていることを確認
4. 多項式変換	圧縮	記録をZIPファイルに圧縮
5. 証明生成	暗号化	ZIPファイルに鍵をかける
6. 検証	鍵の確認	正しい鍵かチェック

ステップ1: 算術回路への分解

1.1 なぜ分解するのか

理由： コンピュータは複雑な式を一度に処理できません。基本演算（加算と乗算）の組み合わせに分解する必要があります。

アナロジー：

複雑な料理のレシピ
 ↓
基本的な調理手順に分解
 ↓
「切る」「炒める」「煮る」など

1.2 PLONKのゲート形式

PLONKでは、全てのゲートが以下の統一フォーマットで表現されます：

q_L \cdot a + q_R \cdot b + q_M \cdot (a \cdot b) + q_C + q_O \cdot c = 0

各要素の役割：

記号	名前	役割	比喩
$a, b$	左入力、右入力	演算の入力値	材料
$c$	出力	演算の結果	完成品
$q_L, q_R$	左/右セレクター	加算を制御	レシピの指示「Aを使う/使わない」
$q_M$	乗算セレクター	乗算を制御	「AとBを混ぜる/混ぜない」
$q_O$	出力セレクター	出力を制御	「結果を使う/使わない」
$q_C$	定数	定数の加算	「塩を5g追加」

なぜこの形式？

この1つの形式で全ての演算を表現可能：

加算：a + b = c
→ 1·a + 1·b + 0·(a·b) + 0 + (-1)·c = 0

乗算：a × b = c
→ 0·a + 0·b + 1·(a·b) + 0 + (-1)·c = 0

定数加算：a + 5 = c
→ 1·a + 0·b + 0·(a·b) + 5 + (-1)·c = 0

1.3 具体的な分解： $x^3 + x + 5 = 35$

計算を5つのステップに分解します。

ゲート1: $x^2$ を計算

目的：x × x を計算

入力：
  a = x = 3
  b = x = 3
出力：
  c = x² = 9

セレクター設定：
  q_L = 0   （aを単独で加算しない）
  q_R = 0   （bを単独で加算しない）
  q_M = 1   （a×bを計算する！）
  q_O = -1  （結果をcに格納）
  q_C = 0   （定数なし）

制約式：
  0·3 + 0·3 + 1·(3×3) + 0 + (-1)·9 = 0
  9 - 9 = 0 ✓

視覚化：

┌─────────────────────┐
│  ゲート1: 乗算      │
│                     │
│  a=3 ──┐            │
│        ├──×── c=9   │
│  b=3 ──┘            │
└─────────────────────┘

ゲート2: $x^3$ を計算

目的：x² × x を計算

入力：
  a = x² = 9  （前のゲートの出力を使用！）
  b = x = 3
出力：
  c = x³ = 27

制約式：
  0·9 + 0·3 + 1·(9×3) + 0 + (-1)·27 = 0
  27 - 27 = 0 ✓

ゲート3: $x^3 + x$ を計算

目的：x³ + x を計算

入力：
  a = x³ = 27
  b = x = 3
出力：
  c = x³ + x = 30

セレクター設定：
  q_L = 1    （aを加算する）
  q_R = 1    （bを加算する）
  q_M = 0    （乗算しない）
  q_O = -1   
  q_C = 0

制約式：
  1·27 + 1·3 + 0·(27×3) + 0 + (-1)·30 = 0
  27 + 3 - 30 = 0 ✓

視覚化：

┌─────────────────────┐
│  ゲート3: 加算      │
│                     │
│  a=27 ──┐           │
│         ├──+── c=30 │
│  b=3  ──┘           │
└─────────────────────┘

ゲート4: $x^3 + x + 5$ を計算

目的：前の結果に5を加算

入力：
  a = x³ + x = 30
  b = 未使用
出力：
  c = x³ + x + 5 = 35

セレクター設定：
  q_L = 1
  q_R = 0
  q_M = 0
  q_O = -1
  q_C = 5    （定数5を加算！）

制約式：
  1·30 + 0·0 + 0·(30×0) + 5 + (-1)·35 = 0
  30 + 5 - 35 = 0 ✓

ゲート5: 出力が35であることを検証

目的：最終結果が公開値35と一致することを確認

入力：
  a = 35
  b = 未使用
出力：
  c = 未使用

セレクター設定：
  q_L = 1
  q_R = 0
  q_M = 0
  q_O = 0
  q_C = -35  （公開入力）

制約式：
  1·35 + 0 + 0 + (-35) + 0 = 0
  35 - 35 = 0 ✓

1.4 全体の流れを視覚化

秘密入力: x = 3
    ↓
┌─────────────────┐
│ ゲート1: x²     │  → v₁ = 9
└─────────────────┘
    ↓
┌─────────────────┐
│ ゲート2: x³     │  → v₂ = 27
└─────────────────┘
    ↓
┌─────────────────┐
│ ゲート3: x³+x   │  → v₃ = 30
└─────────────────┘
    ↓
┌─────────────────┐
│ ゲート4: +5     │  → 35
└─────────────────┘
    ↓
┌─────────────────┐
│ ゲート5: 検証   │  → 35 = 35 ✓
└─────────────────┘

ステップ2: 実行トレース（Execution Trace）の作成

2.1 なぜトレースが必要か

目的： 計算の「録画」を作る

アナロジー：

料理の動画撮影：
- 各ステップで材料の状態を記録
- 後で「ちゃんとレシピ通りに作った」と証明できる

2.2 トレース表

全てのゲートの入出力とセレクターを表にまとめます：

ゲート	$a$	$b$	$c$	$q_L$	$q_R$	$q_M$	$q_O$	$q_C$	検証
1	3	3	9	0	0	1	-1	0	$1\cdot(3\times3)-9=0$ ✓
2	9	3	27	0	0	1	-1	0	$1\cdot(9\times3)-27=0$ ✓
3	27	3	30	1	1	0	-1	0	$27+3-30=0$ ✓
4	30	0	35	1	0	0	-1	5	$30+5-35=0$ ✓
5	35	0	0	1	0	0	0	-35	$35-35=0$ ✓

この表が証明の「生データ」です！

ステップ3: コピー制約（Copy Constraints）

これがPLONKの最も独特で重要な部分です。

3.1 なぜコピー制約が必要か

問題： 異なるゲートで「同じ値」を使っていることをどう証明する？

具体例：

ゲート1で x = 3 を使った
ゲート2でも x = 3 を使った
ゲート3でも x = 3 を使った

でも、これが本当に「同じ x」だと、どう保証する？

悪い例（コピー制約がない場合）：

不正な証明者：
ゲート1: x₁ = 3 を使う
ゲート2: x₂ = 5 を使う  ← 違う値！
ゲート3: x₃ = 7 を使う  ← また違う値！

各ゲートは個別に正しく見えるが、
全体としては矛盾している

コピー制約の役割：

「位置が異なっても、同じ変数は同じ値」
を数学的に保証する

3.2 位置のラベリング

全ての入出力に固有の「位置番号」を割り当てます：

ゲート1:  a₁=3,  b₁=3,  c₁=9
ゲート2:  a₂=9,  b₂=3,  c₂=27
ゲート3:  a₃=27, b₃=3,  c₃=30
ゲート4:  a₄=30, b₄=0,  c₄=35
ゲート5:  a₅=35, b₅=0,  c₅=0

合計15個の位置

3.3 等しい値のグループ化

同じ値を持つ位置をグループにします：

グループ1: x = 3

位置: a₁, b₁, b₂, b₃
値: 全て 3

グループ2: v₁ = 9

位置: c₁, a₂
値: 全て 9

グループ3: v₂ = 27

位置: c₂, a₃
値: 全て 27

グループ4: v₃ = 30

位置: c₃, a₄
値: 全て 30

グループ5: output = 35

位置: c₄, a₅
値: 全て 35

3.4 置換（Permutation） $\sigma$ の構築

各グループ内で、位置を「サイクル」でつなぎます。

グループ1のサイクル:

a₁ → b₁ → b₂ → b₃ → a₁

数式で表現：

\begin{aligned} \sigma(a_1) &= b_1 \\ \sigma(b_1) &= b_2 \\ \sigma(b_2) &= b_3 \\ \sigma(b_3) &= a_1 \quad \text{（閉じる）} \end{aligned}

視覚化：

    a₁
   ↗  ↖
  ↙    ↘
b₃      b₁
  ↖    ↗
   ↘  ↙
    b₂

グループ2のサイクル:

c₁ → a₂ → c₁

\begin{aligned} \sigma(c_1) &= a_2 \\ \sigma(a_2) &= c_1 \end{aligned}

同様に他のグループも...

3.5 なぜサイクルなのか

重要な性質：

もし全ての値が等しいなら、
サイクルをたどっても値は変わらない

a₁ = 3
→ σ(a₁) = b₁ = 3
→ σ(b₁) = b₂ = 3
→ σ(b₂) = b₃ = 3
→ σ(b₃) = a₁ = 3  ← 元に戻る

もし不正なら：

a₁ = 3
→ σ(a₁) = b₁ = 3
→ σ(b₁) = b₂ = 5  ← 異なる！
→ サイクルが壊れる

ステップ4: 多項式への変換

ここが魔法が起こる場所です！

4.1 評価ドメインの準備

目的： 5つのゲート → 5つの評価点

$n$ 乗根の選択：

有限体 $\mathbb{F}_p$ 上で、 $\omega^5 = 1$ となる $\omega$ を選びます。

例: p = 97 の場合
ω = 25

検証:
25¹ mod 97 = 25
25² mod 97 = 42
25³ mod 97 = 80
25⁴ mod 97 = 21
25⁵ mod 97 = 1  ✓

評価ドメイン：

H = \{1, \omega, \omega^2, \omega^3, \omega^4\}

4.2 列ベクトルから多項式へ

左入力の列：

a = [3, 9, 27, 30, 35]

これを多項式 $a(X)$ に変換：

\begin{aligned} a(1) &= 3 \\ a(\omega) &= 9 \\ a(\omega^2) &= 27 \\ a(\omega^3) &= 30 \\ a(\omega^4) &= 35 \end{aligned}

ラグランジュ補間：

5つの点を通る4次多項式が一意に決まります：

a(X) = \sum_{i=0}^{4} a_i \cdot L_i(X)

ここで $L_i(X)$ はラグランジュ基底多項式：

L_i(X) = \prod_{j \neq i} \frac{X - \omega^j}{\omega^i - \omega^j}

性質：

L_i(\omega^j) = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{if } i \neq j \end{cases}

具体例： $L_0(X)$ （ $X=1$ で1、他で0）

L_0(X) = \frac{(X-\omega)(X-\omega^2)(X-\omega^3)(X-\omega^4)}{(1-\omega)(1-\omega^2)(1-\omega^3)(1-\omega^4)}

4.3 多項式の意味

なぜこれが便利か：

圧縮： 5つの値 → 1つの多項式
検証： ランダムな点で評価するだけ
コミット： 多項式全体を48バイトで表現可能

比喩：

データポイント = 星座の星
多項式 = 星を結ぶ線

星の位置（データ）を全て送る代わりに、
線の方程式（多項式）を送るだけでOK

4.4 ゲート制約多項式

全てのゲートで制約が満たされることを1つの多項式で表現：

\begin{aligned} &q_L(X) \cdot a(X) + q_R(X) \cdot b(X) \\ &+ q_M(X) \cdot a(X) \cdot b(X) \\ &+ q_C(X) + q_O(X) \cdot c(X) = 0 \end{aligned}

評価点 $H = \{1, \omega, \omega^2, \omega^3, \omega^4\}$ で

問題： 全ての点で0になることをどう検証？

解決： 消失多項式（Vanishing Polynomial）を使う！

Z_H(X) = (X-1)(X-\omega)(X-\omega^2)(X-\omega^3)(X-\omega^4)

重要な性質：

Z_H(\omega^i) = 0 \quad \text{for all } i \in \{0,1,2,3,4\}

制約が満たされるなら、商多項式 $h(X)$ が存在：

q_L(X) \cdot a(X) + \cdots + q_O(X) \cdot c(X) = Z_H(X) \cdot h(X)

直感的な理解：

左辺が評価点で全て0
 ↓
左辺は Z_H(X) で割り切れる
 ↓
商 h(X) が存在

4.5 コピー制約の多項式

置換 $\sigma$ を多項式で検証します。

アイデア： 累積積（Grand Product）を使う

z(X) = \text{累積積の多項式}

定義：

z(1) = 1

z(\omega \cdot g) = z(g) \cdot \frac{f(g)}{f(\sigma(g))}

ここで：

f(g) = w(g) + \beta \cdot \text{id}(g) + \gamma

$w(g)$ : ワイヤーの値
$\text{id}(g)$ : 位置の識別子
$\beta, \gamma$ : ランダムチャレンジ

最終条件：

z(\omega^5) = z(1) = 1

なぜこれが機能するか：

もし全ての $w(g) = w(\sigma(g))$ なら：

\prod_g \frac{w(g) + \beta \cdot \text{id}(g) + \gamma}{w(\sigma(g)) + \beta \cdot \sigma(\text{id}(g)) + \gamma}

分子と分母で $w$ の項が打ち消し合い、結果は1になる。

ステップ5: 証明の生成

証明者は以下の手順で証明を作成します。

5.1 多項式のコミット

KZG コミットメント：

多項式 $f(X) = \sum_{i=0}^d c_i X^i$ に対して：

[f(X)]_1 = g^{f(\tau)} = \prod_{i=0}^d (g^{\tau^i})^{c_i}

ここで：

$g$ : 楕円曲線の生成元
$\tau$ : トラステッドセットアップの秘密（破棄済み）
$g^\tau, g^{\tau^2}, \ldots, g^{\tau^d}$ : 公開パラメータ

例：

# 多項式 f(X) = 3 + 5X + 2X²

# 係数
c = [3, 5, 2]

# コミットメント計算
commit = g^3 · (g^τ)^5 · (g^τ²)^2
       = g^(3 + 5τ + 2τ²)
       = g^f(τ)

# サイズ: 48バイト（圧縮された楕円曲線点）

コミット（Prover）：

# 1. ワイヤー多項式をコミット
commit_a = KZG.commit(a(X))  # [a(X)]₁
commit_b = KZG.commit(b(X))  # [b(X)]₁
commit_c = KZG.commit(c(X))  # [c(X)]₁

# これらを検証者に送信
# サイズ: 3 × 48 = 144バイト

5.2 ランダムチャレンジの生成

Fiat-Shamir変換：

対話型プロトコルを非対話型に変換する技術。

# ランダムチャレンジをハッシュから生成
β, γ = hash(commit_a, commit_b, commit_c)

# これにより、証明者は「未来の質問」に答えられない
# = 不正ができない

なぜ安全か：

ハッシュ関数は予測不可能
コミット後に決まるので、事前に対策できない
検証者も同じハッシュを計算して検証可能

5.3 コピー制約の累積多項式

# z(X) を計算
z = [1]  # z(1) = 1

for i in range(n):
    numerator = (a[i] + β*id_a[i] + γ) * 
                (b[i] + β*id_b[i] + γ) * 
                (c[i] + β*id_c[i] + γ)
    
    denominator = (a[i] + β*σ_a[i] + γ) * 
                  (b[i] + β*σ_b[i] + γ) * 
                  (c[i] + β*σ_c[i] + γ)
    
    z.append(z[-1] * numerator / denominator)

# z(X) を補間
z_poly = interpolate(z)

# コミット
commit_z = KZG.commit(z_poly)

5.4 商多項式の計算

# ゲート制約の左辺
gate_constraint = (
    q_L * a_poly + 
    q_R * b_poly + 
    q_M * a_poly * b_poly + 
    q_C + 
    q_O * c_poly
)

# 消失多項式で割る
h_poly = gate_constraint / Z_H

# コミット
commit_h = KZG.commit(h_poly)

5.5 評価点での開示

# 新しいチャレンジ
ζ = hash(commit_z, commit_h)

# 評価値を計算
a_ζ = a_poly(ζ)
b_ζ = b_poly(ζ)
c_ζ = c_poly(ζ)
z_ζ = z_poly(ζ)
h_ζ = h_poly(ζ)

# これらは公開値（秘密ではない）

5.6 開示証明の生成

多項式が正しい評価値を持つことを証明：

# a(X) が点 ζ で a_ζ という値を持つことの証明
proof_a = KZG.open(a_poly, ζ, a_ζ)

# 数学的には：
# q_a(X) = (a(X) - a_ζ) / (X - ζ)
# proof_a = [q_a(X)]₁

完全な証明：

proof = {
    # コミットメント（5個 × 48バイト = 240バイト）
    "commitments": {
        "a": commit_a,
        "b": commit_b,
        "c": commit_c,
        "z": commit_z,
        "h": commit_h
    },
    
    # 評価値（5個 × 32バイト = 160バイト）
    "evaluations": {
        "a": a_ζ,
        "b": b_ζ,
        "c": c_ζ,
        "z": z_ζ,
        "h": h_ζ
    },
    
    # 開示証明（5個 × 48バイト = 240バイト）
    "opening_proofs": {
        "a": proof_a,
        "b": proof_b,
        "c": proof_c,
        "z": proof_z,
        "h": proof_h
    }
}

# 合計: 約640バイト

ステップ6: 検証

検証者は証明を受け取り、以下の手順で検証します。

6.1 検証者が知っていること

公開情報：
- 出力値: 35
- セレクター多項式: q_L, q_R, q_M, q_O, q_C
- 置換: σ
- トラステッドセットアップパラメータ

証明：
- コミットメント
- 評価値
- 開示証明

検証者が知らないこと：

秘密情報：
- x = 3
- 多項式の係数
- 中間値（v₁, v₂, v₃）

6.2 ランダムチャレンジの再生成

# Fiat-Shamir: 同じハッシュを計算
β, γ = hash(commit_a, commit_b, commit_c)
ζ = hash(commit_z, commit_h)

# 証明者と同じ値が得られる

6.3 ゲート制約の検証

評価点 $\zeta$ でゲート制約が満たされるかチェック：

# 左辺を計算
gate_check = (
    q_L_ζ * a_ζ + 
    q_R_ζ * b_ζ + 
    q_M_ζ * a_ζ * b_ζ + 
    q_C_ζ + 
    q_O_ζ * c_ζ
)

# 右辺を計算
right_side = Z_H_ζ * h_ζ

# 等しいかチェック
assert gate_check == right_side

数式で：

q_L(\zeta) \cdot a(\zeta) + q_R(\zeta) \cdot b(\zeta) + q_M(\zeta) \cdot a(\zeta) \cdot b(\zeta) + q_C(\zeta) + q_O(\zeta) \cdot c(\zeta) = Z_H(\zeta) \cdot h(\zeta)

6.4 コピー制約の検証

# L₁(ζ): 最初の評価点でのみ1となるラグランジュ多項式
L_1_ζ = compute_lagrange(ζ, 0)

# z(1) = 1 をチェック
assert L_1_ζ * (z_ζ - 1) == 0

# 累積積の整合性をチェック
numerator = (
    (a_ζ + β*ζ + γ) *
    (b_ζ + β*k₁*ζ + γ) *
    (c_ζ + β*k₂*ζ + γ)
)

denominator = (
    (a_ζ + β*σ_a_ζ + γ) *
    (b_ζ + β*σ_b_ζ + γ) *
    (c_ζ + β*σ_c_ζ + γ)
)

assert z_ωζ * numerator == z_ζ * denominator

数式で：

z(\omega \cdot \zeta) \cdot \prod_{i \in \{a,b,c\}} (w_i(\zeta) + \beta \cdot \text{id}_i(\zeta) + \gamma) = z(\zeta) \cdot \prod_{i \in \{a,b,c\}} (w_i(\zeta) + \beta \cdot \sigma_i(\zeta) + \gamma)

6.5 KZG開示の検証

各多項式のコミットメントと評価値が整合することを検証：

# a(X) の開示検証
assert KZG.verify(
    commitment=commit_a,
    point=ζ,
    value=a_ζ,
    proof=proof_a
)

# 同様に b, c, z, h も検証

ペアリングによる検証：

e([a(X)]_1 - [a(\zeta)]_1, [1]_2) = e([q_a(X)]_1, [\tau]_2 - [\zeta]_2)

簡略化すると：

e(g^{a(\tau) - a(\zeta)}, g) = e(g^{q_a(\tau)}, g^{\tau - \zeta})

なぜこれで証明できるか：

もし $q_a(X) = \frac{a(X) - a(\zeta)}{X - \zeta}$ なら：

a(\tau) - a(\zeta) = q_a(\tau) \cdot (\tau - \zeta)

両辺を $g$ の指数として：

g^{a(\tau) - a(\zeta)} = (g^{q_a(\tau)})^{\tau - \zeta}

ペアリングでこれを検証できる！

6.6 検証の完了

if all_checks_passed:
    return "証明は正当です ✓"
    # x の値を知らなくても、
    # 計算が正しいことが確認できた！
else:
    return "証明は無効です ✗"

技術的な仕組みの深掘り

なぜPLONKは安全なのか

1. 多項式の情報理論的性質

Schwartz-Zippel補題の応用：

異なる多項式がランダムな点で一致する確率は無視できるほど小さい：

\Pr[f(r) = g(r)] \leq \frac{\deg(f)}{|F|}

具体例：

次数: d = 2²⁰ ≈ 100万
体のサイズ: |F| = 2²⁵⁶

確率 ≈ 2²⁰ / 2²⁵⁶ = 2⁻²³⁶

これは：
- SHA256を破る確率（2⁻²⁵⁶）に近い
- 宇宙の原子の数（約2²⁶⁶）よりも小さい確率

2. トラステッドセットアップの安全性

「1人が正直なら安全」という性質：

セレモニーに1000人参加
↓
全員が秘密 τ の一部を生成
↓
誰か1人でも τ を破棄すれば安全
↓
1000人全員が共謀しない限り安全

実際のセレモニー例：

Ethereumの「Powers of Tau」：

参加者: 約180人
期間: 2年以上
結果: 公開パラメータが生成され、多くのプロジェクトで使用中

3. Fiat-Shamirの安全性

対話型 vs 非対話型：

対話型（安全だが非効率）：

検証者: ランダムな質問をする
証明者: 答える
検証者: また別のランダムな質問
...

非対話型（効率的で安全）：

証明者: 全ての答えを一度に提供
検証者: ハッシュで質問を再生成して検証

ハッシュ = 予測不可能な質問生成器

安全性の根拠：

ハッシュ関数 $H$ がランダムオラクルモデルで安全なら、Fiat-Shamir変換も安全。

コピー制約の深い理解

なぜ累積積（Grand Product）なのか

直感的な説明：

2つの集合 $A$ と $B$ が等しい（順序は異なってもOK）
↔ それぞれの要素を掛け合わせた積が等しい

例：

A = {2, 3, 5}
B = {5, 2, 3}  （順序は異なる）

∏A = 2 × 3 × 5 = 30
∏B = 5 × 2 × 3 = 30

等しい！

PLONKでの応用：

元のワイヤー値の集合: {w₁, w₂, ..., wₙ}
置換後の集合: {w_σ(1), w_σ(2), ..., w_σ(n)}

もしコピーが正しければ、これらは同じ集合
↓
積も等しい

ランダム化が必要な理由

問題： 単純な積だと、以下のような不正が可能

不正な例：
A = {2, 3}
B = {1, 6}

∏A = 6
∏B = 6  ← 積は等しいが、集合は異なる！

解決策： ランダム線形結合

f(x) = w + \beta \cdot \text{id} + \gamma

ランダムな $\beta, \gamma$ を使うことで、不正な値が一致する確率は無視できるほど小さくなる。

比較と実用例

詳細な性能比較

特性	PLONK	Groth16	STARKs	Halo2
Setup
Trusted Setup	Universal	Circuit-specific	不要	不要
Setup時間	数時間（1回のみ）	数分（回路ごと）	不要	不要
証明サイズ
100万ゲート	~1KB	~200B	~100KB	~2KB
10億ゲート	~1KB	~200B	~500KB	~2KB
証明時間
100万ゲート	10秒	5秒	30秒	2秒
10億ゲート	10,000秒	5,000秒	30,000秒	2,000秒
検証時間
任意のサイズ	10ms	5ms	50ms	15ms
その他
量子耐性	なし	なし	あり	なし
再帰的合成	可能	困難	得意	得意

実用例の詳細

zkRollup: zkSync Era

技術スタック：

Layer 1 (Ethereum)
    ↓
PLONK証明の検証（ガス代: 約500K）
    ↑
Layer 2 (zkSync)
- トランザクション処理（2000 TPS）
- バッチ作成（数千トランザクション）
- PLONK証明生成（約10分）

コスト削減の仕組み：

直接L1に送信する場合：
- 1トランザクション ≈ 21,000 gas
- 1,000トランザクション ≈ 21,000,000 gas

zkRollupの場合：
- 1,000トランザクションのバッチ ≈ 500,000 gas
- 削減率: 約98%

経済性の計算：

# L1でのトランザクションコスト
gas_price = 50 gwei
l1_cost = 21_000 * gas_price = 1,050,000 gwei = 0.00105 ETH

# zkRollupでのトランザクションコスト（1000トランザクションのバッチ）
batch_size = 1000
l2_cost = (500_000 * gas_price) / batch_size = 500 gwei = 0.0000005 ETH

# 約2100倍安い！

プライバシー: Aztec Network

UltraPLONKの特別な機能：

Lookupテーブル：

従来: SHA256の計算に20,000ゲート
Lookup: 事前計算したテーブルから参照、500ゲート
高速化: 40倍

カスタムゲート：

楕円曲線演算（ECAdd, ECMul）を1ゲートで表現
従来: 数百ゲート必要

プライベート取引の例：

公開情報:
- 取引が存在すること
- 取引が有効であること

秘密情報:
- 送信者: Alice（秘密）
- 受信者: Bob（秘密）
- 金額: 10 ETH（秘密）

証明:
- Aliceの残高 ≥ 10 ETH
- 署名が正しい
- nullifier（二重使用防止）が未使用

よくある質問

Q1: トラステッドセットアップは本当に安全？

A: はい、以下の理由で安全です：

「1 of N」信頼モデル：

N人の参加者のうち、1人でも正直なら安全

例：100人参加
- 99人が共謀しても
- 1人が秘密を破棄すれば
→ 安全

検証可能性：

セットアップの各ステップは検証可能
- 不正があればすぐに発見される
- 公開パラメータの正当性を数学的に証明

実績：

Zcashの「Powers of Tau」：
- 176人が参加
- 期間: 約2年
- 問題なく運用中

Q2: なぜ多項式の次数が重要？

A: トラステッドセットアップのサイズを決めるからです。

最大次数 d = 2²⁰（約100万）の場合：

セットアップパラメータ:
{g, g^τ, g^τ², ..., g^τ^(2²⁰)}

サイズ ≈ 2²⁰ × 48バイト ≈ 50MB

この1つのセットアップで、
100万ゲート以下の全ての回路に使える

Q3: 証明の生成は本当に速い？

A: 実装と回路サイズに依存します。

ベンチマーク例（gnark）：

回路サイズ    | 証明時間
-------------|----------
1,000        | ~0.1秒
10,000       | ~1秒
100,000      | ~10秒
1,000,000    | ~100秒
10,000,000   | ~1,000秒（約17分）

最適化技術：

並列化：

FFT（高速フーリエ変換）は並列化可能
→ マルチコアCPUで高速化

GPU加速：

楕円曲線演算をGPUで並列実行
→ 10-100倍の高速化

専用ハードウェア：

FPGAやASICでの実装
→ さらに高速化可能

Q4: PLONKはどんな計算でも証明できる？

A: 「チューリング完全」ではありませんが、実用的にはほとんどの計算を証明できます。

証明可能なもの：

✅ 算術演算（加減乗除）
✅ ビット演算（AND, OR, XOR）
✅ ハッシュ関数（SHA256, Poseidon）
✅ 署名検証（ECDSA, EdDSA）
✅ Merkle Tree検証
✅ スマートコントラクトの実行

課題があるもの：

⚠️ 浮動小数点演算（ゲート数が多い）
⚠️ ループ（事前に回数が決まっている必要）
❌ ランダム性（決定論的である必要）
❌ 外部API呼び出し（オフチェーンで実行不可）

Q5: 証明の検証にどのくらい時間がかかる？

A: 非常に高速で、計算の複雑さに依存しません。

検証時間の内訳：

1. ハッシュ計算（Fiat-Shamir）: ~1ms
2. 体演算（評価値のチェック）: ~1ms  
3. ペアリング演算（KZG検証）: ~10ms

合計: 約10-20ms

スマートコントラクトでの検証：

// Ethereum上での検証
function verify(Proof memory proof) public view returns (bool) {
    // ガス代: 約500,000 gas
    // 時間: ブロックに含まれるまで約15秒
    // コスト: 約0.025 ETH（ガス代50 gwei時）
    
    return verifyPairing(proof);
}

Q6: 再帰的証明とは？

A: 「証明の証明」を作ることです。

用途：

証明1: トランザクション1-1000を処理した
証明2: トランザクション1001-2000を処理した
...
証明100: トランザクション99001-100000を処理した

再帰的証明: 証明1-100が全て正しい

結果: 100,000トランザクションを1つの証明で表現

PLONKでの実現：

証明Aの検証回路を作る
↓
この回路をPLONKで証明（証明B）
↓
証明Bは「証明Aが正しい」ことを証明

証明サイズ: A ≈ 1KB, B ≈ 1KB
検証時間: どちらも約10ms

無限の圧縮：

レベル0: 1,000個のトランザクション → 1証明
レベル1: 1,000個の証明 → 1証明
レベル2: 1,000個の証明 → 1証明
...

100万トランザクション → 1,000証明（L0）→ 1証明（L1）
10億トランザクション → 100万証明（L0）→ 1,000証明（L1）→ 1証明（L2）

学習リソース

段階的な学習パス

レベル1: 基礎（2-4週間）

ゼロ知識証明の基本：
- 動画: "Zero Knowledge Proofs - Computerphile"（YouTube）
- 記事: Vitalik Buterin "An approximate introduction to how zk-SNARKs are possible"
有限体と楕円曲線：
- 本: "A Graduate Course in Applied Cryptography" by Dan Boneh
- オンラインコース: Coursera "Cryptography I"

レベル2: PLONKの理論（4-8週間）

原論文：
- "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge"
- 読み方: 最初は流し読み、2回目で詳細を理解
解説記事：
- Vitalik "Understanding PLONK"
- "PLONK by Hand" by David Wong（実際に手計算で理解）

レベル3: 実装（8-12週間）

ライブラリで実装：

おすすめ順:
1. circom（DSL、初心者向け）
2. gnark（Go、プロダクション品質）
3. arkworks（Rust、研究向け）

プロジェクト例：
- シンプルな算術証明
- Merkle Tree検証
- 簡単なトークン転送
- 署名検証

レベル4: 応用（継続的）

zkRollup実装の理解：
- zkSync Era のソースコード
- Polygon zkEVM のアーキテクチャ
最新の研究：
- eprint.iacr.org（暗号論文のプレプリント）
- ZK Whiteboard Sessions（YouTube）

推奨リソース一覧

論文

PLONK論文 - Gabizon et al., 2019
KZG論文 - Kate et al., 2010
Fiat-Shamir論文 - Fiat & Shamir, 1986

ブログ・記事

Vitalik Buterin's Blog
- "Understanding PLONK"
- "An approximate introduction to how zk-SNARKs are possible"
David Wong's Blog
- "PLONK by Hand"
- "How does polynomial commitment work?"
Aztec Network Blog
- "Explaining the UltraPLONK Arithmetization"

動画コース

ZK Whiteboard Sessions（YouTube）
- プロトコル開発者による詳細解説
- 全50+エピソード
ZKP MOOC 2023（YouTube + Berkeley）
- 大学レベルの体系的コース
- 課題とプロジェクト付き

実装ライブラリ

gnark (Go)

// 使いやすさ: ★★★★☆
// 性能: ★★★★★
// ドキュメント: ★★★★☆

arkworks (Rust)

// 使いやすさ: ★★★☆☆
// 性能: ★★★★★
// ドキュメント: ★★★☆☆

circom (DSL)

// 使いやすさ: ★★★★★
// 性能: ★★★☆☆
// ドキュメント: ★★★★☆

コミュニティ

Discordサーバー：
- Polygon zkEVM
- zkSync
- Aztec Network
フォーラム：
- Ethereum Research（ethresear.ch）
- ZKProof Standards

まとめ

PLONKの重要なポイント

Universal Setup

1回のセットアップ → ∞の回路
開発コスト激減

コンパクトな証明

証明サイズ = O(1)
イーサリアムで実用的

コピー制約

置換 σ で同一性を保証
PLONKの独自技術

多項式の魔法

圧縮 + 検証 + セキュリティ
全てを1つの枠組みで実現

学習の次のステップ

理論の理解（この記事）
    ↓
小さな例の実装（circom推奨）
    ↓
実用例の研究（zkRollup等）
    ↓
独自プロジェクトの開発

実世界での重要性

PLONKは単なる暗号技術ではなく、ブロックチェーンのスケーラビリティ問題を解決する鍵です。

現在のイーサリアム:
- 15 TPS
- 高いガス代

zkRollup（PLONK使用）:
- 2000+ TPS
- ガス代1/100
- セキュリティは同等

未来のWeb3:
- 実用的な速度とコスト
- プライバシー保護
- 複雑な計算の検証可能性

この技術を理解し実装できることは、次世代のブロックチェーン開発者にとって必須のスキルになるでしょう。

この記事について：

この記事は、PLONKゼロ知識証明の実装を、初学者から中級者まで理解できるように段階的に説明したものです。数学的な厳密性と直感的な理解のバランスを重視し、具体例とアナロジーを多用しています。

より深く学びたい方は、参考文献セクションのリソースを活用してください。また、実装を通じて理解を深めることを強くお勧めします。

フィードバックとコントリビューション：

この記事への質問、訂正、改善提案は歓迎します。ゼロ知識証明の普及と教育に貢献できれば幸いです。

PLONKゼロ知識証明の実装：徹底解説ガイド

目次

はじめに - ゼロ知識証明とは

洞窟のアナロジー

PLONKとは

日常的な比喩で理解する

PLONKの主な特徴

1. Universal Trusted Setup（汎用トラステッドセットアップ）

2. コンパクトな証明サイズ

3. 高い汎用性

なぜ多項式を使うのか

理由1: 圧縮

理由2: ランダムチェック

理由3: 簡潔性

実装の詳細解説（ステップバイステップ）

問題設定

ステップ0: なぜこのステップが必要か

ステップ1: 算術回路への分解

1.1 なぜ分解するのか

1.2 PLONKのゲート形式

1.3 具体的な分解：x^3 + x + 5 = 35

1.4 全体の流れを視覚化

ステップ2: 実行トレース（Execution Trace）の作成

2.1 なぜトレースが必要か

2.2 トレース表

ステップ3: コピー制約（Copy Constraints）

3.1 なぜコピー制約が必要か

3.2 位置のラベリング

3.3 等しい値のグループ化

3.4 置換（Permutation）\sigma の構築

3.5 なぜサイクルなのか

ステップ4: 多項式への変換

4.1 評価ドメインの準備

4.2 列ベクトルから多項式へ

4.3 多項式の意味

4.4 ゲート制約多項式

4.5 コピー制約の多項式

ステップ5: 証明の生成

5.1 多項式のコミット

5.2 ランダムチャレンジの生成

5.3 コピー制約の累積多項式

5.4 商多項式の計算

5.5 評価点での開示

5.6 開示証明の生成

ステップ6: 検証

6.1 検証者が知っていること

6.2 ランダムチャレンジの再生成

6.3 ゲート制約の検証

6.4 コピー制約の検証

6.5 KZG開示の検証

6.6 検証の完了

技術的な仕組みの深掘り

なぜPLONKは安全なのか

1. 多項式の情報理論的性質

2. トラステッドセットアップの安全性

3. Fiat-Shamirの安全性

コピー制約の深い理解

なぜ累積積（Grand Product）なのか

ランダム化が必要な理由

比較と実用例

詳細な性能比較

実用例の詳細

zkRollup: zkSync Era

プライバシー: Aztec Network

よくある質問

Q1: トラステッドセットアップは本当に安全？

Q2: なぜ多項式の次数が重要？

Q3: 証明の生成は本当に速い？

Q4: PLONKはどんな計算でも証明できる？

Q5: 証明の検証にどのくらい時間がかかる？

Q6: 再帰的証明とは？

学習リソース

段階的な学習パス

レベル1: 基礎（2-4週間）

レベル2: PLONKの理論（4-8週間）

レベル3: 実装（8-12週間）

レベル4: 応用（継続的）

推奨リソース一覧

論文

ブログ・記事

1.3 具体的な分解： $x^3 + x + 5 = 35$

3.4 置換（Permutation） $\sigma$ の構築