SHRINCS：带有静态备份的 324 字节有状态后量子签名——协议设计

摘要：当公钥生成的签名数量较少时，有状态的基于哈希的签名方案可能非常高效。有状态方案的一个主要问题是，在每次签名操作后，状态都需要被正确地备份和更新。通过将无状态哈希方案（例如 SPHINCS+ 的变体）与一次性签名的非平衡 XMSS 树（有状态）进行简单结合，我们获得了一种称为 SHRINCS 的方案。当只需要少量签名时，它极其高效，并且可以使用静态种子进行备份。更准确地说，SHRINCS 公钥是有状态和无状态公钥的哈希值。我们假设密钥生成发生在能够安全保存状态的签名设备上。因此，签名设备可以使用高效的有状态签名来为公钥签名。当已知状态损坏或丢失时（例如还原了静态种子备份），签名设备仅使用无状态签名。因此，SHRINCS 在正常操作期间提供了有状态签名的效率，同时保持了无状态签名作为后备方案的鲁棒性。

SHRINCS 设计

Mikhail Kudinov 和 Jonas Nick 在报告《Hash-based Signatures for Bitcoin》中简要介绍了 SHRINCS。SHRINCS 的构建需要一个无状态签名方案和一个能生成短签名的有状态签名方案。SHRINCS 包含以下算法：

• KeyGen()：密钥生成算法提取主种子，分别推导出有状态和无状态签名方案的私钥 $\mathit{sk}_1$ 和 $\mathit{sk}_2$。它生成有状态和无状态方案的公钥 $\mathit{pk}_1$ 和 $\mathit{pk}_2$。最后，它返回元组 $(\mathit{seed}, \mathit{pk}, \mathit{state})$，其中 $\mathit{pk} = H(\mathit{pk}_1, \mathit{pk}_2)$，$\mathit{state}$ 是有状态方案的初始状态。
• Restore(seed)：恢复算法重新推导出 SHRINCS 公钥 $\mathit{pk}$，将 $\mathit{state}$ 设置为 $\textsf{LOST}$ 并返回元组 $(\mathit{seed}, \mathit{pk}, \mathit{state})$。
• Sign(seed, state, m)：如果 $\mathit{state} \neq \textsf{LOST}$，签名算法重新推导出 $\mathit{sk}_1$ 和 $\mathit{pk}_2$，并使用 $\mathit{sk}_1$、$\mathit{state}$ 和消息 $m$ 运行有状态方案。它返回更新后的状态 $\mathit{state}'$ 以及与 $\mathit{pk}_2$ 拼接的签名。否则，它重新推导出 $\mathit{sk}_2$ 和 $\mathit{pk}_1$，使用 $\mathit{sk}_2$ 和 $m$ 运行无状态方案，并返回 $\mathit{state}' = \mathit{state}$ 以及与 $\mathit{pk}_1$ 拼接的签名。
• Verify(pk, m, sig)：验证算法将 $\mathit{sig}$ 解析为 $\mathit{sig}' | \mathit{pk}'$，根据无状态或有状态方案验证 $\mathit{sig}'$（从而恢复签名公钥），并检查这两个公钥的哈希值是否为 $\mathit{pk}$。

当一个能够安全维护状态的签名设备初始化后，它使用有状态方案进行签名。每当使用种子恢复设备时，它都会回退到无状态方案。因为有状态路径效率更高，从恢复的设备签名比从原始设备签名的开销更大。

无状态和有状态组件

对于无状态签名方案，候选方案包括 SLH-DSA 或 SPHINCS+ 的变体。签名大小通常在 3KB 到 8KB 之间。对于有状态方案，SHRINCS 使用“非平衡 XMSS”。常规的 XMSS 公钥是一次性签名 (OTS) 公钥的默克尔树。为了签名，签名者递增状态 $q$，使用第 $q$ 个 OTS 密钥生成签名，并提供通向根节点的认证路径。

SHRINCS 的有状态部分使用非平衡树，而不是平衡默克尔树。第一个 OTS 位于深度 1，第二个位于深度 2，依此类推。这使早期签名的认证路径长度最小化。在 NIST 安全级别 1 下，OTS 签名 (WOTS+C) 为 292 字节，认证路径为 $q \cdot 16$ 字节。

状态完好时的签名大小为 $\min(292 + q \cdot 16, s_l) + 16$，其中 $s_l$ 是无状态签名的大小。对于 $q = 1$，此签名比 ML-DSA 小 11 倍以上。虽然安全需要安全的状态管理，但如果状态丢失，SHRINCS 签名者总是可以回退到无状态路径。

技术讨论

安全级别与 Grover 算法

moonsettler：对于 PQC 来说，128 位听起来有点小。针对 Grover 算法只有 64 位安全性。

jonasnick：128 位对应于 NIST 标准中的“安全级别 1”。“针对 Grover 算法的 64 位安全性”没有考虑到哈希函数电路的评估深度。Grover 算法的并行化效果不佳；在 $k$ 台机器上运行只能获得 $\sqrt{k}$ 的加速。你需要数百万台量子计算机运行十年才能破解它。话虽如此，在 NIST 级别 3（192 位）下，$q=1$ 时的签名大小将为 660 字节。

WOTS 与校验和

moonsettler：是否有人可以制造 ASIC 来寻找一个替代消息，从而生成一个每个字节都大于或等于原始字节的有效信封？

jonasnick：校验和防止了这种情况。任何每个数字都大于或等于原始数字的替代消息，其校验和保证更小。在 WOTS+C 中，由于校验和不匹配，验证将会失败。

状态管理与硬件钱包

conduition：SHRINCS 不鼓励地址复用，因为交易会变得更昂贵。然而，故障注入或在设备间复制种子可能会导致状态复用和伪造。

jonasnick：预期的功能是，导入种子的设备必须始终使用无状态路径。只有最初生成种子的设备才使用有状态路径。

conduition：钱包软件并不总能确定其种子是否在多个设备上（例如磁盘克隆）。然而，钱包可以将上次打开后创建的转出交易视为状态丢失的指标。

通过操作码实现

conduition：与其使用单个 OP_SHRINCS，我们可以标准化 OP_SPHINCS 和 OP_WOTS（或 OP_XMSS），并让钱包将它们组织在 Taproot 树中。

jonasnick：这是可行的，尽管让钱包决定树结构可能会留下破坏隐私的指纹，并且效率略低于专用操作码。

conduition：如果我们部署 XMSS，默克尔分支应该是无方向的（字典序排序），以掩盖已发布签名的数量。观察者无法分辨签名是来自平衡树还是非平衡树的第一个或最后一个。

TPM 与安全存储

jonasnick：要在桌面上使用 SHRINCS，我们可以使用 TPM 插槽来存储状态的哈希值。钱包在签名前会检查 TPM，以确保状态没有被磁盘还原回滚。

conduition：你也可以在 TPM 中存储解密密钥，并将状态加密后保存在磁盘上。如果磁盘被还原到新机器上，没有 TPM 密钥就无法访问该状态。

恢复密钥与契约

gmaxwell：许多不同的 SHRINCS 密钥可以共享一个恢复密钥。共识规则可以允许单个恢复签名用于多个输入（跨签名聚合），以减少资金归集期间的链上成本。

EthanHeilman：使用 OP_CAT 实现 SHRINCS 的成本会有多高？我们能否使用契约（Covenants）将状态传递给下一笔交易，以限制状态混淆造成的损失？

SHRINCS-L：在 Liquid 上的性能

olkurbatov：我们设计了 SHRINCS-L，专为 Liquid 优化（验证器位于 Simplicity 中）。它以签名大小换取更少的哈希操作。

Simplicity 验证器基准测试：

• SLH-DSA: ~770,000 kWU
• SHRINCS (无状态): ~222,000 kWU
• SHRINCS-L (无状态): ~92,500 kWU
• SHRINCS-L (有状态): ~37,800+ kWU

SHRINCS-L 规范 (NIST 级别 1):

• 种子 (Seed): 48 字节
• 公钥 (Public Key): 32 字节
• 有状态签名 ($q=1$): 1092 字节
• 无状态签名: 4396 字节

• 原文链接： delvingbitcoin.org/t/shr...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～