# Transformations
## Plonkish Constraint Forms

A Plonkish "constraint form" is defined by a single, fixed, multivariable polynomial.

The variables of this polynomial are called *wire columns* (sometimes shortened to just *wires*, although this is not precisely correct). Wire columns represent indeterminate data. This data can be private to the Prover, or public and provided by the Prover, Verifier, or both, at *proof time*. The [halo2 book](https://zcash.github.io/halo2/concepts/arithmetization.html) uses the terms *advice* and *instance* for the private and public wire columns, respectively. Together these wire columns can be thought of as the inputs and outputs of each node in an arithmetic circuit.

The coefficients of this polynomial are fixed in advance. Most of the coefficients come from *selectors* which turn certain rows and columns on or off, and a few come from other parameters. These are called *fixed* columns in the halo2 book.

### Original Plonk Constraint Form
The [original Plonk paper](https://eprint.iacr.org/2019/953.pdf) used three private wire columns ($a$, $b$, and $c$), one public column $pi$, and five selectors ($q_M, q_L, q_R, q_O, q_C$). The polynomial defining original Plonk is this:

$\quad P_\mathrm{original}(a, b, c, pi) = q_M a b + q_L a + q_R b + q_O c + q_C + pi$

### ZK-Garage Plonk Constraint Form
ZK-Garage adds one more private wire ($d$) and a new selector ($q_4$) to go with it.

$\quad P_\mathrm{zk-garage}(a, b, c, d, pi) = q_M a b + q_L a + q_R b + q_O c + q_4 d + q_C + pi$

### Add/Mul Only Constraint Form
This constraint form most closely matches the usual presentation of an arithmetic circuit, where each constraint is limited to addition or multiplication only, with two inputs and one output.

$\quad P_\mathrm{add-mul-only}(a, b, c, pi) = q_M a b + q_L a + q_R b + q_O c + q_C + pi$

...where $q_M$ is zero if either $q_L$ or $q_R$ is non-zero.

## Transforming Between Circuit Forms

### Example 1: 4-bit range proof
Consider the five constraints in the circuit for a 4-bit range proof. Usually each of these variables will carry private data.

$x_0^2 - x_0$
$x_1^2 - x_1$
$x_2^2 - x_2$
$x_3^2 - x_3$
$8x_3 + 4x_2 + 2x_1 + x_0 - x_4$

The first four constraints "fit" into either of the circuit forms above, so each will contribute one row to the final circuit. The last constraint has five variables, so it does not fit into a single constraint of either of the circuit forms above and needs to be split into multiple rows.

#### Original Plonk
For Original Plonk we must add two additional variables and split the last constraint into three smaller constraints like this:

$8x_3 + 4x_2 + 2x_1 + x_0 - x_4$

becomes

$8x_3 + 4x_2 - x_5$
$x_5 + 2x_1 - x_6$
$x_6 + x_0 - x_4$

Then the circuit can be expressed in the Original Plonk constraint form in 7 rows like this:

|row| a | b | c |$q_M$|$q_L$|$q_R$|$q_O$|$q_C$|
| - |-----|-----|-----|-----|-----|-----|-----|-----|
| 1 |$x_0$|$x_0$|$x_0$| 1 | 0 | 0 | -1 | 0 |
| 2 |$x_1$|$x_1$|$x_1$| 1 | 0 | 0 | -1 | 0 |
| 3 |$x_2$|$x_2$|$x_2$| 1 | 0 | 0 | -1 | 0 |
| 4 |$x_3$|$x_3$|$x_3$| 1 | 0 | 0 | -1 | 0 |
| 5 |$x_3$|$x_2$|$x_5$| 0 | 8 | 4 | -1 | 0 |
| 6 |$x_5$|$x_1$|$x_6$| 0 | 1 | 2 | -1 | 0 |
| 7 |$x_6$|$x_0$|$x_4$| 0 | 1 | 1 | -1 | 0 |

#### ZK-Garage Plonk
For ZK-Garage Plonk we have an extra variable at our disposal so we can split the last constraint into just 2 constraints by adding 1 variable.

$8x_3 + 4x_2 + 2x_1 + x_0 - x_4$

becomes

$8x_3 + 4x_2 + 2x_1 - x_5$
$x_5 + x_0 - x_4$

|row| a | b | c | d |$q_M$|$q_L$|$q_R$|$q_O$|$q_4$|$q_C$|
| - |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|
| 1 |$x_0$|$x_0$|$x_0$| | 1 | 0 | 0 | -1 | 0 | 0 |
| 2 |$x_1$|$x_1$|$x_1$| | 1 | 0 | 0 | -1 | 0 | 0 |
| 3 |$x_2$|$x_2$|$x_2$| | 1 | 0 | 0 | -1 | 0 | 0 |
| 4 |$x_3$|$x_3$|$x_3$| | 1 | 0 | 0 | -1 | 0 | 0 |
| 5 |$x_3$|$x_2$|$x_5$|$x_1$| 0 | 8 | 4 | -1 | 2 | 0 |
| 6 |$x_5$|$x_0$|$x_4$| | 0 | 1 | 1 | -1 | 0 | 0 |

#### Add/Mul Only Plonk

For this example, Add/Mul Only Plonk is identical to Original Plonk.

## How to Transform to Larger Gates

Vamp-IR currently compiles to three-address codes before synthesis. The 4-bit range proof above gives this list of 16 constraints:

$\begin{align}
x_5 &= x_0 - 1\\
0 &= x_0 \cdot x_5\\
x_6 &= x_1 - 1\\
0 &= x_1 \cdot x_6\\
x_7 &= x_2 - 1\\
0 &= x_2 \cdot x_7\\
x_8 &= x_3 - 1\\
0 &= x_3 \cdot x_8\\
x_9 &= x_4 - 1\\
0 &= x_4 \cdot x_9\\
x_{10} &= 2x_1\\
x_{11} &= x_0 + x_{10}\\
x_{12} &= 4x_2\\
x_{13} &= x_{11} + x_{12}\\
x_{14} &= 8x_3\\
x_4 &= x_{13} + x_{14}\\
\end{align}$

From these we can substitute "up" to the larger target gate. We scan the list and look for opportunities to substitute. According to width-3 Plonk, each gate can have at most 3 variables and at most 1 multiplication. If a substituion introduces too many new variables or two many multiplications than it cannot be performed.

After substituting we have the following list:

$\begin{align}
0 &= x_0 \cdot (x_0 - 1)\\
0 &= x_1 \cdot (x_1 - 1)\\
0 &= x_2 \cdot (x_2 - 1)\\
0 &= x_3 \cdot (x_3 - 1)\\
x_{11} &= x_0 + 2x_1\\
x_{13} &= x_{11} + 4x_2\\
x_4 &= x_{13} + 8x_3\\
\end{align}$