# ECC Operations Optimization Plan

Suppose the scalar field of the curve

$$y^2 = x^3 + b$$

is $F_q$ where $q$ has 256 bits and the baby Jubjub prime is $p$ which is slightly less 254-bit. Choose $n$ and $k$ so that
* $nk >= 256$
* $3n + log_2(2k^2) + \epsilon < 254$

where $\epsilon$ is a small constant.

## Addition and Multiplication (no carries)

We represent BigInts with $k$ registers of $n$ bits each. For register size $X = 2^n$, define addition and multiplication without carries by:
* $\sum_i a_i X^i +' \sum_i b_i X^i = \sum_i c_i X^i$ with $c_i = a_i + b_i$
* $\sum_i a_i X^i *' \sum_i b_i X^i = \sum_i d_i X^i$ with $d_i = \sum_{j = 0}^i a_j * b_{i - j}$

### Tracking overflows

Define $n_{z_i} = \lceil log_2(z_i) \rceil$ for a signal $x$. This function represents the number of bits needed to represent $x$.

For an array $z = \sum_i z_i X^i$, define $n_z = \max_i (n_{z_i})$. Tracking $n_z$ allows us to ensure that we are never overflowing the maximum theoretical register size of 253 bits, even when representing numbers in overflow representation.

Additionally, define $k_z$ to be the number of such $n_z$-bit registers used to represent $k$.

Suppose that $c = a +' b$. Then $n_c \leq \max(n_a, n_b) + 1$, and $k_c = \max(k_a, k_b)$.

Now suppose that $d = a *' b$. Then $n_d \leq n_a + n_b + \lceil log_2(\min(k_a, k_b)) \rceil$, and $k_d = k_a + k_b - 1$.

## Handling Carries

See Wen-Ding's code here: https://zkrepl.dev/?gist=e168291f275526db7511dc2d049f7219

## Canonical representation

See Wen-Ding's code here: https://zkrepl.dev/?gist=86d694a9583cc18db77a01a82bcaf884

## Prime trick

Consider $X = 2^{64}$ and

$$S = \sum_{i=0}^9 a_i X^i$$

Where each of the $a_i$ is up to $192+\epsilon$ bits (probably fine to say $\epsilon \leq 6$).

We wish to find some $S'$ that is congruent to $S$ modulo $p$ (secp256k1 prime) with few registers.

The $p = 2^{256} - k$ trick is:

$$2^{256} * Z \equiv k * Z \mod p$$

Since the secp256k1 prime has $p = 2^{256} - 2^{32} - \delta$ for some small $\delta \approx 2^{10}$, we can write the following congruence:

$$S$$
$$\equiv a_9X^9 + a_8X^8 + a_7X^7 + a_6X^6 + a_5X^5 + a_4X^4 + a_3X^3 + a_2X^2 + a_1X + a_0$$
$$\equiv (2^{64}+2^{33}\delta + \delta^2)a_9X + (2^{64}+2^{33}\delta + \delta^2)a_8 + (2^{32}+\delta)a_7X^3 + (2^{32}+\delta)a_6X^2 + (2^{32}+\delta)a_5X + (2^{32}+\delta)a_4 + a_3X^3 + a_2X^2 + a_1X + a_0$$

Since $(2^{32}+\delta)^2 = 2^{64} + 2^{33}\delta + \delta^2$.

Let $C_i$ be the coefficient of $X^i$ after terms are accumulated in this last equation. We have:

$$C_3 = (2^{32}+\delta)a_7 + a_3$$
$$C_2 = (2^{32}+\delta)a_6 + a_2$$
$$C_1 = (2^{64}+2^{33}\delta+\delta^2)a_9 + (2^{32}+\delta)a_5 + a_1$$
$$C_0 = (2^{64}+2^{33}\delta+\delta^2)a_8 + (2^{32}+\delta)a_4 + a_0$$

Let's replace $2^{64}$ with $X$ in the expressions for $C_1$ and $C_0$ and re-accumulate:

$$C_3' = (2^{32}+\delta)a_7 + a_3$$
$$C_2' = (2^{32}+\delta)a_6 + a_2 + a_9$$
$$C_1' = (2^{33}\delta+\delta^2)a_9 + (2^{32}+\delta)a_5 + a_1 + a_8$$
$$C_0' = (2^{33}\delta+\delta^2)a_8 + (2^{32}+\delta)a_4 + a_0$$

We add an additional 44 bits of overflow at most to the registers (the worst coefficient of an $a_i$ involved in a sum is $2^{33}\delta$). Since our $a_i$ are at most 200 bits approximately, the $C_i$ do not overflow the babyjubjub prime (253 bits). So now we have a representation $S' = C_3'X^3 + C_2'X^2 + C_1'X + C_0'$ of a number that is congruent to $S$, such that all of the $C_i'$ are at most 244 bits. After subtracting off some multiple of $p$ we can check that after carries this is equivalent to $0$ in $244 * 4 \approx 1000$ constraints.

For reference, let's see how this plays out for a 7-register number:

$$S$$
$$\equiv a_6X^6 + a_5X^5 + a_4X^4 + a_3X^3 + a_2X^2 + a_1X + a_0$$
$$(2^{32}+\delta)a_6X^2 + (2^{32}+\delta)a_5X + (2^{32}+\delta)a_4 + a_3X^3 + a_2X^2 + a_1X + a_0$$

Here, we get:

$$C_3 = a_3$$
$$C_2 = (2^{32}+\delta)a_6 + a_2$$
$$C_1 = (2^{32}+\delta)a_5 + a_1$$
$$C_0 = (2^{32}+\delta)a_4 + a_0$$

## AddUnequal

For input points $(x_1, y_1)$ and $(x_2, y_2)$ with sum $(x_3, y_3)$, we verify
1. $x_3 = \lambda^2 - x_2 - x_1$ where $\lambda = \frac{y_2-y_1}{x_2-x_1}$
- $(x_1 + x_2 + x_3)(x_2-x_1)^2 - (y_2-y_1)^2 = 0$
2. $\frac{y_3 + y_1}{x_3 - x_1} = \frac{y_3 + y_2}{x_3 - x_2}$, which is equivalent to:
- $y_1 * x_3 + (y_3 + y_2) * x_1 = y_2 * x_3 + (y_3 + y_1) * x_2$
3. $x_3, y_3$ are 4x64 bit numbers in the range [0, p-1]

To verify each of the first two statements, we do the following:
* Evaluate both sides using $+'$ and $*'$ so that no carrying takes place.
* We now wish to verify the identity $\sum_i a_i X^i = \sum_i b_i X^i$ mod $q$ where $0 \leq a_i, b_i < C_1X^3$ for a small constant $C_1$
* [(implementation)](https://zkrepl.dev/?gist=e168291f275526db7511dc2d049f7219). Verify that there is a bigint $r = \sum_i r_i X^i$ for which

$$Carry(\sum_i (a_i - b_i) X^i) = Carry(\sum_i r_i X^i *' \sum_i q_i X^i)$$

Note that we'll have to be a little careful on this third substep. We want the quotient $r$ to be nonnegative, so we probably have to add a fat multiple of $q$ to LHS to ensure that LHS is positive. i.e. If registers can be overful to 200 bits, then following the prime trick we end up four-register overful numbers which are about $136$ bits overful. This gives us $136+256=392$ bit numbers on LHS. So to offset, we probably want to add something like $2^{137}q$ to LHS, which can be easily done by simply adding the registers of $q$ left shifted by $137$ bits to LHS since we're already in overflow representation.

Finally we do a range check.
- [(implementation)](https://zkrepl.dev/?gist=86d694a9583cc18db77a01a82bcaf884). constrain $x_3$ and $y_3$ to be 64 bits per register and also in $[0,p-1]$ by rangechecking that all registers are in $[0,2^{64}-1]$ and if upper registers are all equal to $2^{64}-1$ then checking lowest register is in $[0, 2^{64}-2^{32} - 2^9 -2^8 - 2^7 - 2^6 -2^4 -1 -1]$.

## Double

For input points $(x_1, y_1)$ with double $(x_3, y_3)$, we verify
1. $y_3^2 = x_3^3 + b$
2. $\frac{- y_3 - y_1}{x_3 - x_1} = \frac{3 x_1^2}{2y_1}$, which is equivalent to:
- $-2y_1\cdot (y_3+y_1) = 3x_1^2\cdot(x_3-x_1)$
3. $(x_3,y_3) \neq (x_1,-y_1)$
- only need to do $x_3 \neq x_1$ check
4. $x_3, y_3$ are 4x64 bit numbers and in the range [0,p-1]

Note: If $x_1 = x_2$ and $y_1 + y_2 = 0$, then $P + Q = O$ where $P = (x_1,y_1)$ and $Q = (x_2, y_2)$.

## Additional Resources

Aztec CRT trick: https://hackmd.io/@arielg/B13JoihA8

Previous scratchpad: https://hackmd.io/5YUHE_D-TpKRfxvZtJyAqg?both

Onur Kilic's PLONK strategies: https://hackmd.io/ncuKqRXzR-Cw-Au2fGzsMg