はじめに
Vitalikが最近GKRプロトコルを解説するこんな記事を書いていました。
引用しているニュース記事を読むと、Vitalikが作ったと読めなくもない（知ってか知らずか）感じの記事もありましたが、初出は20年近く前の論文です。
ちょうど勉強していたのもあって、簡単な解説記事を書いていこうかと思います。最終的にはイメージがわかれば良いくらいにしておこうかなと思います。
また、SumCheckプロトコルというGKRプロトコルの中で中核をなす概念があるんですが、こちらの解説は割愛します。（そのうち記事書くかも）
SumCheckプロトコル自体はそういうものがあるという前提で、簡単にSumCheckプロトコルが何かを書くと、以下の通り、ある多項式$g(x_1, x_2, \dots, x_v)$（$x_i$はバイナリ）の全てのパターンを足し合わせた答え$H$が本当に正しく計算されたかを確かめるプロトコルです。
$$
H \stackrel{?}{=}
\sum_{x_1 \in {0,1}}
\sum_{x_2 \in {0,1}}
\cdots
\sum_{x_v \in {0,1}}
g(x_1, x_2, \dots, x_v)
$$
ProverはHを正しく計算したということをVerifierに証明したい時に、変数が多いとVerifierは計算するのが大変（変数の数が$i$とすると、$2^i$パターンを全て加算）なので、この全パターン計算を圧縮し、少ない計算で$H$の値が正しいことを検証するプロトコルです。
※ 本記事の今後の議論では、ProverをP、VerifierをVとします。
1. 全体像
ある大きな回路をPが実行し、それが正しいことをVが回路全体の計算を再実行せずに確認したいとします。
Vは入力とどんな回路かは知っています。
下図の例でいうと、Pは回路の出力は41と主張します。（$y$: 出力値、$x_i$: 入力値、$W_j(k)$: レイヤーjのk番目のゲート）
簡略化した流れ
すごい簡略化すると、以下のような流れで検証します。
- Vは最後のゲートに入る入力をPに聞きます。（上図の例だと、21と20のゲート）
- Vはランダムにindexを選び、その入力をまた聞きます。（上図でindex 0を選んだとします。）
- 上記を繰り返します。
- 最後のレイヤーまで辿り着いたら、Vは入力値を知っているので最後のレイヤーで検証します。
上記がざっくりとしたら流れになっています。これならVは回路の全てを計算せずに回路の計算が正しくされたかをチェックできます。
もちろん上記の流れだと最後のところだけ帳尻合わせられて途中で嘘をつけるのですが、これをもう少し数学的に途中も嘘をつけないようにしています。
数式だけ出てもよく分からないので、まずは雰囲気はこんな感じと分かれば良いかなと思います。
特徴
GKRプロトコルは、以下のような特徴を持ちます。
- Verifier の計算量は $\mathrm{poly}(\log n)$ に抑えられる
- Prover は回路をもとに証明を構成する
- sumcheck を活用して各層の計算の整合性を検証する
- 最後は入力層の確認で完了する
先ほどの例に出した回路を再掲します。$n$とか$l$とかはこの後の章に出てきます。
2. 層状回路モデル
計算を深さ $d$ の層状回路で表すとします。各層を $G_i$（$i=0,\dots,d$）とし、$G_0$ が出力レイヤー、$G_d$ が入力レイヤーです。
レイヤー $i$ のゲート数を $n_i$、ブールインデックスの長さを $\ell_i$ とします。
レイヤー $i$ の $w$ 番目のゲートの値を $V_i(w)$ とします。
これをブールベクトル $w\in{0,1}^{\ell_i}$ に対応させ、多重線形拡張（MLE） $\widetilde{W}_i$ を考えます：
$$
\widetilde{W}_i:\mathbb{W}^{\ell_i}\to\mathbb{F}.
$$
ブール点 $w$ で $\widetilde{W}_i(w)=W_i(w)$ が成り立ち、ブール点以外では補間値が得られます。
MLEは以下で定義されます：
$$
\widetilde{V}i(z) = \sum_{u \in {0,1}^{\ell_i}} V_i(u) \cdot \prod_{j=1}^{\ell_i} \chi_{u_j}(z_j)
$$
ただし $\chi_0(t)=1-t$, $\chi_1(t)=t$ です。
これを簡単に説明すると、例えばG4のレイヤーで左からindexを0,1,2（本当はBoolのベクトルなので、00,01,10です）とします。
各ゲートのoutputが2,0,2とすると、この点を通るような多項式は下の図のようになり、これは$\widetilde{V}_4(z) = z^3 - z^2 - 2z + 2$（${V}_4$の4は4層目の意味）で表せます。このようにすると、本来はindex0,1,2でしか定義できてなかった点がその外でも値を取れるようになります。
3. レイヤー間の関係式
前章で説明した通り、各レイヤーでのゲートの値を表す式を
$$
W_i: {0,1}^{k_i} \to \mathbb{F}
$$
で表します。
これを多線形拡張したものを $\widetilde{W}_i: \mathbb{F}^{k_i} \to \mathbb{F}$ と書きます。
親ゲートとの関係
各ゲート $a \in {0,1}^{k_i}$ は、上層（$i+1$層）の2つの親ゲートから値を受け取ります。
この対応関係を次の写像で表します：
\text{in}_{1,i}, \text{in}_{2,i}: \{0,1\}^{k_i} \to \{0,1\}^{k_{i+1}}
すなわち、$\text{in}_{1,i}(a)$ は左の親ゲート、$\text{in}_{2,i}(a)$ は右の親ゲートを示します。
ワイヤ述語（Wiring Predicate）
ゲート $a$ が加算ゲートまたは乗算ゲートであることを判定する述語を次のように定義します：
\begin{aligned}
\text{add}_i(a,b,c) &=
\begin{cases}
1 & \text{if } (b,c) = (\text{in}_{1,i}(a), \text{in}_{2,i}(a)) \text{ & aが加算ゲート},\\
0 & \text{otherwise},
\end{cases} \\
\text{mult}_i(a,b,c) &=
\begin{cases}
1 & \text{if } (b,c) = (\text{in}_{1,i}(a), \text{in}_{2,i}(a)) \text{ & aが乗算ゲート},\\
0 & \text{otherwise}.
\end{cases}
\end{aligned}
これらを多線形拡張したものを $\widetilde{\text{add}}_i, \widetilde{\text{mult}}_i: \mathbb{F}^{k_i + 2k_{i+1}} \to \mathbb{F}$ とします。ここで$k_i$はゲート$a$の位置を表し、$2k_i$は$b$,$c$の位置を表します（2つあるので2倍になってます）。
多項式によるレイヤー間関係
上記の定義を用いると、層 $i$ の出力は層 $i+1$ のゲート値の線形・乗算的組み合わせとして次のように表せます：
\displaylines{
\widetilde{W}_i(z)
=
\sum_{b,c \in \{0,1\}^{k_{i+1}}}
\Big[
\widetilde{\text{add}}_i(z,b,c)
\big(
\widetilde{W}_{i+1}(b) + \widetilde{W}_{i+1}(c)
\big) \\
+
\widetilde{\text{mult}}_i(z,b,c)
\big(
\widetilde{W}_{i+1}(b) \cdot \widetilde{W}_{i+1}(c)
\big)
\Big].
}
この式は、各層の出力値が上層のゲート値に依存することを多項式として表しています。
ちょっと分かりづらいですが、MLEであることを一旦無視して、例えば$z$にあるゲート$a$のindexを入れます。それが仮に加算ゲートかつ$b,c$がaの入力だとしたら、$add(z,b,c)$は1になって、 $W(b),W(c)$はそれぞれそのゲートの入力値になるので、結果として加算ゲートの計算が結果として出力されます。
4. 検証プロトコル
前節でレイヤー間の関係式が分かったので、その関係が正しいかどうかを検証します。
層 $i \to i+1$ の検証ステップでは、Verifier はランダム点 $r_i \in \mathbb{F}^{k_i}$ を選び、
次の恒等式が成り立つことを sum-check プロトコルで確認します。
\displaylines{
f^{(i)}_{r_i}(r_b, r_c) = \widetilde{\text{add}}_i(r_i,b,c)
\big(
\widetilde{W}_{i+1}(b) + \widetilde{W}_{i+1}(c)
\big) \\
+
\widetilde{\text{mult}}_i(r_i,b,c)
\big(
\widetilde{W}_{i+1}(b) \cdot \widetilde{W}_{i+1}(c)
\big) \\
\widetilde{W}_i(r_i)
=
\sum_{b,c \in \{0,1\}^{k_{i+1}}} f^{(i)}_{r_i}(r_b, r_c)
}
- Verifier は右辺が Prover の主張する $\widetilde{W}_i(r_i)$ に一致するかを sum-check により確認します。
- sum-check の最後に、Verifier はランダム点 $(r_b, r_c) \in \mathbb{F}^{2k_{i+1}}$ を選び、 $f_{r_i}(r_b, r_c)$ の評価を行います。
- この評価には $\widetilde{W}_{i+1}(r_b)$ と $\widetilde{W}_{i+1}(r_c)$ が必要ですが、これらは「2点評価を1点評価に還元する」テクニックを使って、最終的に $\widetilde{W}_{i+1}$ の1点評価 $\widetilde{W}_{i+1}(r_{i+1})$ に帰着されます。
- このプロセスを繰り返し、最下層（入力層）まで到達すれば、Verifier は自力で $\widetilde{W}_d$ を計算でき、Prover の主張全体を検証できます。
まとめ
下手な回路図と色々省略したざっくりとした説明になりましたが、上記がGKRプロトコルの基本的な流れになっています。計算量は$d\cdot log(S)$オーダーで、元の回路サイズ$S$分の計算量が必要だったものが圧縮できました。