ゼロ知識証明：計算を多項式に変換する（第1回/全3回）

ゼロ知識証明が至るところで話題になっている。BalajiはAIへの対抗手段だと位置づけている。「人工知能は攻撃。ゼロ知識は防御。」ポッドキャストにカンファレンス、暗号のロードマップと、ZKはどこにでもある。実際に中で何が起きているのか理解したく、予告どおり数学をゼロから追いかけてみた。最も面白かったのは暗号技術ではなく、その手前のステップだった。どうやってプログラムを、暗号技術が扱える形に変換するのか、というところだ。

この記事ではそこを扱う。小さなプログラムを取り上げ、基本演算に分解し、それらを行列としてエンコードし、すべてをSNARK¹が検証できる1つの方程式に集約する。構成と例は、このトピックの入門として今でも最も明快なVitalikの2016年のQAP解説に沿っている。これは全3回の第1回（第2回は証明プロトコル、第3回は応用を扱う）。以前の記事で取り上げた有限体と多項式コミットメントの知識を前提とする。

見せずに証明する

Aliceは、$f(x) = y$ となる値 $x$ を知っていると主張する。Bobはそれを確信したいが、$f$ を自分で実行したくない（コストが高いかもしれない）。Aliceも $x$ を明かしたくない（秘密かもしれない）。ゼロ知識証明は双方が望むものを実現する。

• 機密性：Aliceは $x$ を明かさない。
• 簡潔性：Bobの検証作業は $f$ の実行に比べてごくわずか。

この記事全体を通して使う例はこれだ。

$$f(x) = x^3 + x + 5$$

Aliceは、出力が35になる入力を知っていると主張する。記事の終わりまでに、この主張を1つの多項式の整除性チェックに変換する。各ステップでは実際の解 $x = 3$ を使うが、本物の証明ではこの値はBobから隠されている点に注意してほしい。

最初のステップは、計算を制約としてエンコードできるほど小さな断片に分解することだ。

フラット化：計算をゲートに分解する

$f(x) = 35$ を基本演算の列として書き直すのが目的だ。各演算は 結果 = 左 (演算) 右 の形を取る。数式を最小の演算にバラすイメージだ。

sym1 = x * x          // ゲート1：二乗
sym2 = sym1 * x        // ゲート2：三乗
sym3 = sym2 + x        // ゲート3：加算
out  = sym3 + 5        // ゲート4：定数の加算

各行がゲートだ。全体が算術回路になる。計算をゲートとしてエンコードするプロセスは算術化（arithmetization）と呼ばれ、SNARKパイプラインの最初の段階だ。フラット化された形式は $f(x)$ とまったく同じロジックをエンコードしている。表現が違うだけだ。

この例は三次方程式だが、フラット化のテクニックは任意の有界プログラムに一般化できる。有限体上の加算と乗算は、条件分岐、比較、ビット演算をエンコードするのに十分な表現力を持つ。たとえば、0か1の値を取る変数 $b$ があるとき、$y = 7b + 9(1 - b)$ という式は2つの値のどちらかを選ぶ。算術で構築した if/else だ。ループは固定の深さまで展開する。ゲート数はプログラムの複雑さに応じて増えるが、エンコードの仕組みは変わらない。

例に戻ろう。4つのゲートがあり、次のステップは各ゲートを検証者がチェックできる制約として表現することだ。

R1CS：内積としての制約

各ゲートは、単一の共有ベクトルに対する制約になる。この形式はRank-1 Constraint System（R1CS）と呼ばれる。ここから先のすべての算術は有限体 $\mathbb{F}_p$ 上で行われる。例を読みやすくするために小さな整数を使うが、実際には $p \sim 2^{255}$ だ。

ベクトル $\mathbf{s}$ は回路内のすべての変数を一列に並べたものだ。

$$\mathbf{s} = [1,\ x,\ \text{out},\ \text{sym1},\ \text{sym2},\ \text{sym3}] \tag{1}$$

$x = 3$ のとき：

$$\mathbf{s} = [1,\ 3,\ 35,\ 9,\ 27,\ 30]$$

先頭の $1$ は変数ではなく、$\text{ゲート } 4$ が三次方程式の「+ 5」をエンコードするときに使う定数項だ。すべての中間値が埋められたこのベクトルがウィットネス（witness）であり、証明者が計算したすべての情報を含んでいる。

各ゲートは次の形の制約になる。

$$(\mathbf{L}_i \cdot \mathbf{s}) \times (\mathbf{R}_i \cdot \mathbf{s}) = \mathbf{O}_i \cdot \mathbf{s} \tag{2}$$

ここで $\mathbf{L}_i$（左入力）、$\mathbf{R}_i$（右入力）、$\mathbf{O}_i$（出力）は行列 $L$, $R$, $O$ の $i$ 番目の行だ。各行ベクトルが $\mathbf{s}$ から適切な変数を「選択」する。

ゲート1と2：乗算のエンコード

$\text{ゲート } 1$ は $\text{sym1} = x \times x$ だ。式$(1)$の $\mathbf{s}$ を見ると、左で $x$ を、右で $x$ を、結果として $\text{sym1}$ を選択するベクトルが必要だ。

$$\mathbf{L}_1 = [0, 1, 0, 0, 0, 0] \quad \text{(selects } x \text{)}$$

$$\mathbf{R}_1 = [0, 1, 0, 0, 0, 0] \quad \text{(selects } x \text{)}$$

$$\mathbf{O}_1 = [0, 0, 0, 1, 0, 0] \quad \text{(selects sym1)}$$

確認：$(\mathbf{L}_1 \cdot \mathbf{s}) \times (\mathbf{R}_1 \cdot \mathbf{s}) = 3 \times 3 = 9 = (\mathbf{O}_1 \cdot \mathbf{s})$。うまくいく。

$\text{ゲート } 2$（$\text{sym2} = \text{sym1} \times x$）も同じ乗算パターンに従う。$\mathbf{L}_2$ が $\text{sym1}$ を、$\mathbf{R}_2$ が $x$ を、$\mathbf{O}_2$ が $\text{sym2}$ を選択する。

ゲート3と4：加算のエンコード

$\text{ゲート } 3$ には乗算がない。$\text{sym3} = \text{sym2} + x$ だ。これを $(\text{sym2} + x) \times 1 = \text{sym3}$ とエンコードし、加算を $\mathbf{L}$ ベクトルに組み込む。右辺は単に定数 $1$ だ。

$$\mathbf{L}_3 = [0, 1, 0, 0, 1, 0]$$

$$\mathbf{R}_3 = [1, 0, 0, 0, 0, 0]$$

$$\mathbf{O}_3 = [0, 0, 0, 0, 0, 1]$$

確認：$(27 + 3) \times 1 = 30$。$\text{ゲート } 4$（$\text{out} = \text{sym3} + 5$）も同じ仕組みで、$\mathbf{L}_4 = [5, 0, 0, 0, 0, 1]$ だ。確認：$(5 + 30) \times 1 = 35$。

ここがポイントで、加算は制約を増やさない。既存のゲートの $\mathbf{L}_i$ や $\mathbf{O}_i$ ベクトルに乗っかるだけだ。もし元の計算が純粋な加算ではなく $(\text{sym2} + x) \times 2$ だったとしても、ゲートは1つで済む。$\mathbf{L}_i$ が $\text{sym2} + x$ を選択し、$\mathbf{R}_i$ が定数 $2$ を選択し、加算のコストは追加されない。制約数を左右するのは乗算であり、加算はタダで付いてくる。

完全な行列

各行がゲート、各列が $\mathbf{s}$ のエントリに対応する。

有効なウィットネスは式$(2)$の4つのインスタンスすべてを同時に満たす。無効なウィットネス（中間値が間違っている、出力が違うなど）は少なくとも1つで失敗する。R1CSが機能することは確認できたが、各ゲートを個別にチェックする必要がある。4つのゲートに対して4回のチェック、それぞれ3つの内積と1つの乗算が必要だ。

QAP：内積から多項式へ

二次算術プログラム（QAP） 変換は、4つの個別のR1CSチェックを1つの多項式の整除性チェックに変換する。

その手法はこうだ。L, R, O行列の各列を取り、ラグランジュ補間で多項式に変換する。Verkleツリーの記事ですでに扱った内容だ。離散的な値を多項式の評価値としてエンコードする。同じ手法、異なるデータ。

具体的には、行列 $L$ の列 $j$ には4つの値（ゲートごとに1つ）がある。これらを点 $t = 1, 2, 3, 4$ での評価値として扱い、3次多項式 $L_j(t)$ を補間する。² たとえば $L$ の $x$ 列は値 $[1, 0, 1, 0]$ を持つので、$L_1(t)$ は点 $(1, 1),\ (2, 0),\ (3, 1),\ (4, 0)$ を通る一意な3次多項式だ。

L, R, Oのすべての列について同じことを繰り返す。結果：L, R, Oそれぞれに6つの多項式（$\mathbf{s}$ が6エントリなので、合計18個の多項式）。

各ゲート点 $t = i$ で内積 $\mathbf{L}_i \cdot \mathbf{s}$ に評価される単一の多項式が欲しい。これを可能にする便利な性質がある。多項式の重み付き和は、それ自体が多項式になるということだ。重みは係数をスケーリングして組み合わせるだけだ。そこで、ウィットネスのエントリ $s_j$ を列多項式の重みとして使える。

$$L(t) = \sum_{j=0}^{5} s_j \cdot L_j(t)$$

$$R(t) = \sum_{j=0}^{5} s_j \cdot R_j(t)$$

$$O(t) = \sum_{j=0}^{5} s_j \cdot O_j(t)$$

任意のゲート点 $t = i$ で、$L(i)$ はゲート $i$ の左辺の内積 $\mathbf{L}_i \cdot \mathbf{s}$ に評価される。$R(i)$ と $O(i)$ も同様だ。各辺につき1つの多項式（合計3つ）で、4つのゲートすべてを一度にエンコードしている。

有効なウィットネスではすべてのゲート制約が成り立つので、$L(t) \cdot R(t) - O(t) = 0$ が $t = 1, 2, 3, 4$ で成立する。この式を $T(t)$ と呼ぼう。これは $1, 2, 3, 4$ に根を持つ多項式だ。ターゲット多項式 $Z(t) = (t-1)(t-2)(t-3)(t-4)$ を定義しよう。これも同じ4点に根を持つ。

$T(t)$ と $Z(t)$ が同じ根を共有するので、$Z(t)$ は $T(t)$ を余りなく割り切る。証明者は多項式の除算を行い、次を満たす商多項式 $H(t)$ を求められる。

$$T(t) = H(t) \cdot Z(t) \tag{3}$$

ゲート制約が1つでも破られていれば、$T(t)$ は根を失い、除算に余りが出て、$H(t)$ は存在しなくなる。

1つの方程式がもたらすもの

Schwartz-Zippelの補題が式$(3)$を強力にする。ランダムな $\tau$ で両辺の等式を評価するだけで計算を検証でき、もし多項式が異なっていれば、偶然通過する確率は無視できるほど小さい。³ 1回のランダムな評価が $n$ 個のゲートチェックすべてを置き換える。本番の回路は数百万のゲートを持つ（Zcash Saplingは約150万、zkEVMロールアップは数千万）。SNARKの「Succinct（簡潔）」はここから来ている。

素朴なアプローチは $T(t)$ と $H(t)$ を検証者に送り、$\tau$ を選ばせることだ。しかしこれらの多項式の次数はゲート数に比例する。ネットワーク上のデータ量は $O(n)$、各検証者の評価作業も $O(n)$ だ。$n$ 個のゲートチェックを1回の評価に集約したのに、多項式を丸ごと送ればその利点が台無しになる。だから証明者が評価して点の値だけを送る形にしたい。

足りないもの

QAPと実際の証明の間には2つの問題が残っている。

証明者は $\tau$ を知ってはならない。 知っていれば、$Z(\tau)$（公開情報）を計算し、適当な $H(\tau)$ を選び、$T(\tau) = H(\tau) \cdot Z(\tau)$ と設定して、有効なウィットネスなしに式$(3)$を満たせてしまう。証明者は $\tau$ が何かを知らないまま $\tau$ で評価しなければならない。

証明者は回路の多項式に束縛されなければならない。 $\tau$ が隠されていても、証明者が実際のQAPの多項式を評価する義務はない。隠された点でチェックを通過する無関係な多項式を捏造できてしまう。

第2回では、これら2つの問題を解決する暗号技術を追加する。$\tau$ を隠すトラステッドセットアップ・セレモニー、証明者を回路の多項式に束縛するペアリングに基づくチェック、そして証明がウィットネスについて何も明かさないようにする秘匿化ステップだ。