Quantum-proof Bitcoin Signatures May Increase Transaction Data by 10x

Quantum-proof Bitcoin signatures would burden network nodes with 10 times larger data. SHRINCS, a proposed hash-based Bitcoin signature scheme, combines smaller stateful signatures with a larger stateless fallback. The current specification sets public keys at 48 bytes, stateful signatures at 548 to 4,619 bytes, and stateless signatures at 5,777 bytes. The current rules require the larger fallback whenever the signing state cannot be trusted, preserving signing capability for someone who can recover the secret.

Brian Armstrong urged industry preparation and cooperation on October 20. Shashank Agrawal's October 13 Coinbase article asks candidate signature schemes to support ordinary wallets, recovery processes and custody servers that operate independently. Coinbase says the company's custody business holds approximately 12% of all existing BTC.

Signing state records which one-time signing slots a key has consumed, and SHRINCS' compact XMSS component relies on avoiding slot reuse. Reusing a slot to sign different messages can enable an observer to forge signatures. A backup can restore the long-lived secret without restoring a reliable history of signatures generated after the backup. Agrawal explained that generating signatures and updating state do not always produce transactions on the blockchain. The signer rules forbid backing up and restoring the changing counter or transferring the counter between software through export and import. An outdated counter therefore cannot establish a safe starting point for compact signing. The stateless fallback derives from the hash-based SLH-DSA standard but uses parameters outside the sets standardized by FIPS 205.

Agrawal described large exchanges operating independent signing servers across different zones for low latency and high availability. Agrawal assessed that stateful signing would complicate those operations by requiring exclusive access to a key and the associated state while generating a signature. A replacement server needs reliable evidence of unused state after an uncertain counter update, and copying an earlier counter does not provide that evidence. SHRINCS prohibits simultaneous signing against the same key state and requires persistent recording of the counter increment before returning the signature. The counter must never move backward, and durable storage must resist rollback and unauthorized modification. These restrictions apply separately to each key rather than requiring an exchange to halt signing with every other key. Agrawal included SHRINCS among candidates for evaluation and called for an option that uses stateless signing exclusively. Questions about ownership of dormant coins constitute a separate policy issue.

Signature-size ratios do not directly translate into transaction-fee ratios because transactions include additional data and Bitcoin treats witness bytes differently. BIP 141 calculates transaction weight as three times the stripped transaction size plus the total transaction size. Virtual size equals transaction weight divided by four, with the result rounded upward. A signature byte in the witness adds one weight unit, while prefixes and other serialization data require separate accounting.

A hypothetical single-signature model assigns 400 weight units to everything except the signature, preserves existing witness accounting and assumes 10 satoshis per virtual byte. The model uses the draft's smallest and largest stateful signatures and calculates virtual size by adding signature bytes to 400, dividing by four and rounding upward. The fallback increases the modeled fee by 13,080 satoshis relative to the smallest stateful signature, or by 2,900 satoshis relative to the largest. A self-custody recovery transaction without reliable state would require the builder to allow for the larger signature when setting the network fee. A custodian faces both the operational burden of maintaining trustworthy state and the transaction weight associated with stateless signing. Actual fee costs await deployment rules, and the documents do not establish whether custodians would absorb those costs or charge customers.

September's informational RFC 10033 describes state-management approaches including sectorization, reserved intervals and controlled transfers of keys and state. Sectorization allocates nonoverlapping signing space to separate devices, enabling parallel signing without coordination among every device for every signature. Partitioned designs therefore offer an engineering approach for Bitcoin custody to assess, with the RFC identifying specific methods and associated operational risks.

SHRINCS remains a draft, and the security proof and fully optimized implementation remain unfinished. A deployment design and implementations demonstrating interrupted writes, server replacement and wallet restoration would provide useful next evidence. Maintaining the savings from compact signatures requires demonstrating that ordinary failures will not cause signing-state reuse.