# [Draft] Baby Plonk

:::info
¿We must assume that the circuit is in layered form? If we do it, we can write a much more efficient protocol.
:::

## Introduction

The goal behind Baby Plonk is to increase the efficiency of the verifier by reducing the number of polynomials and therefore the calculations that are made. The tradeoff is be that the prover has a greater amount of work. This is useful in proof systems where prover load isn't a big issue but verifier load is. A zkRollup is one of this systems proof because prover is executed off-chain but verifier is executed on-chain.

## Plonk Gate Constraint

Recall that in [Plonk](https://eprint.iacr.org/2019/953.pdf) the idea is to connect fan-in two gates that can peform addition or multiplication operations. The operations performed by a gate $i$ can be expressed by the following equation:
$$
(q_L)_ix_{a_i} + (q_R)_ix_{b_i} + (q_M)_ix_{a_i}x_{b_i} + (q_O)_ix_{c_i} + (q_C)_i = 0,
$$
where $x_{a_i},x_{b_i}$ and $x_{c_i}$ are left input, right input and the output for the current gate, and the $q$'s are the selectors to force the desired operation.

The idea behind Baby Plonk is to modify the PLONK gate to have a new gate with three inputs and one output by reducing the wire and the selector polynomials.

## HyperPlonk Gate Constraint

<!--
they take $H = \{\omega^3, \omega^6, \dots, \omega^{3(|C|-1)}, \omega^{3|C|} = 1\}$ and
they define $q \in \mathbb{F}[X]$ such that $q(\omega^{3i}) = 1$ if the $i$-th gate is an addition gate and $q(\omega^{3i}) = 0$ if the $i$-th gate is a multiplication gate.
-->

In [HyperPlonk](https://eprint.iacr.org/2022/1355.pdf), they define the selector $q_{\text{gate}} \in \mathbb{F}^n$ such that $(q_{\text{gate}})_i = 1$ if the $i$-th gate is an addition gate and $(q_{\text{gate}})_i = 0$ if the $i$-th gate is a multiplication gate.
Then, the operations performed by a gate $i$ can be expressed via:
$$
(q_{\text{gate}})_i \cdot \left(x_{a_i} + x_{b_i}\right) + (1 - (q_{\text{gate}})_i) \cdot x_{a_i} \cdot x_{b_i} - x_{c_i} = 0,
$$
where $x_{a_i},x_{b_i},x_{c_i}$ are the values associated to the left input, right input and (negated) output for the $i$-th gate, respectively.

## Baby PLONK Gate Constraint

In Baby Plonk the number of polynomials are reduced by doubling the number of evaluations of those that remain. In particular, wire polynomials are reduced from $(a,b,c)$ to $(a,b)$ and selector polynomials are reduced from $(q_L,q_R,q_M,q_O,q_C)$ to $(q_1,q_2)$.

The operations performed by the $i$-th Baby Plonk gate are expressed by the following constraint:
$$
(q_1)_{i} \cdot x_{a_{i}} + (q_2)_{i} \cdot x_{b_{i}} +(q_1)_{i+1} \cdot x_{a_{i}}x_{b_{i}} + (q_2)_{i+1} \cdot x_{a_{i}} x_{a_{i+1}} + x_{b_{i+1}} = 0.
$$


As we can see in the draw each gate can acces to the current row values and the following ones. Thus, for $i \in \{0,2,4,\dots,2n-2\}$ we define a single gate where:
- $a_i,b_i$, and $a_{i+1}$ are the inputs to the gate.
- $b_{i+1}$ is the output of the gate.

Recall that in Plonk in order to prove knowledge of a witnesses that fulfill a circuit, the following checks have to be performed:
1. Every gate is evaluated correctly (gate constraints).
1. Public inputs are correctly included (public input constraints).
1. The wiring is implemented correctly (copy constraints).

In Baby Plonk, gate constraints must be checked for each gate, thus for each odd row.

<!--
-->

:::warning
TODO Check and expand
! Number of rows on the constraints system must be even
:::

## Constraint systems

Fix positive integers m and n. We present a type of constraint system that captures fan-in two arithmetic circuits of unlimited fan-out with n gates and m wires.

The constraint system $C = (V,Q)$ is defined as follows.
- $V$ is of the form $V = (a,b)$, where $a,b \in [m]^{2n}$. We think of $a,b$ as sequences encoding both the two inputs wires and the output wire, but each gate $i$ will take into account two consecutive values $a_i,a_{i+1},b_i,b_{i+1}$ of the sequences.
- $Q$ is of the form $Q = (q_1,q_2)$, where we think of $q_1,q_2 \in \mathbb{F}^{2n}$ as the “selector vectors”. Similarly as with $V$, each gate will take into account two consecutive values from $q_1,q_2$.

We say $x \in \mathbb{F}^m$ satisfies $C$ if, for each $i\in[2n]$, we have:
$$
(q_1)_{i} \cdot x_{a_{i}} + (q_2)_{i} \cdot x_{b_{i}} +(q_1)_{i+1} \cdot x_{a_{i}}x_{b_{i}} + (q_2)_{i+1} \cdot x_{a_{i}} x_{a_{i+1}} + x_{b_{i+1}} = 0,
$$
where $x_{a_i},x_{b_i}$ are the values associated to the left input and right input, respectively; and $x_{a_{i+1}},x_{b_{i+1}}$

We proceed to show some useful instantiations of this type of constraints.

### Arithmetic circuits
A fan-in three circuit of n gates can be captured in such a constraint system as follows. In the case of arithmetic circuits, we encounter that for each $i \in \{1,3,5,...,2n-1\}$:

#### Additive gate
Set $(q_1)_i = (q_2)_i = 1, (q_1)_{i+1} = (q_2)_{i+1} = 0$ when the $i$-th gate is an additive gate.
$$
(q_1)_{i} \cdot x_{a_{i}} + (q_2)_{i} \cdot x_{b_{i}} + x_{b_{i+1}} = 0,
$$
where:
| | $_{a(X)}$ | $_{b(X)}$ | $_{q_1(X)}$ | $_{q_2(X)}$ |
|:-----:|:---------:|:---------:|:-----------:|:-----------:|
| $i$ | $a$ | $b$ | $1$ | $1$ |
| $i+1$ | $0$ | $-(a+b)$ | $0$ | $0$ |

Note that we can get “linear combination gates” by using other non-zero values for $(q_1)_{i}, (q_2)_{i}$.

#### Multiplicative gate
Set $(q_1)_i = (q_2)_{i} = 0, (q_1)_{i+1} = 1, (q_2)_{i+1} = 0$ when the $i$-th gate is a multiplicative gate.
$$
(q_1)_{i+1} \cdot x_{a_{i}}x_{b_{i}} + x_{b_{i+1}} = 0,
$$
where:
| | $_{a(X)}$ | $_{b(X)}$ | $_{q_1(X)}$ | $_{q_2(X)}$ |
|:-----:|:---------:|:--------------:|:-----------:|:-----------:|
| $i$ | $a$ | $b$ | $1$ | $0$ |
| $i+1$ | $0$ | $-(a \cdot b)$ | $0$ | $0$ |

#### Boolean gate
A common operation in proof systems is to check check if a value $x_i \in \{0, 1\}$. This is equivalent to check $a(a-1)=0$, or equivalently, $aa-a=0$.
Set $(q_1)_i = -1$,$(q_1)_{i+1} = 1$, $(q_2)_i = (q_2)_{i+1} = 0$ when the gate is boolean.
$$
(q_1)_{i+1} \cdot x_{a_{i}}x_{b_{i}} - (q_1)_{i} \cdot x_{a_{i}} = 0,
$$
where:
| | $_{a(X)}$ | $_{b(X)}$ | $_{q_1(X)}$ | $_{q_2(X)}$ |
|:-----:|:---------:|:---------:|:-----------:|:-----------:|
| $i$ | $a$ | $a$ | $-1$ | $0$ |
| $i+1$ | $0$ | $0$ | $1$ | $0$ |

:::warning
Note the equivalence between the multiplicative and the boolean constraint. The difference is that the boolean constraint has no output but it could have some.
:::

#### Constant gate
Set $(q_1)_i = 1, (q_2)_i = (q_1)_{i+1}=(q_2)_{i+1} = 0$ when the gate is a constant input gate.
$$
(q_1)_{i} \cdot x_{a_{i}} + x_{b_{i+1}} = 0,
$$
where:
| | $_{a(X)}$ | $_{b(X)}$ | $_{q_1(X)}$ | $_{q_2(X)}$ |
|:-----:|:---------:|:---------:|:-----------:|:-----------:|
| $i$ | $a$ | $0$ | $1$ | $0$ |
| $i+1$ | $0$ | $-a$ | $0$ | $0$ |

#### Selector gate
Another common operation is a selector (*a.k.a. multiplexor*) gate where a signal $s$ selects which input $a,b$ goes to the output $o$. A selector can be expressed as $o = s(b-a)+a$, when $s=0 \rightarrow o=a$ and when $s=1 \rightarrow o=b$. Developing the equation $sb-sa+a-o=0$. Thus, set $(q_1)_i = 0, (q_2)_i = (q_2)_{i+1} = 1, (q_1)_{i+1} = -1$ when the gate is selector gate.
$$
(q_2)_{i+1} \cdot x_{a_{i}} x_{a_{i+1}} + (q_1)_{i+1} \cdot x_{a_{i}}x_{b_{i}} + (q_2)_{i} \cdot x_{b_{i}} + x_{b_{i+1}} = 0,
$$
where:
| | $_{a(X)}$ | $_{b(X)}$ | $_{q_1(X)}$ | $_{q_2(X)}$ |
|:-----:|:---------:|:---------:|:-----------:|:-----------:|
| $i$ | $s$ | $a$ | $0$ | $1$ |
| $i+1$ | $b$ | $-o$ | $-1$ | $1$ |

Note that a selector gate cannot be performed in a single Plonk gate constraint.

## The Protocol

## Full Description of the Protocol

### Common preprocessed input:

$$
n, (x \cdot [1]_1,...,x^{n+5?} \cdot [1]_1), (q_1, q_2)_{i=1}^n, \\
\begin{align}
q_1(X) &= {\sum}_{i=1}^{n} q_{1_i}L_i(X), \\
q_2(X) &= {\sum}_{i=1}^{n} q_{2_i}L_i(X), \\
S_{\sigma_1}(X) &= {\sum}_{i=1}^{n} \sigma^*(i)L_i(X), \\
S_{\sigma_2}(X) &= {\sum}_{i=1}^{n} \sigma^*(n+i)L_i(X)
\end{align}
$$

### Public input:
$$l, (w_i)_{i \in [l]}$$

### <ins>Prover algorithm:</ins>

#### Prover input:

$$(w_i)_{i \in [2n]}$$

#### Round 1:

Generate random blinding scalars $(b1,\dots, b7) \in \mathbb{F}$

Compute wire polynomials $a(X), b(X)$ :

$$
\begin{align}
a(X) &= (b_1X + b_2)Z_H(X) + {\sum}_{i=1}^n w_iL_i(X) \\
b(X) &= (b_3X + b_4)Z_H(X) + {\sum}_{i=1}^n w_{n+i}L_i(X)
\end{align}
$$

Compute $[a]_1 := [a(x)]_1 , [b]_1 := [b(x)]_1$

First output of $P$ is $([a]_1, [b]_1)$.

#### Round 2:

Compute permutation challenges $(\beta, \gamma) \in \mathbb{F}$ :

$$\beta = H(transcript, 0), \gamma = H(transcript, 1)$$

Compute permutation polynomial $z(X)$ :

$$
z(X) = (b_5X^2 + b_6X + b_7)Z_H(X) \\
+L_1(X)
+{\sum}_{i=1}^{n−1} \left(L_{i+1}(X) {\prod}_{j=1}^i \frac{(w_j + \beta \omega^j + \gamma)(w_{n+j} + \beta k_1 \omega^j + \gamma)}{(w_j + \beta \sigma^*(j) + \gamma)(w_{n+j} + \beta \sigma^*(n+j) + \gamma)}
\right)
$$

Compute $[z]_1 := [z(x)]_1$

Second output of $P$ is $([z]_1)$

#### Round 3:

Compute quotient challenge $\alpha \in \mathbb{F}$ :

$$\alpha = H(transcript)$$

To take in account the gate constraints only in the even rows we define the *flickering polynomial* $I \in \mathbb{F}_{<n/2}[X]$ such that $I(\omega^i) = 1$ for $i \in \{0,2,4,\dots,n-2\}$ and $I(\omega^i) = 0$ for $i \in \{1,3,5,\dots,n-1\}$:
$$
I(X) = \frac{X^{\frac{n}{2}}+1}{2}
$$

:::success
The flickering polynomial is not necessary (and in fact is incorrect) if we equivalently divide by the zerofier over $H_{\text{even}}=\{\omega^0, \omega^2,\dots,\omega^{n-2}\}$:
$$
Z_{H_{\text{even}}}(X) = \prod_{i=0}^{n/2-1} (X-\omega^{2i}) = X^{n/2}-1
$$
:::

Compute quotient polynomial $t(X)$ :

$$
\begin{align}
t(X) = & [ q_1(X)a(X) + q_2(X)b(X) + q_1(X\omega)a(X)b(X) + q_2(X\omega)a(X)a(X\omega) + b(X\omega) ] \cdot \frac{1}{Z_{H_{\text{even}}}(X)} \\
&+[ (a(X) + \beta X + \gamma) (b(X) + \beta k_1 X + \gamma) z(X) \\
&-(a(X) + \beta S_{\sigma_1}(X) + \gamma) (b(X) + \beta S_{\sigma_2}(X) + \gamma) z(X\omega)] \cdot \frac{\alpha}{Z_H(X)}\\
&+(z(X)-1) \cdot L_1(X) \cdot \frac{\alpha^2}{Z_H(X)}
\end{align}
$$

Split $t(X)$ into degree < n polynomial $t′_{lo}(X)$ and $t′_{hi}(X)$ of degree at most $n + 5$, such that

$$t(X) = t′_{lo}(X) + X^nt′_{hi}(X)$$

Now choose random scalars $b_{8} \in \mathbb{F}$ and define

$$t_{lo}(X) := t′_{lo}(X) + b_8X^n, t_{hi}(X) := t′_{hi}(X) − b_8$$

Note that we have $t(X) = t_{lo}(X) + X^nt_{hi}(X)$.

Compute $[t_{lo}]_1 := [t_{lo}(X)]_1 , [t_{hi}]_1 := [t_{hi}(X)]_1$

Third output of P is $([t_{lo}]_1, [t_{hi}]_1)$

#### Round 4:

Compute evaluation challenge $\mathfrak{z} \in \mathbb{F}$ :

$$\mathfrak{z} = H(transcript)$$

:::warning
If $\mathfrak{z}$ is even, we will not check gate constraint in the verifier due to $I(\mathfrak{z})=0$. If we want to force this check we must force $\mathfrak{z}$ to be odd setting LSB to be 1 by a binary operation.
*If we do this, have we to add copy constraints checking in the verifier for the even rows*?
:::

Compute opening evaluations:

$$\bar{a} = a(\mathfrak{z}), \bar{b} = b(\mathfrak{z}), \bar{a}_\omega = a(\mathfrak{z}\omega), \bar{b}_\omega = b(\mathfrak{z}\omega), \bar{S}_{\sigma_1} = S_{\sigma_1}(\mathfrak{z}), \bar{z}_\omega = z(\mathfrak{z}\omega)$$

Fourth output of P is $(\bar{a}, \bar{b}, \bar{a}_\omega, \bar{b}_\omega, \bar{S}_{\sigma_1}, \bar{z}_\omega)$

#### Round 5:

Compute opening challenge $v, v' \in \mathbb{F}$ :

$$v = H(transcript, 0), v' = H(transcript, 1)$$

Compute linearisation polynomial $r(X)$ :

$$
\begin{align}
r(X) = &(q_1(X)\bar{a} + q_2(X)\bar{b} + q_1(X\omega)\bar{a}\bar{b} + q_2(X\omega)\bar{a}\bar{a_\omega} + \bar{b}_\omega)\\
&+ [ (\bar{a} + \beta \mathfrak{z} + \gamma) (\bar{b} + \beta k_1 \mathfrak{z} + \gamma) z(X) \\
&-(\bar{a} + \beta \bar{S}_{\sigma_1} + \gamma) (\bar{b} + \beta S_{\sigma_2}(X) + \gamma) \bar{z}_\omega] \cdot \alpha\\
&+ (z(X)-1)L_1(\mathfrak{z}) \cdot \alpha^2 \\
&-Z_H(\mathfrak{z}) (t_{lo}(X) + \mathfrak{z}^n t_{hi}(X))
\end{align}
$$

Compute opening proof polynomial $W_{\mathfrak{z}}(X)$ :

$$
W_{\mathfrak{z}}(X) = \frac{1}{X-\mathfrak{z}}
\left(
\begin{split}
&r(X)\\
+&v(a(X) - \bar{a}) \\
+&v^2(b(X) - \bar{b}) \\
+&v^3(S_{\sigma_1}(X) - \bar{S}_{\sigma_1}) \\
\end{split}
\right)
$$

Compute opening proof polynomial $W_{\mathfrak{z}\omega}(X)$ :

$$
W_{\mathfrak{z}\omega}(X) = \frac{1}{X-\mathfrak{z}\omega}
\left(
\begin{split}
&z(X) - \bar{z}_\omega \\
+&v'(a(X) - \bar{a}_\omega) \\
+&v'^2(b(X) - \bar{b}_\omega)
\end{split}
\right)
$$

Compute $[W_{\mathfrak{z}}]_1 := [W_{\mathfrak{z}}(X)]_1 ,
[W_{\mathfrak{z}\omega}]_1 := [W_{\mathfrak{z}\omega}(X)]_1$

The fifth output of $P$ is $([W_\mathfrak{z}]_1,[W_{\mathfrak{z}\omega}]_1)$

Return

$$
\pi_{\text{SNARK}} =
\left(
\begin{split}
\begin{align}
[&a]_1,[b]_1,[z]_1,[t_{lo}]_1,[t_{hi}]_1,[W_{\mathfrak{z}}]_1,[W_{\mathfrak{z}\omega}]_1, \\
&\bar{a},\bar{b},\bar{a}_\omega,\bar{b}_\omega,\bar{S}_{\sigma_1},\bar{z}_\omega,
\end{align}
\end{split}
\right)
$$

Compute multipoint evaluation challenge $u \in \mathbb{F}$ :

$$u = H(transcript)$$

We now describe the verifier algorithm in a way that minimizes the number of $\mathbb{G}_1$ scalar multiplications.

### <ins>Verifier algorithm:</ins>

#### Verifier preprocessed input:

$$
\begin{split}
&[q_{1}]_1 := q_1(X) \cdot [1]_1,
[q_{2}]_1 := q_2(X) \cdot [1]_1,
[q_{1\omega}]_1 := q_1(X) \cdot [1]_1, \\
&[q_{2\omega}]_1 := q_2(X) \cdot [1]_1,
[S_{\sigma1}]_1 := S_{\sigma1}(X) \cdot [1]_1,
[S_{\sigma2}]_1 := S_{\sigma2}(X) \cdot [1]_1, \\
&x \cdot [1]_2
\end{split}
$$

$V((w_i)_{i\in[l]}, \pi_\text{SNARK})$ :

1. Validate $([a]_1,[b]_1,[z]_1,[t_{lo}]_1,[t_{hi}]_1,[W_{\mathfrak{z}}]_1,[W_{\mathfrak{z}\omega}]_1) \in \mathbb{G}_1^7$.

2. Validate $(\bar{a}, \bar{b}, \bar{a}_\omega,\bar{b}_\omega, \bar{S}_{\sigma_1}, \bar{z}_\omega) \in \mathbb{F}_6$.

3. Validate $(w_i)_{i \in [l]} \in \mathbb{F}^l$.

4. Compute challenges $\beta,\gamma,\alpha,\mathfrak{z},v,v',u \in \mathbb{F}$ as in prover description, from the common inputs, public input, and elements of $\pi_\text{SNARK}$.

5. Compute the flickering polynomial evaluation:
$$I(\mathfrak{z}) = \frac{\mathfrak{z}^{\frac{n}{2}}+1}{2}$$

6. Compute zero polynomial evaluation $Z_H(\mathfrak{z})=\mathfrak{z}^n-1$.

7. Compute Lagrange polynomial evaluation $L_1(\mathfrak{z}) = \frac{\omega(\mathfrak{z}^n−1)}{n(\mathfrak{z}−\omega)}$.

8. To save a verifier scalar multiplication, we split $r$ into its constant and non-constant terms. Compute $r$’s constant term:

$$
r_0 := L_1(\mathfrak{z})\alpha^2 − \alpha(\bar{a} + \beta\bar{S}_{\sigma_1} + \gamma)(\bar{b} + \gamma)\bar{z}_\omega + \bar{b}_\omega,
$$

:::warning
TODO check!
:::
and let $r′(X) := r(X) − r_0$.

9. Compute first part of batched polynomial commitment $[D]_1 := [r′]_1 + u · [z]_1$ :

$$
[D]_1 :=
\begin{split}
&([q_1]_1\bar{a} + [q_2]_1\bar{b} + [q_{1\omega}]_1\bar{a}\bar{b} + [q_{2\omega}]_1\bar{a}\bar{a_\omega})\\
&+[ (\bar{a} + \beta \mathfrak{z} + \gamma) (\bar{b} + \beta k_1 \mathfrak{z} + \gamma) \alpha + L_1(\mathfrak{z}) \alpha^2 + u ] \cdot [z]_1 \\
&-(\bar{a} + \beta \bar{S}_{\sigma_1} + \gamma) \alpha \beta \bar{z}_\omega \cdot [S_{\sigma2}]_1 \\
&-Z_H(\mathfrak{z}) ([t_{lo}]_1 + \mathfrak{z}^n [t_{hi}]_1)
\end{split}
$$

10. Compute full batched polynomial commitment $[F]_1$ :

$$[F]_1 := [D]_1 + v [a]_1 + v^2 [b]_1 + v^3 [S_{\sigma1}] + u \cdot (v' [a]_1 + v'^2 [b]_1)$$

11. Compute group-encoded batch evaluation $[E]_1$ :

$$
[E]_1 := (-r_0 + v \bar{a} + v^2 \bar{b} + v^3 \bar{S}_{\sigma1} + u \cdot (\bar{z}_\omega + v'\bar{a}_\omega + v'^2\bar{b}_\omega)) \cdot [1]_1
$$

12. Batch validate all evaluations:

$$e([W_\mathfrak{z}]_1 + u \cdot [W_{\mathfrak{z}\omega}]_1, [x]_2 ) \stackrel{?}{=} e(\mathfrak{z} \cdot [W_\mathfrak{z}]_1 + u\mathfrak{z}\omega \cdot [W_{\mathfrak{z}\omega}]_1 + [F]_1 - [E]_1, [1]_2)$$

## Conclusions
:::warning
TODO Conclusions
Does the verifier only save 2 multiplications in G1?
Compare with regular PLONK and explain how more efficient it is and the tradeoff the prover has to pay for
:::

###### tags: `PlonK`