---
# System prepended metadata

title: Scalar mul gate

---

In order to implement [casting out primes], we want to generalize [PSE's Halo2wrong](https://github.com/privacy-scaling-explorations/halo2wrong) main gate to support scalar muls in a single row. 

Their main gate is defined by:
$$
\begin{align}
&q_a a + q_b b + q_c c + q_d d + q_e e + q_{ab} a b + q_{cd} c d + q_{const} = 0
\end{align}
$$ (we will, for now, ignore the $q_{next} e$ term)

Our scalar mul gate depends on a parameter $N \geq 2$ and is defined by:
$$
\sum_{k=0}^{2N - 2} q_{k} \cdot \sum_{i+j = k} x_i y_j  - \sum_{k=0}^{N-1} q_k z_j - q_t t - q_s s = 0
$$Note this gate has $2N+1$ fixed columns and $3N + 2$ advice columns (for our use case we'll most likely use $N = 5$, which results in 28 columns).

It'd be nice if our gate could generalize PSE's, and it'd be better if we could do so by adding as few extra columns as possible. The most naive way (and possibly the right one) to do so would be to add 5 fixed columns as follows:
$$
\sum_{k=0}^{2N - 2} q_{k} \cdot \sum_{i+j = k} x_i y_j  - \sum_{k=0}^{N-1} q_k z_j - q_t t - q_s s \\ q_a x_{N-1} + q_b y_{N-1} + q_{ts} t s + q_z z_0 + q_{const} = 0
$$
Now it is clear that the gate reduces to PSE's when:
$$q_i = 0, \qquad i < 2N-2$$.

An approach that may spare us of a few columns is to check every implemented instruction of that gate and which extra columns are needed for each relevant instruction. 

## Select:
It is of the form 
$$ q_d d + q_e e + q_{ab} ab + q_{cd} cd = 0$$ Requires 2 extra columns, $q_{ts}$ and $q_z$.