bip-anyprevout 项目中的 bips/bip-0340.mediawiki 文件

  • ajtowns
  • 发布于 2025-02-27 22:23
  • 阅读 25

该文档提出了一个基于椭圆曲线 secp256k1 的 64 字节 Schnorr 签名标准，详细阐述了 Schnorr 签名的设计、规范、公钥生成、签名、验证以及批量验证过程，并探讨了其在多重签名、适配器签名和盲签名等方面的应用，旨在替代比特币当前使用的 ECDSA 签名方案，提升安全性和效率, 并且提供了测试向量和参考代码。

跳转到内容

ajtowns/ bips 公开

forked from bitcoin/bips

折叠文件树

文件

bip-anyprevout

搜索此仓库

/

bip-0340.mediawiki

复制路径

Blame更多文件操作

Blame更多文件操作

最近提交

jonasnickjonasnick

BIP340: 移除批量加速图并链接到它

打开提交详情

2021年5月17日

255b5b6 · 2021年5月17日

历史

历史

打开提交详情

查看此文件的提交历史。

251 行 (180 loc) · 34.5 KB

/

bip-0340.mediawiki

顶部

文件元数据和控制

  • 预览

  • 代码

  • Blame

251 行 (180 loc) · 34.5 KB

Raw

复制原始文件

下载原始文件

目录

编辑和原始操作

  BIP: 340
  Title: secp256k1 的 Schnorr 签名
  Author: Pieter Wuille <pieter.wuille@gmail.com>
          Jonas Nick <jonasd.nick@gmail.com>
          Tim Ruffing <crypto@timruffing.de>
  Comments-Summary: 暂无评论。
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0340
  Status: 草案
  Type: 标准跟踪
  License: BSD-2-Clause
  Created: 2020-01-19
  Post-History: 2018-07-06: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html [bitcoin-dev] Schnorr signatures BIP
## 目录<br>固定链接：目录<br>- 简介 <br> - 摘要<br> - 版权<br> - 动机<br>- 描述 <br> - 设计<br> - 规范 <br> - 公钥生成<br> - 公钥转换<br> - 默认签名<br> - 备选签名<br> - 验证<br> - 批量验证<br>- 应用 <br> - 多重签名和阈值签名<br> - 适配器签名<br> - 盲签名<br>- 测试向量和参考代码<br>- 脚注<br>- 致谢

简介

固定链接：简介

摘要

固定链接：摘要

本文档提出了一个标准，用于在椭圆曲线 secp256k1 上的 64 字节 Schnorr 签名。

版权

固定链接：版权

本文档基于 2-clause BSD 许可。

动机

固定链接：动机

传统上，比特币使用 ECDSA 签名，基于 secp256k1 曲线 并使用 SHA256 哈希来验证交易。这些是 标准化的，但与在同一曲线上使用 Schnorr 签名 相比，存在许多缺点：

对于所有这些优点，实际上没有任何缺点，除了未标准化。本文档旨在改变这一点。当我们提出新的标准时，可以进行许多不特定于 Schnorr 签名的改进：

  • 签名编码：我们可以使用简单的固定 64 字节格式，而不是对签名使用 DER 编码（它是可变大小的，最大为 72 字节）。
  • 公钥编码：在本提案中，公钥编码为 32 字节，而不是当今比特币中常见的椭圆曲线点的 压缩 33 字节编码。
  • 批量验证：与单独验证相比，标准化的 ECDSA 签名的特定公式无法更有效地进行批量验证，除非添加额外的见证数据。更改签名方案提供了一个解决此问题的机会。
  • 完全指定：为了在共识系统中安全使用，验证算法必须在字节级别完全指定。这保证了没有人可以构造对某些验证者有效但对所有验证者无效的签名。传统上，这不是对数字签名方案的要求，并且由于缺乏对 ECDSA 签名 DER 解析的精确规范，这在过去给比特币带来了问题 过去，需要 BIP66 解决它。在本文档中，我们的目标是在设计上满足此属性。对于批量验证，由于验证者可以选择其批次，因此批量验证本质上是不确定的，此属性意味着验证结果与单独验证的差异可能仅具有可忽略的概率，即使对于故意尝试使批量验证和非批量验证不同的攻击者。

通过重用比特币用于 ECDSA 的相同曲线和哈希函数，我们能够保留用于选择密钥和公钥的现有机制，并且避免引入关于椭圆曲线和哈希函数安全性的新假设。

描述

固定链接：描述

我们首先通过研究设计选择来构建签名方案的代数公式。之后，我们指定确切的编码和操作。

设计

固定链接：设计

Schnorr 签名变体 消息 m 和公钥 P 的椭圆曲线 Schnorr 签名通常涉及点 R、由签名者选择的整数 e 和 s，以及满足 e = hash(R || m) 和 s⋅G = R + e⋅P 的基点 G。存在两种公式，具体取决于签名者是显示 e 还是 R：

  1. 签名是满足 e = hash(s⋅G - e⋅P || m) 的对 (e, s)。此变体避免了签名中点 R 编码引入的次要复杂性（请参阅本节中“编码 R 和公钥点 P”和“隐式 Y 坐标”段落）。此外，显示 e 而不是 R 可以使签名更短：虽然 R 的编码本质上需要大约 32 个字节，但哈希 e 可以调整为短于 32 个字节，并且 只有 16 个字节的短哈希足以在 128 位的目标安全级别上提供 SUF-CMA 安全性。但是，这种优化的一个主要缺点是，在短哈希函数中找到碰撞很容易。这使得在相互不信任的签名者小组协同工作以生成单个联合签名的场景中，安全签名协议的实施变得复杂（请参阅下面的“应用”）。在这些场景中，由于其假设的单个诚实签名者，SUF-CMA 模型未捕获到这些场景，恶意共同签名者的一种有希望的攻击策略是在哈希函数中找到冲突，以便在诚实共同签名者不打算签名的消息上获得有效的签名。
  2. 签名是满足 s⋅G = R + hash(R || m)⋅P 的对 (R, s)。这支持批量验证，因为哈希中没有椭圆曲线运算。批量验证可以显着加速。[ 4]

由于我们希望避免短哈希带来的脆弱性，因此 e 变体不提供明显的优势。我们选择支持批量验证的 R 选项。

密钥前缀 直接使用上面的验证规则会使 Schnorr 签名容易受到“相关密钥攻击”，在这种攻击中，第三方可以将公钥 P 的签名 (R, s) 转换为公钥 P + a⋅G 的签名 (R, s + a⋅hash(R || m)) 和相同的消息 m，对于签名密钥的任何给定加法调整 a。当使用 BIP32 的未硬化派生 和其他依赖于对现有密钥进行加法调整的方法（例如 Taproot）生成密钥时，这将使签名不安全。

为了防止这些攻击，我们选择密钥前缀[ 5] Schnorr 签名，这意味着公钥在前缀哈希输入中的消息。这将等式更改为 s⋅G = R + hash(R || P || m)⋅P。 可以证明 密钥前缀可以防止使用加法调整的相关密钥攻击。通常，密钥前缀增加了多用户设置的健壮性，例如，它似乎是证明 MuSig 多重签名方案安全的要求（请参阅下面的“应用”）。

我们注意到，密钥前缀对于目前在比特币中使用的交易签名并非绝对必要，因为已签名交易间接提交给公钥，即 m 包含对 pk 的承诺。但是，不应依赖此间接承诺，因为它可能会因 SIGHASH_NOINPUT 等提案而发生变化（BIP118），并且会使签名方案不适用于签名交易以外的目的，例如 签名普通消息。

编码 R 和公钥点 P 存在几种编码椭圆曲线点的可能性：

  1. 编码 P 和 R 的完整 X 和 Y 坐标，从而生成 64 字节的公钥和 96 字节的签名。
  2. 编码完整的 X 坐标和 Y 坐标的一位，以确定两个可能的 Y 坐标之一。这将导致 33 字节的公钥和 65 字节的签名。
  3. 仅编码 X 坐标，从而生成 32 字节的公钥和 64 字节的签名。

对于验证来说，使用第一个选项效率会稍高一些（大约 10%），但我们优先考虑紧凑性，因此选择选项 3。

隐式 Y 坐标 为了支持有效的验证和批量验证，P 和 R 的 Y 坐标不能是模棱两可的（每个有效的 X 坐标都有两个可能的 Y 坐标）。我们可以选择几种对称性破坏的选项：

  1. 隐式选择下半部分的 Y 坐标。
  2. 隐式选择偶数的 Y 坐标[ 6]。
  3. 隐式选择是二次剩余的 Y 坐标（即，具有平方根模 p）。

第二个选项与现有的密钥生成系统具有最大的兼容性，在现有密钥生成系统中，标准的 33 字节压缩公钥格式由指示 Y 坐标奇偶性的字节加上完整的 X 坐标组成。为了避免不必要的不兼容，我们为 P 选择该选项，因此我们的仅 X 公钥等效于以字节 0x02 为前缀的仅 X 密钥的压缩公钥。为了保持一致性，对 R 也这样做[ 7]。

尽管将有效公钥集的大小减半，但隐式 Y 坐标并不会降低安全性。非正式地，如果存在一种快速算法来计算机仅 X 公钥的离散对数，则它也可以用于计算完整公钥的离散对数：将其应用于 X 坐标，然后有选择地对结果取反。这表明，破解仅 X 公钥最多比破解完整公钥快一个小常数项。[ 8]。

标记哈希 密码哈希函数通常用于以下规范和比特币中用于多种目的。为了确保在一个上下文中使用的哈希不能在另一个上下文中被重新解释，可以使用依赖于上下文的标记名称来调整哈希函数，从而可以假设跨上下文的冲突是不可行的。显然，不能完全排除此类冲突，而只能排除使用带有唯一名称的标记的方案。至于其他方案，使用标记的冲突至少不如没有标记的冲突的可能性小。

例如，如果没有标记的哈希，BIP340 签名对于签名方案也可能有效，其中唯一的区别是哈希函数的参数被重新排序。更糟糕的是，如果 BIP340 随机数派生函数被复制或独立创建，则随机数可能会在另一个方案中被意外重用，从而泄露密钥。

该提案建议通过将哈希数据加前缀 SHA256(tag) || SHA256(tag) 来包含标签。因为这是一个 64 字节长的特定于上下文的常量，并且 SHA256 块大小也是 64 字节，所以可以进行优化实现（与 SHA256 本身相同，但初始状态已修改）。对于不选择使用优化的实现，使用标记名称本身的 SHA256 是相当简单和高效的。

最终方案 因此，我们的最终方案最终使用公钥 pk，它是曲线上一个点 P 的 X 坐标，该曲线的 Y 坐标是偶数，签名是 (r,s)，其中 r 是一个点 R 的 X 坐标，该点的 Y 坐标是偶数。签名满足 s⋅G = R + tagged_hash(r || pk || m)⋅P。

规范

固定链接：规范

使用以下约定，常量定义为 secp256k1。我们注意到，将此规范调整为其他椭圆曲线并非易事，并且可能导致不安全的方案[ 9]。

  • 小写变量表示整数或字节数组。
    • 常数 p 指的是字段大小，0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F。
    • 常数 n 指的是曲线阶数，0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141。
  • 大写变量指的是曲线上的点，该曲线的方程是关于整数模 p 的 y2 = x3 + 7。
    • is_infinite(P) 返回 P 是否是无穷远的点。
    • x(P) 和 y(P) 是范围为 0..p-1 的整数，指的是点 P 的 X 和 Y 坐标（假设它不是无穷大）。
    • 常数 G 指的是基点，其中 x(G) = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 和 y(G) = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8。
    • 点的加法指的是通常的 椭圆曲线群运算。
    • 整数和点的乘法 (⋅) 指的是群运算的重复应用。
  • 函数和运算：
    • || 指的是字节数组连接。
    • 函数 x[i:j]，其中 x 是字节数组，i, j ≥ 0，返回一个 (j - i) 字节数组，其中包含 x 的第 i 个字节（包括）到第 j 个字节（不包括）的副本。
    • 函数 bytes(x)，其中 x 是一个整数，返回 x 的 32 字节编码，最高有效字节优先。
    • 函数 bytes(P)，其中 P 是一个点，返回 bytes(x(P))。
    • 函数 int(x)，其中 x 是一个 32 字节数组，返回 256 位无符号整数，其最高有效字节优先编码是 x。
    • 函数 has_even_y(P)，其中 P 是一个点，其中 not is_infinite(P)，返回 y(P) mod 2 = 0。
    • 函数 lift_x(x)，其中 x 是范围 0..p-1 中的整数，返回点 P，其中 x(P) = x[ 10] 且 has_even_y(P)，如果不存在这样的点，则失败。函数 lift_x(x) 等效于以下伪代码：
    • 令 c = x3 + 7 mod p。
    • 令 y = c(p+1)/4 mod p。
    • 如果 c ≠ y2 mod p，则失败。
    • 返回唯一的点 P，使得 x(P) = x，如果 y mod 2 = 0 则 y(P) = y，否则 y(P) = p-y。
    • 函数 hashtag(x)，其中 tag 是 UTF-8 编码的标记名称，x 是字节数组，返回 the 32-byte hash SHA256(SHA256(tag) || SHA256(tag) || x)。
公钥生成

固定链接：公钥生成

输入：

  • 密钥 sk：一个 32 字节的数组，全新生成，均匀随机

算法 PubKey(sk) 定义为：

  • 令 d' = int(sk)。
  • 如果 d' = 0 或 d' ≥ n，则失败。
  • 返回 bytes(d'⋅G)。

请注意，我们使用的公钥格式（32 字节）与现有系统使用的格式（通常使用椭圆曲线点作为公钥，或它们的 33 字节或 65 字节编码）非常不同。副作用是 PubKey(sk) = PubKey(bytes(n - int(sk))，因此每个公钥都有两个对应的密钥。

公钥转换

固定链接：公钥转换

作为随机生成密钥的替代方法，以兼容的方式重新利用现有的 ECDSA 密钥生成算法也是可能的并且安全的。由此类算法构建的密钥可以直接用作 sk。由此类算法构建的公钥（假设它们使用 33 字节的压缩编码）需要通过删除第一个字节来转换。具体而言，BIP32 和构建在其上的方案仍然可用。

默认签名

固定链接：默认签名

输入：

  • 密钥 sk：一个 32 字节的数组
  • 消息 m：一个 32 字节的数组
  • 辅助随机数据 a：一个 32 字节的数组

算法 Sign(sk, m) 定义为：

  • 令 d' = int(sk)
  • 如果 d' = 0 或 d' ≥ n，则失败
  • 令 P = d'⋅G
  • 如果 has_even_y(P) 是真，令 d = d'，否则令 d = n - d'。
  • 令 t 为 bytes(d) 和 hashBIP0340/aux(a)[ 11] 的字节异或。
  • 令 rand = hashBIP0340/nonce(t || bytes(P) || m)[ 12]。
  • 令 k' = int(rand) mod n[ 13]。
  • 如果 k' = 0，则失败。
  • 令 R = k'⋅G。
  • 如果 has_even_y(R) 是真，令 k = k'，否则令 k = n - k'。
  • 令 e = int(hashBIP0340/challenge(bytes(R) || bytes(P) || m)) mod n。
  • 令 sig = bytes(R) || bytes((k + ed) mod n)。
  • 如果 Verify(bytes(P), m, sig)（见下文）返回失败，则中止[ 14]。
  • 返回签名 sig。

辅助随机数据应设置为在签名时生成的新鲜随机性，从而产生所谓的合成随机数。使用 32 字节的随机性是最佳的。如果获取随机性的成本很高，则可以用 16 个空字节填充 16 个随机字节以获得 32 字节的数组。如果在签名时根本没有随机性，则可以使用一个简单的计数器，该计数器足够宽，在实践中不会重复（例如，64 位或更宽），并用空字节填充到 32 字节的数组，或者甚至可以使用带有 32 个空字节的常量数组。使用任何非重复值都会增加对 故障注入攻击 的防护。使用不可预测的随机性还会增加对其他侧信道攻击的防护，并且建议在可用时使用。请注意，虽然这意味着生成的随机数不是确定性的，但随机性仅是对安全性的补充。正常的安全属性（不包括侧信道攻击）不依赖于签名时 RNG 的质量。

备选签名

固定链接：备选签名

应该注意的是，各种备选签名算法可用于生成同样有效的签名。可以以其他方式生成 32 字节的 rand 值，从而产生不同的但仍然有效的签名（换句话说，这不是_唯一的_签名方案）。无论使用哪种方法生成 rand 值，该值都必须是一个新鲜的均匀随机的 32 字节字符串，即使对于攻击者而言，它也不是部分可预测的。 对于没有随机性的随机数，这意味着不得在另一个上下文中显示相同的输入。这可以通过不在不同的签名方案中重用相同的密钥来最可靠地完成。例如，如果 rand 值是按照 RFC6979 计算的，并且相同的密钥在确定性 ECDSA 中与 RFC6979 一起使用，则签名可能会通过随机数重用来泄露密钥。

随机数泄露防护 可以使用第二个设备来加强随机数生成算法。在这种情况下，第二个设备会贡献随机性，实际签名者可以证明该随机性已融入到其随机数中。这可以防止某些攻击，在这种攻击中，签名者设备受到入侵并故意尝试通过其随机数选择来泄露密钥。

多重签名 此签名方案与各种类型的多重签名和阈值方案兼容，例如 MuSig，其中单个公钥需要多个密钥的持有者参与签名（请参阅下面的“应用”）。\ 重要的是要注意，一般来说，多重签名方案对于上述默认签名算法的 rand 生成（或任何其他确定性方法）是不安全的。

预计算的公钥数据 对于许多用途，可能已经知道与密钥对应的公钥的压缩 33 字节编码，从而可以轻松地评估 has_even_y(P) 和 bytes(P)。因此，让签名者直接提供这些数据可能比从密钥重新计算- 公钥 pk: 一个 32 字节的数组

  • 消息 m: 一个 32 字节的数组
  • 签名 sig: 一个 64 字节的数组

算法 Verify(pk, m, sig) 定义如下：

  • 令 P = lift_x(int(pk)); 如果失败则终止。
  • 令 r = int(sig[0:32]); 如果 r ≥ p 则终止。
  • 令 s = int(sig[32:64]); 如果 s ≥ n 则终止。
  • 令 e = int(hashBIP0340/challenge(bytes(r) || bytes(P) || m)) mod n。
  • 令 R = s⋅G - e⋅P。
  • 如果 is_infinite(R) 则终止。
  • 如果 not has_even_y(R) 则终止。
  • 如果 x(R) ≠ r 则终止。
  • 当且仅当在到达此点之前没有发生任何失败时，返回成功。

对于每个有效的私钥 sk 和消息 m，Verify(PubKey(sk),m,Sign(sk,m)) 将会成功。

请注意，验证的正确性依赖于 lift_x 总是返回一个具有偶数 Y 坐标的点的这个事实。一个假想的验证算法将点作为公钥对待，并直接将点 P 作为输入，那么在使用具有奇数 Y 的点时将会失败。虽然可以通过在进一步处理之前对具有奇数 Y 坐标的点进行取反来纠正此问题，但这将导致每个 (消息，签名) 对对于两个公钥都有效 (一种也存在于 ECDSA 中的可延展性，但我们不希望保留)。我们通过仅将 X 坐标作为公钥来避免这些问题。

批量验证

Permalink: 批量验证

输入：

  • 签名数量 u
  • 公钥 pk1..u: u 个 32 字节的数组
  • 消息 m1..u: u 个 32 字节的数组
  • 签名 sig1..u: u 个 64 字节的数组

算法 BatchVerify(pk1..u, m1..u, sig1..u) 定义如下：

  • 生成范围 1...n-1 内的 u-1 个随机整数 a2...u。它们是使用一个 CSPRNG 确定性地生成的，该 CSPRNG 由算法所有输入的密码学哈希作为种子，即 seed = seed_hash(pk1..pku || m1..mu || sig1..sigu )。一个安全的选择是用 SHA256 实例化 seed_hash， 并使用密钥为 seed 的 ChaCha20 作为 CSPRNG 生成 256 比特的整数，跳过范围 1...n-1 之外的整数。
  • 对于 i = 1 .. u:
    • 令 Pi = lift_x(int(pki)); 如果失败则终止。
    • 令 ri = int(sigi[0:32]); 如果 ri ≥ p 则终止。
    • 令 si = int(sigi[32:64]); 如果 si ≥ n 则终止。
    • 令 ei = int(hashBIP0340/challenge(bytes(ri) || bytes(Pi) || mi)) mod n。
    • 令 Ri = lift_x(ri); 如果 lift_x(ri) 失败则终止。
  • 如果 (s1 + a2s2 + ... + ausu)⋅G ≠ R1 + a2⋅R2 + ... + au⋅Ru + e1⋅P1 + (a2e2)⋅P2 + ... + (aueu)⋅Pu 则终止。
  • 当且仅当在到达此点之前没有发生任何失败时，返回成功。

如果所有单个签名都有效 (即，对于它们，Verify 将返回成功)，则 BatchVerify 将始终返回成功。如果至少一个签名无效，则 BatchVerify 将以至多可忽略的概率返回成功。

应用

Permalink: 应用

除了简单的签名之外，还有几个有趣的应用。 虽然最近的学术论文声称它们也可以通过 ECDSA 实现，但对 Schnorr 签名验证的共识支持将大大简化构建。

多重签名和阈值签名

Permalink: 多重签名和阈值签名

通过诸如 MuSig 之类的交互式方案，参与者可以将其公钥聚合为单个公钥，他们可以共同签名。这允许 n-of-n 多重签名，从验证者的角度来看，这与普通签名没有什么不同，与 CHECKMULTISIG 或其他方式相比，提高了隐私和效率。

此外，Schnorr 签名与 分布式密钥生成 兼容，这使得交互式阈值签名方案成为可能，例如，Stinson 和 Strobl (2001) 或 Gennaro, Jarecki 和 Krawczyk (2003) 描述的方案。这些协议可以实现 k-of-n 阈值签名，从而确保 n 个签名者的集合中的任何大小为 k 的子集都可以签名，但小于 k 的子集无法生成有效的 Schnorr 签名。但是，现有方案的实用性受到限制：文献中的大多数方案仅在 k-1 < n/2 的情况下才被证明是安全的，在多个会话中同时使用时不安全，或者需要可靠的广播机制才能安全。需要进一步的研究来改善这种情况。

适配器签名

Permalink: 适配器签名

适配器签名 可以由签名者通过用一个已知的点 T = t⋅G 偏移他的公钥nonce R 来生成，但不偏移签名的 s 值。 具有相同 nonce 的相同消息上的正确签名 (或部分签名，因为多重签名中的单个签名者的贡献被称为部分签名) 然后将等于由 t 偏移的适配器签名，这意味着学习 t 等同于学习正确的签名。 这可以用于启用原子交换，甚至 通用支付通道，其中不相交交易的原子性通过签名本身而不是比特币脚本支持来保证。 所得交易对于验证者而言与普通的单签名者交易没有什么不同，除了可能包含锁定时间退款逻辑。

适配器签名，除了将脚本语义编码为恒定大小的签名所带来的效率和隐私优势外，还比传统的基于哈希的支付渠道具有其他优势。 具体来说，秘密值 t 可以在 hops 之间重新盲化，从而允许构建很长的原子交易链，即使参与者也无法识别哪些交易是链的一部分。 此外，由于秘密值是在签名时而不是在密钥生成时选择的，因此现有输出可以重新用于不同的应用程序，而无需诉诸区块链，甚至可以多次使用。

盲签名

Permalink: 盲签名

盲签名协议是一种交互式协议，使签名者能够在不了解有关签名消息或签名的任何信息的情况下，应另一方的要求对消息进行签名。 Schnorr 签名允许一个非常 简单的盲签名方案，但是该方案是不安全的，因为它容易受到 Wagner's attack 的攻击。 一種已知的緩解措施是让签名者以一定的概率中止签名会话，并且可以在 非标准密码学假设下证明所得到的方案是安全的。

盲 Schnorr 签名例如可以用于 部分盲原子交换，这是一种在不受信任的托管代理的调解下实现转移 coins 的结构，而无需在公共区块链交易图中连接交易者。

测试向量和參考代码

Permalink: 测试向量和參考代码

为了开发和测试的目的，我们提供了一个 CSV 格式的测试向量集合 以及一个幼稚的、效率极低的、非恒定时间的 签名和验证算法的纯 Python 3.7 参考实现。 该參考实现仅用于演示目的，不能在生产环境中使用。

脚注

Permalink: 脚注

  1. ^ 非正式地讲，这意味着在不知道密钥的情况下，但在给定任意消息的有效签名的情况下，不可能提出进一步的有效签名。
  2. ^ 在随机 oracle 模型中一个详细的安全证明，它本质上更明确地重申了 Pointcheval 和 Stern 的原始安全证明，可以在 Kiltz、Masny 和 Pan 的一篇论文 中找到。所有这些安全性证明都假设 Schnorr 签名的一种变体，该变体使用 (e,s) 而不是 (R,s) (请参见上面的设计)。由于我们使用了 R 的唯一编码，因此存在一个可有效计算的双射，该双射将 (R,s) 映射到 (e,s)，从而可以将 (e,s) 变体的成功的 SUF-CMA 攻击者转换为 (R,s) 变体的成功的 SUF-CMA 攻击者 (反之亦然)。此外，这些证明考虑了没有密钥前缀的 Schnorr 签名的一种变体 (请参见上面的设计)，但是可以验证这些证明对于具有密钥前缀的变体也是正确的。因此，所有上述安全性证明均适用于本文档中提出的 Schnorr 签名变体。
  3. ^ 如果对于给定的消息和密钥，(r,s) 是有效的 ECDSA 签名，则 (r,n-s) 对于同一消息和密钥也有效。如果 ECDSA 仅限于仅允许两种变体之一 (如比特币通过网络上的策略规则所做的那样)，则可以在比通常更强的假设下 证明 它不是可延展的。
  4. ^ 批量验证带来的加速可以使用密码学库 libsecp256k1 来证明。
  5. ^ 提交到公钥 (而不是其短哈希，或者根本不提交) 的一个限制是，它消除了公钥恢复或根据短公钥哈希验证签名的能力。这些构造通常与批量验证不兼容。
  6. ^ 由于 p 是奇数，因此对 p 取模的取反会将偶数映射为奇数，反之亦然。这意味着对于有效的 X 坐标，相应的 Y 坐标之一将为偶数，另一个将为奇数。
  7. ^ 本草案的早期版本使用了第三个选项，这是因为人们认为这通常会以签署效率换取验证效率。 当使用 Jacobian 坐标 (ECC 实现中的一种常见优化) 时，可以通过计算 Legendre 符号来确定 Y 坐标是否为二次剩余，而无需先转换为仿射坐标 (这需要模逆)。 由于在实践中模逆和 Legendre 符号具有相似的 性能，因此不值得进行这种权衡。
  8. ^ 这可以通过一个简单的归约来形式化，该归约将对具有隐式 Y 坐标的 Schnorr 签名的攻击简化为对具有显式 Y 坐标的 Schnorr 签名的攻击。 该归约的工作方式是：每当质询公钥具有奇数的显式 Y 坐标时，对公钥进行重新编码并对哈希函数的结果 (建模为随机 oracle) 取反。可以在 此处 找到证明草图。
  9. ^ 除其他缺陷外，将该规范与曲线的阶数与 nonce 派生函数的范围大小不接近的曲线一起使用是不安全的。
  10. ^ 给定范围 0..p-1 中的候选 X 坐标 x，则存在恰好两个或恰好零个有效的 Y 坐标。 如果不存在有效的 Y 坐标，则 x 也不是有效的 X 坐标，即不存在满足 x(P) = x 的点 P。 给定候选 x 的有效 Y 坐标为 c = x3 + 7 mod p 的平方根，如果存在，则可以将其计算为 y = ±c(p+1)/4 mod p (请参见 二次剩余)，这可以通过求平方并与 c 进行比较来检查。
  11. ^ 辅助随机数据被哈希 (带有一个唯一的标签)，以防止随机性可能与私钥本身相关联的情况。它与私钥进行异或运算 (而不是在哈希中与其组合)，以减少暴露给实际密钥的操作数。
  12. ^ 将公钥作为 nonce 哈希的输入 有助于确保签名算法的健壮性，如果在不正确或恶意地执行公钥 P 的计算 (例如，如果出于性能原因将其留给调用者) 的情况下，可以防止泄漏私钥。
  13. ^ 注意，通常，取均匀随机的 256 比特整数以曲线阶数取模将产生不可接受的有偏差的结果。 但是，对于 secp256k1 曲线，该阶数足够接近 2256，以至于无法观察到此偏差 ( 1 - n / 2256 大约为 *1.27 2-128**)。
  14. ^ 在离开签名者之前验证签名可以防止随机或攻击者挑起的计算错误。 这样可以防止发布可能泄漏有关私钥信息的无效签名。 建议这样做，但是如果计算成本过高，则可以省略。

致谢

Permalink: 致谢

本文档是多年来围绕基于 Schnorr 的签名进行的许多讨论的结果，并获得了 Johnson Lau、Greg Maxwell、Andrew Poelstra、Rusty Russell 和 Anthony Towns 的投入。 作者还要感谢所有提供宝贵反馈和评论的人，包括 结构化评论 的参与者。

  • 原文链接： github.com/ajtowns/bips/...
  • 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～
点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
ajtowns
ajtowns
江湖只有他的大名，没有他的介绍。

ajtowns

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！