# Elliptic Curve Addition
## Metadata
**Status**:: #x
**Zettel**:: #zettel/permanent
**Created**:: [[2024-03-28]]
**Parent**:: [[Elliptic Curve]]
## Motivation
The set of points in the elliptic curve plus a special point *Infinity* and the addition operator form an [[Abelian Group]]. It can be used to define [[Elliptic Curve Scalar Multiplication]] which is also an [[Abelian Group]] and is isomorphic to $\mathrm{GF}(n)$. Because it's hard to compute `a` from `aG`, such isomorphism can be used to prove an expression without revealing the secret numbers.
## Definition
Let Infinity be denoted as 0.
To add 2 distinct points P and Q, follow these steps:
1. Draw a line through P and Q.
2. Find the third intersection and negate the y axis.
As demonstrate in the first graph in fig.1, $P + Q = -R$. If there's no third intersection, the result is 0 as in the third graph. The intuition is that the intersection is at infinity.
To add a point Q to itself (doubling Q), following these steps:
1. Draw the tangent line of the curve at the point Q.
2. Find the second intersection and negate the y axis.
As demonstrate in the second graph in fig.1, $Q + Q = -P$. If there's no second intersection, the result is 0 as in the forth graph.
![[ecc-addition.svg|fig.1 Elliptic Curve Addition]]
Also define that:
- P + 0 = P
- 0 + P = P
- 0 + 0 = 0
## Adding Distinct Points
For two distinct points $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$, the result of $P_1 + P_2$ is 0 if $x_1 = x_2$. Otherwise the result is $P_3 = (x_3, y_3)$.
> [!tldr] Summary
> $
> \begin{align}
> \lambda &= \frac{y_2 - y_1}{x_2 - x_1} \\
> x_3 &= \lambda^2-x_1-x_2 \\
> y_3 &= \lambda(x_1-x_3) - y_1 \\
> \end{align}
> $
> ^n4mj9n
Let $\lambda$ be the slope of the line:
$
\lambda = \frac{y_2 - y_1}{x_2 - x_1}
$
The line though $P_1$ and $P_2$ can be written as:
$
\tag{1}
y = \lambda(x - x_1) + y_1
$
Since $-P_3$ is also on the line, thus
$
\begin{align}
-y_3 &= \lambda(x_3-x_1) + y_1\\
\tag{2} y_3 &= \lambda(x_1-x_3) - y_1\\
\end{align}
$
Substituting equation (1) into $y^2 = x^3 + ax + b$ gives
$
\begin{align}
(\lambda x + y_1 - \lambda x_1)^2 &= x^3 + ax + b \\
\tag{3} x^3 - \lambda^2 x^2 + a'x + c' &= 0
\end{align}
$
The value of $a', c'$ does not matter. Given the equation (3) and the Vieta's Formula, it is known that:
$
x_1 + x_2 + x_3 = - \frac{-\lambda^2}{1} = \lambda^2
$
Thus
$\tag{4} x_3=\lambda^2-x_1-x_2$
> [!note] Vieta's Formula
> For a cubic polynomial $ax^3 + bx^2 + cx + d = 0$, the sum of its three roots is $-\frac{b}{a}$
## Doubling
For a point $P_1 = (x_1, y_1)$, the result of $P_1 + P_1$ is 0 if $y_1 = 0$. Otherwise the result is $P_3 = (x_3, y_3)$.
> [!tldr] Summary
> $
> \begin{align}
> \lambda &= \frac{3x_1^2+a}{2y_1} \\
> x_3 &= \lambda^2-2x_1 \\
> y_3 &= \lambda(x_1-x_3) - y_1 \\
> \end{align}
> $
> ^52zrdy
The algorithm is similar to [[#Adding Distinct Points]] except that $\lambda$ becomes the slope of the tangent line of the curve at the point $P_1$. The tangent line slope can be computed using derivative:
$\lambda = y'(x_1)$
The steps to compute derivative of $y^2 = x^3 + ax + b$
$
\begin{align}
\frac{dy^2}{dx} &= \frac{d(x3 + ax + b)}{dx} \\
2y\frac{dy}{dx} &= 3x^2+a \\
\frac{dy}{dx} &= \frac{3x^2 + a}{2y}
\end{align}
$
Or use [[♯ Sympy|Sympy]] to compute the derivative:
```python
from sympy import symbols, diff, solve, simplify
# Define symbols
x, y, a, b = symbols('x y a b')
# Define the elliptic curve equation
roots = solve(y**2 - x**3 - a*x - b, y)
for root in roots:
print(f"y = {root}")
dy = simplify(diff(root, x).subs(root, y))
print(f"dy = {dy}")
# y = -sqrt(a*x + b + x**3)
# dy = (a + 3*x**2)/(2*y)
# y = sqrt(a*x + b + x**3)
# dy = (a + 3*x**2)/(2*y)
```
Thus
$\lambda = \frac{3x_1^2+a}{2y_1}$
Doubling use the same equations (2) and (4) to compute $x_3$ and $y3$. For (4), let $x_2 = x_1$, because there are two identical roots at $x_1$.
## Known Issues
- Using different equations to compute $\lambda$ is [[Mike Rosing - Defense Against Power Analysis Attacks Avoiding Elliptic Curve Side Channel Attacks (Highlights)|vulnerable to the side channel attacks]].
- Division is expensive, which can be optimized by using [[Elliptic Curve in the Homogeneous Coordinate|Homogeneous Coordinate]].
## Implementations
- [py_ecc/py_ecc/bn128/bn128_curve.py](https://github.com/ethereum/py_ecc/blob/main/py_ecc/bn128/bn128_curve.py)
## References
- [[RareSkills Authors - Elliptic Curve Point Addition (Highlights)]]
- [Vieta's formulas - Wikipedia](https://en.wikipedia.org/wiki/Vieta's_formulas)