# Non native field custom logic (first draft)

We wish to evaluate $$a * b = q * p + r$$ where $a, b, q, p, r$ are members of non-native field $\mathbb{F}_p$.

Our arithmetic circuit evaluates arithmetic operations modulo $r$, the 'circuit modulus'

### Notation

* `a0, a1, a2, a3` : 4 limbs of $a$
* `b0, b1, b2, b3` : 4 limbs of $b$
* `r0, r1, r2, r3` : 4 limbs of output 'remainder' $r$
* `q0, q1, q2, q3` : 4 limbs of quotient $q$
* `p0, p1, p2, p3` : 4 limbs of non-native field prime $p$. When these appear in polynomial identities, they are assumed to be circuit constants and not wire values
* `lo0, hi0, hi1` : temporary variables that represent 'lo' and 'hi' limbs respectively
* `lo1, hi2` : output 'lo' and 'hi' limbs, both of which must be range constrained for the non-native field multiplication to be correctly evaluated
* `b` is the number of bits in each of the 4 limbs that compose a non-native field element

### Layout of circuit memory

The rationale behind this layout is to ensure that all equations that involve limbs of the non-native field prime $p$ can be evaluated using regular arithmetic gates. This reduces the number of custom gates required, and allows for the non-native field prime to not be hardcoded (i.e. can support multiple prime fields. To clarify, the prime field still needs to be a circuit constant, it is just that this constant can vary without having to affect the custom gate logic).

This does require regular arithmetic gates to include column 4 of the subsequent gate.

| Gate | Column 1 | Column 2 | Column 3 | Column 4 |
| -------- | -------- | -------- | -------- | -------- |
| 1 | $q_0$ | $q_1$ | $r_1$ | $lo_1$ |
| 2 | $a_1$ | $b_1$ | $r_0$ | $lo_0$ |
| 3 | $a_0$ | $b_0$ | $a_3$ | $b_3$ |
| 4 | $a_2$ | $b_2$ | $r_3$ | $hi_0$ |
| 5 | $a_1$ | $b_1$ | $r_2$ | $hi_1$ |
| 6 | $q_2$ | $q_3$ | $lo_1$ | $hi_1$ |
| 7 | --- | --- | --- | $hi_2$ |

Gate 7 can be merged with the first gate of a sublimb accumulation gate

### Gate equations

* 1. $lo_1 = (lo_0 - q_0p_0 - (q_1p_1 + r_1) 2^b) 2^{-2b}$
* 2. $lo_0 = a_0b_0 - r_0 + (a_1b_0 + a_0b_1)2^b$
* 3. $hi_0 = a_2b_0 + a_0b_2 -r_32^b + (a_0b_3 + a_3b_0)2^b$
* 4. $hi_1 = hi_0 + a_1b_1 - r_2 + (a_1b_2 + a_2b_1) 2^b$
* 6. $hi_2 = (hi_1 + lo_1 - q_2p_2 - q_3p_3 2^b)2^{-2b}$

### Gate equations (2, 3, 4) as polynomial identities

$$
\bar{w}_1\bar{w}_2 + (w_1\bar{w}_2 + \bar{w}_1w_2)2^b - w_3 - w_4 = 0
$$

$$
\bar{w}_1w_2 + w_1\bar{w}_2 + (w_1w_4 + w_2w_3 - \bar{w}_3)2^b - \bar{w}_4 = 0
$$

$$
\bar{w}_1\bar{w}_2 + (\bar{w}_1w_2 + \bar{w}_2w_1)2^b + w_4 - \bar{w}_3 - \bar{w}_4 = 0
$$

### Selector polynomial layout

We can evaluate all of the additional logic using a single **auxiliary** selector polynomial, $Q_x(X)$
We can repurpose arithmetic selector polynomials to toggle on/off specific gates.

Specifically we can compose a product of two of the 6 Plonk arithmetic selectors and $q_f$ to select for a gate equation. This produces 15 distinct terms we can reserve for custom gates.

### Custom sublimb accumulation logic and prime-limb evaluation

We can repurpose some of the above selectors to efficiently accumulate sublimbs into a limb.

If we assume 5 sublimbs constitute a limb, we can use a sublimb size of 14 bits and obtain 70-bit limbs.

We can accumulate 2 limbs in 3 gates. We use notation `s0, s1, s2, s3, s4` and `v0, v1, v2, v3, v4` to describe the sublimbs of two limbs `l0, l1`.

In addition, we can chain a gate to the end of 4 sublimb-accumulations to evaluate the prime-field representation (`lr`) of the limbs `l0, l1, l2, l3`. The gate layout is:

| Gate | Column 1 | Column 2 | Column 3 | Column 4 |
| -------- | -------- | -------- | -------- | -------- |
| 7 | $s_0$ | $s_1$ | $s_2$ | $l_0$ |
| 8 | $s_3$ | $s_4$ | $v_0$ | $v_1$ |
| 9 | $v_2$ | $v_3$ | $v_4$ | $l_1$ |

With gate equations:

7. $l_0 = s_0 + s_12^{14} + s_22^{28} + s_32^{42} + s_42^{56}$
8. $l_1 = v_0 + v_12^{14} + v_22^{28} + v_32^{42} + v_42^{56}$

# Combined Arithmetic Identity

$$
q_xq_2q_3\bigg(
\bar{w}_1\bar{w}_2 + (w_1\bar{w}_2 + \bar{w}_1w_2)2^b - w_3 - w_4
\bigg) \\ +
q_xq_2q_4\bigg(
\bar{w}_1w_2 + w_1\bar{w}_2 + (w_1w_4 + w_2w_3 - \bar{w}_3)2^b - \bar{w}_4
\bigg) \\ +
q_xq_2q_m \bigg(
\bar{w}_1\bar{w}_2 + (\bar{w}_1w_2 + \bar{w}_2w_1)2^b + w_4 - \bar{w}_3 - \bar{w}_4
\bigg) \\ +
q_xq_3q_4 \bigg(
w_1 + w_22^{14} + w_32^{28} + \bar{w}_12^{42} + \bar{w}_22^{56} - w_4
\bigg) \\ +
q_xq_3q_m \bigg(
w_3 + w_42^{14} + \bar{w}_12^{28} + \bar{w}_22^{42} + \bar{w}_32^{56} - \bar{w}_4
\bigg)
$$

None of the above terms need to be linearly independent from one another, as only one term will be active for any given gate.

Accounting for duplicate terms, the total number of field multiplications required to evaluate the above is 23.

## Gate costs for evaluating non-native field multiplication

* 6 gates to range-constrain $r$
* 6 gates to range-constrain $q$
* 3 gates to range-constrain both $lo_1$ and $hi_2$
* 6 gates to evaluate non-native field arithmetic
* 2 gates to evaluate prime-field limbs of $r$ and $q$
* 1 gate to evaluate prime-field identity $a_rb_r - q_rp_r - r_r = 0 \text{ mod } r$

Discounting the extra gates from the sorted-list component of the range check, the gate cost is 24.

We add 50 additional wires into the sorted list, adding the equivalent of 12.5 gates.

This brings the total gate cost to 36.5 gates.

## Three limb version

| Gate | Column 1 | Column 2 | Column 3 | Column 4 |
| -------- | -------- | -------- | -------- | -------- |
| 1 | $a_0$ | $b_0$ | $q_0$ | $lo$ |
| 2 | $a_1$ | $b_1$ | $q_1$ | $mid$ |
| 3 | $a_2$ | $b_2$ | $q_2$ | $hi'$ |
| 4 | $a_0$ | $b_0$ | $q_0$ | $hi$ |

### Gate equations

1. $lo = a_0b_0 - p_0 q_0 - r_0$
2. $mid = a_1b_0 + a_0b_1 -q_1p_0 - q_0p_1 -r_1 lo/2^t$
3. $hi' = a_1b_1 - q_1p_1 + mid/2^t$
4. $hi = hi' + a_2b_0 + a_0b_2 -q_2p_0 - q_0p_2$

### Range checks:
Check that $lo,mid,hi$ start with $t$ zeroes
### Selector polynomial layout

We can evaluate all of the additional logic using a single selector polynomial, $q_f(X)$ (f stands for field? not sure what this one should be named)

We can repurpose arithmetic selector polynomials to toggle on/off specific gates.

Specifically we can compose a product of two arithmetic selectors and $q_f$ to select for 3 gate equations

e.g. we use the following toggles to select for one of 9 identities that contain degree-2 terms or lower

| $q_f$ | $q_1$ | $q_2$ | $q_3$ | $q_4$ | $q_m$ | $q_c$ | gate equation |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 2 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 3 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 4 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 5 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 6 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 7 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 8 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 9 |

### Custom sublimb accumulation logic and prime-limb evaluation

We can repurpose some of the above selectors to efficiently accumulate sublimbs into a limb.

If we assume 5 sublimbs constitute a limb, we can use a sublimb size of 14 bits and obtain 70-bit limbs.

We can accumulate 2 limbs in 3 gates. We use notation `s0, s1, s2, s3, s4` and `v0, v1, v2, v3, v4` to describe the sublimbs of two limbs `l0, l1`.

In addition, we can chain a gate to the end of 4 sublimb-accumulations to evaluate the prime-field representation (`lr`) of the limbs `l0, l1, l2, l3`. The gate layout is:

| Gate | Column 1 | Column 2 | Column 3 | Column 4 |
| -------- | -------- | -------- | -------- | -------- |
| 7 | $s_0$ | $s_1$ | $s_2$ | $s_3$ |
| 8 | $s_4$ | $v_0$ | $v_1$ | $l_0$ |
| 9 | $v_2$ | $v_3$ | $v_4$ | $l_1$ |
| 10 | $l_0$ | $l_2$ | $l_3$ | $l_r$ |

With gate equations:

7. $l_0 = s_0 + s_12^{14} + s_22^{28} + s_32^{42} + s_42^{56}$
8. $l_1 = v_0 + v_12^{14} + v_22^{28} + v_32^{42} + v_42^{56}$
9. $l_r = l_0 + l_12^{70} + l_22^{140} + l_32^{210}$

## Gate costs for evaluating non-native field multiplication

* 6 gates to range-constrain $r$
* 6 gates to range-constrain $q$
* 3 gates to range-constrain both $lo_1$ and $hi_2$
* 6 gates to evaluate non-native field arithmetic
* 2 gates to evaluate prime-field limbs of $r$ and $q$
* 1 gate to evaluate prime-field identity $a_rb_r - q_rp_r - r_r = 0 \text{ mod } r$

Discounting the extra gates from the sorted-list component of the range check, the gate cost is 24.

We add 50 additional wires into the sorted list, adding the equivalent of 12.5 gates.

This brings the total gate cost to 36.5 gates.