SHRIMPS：适用多台带状态设备的小体积后量子签名

作者：jonasnick

来源： https://delvingbitcoin.org/t/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/2355

摘要： SHRINCS（ 中文译本）使用带状态的签名器实现了非常小体积的基于哈希函数的签名，同时依然允许静态备份。不过，任何新设备，如果要使用效率更高的带状态路径，就要为其导入状态，这是非常容易出错的，所以在实际应用中，任何复原的设备或者次要的设备，通常都会回退为大体积的无状态签名方案。SHRIMPS 消除了这种只能使用单一设备的约束。在每个密钥仅用于生成少量签名的条件下（这正是比特币钱包的常见情形），一个静态的种子备份可以导入到许多独立的带状态签名设备；在 $128$ 比特安全性下，每个设备能产生一个大约 $2564$ 字节的签名。这种构造会给设备初始化的次数设置上限：在一个较为保守的上限 $n_{\text{dev}} = 2^{10}$ 之下，SHRIMPS 签名的体积不会超过 SLH-DSA 签名（$7856$ 字节）的三分之一。SHRIMPS 可以跟 SHRINCS 相结合：主设备生成大约 $324$ 字节的签名，同时任何备用设备都生成不到 $3$ KB 的签名。

SHRIMPS 基本原理

在 SPHINCS+ 方案中，参数 $q_s$ 限制了单个密钥可以安全地生成的签名的数量。更小的 $q_s$ 可以让签名的体积更小。SHRIMPS 这种构造在一个公钥内结合了两个 SPHINCS+ 实例：一个紧凑实例，其 $qs = n{\text{dev}}$，其中 $n_{\text{dev}}$ 是设备初始化的次数上限；还有一个备用实例，使用充分大的 $q_s$（例如 $2^{40}$ 或者 $2^{64}$）。SHRIMPS 公钥是这两个公钥的一个哈希值。

             ┌────────────────────────────┐
             │         Public Key         │
             └──────┬─────────────┬───────┘
                    │             │
         ┌──────────▼──────┐  ┌───▼───────────────┐
         │  Compact path   │  │  Fallback path    │
         │  SPHINCS+ with  │  │  SPHINCS+ with    │
         │  q_s = n_dev    │  │  large q_s        │
         └─────────────────┘  └───────────────────┘

签名设备初始化的方法就是导入种子词，这会确定性地派生出两个 SPHINCS+ 密钥对。要签名的实在，设备就查找这个密钥的持久化状态，以确定这个密钥是否曾经签过名：如果没有，就通过紧凑实例来签名，并更新其状态；否则，就通过备用实例来签名。

一个 SHRIMPS 签名由一个（选定实例的） SPHINCS+ 签名和另一个实例的公钥（$16$ 字节1）组成。验证者从 SPHINCS+ 签名中重构签名实例的公钥，然后重新哈希两个公钥来重构 $pk$ ，并将它与已知的公钥相比对。这个 $16$ 字节的姐妹公钥，是标准的 SPHINCS+ 签名以外的唯一开销。

因为每个设备都只使用紧凑实例签名至至多一次，在所有设备中生成路径签名的数量最多就等于初始化设备的数量 $n_{\text{dev}}$，这正是紧凑实例的参数要支持的签名数量。

更一般而言，紧凑实例可以允许每个设备在切换成备用实例之前生成 $n_{\text{dsig}}$ 个签名，只是要将 $qs$ 提高到 $n{\text{dev}} \cdot n{\text{dsig}}$ 。在比特币应用场景中，密钥通常只会用来生成少量签名，所以一个较小的 $n{\text{dsig}}$ 就足以让绝大部分签名都在紧凑路径上。

在比特币钱包的用法中，使用一个种子来初始化一台设备通常是手动操作，而且很少发生。$n_{\text{dev}} = 2^{10} = 1024$ 已经是保守的了；很难想象要把一个种子导入超过 $1000$ 台设备中。一个设备就算弄丢了自己的状态、使用种子重新初始化，也将再次使用紧凑路径，从紧凑路径的 $q_s$ 配额中消耗多一个签名。

备用实例可以使用任何 SPHINCS+ 参数组合，只要 $q_s$ 足够大。使用 SLH-DSA（$q_s = 2^{64}$ 的 SPHINCS+ 实例），备用签名的体积是 $7856$ 字节；使用一个 $q_s = 2^{40}$ 的 SPHINCS+ 变种（来自我们的《 比特币适用的基于哈希函数的签名》)，签名的体积不到 $4.5$ KB 。

下表展示了紧凑路径各参数集合的结果，其中的体积是 SPHINCS+ 签名的体积加上姐妹公钥的体积（$16$ 字节）。

签名开销的单位是 SHA-256 的调用次数。相比之下，SLH-DSA（$q_s = 2^{64}$）会以 $2.3$M 次调用生成 $7856$ 字节的签名。验证开销是签名的每一字节消耗 $0.3$ 次调用；上述 $d = 1$ 的参数集合实现了每一字节消耗大约 $0.19$ 次调用（降低了 $35\%$），而 $d = 2$ 参数集合实现了每一字节消耗大约 $0.25$ 次调用。每一行都可以使用 SPHINCS-Parameters 库（编号 f2ea2a2）的 costs.sage 程序中使用 --params 选项复现。

sage costs.sage --params <scheme> <q_s> <k> <a> <h> <d> <w> <S_wn>

比如说，第二行就用这样的命令复现：sage costs.sage --params W+C_P+FP 10 8 17 12 1 16 240。

状态管理

紧凑路径需要为每个公钥保存一个状态：设备需要存储一个紧凑路径签名次数的计数器（ $\lceil \log2(n{\text{dsig}}+1) \rceil$ 比特）。

使用来自一个种子的密钥派生（类似于 BIP-32)，每一个派生密钥都是一个独立的 SHRIMPS 实例；设备必须为每个派生密钥维护这个状态，或者为每个密钥存储一个比特，来表明应该使用备用实例。

如果紧凑路径的签名数量超过 $q_s$ 配额（比如说，因为初始化设备的数量超过了预料，或者因为一个设备在更新其状态时出现了故障），安全性不会立即打破。相反，它只是逐步降级。下表展示了在 $(k, a, h, d) = (8, 17, 12, 1)$ 参数集合下，安全性如何随着紧凑路径签名数量超过 $q_s = 2^{10}$ 而逐步降级：

| 紧

• 本文转载自： btcstudy.org/2026/04/06/... , 如有侵权请联系管理员删除。