この記事は、[PSE Learning Grant](https://pse.dev/en)にサポートされています。私は[PSE ZK Summer Contribution Program 2023](https://twitter.com/PrivacyScaling/status/1664436677073305602)でPlonkについて学びました。PlonkのVerifierは、n個のゲートが充足していることを$O(1)$の計算量で検査するために、ZeroTestと呼ばれるインタラクティブプルーフを使います。Verifier側が支払う計算量を$O(1)$に抑えられて便利ですが、ZeroTestのProverは巨大な多項式を巨大な多項式で割って商を計算する必要があるため、プルーフ生成に$O(n \log n)$の計算量が必要になります。これは、zkEVMなど、大量のゲート数を消費するサーキットを扱う際に問題になります。プルーフ生成を高速化するためには、プルーフ生成に掛かる計算量を$O(n)$に抑えられると便利です。SpartanやHyperPlonkで使われているZeroCheckと呼ばれるインタラクティブプルーフは、これを実現します。トレードオフは、Verifierが支払う計算量が$O(\log_2 n)$に増えてしまうことです。

| | ZeroTest | ZeroCheck |
| -------- | -------- | -------- |
| Prover | $O(n \log n)$ | > $O(n)$ |
| Verifier | $O(1)$ | < $O(\log_2 n)$ |
|安全性の根拠|因数定理|SumCheck|

この記事では、両者の仕組みを比較していきます。

# Citation
- [Plonk](https://eprint.iacr.org/2019/953)
- [David Wong によるPlonk解説動画](https://youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC&si=sz5IxJOw9JEgTtYN) とてもわかりやすい！
- [Spartan](https://eprint.iacr.org/2019/550) 17ページにZeroCheckの解説が載っています。
- [Bunz先生によるHyperPlonk解説動画](https://youtu.be/mZEXgoQL6xk?si=S-_-ybSgV7ILCCto&t=351) HyperPlonkのSumCheckの使い方はSpartanと同じなので、こちらの動画も勉強になります。

# ZeroTest
Plonkのゲートには左入力、右入力、出力の3つの数が紐づいています。掛け算ゲートの出力は、左入力と右入力を掛けたものでなければなりません。足し算ゲートの出力は左入力と右入力を足したものでなければなりません。すべてのゲートの左入力,右入力,出力の組み合わせが充足していることのプルーフを生成するために、まず各ゲートにIDを割り当てます。
次に、左入力ワイヤを表現する多項式を作ります。ω^ゲートのID をxに代入すると、そのゲートの左入力を返す多項式$X_a(x)$を作ります。次に、右入力ワイヤを表現する多項式を作ります。ω^ゲートのID をxに代入すると、そのゲートの右入力を返す多項式$X_b(x)$を作ります。次に、出力ワイヤを表現する多項式を作ります。ω^ゲートのID をxに代入すると、そのゲートの出力*-1を返す多項式$X_c(x)$を作ります。次に、多項式$q_L(x), q_R(x)$があり、この2つは、xにω^足し算ゲートのID を代入すると1、それ以外の場合は0になるものとします。多項式$q_M(x)$があり、これはxにω^掛け算ゲートのIDを代入すると1、それ以外の場合は0になるものとします。多項式$q_O(x)$があり、これはとりあえず常に1になるものとします。
ωは、ω^ゲートの数 =ω^0が成り立つ数とします。
そうすると、次が言えます。
$$q_L(x) \cdot X_a(x) + q_R(x) \cdot X_b(x) + q_O(x) \cdot X_c(x) + q_M(x) \cdot X_a(x) \cdot X_b(x) \equiv 0 \mod (x - ω^0)(x - ω^1)(x - ω^2)(x - ω^3)$$

## 因数定理
xにaを代入すると0になる多項式は、(x-a)を因数として持ちます。(x-a)を因数として持つ多項式は、xにaを代入すると0になります。つまり、0,1,2,3すべてのゲートが充足している場合、上の等式の左辺は(x - ω^0)と(x - ω^1)と(x - ω^2)と(x - ω^3)を因数として持ちます。つまり、次の等式を満たすようなH(x)が存在します。

$$q_L(x) \cdot X_a(x) + q_R(x) \cdot X_b(x) + q_O(x) \cdot X_c(x) + q_M(x) \cdot X_a(x) \cdot X_b(x) = H(x)(x - ω^0)(x - ω^1)(x - ω^2)(x - ω^3)$$

しかし、多項式2つの等価性を検証しようとすると、多項式2つの全係数が同じであるかを検証する必要があり、重たいです。これを簡潔に検証するために、ZeroTestが使えます。https://hackmd.io/_uploads/H1EanrbzC.svg

Proverは、X_a(x), X_b(x), X_c(x), H(x) にKZGでコミットし、コミットメントをVerifierへ送ります。Verifierはランダムな点sをサンプルし、Proverへ送ります。Proverは、X_a(s), X_b(s), X_c(s), H(s) のオープニングプルーフを作り、Verifierへ送ります。Verifierは、$$q_L(s) \cdot X_a(s) + q_R(s) \cdot X_b(s) + q_O(s) \cdot X_c(s) + q_M(s) \cdot X_a(s) \cdot X_b(s) = H(s)(s - ω^0)(s - ω^1)(s - ω^2)(s - ω^3)$$を検査します。

この図を見ると、Proverが$q_L(x) \cdot X_a(x) + q_R(x) \cdot X_b(x) + q_O(x) \cdot X_c(x) + q_M(x) \cdot X_a(x) \cdot X_b(x)$を$(x - ω^0)(x - ω^1)(x - ω^2)(x - ω^3)$で割った商$H(x)$を計算する必要があることがわかります。これをやるためにFFTが必要になり、重たい。

多項式2つをランダムな一点で評価した結果が一致することは、negligible probability を除いて、多項式2つの定義自体が一致していることを示す、ということは、[シュワルツジッペルの補題](https://tasusu.hatenablog.com/entry/2014/10/30/210828)から言えます。
これで、算術回路内のn個のゲートが充足していることを、1点sについての等式を見るだけで、検査できました。

# ZeroCheck
ZeroTestと同じことを、多項式の割り算を使わずに行うことができます。
各ゲートに対するIDを、2進数で振ることにします。

そうすると、全ゲートが充足しているかを確認する問題は、$q_L(x_0, x_1) \cdot X_a(x_0, x_1) + q_R(x_0, x_1) \cdot X_b(x_0, x_1) + q_O(x_0, x_1) \cdot X_c(x_0, x_1) + q_M(x_0, x_1) \cdot X_a(x_0, x_1) \cdot X_b(x_0, x_1) = 0$が全ての$x_0, x_1$で正しくなるかという問題に帰着します。ここで、x_0, x_1は、それぞれ各ゲートのIDの0ビット目、1ビット目とします。それぞれには0か1が入ります。

今後の解説を楽にするために、$f(x_0, x_1) := q_L(x_0, x_1) \cdot X_a(x_0, x_1) + q_R(x_0, x_1) \cdot X_b(x_0, x_1) + q_O(x_0, x_1) \cdot X_c(x_0, x_1) + q_M(x_0, x_1) \cdot X_a(x_0, x_1) \cdot X_b(x_0, x_1)$を定義します。

ここでシュワルツジッペルの補題を使える気がします。しかしシュワルツジッペルの補題が言っているのは、多項式が定義されている体上のランダムな点でその多項式を評価した結果が0になる && 多項式が定義されている体上にその多項式を0にさせないような点がある 確率が、多項式の次数/体のサイズ であるということです。今回検査したいのは、上記の等式が体上の全ての点で0になることではなく、00から11までの全ての点で0になることなので、直接シュワルツジッペルの補題を使うことができません。そのため、シュワルツジッペルの補題を使うためには、$f(x_0, x_1)$が0,0から1,1までの全ての点で0になる <=> $\bar f(t)$が体上の全ての点で0になる が成立するような$\bar f(t)$を定義する必要があります。

$$\bar f(t) = \sum_{x_0 \in \{0,1\}, x_1 \in \{0,1\}} f(x_0, x_1) \cdot eq(t_0, t_1, x_0, x_1)$$
ここで、t_0,t_1は、体上の数tをビット列で表したときの0ビット目、1ビット目とします。

eqの定義は、以下です。s=log_2(ゲートの数)とします。
この式は多変数一次多項式になります。t<2^s && t==xなら1を、t<2^s && t!=x なら0を、t>=2^sなら適当な値を返します。

ここから、もしも$\bar f(t) = 0$が体上の全てのtに対して言える場合、算術回路が充足していることが言えます。t<2^sの場合に関して$\bar f(t) = f(t_0, t_1)$が言えるので、算術回路が充足していなかった場合、t<2^sの中に$\bar f(t) = 0$を成り立たせないようなtが発生してくるため。

これでシュワルツジッペルの補題を使えるようになりました。ランダムな点$r_0$を選んで$\bar f(r_0) = 0$を検査することで、体上の全てのtで$\bar f(t)$が0であることが確率的に言えます。そしてそこから、算術回路が充足していることが言えます。

## SumCheck
ランダムな一点$r_0$で$\bar f(r_0)$を評価すると言っても、そのためにはシグマの中を全通り計算する必要があり、重たいです。これをSumCheck Protocolが解決します。

SumCheck Protocol というインタラクティブプルーフを使うと、多項式を2^v通りの組み合わせで評価した結果の総和が特定の数になることを、O(v)で検査できます。

### ラウンド1
Proverは、ラウンド1で、多項式gの1つ目の変数のみを自由変数とする多項式を作ります。その後の変数には全通りの組み合わせを代入しておきます。
$$g_1(X) := \sum_{x_2 \in \{0,1\}} \sum_{x_3 \in \{0,1\}} g(X, x_2, x_3)$$
Proverは、この多項式の定義をVerifierへ送ります。Verifierは、$H = g_1(0) + g_1(1)$を検査します。この検査が通れば、それはProverがmaliciousでなかったことを意味します。ProverがSumCheck Protocolに規定された通りの多項式を送ってきたことを意味します。検査が通れば、Verifierはプロトコルを続行します。Verifierはランダムチャレンジ$r_1$をProverへ送ります。

### ラウンド2
Proverは、ラウンド2で、多項式gの2つ目の変数のみを自由変数とする多項式を作ります。その後の変数には全通りの組み合わせを代入しておきます。その前の変数には前のラウンドで受け取ったチャレンジ$r_1$を代入しておきます。
$$g_2(X) := \sum_{x_3 \in \{0,1\}} g(r_1, X, x_3)$$
Proverは、この多項式の定義をVerifierへ送ります。Verifierは、$g_1(r_1) = g_2(0) + g_2(1)$を検査します。この検査が通れば、それはProverがmaliciousでなかったことを意味します。ProverがSumCheck Protocolに規定された通りの多項式を送ってきたことを意味します。これはシュワルツジッペルの補題から言えます。検査が通れば、Verifierはプロトコルを続行します。Verifierはランダムチャレンジ$r_2$をProverへ送ります。

### ラウンド3
Proverは、ラウンド3で、多項式gの3つ目の変数のみを自由変数とする多項式を作ります。その前の変数には前のラウンドで受け取ったチャレンジ$r_1, r_2$を代入しておきます。
$$g_3(X) := g(r_1, r_2, X)$$
Proverは、この多項式の定義をVerifierへ送ります。Verifierは、$g_2(r_2) = g_3(0) + g_3(1)$を検査します。この検査が通れば、それはProverがmaliciousでなかったことを意味します。ProverがSumCheck Protocolに規定された通りの多項式を送ってきたことを意味します。これはシュワルツジッペルの補題から言えます。検査が通れば、Verifierはプロトコルを続行します。Verifierはランダムチャレンジ$r_3$を生成します。

### 最終ラウンド
Verifierは、$g_3(r_3) = g(r_1, r_2, r_3)$ を検査します。この検査が通れば、$$H = \sum_{x_1 \in \{0,1\}} \sum_{x_2 \in \{0,1\}} \sum_{x_3 \in \{0,1\}} g(x_1, x_2, x_3)$$が言えます。

### まとめ
各ラウンドごとに、Hとg_1の関係性、g_1とg_2の関係性、g_2とg_3の関係性、、、をシュワルツジッペルの補題を用いて検査していき、最終ラウンドでg_3とgの関係性を検査する。そうするとそこから間接的にHとgの関係性がわかる。

$H := 0, g(x_0, x_1) := f(x_0, x_1)eq(t_0, t_1, x_0, x_1)$と置くと、ZeroCheckの検証にSumCheckが使えることがわかります。
$$0 = \sum_{x_0 \in \{0, 1\}}\sum_{x_1 \in \{0, 1\}}f(x_0, x_1)eq(t_0, t_1, x_0, x_1)$$をSumCheckに対して使うことで、算術回路が充足していることをO($\log_2$ゲートの数)で検査できます。ZeroTestと同じことを、多項式の除算を使わずに実現できました。
ZeroTestと比較すると、ラウンドの数が増えることがわかります。これはVerifierが行わなければならない計算の量が増えることを意味します。しかし、Proverは多項式の除算をする必要がないため、Proverが支払う必要のある計算の量は減ります。

# 注意
上記のプロトコルは、厳密には zero knowledge 性を満たしません。コミットする先の多項式の定義にランダムネスが混ざっていないため。HyperPlonkのペーパーでは、SumCheck Protocol の中で扱うg(x)の定義の中に秘密の情報が含まれている場合に、それを実際に厳密に隠す方法が解説されています。