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$a0, b7$ 曲线上的特化公式并结合模块源码 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 Function2.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 的倍数。若 $a0$该条件恒成立。对secp256k1$a0$$b7$。$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 坐标唯一的例外是 $z0$但此时三个值中仍有一个是合法 x 坐标。2.2 解码函数的定义定义解码函数 $F_u(t)$为计算 $(x_1, x_2, x_3, z) \psi_u(P_u(t))$。返回 $(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)$ 在以下情形未定义$a0$ 时$u0$ 或 $t0$除零$g(u) -t^2$会导致 $Y0$。$a \neq 0$ 时$X_0(u) 0$ 或 $h(u)t^2 -1$除零$Y_0(u)(1 - h(u)t^2) 2X_0(u)t$会导致 $Y0$。其中 $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 特化的解码$a0$将所有公式代入并针对 $a0$ 曲线化简解码 $(u, t)$ 到 x 坐标的流程为定义 $F_u(t)$为令 $X \dfrac{u^3 b - t^2}{2t}$。令 $Y \dfrac{X t}{u\sqrt{-3}}$。返回 $(u 4Y^2,\ \dfrac{-X}{2Y} - \dfrac{u}{2},\ \dfrac{X}{2Y} - \dfrac{u}{2})$ 中第一个使 $g(x)$ 为平方数的元素。输入重映射为保证每个输入都能解码到合法 x 坐标在 $P_u$ 未定义的情形$u0$、$t0$ 或 $g(u) -t^2$下需要对输入做重映射定义 $F_u(t)$为$uu$若 $u \neq 0$否则 $u1$保证 $u \neq 0$。$tt$若 $t \neq 0$否则 $t1$保证 $t \neq 0$。$tt$若 $g(u) \neq -t^2$否则 $t2t$保证 $t \neq 0$ 且 $g(u) \neq -t^2$。$X \dfrac{u^3 b - t^2}{2t}$。$Y \dfrac{X t}{u\sqrt{-3}}$。返回 $(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}$ 的一个平方根配合 $u0 \to 1$、$t0 \to 1$、$u^3 t^2 7 0 \to t$ 加倍三步重映射然后计算 $X (u^3 7 - t^2)/(2t)$、$Y (Xt)/(C \cdot u)$返回 $[u4Y^2,\ (-X/Y - u)/2,\ (X/Y - u)/2]$ 中第一个落在曲线上的值。3. 编码函数Encoding Function要实现 $F_u^{-1}(x)$找出所有满足 $F_u(t) x$ 的 $t$ 集合需要逆向整个流程找出所有可能通过 $\psi_u$ 中 $x_1$、$x_2$ 或 $x_3$ 公式产生 $x$ 的 $(X, Y) \in S_u$用 $P_u^{-1}(X, Y)$ 将这些 $(X, Y)$ 映射回 $t$ 值对每个 $t$ 验证 $F_u(t) x$返回验证通过的 $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)$ 集合。对 $a0$ 曲线$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_varmain_impl.h。3.3 求解逆元素 $G_{c,u}$$c$ 到公式的映射$c0$ 对应 $x_1$ 公式$c1$ 对应 $x_2$ 公式$c2,3$ 对应 $x_3$ 公式$c4$ 到 $c7$ 是上述公式的 $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$ 时会有 $swY0$不在 $S_u$ 上。这只在偶数阶曲线上可能出现。排除它同时消除了简化 $x_3$ 检查失效的唯一条件即 $g(x_1)g(x_2)0$ 但 $g(x_3)$ 非平方。这会排除一些合法编码当 $g(u)0$ 且 $u^2uxx^2a0$蕴含 $g(x)0$时$S_u$ 方程退化为 $00$可能存在大量合法 $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}$$s0$ 时发生除零。$c \in {3, 7}$ 且 $v -u-v$ 时会返回与 $c \in {2, 6}$ 情形相同的 $t$。这等价于检查 $r0$。它在 $x_1$、$x_2$ 分支中不会出现因为那会触发$g(-u-x)$ 是平方数条件。$w -w$ 的类似顾虑不存在$w0$ 在两个分支中都已不可能——第一个分支需要 $g(u)0$偶数阶曲线已排除其他曲线不可能第二个分支会触发除零。曲线相关的特殊情形也需拒绝因为它们会产生解码器不接受的 $(u,t)$或导致编码器除零对 $a0$ 曲线$u0$ 或 $t0$。后者只能由编码器在 $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)$若 $a0$ 且 $u0$返回 $\bot$。若 $a \neq 0$ 且 $X_0(u)0$返回 $\bot$。若 $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$。否则$c \in {2, 3, 6, 7}$令 $s x-u$。令 $r \sqrt{-s(4g(u) sh(u))}$若非平方数返回 $\bot$。若 $c \in {3, 7}$ 且 $r0$返回 $\bot$。若 $s 0$返回 $\bot$。令 $v (r/s - u)/2$。令 $w \sqrt{s}$若非平方数返回 $\bot$。若 $a \neq 0$ 且 $w(u2v) 2X_0(u)$ 且$w \neq 2Y_0(u)$ 或 $h(u)0$返回 $\bot$。按 $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)$。若 $a0$ 且 $t0$返回 $\bot$仅偶数阶曲线。若 $a \neq 0$ 且 $h(u)t^2 -1$返回 $\bot$。返回 $t$。完备性结论对任意 $u$对全部 $x$、$c$ 运行上述算法每个满足 $F_u(t) x$ 的 $t$ 值都会被恰好到达一次除以下不可达情形所有 $P_u(t)$ 未定义的情形$a0$ 曲线$u0$、$t0$ 或 $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 特化的编码$a0$ 奇数阶曲线针对奇数阶 $a0$ 曲线特化定义 $G_{c,u}(x)$为若 $u0$返回 $\bot$。若 $c \in {0, 1, 4, 5}$若 $(-u-x)^3 b$ 是平方数返回 $\bot$。令 $s -(u^3 b)/(u^2 ux x^2)$不会除零令 $v x$。否则$c \in {2, 3, 6, 7}$令 $s x-u$。令 $r \sqrt{-s(4(u^3 b) 3su^2)}$若非平方数返回 $\bot$。若 $c \in {3, 7}$ 且 $r0$返回 $\bot$。若 $s 0$返回 $\bot$。令 $v (r/s - u)/2$。令 $w \sqrt{s}$若非平方数返回 $\bot$。按 $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_varmain_impl.h。而 x-only 的 ElligatorSwift 编码算法仍为定义ElligatorSwift(x)为循环 1. 均匀随机选取域元素 u 2. 均匀随机选取整数 c ∈ [0, 8) 3. 计算 t G_{c,u}(x) 4. 若 t ≠ ⊥返回 (u, t)否则重启循环注意该逻辑不处理解码器中的 $u0$、$t0$、$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)$为计算 $(X, Y) P_u(t)$。令 $x$ 为 $(u 4Y^2,\ \frac{-X}{2Y} - \frac{u}{2},\ \frac{X}{2Y} - \frac{u}{2})$ 中第一个使 $g(x)$ 为平方数的值。令 $y \sqrt{g(x)}$。若 $sign(y) sign(Y)$返回 $(x, y)$否则返回 $(x, -y)$。编码使用 $G_{c,u}(x, y)$ 函数定义 $G_{c,u}(x, y)$为若 $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$。否则$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$。令 $w \sqrt{s}$若非平方数返回 $\bot$。令 $w w$若 $sign(w/2) sign(y)$否则 $w -w$。按 $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)$ 坐标编码对 $a0$ 曲线还有另一种做法。注意此时 $P_u(t)$ 会把 $t$ 的取负翻译成 $X$ 和 $Y$两者同时取负。因此可以直接用 $sign(t)$ 编码 y 坐标。结合前面保证所有输入都落在曲线上的重映射得到解码器定义Decode(u, t)为$uu$若 $u \neq 0$否则 $u1$。$tt$若 $t \neq 0$否则 $t1$。$tt$若 $u^3 b t^2 \neq 0$否则 $t2t$。$X \dfrac{u^3 b - t^2}{2t}$。$Y \dfrac{X t}{u\sqrt{-3}}$。令 $x$ 为 $(u 4Y^2,\ \frac{-X}{2Y} - \frac{u}{2},\ \frac{X}{2Y} - \frac{u}{2})$ 中第一个使 $g(x)$ 为平方数的值。令 $y \sqrt{g(x)}$。若 $sign(y) sign(t)$返回 $(x, y)$否则返回 $(x, -y)$。该实现对应secp256k1_ellswift_swiftec_varmain_impl.h使用的 $sign(x)$ 是 $x$ 表示为 $[0, q)$ 内整数时的奇偶性parity。对应的编码器只需调用 x-only 编码器然后在 $sign(t) \neq sign(y)$ 时对输出 $t$ 取负。该实现对应secp256k1_ellswift_elligatorswift_varmain_impl.h。重要使用限制此方案仅适用于 x 坐标与 y 坐标都不可预测的点。当编码 x-only 点且 y 坐标被隐式规定如隐式为偶数、隐式为平方数、或隐式落在 $[0, q/2]$时必须使用 3.5 节 的编码器否则会重新引入偏差抵消使用 ElligatorSwift 的全部收益。5. 模块 API 与在 Zcash 仓库中的使用5.1 公开 API 一览ellswift模块的公开接口定义在 include/secp256k1_ellswift.h核心函数如下函数作用备注secp256k1_ellswift_encode(ctx, ell64, pubkey, rnd32)将给定公钥编码为 64 字节 ElligatorSwift 格式恒返回 1rnd32需为 32 字节均匀随机数16 字节足够其余可补零且不得是公钥的确定性函数可以从私钥派生变时运行不保证跨版本稳定secp256k1_ellswift_decode(ctx, pubkey, ell64)将 64 字节编码解码回公钥恒返回 1变时运行secp256k1_ellswift_create(ctx, ell64, seckey32, auxrnd32)直接由私钥生成 ElligatorSwift 公钥私钥无效返回 0在seckey32与auxrnd32上常数时间auxrnd32可选即使缺省编码也不可区分于均匀比先secp256k1_ec_pubkey_create再encode更安全因为它用私钥本身作为编码熵源secp256k1_ellswift_xdh(ctx, output, ell_a64, ell_b64, seckey32, party, hashfp, data)基于编码密钥的 x-only ECDH比先解码再做 ECDH更高效在seckey32上常数时间party指示本方是 A0还是 B非 0secp256k1_ellswift_xdh_hash_function_prefix内置哈希函数SHA256(prefix64 \|\| ell_a64 \|\| ell_b64 \|\| x32)prefix64由data指向secp256k1_ellswift_xdh_hash_function_bip324与 BIP324 兼容的哈希函数H_tag(ell_a64 \|\| ell_b64 \|\| x32)标签为bip324_ellswift_xonly_ecdh的 BIP340 带标签哈希等价于prefix64 SHA256(tag)\|\|SHA256(tag)头文件注释还给出了模块的逐字解码定义全部运算模 $p 2^{256} - 2^{32} - 977$f(u,t): - 令 C 0xa2d2ba93507f1df233770c2a797962cc61f6d15da14ecd47d8d27ae1cd5f852√-3 的一个平方根 - 若 u0改为 u1 - 若 t0改为 t1 - 若 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)$ 保证任意输入都映射到合法曲线点配合 $u0$、$t0$、$g(u)-t^2$ 三种情形的输入重映射避免输出无穷远点编码方向通过 8 路公式 $G_{c,u}$ 均匀采样满足 $F_u(t)x$ 的 $(u,t)$ 对利用 $x_1x_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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考