# Non-Native Field Arithmetic

**Disclaimer:** This documentation was written on January, 2023. 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.
This article explains Non-Native Field Arithmetic with Rust code implementation examples. There is a [paper](https://hackmd.io/@arielg/B13JoihA8) that explains mathematical part of the arithmetization.

### Notation Summary
* **$p$** = Wrong field modulus (Base)
* **$n$** = Native field modulus (Scalar)
* **$2^t$** = Binary field modulus (Extra CRT modulus)
* **$p'$** = Negative wrong field in Binary Field
* **$q$** = Quotient from the mod p
* **$r$** = Result from the mod p
* **$Limbs$** = $i_1$, $i_2$, $i_3$, $i_4$ are the four limbs of the variable
* **$Bits$** = $t/4$

### Why Non-Native Field Arithmetic is needed?
Non-Native Field Arithmetic is usable when we deal with proof aggregation. In proof systems we use native (**scalar**) field to make constraints, and to make proof verifications we need to use wrong field. We are using constraints to build correct wrong field elements and pair them in such a way to verify the equation. Thanks to Non-Native Field Arithmetic there is a way to extend this feature much further. We can use wrong field elements in native field and we can create new constraints from the wrong field elements representations. To make long story short, with this simulation technique we can merge multiple proofs and create a single proof from them to save resource.

As told above we are doing a native field operations inside a non-native field. For this operation we need to understand [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem#:~:text=In%20mathematics%2C%20the%20Chinese%20remainder,are%20pairwise%20coprime%20(no%20two)) (CRT) and [Residue Number System](https://en.wikipedia.org/wiki/Residue_number_system). We will use CRT to constrain equation to check validity. In the other hand RNS will be used for the calculations.

//RNS example:
//In mod 5 we will have number range (0, 1, 2, 3, 4)
//With RNS we can say that (5, 6, 7, 8, 9) are also in the range of the mod 5.
//This allow us to range infinite number for a given mod.
//This is because when we take mod of that range we still get (0, 1, 2, 3, 4).
(0 % 5 = 0, 1 % 5 = 1, 2 % 5 = 2, 3 % 5 = 3, 4 % 5 = 4)
(5 % 5 = 0, 6 % 5 = 1, 7 % 5 = 2, 8 % 5 = 3, 9 % 5 = 4)
(10 % 5 = 0, 11 % 5 = 1, 12 % 5 = 2, 13 % 5 = 3, 14 % 5 = 4)
...
...
// This is useful when when we take native mod of a wrong field number. 
// Wrong field can be bigger than native mod's range
// but it is still represented in the native field's mod.

// CRT example:
// To calculate CRT we need two or more relatively prime moduli. 
x_in_5 = 2 (mod 5)   => r1 = 2
x_in_7 = 3 (mod 7)   => r2 = 3
x_in_11 = 4 (mod 11) => r3 = 4

// We need to calculate big_m which is m_1 * m_2 * m_3
big_m = 5 * 7 * 11 => big_m = 385

// Also, we will need to calculate big_m1, big_m2 and big_m3
// big_m1 = M / 5, big_m2 = M / 7 and big_m3 = M / 11
big_m_1 = 77
big_m_2 = 55
big_m_3 = 35

// Now we need to calculate m1_inverse, m2_inverse and m3_inverse
// To calculate inverse of them we need to follow formula 
// big_m_i * big_m_i_inverse = 1 (mod m_i)
big_m_1_inv = 77 * big_m_1_inv = 1 (mod 5) => big_m_1_inv = 3
big_m_2_inv = 55 * big_m_2_inv = 1 (mod 7) => big_m_2_inv = 6
big_m_3_inv = 35 * big_m_3_inv = 1 (mod 11)=> big_m_3_inv = 6

// Formula is;
// x = m1 * m1_inverse * r1 + m2 * m2_inverse * r2+ m3 * m3_inverse * r3
x = 77 * 3 * 2 + 55 * 6 * 3 + 35 * 6 * 4 = 2292 (mod 385)
x = 367 (mod 385)

## Implementation of the arithmetic
There is an implementation from the [Eigen-Trust](https://github.com/eigen-trust/eigen-trust) project. You can find [Halo2 circuit implementation](https://github.com/eigen-trust/eigen-trust/blob/master/circuit/src/integer/mod.rs) inside the project but in this article we will see examples from native part of the code.

### Limbs
As we mentioned before, **$p$** is bigger than **$n$**, so we need some tricks to achieve this calculations correctly in **$n$**. We will break down our **$p$** field element to its limbs to achieve this goal. Each limb will have same bit size and this size will be determined from size of the binary field.

### Binary field
We will use a helper field to leverage our **$n$**. We will need such a integer $t$ that satisfies equation:

$2^t * n > p^2 + p$

The reason we want this formula to work out is because, $p * q + r$ cannot be bigger than $p^2 + p$ at max, so we need to range q such that it shouldn't be bigger than $p$.
In Eigen-Trust implementation **$t = 272$**. This number can be divided to 68 bits of 4 limbs. Basically, this bigger field number will allow us to do calculations without losing any data.

## Algorithm for the addition
We will need to calculate `intermediate values`, `quotient`, `residues` and `result`. Formula below is our main equation for the addition operation.

$a + b = q * p + r$

In the code, there is a [ReductionWitness](https://github.com/eigen-trust/protocol/blob/master/circuit/src/integer/native.rs#L42-L61) structure to keep the track for 4 variables that comes out from this calculation.

### Quotient
We will calculate both [`quotient` and `result`](https://github.com/eigen-trust/protocol/blob/master/circuit/src/integer/rns.rs#L246-L255) on wrong field modulus. Quotient is the number of wraps that wraps around the wrong field while we calculate the operation. For addition and subtraction operations, quotient cannot be bigger than 1, so it is either 0 or 1.

### Intermediate
Now we can [calculate intermediate values](https://github.com/eigen-trust/protocol/blob/master/circuit/src/integer/native.rs#L156-L158) with using quotient value. While we calculate intermediate values, we use corresponding value for negative wrong modulus inside the native field modulus.

$intermediate[i] = a[i] + b[i] + p'[i] * q$

after we calculate each limb for the intermediate value we can continue and calculate residue value.
### Residue
When we calculate the residue values, we need to do some shift operations. $lsh_1$ means we are doing one step left shift. Same goes for $rsh_2$ which means two steps right shift operation. $t_i$ and $t_{i+1}$ represents two limbs from intermediate values. $r_i$ and $r_{i+1}$ represents first two limbs from the `result` we got from `quotient` calculation.
#### What is LSH and RSH?
$lsh_i$ means that we multiply given number with the $i$'th element of the `left_shifters` array (same goes for the $rsh_i$). This operation will shift given number to the $i$ times upper limb. In the other hand, multiplying with $rsh_i$ means that we are shifting given number $i$ times to the lower limb. This is useful when we want to merge two or more limbs without losing any data.

// LSH 
    left_shifters: [
     0x0000000000000000000000000000000000000000000000000000000000000001,
     0x0000000000000000000000000000000000000000000000100000000000000000,
     0x0000000000000000000000000000010000000000000000000000000000000000,
     0x0000000000001000000000000000000000000000000000000000000000000000,
    ],
// RSH
    right_shifters: [
     0x0000000000000000000000000000000000000000000000000000000000000001,
     0x0b603a5609b3f6f81dbc9c192fc7933ab42e346981868e480f8e4610fb396ee5,
     0x1b7c016fe8acfaed1a908db2cea9b991a31a140f219532a9568bea8e0766f9dd,
     0x0523513296c10199338287b1e0bedd9955a33201cd88df51769b0bf04e2f27cc,
    ],

// Example:
    example_limbs: [
     0x00000000000000000000000000000000000000000000000c25aaba4210b1aa76,
     0x00000000000000000000000000000000000000000000000d3fe2c80a77092fd3,
     0x00000000000000000000000000000000000000000000000932781096bdece7bd,
     0x0000000000000000000000000000000000000000000000000bd07d269dbdbc38,
    ]
// example_limbs[1] * lsh1 
    example_limbs[1] = example_limbs[1] * left_shifters[1] = [
     0x00000000000000000000000000000000000000000000000c25aaba4210b1aa76,
     0x000000000000000000000000000000d3fe2c80a77092fd300000000000000000,
     0x00000000000000000000000000000000000000000000000932781096bdece7bd,
     0x0000000000000000000000000000000000000000000000000bd07d269dbdbc38,
    ]
// example_limbs[0] + example_limbs[1]
    example_limbs[0] = example_limbs[0] + example_limbs[1] = [
    0x000000000000000000000000000000d3fe2c80a77092fd3c25aaba4210b1aa76,
    0x000000000000000000000000000000d3fe2c80a77092fd300000000000000000,
    0x00000000000000000000000000000000000000000000000932781096bdece7bd,
    0x0000000000000000000000000000000000000000000000000bd07d269dbdbc38,
    ]
// example_limbs[1] * rsh1 
    example_limbs[1] = example_limbs[1] * right_shifters[1] = [
    0x000000000000000000000000000000d3fe2c80a77092fd3c25aaba4210b1aa76,
    0x00000000000000000000000000000000000000000000000d3fe2c80a77092fd3,
    0x00000000000000000000000000000000000000000000000932781096bdece7bd,
    0x0000000000000000000000000000000000000000000000000bd07d269dbdbc38,
    ]
// As we can see, we took second limb and added to the first limb without
// losing any data from the first limb or second limb.
// We can construct original number with following operation:
// Original integer with a single limb =
// example_limbs[3] * lsh3 + example_limbs[2] * lsh2 +
// example_limbs[1] * lsh1 + example_limbs[0] * lsh0 

We need to use formula below for the calculation of the $u_i$ variable.

$u_i = t_i + (t_{i+1} * lsh_1) - r_i - (r_{i+1} * lsh_1) + v_i$

$v_0$ is equal to the zero in the $u_0$ calculation and it will be carrying calculated $v$ for the next iteration.
To calculate $v_i$ for second and future iterations, we need to follow formula below.

$v_i = u_i * rsh_2$

Basically, we are doing a two right shift operation to the $u$ variable. Each $v_i$ value is our one residue value. Residue length will be equal to half of the limbs length. In Eigen-Trust we are using 4 limbs to do these calculations and therefore residue length is equal to 2.

### Result
Result we keep in `ReductionWitness` is basically the `result` from the `quotient` calculation.

### Native Constraint
To do native constraint we need to do

$a + b - p * q - r = 0 (modn)$

// Example:
a = 11 // first number
b = 8 // second number
p = 17 // base modulus in scalar modulus
n = 5 // scalar modulus

// (r, q) = a + b % p
r = 2 // correct result
q = 1 // quotient - number of times we wrap around the wrong field


a_prime = 1 // a % n
b_prime = 3 // b % n
r_prime = 2 // r % n
p_prime = 2 // p modulus inside n field 17 % 5
q_prime = q // For addition q will be either 1 or 0

a_prime + b_prime - p_prime * q - r_prime = 1 + 3 - 2 * 1 - 2 = 0

### Binary Constraint (CRT constraint)
To do Binary (CRT) constraint we need to follow formula below

$u_i - residues[i] * lsh_2 + v_i = 0$

$v_0 = 0$, and in the second and future iterations it will be calculated by following formula below

$v_i = residues[i/2]$

if these results returns 0, then our constraint satisfies.

## Algorithm for the multiplication
We will need several different variables to achieve this implementation. Our main equation is:

$a * b = q * p + r$

In the code, there is a [ReductionWitness](https://github.com/eigen-trust/protocol/blob/master/circuit/src/integer/native.rs#L42-L61) structure to keep the track for variables that comes out from this calculation.

### Quotient
We will calculate both [`quotient` and `result`](https://github.com/eigen-trust/protocol/blob/master/circuit/src/integer/rns.rs#L238-L244) on wrong field modulus. Quotient is the number of wraps that wraps around the wrong field while we calculate the operation. For multiplication and division operations, quotient can be any number.

### Intermediate
Now we can [calculate intermediate values](https://github.com/eigen-trust/protocol/blob/master/circuit/src/integer/native.rs#L205-L210) with using quotient. While we calculate intermediate values we, use corresponding value for negative wrong modulus inside the native field modulus.
To calculate intermediate values for multiplication operation, we need to follow formula below.

$intermediate[i + j] = intermediate[i + j] + a[i] + b[j] + p'[i] * q[j]$

after we calculate each limb for the intermediate value we can continue and calculate residue value.

### Residue
When we calculate the residue values, we need to do some shift operations. $lsh_1$ means we are doing one step left shift. Same goes for $rsh_2$ which means two steps right shift operation. $t_i$ and $t_{i+1}$ represents two limbs from intermediate values. $r_i$ and $r_{i+1}$ represents first two limbs from the `result` we got from `quotient` calculation.
We need to use formula below for the calculation of the $u_i$ variable.

$u_i = t_i + (t_{i+1} * lsh_1) - r_i - (r_{i+1} * lsh_1) + v_i$

$v_0$ is equal to the zero in the $u_0$ calculation and it will be carrying calculated $v$ for the next iteration.
To calculate $v_i$, we need to follow formula below.

$v_i = u_i * rsh_2$

Basically, we are doing a two right shift operation to the $u$ variable. Each $v_i$ value is our one residue value. Residue length will be equal to half of the limbs length. In Eigen-Trust we are using 4 limbs to do these calculations and therefore residue length is equal to 2.

### Result
Result we keep in `ReductionWitness` is basically the `result` from the `quotient` calculation.

### Native Constraint
To do native constraint we need to do

$a * b - p * q - r = 0$

Example:

a = 11 // first number
b = 8 // second number
p = 17 // base modulus in scalar modulus
n = 5 // scalar modulus

//(r, q) = a * b % p
r = 3 // correct result
q = 5 // quotient - number of times we wrap around the wrong field

a_prime = 1 // a % n
b_prime = 3 // b % n
r_prime = 2 // r % n
p_prime = 2 // p modulus inside n field 17 % 5
q_prime = 0 // q % n

a_prime + b_prime - p_prime * q_prime - r_prime = 1 + 3 - 2 * 0 - 3 = 0

### Binary Constraint (CRT constraint)
To do Binary (CRT) constraint we need to follow formula below

$u_i - residues[i] * lsh_2 + v_i = 0$

$v_0 = 0$, and in the second and future iterations it will be calculated by following formula below

$v_i = residues[i/2]$

if these results returns 0, then our constraint satisfies.