# Plonky2

Plonky2は次の特徴を持つSNARKsです。

**主な特徴**
- 回路で用いられる有限体のサイズが小さい(64bit)ので高速
- Trusted setupが不要(Transparent)
- Recursive proofが速い(M1 Macで0.2sくらい)

# Goldilocks field

Goldilocks fieldは

$$p = 2^{64} - 2^{32} + 1$$

を位数とする有限体$\mathbb{F}_p$で、plonky2で使われています。

Circomで標準的に使われるBN254は254bitで、四則演算にBigUintが必要なため64bitCPUでの計算効率が悪いという問題があります。一方でGoldilocks field 64bitなので、64bit CPUでネイティブ計算が可能なため計算が速いです。

しかしながら有限体の大きさが小さいとセキュリティが低下してしまう場合があります。SNARKsで標準的に使われるテクニックに、低次の多項式$f(x)$, $g(x)$をあるランダムな点$x$で両者評価し、一致していたら等しい、そうでなければ異なると判定するものがあります(Schwartz–Zippelの補題)。

誤判定してしまう確率は、多項式の次数を$d$としたとき、$\frac{d}{|\mathbb{F}_p|}$となります。従って、$\mathbb{F}_p$が小さいときはセキュリティが不十分になってしまいます。

このセキュリティを向上させるために、Schwartz–Zippelのテクニックを使う際は、

$$\frac{\mathbb{F}_p[X]}{X^2 - 7}$$

という拡大体を使います。これは128bitあるので、比較的安全です。

# FRI
plonky2はTrusted setupが不要です。これはplonkのKZG commitmentの代替としてFRIを利用しているからです。

FRIが何なのかを見る前に、KZG commitmentの役割について確認しておきます。

KZG commitmentでは、$f(x) = \sum_{i=0}^{d-1} a_ ix^i$のcommitmentは、setupを

$$(G, \alpha G,\alpha^2 G, \ldots , \alpha^{n-1} G )$$

としたときに、

$$[f(x)] := f(\alpha)G = \sum_{i=0}^{n-1} a_i \alpha^{i} G$$

となります。ここで$d \le n$である必要があることに注意してください。言い換えると、正しくcommitmentができている時点で、$f(x)$の次数が$n$次以下であることが保証されます。

このように、KZG commitmentは多項式がある次数以下であることを証明することができます。これはSchwartz–Zippelの補題を使う際に、健全性のエラーの$\frac{d}{|\mathbb{F}_p|}$が小さいことを保証する($d$が小さいことを保証する)ために必要です。

FRIではKZG commitmentの代わりに、$f(x)$のMerkle tree commitmentを利用して、$f(x)$が低次であることを証明します。

## FRIのアイデア
$f(x)$を最大で$n$次の多項式とします。

$f(x)$の$x^2$を全て$y$に置き換え、$g(x, y)$を作ります。つまり$g(x, x^2) = f(x)$となります。

検証者はランダムに選んだ$\beta$を証明者に渡し、証明者は$g(\beta, y)$を計算します。$g(x, y)$は$y$に関して$n/2$次以下の次数しか持ちません。そのため、$g(\beta, y)$は$n/2$次以下の1変数多項式になります。

この操作を繰り返すと、最終的に定数(多項式)になります。数点の$x$での評価を求め、全て同じであることを確認すれば、それは高い確率で本当の定数(多項式)です。

このようにして検証者は$f(x)$の次数が$n$次以下であることを検証することができます。

$f(x)$から$g(\beta, y)$が正しく構成されていることは、ランダムな点で複数回評価することで確認できます。証明者は検証者が要求した点における評価値をMerkle proofとともに返します。検証者は同一のcommitmentに対するMerkle proofであることを確認することで、やりとりの間に$f(x)$や$g(\beta, y)$がすり替えられることがないということを確認できます。

plonky2のproofサイズが大きいのは、proofにFRIのmerkle proofが含まれるためです。

# Recursive proof

plonky2はFRIベースの証明スキームであるため、再帰証明では回路内で大量のhashを計算する必要があります。

plonky2では、hash(poseidon hash)を一つのcustom gateとして処理できるために非常に高速な再帰証明が可能になっています。

https://github.com/mir-protocol/plonky2/blob/main/plonky2/src/gates/poseidon.rs

また、再帰証明に必要なほかの処理もcustom gateとして定義されており、再帰証明に$2^{12}$個の制約しか必要としません。