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 recovery test reaches wallets and exchanges

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.

SHRINCS signatures range from 548 to 4,619 bytes with reliable counter state, while a 5,777-byte stateless mode preserves security when that state cannot be trusted.

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.

The per-key constraints do not imply that an exchange must stop processing every other key while one signs. Agrawal's article included SHRINCS among candidates worth evaluating and calls for an available stateless-only operating mode.

Coinbase says it holds approximately 12% of BTC in existence in the context of its custody business.

What the fallback changes in a Bitcoin fee model

A 5,777-byte signature is larger than a 548-byte signature, but that ratio does not directly describe a transaction's fee. Transactions contain other data, and Bitcoin accounts for witness data differently from other bytes.

Under BIP 141's transaction-weight definitions, weight equals three times the stripped transaction size plus the total size. Virtual size is weight divided by four, rounded up.

A signature payload byte placed in the witness contributes one weight unit under that accounting, while prefixes and other serialization data still count separately.

Consider a deliberately hypothetical one-signature model. Hold everything except that signature at 400 weight units, assume unchanged witness accounting, and fix the fee rate at 10 satoshis per virtual byte.

The stateful rows use the draft's minimum and maximum signature sizes. The calculation is total weight = 400 + signature bytes, then virtual size = total weight divided by four, rounded up:

In this model, fallback adds 13,080 sats compared with the smallest stateful case, or 2,900 sats compared with the largest.

For self-custody, a recovery transaction would carry a larger signature when correct state is absent, so its builder would need to account for that weight when setting the network fee. A custodian faces both the work of preserving trustworthy state and the transaction weight of any stateless signing it uses.

Whether it absorbs those costs or passes them to customers is a separate pricing decision that these documents do not establish.

Partitioning offers a path to evaluate

Stateful signing also has mitigations beyond one shared counter. September's informational RFC 10033 catalogs approaches including sectorization, reserved intervals, and controlled transfer of key and state material.

Sectorization divides signing space into nonoverlapping parts that separate devices can manage. This permits parallel signing without every device coordinating each signature with every other one.

For Bitcoin custody, that makes partitioned designs a relevant engineering avenue to assess. The RFC's value is to identify concrete ways of managing state and the operational risks each introduces.

SHRINCS itself remains a draft, with its security proof and fully optimized implementation still listed as unfinished. Armstrong's call to prepare supplies renewed attention, while Agrawal's article supplies requirements against which candidates can be evaluated.

The next useful evidence would be a deployment design and implementations showing how the compact path behaves through interrupted writes, server replacement, and wallet restoration.

The existing fallback already makes the choice explicit: when trustworthy state is unavailable, retain signing capability by using the larger signature. Preserving the smaller path's savings requires proving that ordinary failures will not lead to state reuse.

This content is provided for general informational purposes only and doesn't constitute financial, investment, legal, or tax advice. Any events, rewards, online promotions, or related information mentioned herein should not be considered a recommendation, solicitation, or invitation to purchase, sell, trade, or otherwise deal in any crypto assets. Crypto assets are highly volatile and may result in loss. The availability of WEEX services, products, and related events may vary by region. You are responsible for ensuring that your participation is in accordance with applicable local laws and regulations.