译自 halo2 book：background/curves.md

椭圆曲线(elliptic curve)

在有限域上构造的椭圆曲线是另一种重要的密码学工具。

我们使用椭圆曲线，因为它们提供了一个密码学 群(group)，即一个其中离散对数问题（下面讨论）困难的群。

定义曲线方程有若干种方式，但就我们的目的而言，设 ${\mathbb{F}}_p$ 是一个大的（255 位的）域，再让 $y^2=x^3+b$（对某个常数 $b$）的解 $(x,y)$ 的集合定义椭圆曲线 $E({\mathbb{F}}_p)$ 上的 ${\mathbb{F}}_p$-有理点(${\mathbb{F}}_p$-rational points)。这些 $(x,y)$ 坐标称为"仿射坐标(affine coordinates)"。每个 ${\mathbb{F}}_p$-有理点，连同充当群单位元的"无穷远点(point at infinity)" $\mathcal{O}$，都可以被解释为某个群的元素。按惯例，椭圆曲线群用加法记法书写。

"一条直线上的三个点之和为零，即无穷远点。"

群加法法则很简单：要把两个点相加，找到同时经过这两个点的直线并求出第三个点，然后对其 $y$ 坐标取负。一个点与自身相加的情形，称为倍点(point doubling)，需要特殊处理：我们找到与该点相切的直线，然后找到与这条直线相交的另一个唯一的点并取负。此外，在一个点与其负元"相加"的情况下，结果是无穷远点。

把点相加和倍乘的能力自然地给了我们用整数（称为 标量(scalars)）来缩放它们的方法。曲线上点的个数即群的阶。如果这个数是素数 $q$，那么这些标量可以被视为某个 标量域(scalar field) ${\mathbb{F}}_q$ 的元素。

椭圆曲线在正确设计时具有一个重要的安全性质。给定两个随机元素 $G,H\in E({\mathbb{F}}_p)$，求满足 $[a]G=H$ 的 $a$（也就是 $H$ 关于 $G$ 的离散对数），在经典计算机上被认为是计算上不可行的。这称为椭圆曲线离散对数假设(elliptic curve discrete log assumption)。

如果一个椭圆曲线群 $\mathbb{G}$ 具有素数阶 $q$（就像 Halo 2 中使用的那些），那么它是一个有限循环群。回忆 群(groups) 一节中讲过，这意味着它同构于 $\mathbb{Z}/q\mathbb{Z}$，或等价地同构于标量域 ${\mathbb{F}}_q$。每个可能的生成元 $G$ 都确定了这个同构；于是标量那一侧的某个元素，恰好就是对应群元素关于 $G$ 的离散对数。在密码学安全的椭圆曲线的情形下，这个同构在 $\mathbb{G}\to {\mathbb{F}}_q$ 方向上难以计算，因为椭圆曲线离散对数问题是困难的。

利用这个同构、用标量而不是用群元素来思考基于群的密码学协议和算法，有时是有帮助的。这能使证明和记法更简单。

例如，在证明系统的论文中，用记号 $[x]$ 来表示离散对数为 $x$ 的群元素（其中生成元是隐含的）已变得很常见。

我们在 "distinct-x 定理" 中也用到了这个想法，以证明 Sapling 中 椭圆曲线标量乘法 的优化的正确性，以及原始 Halo 论文 附录 C 中一个基于自同态(endomorphism)的优化。

曲线算术(Curve arithmetic)

倍点(Point doubling)

最简单的情形是给一个点 $(x_0,y_0)$ 做倍点。继续我们的例子 $y^2=x^3+b$，这首先通过计算导数来完成 $$\lambda =\frac{\mathrm{d}y}{\mathrm{d}x}=\frac{3x^2}{2y}.$$

为得到 $(x_1,y_1)=(x_0,y_0)+(x_0,y_0)$ 的表达式，我们考虑

$$\begin{array}{rl}\frac{-y_1-y_0}{x_1-x_0}=\lambda & ⟹-y_1=\lambda (x_1-x_0)+y_0\\ & ⟹\boxed{y_1=\lambda (x_0-x_1)-y_0}.\end{array}$$

为得到 $x_1$ 的表达式，我们把 $y=\lambda (x_0-x)-y_0$ 代入椭圆曲线方程：

$$\begin{array}{rl}{y}^2=x^3+b& ⟹(\lambda (x_0-x)-y_0{)}^2=x^3+b\\ & ⟹x^3-{\lambda }^2{x}^2+\cdots =0\leftarrow \text{(rearranging terms)}\\ & =(x-x_0)(x-x_0)(x-x_1)\leftarrow \text{(known roots x0,x0,x1)}\\ & =x^3-(x_0+x_0+x_1)x^2+\cdots .\end{array}$$

比较 $x^2$ 项的系数给出 ${\lambda }^2=x_0+x_0+x_1⟹\boxed{x_1={\lambda }^2-2x_0}.$

射影坐标(Projective coordinates)

不幸的是，这需要对 $2y$ 做一次开销很大的求逆。我们可以通过安排我们的方程来"推迟"逆的计算，从而避免这一点，因为在单个曲线运算之后，我们通常不需要立即得到所得点的实际仿射 $(x^{\prime },y^{\prime })$ 坐标。我们引入第三个坐标 $Z$，并像下面这样把曲线方程用 $Z^3$ 缩放：

$$Z^3{y}^2=Z^3{x}^3+Z^{3}b$$

我们原来的曲线就是这条曲线在 $Z=1$ 限制下的样子。如果我们允许仿射点 $(x,y)$ 由 $X=xZ$、$Y=yZ$ 和 $Z\ne 0$ 表示，那么我们就有了 齐次射影曲线(homogenous projective curve)

$$Y^{2}Z=X^3+Z^{3}b.$$

当 $Z\ne 0$ 时，从 $(X,Y,Z)$ 得到 $(x,y)$ 就像计算 $(X/Z,Y/Z)$ 那么简单。（当 $Z=0,$ 时，我们处理的是无穷远点 $O:=(0:1:0)$。）在这种形式下，我们现在有了一种便利的方法来推迟倍点所需的求逆。一般策略是用 $x=X/Z$ 和 $y=Y/Z$ 把 $x^{\prime },y^{\prime }$ 表达为有理函数(rational function)，重新整理以使它们的分母相同，然后取所得点 $(X,Y,Z)$，使 $Z$ 为公共分母且 $X=x^{\prime }Z,Y=y^{\prime }Z$。

射影坐标往往（但并非总是）比仿射坐标更高效。当我们有不同的方式应用蒙哥马利技巧时，或者当我们处在电路环境中（其中乘法和求逆的开销大致相当——至少就电路规模而言）时，可能会有例外。

下面展示一个不做求逆给点 $(X,Y,Z)=(xZ,yZ,Z)$ 做倍点的例子。代入 $X,Y,Z$ 给出 $$\lambda =\frac{3x^2}{2y}=\frac{3(X/Z{)}^2}{2(Y/Z)}=\frac{3X^2}{2YZ}$$

并给出 $$\begin{array}{rl}{x}^{\prime }& ={\lambda }^2-2x\\ & ={\lambda }^2-\frac{2X}{Z}\\ & =\frac{9X^4}{4Y^2{Z}^2}-\frac{2X}{Z}\\ & =\frac{9X^4-8X{Y}^{2}Z}{4Y^2{Z}^2}\\ & =\frac{18X^{4}YZ-16X{Y}^3{Z}^2}{8Y^3{Z}^3}\\ & \\ y^{\prime }& =\lambda (x-x^{\prime })-y\\ & =\lambda (\frac{X}{Z}-\frac{9X^4-8X{Y}^{2}Z}{4Y^2{Z}^2})-\frac{Y}{Z}\\ & =\frac{3X^2}{2YZ}(\frac{X}{Z}-\frac{9X^4-8X{Y}^{2}Z}{4Y^2{Z}^2})-\frac{Y}{Z}\\ & =\frac{3X^3}{2Y{Z}^2}-\frac{27X^6-24X^3{Y}^{2}Z}{8Y^3{Z}^3}-\frac{Y}{Z}\\ & =\frac{12X^3{Y}^{2}Z-8Y^4{Z}^2-27X^6+24X^3{Y}^{2}Z}{8Y^3{Z}^3}\end{array}$$

注意 $x^{\prime }$ 和 $y^{\prime }$ 的分母是相同的。因此，我们不必计算 $(x^{\prime },y^{\prime })$，而是可以计算 $(X,Y,Z)$，其中 $Z=8Y^3{Z}^3$，且 $X,Y$ 设为相应的分子，使得 $X/Z=x^{\prime }$ 且 $Y/Z=y^{\prime }$。这完全避免了倍点时执行求逆的需要，而当把两个不同的点相加时也可以做类似的事情。

点加法(Point addition)

现在我们把两个具有不同 $x$ 坐标的点 $P=(x_0,y_0)$ 和 $Q=(x_1,y_1)$（其中 $x_0\ne x_1$）相加，得到 $R=P+Q=(x_2,y_2).$ 直线 $\overline{PQ}$ 的斜率为 $$\lambda =\frac{y_1-y_0}{x_1-x_0}⟹y-y_0=\lambda \cdot (x-x_0).$$

利用 $\overline{PQ}$ 的表达式，我们计算 $-R$ 的 $y$ 坐标 $-y_2$ 为： $$-y_2-y_0=\lambda \cdot (x_2-x_0)⟹\boxed{y_2=\lambda (x_0-x_2)-y_0}.$$

把 $\overline{PQ}$ 的表达式代入曲线方程 $y^2=x^3+b$ 得到 $$\begin{array}{rl}{y}^2=x^3+b& ⟹(\lambda \cdot (x-x_0)+y_0{)}^2=x^3+b\\ & ⟹x^3-{\lambda }^2{x}^2+\cdots =0\leftarrow \text{(rearranging terms)}\\ & =(x-x_0)(x-x_1)(x-x_2)\leftarrow \text{(known roots x0,x1,x2)}\\ & =x^3-(x_0+x_1+x_2)x^2+\cdots .\end{array}$$

比较 $x^2$ 项的系数给出 ${\lambda }^2=x_0+x_1+x_2⟹\boxed{x_2={\lambda }^2-x_0-x_1}$。

重要说明：

• 存在不带边界情形的点加法高效公式¹（即所谓的"完备(complete)"公式），它把加法和倍点两种情形统一在一起。用这些公式把一个点与其负元相加，结果产生 $Z=0$，它表示无穷远点。
• 此外，还有其他模型，比如雅可比表示(Jacobian representation)，其中 $(x,y)=(x{Z}^2,y{Z}^3,Z)$，曲线用 $Z^6$ 而不是 $Z^3$ 重新缩放，这种表示具有甚至更高效的算术，但没有统一/完备公式。
• 我们可以在齐次射影坐标空间中通过把两个曲线点 $(X_1,Y_1,Z_1)$ 和 $(X_2,Y_2,Z_2)$ 的 Z 坐标"齐次化(homogenizing)"来轻松地比较它们是否相等；检查变为 $X_1{Z}_2=X_2{Z}_1$ 和 $Y_1{Z}_2=Y_2{Z}_1$。

曲线自同态(Curve endomorphisms)

设想 ${\mathbb{F}}_p$ 有一个本原三次单位根，换言之 $3|p-1$ 因而存在一个元素 ${\zeta }_p$ 生成一个 $3$ 阶乘法子群。注意我们的示例椭圆曲线 $y^2=x^3+b$ 上的一个点 $(x,y)$ 有两个"表亲"点：$({\zeta }_{p}x,y),({\zeta }_p^{2}x,y)$，因为计算 $x^3$ 实际上杀死了 $x$ 坐标的 $\zeta$ 分量。应用映射 $(x,y)\mapsto ({\zeta }_{p}x,y)$ 就是对曲线应用一个自同态(endomorphism)。其中涉及的精确机制很复杂，但当曲线有素数 $q$ 个点（因而有素数"阶"）时，这个自同态的效果就是把该点乘以 ${\mathbb{F}}_q$ 中的一个标量，而这个标量也是标量域中的一个本原三次根 ${\zeta }_q$。

曲线点压缩(Curve point compression)

给定曲线上的一个点 $P=(x,y)$，我们知道它的负元 $-P=(x,-y)$ 也在曲线上。要唯一地确定一个点，我们只需编码它的 $x$ 坐标连同其 $y$ 坐标的符号。

序列化(Serialization)

正如 域(Fields) 一节中提到的，我们可以把域元素的最低有效位解释为它的"符号"，因为它的加法逆元总有相反的最低有效位。所以我们把 $y$ 坐标的最低有效位记为 sign。

Pallas 和 Vesta 定义在 ${\mathbb{F}}_p$ 和 ${\mathbb{F}}_q$ 域上，其元素可以用 $255$ 位表示。这恰好在 32 字节表示中留出一个未用的位。我们把 $y$ 坐标的 sign 位塞进 $x$ 坐标表示的最高位：

         <----------------------------------- x --------------------------------->
Enc(P) = [_ _ _ _ _ _ _ _] [_ _ _ _ _ _ _ _] ... [_ _ _ _ _ _ _ _] [_ _ _ _ _ _ _ sign]
          ^                <------------------------------------->                 ^
         LSB                              30 bytes                                MSB

充当群单位元的"无穷远点" $\mathcal{O}$ 没有仿射 $(x,y)$ 表示。然而事实证明，Pallas 或 Vesta 曲线上都没有 $x=0$ 或 $y=0$ 的点。因此我们使用"伪造的"仿射坐标 $(0,0)$ 来编码 $\mathcal{O}$，其结果是全零的 32 字节数组。

反序列化(Deserialization)

反序列化一个压缩曲线点时，我们首先读取最高有效位作为 ysign，即 $y$ 坐标的符号。然后，我们把这一位置零以恢复原始的 $x$ 坐标。

如果 $x=0,y=0,$ 我们返回"无穷远点" $\mathcal{O}$。否则，我们继续计算 $y=\sqrt{x^3+b}.$ 这里，我们读取 $y$ 的最低有效位作为 sign。如果 sign == ysign，我们已经有了正确的符号，直接返回曲线点 $(x,y)$。否则，我们对 $y$ 取负并返回 $(x,-y)$。

曲线环(Cycles of curves)

设 $E_p$ 是有限域 ${\mathbb{F}}_p$ 上的椭圆曲线，其中 $p$ 为素数。我们把它记为 $E_p/{\mathbb{F}}_p.$ 并把 $E_p$ 在 ${\mathbb{F}}_p$ 上的点构成的群记出来，其阶为 $q=\#E({\mathbb{F}}_p).$ 对于这条曲线，我们称 ${\mathbb{F}}_p$ 为"基域(base field)"，称 ${\mathbb{F}}_q$ 为"标量域(scalar field)"。

我们在椭圆曲线 $E_p/{\mathbb{F}}_p$ 上实例化我们的证明系统。这使我们能够证明关于 ${\mathbb{F}}_q$-算术电路可满足性(arithmetic circuit satisfiability)的命题。

（旁注）如果我们的曲线 $E_p$ 在 ${\mathbb{F}}_p$ 上，为什么算术电路反而在 ${\mathbb{F}}_q$ 中？ 证明系统基本上是在电路中标量的编码（或更确切地说，是对系数为标量的多项式的承诺）上工作。当标量的编码/承诺是 $E_p/{\mathbb{F}}_p$ 中的椭圆曲线点时，这些标量就在 ${\mathbb{F}}_q$ 中。

然而，验证者(verifier)的大部分算术计算都在基域 ${\mathbb{F}}_p$ 上，因此可以高效地表达为一个 ${\mathbb{F}}_p$-算术电路。

（旁注）为什么验证者的计算（主要）在 ${\mathbb{F}}_p$ 上？ Halo 2 验证者实际上必须使用电路输出的信息执行群运算。像倍点和点加法这样的群运算使用 ${\mathbb{F}}_p$ 中的算术，因为点的坐标在 ${\mathbb{F}}_p$ 中。

这促使我们构造另一条标量域为 ${\mathbb{F}}_p$ 的曲线，它有一个 ${\mathbb{F}}_p$-算术电路，能够高效地验证来自第一条曲线的证明。作为额外好处，如果这第二条曲线的基域是 $E_q/{\mathbb{F}}_q,$ 它就会生成可以在第一条曲线的 ${\mathbb{F}}_q$-算术电路中被高效验证的证明。换言之，我们在 $E_q/{\mathbb{F}}_q$ 上实例化第二个证明系统，与第一个形成一个 2-环(2-cycle)：

TODO：Pallas-Vesta 曲线

参考：https://github.com/zcash/pasta

哈希到曲线(Hashing to curves)

有时，能够针对某个输入产生椭圆曲线 $E_p/{\mathbb{F}}_p$ 上的一个随机点，并且使任何人都不会知道它（关于任何其他基的）离散对数，是很有用的。

这在 关于哈希到椭圆曲线的互联网草案(Internet draft on Hashing to Elliptic Curves) 中有详细描述。根据效率和安全要求的不同，可以使用若干种算法。该互联网草案使用的框架用到了几个函数：

• hash_to_field：接受一个字节序列输入，并把它映射到基域 ${\mathbb{F}}_p$ 中的一个元素；
• map_to_curve：接受一个 ${\mathbb{F}}_p$ 元素，并把它映射到 $E_p$。

TODO：简化 SWU(Simplified SWU)

参考：https://eprint.iacr.org/2019/403.pdf

参考文献

1. Renes, J., Costello, C., & Batina, L. (2016, May). "Complete addition formulas for prime order elliptic curves." In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 403-428). Springer, Berlin, Heidelberg. ↩