企业官网建设流程全解析

ElligatorSwift for secp256k1 深入解析：原理、编码解码算法与实现细节

【免费下载链接】zcashZcash - Internet Money项目地址: https://gitcode.com/GitHub_Trending/zc/zcash

导读

本文基于 Zcash 仓库内 vendored 的 secp256k1 库（路径src/secp256k1）中的官方文档 doc/ellswift.md，系统讲解 ElligatorSwift 这一将 secp256k1 公钥编码为与均匀随机字节串不可区分的 64 字节格式的完整算法。文章从解码函数 $F_u(t)$、编码函数 $F_u^{-1}(x)$ 的数学构造出发，逐步推导 secp256k1（$a=0, b=7$ 曲线）上的特化公式，并结合模块源码 main_impl.h 与公开 API 头文件 secp256k1_ellswift.h 说明每个数学步骤对应的实际实现函数。读完本文，你将掌握 ElligatorSwift 的核心原理、编码/解码/密钥生成/ECDH 的完整调用方式，以及它在抵抗公钥指纹检测场景（如 BIP324 传输加密）中的设计动机。

1. 引言：ElligatorSwift 解决什么问题

ellswift模块引入了一种新的64 字节公钥格式：它能够把（均匀随机的）secp256k1 公钥编码成与均匀随机字节数组计算上不可区分的 64 字节数组。这一性质对抵抗"公钥指纹检测"至关重要——在未加密的 P2P 协议中，攻击者可以通过检查公钥是否落在曲线上来识别加密流量，而 ElligatorSwift 编码后的字节在外观上与随机数完全一致，从而隐藏了"这里存在一个公钥"这一事实。

该模块不仅提供公钥与此格式之间的互转函数，还提供直接作用于编码后密钥的密钥生成与 ECDH 便捷函数，用于 BIP324 等传输层加密场景。官方头文件 secp256k1_ellswift.h 开篇即说明：

"This module provides an implementation of ElligatorSwift as well as a version of x-only ECDH using it (including compatibility with BIP324)."

在仓库中，该模块由 configure.ac 的--enable-module-ellswift开关控制（默认开启），并被 CHANGELOG.md 列为新增模块，配套提供 API 头文件与本文所依据的数学背景文档。

1.1 编码的组成结构

编码结果是两个（32 字节大端序）域元素 $u$ 和 $t$ 的拼接。二者共同编码曲线上的一个 x 坐标 $x$（进一步扩展后还可编码完整点 $(x, y)$，见第 4 节）。

• 解码（Decoding）：将 $u$、$t$ 解码为域元素（大于域大小 $p$ 的值取模 $p$），然后计算 $F_u(t)$。对任意 $u$、$t$，$F_u(t)$ 都产生曲线上的一个合法 x 坐标。
• 编码（Encoding）：给定 x 坐标，按以下流程寻找 $(u, t)$：

循环： 1. 均匀随机选取域元素 u 2. 计算集合 L = F_u^{-1}(x)，即满足 F_u(t) = x 的所有 t（最多 8 个） 3. 以概率 1 - #L/8 重新开始循环 4. 从 L 中均匀随机选取 t，返回 (u, t)

这就是ElligatorSwift 算法（此处仅针对 x 坐标，扩展到完整 $(x,y)$ 点见第 4 节）。算法在满足 $F_u(t)=x$ 的（几乎所有）$(u,t)$ 对中均匀随机取样。论文第 3.2 节证明：对曲线上几乎所有 x 坐标（至多 39 个例外），这种编码的数量接近域大小的两倍——精确地说落在 $2q \pm (22\sqrt{q} + O(1))$ 范围内，其中 $q$ 是域大小。正是这种"每个点对应编码数量近似均匀"的计数性质，保证了均匀采样的编码结果在统计上不可区分于随机字节。

2. 解码函数（Decoding Function）

2.1 数学定义与记号

首先给出论文中的记号体系：

• $\mathbb{F}$：大小为 $q$ 的有限域，特征为 5 或更大，且 $q \equiv 1 \mod 3$。
  • 对secp256k1：$q = 2^{256} - 2^{32} - 977$，满足上述要求。
• $E$：满足 $y^2 = x^3 + ax + b$ 的椭圆曲线，$a$、$b$ 为公开常数，且要求判别式 $\Delta_E = -16(4a^3 + 27b^2)$ 为平方数、$(-b \pm \sqrt{-3\Delta_E}/36)/2$ 至少有一个为平方数。这蕴含 $E$ 的阶为奇数或是 4 的倍数。若 $a=0$，该条件恒成立。
  • 对secp256k1：$a=0$，$b=7$。
• $g(x) = x^3 + ax + b$，曲线方程等价于 $y^2 = g(x)$。
• $h(x) = 3x^3 + 4a$。
• $V$：方程 $z^2 = g(x_1)g(x_2)g(x_3)$ 的解集 $(x_1, x_2, x_3, z)$。
• $S_u$：方程 $X^2 + h(u)Y^2 = -g(u)$ 且 $Y \neq 0$ 的解集 $(X, Y)$。
• $P_u$：从 $\mathbb{F}$ 到 $S_u$ 的函数（下文定义）。
• $\psi_u$：从 $S_u$ 到 $V$ 的函数（下文定义）。

与论文的对应关系（论文记号对照）：

• 论文中的 $F_{0,u}$ 即本文的 $F_u$；
• 论文中的 $P$ 即本文的 $P_u(t)$；
• 所有 $S_u$ 集合的并集对应论文中的 $S$；
• 所有 $\psi_u$ 函数（作用在 $S$ 元素上）对应论文中的 $\psi$。

一个关键观察：对 $V$ 而言，等式左侧 $z^2$ 是平方数，因此右侧也必须是平方数。由于域中两个非平方数相乘得到平方数，三个右端因子 ${g(x_1), g(x_2), g(x_3)}$ 中必须恰好有 1 个或恰好 3 个是平方数。这意味着对任意 $(x_1,x_2,x_3,z) \in V$，${x_1, x_2, x_3}$ 中至少有一个是 $E$ 上的合法 x 坐标（唯一的例外是 $z=0$，但此时三个值中仍有一个是合法 x 坐标）。

2.2 解码函数的定义

定义解码函数 $F_u(t)$为：

1. 计算 $(x_1, x_2, x_3, z) = \psi_u(P_u(t))$。
2. 返回 $(x_3, x_2, x_1)$ 中第一个满足"是 $E$ 上合法 x 坐标"（即 $g(x)$ 为平方数）的元素。

其中 $P_u(t) = (X(u, t), Y(u, t))$，具体公式为：

$$ \begin{array}{lcl} X(u, t) & = & \left{\begin{array}{ll} \dfrac{g(u) - t^2}{2t} & a = 0 \ \dfrac{g(u) + h(u)(Y_0(u) - X_0(u)t)^2}{X_0(u)(1 + h(u)t^2)} & a \neq 0 \end{array}\right. \ Y(u, t) & = & \left{\begin{array}{ll} \dfrac{X(u, t) + t}{u \sqrt{-3}} = \dfrac{g(u) + t^2}{2tu\sqrt{-3}} & a = 0 \ Y_0(u) + t(X(u, t) - X_0(u)) & a \neq 0 \end{array}\right. \end{array} $$

$P_u(t)$ 在以下情形未定义：

• $a=0$ 时：$u=0$ 或 $t=0$（除零）；$g(u) = -t^2$（会导致 $Y=0$）。
• $a \neq 0$ 时：$X_0(u) = 0$ 或 $h(u)t^2 = -1$（除零）；$Y_0(u)(1 - h(u)t^2) = 2X_0(u)t$（会导致 $Y=0$）。

其中 $X_0(u)$、$Y_0(u)$ 定义于论文附录 A，依赖于曲线的具体性质。

而 $\psi_u$ 对所有曲线都是一样的：$\psi_u(X, Y) = (x_1, x_2, x_3, z)$，其中

$$ \begin{array}{lcl} x_1 & = & \dfrac{X}{2Y} - \dfrac{u}{2} \ x_2 & = & -\dfrac{X}{2Y} - \dfrac{u}{2} \ x_3 & = & u + 4Y^2 \ z & = & \dfrac{g(x_3)}{2Y}(u^2 + ux_1 + x_1^2 + a) = \dfrac{-g(u)g(x_3)}{8Y^3} \end{array} $$

注意 $x_1 + x_2 = -u$，这一关系在编码时的 round-trip 校验中被反复使用。

2.3 secp256k1 特化的解码（$a=0$）

将所有公式代入并针对 $a=0$ 曲线化简，解码 $(u, t)$ 到 x 坐标的流程为：

定义 $F_u(t)$为：

1. 令 $X = \dfrac{u^3 + b - t^2}{2t}$。
2. 令 $Y = \dfrac{X + t}{u\sqrt{-3}}$。
3. 返回 $(u + 4Y^2,\ \dfrac{-X}{2Y} - \dfrac{u}{2},\ \dfrac{X}{2Y} - \dfrac{u}{2})$ 中第一个使 $g(x)$ 为平方数的元素。

输入重映射：为保证每个输入都能解码到合法 x 坐标，在 $P_u$ 未定义的情形（$u=0$、$t=0$ 或 $g(u) = -t^2$）下需要对输入做重映射：

定义 $F_u(t)$为：

1. $u'=u$（若 $u \neq 0$），否则 $u'=1$（保证 $u' \neq 0$）。
2. $t'=t$（若 $t \neq 0$），否则 $t'=1$（保证 $t' \neq 0$）。
3. $t''=t'$（若 $g(u') \neq -t'^2$），否则 $t''=2t'$（保证 $t'' \neq 0$ 且 $g(u') \neq -t''^2$）。
4. $X = \dfrac{u'^3 + b - t''^2}{2t''}$。
5. $Y = \dfrac{X + t''}{u'\sqrt{-3}}$。
6. 返回 $(u' + 4Y^2,\ \dfrac{-X}{2Y} - \dfrac{u'}{2},\ \dfrac{X}{2Y} - \dfrac{u'}{2})$ 中第一个使 $x^3 + b$ 为平方数的元素。

文档特别说明：这些选择并非严格必要——在任意未定义情形下返回固定常量也能满足正确性，但上述做法实现简单且在特殊情形下输出也足够均匀。

与论文的差异：论文中这些条件因使用射影坐标而输出无穷远点 $\infty$，但实现希望避免调用方处理这一特殊情况，因此改为重映射输入。

实现对应：这一逻辑分别实现为：

• secp256k1_ellswift_xswiftec_frac_var——解码为用分数（分子/分母）表示的 x 坐标；
• secp256k1_ellswift_xswiftec_var——输出真正的 x 坐标。

两个函数都定义在 main_impl.h 中（xswiftec_frac_var在第 24 行，xswiftec_var在第 135 行）。在 secp256k1_ellswift.h 的注释中，解码函数 $f(u,t)$ 被以常量形式给出：$C = 0xa2d2ba93507f1df233770c2a797962cc61f6d15da14ecd47d8d27ae1cd5f852$ 是 $\sqrt{-3}$ 的一个平方根，配合 $u=0 \to 1$、$t=0 \to 1$、$u^3 + t^2 + 7 = 0 \to t$ 加倍三步重映射，然后计算 $X = (u^3 + 7 - t^2)/(2t)$、$Y = (X+t)/(C \cdot u)$，返回 $[u+4Y^2,\ (-X/Y - u)/2,\ (X/Y - u)/2]$ 中第一个落在曲线上的值。

3. 编码函数（Encoding Function）

要实现 $F_u^{-1}(x)$（找出所有满足 $F_u(t) = x$ 的 $t$ 集合），需要逆向整个流程：

1. 找出所有可能通过 $\psi_u$ 中 $x_1$、$x_2$ 或 $x_3$ 公式产生 $x$ 的 $(X, Y) \in S_u$；
2. 用 $P_u^{-1}(X, Y)$ 将这些 $(X, Y)$ 映射回 $t$ 值；
3. 对每个 $t$ 验证 $F_u(t) = x$；
4. 返回验证通过的 $t$ 集合。

其中 $P_u^{-1}$（已知 $(X,Y) \in S_u$ 求 $t$）比 $P_u$ 简单得多：

$$ P_u^{-1}(X, Y) = \left{\begin{array}{ll} Yu\sqrt{-3} - X & a = 0 \ \dfrac{Y-Y_0(u)}{X-X_0(u)} & a \neq 0 \land X \neq X_0(u) \ \dfrac{-X_0(u)}{h(u)Y_0(u)} & a \neq 0 \land X = X_0(u) \land Y = Y_0(u) \end{array}\right. $$

为什么需要第 3 步验证：通过 $x_1$、$x_2$ 表达式找到的 $(X, Y)$，其解码结果有可能在 $x_3$ 位置上恰好是合法曲线点，而解码器对 $x_3$ 有优先权，此时这些 $(X, Y)$ 必须被拒绝。

简化的 round-trip 检查：由于对任意 $t$，${x_1, x_2, x_3}$ 中恰好有 1 个或 3 个是合法 x 坐标，因此"$x_1$ 或 $x_2$ 合法且同时 $x_3$ 也合法"必然意味着三者全部合法。于是可以用一个更简单的检查替代"$x_3$ 是否在曲线上"：检查 $x_1$、$x_2$ 中另一个是否在曲线上。

利用 $\psi_u$ 保证的 $x_1 + x_2 = -u$：给定 $x = x_1$ 或 $x = x_2$，另一个值即为 $-u-x$。因此，当通过 $x_1$ 或 $x_2$ 表达式编码 $x$ 时，只需检查 $g(-u-x)$ 是否为平方数，若是则不把对应的 $t$ 值放入返回集合。该条件不依赖 $X$、$Y$ 或 $t$，可以在计算这些值之前就确定。

类似地，通过 $x_1$ 表达式得到的编码不可能解码到另一个合法 x 坐标（经 $x_2$）——因为若 $x_1$、$x_2$ 解码都有效，则 $x_3$ 也有效并优先返回。因此对 $x_1$、$x_2$ 而言，$g(-u-x)$ 是否为平方数是保证 round-trip 正确所需的唯一检查。这正是解码器选择 $(x_3, x_2, x_1)$ 优先顺序的原因；任何不把 $x_3$ 放在首位的顺序都需要在编码器中做更复杂的 round-trip 检查。

3.1 切换到 $v, w$ 坐标

为简化公式推导，对 $S_u$ 换元：令 $v = (X/Y - u)/2$，$w = 2Y$；反解为 $X = w(u/2 + v)$、$Y = w/2$。于是：

• $S_u'$ 成为满足 $w^2(u^2 + uv + v^2 + a) = -g(u)$ 且 $w \neq 0$ 的 $(v, w)$ 集合。
• 对 $a=0$ 曲线，$P_u^{-1}$ 在 $(v,w)$ 下可写为 $P_u^{'-1}(v, w) = w\left(\frac{\sqrt{-3}-1}{2}u - v\right)$。
• $\psi_u$ 在 $(v,w)$ 下写为 $\psi_u'(v, w) = (x_1, x_2, x_3, z)$：

$$ \begin{array}{lcl} x_1 & = & v \ x_2 & = & -u - v \ x_3 & = & u + w^2 \ z & = & \dfrac{g(x_3)}{w}(u^2 + uv + v^2 + a) = \dfrac{-g(u)g(x_3)}{w^3} \end{array} $$

现在可以显式写出已知 $x$ 求 $(v, w)$ 的表达式：分别把 ${x_1, x_2, x_3}$ 三个表达式对 $v$ 或 $w$ 求解，再用 $S_u'$ 方程求另一变量：

• 假设 $x = x_1$：得 $v = x$，$w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}$（两个解）。
• 假设 $x = x_2$：得 $v = -u-x$，$w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}$（两个解）。
• 假设 $x = x_3$：得 $w = \pm\sqrt{x-u}$，$v = -u/2 \pm \sqrt{-w^2(4g(u) + w^2h(u))}/(2w^2)$（四个解）。

合计最多 8 个候选 $(v, w)$，与第 1 节中 $F_u^{-1}(x)$ 至多 8 个元素的事实吻合。

3.2 避免计算全部逆元素

第 1 节的 ElligatorSwift 算法要求完整计算 $L = F_u^{-1}(x)$，这其实没有必要。

观察：以概率 $(1 - #L/8)$ 重启、否则均匀返回 $L$ 中一个元素的过程，等价于：始终把 $L$ 用 $\bot$ 占位符填充到长度 8，均匀选取一个元素，选到 $\bot$ 就重启：

定义ElligatorSwift(x)为：

循环： 1. 均匀随机选取域元素 u 2. 计算集合 L = F_u^{-1}(x) 3. 构造 8 元素向量 T = L 的元素 + (8 - #L) 个 ⊥ 4. 均匀随机选取 t ∈ T 5. 若 t ≠ ⊥，返回 (u, t)；否则重启循环

由于 $T$ 中元素顺序无关紧要（反正只做均匀选取），无需把所有 $\bot$ 放在末尾。既然有 8 个不同的 $(v, w)$ 求解公式（含 $\pm$ 变体），可以让 $T$ 的每个下标对应恰好一个公式，并保证：

• 无解（除零或平方根不存在）或非法解的情形返回 $\bot$；
• 对 $x_1$、$x_2$ 情形，若 $g(-u-x)$ 是平方数则返回 $\bot$（round-trip 检查）；
• 若多个公式返回相同的非 $\bot$ 结果，除一个外其余都必须改为 $\bot$，以避免引入偏差。

最后一个条件在密码学规模的曲线上发生概率可忽略，但值得考虑，因为它允许在小群上做穷举测试（见 3.4 节对所有这些可忽略情形的分析）。

定义 $T = (G_{0,u}(x), G_{1,u}(x), \ldots, G_{7,u}(x))$，每个 $G_{i,u}$ 对应一个公式，循环可简化为只计算一个逆元素：

定义ElligatorSwift(x)为：

循环： 1. 均匀随机选取域元素 u 2. 均匀随机选取整数 c ∈ [0, 8) 3. 计算 t = G_{c,u}(x) 4. 若 t ≠ ⊥，返回 (u, t)；否则重启循环

该实现对应secp256k1_ellswift_xelligatorswift_var（main_impl.h）。

3.3 求解逆元素 $G_{c,u}$

$c$ 到公式的映射：$c=0$ 对应 $x_1$ 公式，$c=1$ 对应 $x_2$ 公式，$c=2,3$ 对应 $x_3$ 公式；$c=4$ 到 $c=7$ 是上述公式的 $w$ 取相反符号的变体（注意每个公式中 $w$ 都是某个表达式的平方根）。忽略可忽略情形，有：

定义 $G_{c,u}(x)$为：

• 若 $c \in {0, 1, 4, 5}$（$x_1$、$x_2$ 公式）：
  • 若 $g(-u-x)$ 是平方数，返回 $\bot$（因为 $x_3$ 会合法并优先）。
  • 若 $c \in {0, 4}$（$x_1$ 公式），令 $v = x$；否则令 $v = -u-x$（$x_2$ 公式）。
  • 令 $s = -g(u)/(u^2 + uv + v^2 + a)$（下文用 $s = w^2$）。
• 否则（$c \in {2, 3, 6, 7}$，$x_3$ 公式）：
  • 令 $s = x-u$。
  • 令 $r = \sqrt{-s(4g(u) + sh(u))}$。
  • 若 $c \in {3, 7}$，令 $v = (r/s - u)/2$；否则 $v = (-r/s - u)/2$。
• 令 $w = \sqrt{s}$。
• 按 $c$ 返回：
  • $c \in {0, 1, 2, 3}$：返回 $P_u^{'-1}(v, w)$；
  • $c \in {4, 5, 6, 7}$：返回 $P_u^{'-1}(v, -w)$。

失败情形：对非平方数开平方根时返回 $\bot$——对随机输入，两个平方根各有约 50% 概率失败；除零时同样返回 $\bot$，但这只以可忽略概率发生。第一个分支中的除零其实不可能发生：$u^2 + uv + v^2 + a = 0$ 蕴含 $g(-u-x) = g(x)$，意味着 $g(-u-x)$ 为平方数的条件已触发、早已返回 $\bot$。

与论文的差异：论文中的case变量大致对应上述 $c$，但只有 4 个取值（1 到 4）；其最后的 $w$ 条件取反是随机决定的，效果等价但不利于测试。本实现让 $G_{c,u}$确定化，把所有随机选择都收进 $c$ 中。

进一步化简：$c \in {1, 5}$ 与 $c \in {3, 7}$ 实际执行的是同一个 $v \to -u-v$ 变换；且该变换在第一个分支中不改变 $s$（因为 $u^2 + ux + x^2 + a = u^2 + u(-u-x) + (-u-x)^2 + a$）。于是可以把它提取出来并下移：

定义 $G_{c,u}(x)$为：

• 若 $c \in {0, 1, 4, 5}$：
  • 若 $g(-u-x)$ 是平方数，返回 $\bot$。
  • 令 $s = -g(u)/(u^2 + ux + x^2 + a)$；令 $v = x$。
• 否则（$c \in {2, 3, 6, 7}$）：
  • 令 $s = x-u$；令 $r = \sqrt{-s(4g(u) + sh(u))}$；令 $v = (r/s - u)/2$。
• 令 $w = \sqrt{s}$。
• 按 $c$ 返回：
  • $c \in {0, 2}$：$P_u^{'-1}(v, w)$；
  • $c \in {1, 3}$：$P_u^{'-1}(-u-v, w)$；
  • $c \in {4, 6}$：$P_u^{'-1}(v, -w)$；
  • $c \in {5, 7}$：$P_u^{'-1}(-u-v, -w)$。

这揭示了重要性质：给定 $(u, x)$，$t$ 的数量总是恰好 0、4 或 8 个。调用 $P_u^{'-1}$ 之前可能有 0、1 或 2 个 $(v, w)$ 对，每对产生 4 个不同的 $t$ 值。

3.4 特殊情形处理

下列情形只在可忽略的子集输入中发生。对密码学规模的域，若只考虑随机输入，不处理它们也是可以的；文档仍为完备性逐一分析。它们大体分为两类：编码器产生的 $t$ 值不能（或不能保证能）解码回 $x$ 的情形；以及编码器对多个 $c$ 可能产生相同 $t$ 值（从而引入偏差）的情形：

• 在 $x_1$、$x_2$ 分支（$c \in {0, 1, 4, 5}$）：
  • $g(u) = 0$ 时，会有 $s=w=Y=0$，不在 $S_u$ 上。这只在偶数阶曲线上可能出现。排除它同时消除了简化 $x_3$ 检查失效的唯一条件（即 $g(x_1)=g(x_2)=0$ 但 $g(x_3)$ 非平方）。这会排除一些合法编码：当 $g(u)=0$ 且 $u^2+ux+x^2+a=0$（蕴含 $g(x)=0$）时，$S_u'$ 方程退化为 $0=0$，可能存在大量合法 $t$ 值。但编码器反正无法均匀覆盖它们，因为数量通常超过 8。
  • $g(x) = 0$ 时，会产生与 $x_3$ 分支（$c \in {2, 3, 6, 7}$）相同的 $t$，后者被赋予优先权因为它能处理 $g(u)=0$。同样只可能在偶数阶曲线上出现。
• 在 $x_3$ 分支（$c \in {2, 3, 6, 7}$）：
  • $s=0$ 时发生除零。
  • $c \in {3, 7}$ 且 $v = -u-v$ 时，会返回与 $c \in {2, 6}$ 情形相同的 $t$。这等价于检查 $r=0$。它在 $x_1$、$x_2$ 分支中不会出现，因为那会触发"$g(-u-x)$ 是平方数"条件。$w = -w$ 的类似顾虑不存在：$w=0$ 在两个分支中都已不可能——第一个分支需要 $g(u)=0$（偶数阶曲线已排除，其他曲线不可能），第二个分支会触发除零。
• 曲线相关的特殊情形也需拒绝，因为它们会产生解码器不接受的 $(u,t)$，或导致编码器除零：
  • 对 $a=0$ 曲线：$u=0$ 或 $t=0$。后者只能由编码器在 $g(u)=0$ 时达到，需要偶数阶曲线。
  • 对 $a \neq 0$ 曲线：$X_0(u)=0$；$h(u)t^2 = -1$；或 $w(u + 2v) = 2X_0(u)$ 且同时 $w \neq 2Y_0(u)$ 或 $h(u)=0$。

处理所有这些情形的完整版 $G_{c,u}(x)$：

1. 若 $a=0$ 且 $u=0$，返回 $\bot$。
2. 若 $a \neq 0$ 且 $X_0(u)=0$，返回 $\bot$。
3. 若 $c \in {0, 1, 4, 5}$：
   • 若 $g(u)=0$ 或 $g(x)=0$，返回 $\bot$（仅偶数阶曲线）。
   • 若 $g(-u-x)$ 是平方数，返回 $\bot$。
   • 令 $s = -g(u)/(u^2 + ux + x^2 + a)$（不会除零）；令 $v = x$。
4. 否则（$c \in {2, 3, 6, 7}$）：
   • 令 $s = x-u$。
   • 令 $r = \sqrt{-s(4g(u) + sh(u))}$；若非平方数返回 $\bot$。
   • 若 $c \in {3, 7}$ 且 $r=0$，返回 $\bot$。
   • 若 $s = 0$，返回 $\bot$。
   • 令 $v = (r/s - u)/2$。
5. 令 $w = \sqrt{s}$；若非平方数返回 $\bot$。
6. 若 $a \neq 0$ 且 $w(u+2v) = 2X_0(u)$ 且（$w \neq 2Y_0(u)$ 或 $h(u)=0$），返回 $\bot$。
7. 按 $c$ 计算 $t$：$c \in {0,2} \to P_u^{'-1}(v, w)$；$c \in {1,3} \to P_u^{'-1}(-u-v, w)$；$c \in {4,6} \to P_u^{'-1}(v, -w)$；$c \in {5,7} \to P_u^{'-1}(-u-v, -w)$。
8. 若 $a=0$ 且 $t=0$，返回 $\bot$（仅偶数阶曲线）。
9. 若 $a \neq 0$ 且 $h(u)t^2 = -1$，返回 $\bot$。
10. 返回 $t$。

完备性结论：对任意 $u$，对全部 $x$、$c$ 运行上述算法，每个满足 $F_u(t) = x$ 的 $t$ 值都会被恰好到达一次，除以下不可达情形：

• 所有 $P_u(t)$ 未定义的情形：
  • $a=0$ 曲线：$u=0$、$t=0$ 或 $g(u) = -t^2$。
  • $a \neq 0$ 曲线：$h(u)t^2 = -1$、$X_0(u)=0$ 或 $Y_0(u)(1 - h(u)t^2) = 2X_0(u)t$。
• 当 $g(u)=0$ 时，可能存在的、通过 $x_2$ 公式解码到满足 $g(x)=0$ 的 $x$ 的大量 $t$ 值（被 $c \in {0, 1, 4, 5}$ 分支的 $g(u)=0$ 条件排除）。

这些情形在密码学规模曲线上构成 $(u,t)$ 全空间的可忽略子集。

3.5 secp256k1 特化的编码（$a=0$ 奇数阶曲线）

针对奇数阶 $a=0$ 曲线特化：

定义 $G_{c,u}(x)$为：

1. 若 $u=0$，返回 $\bot$。
2. 若 $c \in {0, 1, 4, 5}$：
   • 若 $(-u-x)^3 + b$ 是平方数，返回 $\bot$。
   • 令 $s = -(u^3 + b)/(u^2 + ux + x^2)$（不会除零）；令 $v = x$。
3. 否则（$c \in {2, 3, 6, 7}$）：
   • 令 $s = x-u$。
   • 令 $r = \sqrt{-s(4(u^3 + b) + 3su^2)}$；若非平方数返回 $\bot$。
   • 若 $c \in {3, 7}$ 且 $r=0$，返回 $\bot$。
   • 若 $s = 0$，返回 $\bot$。
   • 令 $v = (r/s - u)/2$。
4. 令 $w = \sqrt{s}$；若非平方数返回 $\bot$。
5. 按 $c$ 返回：
   • $c \in {0, 2}$：$w(\frac{\sqrt{-3}-1}{2}u - v)$；
   • $c \in {1, 3}$：$w(\frac{\sqrt{-3}+1}{2}u + v)$；
   • $c \in {4, 6}$：$w(\frac{-\sqrt{-3}+1}{2}u + v)$；
   • $c \in {5, 7}$：$w(\frac{-\sqrt{-3}-1}{2}u - v)$。

该实现对应secp256k1_ellswift_xswiftec_inv_var（main_impl.h）。而 x-only 的 ElligatorSwift 编码算法仍为：

定义ElligatorSwift(x)为：

循环： 1. 均匀随机选取域元素 u 2. 均匀随机选取整数 c ∈ [0, 8) 3. 计算 t = G_{c,u}(x) 4. 若 t ≠ ⊥，返回 (u, t)；否则重启循环

注意：该逻辑不处理解码器中的 $u=0$、$t=0$、$g(u) = -t^2$ 重映射情形，只是回避它们。虽然并非不可能让编码器瞄准这些情形，但这会把给定 $(u,x)$ 的 $t$ 数量上限推到 8 以上，按比例拖慢 ElligatorSwift 循环，却只为均匀性带来可忽略的增益，得不偿失。

4. 完整 $(x, y)$ 坐标的编码与解码

此前只处理 x 坐标；但有些场景需要编码完整点 $(x, y)$。这些信息可以一并编进 $t$ 中。

关键观察：对任意 $(X, Y) \in S_u$，$(\pm X, \pm Y)$ 也都在 $S_u$ 上，且都映射到同一个 x 坐标。对 $X$ 或 $Y$ 取负只会交换 $x_1$、$x_2$，不影响 $x_3$，也不改变最终 x 坐标（因为 $x_1$、$x_2$ 的顺序只在两者都合法时才有意义，而那种情况下会改用 $x_3$）。然而，这四个 $(X, Y)$ 组合对应四个不同的 $t$ 值，因此可以在 $X$ 或 $Y$ 的符号中编码 y 坐标的符号。它们正好对应 $G_{u,c}$ 定义中的四次 $P_u^{'-1}$ 调用。

与论文的差异：论文把 y 坐标的符号编进一个独立的编码位，而本实现把符号编进 $Y$ 的符号（secp256k1 特化版本则编进 $t$ 的符号，见 4.1 节）。

用 $Y$ 的符号编码 $y$ 的符号：

定义Decode(u, t)（完整 $(x,y)$）为：

1. 计算 $(X, Y) = P_u(t)$。
2. 令 $x$ 为 $(u + 4Y^2,\ \frac{-X}{2Y} - \frac{u}{2},\ \frac{X}{2Y} - \frac{u}{2})$ 中第一个使 $g(x)$ 为平方数的值。
3. 令 $y = \sqrt{g(x)}$。
4. 若 $sign(y) = sign(Y)$，返回 $(x, y)$；否则返回 $(x, -y)$。

编码使用 $G_{c,u}(x, y)$ 函数：

定义 $G_{c,u}(x, y)$为：

1. 若 $c \in {0, 1}$：
   • 若 $g(u)=0$ 或 $g(x)=0$，返回 $\bot$（仅偶数阶曲线）。
   • 若 $g(-u-x)$ 是平方数，返回 $\bot$。
   • 令 $s = -g(u)/(u^2 + ux + x^2 + a)$（不会除零）；令 $v = x$。
2. 否则（$c \in {2, 3}$）：
   • 令 $s = x-u$；令 $r = \sqrt{-s(4g(u) + sh(u))}$；若非平方数返回 $\bot$。
   • 若 $c = 3$ 且 $r = 0$，返回 $\bot$。
   • 令 $v = (r/s - u)/2$。
3. 令 $w = \sqrt{s}$；若非平方数返回 $\bot$。
4. 令 $w' = w$（若 $sign(w/2) = sign(y)$），否则 $w' = -w$。
5. 按 $c$ 返回：$c \in {0, 2} \to P_u^{'-1}(v, w')$；$c \in {1, 3} \to P_u^{'-1}(-u-v, w')$。

注意 $c$ 现在只取 $[0, 4)$，因为 $w'$ 的符号由 $y$ 的符号决定而非由 $c$ 决定。这一改变使部分合法编码不可达：当 $y = 0$ 且 $sign(Y) \neq sign(0)$ 时。

关于 $sign$ 的实现：$sign$ 可以有多种实现方式，例如域元素整数表示的奇偶性（对素数阶域），或二次剩余性（对 $-1$ 非平方的域）。只要它只取两个值、且对 $x \neq 0$ 满足 $sign(x) \neq sign(-x)$，具体选择不影响正确性。

4.1 secp256k1 的完整 $(x, y)$ 坐标编码

对 $a=0$ 曲线还有另一种做法。注意此时 $P_u(t)$ 会把 $t$ 的取负翻译成 $X$ 和 $Y$（两者）同时取负。因此可以直接用 $sign(t)$ 编码 y 坐标。结合前面保证所有输入都落在曲线上的重映射，得到解码器：

定义Decode(u, t)为：

1. $u'=u$（若 $u \neq 0$），否则 $u'=1$。
2. $t'=t$（若 $t \neq 0$），否则 $t'=1$。
3. $t''=t'$（若 $u'^3 + b + t'^2 \neq 0$），否则 $t''=2t'$。
4. $X = \dfrac{u'^3 + b - t''^2}{2t''}$。
5. $Y = \dfrac{X + t''}{u'\sqrt{-3}}$。
6. 令 $x$ 为 $(u' + 4Y^2,\ \frac{-X}{2Y} - \frac{u'}{2},\ \frac{X}{2Y} - \frac{u'}{2})$ 中第一个使 $g(x)$ 为平方数的值。
7. 令 $y = \sqrt{g(x)}$。
8. 若 $sign(y) = sign(t)$，返回 $(x, y)$；否则返回 $(x, -y)$。

该实现对应secp256k1_ellswift_swiftec_var（main_impl.h），使用的 $sign(x)$ 是 $x$ 表示为 $[0, q)$ 内整数时的奇偶性（parity）。

对应的编码器只需调用 x-only 编码器，然后在 $sign(t) \neq sign(y)$ 时对输出 $t$ 取负。该实现对应secp256k1_ellswift_elligatorswift_var（main_impl.h）。

重要使用限制：此方案仅适用于 x 坐标与 y 坐标都不可预测的点。当编码 x-only 点且 y 坐标被隐式规定（如隐式为偶数、隐式为平方数、或隐式落在 $[0, q/2]$）时，必须使用 3.5 节 的编码器，否则会重新引入偏差，抵消使用 ElligatorSwift 的全部收益。

5. 模块 API 与在 Zcash 仓库中的使用

5.1 公开 API 一览

ellswift模块的公开接口定义在 include/secp256k1_ellswift.h，核心函数如下：

头文件注释还给出了模块的逐字解码定义（全部运算模 $p = 2^{256} - 2^{32} - 977$）：

f(u,t): - 令 C = 0xa2d2ba93507f1df233770c2a797962cc61f6d15da14ecd47d8d27ae1cd5f852（√-3 的一个平方根） - 若 u=0，改为 u=1 - 若 t=0，改为 t=1 - 若 u³ + t² + 7 = 0，把 t 乘 2 - 令 X = (u³ + 7 - t²) / (2t) - 令 Y = (X + t) / (C·u) - 返回 [u + 4Y², (-X/Y - u)/2, (X/Y - u)/2] 中第一个是曲线上 X 坐标的值（对任意 u、t 至少有一个成立）

ElligatorSwift 对 $x$ 的编码就是 $u$、$t$ 两个 32 字节大端域元素拼接，满足 $f(u,t) = x$；若涉及 y 坐标，则约定其与 $t$ 同奇偶性。

5.2 在 Zcash 仓库中的构建配置与测试

• 构建开关：模块默认启用，可由 configure.ac 的--enable-module-ellswift选项控制；CI 脚本 ci.sh 会将该开关透传给 configure。
• 源码组成：实现位于 src/modules/ellswift/main_impl.h（核心算法），配套 tests_impl.h（单元测试）、tests_exhaustive_impl.h（小群穷举测试，正是 3.2 节提到"允许在小群上穷举测试"的落地）、bench_impl.h（基准测试）。模块头文件经 secp256k1.c 汇总导出，并通过 Makefile.am 的Makefile.am.include纳入构建。
• 测试覆盖：测试验证编码/解码往返（round-trip）、全空间可达性、y 符号编码、ECDH 与 BIP324 哈希函数兼容性等；穷举测试在小群上验证"每个 $t$ 恰好被到达一次"的完备性结论。

5.3 使用约束与安全建议（来自官方头文件）

• secp256k1_ellswift_encode的rnd32建议为 32 字节均匀随机数且不被任何试图检测编码的敌手知晓；16 字节随机性（填充到 32 字节）足以使结果不可区分于均匀。
• secp256k1_ellswift_create的auxrnd32可选但推荐提供；它比两步式（创建 + 编码）更安全，因为编码熵来自私钥本身。
• 编码结果不保证跨库版本稳定，即使参数完全相同。
• 对 x-only 点编码，若 y 坐标隐式固定（偶/平方/下半个区间），必须使用 x-only 编码器，否则将重新引入可检测偏差。

6. 总结

ElligatorSwift 为 secp256k1 提供了一种可证明均匀的 64 字节公钥编码：解码方向由代数函数 $F_u(t)$ 保证任意输入都映射到合法曲线点（配合 $u=0$、$t=0$、$g(u)=-t^2$ 三种情形的输入重映射，避免输出无穷远点）；编码方向通过 8 路公式 $G_{c,u}$ 均匀采样满足 $F_u(t)=x$ 的 $(u,t)$ 对，利用 $x_1+x_2=-u$ 的代数关系把 round-trip 校验简化为一次平方性检查，并依靠 $(x_3, x_2, x_1)$ 的优先顺序保证解码正确性。完整点编码把 y 坐标符号编入 $t$（secp256k1 特化版）或 $Y$（通用版），并配套提供直接作用于编码密钥的 ECDH（含 BIP324 兼容哈希）。在 Zcash 仓库中，该模块以默认启用的可配置模块形式存在，其数学文档 doc/ellswift.md、API 头文件 secp256k1_ellswift.h 与实现 main_impl.h 三者一一对应，读者可从任一入口深入验证本文所述的全部构造细节。

【免费下载链接】zcashZcash - Internet Money项目地址: https://gitcode.com/GitHub_Trending/zc/zcash