Solana上的Winternitz签名
与依赖于整数分解或离散对数等数学问题的RSA或ECDSA签名不同，这些签名容易受到量子攻击的威胁，Winternitz签名的安全性完全依赖于加密哈希函数的单向性。
这一根本性的区别使其成为后量子密码学的基石。
什么是Winternitz签名
Winternitz一次性签名（WOTS）源自Leslie Lamport在20世纪70年代的开创性工作。Lamport证明了仅使用加密哈希函数而无需复杂的数学假设也可以创建数字签名。
Lamport的原始方案使用两个秘密值对单个位进行签名。要签名位b，需要揭示哈希值H₀的前像（如果b=0）或H₁的前像（如果b=1）。其安全性完全依赖于找到哈希前像的计算不可行性：本质上是从哈希输出反推其输入。
然而，Lamport签名效率极低。签名一个n-bit消息需要2n个秘密值，并生成2n值的签名。对于256位消息，这意味着需要管理512个秘密值并生成512值的签名。
Robert Winternitz在20世纪90年代意识到，与其在基数2中对单个位进行签名，不如在更高的基数（如基数16或基数256）中对更大的“数字”进行签名。这一创新大大减少了密钥和签名的大小，同时保持了相同的安全保证。
数学基础
Winternitz参数与基数表示
Winternitz签名中的关键参数是w，它决定了如何对消息位进行分组：
- 基数：
b = 2^w - 数字范围：每个数字表示
w位，其值范围从0到2^w - 1
常见的参数选择：
w = 1：每个位置代表1位（值为0或1），相当于二进制的Lamport签名w = 4：每个位置代表4位（值为0-15），即十六进制表示w = 8：每个位置代表8位（值为0-255），即二百五十六进制表示
哈希链
Winternitz签名使用哈希链——从一个秘密值开始，通过重复应用哈希函数生成的序列：H⁰(s) = s，H¹(s) = H(s)，H²(s) = H(H(s))，...，Hⁱ(s) = H(H^(i-1)(s))
其安全性具有不对称性：给定Hⁱ(s)，计算任何Hʲ(s)，其中j > i是简单的（只需对j-i进行更多次哈希），但计算任何Hʲ(s)，其中j < i在计算上是不可行的，因为这需要逆转哈希函数。
校验和机制
校验和机制可以防止一种特定类型的伪造攻击。如果没有校验和，攻击者在看到签名后，可能会修改消息，使其需要在某些链上进行更多的哈希操作，然后伪造这些部分。
校验和确保了所有链的总“哈希预算”保持不变：如果攻击者将消息数字修改为更大的值（需要更多的哈希操作），校验和数字会自动变小（需要在其他值中减少哈希操作，这是没有私钥的情况下无法伪造的）。
密钥生成过程
对于消息长度为n位，Winternitz参数为w的情况：
- 计算签名长度：首先，确定表示任何消息所需的“块”数量。如果消息长度为256位，选择Winternitz参数为
w = 4，则总共需要64个块：l₁ = ⌈n/w⌉。使用公式l₂ = ⌊log₂(l₁ × (2^w - 1))/w⌋ + 1，我们可以得出，对于w = 4，最大校验和为960，l₂ = 3，签名的大小将是l = l₁ + l₂
-
创建随机起点：为每个需要的哈希链生成一个随机的秘密值。这些随机值成为您的私钥组件。可以将每个值视为单独哈希链的“起点”：
sk = (sk₁, sk₂, ..., skₗ) -
对于每个私钥组件，重复应用哈希函数，直到达到最大可能的哈希次数（
2^w - 1）：pk = (H^(2^w-1)(sk₁), H^(2^w-1)(sk₂), ..., H^(2^w-1)(skₗ))
签名过程
对消息M进行签名：
-
将消息转换为基数表示形式：
M → (m₁, m₂, ..., m_l₁)，其中每个mᵢ ∈ [0, 2^w - 1] -
计算校验和：
c = Σ((2^w - 1) - mᵢ) for i = 1 to l₁并将c转换为基数表示形式：c → (c₁, c₂, ..., c_l₂)
- 生成签名：基数表示形式指示私钥需要被哈希的次数。
验证过程
验证消息M的签名σ与公钥pk：
-
重新计算消息表示形式：
M → (m₁, m₂, ..., m_l₁) -
重新计算校验和：
c = Σ((2^w - 1) - mᵢ) → (c₁, c₂, ..., c_l₂) -
对每个签名组件，哈希剩余次数：
- 对于消息部分：验证
H^((2^w-1)-mᵢ)(σᵢ) = pkᵢ - 对于校验和部分：验证
H^((2^w-1)-cⱼ)(σ_(l₁+j)) = pk_(l₁+j)
- 对于消息部分：验证
安全性
一次性使用限制
Winternitz签名是一次性签名（OTS）：每个密钥对只能安全使用一次。
攻击的原理如下：当您使用相同的私钥签署多个消息时，会暴露哈希链中的中间值。
校验和机制要求增加某些消息数字（更多哈希）必须通过减少校验和数字（更少哈希）来平衡。通过多个签名在不同位置暴露中间值，攻击者可以构造伪造签名，利用更高的中间位置进一步提升消息组件，同时利用较低的中间位置平衡校验和，从而遵守总哈希预算的限制。
后量子安全性
Winternitz 签名的安全性完全依赖于哈希函数的原像抗性。量子计算机无法高效地反转像 SHA-256 或 SHA-3 这样的加密哈希函数——这与能够在多项式时间内破解 RSA 和 ECDSA 的量子算法（如 Shor 算法）不同。
使用适当参数的 SHA-256 提供了 128 位的后量子安全性，使这些签名即使在后量子时代也适用于长期加密应用。
Winternitz Signatures on Solana
Solana 当前的加密基础完全依赖于 Ed25519 签名，这种签名通过 Shor 算法容易受到量子攻击。
当量子计算机变得实用时，Solana 上的每个钱包、程序权限和交易都可能被伪造。
后量子迁移不是一夜之间可以完成的事情。系统需要从今天开始设计量子抗性，创建在前量子和后量子世界中都能运行的混合方法。
虽然 Solana 的基础层仍然容易受到量子攻击，但开发者可以使用 Winternitz 签名在其之上构建量子抗性应用程序。