Incomplete and complete addition

We will use formulae for curve arithmetic using affine coordinates on short Weierstrass curves, derived from section 4.1 of Hüseyin Hışıl's thesis.

Incomplete addition

Inputs: $P = (x_{p}, y_{p}), Q = (x_{q}, y_{q})$
Output: $R = P ⸭ Q = (x_{r}, y_{r})$

The formulae from Hışıl's thesis are:

$x_{3} = (\frac{y _{1} - y _{2}}{x _{1} - x _{2}})^{2} - x_{1} - x_{2}$
$y_{3} = \frac{y _{1} - y _{2}}{x _{1} - x _{2}} \cdot (x_{1} - x_{3}) - y_{1} .$

Rename $(x_{1}, y_{1})$ to $(x_{q}, y_{q})$ , $(x_{2}, y_{2})$ to $(x_{p}, y_{p})$ , and $(x_{3}, y_{3})$ to $(x_{r}, y_{r})$ , giving

$x_{r} = (\frac{y _{q} - y _{p}}{x _{q} - x _{p}})^{2} - x_{q} - x_{p}$
$y_{r} = \frac{y _{q} - y _{p}}{x _{q} - x _{p}} \cdot (x_{q} - x_{r}) - y_{q}$

which is equivalent to

$x_{r} + x_{q} + x_{p} = (\frac{y _{p} - y _{q}}{x _{p} - x _{q}})^{2}$
$y_{r} + y_{q} = \frac{y _{p} - y _{q}}{x _{p} - x _{q}} \cdot (x_{q} - x_{r}) .$

Assuming $x_{p} \neq = x_{q}$ , we have

$and ⟺ ⟺ ⟺ ⟺ x_{r} + x_{q} + x_{p} (x_{r} + x_{q} + x_{p}) \cdot (x_{p} - x_{q})^{2} (x_{r} + x_{q} + x_{p}) \cdot (x_{p} - x_{q})^{2} - (y_{p} - y_{q})^{2} y_{r} + y_{q} (y_{r} + y_{q}) \cdot (x_{p} - x_{q}) (y_{r} + y_{q}) \cdot (x_{p} - x_{q}) - (y_{p} - y_{q}) \cdot (x_{q} - x_{r}) = = = = = = (\frac{y _{p} - y _{q}}{x _{p} - x _{q}})^{2} (y_{p} - y_{q})^{2} 0 \frac{y _{p} - y _{q}}{x _{p} - x _{q}} \cdot (x_{q} - x_{r}) (y_{p} - y_{q}) \cdot (x_{q} - x_{r}) 0.$

So we get the constraints:

$(x_{r} + x_{q} + x_{p}) \cdot (x_{p} - x_{q})^{2} - (y_{p} - y_{q})^{2} = 0$
- Note that this constraint is unsatisfiable for $P ⸭ (- P)$ (when $P \neq = O$ ), and so cannot be used with arbitrary inputs.
$(y_{r} + y_{q}) \cdot (x_{p} - x_{q}) - (y_{p} - y_{q}) \cdot (x_{q} - x_{r}) = 0.$

Constraints

$Degree 43 Constraint q_{add-incomplete} \cdot ((x_{r} + x_{q} + x_{p}) \cdot (x_{p} - x_{q})^{2} - (y_{p} - y_{q})^{2}) = 0 q_{add-incomplete} \cdot ((y_{r} + y_{q}) \cdot (x_{p} - x_{q}) - (y_{p} - y_{q}) \cdot (x_{q} - x_{r})) = 0$

Complete addition

$O O (x_{p}, y_{p}) (x, y) (x, y) (x_{p}, y_{p}) + + + + + + O (x_{q}, y_{q}) O (x, y) (x, - y) (x_{q}, y_{q}) = O = (x_{q}, y_{q}) = (x_{p}, y_{p}) = [2] (x, y) = O = (x_{p}, y_{p}) ⸭ (x_{q}, y_{q}), if x_{p} \neq = x_{q} .$

Suppose that we represent $O$ as $(0, 0)$ . ( $0$ is not an $x$ -coordinate of a valid point because we would need $y^{2} = x^{3} + 5$ , and $5$ is not square in $F_{q}$ . Also $0$ is not a $y$ -coordinate of a valid point because $- 5$ is not a cube in $F_{q}$ .)

$P + Q (x_{p}, y_{p}) + (x_{q}, y_{q}) λ x_{r} y_{r} = R = (x_{r}, y_{r}) = \frac{y _{q} - y _{p}}{x _{q} - x _{p}} = λ^{2} - x_{p} - x_{q} = λ (x_{p} - x_{r}) - y_{p}$

For the doubling case, Hışıl's thesis tells us that $λ$ has to instead be computed as $\frac{3 x ^{2}}{2 y}$ .

Define $inv0 (x) = {0, 1/ x, if x = 0 otherwise.$

Witness $α, β, γ, δ, λ$ where:

$α = β = γ = δ = λ = inv0 (x_{q} - x_{p}) inv0 (x_{p}) inv0 (x_{q}) {inv0 (y_{q} + y_{p}), 0, if x_{q} = x_{p} otherwise ⎩ ⎨ ⎧ \frac{y _{q} - y _{p}}{x _{q} - x _{p}}, \frac{3 x _{p} ^{2}}{2 y _{p}} 0, if x_{q} \neq = x_{p} if x_{q} = x_{p} \land y_{p} \neq = 0 otherwise.$

Constraints

$Degree 456666444444 Constraint q_{add} \cdot (x_{q} - x_{p}) \cdot ((x_{q} - x_{p}) \cdot λ - (y_{q} - y_{p})) q_{add} \cdot (1 - (x_{q} - x_{p}) \cdot α) \cdot (2 y_{p} \cdot λ - 3 x_{p}^{2}) q_{add} \cdot x_{p} \cdot x_{q} \cdot (x_{q} - x_{p}) \cdot (λ^{2} - x_{p} - x_{q} - x_{r}) q_{add} \cdot x_{p} \cdot x_{q} \cdot (x_{q} - x_{p}) \cdot (λ \cdot (x_{p} - x_{r}) - y_{p} - y_{r}) q_{add} \cdot x_{p} \cdot x_{q} \cdot (y_{q} + y_{p}) \cdot (λ^{2} - x_{p} - x_{q} - x_{r}) q_{add} \cdot x_{p} \cdot x_{q} \cdot (y_{q} + y_{p}) \cdot (λ \cdot (x_{p} - x_{r}) - y_{p} - y_{r}) q_{add} \cdot (1 - x_{p} \cdot β) \cdot (x_{r} - x_{q}) q_{add} \cdot (1 - x_{p} \cdot β) \cdot (y_{r} - y_{q}) q_{add} \cdot (1 - x_{q} \cdot γ) \cdot (x_{r} - x_{p}) q_{add} \cdot (1 - x_{q} \cdot γ) \cdot (y_{r} - y_{p}) q_{add} \cdot (1 - (x_{q} - x_{p}) \cdot α - (y_{q} + y_{p}) \cdot δ) \cdot x_{r} q_{add} \cdot (1 - (x_{q} - x_{p}) \cdot α - (y_{q} + y_{p}) \cdot δ) \cdot y_{r} = = = = = = = = = = = = 000000000000 Meaning x_{q} \neq = x_{p} ⟹ λ = \frac{y _{q} - y _{p}}{x _{q} - x _{p}} {x_{q} = x_{p} \land y_{p} \neq = 0 ⟹ λ = \frac{3 x _{p} ^{2}}{2 y _{p}} x_{q} = x_{p} \land y_{p} = 0 ⟹ x_{p} = 0 x_{p} \neq = 0 \land x_{q} \neq = 0 \land x_{q} \neq = x_{p} ⟹ x_{r} = λ^{2} - x_{p} - x_{q} x_{p} \neq = 0 \land x_{q} \neq = 0 \land x_{q} \neq = x_{p} ⟹ y_{r} = λ \cdot (x_{p} - x_{r}) - y_{p} x_{p} \neq = 0 \land x_{q} \neq = 0 \land y_{q} \neq = - y_{p} ⟹ x_{r} = λ^{2} - x_{p} - x_{q} x_{p} \neq = 0 \land x_{q} \neq = 0 \land y_{q} \neq = - y_{p} ⟹ y_{r} = λ \cdot (x_{p} - x_{r}) - y_{p} x_{p} = 0 ⟹ x_{r} = x_{q} x_{p} = 0 ⟹ y_{r} = y_{q} x_{q} = 0 ⟹ x_{r} = x_{p} x_{q} = 0 ⟹ y_{r} = y_{p} x_{q} = x_{p} \land y_{q} = - y_{p} ⟹ x_{r} = 0 x_{q} = x_{p} \land y_{q} = - y_{p} ⟹ y_{r} = 0$

Max degree: 6

Analysis of constraints

Propositions:

$(1) (2) (3) (4) (5) (6) x_{q} \neq = x_{p} ⟹ λ = (y_{q} - y_{p}) / (x_{q} - x_{p}) (x_{q} = x_{p}) \land y_{p} \neq = 0 ⟹ λ = 3 x_{p}^{2} /2 y_{p} (x_{p} \neq = 0) \land (x_{q} \neq = 0) \land ((x_{q} \neq = x_{p}) \lor (y_{q} \neq = - y_{p})) ⟹ (x_{r} = λ^{2} - x_{p} - x_{q}) \land (y_{r} = λ \cdot (x_{p} - x_{r}) - y_{p}) x_{p} = 0 ⟹ (x_{r}, y_{r}) = (x_{q}, y_{q}) x_{q} = 0 ⟹ (x_{r}, y_{r}) = (x_{p}, y_{p}) x_{q} = x_{p} \land y_{q} = - y_{p} ⟹ (x_{r}, y_{r}) = (0, 0)$

Cases:

$(x_{p}, y_{p}) + (x_{q}, y_{q}) = (x_{r}, y_{r})$

Note that we rely on the fact that $0$ is not a valid $x$ -coordinate or $y$ -coordinate of a point on the Pallas curve other than $O$ .

$(0, 0) + (0, 0)$
- Completeness:
  
  $(1) (2) (3) (4) (5) (6) holds because x_{q} = x_{p} holds because y_{p} = 0 holds because x_{p} = 0 holds because (x_{r}, y_{r}) = (x_{q}, y_{q}) = (0, 0) holds because (x_{r}, y_{r}) = (x_{p}, y_{p}) = (0, 0) holds because (x_{r}, y_{r}) = (0, 0) .$
- Soundness: $(x_{r}, y_{r}) = (0, 0)$ is the only solution to $(6) .$
$(x, y) + (0, 0)$ for $(x, y) \neq = (0, 0)$
- Completeness:
  
  $(1) (2) (3) (4) (5) (6) holds because x_{q} \neq = x_{p}, therefore λ = (y_{q} - y_{p}) / (x_{q} - x_{p}) is a solution holds because x_{q} \neq = x_{p}, therefore α = (x_{q} - x_{p})^{- 1} is a solution holds because x_{q} = 0 holds because x_{p} \neq = 0, therefore β = x_{p}^{- 1} is a solution holds because (x_{r}, y_{r}) = (x_{p}, y_{p}) holds because x_{q} \neq = x_{p}, therefore α = (x_{q} - x_{p})^{- 1} and δ = 0 is a solution.$
- Soundness: $(x_{r}, y_{r}) = (x_{p}, y_{p})$ is the only solution to $(5) .$
$(0, 0) + (x, y)$ for $(x, y) \neq = (0, 0)$
- Completeness:
  
  $(1) (2) (3) (4) (5) (6) holds because x_{q} \neq = x_{p}, therefore λ = (y_{q} - y_{p}) / (x_{q} - x_{p}) is a solution holds because x_{q} \neq = x_{p}, therefore α = (x_{q} - x_{p})^{- 1} is a solution holds because x_{p} = 0 holds because x_{p} = 0 only when (x_{r}, y_{r}) = (x_{q}, y_{q}) holds because x_{q} \neq = 0, therefore γ = x_{q}^{- 1} is a solution holds because x_{q} \neq = x_{p}, therefore α = (x_{q} - x_{p})^{- 1} and δ = 0 is a solution.$
- Soundness: $(x_{r}, y_{r}) = (x_{q}, y_{q})$ is the only solution to $(4) .$
$(x, y) + (x, y)$ for $(x, y) \neq = (0, 0)$
- Completeness:
  
  $(1) (2) (3) (4) (5) (6) holds because x_{q} = x_{p} holds because x_{q} = x_{p} \land y_{p} \neq = 0, therefore λ = 3 x_{p}^{2} /2 y_{p} is a solution holds because x_{r} = λ^{2} - x_{p} - x_{q} \land y_{r} = λ \cdot (x_{p} - x_{r}) - y_{p} in this case holds because x_{p} \neq = 0, therefore β = x_{p}^{- 1} is a solution holds because x_{p} \neq = 0, therefore γ = x_{q}^{- 1} is a solution holds because x_{q} = x_{p} and y_{q} \neq = - y_{p}, therefore α = 0 and δ = (y_{q} + y_{p})^{- 1} is a solution.$
- Soundness: $λ$ is computed correctly, and $(x_{r}, y_{r}) = (λ^{2} - x_{p} - x_{q}, λ \cdot (x_{p} - x_{r}) - y_{p})$ is the only solution.
$(x, y) + (x, - y)$ for $(x, y) \neq = (0, 0)$
- Completeness:
  
  $(1) (2) (3) (4) (5) (6) holds because x_{q} = x_{p} holds because x_{q} = x_{p} \land y_{p} \neq = 0, therefore λ = 3 x_{p}^{2} /2 y_{p} is a solution (although λ is not used in this case) holds because x_{q} = x_{p} and y_{q} = - y_{p} holds because x_{p} \neq = 0, therefore β = x_{p}^{- 1} is a solution holds because x_{q} \neq = 0, therefore γ = x_{q}^{- 1} is a solution holds because (x_{r}, y_{r}) = (0, 0)$
- Soundness: $(x_{r}, y_{r}) = (0, 0)$ is the only solution to $(6) .$
$(x_{p}, y_{p}) + (x_{q}, y_{q})$ for $(x_{p}, y_{p}) \neq = (0, 0)$ and $(x_{q}, y_{q}) \neq = (0, 0)$ and $x_{p} \neq = x_{q}$
- Completeness:
  
  $(1) (2) (3) (4) (5) (6) holds because x_{q} \neq = x_{p}, therefore λ = (y_{q} - y_{p}) / (x_{q} - x_{p}) is a solution holds because x_{q} \neq = x_{p}, therefore α = (x_{q} - x_{p})^{- 1} is a solution holds because x_{r} = λ^{2} - x_{p} - x_{q} \land y_{r} = λ \cdot (x_{p} - x_{r}) - y_{p} in this case holds because x_{p} \neq = 0, therefore β = x_{p}^{- 1} is a solution holds because x_{q} \neq = 0, therefore γ = x_{q}^{- 1} is a solution holds because x_{q} \neq = x_{p}, therefore α = (x_{q} - x_{p})^{- 1} and δ = 0 is a solution.$
- Soundness: $λ$ is computed correctly, and $(x_{r}, y_{r}) = (λ^{2} - x_{p} - x_{q}, λ \cdot (x_{p} - x_{r}) - y_{p})$ is the only solution.

The halo2 Book

Incomplete addition

Constraints

Complete addition

Constraints

Analysis of constraints

Propositions:

Cases: