# ZK Plonk

https://o1-labs.github.io/proof-systems/plonk/zkpm.html
https://minaprotocol.com/blog/a-more-efficient-approach-to-zero-knowledge-for-plonk
https://mirprotocol.org/blog/Adding-zero-knowledge-to-Plonk-Halo
https://zcash.github.io/halo2/design/protocol.html
https://twitter.com/yezhang1998/status/1547068196783476736
https://github.com/zcash/halo2/pull/219
https://github.com/zcash/halo2/pull/316
https://github.com/arkworks-rs/groth16/blob/765817f77a6e14964c6f264d565b18676b11bd59/src/r1cs_to_qap.rs

What is a domain: $D=\{\omega^0,\ldots,\omega^{n-1}\}$, defined by a selection of a primitive root

What is a coset? A set $gH$ for $g\in G, H<H$

For us $G$ is $\mathbb{F}^*$, and $D$ is $H$

So any $g\in\mathbb{F}^*$ gives a coset $gD=\{g\omega^0,\ldots,g\omega^{n-1}\}$
IF $g\notin D$, $gD$ has no $1$:
$g\omega^i=1 \implies g^n\omega^{in}=1^n \implies g^n=1$

### Coset FFT
To evaluate $p\in\mathbb{F}[X]$, $deg(p)=n-1$ on $gD$
For $p(X)=p_{n-1}X^{n-1}+p_{n-2}X^{n-2}+\ldots+p_0$
just FFT $p^g(X)=(p_{n-1}g^{n-1})X^{n-1}+(p_{n-2}g^{n-2})X^{n-2}+\ldots+p_0$

### Coset iFFT
To interpolate $p$ from evaluations overt the coset $gD$ just iFFT the polynomial $p^{g^{-1}}(X)=(p_{n-1}(g^{-1})^{n-1})X^{n-1}+(p_{n-2}(g^{-1})^{n-2})X^{n-2}+\ldots+p_0$

### Vanishing polynomial of the domain evaluated over a coset
$$Z_D(X)=X^n-1$$
$$Z_D(g\omega^i)=(g\omega^i)^n-1=g-1$$

### Vanishing polynomial of the domain evaluated over a coset of a larger domain

$$\omega^{2N}=1=\omega^0$$

$$D_{2N}=\{\omega^0,\omega^1,\ldots,\omega^{2N-1}\}$$

$$D_N=\{\omega^0,\omega^2,\ldots,\omega^{N-1}\}$$

$$Z_{D_N}(X)=X^N-1$$

$$Z_{D_{2N}}(X)=X^{2N}-1$$

$$gD_{2N}=\{g\omega^0,\ldots,g\omega^{2N-1}\}$$

$$Z_{D_N}(gD_{2N})=\{{(g\omega^0})^N-1,\ldots,(g\omega^{2N-1})^{N}-1\}=\{g^N-1,(g\omega)^N-1,\ldots,g^N-1,(g\omega)^N-1\}$$