この記事は、[PSE Learning Grant](https://pse.dev/en)にサポートされています。私は[PSE ZK Summer Contribution Program 2023]()でGroth16について学びました。Groth16がcompletenessを満たすことを理解するのは簡単ですが、Groth16がknowledge soundnessを満たすことを理解するのは比較的に難しいです。この記事では、Groth16のProverがチートできない理由を深掘りします。

# Citation
- [Groth16の原論文](https://eprint.iacr.org/2016/260.pdf)
- [Groth16のWeak Simulation Extractabilityを証明した論文](https://eprint.iacr.org/2020/811.pdf) この論文の中には、Groth16の knowledge soundness を原論文と別の方法で証明した章があります。

# 広告
PSEは今年も[PSE ZK Summer Contribution Program](https://pse.dev/en/programs)を開催するようです。3ヶ月間でゼロ知識証明の基礎を学べるプログラムです。参加費無料。去年の会場は東京大学でした。興味のある方は参加をおすすめします。

# NILP: Non-interactive linear proof
Groth16は、楕円曲線暗号を活用したプルーフシステムです。しかし、これのknowledge soundnessの証明のキモを掴むためには、楕円曲線暗号の詳細はとりあえず置いておくことができます。これは、NILPという抽象化のおかげです。

NILPは、プルーフシステムの種類です。プルーフ$\pi$を以下の式で計算できるプルーフシステムを、NILPと呼びます。
$$\pi = \Pi\sigma$$
各文字は行列です。$\sigma$は common reference string です。Common reference string, またはCRS は、trusted setup の際に生成される値のリストのことを指す業界用語?学術用語?です。

Groth16の定義を思い出すと、プルーフ$\pi$は$A,B,C$で構成されているのでした。そして、trusted setup は、以下の値を生成するのでした。

つまり、NILPの式を、以下のように具体化することができます。
$$\begin{bmatrix}A \\ B \\ C\end{bmatrix} = \Pi
\begin{bmatrix}\alpha \\ \beta \\ \gamma \\ \delta \\ x^0 \\ \vdots \\ x^{n-1} \\ \frac{\beta u_0(x) + \alpha v_0(x) + w_0(x)}{\gamma} \\ \vdots \\ \frac{\beta u_l(x) + \alpha v_l(x) + w_l(x)}{\gamma} \\ \frac{\beta u_{l+1}(x) + \alpha v_{l+1}(x) + w_{l+1}(x)}{\delta} \\ \vdots \\ \frac{\beta u_m(x) + \alpha v_m(x) + w_m(x)}{\delta} \\ \frac{x^0t(x)}{\delta} \\ \vdots \\ \frac{x^{n-2}t(x)}{\delta}\end{bmatrix}$$
今後の解説を楽にするために、行列$\Pi$の中の各要素に文字を割り当てておきます。
$$\begin{bmatrix}A \\ B \\ C\end{bmatrix} = \begin{bmatrix}A_\alpha && A_\beta && A_\gamma && A_\delta && A_{x,0} && \dots && A_{x,n-1} && A_{uvw,0} && \dots && A_{uvw,m} && A_{t,0} && \dots && A_{t,n-2} \\ B_\alpha && B_\beta && B_\gamma && B_\delta && B_{x,0} && \dots && B_{x,n-1} && B_{uvw,0} && \dots && B_{uvw,m} && B_{t,0} && \dots && B_{t,n-2} \\ C_\alpha && C_\beta && C_\gamma && C_\delta && C_{x,0} && \dots && C_{x,n-1} && C_{uvw,0} && \dots && C_{uvw,m} && C_{t,0} && \dots && C_{t,n-2}\end{bmatrix}
\begin{bmatrix}\alpha \\ \beta \\ \gamma \\ \delta \\ x^0 \\ \vdots \\ x^{n-1} \\ \frac{\beta u_0(x) + \alpha v_0(x) + w_0(x)}{\gamma} \\ \vdots \\ \frac{\beta u_l(x) + \alpha v_l(x) + w_l(x)}{\gamma} \\ \frac{\beta u_{l+1}(x) + \alpha v_{l+1}(x) + w_{l+1}(x)}{\delta} \\ \vdots \\ \frac{\beta u_m(x) + \alpha v_m(x) + w_m(x)}{\delta} \\ \frac{x^0t(x)}{\delta} \\ \vdots \\ \frac{x^{n-2}t(x)}{\delta}\end{bmatrix}$$

驚くべきことに、Groth16では、悪意を持ったProverでも、$A, B, C$を上記の方程式に従って生成する必要があります。この理由を理解するためには、trusted setup で生成される値が、楕円曲線上の点の中に隠されていることを思い出す必要があります。$\sigma = ([\sigma_1]_1, [\sigma_2]_2)$ であって $\sigma = (\sigma_1, \sigma_2)$ でないことに注目してください。


楕円曲線上の点の群の中では、点と点を掛け合わせることができません。群であって体ではないので、掛け算はそもそも定義されていません。そのため、Verifierは、Proverがどんな$A, B, C$を送ってきたとしても、そのいずれの中にも例えば$\alpha\beta$が含まれていないことを信頼できます。 $[\alpha]_1$ と $[\beta]_1$ を掛け合わせることはできないため。

NILPは、このGroth16の性質の上手い抽象化になっています。trusted setup で生成された値を、また別のtrusted setupで生成された値で掛けることができないという性質の。この記事では、この事実を上手く使い、正しいwitnessを知らないProverが、検証を通る$A, B, C$を生成できないことを示します。

# A, B
Groth16のプルーフ$\pi = (A, B, C)$は、以下の方程式が満たされるならばvalidです。
私が示したいのは、上記のGroth16検証方程式が満たされるのは、下記のQAP検証方程式が満たされる場合のみということです。
$$\sum_{i=0}^m a_iu_i(x) \cdot \sum_{i=0}^m a_iv_i(x) - \sum_{i=0}^m a_iw_i(x) \equiv 0 \mod t(x)$$
そのため、Groth16の検証を通るようなプルーフ$\pi$をProverが生成するためには、QAPの検証を通るようなwitness$a_i$をProverが知っている必要があります。

このことを示すために、左辺$A \cdot B$が生成する項を一つ一つ確認していきます。

## $\alpha$ and $\beta$
まず始めに、$\alpha^2$が掛かっている項から見ていきます。この項は発生します。NILP方程式は、$A$は$A_\alpha \alpha$を、$B$は$B_\alpha \alpha$をそれぞれ項として含んでいることを示しています。そのため、その2つを掛け合わせた $A \cdot B$は、$\alpha^2 A_\alpha B_\beta$を含んでいます。しかし、Groth16検証方程式の右辺を見ると、$\alpha^2$の掛かった項は存在しません。つまり、最低でも $A_\alpha = 0$ もしくは $B_\alpha = 0$であることが言えます。両方かもしれません。

しかし、Groth16検証方程式の右辺をもう一度確認すると、$\alpha\beta$が存在します。このことは、$A_\alpha = 0$ かつ $B_\alpha = 0$ である、つまり$A$も$B$も項として$\alpha$を含まないことがありえないことを示します。両方が0であった場合、$\alpha\beta$であるはずの項は$\beta$になってしまい、検証が通りません。

そのため、$A_\alpha = 0$ と $B_\alpha = 0$のどちらか一つが正しく、どちらか一つが間違っていることが言えます。

### $B_\alpha = 0$ を仮定した場合
$\alpha\beta$が掛かっている項を見ていきます。NILP方程式は、この項が次のような形をしていることを示しています。$\alpha\beta(A_\alpha B_\beta + A_\beta B_\alpha)$。右辺には、$\alpha\beta1$が存在します。そのため、$A_\alpha B_\beta + A_\beta B_\alpha = 1$であることが言えます。仮定から、右の項が0であることが言えます。そのため、左の項が1であることが言えます。そこから、次が言えます。$A_\alpha \neq 0$ かつ $B_\beta \neq 0$

次に、$\beta^2$が掛かっている項を見ていきます。NILP方程式は、この項が次のような形をしていることを示しています。$A_\beta B_\beta \beta^2 = 0$。Groth16検証方程式の右辺には$\beta^2$が掛かっている項は存在しません。そのため、$A_\beta$もしくは$B_\beta$が0であることが言えます。$B_\beta \neq 0$であることはすでに示したので、そこから$A_\beta = 0$であることが言えます。

### $A_\alpha = 0$ を仮定した場合
$\alpha\beta$が掛かっている項を見ていきます。NILP方程式は、この項が次のような形をしていることを示しています。$\alpha\beta(A_\alpha B_\beta + A_\beta B_\alpha)$。右辺には、$\alpha\beta1$が存在します。そのため、$A_\alpha B_\beta + A_\beta B_\alpha = 1$であることが言えます。仮定から、左の項が0であることが言えます。そのため、右の項が1であることが言えます。そこから、次が言えます。$A_\beta \neq 0$ かつ $B_\alpha \neq 0$

次に、$\beta^2$が掛かっている項を見ていきます。NILP方程式は、この項が次のような形をしていることを示しています。$A_\beta B_\beta \beta^2 = 0$。Groth16検証方程式の右辺には$\beta^2$が掛かっている項は存在しません。そのため、$A_\beta$もしくは$B_\beta$が0であることが言えます。$A_\beta \neq 0$であることはすでに示したので、そこから$B_\beta = 0$であることが言えます。

### Summing it up
ここまでの話をまとめると、 $$(A_\alpha = 0 \lor B_\alpha = 0) \land \lnot(A_\alpha = 0 \land B_\alpha = 0) \land ((A_\alpha = 0 \land B_\beta = 0) \lor (B_\alpha = 0 \land A_\beta = 0))$$

$A$は$\alpha$の掛かった項と$\beta$の掛かった項を両方含むことができません。$A$は、$\alpha$の掛かった項もしくは$\beta$の掛かった項を含みます。$B$は$\alpha$の掛かった項と$\beta$の掛かった項を両方含むことができません。$B$は、$\alpha$もしくは$\beta$のうち、$A$に含まれていない方を項として含みます。

$\alpha$と$\beta$はどちらも同じ分布からランダムにサンプルされたものなので、双方の文字がひっくり返っても今後の証明には影響しません。今後はとりあえず、$A$に含まれている方を$\alpha$、$B$に含まれている方を$\beta$と呼ぶことにします。

## $\delta$
### $\alpha\delta^{-1}$
Groth16検証方程式の左辺 $A \cdot B$ は$\alpha \delta^{-1}$の掛かった項を含みます。次のような形をしています。
$$A_\alpha\alpha\left( \sum_{i=l+1}^m B_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} + \sum_{i=0}^{n-2} B_{t,i}\frac{x^it(x)}{\delta}\right) = 0$$
これが0に等しいことは、Groth16検証方程式の右辺が$\alpha \delta^{-1}$の掛かった項を持っていないことからわかります。$\alpha \neq 0$ と $A_\alpha \neq 0$ から、最右辺が0であることが言えます。
$$\sum_{i=l+1}^m B_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} + \sum_{i=0}^{n-2} B_{t,i}\frac{x^it(x)}{\delta} = 0$$

私は、Groth16の原論文を読んでいるときに、下は$\alpha\delta^{-1}$の掛かった項を生成しないのかと不安になりました。
$$\left(\sum_{i=l+1}^mA_{uvw,i}\frac{\alpha v_i(x)}{\delta}\right)\left(TermsThatComeFromB\right)$$
しかしそんなことはありません。$\delta^{-2}$の章に理由が出てきます。

### $\beta\delta^{-1}$
Groth16検証方程式の左辺 $A \cdot B$ は$\beta \delta^{-1}$の掛かった項を含みます。次のような形をしています。
$$B_\beta\beta\left( \sum_{i=l+1}^m A_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} + \sum_{i=0}^{n-2} A_{t,i}\frac{x^it(x)}{\delta}\right) = 0$$
これが0に等しいことは、Groth16検証方程式の右辺が$\beta \delta^{-1}$の掛かった項を持っていないことからわかります。$\beta \neq 0$ と $B_\beta \neq 0$ から、最右辺が0であることがわかります。
$$\sum_{i=l+1}^m A_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} + \sum_{i=0}^{n-2} A_{t,i}\frac{x^it(x)}{\delta} = 0$$

私は、Groth16の原論文を読んでいるときに、下は$\beta\delta^{-1}$の掛かった項を生成しないのかと不安になりました。
$$\left(\sum_{i=l+1}^mB_{uvw,i}\frac{\beta u_i(x)}{\delta}\right)\left(TermsThatComeFromA\right)$$
しかしそんなことはありません。$\delta^{-2}$の章に理由が出てきます。

### $\delta^{-2}$
Groth16検証方程式の左辺 $A \cdot B$ は$\delta^{-2}$の掛かった項を含みます。次のような形をしています。$$\left( \sum_{i=l+1}^m A_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} + \sum_{i=0}^{n-2} A_{t,i}\frac{x^it(x)}{\delta}\right)\left( \sum_{i=l+1}^m B_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} + \sum_{i=0}^{n-2} B_{t,i}\frac{x^it(x)}{\delta}\right) = 0$$
これが0に等しいことは、Groth16検証方程式の右辺が$\delta^{-2}$の掛かった項を持っていないことからわかります。左の因数もしくは右の因数が0でないとこの等式は成立しません。しかしなんと、ここから左の因数と右の因数が両方0であることが言えます。

#### 左の因数が0であることを仮定した場合
$$\left( \sum_{i=l+1}^m A_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} + \sum_{i=0}^{n-2} A_{t,i}\frac{x^it(x)}{\delta}\right) = 0$$
この式を$\alpha, \beta, \delta$を変数として取る多項式と見ると、シュワルツジッペルの補題から次が言えます。
$$\sum_{i=l+1}^mA_{uvw,i}\frac{\alpha v_i(x)}{\delta} = 0$$
これは、$\alpha\delta^{-1}$の章で0になってほしかった式そのものです。そのため、左の因数が0であることを仮定すると、右の因数が0であることが言えます。

#### 右の因数が0であることを仮定した場合
$$\left( \sum_{i=l+1}^m B_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} + \sum_{i=0}^{n-2} B_{t,i}\frac{x^it(x)}{\delta}\right) = 0$$
この式を$\alpha, \beta, \delta$を変数として取る多項式と見ると、シュワルツジッペルの補題から次が言えます。
$$\sum_{i=l+1}^mB_{uvw,i}\frac{\beta u_i(x)}{\delta} = 0$$
これは、$\beta\delta^{-1}$の章で0になってほしかった式そのものです。そのため、右の因数が0であることを仮定すると、左の因数が0であることが言えます。

#### まとめ
- 左の因数が0 => 右の因数が0
- 右の因数が0 => 左の因数が0
- 左の因数が0 $\lor$ 右の因数が0

ここから、左の因数が0 かつ 右の因数が0 であることが言えます。
$$\sum_{i=l+1}^m A_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} + \sum_{i=0}^{n-2} A_{t,i}\frac{x^it(x)}{\delta} = 0$$$$\sum_{i=l+1}^m B_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} + \sum_{i=0}^{n-2} B_{t,i}\frac{x^it(x)}{\delta} = 0$$

## $\gamma$
### $\alpha\gamma^{-1}$
Groth16検証方程式の左辺 $A \cdot B$ は$\alpha \gamma^{-1}$の掛かった項を含みます。次のような形をしています。
$$A_\alpha\alpha\left( \sum_{i=0}^l B_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma}\right) = 0$$

これが0に等しいことは、Groth16検証方程式の右辺が$\alpha \gamma^{-1}$の掛かった項を持っていないことからわかります。$\alpha \neq 0$ と $A_\alpha \neq 0$ から、最右辺が0であることが言えます。
$$\sum_{i=0}^l B_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} = 0$$

私は、Groth16の原論文を読んでいるときに、下は$\alpha\gamma^{-1}$の掛かった項を生成しないのかと不安になりました。
$$\left(\sum_{i=0}^lA_{uvw,i}\frac{\alpha v_i(x)}{\gamma}\right)\left(TermsThatComeFromB\right)$$
しかしそんなことはありません。$\gamma^{-2}$の章に理由が出てきます。

### $\beta\gamma^{-1}$
Groth16検証方程式の左辺 $A \cdot B$ は$\beta \gamma^{-1}$の掛かった項を含みます。次のような形をしています。
$$B_\beta\beta\left( \sum_{i=0}^l A_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma}\right) = 0$$

これが0に等しいことは、Groth16検証方程式の右辺が$\beta \gamma^{-1}$の掛かった項を持っていないことからわかります。$\beta \neq 0$ と $B_\beta \neq 0$ から、最右辺が0であることがわかります。
$$\sum_{i=0}^l A_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} = 0$$

私は、Groth16の原論文を読んでいるときに、下は$\beta\gamma^{-1}$の掛かった項を生成しないのかと不安になりました。
$$\left(\sum_{i=0}^lB_{uvw,i}\frac{\beta u_i(x)}{\gamma}\right)\left(TermsThatComeFromA\right)$$
しかしそんなことはありません。$\gamma^{-2}$の章に理由が出てきます。

### $\gamma^{-2}$
Groth16検証方程式の左辺 $A \cdot B$ は$\gamma^{-2}$の掛かった項を含みます。次のような形をしています。$$\left(\sum_{i=0}^l A_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma}\right)\left(\sum_{i=0}^l B_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma}\right) = 0$$
これが0に等しいことは、Groth16検証方程式の右辺が$\gamma^{-2}$の掛かった項を持っていないことからわかります。左の因数もしくは右の因数が0でないとこの等式は成立しません。しかしなんと、ここから左の因数と右の因数が両方0であることが言えます。

#### 左の因数が0であることを仮定した場合
$$\sum_{i=0}^l A_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} = 0$$
この式を$\alpha, \beta, \gamma$を変数として取る多項式と見ると、シュワルツジッペルの補題から次が言えます。
$$\sum_{i=0}^lA_{uvw,i}\frac{\alpha v_i(x)}{\gamma} = 0$$
これは、$\alpha\gamma^{-1}$の章で0になってほしかった式そのものです。そのため、左の因数が0であることを仮定すると、右の因数が0であることが言えます。

#### 右の因数が0であることを仮定した場合
$$\sum_{i=0}^l B_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} = 0$$
この式を$\alpha, \beta, \gamma$を変数として取る多項式と見ると、シュワルツジッペルの補題から次が言えます。
$$\sum_{i=0}^lB_{uvw,i}\frac{\beta u_i(x)}{\gamma} = 0$$
これは、$\beta\gamma^{-1}$の章で0になってほしかった式そのものです。そのため、右の因数が0であることを仮定すると、左の因数が0であることが言えます。

#### まとめ
- 左の因数が0 => 右の因数が0
- 右の因数が0 => 左の因数が0
- 左の因数が0 $\lor$ 右の因数が0

ここから、左の因数が0 かつ 右の因数が0 であることが言えます。
$$\sum_{i=0}^l A_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} = 0$$$$\sum_{i=0}^l B_{uvw,i}\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} = 0$$

## ABまとめ
ここまでで0になることを示した項をすべて取り除くと、$A \cdot B$は以下のような式になります。
$$A \cdot B = (A_\alpha\alpha + \sum_{i=0}^{n-1} A_{x,i} x^i + A_\delta \delta)(B_\beta\beta + \sum_{i=0}^{n-1} B_{x,i} x^i + B_\delta \delta) = \alpha\beta + \sum_{i=0}^l a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) + C \cdot \delta$$

# C
左辺を移項すると、
$$(A_\alpha\alpha + \sum_{i=0}^{n-1} A_{x,i} x^i + A_\delta \delta)(B_\beta\beta + \sum_{i=0}^{n-1} B_{x,i} x^i + B_\delta \delta) - \alpha\beta + \sum_{i=0}^l a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) - C \cdot \delta = 0$$
この等式を成り立たせるようなCの作り方が一つだけ存在します。上の等式の左辺を変数$\alpha, \beta, \delta$に纏わる多項式としてみなすと、シュワルツジッペルの補題から、negligible probability を除いて
- 3つのランダムチャレンジのうち、$\alpha$のみが掛かっている項の係数 = 0
- 3つのランダムチャレンジのうち、$\beta$のみが掛かっている項の係数 = 0
- 3つのランダムチャレンジのいずれも掛かっていない項の係数 = 0

の3つが言えます。

## $\alpha$のみが掛かっている項の係数
$$A_\alpha\alpha \left( \sum_{i=0}^{n-1} B_{x,i} x^i \right) - \alpha\sum_{i=0}^l a_i v_i(x) - \alpha\sum_{i=l+1}^mC_{uvw,i} v_i(x) = 0$$
最後の項は$C\cdot \delta$から発生します。前述した理由から、$\alpha$が掛かっている必要があります。また、Groth16検証方程式はCに$\delta$を掛けているため、そこと打ち消し合うために$\delta^{-1}$も掛かっている必要があります。Groth16の trusted setup のうち、$\alpha$と$\delta^{-1}$が掛かっているものは下記の部分だけです。そのため、上の等式が正しいことがわかります。
$$\sum_{i=l+1}^mC_{uvw,i} \frac{\alpha v_i(x)}{\delta}$$

## $\beta$のみが掛かっている項の係数
$$B_\beta\beta \left( \sum_{i=0}^{n-1} A_{x,i} x^i \right) - \beta\sum_{i=0}^l a_i u_i(x) - \beta\sum_{i=l+1}^mC_{uvw,i} u_i(x) = 0$$
最後の項は$C\cdot \delta$から発生します。前述した理由から、$\beta$が掛かっている必要があります。また、Groth16検証方程式はCに$\delta$を掛けているため、そこと打ち消し合うために$\delta^{-1}$も掛かっている必要があります。Groth16の trusted setup のうち、$\beta$と$\delta^{-1}$が掛かっているものは下記の部分だけです。そのため、上の等式が正しいことがわかります。
$$\sum_{i=l+1}^mC_{uvw,i} \frac{\beta u_i(x)}{\delta}$$

## いずれも掛かっていない項の係数
$$\left( \sum_{i=0}^{n-1} A_{x,i} x^i \right)\left( \sum_{i=0}^{n-1} B_{x,i} x^i \right) - \sum_{i=0}^l a_i w_i(x) - \sum_{i=l+1}^m C_{uvw,i}w_i(x) - \sum_{i=0}^{n-2}C_{t,i}x^it(x) = 0$$
最後2つの項は、$C\cdot \delta$から発生します。trusted setup のうち、$\delta^{-1}$が掛かっていて、かつ$\alpha$も$\beta$も掛かっていない部分は、以下のみです。そのため、上の等式が正しいことがわかります。
$$\sum_{i=l+1}^m C_{uvw,i}\frac{w_i(x)}{\delta} + \sum_{i=0}^{n-2}C_{t,i}\frac{x^it(x)}{\delta}$$

## Cまとめ
ここまでで、3つの等式が成り立つことを示しました。
$$A_\alpha \left( \sum_{i=0}^{n-1} B_{x,i} x^i \right) = \sum_{i=0}^l a_i v_i(x) + \sum_{i=l+1}^mC_{uvw,i} v_i(x)$$
$$B_\beta \left( \sum_{i=0}^{n-1} A_{x,i} x^i \right) = \sum_{i=0}^l a_i u_i(x) + \sum_{i=l+1}^mC_{uvw,i} u_i(x)$$
$$\left( \sum_{i=0}^{n-1} A_{x,i} x^i \right)\left( \sum_{i=0}^{n-1} B_{x,i} x^i \right) = \sum_{i=0}^l a_i w_i(x) + \sum_{i=l+1}^m C_{uvw,i}w_i(x) + \sum_{i=0}^{n-2}C_{t,i}x^it(x)$$

$C_{uvw,i}$の値から$A_{x,i}$と$B_{x,i}$が決定し、$A_{x,i}$と$B_{x,i}$の積が$C_{t,i}$を決定することが見て取れます。右辺に居るwitnessが左辺を制約して、そのあと左辺で取った積が一周回って右辺を制約する。

上に挙げた3つの等式を同時に成り立たせるには、
$$C_{uvw,i} = a_i \hspace{1cm} \forall i \in (l+1) \dots m$$$$\sum_{i=0}^{n-1} A_{x,i}x^i = \sum_{i=0}^m a_i u_i(x)$$$$\sum_{i=0}^{n-1} B_{x,i}x^i = \sum_{i=0}^m a_i v_i(x)$$$$\sum_{i=0}^{n-2}C_{t,i}x^it(x) = h(x)t(x)$$
となるように$\Pi$の各要素を代入する必要があります。

これは正直なProverの振る舞いと一致します。

これで、悪意を持ったProverでも、オリジナルのGroth16ペーパーに記載されている方法で$A, B, C$を生成しなければならない理由がわかりました。

Groth16検証方程式の左辺$A\cdot B$がやっているのは、ちょうどQAPの検証方程式のように、算術回路内の掛け算ゲートの左入力ワイヤと右入力ワイヤを掛ける作業だとわかります。
$$\sum_{i=0}^m a_iu_i(x) \cdot \sum_{i=0}^m a_iv_i(x) - \sum_{i=0}^m a_iw_i(x) \equiv 0 \mod t(x)$$
あとは右辺$C$に掛け算ゲートの出力$\sum_{i=0}^ma_iw_i(x)$ と $\equiv 0 \mod t(x)$を示す$h(x)t(x)$を含めれば完成です。

QAPの検証方程式を満たすようなwitness $a_i$をProverが知らない限り、Groth16の検証が通らないことがわかりました。

# 辞書
# Soundness
Proverが新しくvalidなプルーフを作れるのは、validなwitnessがこの世に存在する場合のみ

# Knowledge Soundness
Proverが新しくvalidなプルーフを作れるのは、Proverがvalidなwitnessを知っている場合のみ
(このとき、Proverは、他のvalidなプルーフを一切知らないと仮定する)

# Non malleability
validなプルーフからまた別のvalidなプルーフを作ることができない
Non-malleableなプルーフシステムは、Re-randomizableでない。

# Re-randomizable
validなプルーフを受け取った人は、そのプルーフに細工をして、同じ public input / output に関しての別のプルーフを生成できる

# Strong Simulation Extractable
プルーフシステムが

- Knowlodge Sound である
- Non-malleable である

Proverが新しくvalidなプルーフを作れるのは、Proverがvalidなwitnessを知っている場合のみ
(このとき、Proverは、他のvalidなプルーフを知っているとする)

# Weak Simulation Extractable

プルーフシステムが

- Knowlodge Sound である
- Non-malleable でない
- Re-randomizable である

Proverが新しいプルーフを作れるのは、そのProverがvalidなwitnessを知っている場合 もしくは そのProverが同じpublic ioにまつわる古いプルーフを知っている場合