不完整与完整点加法（Incomplete and complete addition） - halo2 中文手册 (The halo2 Book

译自 halo2 book:https://zcash.github.io/halo2/design/gadgets/ecc/addition.html

我们将使用短 Weierstrass 曲线上仿射坐标(affine coordinates)的曲线算术公式, 推导自 Hüseyin Hışıl 博士论文的第 4.1 节。

不完全加法(Incomplete addition)

输入: $P = (x_{p}, y_{p}), Q = (x_{q}, y_{q})$
输出: $R = P ⸭ Q = (x_{r}, y_{r})$

Hışıl 论文中的公式为:

$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} .$

把 $(x_{1}, y_{1})$ 重命名为 $(x_{q}, y_{q})$ ,把 $(x_{2}, y_{2})$ 重命名为 $(x_{p}, y_{p})$ ,把 $(x_{3}, y_{3})$ 重命名为 $(x_{r}, y_{r})$ ,得到

$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}$

这等价于

$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}) .$

假设 $x_{p} \neq = x_{q}$ ,我们有

$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.$

于是我们得到约束:

$(x_{r} + x_{q} + x_{p}) \cdot (x_{p} - x_{q})^{2} - (y_{p} - y_{q})^{2} = 0$
- 注意此约束对于 $P ⸭ (- P)$ (当 $P \neq = O$ 时)是不可满足的, 因此不能用于任意输入。
$(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} .$

假设我们把 $O$ 表示为 $(0, 0)$ 。( $0$ 不是有效点的 $x$ 坐标,因为那将需要 $y^{2} = x^{3} + 5$ ,而 $5$ 在 $F_{q}$ 中不是平方数。同样 $0$ 也不是有效点的 $y$ 坐标,因为 $- 5$ 在 $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}$

对于倍点(doubling)情形,Hışıl 的论文告诉我们 $λ$ 必须改为计算为 $\frac{3 x ^{2}}{2 y}$ 。

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

见证(Witness) $α, β, γ, δ, λ$ ,其中:

$α = β = γ = δ = λ = 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})$

注意我们依赖于这样一个事实: $0$ 不是 Pallas 曲线上除 $O$ 之外任何点的有效 $x$ 坐标或 $y$ 坐标。

$(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)$ 是 $(6)$ 的唯一解。
$(x, y) + (0, 0)$ ,其中 $(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})$ 是 $(5)$ 的唯一解。
$(0, 0) + (x, y)$ ,其中 $(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})$ 是 $(4)$ 的唯一解。
$(x, y) + (x, y)$ ,其中 $(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): $λ$ 被正确计算,且 $(x_{r}, y_{r}) = (λ^{2} - x_{p} - x_{q}, λ \cdot (x_{p} - x_{r}) - y_{p})$ 是唯一解。
$(x, y) + (x, - y)$ ,其中 $(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)$ 是 $(6)$ 的唯一解。
$(x_{p}, y_{p}) + (x_{q}, y_{q})$ ,其中 $(x_{p}, y_{p}) \neq = (0, 0)$ 且 $(x_{q}, y_{q}) \neq = (0, 0)$ 且 $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): $λ$ 被正确计算,且 $(x_{r}, y_{r}) = (λ^{2} - x_{p} - x_{q}, λ \cdot (x_{p} - x_{r}) - y_{p})$ 是唯一解。

Keyboard shortcuts

halo2 中文手册 (The halo2 Book · 简体中文版)

不完全加法(Incomplete addition)

约束(Constraints)

完全加法(Complete addition)

约束(Constraints)

约束分析(Analysis of constraints)

命题(Propositions):

情形(Cases):