# Plonky2 summary notes

Quick notes about [Plonky2](https://github.com/0xPolygonZero/plonky2) from [ZK Whiteboard Sessions – Module Thirteen: Fast Recursion with Plonky2](https://www.youtube.com/watch?v=-pucWUDn5Hw)

**Disclaimer**:
This summary note is intended solely for educational and informational purposes. While the notations and terminology are primarily adopted from the original paper, certain modifications or reinterpretations may be made for clarity or brevity. No claim of ownership is made over the original content, and this note does not serve any commercial purpose. It is provided in good faith, and the author assumes no liability for any misunderstandings, misinterpretations, or legal claims that may arise from its use. Any concerns regarding the original work should be directed to the original authors or publishers.

### Problem of recursion when verifying ECC-based ZK proof

$\mathbb{F}_q$ => base field of ECC $E$
$\mathbb{F}_p$ => scalar field

V of groth16 proof uses both field

=> $\mathbb{F}_q$ is much slower since it's non-native => we have to represent it as a bunch of limbs & do range check

**=> need to use cycle of curves**

change curve $E <-> E'$: $E'(\mathbb{F}_p)$ - scalar field $\mathbb{F}_q$

$\pi/E$ <-> $V/E'$ => $\mathbb{F}_q$ is cheap, $\mathbb{F}_p$ is costly

$E <-> E'$ both pairing friendly
=> size of best cycle is 700-800 bits => way too slow => MNT curve

### Plonky2's approach

**IPA-based PCS (inner-product argument, Bulletproofs/Bootle proof)**
- based on DLog: 256-bit of security
- much cheapter for 400 bits when using with pairing-friendly curves to achieve security
- big issue: verification is linear

**Halo: Accumulation scheme**
- $\circ \rightarrow \circ \rightarrow \circ \rightarrow \circ \rightarrow \circ$
- $\circ \rightarrow \circ \rightarrow \circ \rightarrow \circ \rightarrow \circ$
- each step -> accumulate some verification -> verify them at the end

> Accumulation schemes can't accumulate different instance types, the same for folding schemes


- Plonky1 = IPA + Accumulation for IVC
### Plonky2 = low degree test
- FRI-based PCS
- No non-native arithmetic
- Use small field
- No trusted setup
- Post-quantum secure
- Turbo-Plonk
- $p = 2^{64} - 2^{32} + 1$ => Goldilocks field
- reduction 128-bit mod $p$ is cheap: $x.y$ $x,y$ are 64-bit
- Modulo of $32-bit$ int doesn't overflow $x.y + z$

### Row of trace
- Constants: $c_0...c_k$
- Routable wires: $x_0...x_v$
- in traditional PLONK, all wires are routable, so you can have copy constraints between any two wires in the table => permutation argument => not free
- Advice wires: $y_0...y_w$ => intermediate computations
- e.g. to compute $x^{16}$, $x^2, x^4, x^8$ are advice wires
- $P(c_0, ..., c_k, x_0, ..., x_v, y_0, ..., y_w) = 0$ => custom gate
- Increase or decrease the width of the table + degree P => expressive
- 135-wires => deg P <= 9

### FRI config
- Commitment($P_0, ..., P_N$) = Root of Merkle tree

- Rate: $2^{\varphi}$, \#queries = $q$
- $\lambda = \varphi \cdot q + g$
- e.g. $g = 16$ -> grinding bits (proof-of-work bits)
- Decrease rate, increase $q$ -> faster proving time but larger proof
- Increase rate, decrease $q$ -> slower proving time & smaller proof

### Example of custom gate

Arithmetic Base Gate: $c_0 \cdot x \cdot y + c_1 \cdot z = w$
- e.g. $x \cdot y = w$ => $c_0 = 1, c_1 = 0$
- constants: $c_0, c_1$
- routed wires: $x, y, z, w$
- $P(c_0, c_1, x, y, z, w) = w - c_0 \cdot x \cdot y - c_1 \cdot z$
- number of routed wires in plonky2 is 80 => 20 operations in 1 row
- $x_0, y_0, z_0, w_0$ | $x_1, y_1, z_1, w_1$ ...
- => need wide table for Poseidon
- arithmetic operation are basically free in plonky2

### Merkle tree
- Merkle caps => chopped merkle tree
- Shorter Merkle proof
### Starky
- STARK/AIR $\subseteq$ PLONK
- E.g. VM state transition
- Each row has access to the next row => transition constraint
- Some cells have specified value => boundary constraint
- In some version of PLONK, we don't have access to the next state in the constraints
- TurboPlonk: include the next state in the constraint
- Best way to write VM is via AIR & execution trace not PLONK & custom gate
- Constraints:
- degree 3 -> rate = 2 => fast prover

### ZK-Rollup

- Starky low rate -> prove each transaction individually
- Plonky2 low rate -> aggregate Starky proof
- ...
- Final proof is generated via Plonky2 high rate + keccak -> faster to verify on L1
- Poseidon is good for recursion
- but keccak is faster in ETH


# References
1. <a id="plonky2-ref"></a>[ZK Whiteboard Sessions – Module Thirteen: Fast Recursion with Plonky2](https://www.youtube.com/watch?v=-pucWUDn5Hw)
2. <a id="plonky2-github-ref"></a>[0xPolygonZero/plonky2](https://github.com/0xPolygonZero/plonky2)