作者：jonasnick
摘要：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+ 实例：一个紧凑实例，其 $q_s = n_{dev}$，其中 $n_{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_{dev}$，这正是紧凑实例的参数要支持的签名数量。
更一般而言，紧凑实例可以允许每个设备在切换成备用实例之前生成 $n_{dsig}$ 个签名，只是要将 $q_s$ 提高到 $n_\text{dev} \cdot n_\text{dsig}$ 。在比特币应用场景中，密钥通常只会用来生成少量签名，所以一个较小的 $n_{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 字节）。
| $q_s$ | 参数 | 体积 + 16 | 签名开销 |
|---|---|---|---|
| $2^{5}$ | W+C P+FP $(k, a, h, d) = (10, 12, 12, 1)$ , $w = 16$, $S_{w,n} = 240$0 | 2324 B | 2.5M |
| $2^{10}$ | W+C P+FP $(k, a, h, d) = (8, 17, 12, 1)$ , $w = 16$, $S_{w,n} = 240$0 | 2564 B | 6.8M |
| $2^{10}$ | W+C P+FP $(k, a, h, d) = (12, 12, 12, 1)$ , $w = 16$, $S_{w,n} = 240$0 | 2708 B | 2.4M |
| $2^{12}$ | W+C P+FP $(k, a, h, d) = (10, 14, 14, 1)$ , $w = 16$, $S_{w,n} = 240$0 | 2628 B | 9.9M |
| $2^{12}$ | W+C P+FP $(k, a, h, d) = (12, 13, 12, 1)$ , $w = 16$, $S_{w,n} = 240$0 | 2884 B | 2.7M |
| $2^{14}$ | W+C P+FP $(k, a, h, d) = (8, 17, 16, 1)$ , $w = 16$, $S_{w,n} = 240$0 | 2580 B | 41.0M |
| $2^{14}$ | W+C P+FP $(k, a, h, d) = (10, 15, 14, 1)$ , $w = 16$, $S_{w,n} = 240$0 | 2772 B | 10.9M |
| $2^{14}$ | W+C P+FP $(k, a, h, d) = (10, 12, 22, 2)$ , $w = 16$, $S_{w,n} = 240$0 | 3000 B | 2.5M |
签名开销的单位是 SHA-256 的调用次数。相比之下，SLH-DSA（$q_s = 2^{64}$）会以 2.3M 次调用生成 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 \log_2(n_\text{dsig}+1) \rceil$ 比特）。
使用来自一个种子的密钥派生（类似于 BIP-32)，每一个派生密钥都是一个独立的 SHRIMPS 实例；设备必须为每个派生密钥维护这个状态，或者为每个密钥存储一个比特，来表明应该使用备用实例。
如果紧凑路径的签名数量超过 $q_s$ 配额（比如说，因为初始化设备的数量超过了预料，或者因为一个设备在更新其状态时出现了故障），安全性不会立即打破。相反，它只是逐步降级。下表展示了在 $(k, a, h, d) = (8, 17, 12, 1)$ 参数集合下，安全性如何随着紧凑路径签名数量超过 $q_s = 2^{10}$ 而逐步降级：
| 紧凑路径签名总数 | 安全性 |
|---|---|
| $2^{10}(配额） | 128.0 比特 |
| $2^{11}$ | 128.0 比特 |
| $2^{12}$ | 125.1 比特 |
| $2^{13}$ | 120.4 比特 |
| $2^{14}$ | 115.0 比特 |
| $2^{15}$ | 108.9 比特 |
顺带说一句，“带状态性”（签名设备需要为一个公钥记忆生成过签名的数量）是一个很强的假设，但相关的风险是局部的，限缩在单个没有妥善管理状态的钱包内。相反，其它后量子方案都带有系统性风险：使用新的密码学假设（格（lattices）或同源（isogenies）），或者签名体积更大。
讨论
如果我们假设用户使用带状态的钱包，并且可以约束设备初始化的次数，那么，SHRIMPS 紧凑路径签名（的体积）就比 SLH-DSA 药效，而且验证开销更低、签名开销相当。当$n_{dev$ = 2^{10}$ 以及 $n_{dsig} =1$ 时，签名体积是 2564 字节，是 SLH-DSA 的 7856 字节的 1/3 。提高 $n_{dsig}$ 的大小，可以允许每个设备生成更多（紧凑路径）签名，只是签名体积更大、签名时间也会变长；但是，即使是 $n_{dsig} = 2^4$，签名体积也不到 3000 字节。
SHRINCS 已经假设要使用带状态的钱包，所以 SHRIMPS 可以与之结合：主设备使用 SHRINCS 的高效带状态路径（产生大约 324 字节的签名），而任何备用设备都使用 SHRIMPS 紧凑路径，而不是直接回退为完全无状态的签名方案。
关于密钥生成开销的对比，尚待开发。本文所使用的参数集合，基本将每字节的验证开销约束在 SLH-DSA 的基准（大约每字节 0.30 次调用）之下。放宽这个约束（比如说，允许每字节的验证开销与 Schnorr 签名相比），将允许 $w = 256$，也许能产生体积更小的签名。这部分探索，也留给将来的工作。
– – –
感谢 Mikhail Kudinov 和 Oleksandr Kurbatov 的讨论，带来了 SHRIMPS 的概念；以及他们给本文较早版本的反馈。
– – –
1. 一个 SPHINCS+ 公钥由一个公钥（$\mathit{PK.seed}$，16 字节）与一个超级树根（$\mathit{PK.root}$，16 字节）组成。SHRIMPS 内的两个实例使用相同的 $\mathit{PK.seed}$，所以姐妹公钥只需要包含 $\mathit{PK.root}$ 。 ↩
jonasnick 2026-04-06
https://www.btcstudy.org/2026/04/06/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/