现在是上午255：19。你知道你的认证标准是什么吗？

数字签名方案的一个基本属性是，它应该指定哪些签名是有效的，哪些签名是无效的，这样所有实现都可以只接受有效签名，只拒绝无效签名。不幸的是，Ed25519签名不提供此属性，这使得它们在分布式系统中的使用脆弱且有风险。

虽然该方案是在RFC8032中标准化的，但RFC没有指定验证标准，也不需要符合标准的实现来就特定签名是否有效达成一致。此外，由于该规范在部署数年后更改了验证标准，因此它与几乎所有现有实现都不兼容。更糟糕的是，一些实现添加了额外的特别标准，使它们进一步不兼容。

结果是不同实现之间的验证标准差异极大。下图绘制了14乘以14的边缘情况网格的验证结果，亮方块表示接受的签名，深色方块表示拒绝的签名。如图所示，验证结果通常不仅在实现之间不一致，而且在不同版本和不同模式之间也不一致。

一些协议可能会容忍这种变化，但对于任何要求参与者就签名有效性达成共识的协议来说，这都是不可接受的。恶意参与者可以提交一些实现接受但另一些实现拒绝的签名，从而导致网络分区或共识分叉。只有一个实现会使这个问题变得不那么明显，但它不会消失，因为不同版本的“相同”实现的行为可能会有所不同。在实践中，广泛使用的libNa库发生了这种情况，它在一个点版本中对验证标准进行了突破性的更改。

最后，虽然在单独验证签名时会出现所有这些问题，但它们也会阻止批量验证的使用，这可以提供显著的性能优势。

ED25519签名的结构和验证标准中的潜在分歧范围(JUMP)；

不仅在不同的实现之间，而且在同一实现的不同版本之间，行为也有很大的差异；

Go的crypto/ed25519中的一个特定于平台的错误，它在IBMz/Architecture上给出了不同的验证结果；

Tor中由验证攻击者控制的签名触发的崩溃拒绝服务错误(尽管由于函数当前的使用方式，此错误碰巧不可利用)。

ZIP215规则(JUMP)，一套针对共识关键型Ed25519签名的精确定义的验证标准，可解决此问题。这些规则在Rust中的ed25519-Zebra和围棋中的ed25519 Consensus中实现，与现有签名向后兼容，并将作为Canopy网络升级的一部分部署在ZCash中。

在解释验证标准之前，简要回顾一下签名过程很有用。诚实的签名者通过一个与这里无关的复杂过程生成他们的签名密钥，一个随机标量\(a\)。然后，他们将签名密钥乘以Curve25519基点\(B\)以获得其验证密钥，即曲线点\(A=[a]B\)。签名和验证密钥通常称为私钥和公钥，但是(在Daira Hopwood之后)，我更喜欢使用基于功能的术语，因为它更准确地反映了密钥材料的作用。

为了签名消息M，签名者首先通过这里也不相关的过程生成秘密随机数\(r\)，然后通过计算\(R=[r]B\)来形成对该随机性的公开承诺。接下来，他们使用散列函数\(H\)计算挑战标量，因为\(k\得到H(R，A，M)\)。最后，他们将响应标量计算为\(s\get r+ka\)。

要了解验证标准中潜在差异的范围，让我们逐步完成使用消息M上的验证密钥\(A\)验证签名签名的步骤，并注意每个步骤都可能有不同的行为选择。然后，在接下来的几节中，我们将研究每个分歧的范围和影响。

Ed25519签名为64字节长，由两个32字节的组件构成：sig=R_bytes||s_bytes。前32个字节存储\(R\)编码，后32个字节存储\(s\)编码。ED25519验证密钥为32字节长，存储\(A\)编码。

接下来，验证器将s_bytes解析为\(s\)。始终可以将字节字符串解释为小端编码的整数，因此解析\(s\)不会失败。然而，假设\(s\)表示整数\(\mod q\)，其中\(q\)是曲线25519的素数阶子群的阶。诚实生成的签名将具有\(0\leq<；q\)，并且实现可以选择拒绝\(s\ge q\)。称这张支票为规范的\(s\)。

接下来，验证器尝试将A_Bytes解析为\(A\)。并非所有字节字符串都是有效的点编码，因此解析\(A\)可能会失败，从而导致签名被拒绝。点可以非规范地编码，尽管与\(s\)的编码相比，该机制稍微复杂和微妙一些，下面将对此进行描述。实现可以选择拒绝非规范编码的曲线点。称这张支票为规范的\(A\)。

然后，验证器使用A字节、R字节和消息M来重新计算挑战值\(k\得到H(R，A，M)\)。(请注意，由于\(H\)是散列函数，因此它实际上对编码A_bytes和R_bytes进行操作，而不是对其解码的内部表示进行操作)。

然后，实现选择验证方程式，选择两个验证方程式中的哪一个进行检查。他们可以使用批次方程\[[8]R=[8]([s]B-[k]A)，\]也可以使用非批次方程\[R=[s]B-[k]A\]。批次方程与非批次方程的命名表明，这种差异与批次验证和单独验证有关，但实际上，即使在单独验证的情况下，它们也会给出不同的行为，下面将对此进行解释。

最后，要实际检查使用了哪一个等式，实现必须选择相等检查。回想一下，我们还没有将R_bytes实际解码为\(R\)。当使用批处理方程时，实现必须在\(R\)上操作，因此它必须将R_bytes解码为\(R\)，并检查曲线点的等价性。这也意味着它必须选择是否需要规范\(R\)。

然而，当使用未批处理的等式时，实现可以选择检查曲线点的相等性，或者计算\(R‘\GETS[s]B-[k]A\)，将\(R’\)编码为RPrime_Bytes，并检查字节串的相等性。当对\(R\)进行规范编码时，这些相等检查会产生相同的结果。但是，由于编码过程产生规范编码，如果R_bytes包含\(R\)的非规范编码，则即使\(R‘=R\)(作为曲线点)，RPrime_Bytes也可能不同于R_Bytes(作为字节字符串)。

在比较RFC8032做出的选择和实际存在的实现之前，让我们先检查一下每个潜在分歧点的确切机制和含义。

值A_BYTES、R_BYTES和M都被送入哈希函数，因此如果不更改质询值，则无法修改它们。但是，第三方可以将\(s\)替换为\(s‘=s+nq\)。因为\(s‘\Equiv s\pmod Q\)，修改后的签名\((R，s’)\)仍将通过验证。要求s_bytes编码\(s<；q\)可以避免这种情况。

该检查简单、低成本、防止延展性，是RFC8032所要求的，并且大多数实现都会执行该检查。唯一值得注意的例外是Ed25519最初的参考实现，它选择写一段话，声称签名的延展性从来不是问题，而不是执行检查。

因为这项检查相当常见、广为人知并且不会引起异议，所以我没有关注它，也没有全面地测试实现行为。

虽然用于构造非规范编码标量值的机制相当简单，但是如上所述，用于构造非规范编码点值的机制稍微复杂一些。为了解释它，我们需要描述Ed25519使用的“压缩的Edwards\(y\)”编码。

曲线25519定义在有限域\(p=2^{255}-19\)上，因此曲线点的坐标\((x，y)\)是整数\(\mod p\)。(扭)Edwards形式的曲线方程为[-x^2+y^2=1+dx^2y^2]，其中d是曲线参数。这意味着\[x^2=\frac{y^2-1}{d y^2+1}。如果右侧的分数不是正方形，则没有x，因此右侧等于x^2，并且y的值不是曲线点的y坐标。如果它是平方根，则存在平方根\(x\)，并且\(y\)的值足以恢复\(x\)到所选的符号。

因为\(p<；2^{255}\)，字段元素的编码适合255位。压缩爱德华兹\(y\)格式使用前255位存储\(y\)坐标，第256位表示\(x\)坐标的符号。要解码此格式，实现将解析\(y\)和符号位，并尝试恢复\(x\)。如果存在平方根，则使用符号位来选择符号。否则，解码失败。

编码有两个组件，因此有两种构建非规范编码的潜在方法。首先，我们可以尝试使用\(y\)的非规范编码。其次，我们可以选择\(y\)，以便两个符号选项提供相同的\(x\)值。

在第一种情况下，对字段元素进行非规范编码需要将\(y\)编码为\(y+p\)。但是，因为字段元素是以255位和(p=2^{255}-19\)编码的，所以这仅对可以编码为\(y+p<；2^{255}\)的19个值(y=0\ldts 18\)是可能的。并不是所有这些值都是点的\(y\)坐标，但是因为候选值很少，所以我们可以检查enc(Y)||0和enc(Y)||1的每一个组合来枚举它们。

在第二种情况下，我们需要\(x=-x\)。这将强制\(x=0\)。曲线方程为[-x^2+y^2=1+dx^2 y^2]，这就要求y^2=1，给出了y=1和y=-1两个候选值。

当\(y=-1\)时，\(y\)只能进行规范编码，因此可能的编码为：

这提供了一种构建非规范编码点的机制，我在ed25519-zebra的测试套件中实现了该机制。总共有25个这样的点。其中有6个是小数量级的，对于构建签名边缘案例很有用，如下一节所述。(此分类是使用来自Sean Bowe和NCC Group的指针创建的)。

回想一下，实现可以使用两个验证方程式中的一个：分批方程式\([8]R=[8]([s]B-[k]A)\)或非分批方程式\(R=([s]B-[k]A)\)。这两个方程之间唯一的区别是第一个方程乘以\(8)。对于诚实生成的签名，\(s=r+ka\)，\(A=[a]B\)和\(R=[r]B\)，因此\[\Begin{aligned}[s]B-[k]A&；=[r+ka]B-[k]A\\&；=[r]B+[k]([a]B)-[k]A\\&；=R+[k]A-[k]A\\&；=R\end{alized}\]，并且两个方程都满足。那么，为什么会有两个验证方程式，它们与批量验证有什么关系呢？

要解释这一点，我们需要了解有关曲线25519组的结构的一些事实。许多抽象密码协议需要实现一组大素数阶\(q\)。这通常使用椭圆曲线(如Curve25519)提供，其中\(q\sim 2^{252}\)。然而，曲线25519和其他可以用爱德华兹形式写成的曲线没有素数阶。取而代之的是，它们为一个小的余因子\(h\)提供了一个阶数为\(hq\)的群，例如在曲线25519的情况下\(h=8)。有关辅因子的更多信息可以在Ristretto网站上找到。

这意味着除了素数阶子群之外，Curve25519还包含一个小阶点的“扭转”子群。全Curve25519群的结构是\(\mathbb Z/q\mathbb Z\Times\mathbb Z/8\mathbb Z\)，这意味着全群中的每个点\(P\)都可以唯一地写成素数阶子群中的一点(称为素数阶分量)和扭子群中的一点(称为扭转分量)之和\(Q+T\)。

当我们将\(P\)乘\(8\)时，素数阶分量将为\([8]Q\)。由于[8]和[q]是互素的，所以我们可以用[8]q乘以[1/8]q来恢复[q]，这样就“移位”了素数阶分量，但不会丢失任何结构。然而，由于扭子群中的每个点都有阶除\(8)，\([8]T=0\)，因此扭转分量被乘以\(8)映射杀死。

这对两个验证方程式意味着什么？因为乘8会杀死扭转分量，所以批处理方程可以认为是只在素数阶子群中检查有效性，而未批处理方程可以认为是在整个群中检查有效性。诚实的Ed25519签名者只在素数阶子群中工作，所以对于诚实生成的签名，两个验证公式给出了相同的结果。

但是没有什么能阻止签名者背离协议，生成具有非零扭矩分量的验证密钥。作为一个具体的例子，他们可以选择一个8阶的扭点\(T\)，并发布\(A‘=[a]B+T\)作为他们的验证密钥，而不是\(A=[a]B\)。如果他们照常签署消息，他们将选择一个随机的\(r\)，生成\(R\gets[r]B\)和\(s\获得r+ka\)。现在，考虑一下发生在\([s]B-[k]A‘\)上的情况：\[\BEGIN{ALIGNED}[s]B-[k]A’&；=[r+ka]B-[k](A+T)\\&；=[r]B+[k]A-[k]A-[k]T\\&；=R-[k]T\\&；=R-[k]T\END{ALIGNED}\]。

如果\([8]R=[8]([s]B-[k]A‘)\)，使用分批方程的验证者将接受签名。由于([s]B-[k]A‘=R-[k]T\)和([8]T=0)，[[8]([s]B-[k]A’)=[8]R-[8][k]T=[8]R\]总是满足分批方程。

然而，使用未批处理方程的验证器仅当\([k]T=0\)时才接受签名，这在\(8\)除以\(k\)时发生。由于\(k=H(R，A，M)\)是一个均匀分布的散列输出，签名者有\(1/8)次机会生成一个通过非批验证的签名。

我们现在已经看到了验证方程式之间的区别。要理解与批处理验证的联系，我们需要描述批处理验证是如何工作的。

批量校验是询问某个集合中的所有项目是否都有效，而不是询问每个项目是否都有效。这可以通过允许跨项目共享计算来增加吞吐量。在Ed25519的情况下，批处理验证的工作方式如下。首先，将验证公式重新排列为\[0=[8]R-[8][s]B+[8][k]A，这样我们就可以检查右侧的验证项是否为零。

在批处理设置中，我们有多个(消息、密钥、签名)对，我们想检查它们的验证条件是否都为零。为此，我们将验证项与系数\(z_i\)进行线性组合：\[0=\sum_i z_i\Left([8]R_i-[8][S_i]B+[8][ki]A_i\right)。\]当且仅当所有验证项都为零时，此等式才适用于\(z_i\)的所有值。直接进行检查在计算上是不可行的，但是验证者可以为\(z_i\)选择随机的高熵值。因为我们在素数阶(子)组中工作，所以如果任何验证项为非零，则它们在乘以\(z_i\)后将保持非零。

为什么这样更好呢？原因是它允许验证器计算多个点和标量的单个多标量乘法。这可以比计算多个单独的标量乘法并对结果求和更有效地执行。

在实践中，验证器使用略微改写的公式\[0=[8]\Left(\Left[-\textstyle\sum_Iz_Is_i\right]B+\sum_i[z_i]R_i+\sum_i[z_i_i]A\right)。\]这会将基点的系数合并到单个项中，从而减小多标量乘法的大小，并在结束时执行单个余因子乘法(三次倍增)。这可以很容易地提供2倍或更多的验证加速。还可以更进一步：ed25519-zebra实现了一种自适应策略，可以检测重复使用的验证密钥，在所有签名都使用相同的验证密钥的极限情况下，提供额外2倍的加速比。

然而，如果我们尝试在不乘以余因子的情况下这样做(就像在原始的Ed25519论文中那样)，那么当存在一个或多个具有非零扭转分量的候选签名时，我们会得到完全不一致的行为。

首先，验证结果将成为概率的，因为随机系数可能会杀死扭转分量，也可能不会杀死扭转分量。其次，如果一个术语的小订单组件与另一个术语的小订单组件取消，则验证结果可能取决于批次中包括或不包括哪些项目。第三，也是最令人惊讶的是，可以构建通过单次验证但未通过(无协因子)批验证的签名，即使是在单元素批处理中也是如此！

为什么最后一个案例令人惊讶呢？如果签名满足未批等式\(R=[s]B-[k]A\)，则验证项\(R-[s]B-[k]A\)为零。但是(无cofactorless)批处理验证计算的是这个项的随机线性组合，而这个项是零，那么这个组合怎么可能是非零的呢？

答案在于细微的实现细节。验证器实际检查的不是\[0=z\Left(R-[s]B+[k]A\right)\]，而是\[0=[-zs]B+[z]R+[Zk]A\]假设\(A\)具有\(8\)阶的扭转分量，并且\(8\)除以\(k\)。然后，在第一种情况下，验证器计算\([k]A\)，乘以\(k\)将杀死\(A\)的扭转分量。在第二种情况下，验证器计算\([ZK]A\)。由于\(8\)除以\(k\)，我们可以预期\(8\)除以\(zk\)。但是每个现有的实现都实现了标量算术\(\mod q\)，即素数阶群的阶数，而不是\(\mod 8q\)，即整个群的阶数。因此，验证器首先计算\(zk\mod q\)，然后使用得到的整数表示(可能不能被\(8\)整除)来执行标量乘法。

这个问题的根本原因是，Ed25519实现中的标量运算只在素数阶子群上产生明确定义的结果，而不是在整个群上产生明确定义的结果。这是不好的，因为它意味着基本的算术法则(例如，重新排列项不应该改变表达式的值)不适用，除非我们将其限制在素数阶子群上。

由于这些原因，使批处理验证产生内部一致结果的唯一方法是使用包含余因乘法的批处理验证公式。

ED25519在各种共识关键环境中广泛实施和使用。正如我们在上面看到的，原则上不同实现之间存在几个潜在的分歧点。这种情况在实践中会发生吗？为了找出答案，我收集了一个要查看的系统列表，并对照我为ZIP215创建的测试向量检查了它们的行为，下面描述了一组验证规则，它们在ZCash中修复了这个问题。

因为潜在的分歧发生在边缘情况下，而不是在诚实生成的签名上，如果我们想要检查分歧行为，我们需要构造专门制作的测试向量，当实现做出不同的选择时，这些测试向量将产生不同的行为。

我们怎么能。

.