# ECC gadget

[TOC]

Orchard straw protocol: https://hackmd.io/Yyz4wYntSASHfpvqNN4fYQ?both

## Witness point
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
x_A & y_A & x_P & y_P & \lambda_1 & \lambda_2 & q_{add} & q_{double} & q_{mul} & q_{mul\_fixed} & q_{point} \\ \hline
0 & 0 & x_p & y_p & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline
\end{array}

Constraints:
- $y_p^2 = x_p^3 + b,$ where $b=5$ from the Pallas equation

## Point doubling
(Refer to https://zcash.github.io/halo2/background/curves.html#point-doubling for point doubling formula)

Input: $P = (x_P, y_P)$
Output: $A = [2]P = (x_A, y_A)$

\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
x_A & y_A & x_P & y_P & q_{add} & q_{double} & q_{mul} & q_{mul\_fixed} \\ \hline
x_a & y_a & x_p & y_p & 0 & 1 & 0 & 0 \\ \hline
\end{array}

Formulae:
$\lambda_1 = \frac{3 x_p^2}{2 \cdot y_p}$
$x_a = \lambda_1^2 - 2 \cdot x_p$
$y_a = \lambda_1(x_p - x_a) - y_p$

Substituting for $\lambda_1$, we get the constraints:
$4 \cdot y_p^2(x_a + 2 \cdot x_p) - 9 x_p^4 = 0$
$2 \cdot y_p(y_a + y_p) - 3 x_p^2(x_p - x_a) = 0$

## Point addition
(Refer to https://zcash.github.io/halo2/background/curves.html#todo-point-addition for point addition formula)

Inputs: $P = (x_P, y_P), Q = (x_Q, y_Q)$
Output: $A = P + Q = (x_A, y_A)$

\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
x_A & y_A & x_P & y_P & q_{add} & q_{double} & q_{mul} & q_{mul\_fixed} \\ \hline
x_q & y_q & x_p & y_p & 1 & 0 & 0 & 0 \\ \hline
x_a & y_a & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
\end{array}

Formulae:
$\lambda_1 \cdot (x_p - x_{q}) = y_p - y_{q}$
$x_{a} = \lambda_1^2 - x_{q} - x_p$
$y_{a} = \lambda_1(x_{q} - x_{a}) - y_{q}$

Substituting for $\lambda_1$, we get the constraints:
$(x_{a} + x_{q} + x_p) \cdot (x_p - x_q)^2 - (y_p - y_{q})^2 = 0$
$(y_{a} + y_{q})(x_p - x_{q}) - (y_p - y_{q})(x_{q} - x_{a}) = 0$

## Variable-base scalar multiplication
See https://hackmd.io/o9EzZBwxSWSi08kQ_fMIOw?view

## Load fixed bases
For each fixed point, we precompute Lagrange interpolation polynomials for its multiples using 3-bit windows. Since we only need these points for scalar multiplication with 255-bit scalars, we can stop at $\mathsf{ceiling}(255/3) = 85$ windows.

For some fixed base $B,$ define a matrix: $M[0..84][0..7]$ such that:

- for the first 84 rows $M[0..83][0..7]$: $M[w][k] = [(k+2) \cdot (2^3)^w]B$
- in the last row $M[84][0..7]$: $M[w][k] = [k \cdot (2^3)^w - \sum\limits_{j=0}^{83} (2)^{3j+1}]B$

This avoids adding the point at infinity in the case $k = 0$.

Assert that all the matrix entries have distinct $x$-coordinates. We don't have enough table space to use lookups (that would need $5 \times \mathsf{ceiling}(255/3) \times 2^3$ entries for $3$-bit tables), so we should use interpolation instead.

(We checked that using fewer tables and some doublings doesn't help, relative to interpolation.)

For each set of fixed-base multiples $M[w] = (M[w][0], \cdots, M[w][7]), w \in [0..84]$:
- define a Lagrange interpolation polynomial $\mathcal{L}_x(k)$ that maps $k \in [0..7]$ to the $x$-coordinate of the multiple $M[w][k]$, i.e.
- $\mathcal{L}_x(k) = ([(k + 2) \cdot (2^3)^w] B)_x$ for $w \in [0..83]$;
- $\mathcal{L}_x(k) = ([k \cdot (2^3)^w - \sum\limits_{j=0}^{83} (2)^{3j+1}] B)_x$ for $w = 84$; and
- find a value $z_w$ such that $z_w + (M[w][k])_y$ is a square $u^2$ in the field, but the wrong-sign $y$-coordinate $z_w - (M[w][k])_y$ does not produce a square.

Repeating this for all $85$ windows, we end up with:
- an $85 \times 8$ table $\mathcal{L}_x$ storing $8$ coefficients interpolating the $x-$coordinate for each window; and
- a length-$85$ array $Z$ of $z_w$'s.

Each $x$-coordinate interpolation polynomial will be of the form
$$\mathcal{L}_x[w](k) = c_0 + c_1 \cdot k + c_2 \cdot k^2 + \cdots + c_7 \cdot k^7,$$
where $w \in [0..84]$ and $c_k$'s are the coefficients for each power.

### Reusing for multiple bases
Note that in the Orchard protocol, we have $5$ fixed bases:
* $\mathcal{K}^{\mathsf{Orchard}}$ ([for nullifier](https://zcash.github.io/orchard/design/nullifiers.html))
* $\mathsf{nf} = [F_{\mathsf{nk}}(\rho) + \psi \pmod{p})] \mathcal{K}^{\mathsf{Orchard}} + \mathsf{cm}$
* base for $\mathsf{NoteCommit^{Orchard}}$
* $\mathcal{V}$ and $\mathcal{R}$ bases for $\mathsf{ValueCommit^\mathsf{Orchard}}$
* $\mathcal{G}$ base for $\mathsf{SpendAuthSig}^\mathsf{Orchard}$

We reuse the same selector columns for each base.

## Witness scalar (for fixed-base scalar mul)
We decompose a 255-bit scalar $\alpha \in [0, q)$ in 3-bit windows (i.e. base $2^3 = 8$), which gives $\mathsf{ceiling}(255 / 3) = 85$ windows:

\begin{align*}
\alpha &= \sum\limits_{w = 0}^{84} k_w \cdot 8^w \\
&= \sum k_0 + k_1 \cdot 8 + k_2 \cdot 8^2 + \cdots + k_{84} 8^{84}.
\end{align*}

where each $k_w \in [0..7].$

Assignment:
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
k & q_{witness\_scalar\_fixed}\\ \hline
k_0 & 1 \\ \hline
k_{1} & 1 \\ \hline
\vdots & 1 \\ \hline
k_{83} & 1 \\ \hline
k_{84} & 1 \\ \hline
\end{array}

Constraints:
$q_{witness\_scalar\_fixed} \cdot \mathsf{range\_check\_8}(k_i)$

## Fixed-base scalar multiplication
We implement fixed-base scalar multiplication with precomputed points encoded in interpolation polynomials.

Given an input scalar $\alpha$ and a fixed base $B$, we compute $[\alpha]B$ as such:

1. Decompose $\alpha = \sum\limits_{w = 0}^{84} k_w \cdot 8^w$ in 3-bit windows.
2. For each $k_w,$ we have loaded the coefficients of the $x$-coordinate interpolation polynomial $\mathcal{L}_x[w]$ such that $\mathcal{L}_x[w](k_w) = M[w][k]_x.$
- for the first 84 rows $M[0..83][0..7]$: $$M[w][k] = [(k+2) \cdot (2^3)^w]B$$
- in the last row $M[84][0..7]$: $$M[w][k] = [k \cdot (2^3)^w - \sum\limits_{j=0}^{83} (2)^{3j+1}]B$$

3. We have also loaded the $Z$ array such that $Z[w] = z_w.$
4. We witness the $x$- and $y$-coordinates $(x_w,y_w) = M[w][k_w].$
5. Check that $(x_w, y_w)$ is on the curve: $y_w^2 = x_w^3 + b$.
6. We also witness $u_w$ such that $y_w + z_w = u_w^2$.
7. Use point addition to sum the $M[w][k_w]$'s, resulting in $[\alpha]B$.

Constraints:
- $x_w = \mathcal{L}_x[w](k_w)$;
- $y_w^2 = x_w^3 + b,$ where $b = 5$ (from the Pallas curve equation);
- $u_w^2 = y_w + Z[w].$

\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
k & x_A & y_A & x_P & y_P & u_P & c_0 & c_1 & c_2 & c_3 & c_4 & c_5 & c_6 & c_7 & z & q_{add} & q_{mul\_fixed} & q_{witness\_point} \\ \hline
k_0 & x_{a, 0} & y_{a, 0} & M[0][k_0]_x & M[0][k_0]_y & u_{0} &c_{0,0} & c_{1,0} & c_{2,0} & c_{3,0} & c_{4,0} & c_{5,0} & c_{6,0} & c_{7,0} & z_{0} & 1 & 1 & 1 \\ \hline
k_{1} & x_{a,1} & y_{a,1} & M[1][k_1]_x & M[1][k_1]_y & u_{1} &c_{0,1} & c_{1,1} & c_{2,1} & c_{3,1} & c_{4,1} & c_{5,1} & c_{6,1} & c_{7,1} & z_{1} & 1 & 1 & 1 \\ \hline
k_{2} & x_{a,2} & y_{a,2} & M[2][k_2]_x & M[2][k_2]_y & u_{2} &c_{0,2} & c_{1,2} & c_{2,2} & c_{3,2} & c_{4,2} & c_{5,2} & c_{6,2} & c_{7,2} & z_{2} & 1 & 1 & 1 \\ \hline
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \hline
k_{84}& x_{a,84} & y_{a,84} & M[84][k_{84}]_x & M[84][k_{84}]_y & u_{84} & c_{0,84}& c_{1,84} & c_{2,84} & c_{3,84} & c_{4,84} & c_{5,84} & c_{6,84} & c_{7,84} & z_{84} & 1 & 1 & 1 \\ \hline
& x_{a} & y_{a} & & & & & & & & & & & & & & & \\ \hline
\end{array}

### Fixed-base scalar multiplication with signed short exponent

This is used for $\mathsf{ValueCommit^{Orchard}}$.

We want to compute $\mathsf{ValueCommit^{Orchard}_{rcv}}(\mathsf{v^{old}} - \mathsf{v^{new}}) = [\mathsf{v^{old}} - \mathsf{v^{new}}] \mathcal{V} + [\mathsf{rcv}] \mathcal{R}$, where
$$
-(2^{64}-1) \leq \mathsf{v^{old}} - \mathsf{v^{new}} \leq 2^{64}-1
$$

$\mathsf{v^{old}}$ and $\mathsf{v^{new}}$ are each already constrained to 64 bits (by their use as inputs to $\mathsf{NoteCommit^{Orchard}}$).

Witness the sign $s$ and magnitude $m$ such that
$$
s \in \{-1, 1\} \\
m \in [0, 2^{64}) \\
\mathsf{v^{old}} - \mathsf{v^{new}} = s \cdot m
$$

Then compute $P = [m] \mathcal{V}$, and conditionally negate $P$ using $(x, y) \mapsto (x, s \cdot y)$.

> We need to precompute $M[21][0..7]$: $M[w][k] = [k \cdot (8)^w - \sum\limits_{j=0}^{20} (8)^j]B$