Quantum-proof Bitcoin signatures would clog network nodes with 10x larger data

Coinbase’s push to prepare Bitcoin for quantum computing addresses what happens when a wallet returns from an old backup or a signing server fails.

Brian Armstrong called on Oct. 20 for preparation and collaboration across the industry. The operational detail comes from Shashank Agrawal’s Oct. 13 Coinbase article, which asks prospective signature schemes to work with ordinary wallets, recovery procedures, and independently operating custody servers.

SHRINCS, a draft hash-based signature scheme for Bitcoin, combines smaller signatures that require a reliable record of previous signing with a larger fallback that works without that record. Under its current rules, recovery with uncertain state means taking the larger path.

That preserves a route to signing for someone who can recover the secret. The bargain is that keeping the smaller signatures requires additional operational discipline.

The current SHRINCS specification lists a 48-byte public key, stateful signatures between 548 and 4,619 bytes, and a stateless signature of 5,777 bytes.

“State” is the changing record of which one-time signing slots a key has already used. SHRINCS’ compact component (XMSS) depends on not reusing those slots. Reusing one for different messages can allow an observer to forge signatures.

A backup can recover the long-lived secret without recovering a trustworthy record of every signature created since the backup. Agrawal also explained that signatures and state updates do not necessarily result in an on-chain transaction.

When correct state is unavailable, including after restoring from a static backup, the implementation must refuse stateful signing and use only the stateless path. That fallback is derived from SLH-DSA, a hash-based signature standard, but uses a parameter set outside the sets standardized in FIPS 205.

The signer rules prohibit backing up and restoring the mutable counter or exporting and importing it into other software. Yet, an old counter cannot simply be treated as a safe starting point for compact signatures.

The ownership questions surrounding dormant coins present a separate policy problem.

For an exchange, the same requirement reaches beyond a recovery screen. Agrawal described large exchanges running signing servers independently in different zones to provide low latency and high availability.

In his assessment, stateful signing would require exclusive access to a key and its state during signature generation, complicating that independent operation.

If a server creates a signature but the outcome of its counter update is unclear, a replacement server needs a reliable basis for knowing which state remains unused. Copying an older counter onto the replacement would not establish that.

SHRINCS’ current rules prohibit concurrent signing with a key’s state and require the counter increment to be recorded persistently before the signature returns to its caller. The counter must never decrease, and its storage must be protected against unauthorized changes. The specification emphasizes durable storage that resists rollback.