# Dealing with Negatives

When working with circuits, the elements of our computation can only be expressed as non-negative element of a Prime Field.

If the prime field is `bn254` (which is the case for halo2lib and circom) the prime is

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

It means that only number is the set `[0, p)` can exist in a circuit. Each number $n$ outside of this set will be considered $n\mod p$.


So can we deal with negatives? The answer is yes. If you want to represent $-a$ in a field $\mod p$ you simply need to find the additive inverse of $a$ which is the number $b$ that when added to $a$ gives back zero.

$a + b = 0 \mod p$

For example the additive inverse of 4, in the 7 prime field is 3:

$4 + b = 0 \mod 7$
$4 + 3 = 0 \mod 7$

Therefore we can represent the value -4 as 3. Which is equal to:

$- b= p - b \mod p$
$-b = 7 - 4 \mod p$
$-b = 3 \mod p$

In conclusion, the additive inverse of a number in a prime field is the number you need to add to it to get zero, modulo the prime defining the field. It can be determined by subtracting the number from the prime.

### Subtraction

If we have to perform a subtraction $a - b$ we can simply consider $-b$ as the additive inverse of b so performing an addition between $a$ and the additive inverse of b.

4 - 5 mod 7
4 + (7 - 5) mod 7
4 + 2 mod 7
6 mod 7

### Multiplication with Negatives

That's also the case when you have to perform multiplication with a factor which is a negative value.

4 * (-5) mod 7
4 * 2 mod 7 
1 mod 7

So the key takeaway here is that subtraction and multiplication with negatives can performed within a finite field of non-negative elements.

### Centered Remainder

In cryptographic protocols that involve lattice-based cryptography is it common to work within centered remainder sets which ensure that error distributions are symmetric around zero.

Considering a prime field with modulus 7, you are used to define the set as $[0, p)$. When dealing with a Centered Remainder set, this is defined as $[-\frac{p}{2}, \frac{p}{2})$.


Here's an implementation of the `get_centered_remainder` algorithm in Python => https://github.com/enricobottazzi/rlwe/blob/main/poly.py#L59.

def get_centered_remainder(x, modulus):
    # The concept of the centered remainder is that after performing the modulo operation,
    # The result is in the set (-modulus/2, ..., modulus/2], rather than [0, ..., modulus-1].
    # If r is in range [0, modulus/2] then the centered remainder is r.
    # If r is in range [modulus/2 + 1, modulus-1] then the centered remainder is r - modulus.
    # If modulus is 7, then the field is {-3, -2, -1, 0, 1, 2, 3}.
    # 10 % 7 = 3. The centered remainder is 3.
    # 11 % 7 = 4. The centered remainder is 4 - 7 = -3.
    r = x % modulus
    return r if r <= modulus / 2 else r - modulus

How can we work with a centered remainder field in a circuit, in which we cannot represent negative numbers?

### How Circom deals with negatives

A similar concept is adopted in Circom when defining comparators => https://docs.circom.io/circom-language/basic-operators/#relational-operators.


Note that this is just a `val(x)` function that describes how to evaluate an element within the circuit. All the operations are safely performed inside the circuit using their actual element in the set [0, p). This `val` function only express a way to express the value of an element inside the circuit.

The `val()` behaves the same way as the `get_centered_remainder()` function presented before.

The takeaway here is that the centered remainder set doesn't actually influence the nature of the operations being performed only on non-negative values within the set [0, p) inside the circuit.

### Addition

Here's how addition operation is performed inside a circuit where the finite field is `p`.


If we want to operate in a centered remainder field, we can just "see" the values differently, similar to what the `val()` function does. It doesn't really influence the nature of the operations


### Multiplication

The same goes for the multiplication



### Application

In the specific application of our interest, namely proving inside a Circuit the Correct Encryption under BFV Scheme, we have to deal with polynomials in which the coefficients are defined within the remainder field [-q/2, q/2).

So as we said before, dealing with this centered remainder field is not a problem. The polynomial passed as input to the circuit will have their coefficients defined in the [-q/2, q/2). To handle this coefficients inside the circuit we simply perform a `get_normal_remainder` operation on the coefficients. The resulting coefficients will be used as input to the circuit.

def get_normal_remainder (x, modulus):

    if x < 0
        return x % modulus
        
    else 
        return x

get_normal_remainder(-3, 7) = 4
get_normal_remainder(-2, 7) = 5
get_normal_remainder(-1, 7) = 6
get_normal_remainder(0, 7) = 0
get_normal_remainder(1, 7) = 1
get_normal_remainder(2, 7) = 2
get_normal_remainder(3, 7) = 3

All the operations are then safely performed on non-negative integers within the circuit.

The resulting coefficient outputs will then have to be parsed, outside of the circuit, using the `get_centered_remainder` function.

But there's another problem to take into account. In our application the prime field is `q` which is different from the prime field `p` of the circuit.

Halo2 lib provides a chip to perform modulus operations specifying a modulo that is different from the prime field of the circuit [div mod](https://docs.axiom.xyz/zero-knowledge-proofs/getting-started-with-halo2#rangechip-functions).

But there are cases in which the addition and the multiplication can overflow the prime `p` genereating unintended behaviour.

### Wrong Field Operations - Addition

Let's first analyse how addition behaves when $q \neq p$ and $q \lt p$.


The actual (unexpected) behaviour is determined by the fact that the result of the operation $12$ will overflow the prime $p = 11$ and will be therefore interpreted as $12 \mod 11$ inside the circuit, which is equal to $1$.

This operation is not safe because the prime `q` is 3 bits, while the prime `p` is 4 bits. Therefore sum between 2 `q` elements can overflow the prime `p`.

More generally, the addition between two elements of `q`, in which `q` is `n` BITS can result in an element at most of `n + 1` bits.

### Wrong Field Operations - Multiplication

Let's now analyse how multiplication behaves when $q \neq p$ and $q \lt p$.


The actual (unexpected) behaviour is determined by the fact that the result of the operation $30$ will overflow the prime $p = 11$ and will be therefore interpreted as $30 \mod 11$ inside the circuit, which is equal to $8$.

This operation is not safe because the prime `q` is 3 bits, while the prime `p` is 4 bits. Therefore the multiplication between 2 `q` elements can overflow the prime `p`.

More generally, the multiplication between two elements of `q`, in which `q` is `n` BITS can result in an element at most of `n * 2` bits.

### Conclusion

Dealing with a centered remainder set in our own application is not a problem. Considering the coefficients of a polynomial defined in the interval `[-q/2, q/2)`, the solution would be:

- Parse the coefficients with `get_normal_remainder` and use the result as input to the circuit
- Perform the operations inside the circuit
- Parse the output coefficients of the circuit with `get_centered_remainder`

The operations `mod q` performed inside the circuit might not be safe. The safeness of the operations in `q` within a circuit defined in modulo `p` depends on the relative dimensions of the two primes.

If `p` is `m` bits and `q` is `n` bits, all the addition operations between elements of `q` are safe (the result won't ever overflow `p`) if $m_{BITS} \gt t_{BITS} + 1$.

If `p` is `m` bits and `q` is `n` bits, all the multiplication operations between elements of `q` are safe (the result won't ever overflow `p`) if $m_{BITS} \gt t_{BITS} * 2$.

If `q` doesn't meet this requirement (even considering the case in which q is greater than p), we have to resort to BigInt aritmethic as decribed in this blogpost => https://0xparc.org/blog/zk-ecdsa-2