Verifiable Monotone Chains: A Primitive for Cryptographically Enforced State Lifecycles, with an Application to XMSS

Abstract

Stateful cryptographic schemes—exemplified by the hash-based signatures XMSS (RFC 8391) and LMS (RFC 8554)—require the signer to advance a local state monotonically; any rollback is catastrophic, yet a verifier has no way to check it. IETF guidance on state and backup management for hash-based signatures states explicitly that the verifier must simply trust the signer not to have reused state. We define verifiable monotone chains (VMC), a primitive that makes such state discipline cryptographically verifiable: state evolves along a finite poset (S, ⪯) under inflationary monotone operators, every transition carries a zero-knowledge proof, and a public commitment to the state provides an audit trail. We formalize two security notions: monotone-unforgeability (MU), which captures that an external adversary cannot certify an illegal or rolled-back transition, and auditability (AUD), which captures that signer rollback cannot be hidden from a public root history. Both notions reduce, with explicit advantage bounds, to position binding of the underlying vector commitment and knowledge soundness of the proof system. We instantiate VMC as RSEP-XMSS, in which each XMSS signature carries a proof that the signed leaf advanced along the chain FRESH ≺ USED ≺ SPENT in a Poseidon-based state Merkle tree, and we give a complete algorithmic specification with a concrete circuit design (~6041 R1CS constraints estimated, Groth16 proving time estimated at 5–15 ms, signature overhead of about 1–3 KB). RSEP-XMSS is one-way compatible with standard XMSS: legacy verifiers verify the core signature, while enhanced verifiers reject unprotected signatures, preventing downgrade attacks.