作者：Blockstream

来源：https://blog.blockstream.com/lattice-signatures-for-bitcoin/

Blockstream Research 已经发布了为比特币评估基于格的数字签名的完整报告。本文总结了我们的测试内容、发现以及建议。报告本身可在 ePrint 获得。

数字签名是比特币协议中授权交易的核心机制，目前，Schnorr 签名和 ECDSA 签名服役于此事，并且它们是非常轻量的。Shor 在 1994 年证明，规模足够大的量子计算机可以攻破这两种签名。这样的机器何时问世，依然是一个热议的话题，但我们必须在答案浮出水面之前，为加入后量子签名制订一个可靠的部署计划。

基于格的数字签名方案（Lattice-based signature schemes）是取代现有方案的有力候选。
“格” 这种结构已经被研究了超过一个世纪，它的密码学应用也已问世接近三十年；并且，在所有后量子签名类型中，格签名的单签名与公钥体积之和小于 1.6 kB，显得很有前景，再加上它的代数结构，也许最终能支持多重签名、门限签名和简洁证据（succinct proofs）。

我们的报告研究了三种方案：Dilithium、Falcon，以及 Hawk。对每一种方案，我们演示了其设计背后的直觉，并给了出对其算法的完整描述，并分析了其安全性、性能，以及有关应用的细节，比如钱包的密钥派生。报告预设读者从未了解过格密码学。

本文总结了研究的成果：在这三者中，有没有哪一个能进入比特币协议？

研究内容

在选择签名方案时，比特币的特殊性带来了约束。我们用四个指标来评估这些方案：

链上开销。最重要的指标之一，就是公钥和签名的合并体积，因为在花费一个输出时，这两者都会记录在区块链，它们的每一个字节都会被整个网络的每一个全节点下载和存储。验证成本也是因为同样的理由而成为重要指标：每一个签名都会得到每一个节点的验证，所以，验证速度慢就会给整个网络带来负担。

实现的复杂性。 一个重要问题是，安全地实现目标方案有多难。如果一个设计需要浮点数代数，或者精细的高斯采样（Gaussian sampling），就由可能因为实现错误或者侧信道（比如时序分析）而泄露私钥。我们的目标是平滑地迁移，所以实现的复杂性是一个关键的因素。

部署难度。我们也要考虑各方案的比特币版本将面临的摩擦力： 共识攸关的哈希函数选择（这些候选者使用 SHAKE，而比特币现在使用 SHA-256），签名方案在不同硬件平台上的可复现性，以及签名程序是否适应硬件签名器的 RAM（内存）预算。

潜能：绝大部分比特币钱包都是层级式确定性的（BIP 32：从一个主公钥派生出无限数量的子公钥，而无需触及私钥。没有任何一个已经标准化的后量子方案是现成支持这种特性的，所以我们也考虑了加上这种特性需要多大的代价。我们也看了这些方案的修改版，它们并不是标准化的，但也许能带来更多好处。

哪个安全等级？

在比较体积之前，我们需要先固定一个目标安全性等级，而且这个选择没有听起来那么轻巧。NIST 定义了从 1 到 5 的安全类别，越高的类别提供了越强的安全性，但反过来需要使用更大的密钥和签名。

我们主张，比特币至少要达到等级 3 。比特币的钱币可能数十年保持不动，如果密码分析技术的进步揭晓一种方案（的安全性）低于所需的等级，那么钱币会锁定在实际较弱的密钥中，并且无限期伴有漏洞。格密码学的假设并不新颖（在公开的密码分析视野下已经存在了接近三十年，比椭圆曲线在得到比特币采用时还要久），但它们的丰富的代数结构给未来的攻击者留下了更多机会，这使我们不愿打赌它的远景。

多家重量级参与者已经得出了相同的结论。Apple 在其 iMessage PQ3 协议中完全跳过了等级 1 的格参数，只使用等级 3 和 5 的参数。Cloudflare 在其后量子 TLS 中部署了 ML-KEM -768（等级 3），并指出虽然等级 1 看起来不错，但他们倾向于为将来数十年的密码分析留出安全余量。比特币的时间尺度比这两者都要长。

安全余量伴随着代价。比如，将 Dilithium 从等级 2 升到等级 3，会在（公钥和签名）合并体积重增加大约 1.5 kB。我们的报告比较了所有可用的安全等级的参数集合，所以读者可以自行了解其取舍。近期的事件 —— 我们在 Hawk 上看到的 —— 表明谨慎并非只有理论意义。

候选者

Dilithium：最直接的选择

Dilithium（由 NIST 在 FIPS 204 重标准化为 “ML-DSA”）遵循与 Schnorr 签名相同的 承诺-挑战-响应 范式，只是转译成模格（module-lattice）代数。

它的核心特性是简洁。Dilithium 的运算都是基于整数的：环代数、矩阵向量乘积、哈希、舍入（rounding）。没有浮点数，也没有离散高斯采样，因此，我们更容易正确地实现一个安全的、常量时间的实现。它同时也是得到最广泛采用的候选，已经进入 OpenSSL、BoringSSL、AWS-LC 和 Apple CryptoKit。

代价则是体积。在安全等级 3（ML-DSA -65）， 公钥体积是 1952 字节、签名体积是 3309 字节（总计5261 字节），几乎是比特币当前的公钥签名合并体积的 55 倍，也是三个候选方案实现相同安全等级时体积最大的。

从比特币角度看，Dilithium 最有趣的特性是，它是唯一一个能够以接近实用的水平实现 BIP 32 风格的密钥派生的候选。随机化密钥构造 DilithiumRK 可以将一个亲密钥转化为子密钥，只使用公开的信息。本报告分析了 Dilithium 的三个变种，包括 DilithiumRKS，这是我们提出的一个变种，其密钥派生逻辑可以完全放在钱包软件中，而在区块链上只能看到普通的 ML-DSA 签名。这三个变种都尚未准备好部署：其中两个需要使用偏离标准的验证者，而我们提出的 DilithiumRKS 还缺乏完整的不可伪造性证明，并且所有人都依赖于一个整个网络共享的矩阵 —— 这种转化在 Module-LWE（带错误学习）的假设下是可靠的，但会将所有密钥的安全性都集中在一个实例上。我们认为，在当前阶段，基于 Dilithium 的密钥派生解决方案还属于概念验证阶段，而不是可部署的选项。

Falcon：最紧凑的一个

Falcon 由 NIST 挑选出来并标准化为 “FN-DSA”，是三者方案中最紧凑的一个。在安全等级 1，Falcon-512 只需要 1563 字节来表示一个公钥和签名；而在等级 5，Falcon-1024 只需 3073 字节。 Falcon-1024，已经有很大的安全余量，依然比安全等级 3 的 Dilithium 签名要小。

Falcon 采用了与 Dilithium 不同的路径：在 NTRU 格上使用先哈希再签名（hash-and-sign）范式。签名人的私钥是一个格的短基（short basis）；消息则哈希成空间中的一个点，然后签名人使用自己的短基来发现贴近这个点的一个格向量。点和相邻向量这两者就构成了一个签名；而验证程序只检查这个向量在这个格上，并且与这个点足够贴近。精细的部分是既要找出这个向量，又不能泄露你的基；更早的方案（GGH、NTRUSign）直接舍入为一个临近的格点，而每一个签名都会泄露少量几何学信息。Falcon 转而采用 GPV 框架，从一个高斯分布中采样临近的向量 —— 这个高斯分布的输出可以证明与基独立，从而关闭了泄露，代价则是需要一个精细得多的采样器（sampler）。

这个采样器是 Falcon 在实践中的弱点。它在复数集（complex numbers）上的傅里叶域（Fourier domain）上工作，也就是说，它使用浮点数运算。浮点数运算的结果可能因处理器、编译器甚至优化标签的不同而不同。这不仅仅影响可移植性，也是一个安全问题：GPV 证明要求签名人绝不为同一个摘要释放两个不同的短向量，然而，一旦签名程序去随机化，那么依赖于运算平台的舍入可能恰好会违反这一点。有一个解决方案：使用一个确定性的 Falcon 实现，将硬件浮点数替换成整数仿真，从而在每一个计算平台上实现完全相同比特的签名。这样一来，签名流程会降速大约 15 倍；密钥生成会降速 2 倍。

重要的是，验证过程不会受到影响，因为 Falcon 验证过程完全不使用浮点数。Falconq 签名的验证只使用整数，是确定性的，也是所有候选方案中最快的。这种不对称性对比特币非常好：一个输出只会被签名一次，也就是只有一个钱包会花费时间；但这个签名要被每一个全节点验证。在不频繁的签名上降速 15 倍，换来可复现性以及只使用整数，在我们看来是值得的。因此，我们认为，使用浮点数的要求只是一个可以处理的工程抉择，而不是一个瓶颈。

两点提醒。其一，因为结构性的要求，Falcon 没有等级 3 参数集合。要么选等级 1，要么选等级 5。基于安全余量，我们建议使用 Falcon-1024 。其二，签名过程需要占用大量内存：采样器是由一个预先计算的树驱动的，这棵树会占用 90 kB 的内存（1024 参数集）。硬件签名器可能必须逐个逐个分支重构，才能放在 16 kB 的内存内，代价是签名时长加倍。更长的签名时间，在一个小设备上是真实的成本，但也可以说是可以克服的。

Hawk：失败者

Hawk 的出发点是结合另外两个候选方案的有点：签名体积甚至比 Falcon 更小（在 512 参数等级，只有555 字节），并且使用一个简单、仅依赖于整数的签名器，签名过程只占用 6 kB 内存。它是在 NIST 的附加性签名（additional-signatures）竞赛中站到第三轮的唯一一个基于格的候选，我们的报告有一大部分篇幅是在介绍它。

取舍在其假设中。它不使用 NTRU 和 SIS（它们累积了数十年的密码分析），Hawk 的安全性依赖于 “格同构问题（Lattice Isomorphism Problem）” 以及 “one-more-SVP” 假设，两个都比较年轻。

就在我们完成这份报告的不久之后，Anthropic 公司的 Straznickas 和 Weis 在 Hawk 的格构造中发现了一个结构性的弱点：密钥复原（key recovery）事实上依赖于求解一个格的 SVP（短向量问题），但这个格的维度只有设计者们所假设的一半。这让拟议的参数集合中的密钥复原的预计成本减少了数十比特；并且，在 HAWK-256 上 —— 这个方案的挑战参数集合的意图是用于密码分析 —— 作者们演示了一个完整的端到端密钥复原（拟议的 HAWK-512 和 HAWK-1024 哪怕在此种攻击发现后，依然超出现实的破解能力）。Hawk 团队确认了这种攻击，并从 NIST 流程中撤回了这种方案，并指出，通过参数倍增来修补这个问题会毁灭 Hawk 引以为豪的紧凑性。

（译者注：这里的 “密钥复原” 应该是指从公钥求解私钥。）

我们在报告中保留了关于 Hawk 的章节，因为这种攻击爆破了被选定的数域的一个具体的代数特性，而不是设计方案范式本身。 重新设计是否能避免这个问题，还不能确定。Hawk 现在也成了一个绝佳的例子，表明了我们采用保守假设和安全余量的必要性。一个方案可能紧凑、快速、在一个标准化流程中坚持三轮，但依然因为一纸论文而导致预期安全性大幅下降。

各方案的体积

表格中的所有方案，包括 SPHINCS+ ，都是 “无状态的”：签名人无需记忆以往生成的签名。带状态的基于哈希函数的方案，比如 XMSS，实现了更小的签名体积，代价是需要管理记忆；关于这部分比较，详见我们关于哈希函数签名的报告。

为什么现在还无法定论

Falcon 没有密钥派生方法。唯一一种在 Falcon 上实现 BIP 32 形式密钥派生的构造，会随机化私钥基，导致签名范数（signature-norm）的范围大幅扩大，让放到区块链上的签名膨胀到大约 23.7 kB。更糟的是，其拟议的参数不符合该方案的安全条件，而修复这个问题又会导致体积进一步扩大。现在 Falcon 没有可用的公钥派生方法；我们把这个问题当成是这份报告找出的最有趣的开放问题之一。

Falcon 标准还未敲定。NIST 选择了 Falcon ，但 FN-DSA 草稿还未发布。标准化之后才有可以审计的实现、测试向量和硬件支持。广泛的采用会让一个共识攸关的集成更容易通过、也更安全。我们认为，等待 Falcon 发布是有意义的：从那之前，Falcon 只是一个移动的目标。

Falcon-WS 。一个新的变种放款了一项内部参数，使用 “拒绝采样” 加以补偿，使得合并体积分别降到了 1114 字节（等级 1）和 2387 字节（等级 5）。这明显小于普通版 Falcon 。我们将它视作一个非常有前景的方向，但对所有年轻的方案都有相同的提醒：它可能不会成为标准，而且需要更多密码分析。一篇后续论文已经在强不可伪造性的证明中发现了缺失（普通版本的不可伪造性不受影响）。

更好的方案会出现吗？在上述方案之外，已知最有前景的方向是从 2013 年出现的 BLISS 所代表的 Fiat-Shamir 范式，其最新的成员（由 Gärtner 在 CRYPTO 2025 发表，我们的报告也有介绍）达到了可与 Falcon 媲美的体积，并且是在已经得到充分研究的假设之下。而让它无法进入实用范围的东西是实现的安全性：BLISS 会在其非常量时间的高斯采样中因为侧信道而被攻破，而且这条路径上的后续方案都没有解决这个问题。最新的方案还警告其采样流程甚至更难保护。在这一局面改变以前，我们认为它们的吸引力都停留在纸面上，无法成为可以部署的方案。

格签名和基于哈希函数的签名是互补的。一个格方案可以成为混合方案的一部分。在 SHRINCS 中，当前设计的无状态复原路径实用 SPHINCS+ 签名，体积达到几千字节；如果换成一个 Falcon （或者 Falcon-WS）签名，体积将小得多，验证起来也更快，从而，可以让常用路径的成本不受影响，不常用路径的实用成本大幅下降。

我们的结论

在这些格签名候选方案中，排名非常明确。Hawk 已在 Anthropic 攻击后撤回。Dilithium 是最容易实现的，也是唯一一个可以使用密钥派生的，但它的体积使之不适用于比特币。Falcon 提供了最均衡的表现：紧凑性、验证速度、成熟的安全假设；并且，其主要缺点（浮点数签名）有已知的、实用的缓解措施。如果我们今天就必须为比特币挑选一种基于格的签名方案，那么我们会选 Falcon-1024 。

立足今日，我们的观点还是写在哈希函数签名报告里的那样：保守的、近期内的选择，依然是基于哈希函数的方案，它依赖于最成熟的假设，并且风险最小。这很可能是比特币的一个过渡阶段。一旦 FN-DSA 标准敲定，带来了固定的规范、可审计的实现、硬件支持，Falcon 可以显著优化纯粹基于哈希函数的签名，一种混合方案可以让两种互相补充。

完整的报告，包括完整的算法描述、安全分析、参数推导以及钱包派生构造，可以在 ePrint 上阅读，并且不需要你先掌握格密码学的背景。欢迎提出问题和反馈，我们希望这份报告能够为解决各开放问题提供有用的起点。

（完）