# PlonK

PlonK(と、その拡張版のTurboPlonK)は次のような特徴を持っています。

- universal setup
- custom gateが使える
- lookupが使える

それぞれ解説していきます。

1つ目のuniversal setupは、trusted setupで生成されたデータがどのような回路に対しても普遍的に利用できることを意味します(ただし、回路のサイズごとに別のtrusted setupが必要になります。様々なサイズのtrusted setupのデータが網羅されているhttps://github.com/weijiekoh/perpetualpowersoftau などを使うことができます)。

2つ目のcustom gateは、回路内に繰り返し現れる計算をgateとして定義することで、proofの生成速度を向上させる手法です。例えばhash関数の計算をcustom gateにすることで、大量のhash関数が含まれる回路のproof生成速度を向上させることができます。

3つ目のlookupは、値が予め決められたある集合の中に含まれることを効率的に証明する手法です。例えば$x$が$0 \le x < 8$であることを、集合$\{0, 1, ..., 7 \}$に対するlookupで証明することができます(range check)。

# PlonKのアイデア

PlonKで基本となる概念は「表」です。回路内の変数は表の中のセルに対応します。例えば下の図は$a + b = c$を証明する回路の表です。

| $a$ | $b$ | $c$ |
| ---- | ---- | ---- |
| 1 | 1 | 2 |
| 3 | 1 | 4 |
| 2 | 3 | 5 |
| 6 | 3 | 9 |

全ての行において、$a + b = c$の関係が成り立っていることが確認できると思います。

それぞれの列を多項式で表してみます。

1列目を$f_a(1) = 1$, $f_a(2)=3$, $f_a(3)=2$, $f_a(4) = 6$となるような多項式$f_a$で、
2列目を$f_b(1) = 1$, $f_b(2)=1$, $f_b(3)=3$, $f_b(4) = 3$となるような多項式$f_b$で、
3列目を$f_c(1) = 2$, $f_c(2)=4$, $f_c(3)=5$, $f_c(4) = 9$となるような多項式$f_c$で表します。

すると上の表の関係は

$$f_a(x)+f_b(x)=f_c(x)(x=1,2,3,4)$$

という多項式で表すことができます。

PlonKのアイデアは、verifierがランダムな点$x = \zeta$を選び、その点で上の式が成り立っているか確認することで、効率的に「表」全体が正しいことを検証するというものです。

ただし、$x=1, 2, 3, 4$からランダムに選んでしまうと、例えば$f_a(1)$の値を変えても$\zeta \neq 1$である限り検出できないので不正ができてしまいます。

そこで、$x=1, 2, 3, 4$の外の「全ての$x$」から$\zeta$をランダムに選ぶことにします(実際は$x$は有限体の元なので、その有限体の全ての元の中から選ばれます)。

$f_a(x)+f_b(x) -f_c(x)$は$x=1,2,3,4$において$0$になる、すなわち根を持つので、ある多項式$D(x)$が存在して

$$f_a(x)+f_b(x) -f_c(x) = (x-1)(x-2)(x-3)(x-4) D(x)$$

と書くことができます。

この状態で、verifierはランダムな点$x = \zeta$を選び

$$f_a(\zeta)+f_b(\zeta) -f_c(\zeta) = (\zeta-1)(\zeta-2)(\zeta-3)(\zeta-4) D(\zeta)$$

が成り立つことをチェックします。ただし、verifierは$f_a(\zeta)$などの値は知らないので、proverは「$f_a(x)$を$x=\zeta$で評価すると$f_a(\zeta)$になる」ということを別途証明する必要があります。これは後で述べるopening proofで行うことができます。

以上の工夫によって、例えば$f_a(1)$の値のみ変えるような不正に関しては、根の位置が変わり恒等式が成り立たなくなるため、不正を検出することができます。

詳しくは以下の記事のSchwartz–Zippelの補題の項目を御覧ください。

https://zenn.dev/qope/articles/f94b37ff2d9541#schwartz%E2%80%93zippel%E3%81%AE%E8%A3%9C%E9%A1%8C

これにより、元々は4行あった足し算が、1行分の計算で検証できるようになりました。この方法を使えば、行数が幾ら多くても1行分の計算で検証できます。

掛け算の場合も同様に可能ですが、では足し算と掛け算が混合している場合はどうでしょうか？

PlonKではselectorというものを用いて、演算を切り替えます。

$$ q_{L} a + q_{R} b + q_{O}c + q_{M}ab + q_{C} = 0 $$

この式の$q_{L}$, $q_{R}$, $q_{O}$, $q_{M}$がselectorで、これらの値を調整することで足し算と掛け算の両方に対応することができます。例えば$ab=c$という制約を課したい場合は、$q_{L} = q_{R} = q_{C} = 0$, $q_{O} = -1$　, $q_{M} = 1$となります。

$q_{C}$は定数項を扱うのに使います。

このとき表は例えばこんな感じになります

| $a$ | $b$ | $c$ | $q_L$ | $q_R$ | $q_O$ | $q_M$ | $q_C$ |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 1 | 1 | 2 | 1 | 1 | -1 | 0 | 0 |
| 2 | 3 | 6 | 0 | 0 | -1 | 1 | 0 |

一行目は$1 + 1 = 2$で、二行目は$2\times 3 = 6$です。

同様に、どれだけ複雑な演算であっても適切に恒等式を設定することで、一行で表現できることがわかると思います。これをcustom gateと言います。custom gateは複雑な回路を少数の行数で表現するための強力な武器です。ただしcustom gateは検証のコストを上げるので注意が必要です。検証時には1行分の計算をする必要があるので、複雑な制約であるほど、列の個数が増えるほど検証のコストは増えます。

## permutation argument

permutation argumentは、表の中の(複数の)セルの値が等しいという制約を掛けるための手法です。
例えば次の表は最初に出てきた足し算の表を使ってフィボナッチ数列を計算する例ですが、このときにpermutation argumentが必要になります。

| a | b | c |
| ---- | ---- | ---- |
| 1 | 1 | 2 |
| 1 | 2 | 3 |
| 2 | 3 | 5 |
| 3 | 5 | 8 |

この表にはある行の2列目のセルが、その下の行の1列目のセルであり、ある行の3列目のセルが、その下の行の2列目のセルであるという制約があります。

より簡単な例で、permutation argumentの作り方を見てみます。

|a|
| --- |
|2|
|2|
|3|
|4|

いま、1行目のセルと2行目のセルが等しいことを証明する場合、先ほどと同様に$a$の多項式を作ります。

$$f_a(1) = 2, f_a(2)=2, f_a(3)=3, f_a(4) = 4$$

そして、

$$
\begin{align*}
& \prod_{x=1}^{4} (f_a(x) + \beta x + \gamma ) = \\
& ( f_a(1) + \beta + \gamma)( f_a(2) + 2\beta + \gamma)( f_a(3) + 3\beta + \gamma)( f_a(4) + 4\beta + \gamma)
\end{align*}
$$

という量を作ります。ここで$\beta$と$\gamma$はランダムに選んだ値です。

次に1行目と2行目を入れ替えた

$$
\begin{align*}
& \prod_{x=1}^{4} (f_a(x) + \beta s(x) + \gamma ) = \\
& ( f_a(1) + 2\beta + \gamma)( f_a(2) + \beta + \gamma)( f_a(3) + 3\beta + \gamma)( f_a(4) + 4\beta + \gamma)
\end{align*}
$$

という"同じような"値も作ります。

ここで$s(x)$は同じ値のセルの行数に対応する$x$に関しては入れ替えて、それ以外の$x$はそのまま出力する関数です。この2つの値が等しいことと、$f_a(1) = f_a(2)$が同値であることは直感的に理解できると思います^[正確には$\beta$, $\gamma$が特定の値になったとき(例えば両方$0$)、成立しないので必要十分条件では無いですが、確率的にそのような事象はめったに起こらないです]。

さて、これを使ってpermutation argumentを証明したいですが、このままだと検証時に行数分の積を計算する必要があり、効率的に実行できません。そこで、新たに$z$という関数を定義します。

$$
\begin{align}
& z(1) = 1 \\
& z(x) (f_a(x) + \beta x + \gamma ) = z(x+1) (f_a(x) + \beta s(x) + \gamma )
\end{align}
$$

ここで$z(x+1)$が$x = 4$のとき$z(1)$に戻ると約束します(この性質は$1, 2, 3, 4$では無く、有限体の生成元のべき乗を使うことで満たされます)。

すると、上記の$z(x)$が存在することがpermutation argumentと同値であることがわかります。

具体的には$z(2), z(3), z(4), z(1)$を順に計算すると

$$z(1) = \frac{\prod_{x=1}^{4} (f_a(x) + \beta x + \gamma )}{\prod_{x=1}^{4} (f_a(x) + \beta s(x) + \gamma )}$$

となり、これが$1$と一致するという条件からpermuation argumentが満たされることが分かります。

上記2式のうち、前者$z(1) = 1$はopening proofというもので証明できます(後述)。

また後者$z(x) (f_a(x) + \beta x + \gamma ) = z(x+1) (f_a(x) + \beta s(x) + \gamma )$は多項式の恒等式なので、custom gateのときと同様に、$(x-1)(x-2)(x-3)(x-4)$で割り、ランダムな点$x = \zeta$で評価することで、一回の計算で検証できます。

このように、Plonkではcustom gateとpermutation argumentを組み合わせることで様々な回路(制約)を表すことができ、またどれだけ多くの行があっても、定数回の計算で検証することができます。

## Opening proof
最後に、解説を先延ばしにしていたopening proofについて解説します。

Opening proofとは、ある多項式$f(x)$のcommitment $Commit(f)$と値$a$, $b$に対して、$f(a) = b$の関係が成り立つことを証明することができるプロトコルです。

PlonkではOpening proofにKate commitmentが用いられます^[ちなみに、plonky2ではKate commitmentの代わりにFRIが用いられます]。

Kate commitmentについては以下の記事をご参照ください。

https://zenn.dev/dantehrani/articles/e8882dd72b514e

これを使うと、「$x=\zeta$をランダムに選び、その点で等式が成り立っていることを確認する」ということが可能になります。

例えば、$f_a(x)+f_b(x) -f_c(x) = (x-1)(x-2)(x-3)(x-4) D(x)$を証明したいとき、次の手順でこれを行うことができます。

1. proverは$Commit(f_a)$, $Commit(f_b)$, $Commit(f_c)$, $Commit(D)$をverifierに渡す。
2. verifierは$x=\zeta$をランダムに選び、proverに送る。
3. proverは$f_a(\zeta)$, $f_b(\zeta)$, $f_c(\zeta)$, $D(\zeta)$のOpening proofを作り、verifierに渡す。
4. verifierはOpening proofを検証するとともに、$f_a(\zeta)+f_b(\zeta) -f_c(\zeta) = (\zeta-1)(\zeta-2)(\zeta-3)(\zeta-4) D(\zeta)$を確認する。

4でverifierは$(\zeta-1)(\zeta-2)(\zeta-3)(\zeta-4)$を計算する必要があり、これは直接計算しようとすると行数分(この場合は4)の計算が必要になります。ただし、これは自然数ではなく有限体を用いることで$\Pi_i(x-w^i) = x^n -1$という公式を使うことができ、効率的に計算することができます。

なお、2番目の手順が必要なせいで、verifierからproverへの通信が必要になります。これは、verifierが乱数を選ぶ代わりに、proverが疑似乱数を使うことで無くすことができます。これをFiat-shamir変換といいます。詳しくはこの記事の該当箇所をご参照ください。Fiat-shamir変換後は、proverからverifierへの一方通信となり、non-interactiveなプロトコルになります。

https://zenn.dev/qope/articles/8d60f77e3a7630#fiat-shamiar-trasform

以上はcustom gateを例にとって説明しましたが、permutation argumentの場合も同様に証明できることがお分かり頂けると思います。

## 実際のplonkとの相違点
以上はplonkのざっくりとしたアイデアですが、plonkの原論文から一部変更して説明したところがあります。以下がその相違点です。

1. $x$は有限体の元で、全ての演算は有限体上で行われます
2. 複数のKate commitmentの乱数結合を取り、2回のペアリングで検証できるように工夫されています
3. opening proofの回数を削減するために、linearizationのテクニックが使われています

## 補足
Kate commitmentはuniversal setupです。即ち、trusted setupはopenする多項式に依存しません。これがplonkがuniversal setupである理由でもあります。Kate commitmentはuniversal setupなので、plonkもその性質を継承するのです。なお、Kate commitmentをFRIに変えたplonky2はtrusted setupすらも不要になります。これはFRIがtrusted setup不要だからです。

# まとめ

まとめると、Plonkは、次の方法で回路の証明を生成します。

- 回路に割り当てられる値を「表」にして、列ごとに多項式を作る
- 各行の制約はcustom gateで表すことができ、多項式の恒等式として表現される
- セルの値が等しいという制約は、permutation argumentで表すことができ、これも多項式の恒等式として表現される
- 多項式の恒等式は、Kate commitmentを使ってランダムな点で多項式を評価し、その点で恒等式を検証することで効率的に検証することができる。