Halo2で使われている最新のzk-SNARKプロトコルPLONKの数学的解説

Table of Contents

概要

この記事では最新のzk-SNARKプロトコルである PLONK [1]の数学的解説を行います。この記事の多くはYouTubeで公開されている動画シリーズ [2][3]に基づいています。

解説

算術回路の変数割当

ゼロ知識証明は「何らかの条件を満たす変数の具体的な値を証明者が知っている」ということを検証者に対して伝える問題として定式化できる。例として $b - 1 = a^2$ という簡単な式を考えてみる。証明者はこの式を満たすような変数のペアを少なくとも１つ（たとえば $(a,b)=(5, 26)$ など）知っているということを( $a,b$ の具体的な値は公開せずに)検証者に伝えたい。

この問題を算術回路に変換することを考える。一般に上記のような証明したいステートメント（つまり、コンピュータ上で表現できる証明したい式）は足し算（加算）と掛け算（乗算）の回路を組み合わせたもの（算術回路 [4]）で表現できることが知られている。

なお[4]の資料ではブール演算が使われているが、これを ${0,1}$ のみの値の範囲を取る変数から ${0, 1, ..., p-1}$ の値を取るような有限体 $\mathbb{F}$ 上の変数に拡張することができる。

$b - 1 = a^2$ という式を、上記の加算と乗算で表現し直してみると以下の図のようになる。ここで $l_1, r_1, o_1, l_2, o_2$ は証明者が検証者にその値を明かさないプライベート変数であるとする。また、 $c$ は検証者と証明者が共有している定数であるとする。

上図を数式に落とし込むと以下のような4つの式になる。このうち後者2つ(3)(4)は「ある変数が同じものである」という条件を示す制約であり、「コピー制約」と呼ばれる。

$\begin{cases} {(1): l_1 * r_1 - o_1 = 0 } \\ {(2): l_2+1 - o_2 = 0}\\ {(3): o_1 = l_2} \\ {(4): l_1 = r_1} \end{cases}$

コピー制約と算術回路の式は別々に扱う必要がある。この記事では[1]の解説にならって算術回路の表現のみを先に扱い、コピー制約は後で別枠で扱う。コピー制約は個別のゲートだけではなくゲート間の関係を表すものであり、これを如何に効率的に表現するかがこのPLONKという論文の核心部分であるが、全体的なプロトコルの理解をするためにはコピー制約のないPLONKを理解する方がやさしいためである。

上記を満たす変数（証明者の知っている答え）は例えば $a = l_1 = r_1 = 5, o_1 = l_2 = 25, b = o_2 = 26$ である。

このようにして問題を算術回路に変換し、算術回路の入出力に変数を割り当てて関係を数式に分解して表現することができる。

算術回路の多項式化

上記で得られたそれぞれのゲートに関する式(1)(2)を以下のようなより一般的な形で表現することを考える。i番目のゲートは以下のような式として表現できる。

(5): $l_i * q_{L_i} + r_i * q_{R_i} + o_i*q_{O_i} + q_{c_i} + l_i * r_i * q_{M_i} = 0$

ここで $q_{L_i}, q_{R_i}, q_{O_i}, q_{M_i} \in \{0,1 \}$ はセレクタ変数であり、表現したいゲートに応じて定まる。また $q_{c_i} \in \mathbb{F}$ であり、これは定数値を表現している。例えば(1)の式を表現したい場合には加算のみを使い乗算と定数は使わないので $q_{L_1} = q_{R_1} = q_{O_1} = 1$ かつ $q_{M_1} = q_{c_1} = 0$ となる。また(2)の式では乗算と定数が使われているため $q_{L_2} = q_{R_2} = 0$ , $q_{O_2} = q_{M_2} = q_{c_2} = 1$ である。

実際代入して計算してみると

(1'): $5 * 0 + 5 * 0 + (-25) * 1 + 0 + 5 * 5 * 1 = 0$
(2'): $(25) * 1 + 0 * 0 + (-26)*1 + 1 + (-25) * 0 * 0= 0$

のような値の代入で(5)の式を両方満たせることがわかる。（正負の符号が怪しいところはセレクタ変数で調整することにしよう。セレクタ変数は公開されており証明者と検証者の間で合意ができていればどんな形式でも構わない）

次に、上記の変数 $q, l, r$ を多項式とみなすことを考える。例えば式(1)(2)では $l_1 = 5, l_2 = 25$ であるが、 $l$ を多項式と考えて $l(1) = 5, l(2) = 25$ となるような（一次）多項式が存在するはずである。同様に、ゲートがn個存在し式がn本の場合でも、これらのn点すべてで評価した時に正しい値を返すような多項式として補間することができる。これを $q, l, r$ すべてに対して行い、式(5)を以下のような多項式として表現し直せる。

(6): $f(x) = l(x) * q_{L}(x) + r(x) * q_{R}(x) + o(x)*q_{O}(x) + q_{c}(x) + l(x) * r(x)* q_{M}(x)$

これで式(1)(2)を満たす場合に 0として評価される単一の多項式 $f$ を定義することができた。なおここでは先述の通りコピー制約である(3)(4)は考慮していないことに注意する。また、この多項式がとして評価される定義域を $\mathbb{H} \subset \mathbb{F}$ とする。例えば上の例であれば $\mathbb{H} = \{1,2\}$ である。

多項式ベースの知識証明プロトコル: Schwartz-Zippelの補題

式(6)の多項式 $f$ は定義域 $\mathbb{H}$ の要素で評価すると0 になることから、以下のような消失多項式 $Z_{\mathbb{H}}(x) = (x-1)(x-2)...(x-|\mathbb{H}|)$ と商多項式 $t(x)$ を用いて $f(x) = Z_{\mathbb{H}}(x) t(x)$ と書き直せる（実際には $x=1, 2, ...$ ではなく $x^{n} = 1$ の根が定義域になるが、ここでは連続する整数とする）。

証明者Pと検証者Vの間の以下のようなプロトコルを考える。式(6)の多項式 $f$ を非公開情報である多項式 $l, r, o$ と公開情報である多項式 $q$ に分けて考える。

Pは「多項式 $l, r, o$ それ自体を知らせることなくその多項式をコミットしてVに送信しておき、後からその多項式を特定の点で評価した際には『確かに事前にコミットされていた多項式であった』ということをVに納得してもらえるようなコミットメントスキーム $\text{com}$ (多項式コミットメントスキーム; PCS)」を用いて $l, r, o$ と $t$ をコミットして $\text{com}(l), \text{com}(r), \text{com}(o), \text{com}(t)$ をVに送る。
Vは乱数 $z \leftarrow \mathbb{F}$ を生成してPに送る。
Pは $l, r, o, t$ を点 $z$ で評価してVに送る。また $l, r, o, t$ のコミットメントが正しく点 $z$ で評価されていることの証明 $\pi$ もVに送る。
Vは $l(z) * q_{L}(z) + r(z) * q_{R}(z) + o(z)*q_{O}(z) + q_{c}(z) + l(z) * r(z) * q_{M}(z) = Z_{\mathbb{H}}(z) t(z)$ であることを手元で検証する。

4.にてVは $q$ と $Z_{\mathbb{H}}$ を知っているためそれを手元で $z$ で評価し、他の多項式 $l, r, o, t$ はPから送られてきた $z$ での評価値のみを知っているのでそれを使う。Vは $f$ 本体の値は知らないことに注意する。また、 $p(x) = f(x) - Z_{\mathbb{H}}t(x)$ と置くと、同じことではあるが「検証者がランダムに選んだ値に対して $p(z) = 0$ となるかを検証する問題」と言い換えることができることに注意する。

上記のようなプロトコルで、Pが $f$ を知っている場合には $t$ を正しく計算できるため、乱数 $z$ に対して $p(z) = 0$ が常に成立する。もしPが $f$ を知らない場合であっても偶然 $p(z) = 0$ が成立しPがVを欺くことに成功してしまう可能性がある。そのような確率が低いということを示すのが以下のSchwartz-Zippelの補題である。詳しくは[5]のブログを参照。

Schwartz-Zippelの補題

$p(x_1,\dots,x_n) \neq 0$ を体 $\mathbb{F}$ 上の $n$ 変数非ゼロ多項式とする。 $S$ を $\mathbb{F}$ の有限部分集合とし $r_1, \dots, r_n$ を $S$ から独立かつ一様ランダムに選ぶとする。すると $\mathrm{Pr}(p(r_1, \dots, r_n) = 0) \leq \frac{\mathrm{deg}(p)}{|S|}$ である。

プロトコルのプロトタイプと足りないもの

上記がPLONKの基本的なプロトコルであるが、いくつか問題点がある。

PCS(多項式コミットメントスキーム)が具体的にどんなものなのか分からない
変数コピー制約を満たさない

PCSは独立したプロトコルであるため、特定のPCSプロトコルを用いる必要はない。論文ではKZGコミットメントを使っているが、このKZGコミットメントは

トラステッドセットアップが必要である
ペアリングが可能な楕円曲線という新たな暗号学的仮定を必要とする

など問題があるため、例えばHalo2では他のPCSでこれを代替している。 KZGコミットメントについては詳しくは[6]を参照。

変数コピー制約については下記で別途説明する。

変数コピー制約の多項式表現

ある変数の組 $(a_1, a_2, a_3)$ に対して、この組のうち特定の変数同士が同じ値を取るということを、表現したいとする。変数 $a_1 = a_3$ が同じ値を取るということ（コピー制約）は $(a_1, a_2, a_3) = (a_3, a_2, a_1)$ という置換で表現できる。そして、この置換表現を算術回路と同様に多項式として表現すれば、上述のようなSchwartz-Zippelの補題を使った多項式同一性判定アルゴリズムが使えることになる。

$(a_1, a_2, a_3) = (a_3, a_2, a_1)$ を表現するためには

両辺に登場する変数の集合が正しく一致していること
両辺で入れ替えられている変数が意図したものであること ( $(a_1, a_2)$ ではなく $(a_1, a_3)$ が入れ替えられていること)

が満たされていることを知りたい。

1を表現するために、両辺に登場する変数に乱数を足してかけ合わせたものが一致するかどうかを考える。すなわち、ベクトル $v$ と乱数 $\alpha$ に対して $\prod_{i=1}^{3} (\alpha + v_i)$ を両辺で計算し、それらが一致することを調べれば、両辺のベクトルの要素の集合は一致していることが高い確率で示される。

2を表現するために、上記の乱数 $\alpha$ を使った式を少し改良する。置換 $\sigma$ はある変数の組の添字を別の添字に移す写像であるとする。例えば $\sigma(1) = 3$ であるとき上の変数の組の例で言えば $a_1 = a_3$ を表現しているとする。このような置換 $\sigma$ を使って、ベクトル $a$ と乱数 $\alpha, \beta$ に対して以下のような式を考える。

$\prod_{i=1}^{3} (\alpha + i\beta + a_i) = \prod_{i=1}^{3} (\alpha +\sigma(i)\beta + a_i)$

もしこの式が成り立つならば、置換 $\sigma$ で入れ替えられたaの変数は、高い確率で値が一致しているといえるということを以下で説明しよう。

この式を一般化して、n個のワイヤ変数( $w$ )が登場する一般の場合を考える。なお以下でn個ではなく3n個の式が必要な理由は、n個のワイヤ変数を表現する際に3つの入出力変数( $l, r, o$ )を使うためインデックスの空間を拡張する必要があるからだと思われる。

※それとは別に[7]によれば、変数を追加しないと多項式を評価した結果をPがVに渡した際にゼロ知識性が失われてしまうこともあるらしい（つまり、2回の多項式評価を行う際にはゼロ知識性を保持するためには3個分の変数が余分に必要になる(?)らしい）。

(7): $z_1 = \prod_{i=1}^{3n} (\alpha + i\beta + w_i), z_2 = \prod_{i=1}^{3n} (\alpha + \sigma(i)\beta + w_i)$
と定め、 $z_1 = z_2$ が成り立つかを調べる。

$z_1 = z_2$ が成り立つならば、乱数 $\alpha$ を $x$ に置き換えて多項式として表現し直し、
$P_1(x) = \prod_{i=1}^{3n} (x + i\beta + w_i), P_2(x) = \prod_{i=1}^{3n} (x + \sigma(i)\beta + w_i)$

と定めると $P_1(x) = P_2(x)$ も高い確率で成り立つ。

$P_1(x) = P_2(x)$ である時、以下の $x$ の根が一致したとする。

$w_i + i\beta = w_j + \sigma(j)\beta$

このとき、 $\beta$ がランダムであることから高い確率で $w_i = w_j, i = \sigma(j)$ であるとわかる。したがって、 $z_1 = z_2$ が成り立つならば最初に定めた置換の条件を満たしているのだと言える。

なお実際には (7) が単独で成り立つことを証明するのは検証者側の計算量の観点から困難なので、(i)最初は両辺が1であり(ii)両辺に新しい項が次々に掛け合わせられていき(iii)最終的にn個の変数について掛け合わせたものが(7)のようになる、ということを順番に証明することで、(7)の代わりの証明とする。

n個の再帰的な変数コピー制約多項式を定数個の式で表現する

$z_1 = \prod_{i=1}^{3n} (\alpha + i\beta + w_i), z_2 = \prod_{i=1}^{3n} (\alpha + \sigma(i)\beta + w_i)$ で使う $w$ を拡大することを考える。 $w$ の代わりに上でも使った実際の変数 $l(x), r(x), o(x)$ を使いたいので、[9]のようにインデックスを拡張して同様の議論が3つの変数でもできるようにする。

これによって $z_1, z_2$ は改めて以下のように定義できる。

$z_1 = \prod_{i=1}^{n} (\alpha + i\beta + l(i)) (\alpha + (n+i)\beta + r(i)) (\alpha + (2n+i)\beta + o(i))$
$z_2 = \prod_{i=1}^{n} (\alpha + \sigma(i)\beta + l(i)) (\alpha + \sigma(n+i)\beta + r(i)) (\alpha + \sigma(2n+i)\beta + o(i))$

しかし、上述のようにこの $z_1, z_2$ はそのまま計算することは難しい。そこで、代わりに以下のような仮想的なアルゴリズムから再帰的に定まる変数 $s_i$ を考える。

$z_1, z_2$ の一致を検証するアルゴリズム:
(a) $s_0 = 1$
(b) $s_{i+1} = s_{i} * \frac{ (\alpha + i\beta + l(i)) (\alpha + (n+i)\beta + r(i)) (\alpha + (2n+i)\beta + o(i))}{(\alpha + \sigma(i)\beta + l(i)) (\alpha + \sigma(n+i)\beta + r(i)) (\alpha + \sigma(2n+i)\beta + o(i)) }$
(c) $s_n = 1$

この(a)(b)の条件が満たされて $s_i$ が定まり、(c)で最後の $s_n = 1$ が成立するときには、 $z_1 = z_2$ が成り立つ。したがって(a)(b)(c)と同値な式で、 $z_1, z_2$ を検証者が直接計算するよりも少ない計算量で計算でき、かつゼロ知識性を保持できるものがあれば、それを使えばよいことになる。

実際そのような式は存在することが知られている。

まず、 $\omega^{n+1} = 1$ となる根を求めておく。補助的な多項式 $L_i(x), z_1(x), z_2(x), S_\text{ID}(x), S_{\sigma_1}(x), S_{\sigma_2}(x), S_{\sigma_3}(x), Z_{\mathbb{H}}(x)$ を以下のように定める。
$L_i(x)$ : $\delta_i(x) = \begin{cases} {0 \text{ if } x \neq i \cap x\in[n] } \\ { 1 \text{ if } x = i } \end{cases}$ となる関数を補完した多項式
$z_1(x) = L_1(x) + \sum_{i=1}^{n} L_{i+1}(x) \prod_{j=1}^{i} (\alpha + j\beta + l(j)) (\alpha + (n+j)\beta + r(j)) (\alpha + (2n+j)\beta + o(j))$
$z_2(x) = L_1(x) + \sum_{i=1}^{n} L_{i+1}(x) \prod_{j=1}^{i} (\alpha + \sigma(j)\beta + l(j)) (\alpha + \sigma(n+j)\beta + r(j)) (\alpha + \sigma(2n+j)\beta + o(j))$
$S_\text{ID}(x) = \sum_{i=1}^{n} i*L_i(x)$
$S_{\sigma_1}(x) = \sum_{i=1}^{n} \sigma(i)L_i(x)$
$S_{\sigma_2}(x) = \sum_{i=1}^{n} \sigma(n+i)L_i(x)$
$S_{\sigma_3}(x) = \sum_{i=1}^{n} \sigma(2n+i)L_i(x)$
$Z_{\mathbb{H}}(x) = \frac{Z_{\mathbb{H}}(x)}{x - \omega^{n+1}}$

これらを用いて、 $z_1 = z_2$ が成り立つような式を以下のように定める。

(a') $(z_1(x) - z_2(x))L_1(x) = 0 \text{ mod } Z_{\mathbb{H}}(x)$
(b') $(\alpha + S_\text{ID}(x)\beta + l(x)) (\alpha + S_\text{ID}(n+x)\beta + r(j)) (\alpha + S_\text{ID}(2n+x)\beta + o(j))z_1(x) - z_1(x \omega^{-1}) = 0 \text{ mod } Z_{\mathbb{H}}(x)$
(b'') $(\alpha + S_{\sigma_1}(x)\beta + l(x)(\alpha + S_{\sigma_2}(x)\beta + r(j)) (\alpha + S_{\sigma_3}(x)\beta + o(j))z_2(x) - z_2(x \omega^{-1}) = 0 \text{ mod } Z_{\mathbb{H}}(x)$
(c') $(z_1(x\omega^{-1}) - z_2(x\omega^{-1}))L_n(x) = 0 \text{ mod } Z_{\mathbb{H}}(x)$

(a'),(b')(b''),(c')は上記の(a),(b),(c)にそれぞれ対応している。

すべての制約をまとめて一つの式とする

算術回路の式(6)と上記の(a'),(b')(b''),(c')の5つの式を乱数を使って合成し１つの制約として表現し直すことができる。

詳しくは[3]の47:40のスライドを参照。

この制約に関して $l, r, o, z_1, z_2, t$ の6つの式に対するコミットメントと式評価を上述の「多項式ベースの知識証明プロトコル: Schwartz-Zippelの補題」で書いたようなプロトコルで行うことで、コピー制約を含めたPLONKの全体像が記述できたことになる。

まとめ

PLONKは [7]にあるように論文の詳細が専用のウェブサイト plonk.cafe にて公開レビューを受け何度か訂正されています。非常に新しい論文なので安全性の証明が十分であると認められたとはいえない状態ではあると思います。それでもCoinWitness[8]のような古くからあるアイデアの実現に向かって前進しているのは喜ばしいことだと思いました。