{%hackmd theme-dark %}
$$
\DeclareMathOperator{\originpoints}{\texttt{origin_points}}
\DeclareMathOperator{\ladder}{\texttt{ladder}}
\DeclareMathOperator{\idaccum}{\texttt{accumulator_identity}}
\DeclareMathOperator{\idxalpha}{\texttt{x_alpha_identity}}
\DeclareMathOperator{\idxaccum}{\texttt{x_accumulator_identity}}
\DeclareMathOperator{\idyaccum}{\texttt{y_accumulator_identity}}
\DeclareMathOperator{\idaccuminit}{\texttt{accumulator_init_identity}}
\DeclareMathOperator{\idxinit}{\texttt{x_init_identity}}
\DeclareMathOperator{\idyinit}{\texttt{y_init_identity}}
\DeclareMathOperator{\idgate}{\texttt{gate_identity}}
\DeclareMathOperator{\ecc}{\text{ecc}}
\DeclareMathOperator{\grumpkin}{\text{grumpkin}}
$$
# Gates in Turbo Plonk
**Disclaimer:** This documentation was written on July, 2021. It is intended to give readers a high-level understanding. The codebase is the canonical source of truth, and over time this document might fall behind the implementation details of the code.
###### tags: `plookup`
Original author: Cody

## TurboFixedBaseWidget

A reference for this widget is https://app.gitbook.com/@aztec-protocol/s/zkproofs-proposal/. This is the basis of the fixed group addition implementation. What follows uses the notation in Barretenberg.

Preliminaries: $\delta = w_{4\omega} - 4w_4$ and $b_{\grumpkin} = -17$.
### Linear terms
The contribution to the quotient polynomial is $q_{\ecc, 1}$ times the sum of the products formed by multiplying the non-$i$ row values of the table that follows.

| $i$ | selector | $\alpha^?$ | coefficient |
| --- | -------- | ---------- | ----------------------------------------------- |
| 0 | $q_m$ | $\alpha^6$ | $w_3 q_c$ |
| 1 | $q_1$ | $\alpha^1$ | $\delta^2$ |
| 2 | $q_2$ | $\alpha^1$ | $1$ |
| 3 | $q_3$ | $\alpha^2$ | $\delta w_{3,\omega} \cdot 2w_2$ |
| 3 | $q_3$ | $\alpha^3$ | $\delta w_{3,\omega} \cdot (w_{1,\omega}-w_1)$ |
| 4 | $q_4$ | $\alpha^5$ | $w_3 q_c$ |
| 5 | $q_5$ | $\alpha^5$ | $(1-w_4) q_c$ |

### Nonlinear terms

This is a sum of seven terms.

The contribution to the quotient polynomial is
\begin{aligned}
q_{\ecc, 1}\cdot \Big(&q_c\cdot(\idaccuminit + \idxinit + \idyinit) \\
&+\idaccum + \idxalpha \\
&+ \idxaccum + \idyaccum\Big),
\end{aligned}
where the terms that appear are obtained by multiplying the non-name columns of a given row in the table that follows.

| identity name | $\alpha^?$ | coefficient |
| ------------- | ---------- | ---------------------------------------------------------------------------------------------------------------------------- |
| $\idaccum$ | $1$ | $(\delta-1)(\delta+1)(\delta-3)(\delta+3)$ |
| $\idxalpha$ | $\alpha^1$ | $-w_{3,\omega}$ |
| $\idxaccum$ | $\alpha^2$ | $(w_{3,\omega}-w_1)^2 (w_{3,\omega}+w_{1,\omega}+w_1) - (w_{3,\omega}^3 + w_{2}^2 + b_{\grumpkin}) + 2\delta w_{2}q_{\ecc,1}$ |
| $\idyaccum$ | $\alpha^3$ | $(w_{2, \omega} + w_2)(w_{3,\omega}-w_1) + (w_2-q_{\ecc,1}\delta)(w_{1}-w_{1,\omega})$ |
| $\idaccuminit$ | $\alpha^4$ | $(w_{4}-1)(w_{4}-1-w_{3})$ |
| $\idxinit$ | $\alpha^5$ | $-w_{1}w_{3}$ |
| $\idyinit$ | $\alpha^6$ | $(1-w_{4})q_{c}-w_{2}w_{3}$ |
## Altogether
The contribution to the quotient polynomial is $q_{\ecc,1}$ times the expression that follows.

\begin{aligned}
1 & \cdot (\delta-1)(\delta+1)(\delta-3)(\delta+3) + \\
\alpha \cdot & (q_1\delta^2 + q_2 - w_{3,\omega}) +\\
\alpha^{2} \cdot &((w_{3,\omega}-w_1)^2 (w_{3,\omega}+w_{1,\omega}+w_1) - (w_{3,\omega}^3 + w_{2}^2 + b_{\grumpkin}) + 2\delta w_2 q_{\ecc,1} + q_3\delta w_{3,\omega} \cdot 2w_2) + \\
\alpha^{3} \cdot &\big((w_{2, \omega} + w_2)(w_{3,\omega}-w_1) + (w_2-q_{\ecc,1}\delta)(w_{1}-w_{1,\omega})+ q_3\delta w_{3,\omega} \cdot (w_{1,\omega}-w_1)\big) + \\
\alpha^{4} \cdot &q_c\cdot(w_{4}-1)(w_{4}-1-w_{3})+ \\
\alpha^{5} \cdot &q_c\cdot(q_4 w_3 + q_5(1-w_4)-w_{1}w_{3})+ \\
\alpha^{6} \cdot &q_c\cdot((1-w_{4})q_{c}-w_{2}w_{3} + q_m w_3) \\
\end{aligned}

Slightly cleaned to match with gitbook:

\begin{aligned}
&\texttt{// accumulated digit is one of $\pm 1,\, \pm 3$} \\
1 \cdot & (\delta-1)(\delta+1)(\delta-3)(\delta+3) \\
+&\texttt{ // $w_{3,\omega}$ is the $x$-coordinate of the point to be added } \\
\alpha \cdot & (q_1\delta^2 + q_2 - w_{3,\omega}) \\
+&\texttt{ // $w_{1, \omega}$ is the $x$-coordinate of the new point} \\
\alpha^{2} \cdot &((w_{3,\omega}-w_1)^2 (w_{3,\omega}+w_{1,\omega}+w_1) - (w_{3,\omega}^3 + w_{2}^2 + b_{\grumpkin}) + 2\delta w_2 (q_3w_{3,\omega} + q_{\ecc,1})) \\
+&\texttt{ // $w_{2, \omega}$ is the $y$-coordinate of the new point} \\
\alpha^{3} \cdot &\big((w_{2, \omega} + w_2)(w_{3,\omega}-w_1) - (\delta(w_{3,\omega}q_3 + q_{\ecc,1}) - w_2)(w_{1}-w_{1,\omega}) \big)\\
+&\texttt{ // init only: switch $ = 1-w_4$ is $0$ or $-w_3$} \\
\alpha^{4} \cdot &q_c\cdot(1-w_{4})(1-w_{4}+w_{3}) \\
+&\texttt{ // init only: $x$-coordinate is origin_points[0].x or} \\
&\texttt{ // origin_points[1].x, depending on value of switch} \\
\alpha^{5} \cdot &q_c\cdot(w_3 (q_4 - w_1) + q_5(1-w_4)) \\
+&\texttt{ // init only: $y$-coordinate is origin_points[0].y,} \\
&\texttt{ // or origin_points[1].y, depending on value of switch} \\
\alpha^{6} \cdot &q_c\cdot(w_3(q_m - w_{2}) + q_{c}(1-w_{4})) \\
\end{aligned}

# Additional commentary
## Initialization
Following the notation of `stdlib/pedersen/pedersen.cpp`, this is the case where $i=0$. The code is divided into two branches depending on the parity of `scalar`. Regardless of cases, set $q_{z,j} = \texttt{ladder[1].q_z_j}$ for $z=x,y$ and $j=1,2$.

For brevity, set $P_{k,z} := \originpoints[k].z$ for $k=0,\,1$, $z= x,\, y$. Then, when initializing, we set gates as follows:

| Selector | $q_4$ | $q_5$ | $q_m$ | $q_c$ |
| ------------- | ---- | --- | --- | -------- |
| Value at init | $P_{0, x}$ | $P_{0,x}-P_{1,x}$ | $P_{0, y}$ | $P_{0,y}-P_{1,y}$ |

The first row the Turbo Plonk execution trace table depends on cases. The special initialization selectors are chosen to allow switching between those cases.

### Case: scalar is even
If `scalar` is even, i.e. if `skew=0`, then the first row is set to be (where $n=127$)
$$((w_1, w_2), w_3, w_4) = ((4^{n-1}+1)g, 4^{-n}, 1 + 4^{-n}).$$
In this case, $1-w_4 = -w_3$, and the $\alpha^5$ and $\alpha^6$ parts of the polynomial are
$$
\alpha^{5} q_cw_3\cdot(q_4 - q_5 - w_1 ) = \alpha^{5} q_{c} 4^{-n}\cdot(P_{1,x}-x)
$$
and
$$
\alpha^{6} \cdot q_c\cdot w_3 \cdot(q_{m} - q_c - w_{2}) = \alpha^{6} \cdot q_c\cdot 4^{-n} \cdot(P_{1, y} - y)
$$

In our implementation, we ensure that $q_c$ is nonzero (by validing our generator choices satisfy this) and that $w_3$ is nonzero (by setting it to a nonzero circuit constant). Hence the two terms above impose that the initial value of $(w_1, w_2)$ is $(4^{n}+1)g$.

### Case: scalar is odd

If `scalar` is odd, i.e. if `skew=1`, then the first row is required to be (where $n=127$)
$$((w_1, w_2), w_3, w_4) = (4^{n-1}g, 4^{-n}, 1).$$
In this case, $1-w_4 = 0$, and the $\alpha^5$ and $\alpha^6$ parts of the polynomial are
$$
\alpha^{5} q_cw_3\cdot(q_4 - w_1 ) = \alpha^{5} q_{c} 4^{-n}\cdot(P_{0,x}-x)
$$ and
$$
\alpha^{6} \cdot q_c\cdot w_3 \cdot(q_{m} - w_{2}) = \alpha^{6} \cdot q_c\cdot 4^{-n} \cdot(P_{0, y} - y)
$$

In our implementation, we ensure that $q_c$ is nonzero (by validing our generator choices satisfy this) and that $w_3$ is nonzero (by setting it to a nonzero circuit constant). Hence the two terms above impose that the initial value of $(w_1, w_2)$ is $4^{n}g$.