Backed into a corner

Blockchains are confronting the challenge of quantum computing with renewed urgency as more researchers continue to sound the alarm. Denial is giving way to anger and bargaining. As the first and largest cryptocurrency, Bitcoin has always benefited from a certain immunity against criticism over its original design decisions and selection of features— or lack thereof, as critics frame it: rudimentary scripting language and stubborn refusal to accept even simple improvements that restore pre-existing functionality. Defenders see the intransigence and allegiance to 2008-vintage design as a virtue: sound money must be resistant to fads, very difficult to change except by near unanimous consensus of the community. Constantly hard-forking to jump on the latest smart-contract bandwagon or implementing the most fashionable signature algorithm of the day is the last thing users need. In the extreme, this becomes a version of the originalism doctrine from US jurisprudence: every contentious question is adjudicated by deference to historical pronouncements from Satoshi.

The specter of cryptographically relevant quantum computers (CRQC) is bringing some of those ancient design relics back into sharp relief. If the engineering challenges around quantum computers are overcome anywhere as quickly as optimists are predicting, the security guarantees of Bitcoin and virtually every other cryptocurrency will be immediately undermined. That often-repeated self-custody mantra “your keys, your coins” starts to ring hollow when a quantum computer can turn your keys into their keys. This is the problem every blockchain must contend with. There are some incremental solutions such as minimizing address reuse. These are not realistic, for reasons discussed in following sections. There is widespread agreement on principle that the only long-term defense against CRQC is the adoption of new signature algorithms purpose-built to resist known quantum capabilities. The engineering challenge is deciding which one— or which options, if one fully embraces cryptographic agility and giving users an option among multiple competing algorithms— and exactly how these new capabilities will be phased into an unruly system with no formal governance model. The challenge for Bitcoin is that all options on the table pose the same problem: signatures or public-keys will take up significantly more space on chain, cutting into already scarce limits for the number of transactions that can be accommodated in each block. It turns out one of those original design assumptions will greatly aggravate that problem.

Address reuse in the original vision

To explain how 2008-era decisions have backed Bitcoin into a corner today, it is helpful to highlight one aspect of the original design. Satoshi expected that addresses would only be used once. This also implies underlying cryptographic keys are also not reused, since there was a strict one-to-one mapping between them originally.¹ Every Bitcoin wallet could generate an unbounded list of new addresses from a single “seed” secret. Each time the owner of that wallet needs to receive funds, they generate a fresh address with no previous history on-chain. That would be true even when sending funds back to oneself, as part of the so-called “change output.” If Alice has an unspent output of 10 bitcoins and needs to send Bob 1 bitcoin, the remaining 9 bitcoins would be sent back to a brand-new address Alice controls, not the original source address where the funds originated.

It was privacy and not the distant threat of quantum computers that underpinned this original avoidance of address reuse. CRQC remained very much in the realm of academic research during the 2000s when core ideas underlying Bitcoin were brewing in the cypherpunk community. Regardless of the motivation, some key decisions followed from this assumption:

• Every transaction input is signed independently. If there are 10 inputs, there must be 10 signatures. It would not make sense to have a single signature authenticating multiple inputs, since they are all going to be coming from different addresses controlled by different keys. (In theory there is another, more advanced optimization possible: called “signature aggregation,” it allows combining multiple signatures into a single signature that is in turn verified against a combination of public-keys. But this is not supported by the consensus layer either.)
• Each signature must be accompanied by the associated public key, since there is no other way to verify whether that address is controlled by that key. Later this would extend to revealing the full redeem script, which may include multiple public keys in the case of multisig. Again this makes sense if addresses are never reused. That specific public-key or redeem script has never appeared on-chain before, so it is not possible to refer back to a previous occurrence or waste space on storing that for future use, since that address will never appear in a future transaction again.

Address reuse in reality

In actual usage of Bitcoin, it turns out address reuse has become the norm. It is not some exceptional case of opsec failure. In fact later blockchains even made a virtue of address stability. For example, Ethereum and Solana group funds by address, not by chunks of coins (“UTXO” for “unspent transaction output”) as with Bitcoin. There are good reasons for this:

1. Enforcing transaction policy. The easiest way to lose control of assets on a blockchain is key compromise— when the threat actor gets hold of the private key. A close second is when the legitimate owner is tricked into wielding that private key to sign the “wrong” transaction: one that sends funds to the threat actor instead of the intended recipient. The difference between a right and wrong transaction comes down to a handful of factors, with the most significant one being the destination address. When addresses are stable, it is easy to determine whether a given address is friend or foe. Given a list of known addresses for every potential recipient, including other wallets belonging to oneself, it becomes trivial to determine what the effect of a transaction will be: how much funds are being sent to another party, how much is returned back to the sender as “change” and what fees are paid to miners for the privilege of transacting.

This concept of address whitelisting is now table-stakes for custodial services: users commit to a list of known safe addresses ahead of time and the system does not allow transfers outside of that set. (Of course there has to be some way of adding new entries to the list, and that process is made deliberately high-friction, for example by requiring out-of-band authentication or mandatory 7-day waiting period. The threat model is that even if an attacker can impersonate the legitimate customer or attempts to coerce them into executing a transfer, they can not succeed.)

2. Proof-of-reserves. In PoR a custodial service proves to its customers that they have control of all digital assets entrusted to its safekeeping. This involves two pieces:

• Proof of liabilities: committing to the BTC balance of every customer in a verifiable manner, including the total balance across the entire customer base
• Proof of assets: proving that the custodian controls an amount of BTC on the blockchain that is equal or greater than the liabilities.

For all practical purposes, this second step requires not only disclosing addresses but proving that the custodian still has possession of the private keys associated with that address by signing with them. While there have research proposals for doing semi-private proof-of-assets by mixing in an additional “cover” set of addresses to obfuscate the ones controlled by the custodian, it turns out the privacy improvements are limited. A satisfactory proof also requires keeping funds at the existing addresses over which the proof was conducted. If one were to conduct the PoR by moving all funds to new addresses, it would leave open the question of whether the custodian accidentally moved funds to some address they can not control, until the next PoR demonstration when they can be moved again.²

Signature bloat

As noted, the Bitcoin transaction signing format lacks any optimizations to reduce the cost of signing multiple inputs with the same public key. This is hardly noticeable when using ECDSA because both signatures and public-keys are short: public-keys take up 33 bytes with point compression while signatures are around ~70 bytes depending on encoding.

That calculus changes with post-quantum signatures. All of the algorithms standardized as part of the NIST post-quantum cryptography effort have either large signatures, large public-keys or both. NIST Signature Zoo provides a convenient way to compare these schemes, including an option to sort by total size of public-key plus signature. That is the relevant metric for Bitcoin’s existing design where every input is signed independently and contains the full public-key. Among algorithms standardized by NIST so far, the “winner” according to that criteria is ML-DSA. At 3723 bytes for one signature and public-key, it still represents a almost 40-fold expansion in space required— and that is at the lowest acceptable security level by NIST standards. Slightly more promising is Falcon/NTRU scheme, currently pending standardization. It would reduce that overhead to ~1600 bytes, a meaningful improvement over ML-DSA but far from the status quo.

Hash-based signature schemes such as SLH-DSA fare much worse on this metric. Their public-keys are qiute compact— effectively the size of one classical hash— but signatures run into multiple kilobytes. In a world where address reuse is common, this is exactly the wrong trade-off: a public-key can be “cached” on chain to amortize the storage cost of a public-key, but every transaction must still be signed independently. Note these figures assume funds are controlled by a single key: the overhead gets worse when starting to compare more complex configurations such as multi-signature schemes where all possible public-keys must be included in the signature script. ³

Reckoning with address reuse

For Bitcoin to achieve post-quantum security without further degradation of its throughput, there are two paths forward:

1. Double-down on the hope that address reuse can be eliminated or at least strictly bounded. If one assume only a limited number of transactions are permitted out of each address, there are purpose-built stateful hash-based “few-time” signature algorithms that are more compact than the general NIST-sanctioned stateless hash-based signatures. The trade-off is a highly brittle security model: if the number of transactions is exceeded or state is mismanaged (for example, restoring from a backup resulting in reuse of previously “spent” private-key) the result is a catastrophic failure.
2. Accept that address reuse is going to be the norm and implement difficult protocol changes to optimize for block space given the demands of post-quantum signatures. This will likely involve a hard-fork to improve transaction verification:

• Cache redeem scripts in unpruned UTXO, to avoid outputting the same public-key over and over again
• Allow one signature to cover multiple inputs. This could involve consolidating inputs when they share a redeem script or supporting signature aggregation across inputs. Aggregation is a more generic, powerful technique: it works across messages signed with different keys. But it is also highly dependent on the choice of signature algorithm; not every scheme lends itself to efficient aggregation. Having a “batched” signature cover multiple inputs is more straightforward from a cryptographic perspective as it does not depend on the mathematical structure of the algorithm. On the other hand, it is more complex for interoperability with Bitcoin script, since the spending conditions encumbering an input may include additional logical constraints in addition to a signature check.

CP

1 Interestingly that is no longer true: with the introduction of Bitcoin script, it is possible to generate infinite variants of a script that effectively expresses a spending condition involving the same key. Each of those variants would result in a unique address that looks independent, until the script is revealed at the time of spend.

2 Interestingly the proof-of-reserves requirement also complicates attempts to defend against quantum computers by hiding public-keys until they are spent.

3 Incidentally this discussion ignores speed of signing and verification. As things stand, the Bitcoin blockchain can only sustain a handful of transactions per second. One modern, low-end embedded device can handily out-sign and out-verify the entire network, even with the increased computational requirements of post-quantum algorithms.