1+1=2 で理解する zk-SNARKs の仕組み

「計算が正しく行われたこと」を、計算の中身を明かさずに証明できる。それが zk-SNARKs（ゼロ知識証明）です。

この記事では「1+1=2」を題材に、zk-SNARKsがどう動いているのかを解説します。

今回証明すること

「私は a + b = 2 となる a と b を知っている」

秘密の入力：a = 1, b = 1
公開される出力：c = 2
検証者は「和が2である」ことだけを確認でき、a, b の値は知らない

「それが証明できて何が嬉しいの？」と思うかもしれません。

実用例としてパスワード認証があります。通常、ログイン時にパスワードをサーバーに送りますが、これには漏洩リスクがあります。

zk-SNARKsを使えば：

「このハッシュ値を生成できる元の文字列（=パスワード）を知っている」ことを証明
パスワード自体は一切送らない

秘密を明かさずに「知っている」ことだけを証明する。これがゼロ知識証明の価値です。

1. 回路（Circuit）：計算を配線図にする

zk-SNARKsでは、計算を回路として表現します。

      ┌─────────┐
a ───→│   ADD   │───→ c
b ───→│         │
      └─────────┘

Circom（回路記述言語）で書くと下のコードになります。
Circomは代入が<==なので少しクセが強いかもしれませんが、慣れれば簡単です。最近はClaud Codeとかでも書けるようになってきています。

template Add() {
    signal input a;
    signal input b;
    signal output c;

    c <== a + b;
}

2. R1CS：制約を数式にする

回路を**R1CS（Rank-1 Constraint System）**に変換します。

すべての制約を A * B = C の形で表現：

1 * (a + b - c) = 0

これは a + b = c と同じ意味です。

3. Witness：計算の「証拠」

Witness は、回路を実行したときの全ての値です。「この計算を正しく実行した」という証拠になります。

入力 {"a": 1, "b": 1} から計算：

[
  "1",   // witness[0]: 定数 1
  "2",   // witness[1]: c（公開出力）
  "1",   // witness[2]: a（秘密）
  "1"    // witness[3]: b（秘密）
]

WASMファイル（add.wasm）がこの計算を行います。ブラウザでも動作可能。

4. なぜ証明できるのか：核心部分

ここがzk-SNARKsの本質です。

Step 1: 多項式に変換（QAP）

R1CSの制約を多項式に埋め込みます。

R1CS（今回の例）:
  制約1: 1 * (a + b - c) = 0

     ↓ 多項式に変換

QAP:
  A(x) * B(x) - C(x) = H(x) * Z(x)

今回は制約が1つなので：

制約「a + b - c = 0」 → x=1 で検証

witnessが正しいなら:
  A(1)*B(1) - C(1) = 0

→ x=1 で 0 になる
→ (x-1) で割り切れる！

複雑な回路で制約が100個あれば、x=1,2,...,100 の100点で検証し、Z(x)=(x-1)(x-2)...(x-100) で割り切れるかを確認します。

「計算が正しい」⟺「多項式が割り切れる」

Step 2: 楕円曲線で値を隠す

多項式の値をそのまま見せると秘密がバレます。
楕円曲線で「隠し」ます。

G: 楕円曲線上の基準点

sG を計算するのは簡単
sG から s を逆算するのは不可能（離散対数問題）

多項式 P(s) を直接公開せず、P(s)・G を公開：

P(s)・G から P(s) を逆算することは不可能

Step 3: Trusted Setup

問題: 秘密の s を誰が持つ？

Prover が知ってると嘘の証明が作れる
Verifier が知ってると秘密がバレる

解決: s を誰も知らない状態で [G, sG, s²G, ...] を作る

これが Trusted Setup（Powers of Tau） です。

pot12_final.ptau の中身:
[G, sG, s²G, s³G, ..., s^nG]
※ s は生成後に破棄

Step 4: ペアリングで検証

楕円曲線上の点だけで、どうやって検証する？

ペアリング（双線形写像） を使うらしいです。

e(aG, bG) = e(G, G)^(ab)

この性質で点のまま掛け算を検証できる：

e(π_A, π_B) = e(π_C, G) · e(π_H, Z(s)G)

Verifier は s も witness も知らずに検証可能。

5. 実際の証明

生成された証明（proof.json）：

{
  "pi_a": ["11061087...", "7816159...", "1"],
  "pi_b": [["1186762...", "13048250..."], ...],
  "pi_c": ["19689167...", "21748410...", "1"],
  "protocol": "groth16",
  "curve": "bn128"
}

BN128楕円曲線上の3つの点（π_A, π_B, π_C）です。

なぜ3つ？ → R1CSが A * B = C の形だったのを思い出してください。証明もこの構造に対応しています。

公開出力（public.json）：

["2"]

検証者はこれだけで「a + b = 2」を確認できます。
a = 1, b = 1 という秘密は一切知らない。

まとめ

┌───────────────────────────────────────────────────────┐
│                   zk-SNARKs の流れ                     │
├───────────────────────────────────────────────────────┤
│                                                       │
│  [回路]     a + b = c                                 │
│      ↓                                                │
│  [R1CS]     1 * (a + b - c) = 0                       │
│      ↓                                                │
│  [QAP]      多項式に変換（割り切れる ⟺ 正しい）         │
│      ↓                                                │
│  [Witness]  [1, 2, 1, 1]                              │
│      ↓                                                │
│  [Proof]    楕円曲線上の点（離散対数で隠す）            │
│      ↓                                                │
│  [検証]     ペアリングで等式を検証 → OK!               │
│                                                       │
└───────────────────────────────────────────────────────┘

回路: 計算を配線図に
R1CS: 「A * B = C」の形に
QAP: 多項式に（割り切れる ⟺ 正しい）
楕円曲線: 離散対数問題で値を隠す
ペアリング: 点のまま等式を検証

「何を計算したか」は隠したまま、「計算が正しいこと」だけを証明できる。

参考