Merkle树签名与一次性索引

一次性签名的缺点不是“只能验证一次”，而是同一秘密不宜继续签新消息。认证树先给出一批不同公钥的共同根，让每次签名带上自己那片叶的身份证明。接收者只需保管短根，不必提前收到全部公钥。

树不会修复用坏的一次性密钥。重复使用某片叶，只是给已经暴露过材料的钥匙附上同一份正确路径。签名者必须记住哪些钥匙已经消耗；这个状态不变量与哈希困难性同样属于安全前提。

四片叶中的一次失败 ​

HASH-6任务取h=2、N=4、ℓ=4，使用四组不同标签产生公开教学密钥。根为：

6e4304b913204768203ceb208683f6b2ae8566b4f43d931e297f988a121be2ff

索引1被烧掉，虽然调用者没有拿到结果，也不重新使用它。这样牺牲一个名额，换来“已输出或者可能输出过的签名不会与未来请求复用钥匙”的明确保证。允许重传已经保存的同一份签名，是另一种不消耗新钥匙的接口，不必重新调用签名算法。

回滚真的会让新消息通过 ​

故意破坏合同：索引0先签0000，把next回滚为0，再用同一叶签1111。攻击者把两份签名的原像拼成0101，附上索引0的原公钥和原路径，完整树签名验证仍接受。它未找到哈希碰撞，也没有更换根；失败恰在一次性密钥被用两次。

检查器实际执行这次攻击，与只打印一句“回滚危险”不同。它的模拟状态只用于展示接口行为，不提供真实崩溃恢复或防回滚功能。确定性公开密钥材料也只为复算，不能用于签署任何真实内容。

验证一次与签名一次是两回事 ​

同一份合法签名可以被许多人验证、重复验证，通常都会接受。EUF-CMA防的是新消息伪造，不负责让旧消息在第二次出现时失效。若应用要防重放，应把会话、序号或唯一请求标识编码进消息，并实施自己的接收策略，不能期待树路径替它记账。

删除已经用过的秘密可以减少部分后续泄漏风险，但本页保存整棵树私钥的简单实现没有证明前向安全。更换树根、分层树、私钥种子派生与标准LMS/XMSS遍历算法也各有独立规则，不从N次构造自动获得。

安全归约分成两个出口 ​

假设底层OTS满足一查询EUF安全，认证树哈希抗碰撞，各叶密钥独立，并且每叶最多产生一次签名。用成功伪造中的索引i，把提交的公钥与建树时真正的 $p{k}_i$ 比较。

若不同，正确路径却打开了同一位置的另一份公钥字节，认证树的首分歧层论证就提取哈希碰撞。若相同，伪造签名是在真实OTS公钥下成立。由于目标消息从未向整棵树请求过，它也不可能向这一叶请求过；而这一叶最多签过一条消息，所以它构成OTS的一查询新消息伪造。

把归约写成单挑战算法时，均匀猜一个叶，把挑战OTS公钥嵌在那里，其他叶自行生成。该叶被请求时转交唯一签名查询，其他叶自己回答；猜中伪造叶的概率为1/N。于是有保守的界

其中两个右侧对手都是由原伪造者构造的高效算法，碰撞提取不另乘h。要从该界推出随安全参数可忽略，N须受多项式控制，且显式生成N对密钥的工作也须为多项式。不能一边把N取为指数大，一边忽略朴素建树的指数成本。

这个二分说明各前提的位置：错误公钥靠树绑定挡住，真公钥下的新签名靠OTS挡住，索引不复用保证OTS实验只收到一次查询。长期公钥身份认证则在实验开始前由可信根前提给出。

用字节账本看公钥压缩 ​

朴素生成保存全部叶密钥与树，空间 $O(N\ell n+Nn)$ 字节。树根只占n字节，但每份签名仍带一份OTS公钥、ℓ项OTS签名及h项路径。按本文4字节索引与4字节ℓ字段，总长度为 $(3\ell +h)n+8$ 字节，消息和长期参数另计；本例为456字节。不能把“长期公钥只有一个根”误说成“每次只发送一个根”。

本例公钥生成调用32次Lamport函数，另做4次叶哈希与3次内部哈希。单次验证需4次OTS函数、1次公钥叶哈希、2次父哈希，共7次；其中公钥叶输入较长，逐字节处理成本仍要计算。已有全树时取路径只需h次读取。

终点任务：解释为什么失败发生在保留前可不消耗名额，保留后即使没有输出也应烧掉；再在N=4的轨迹中把第二步改为成功，写出最终允许的索引集合仍为{0,1,2,3}。最后只删除“每叶最多一次”这条前提，用0000、1111到0101的实测伪造定位归约中无法再回答的第二次OTS查询。