In my personal opinion, the most dangerous and unpredictable challenge facing Bitcoin is not political pressure, practical usability, scaling, or economic incentive… It is the threat of quantum computers.
Large and powerful organizations  both political and corporate  have been pouring billions of dollars into developing quantum computers for decades. Ever since Peter Shor published his (in)famous namesake algorithm in 1994, cryptographers have been preparing for “QDay”  the day a large, practically usable quantum computer becomes available.
If you’re reading my blog, I can assume you are at least roughly familiar with elliptic curve public/private keys. I’ll simply tell you that a quantum computer of sufficient power would be able to flip an EC public key backwards into its private key  a feat thought to be implausible with ordinary classical computers. You can see how this might be a problem. If you’d like to learn how this can be done in detail, check out Shor’s original paper.
This article won’t dissect the mechanics of how quantum computers break Bitcoin public keys, nor is it intended as a doomandgloom FUDpiece about how we should all be digging graves, stocking bunkers, and prepping for day zero of the postquantum meltdown. I won’t bother to conjecture how long it will take for a powerful quantum computer to be invented  Estimates of when this will occur vary widely even between professional analysts. I will simply assume it will happen, one day, eventually. When it does, we must deal with it.
My hope is that this article will show you the landscape of the quantum threats facing the Bitcoin community. Then I’ll explore various hashbased signature schemes and analyze their potential to diffuse these threats, and the tradeoffs which inevitably come with them. Finally, I’ll propose a novel upgrade path for Bitcoin clients which uses hashbased cryptography as a fallback option to insure bitcoin users against future quantum adversaries, without the need for any nearterm consensus changes.
_{All safe roads once were wild.}
The Quantum Threat
In this section I’ll dive into the mechanics of how exactly a selfish quantum adversary could attack Bitcoin for financial gain. Understanding the fundamental threat of quantum computers in more detail will lead us to clues as to how we can improve our defenses.
Almost every Bitcoin transaction mined from the genesis block to today has authenticated itself using one or more asymmetric signatures. Sometimes public keys are hashed. Sometimes we use Bitcoin script opcodes to encumber coins with additional validation steps (e.g. time delays). But eventually, to spend a Bitcoin UTXO safely, one must be required to supply an asymmetric signature matching some public key committed to by the UTXO itself. The signature must commit to the spending transaction in some way so that it can’t be applied to a different transaction.
If one were to encumber a transaction output with only a hashlock, or only a timelock, etc, with no asymmetric signature requirement, then that UTXO can be spent by anyone who observes it being spent (including the miners who must see the transaction to validate it).
1  OP_SHA256 <hash> OP_EQUAL 
_{A simple hashlock Bitcoin script pubkey. This script is unspendable until someone reveals the preimage of <hash>. After that, the script could be easily unlocked by anyone.}
Bitcoin transactions use signatures on the secp256k1 elliptic curve to achieve this asymmetric authentication dynamic. ECDSA is the older and more wellknown signing algorithm, and Schnorr is a cleaner, faster, more secure and more flexible signing algorithm which was adopted several years ago as part of Bitcoin’s Taproot upgrade. Bitcoin’s Schnorr and ECDSA signing protocols both use the same secp256k1 elliptic curve.
ECDSA and Schnorr signing protocols are equally vulnerable to a quantum adversary (QA) who knows a victim’s secp256k1 public key, because the QA can simply invert the public key into the private key, and sign any message they desire.
However, the same QA will have a much harder time computing the preimage (i.e. input) of a hash function given its output. The currentlyknown bestcasescenario for a QA bruteforcing a hash preimage is a quadratic speed boost, given by Grover’s algorithm. Quadratic in this context means that if a classical computer requires
So not all oneway functions are dead in the water, and cryptographic hashes aren’t the only ones still kicking.
Let’s examine the different address (output script) types in more detail.
Hashed Output Types
_{(AKA P2PKH/P2SH/P2WPKH/P2WSH)}
The most commonly used type of Bitcoin address today is a payto(witness)publickeyhash address (P2PKH/P2WPKH), in which the public key is first hashed before being given to the payer. When spending this output, the owner signs the transaction and provides the raw public key so that verifiers (Bitcoin nodes) may rehash it and compare the hash against the output script being spent.
1  OP_DUP OP_HASH160 <hash> OP_EQUALVERIFY OP_CHECKSIG 
_{The classic P2PKH lockingscript.}
In P2SH and P2WSH, the address instead is the hash of a Bitcoin locking script which itself almost always contains at least one ECDSA pubkey, whose signature is required for spending. For the purposes of assessing postquantum security, scripthash type outputs have effectively the same properties as keyhash type outputs, with the exception that P2WSH outputs are encoded as SHA256 hashes whereas all others are encoded as RMD160 hashes.
1  OP_HASH160 <hash> OP_EQUAL 
_{The classic P2SH lockingscript.}
These four types of addresses currently protect the bulk of the mined and circulating Bitcoin supply.
The threat of a quantum adversary (QA) is in its ability to invert public keys into private keys. If a keyhash or scripthash address has received but not spent any of its coins, then the preimage of that hash (the key or the script) hasn’t been revealed yet. Barring outofband exposure (e.g. via BIP32 xpubs leaked to servers or peers), the QA generally won’t be able to attack such addresses practically.
This protection ends the moment the owner of the key/scripthash address tries to spend any of their coins. To validate a transaction spending a payto*hash output, the Bitcoin network peers must be given the key/script preimage. A quantum adversary could easily monitor these transactions and see that preimage, which always contains a public key the QA can invert. After inverting, the QA can try to doublespend the coins with a new higherfee transaction.
Gracefully, the QA will have a limited time in which to mount this attack. A typical Bitcoin TX spends only 5 to 60 minutes of its public existence in the mempool before it is mined, at which point the coins will have moved permanently to a new address. If that new address is protected by a hash whose preimage the QA does not know, then the coins will be out of reach for the QA.
However, a significant fraction of keyhash and scripthash addresses are being reused on mainnet today. A reused address is one which receives one or more UTXOs, spends them, and having revealed their public key or spendingscript, is still being used to custody additional Bitcoin UTXOs. Some estimate the amount of bitcoin held on such reused addresses was at least 5 million BTC as recently as 2019. A quantum adversary has much more time to compute the public keys exposed by these addresses. Time is on the side of the QA here; The burden of action is squarely on the shoulders of the owner to move their coins to a fresh unused address.
There is also the possibility of a large mining pool becoming a quantum adversary. Such a pool could delay mining certain transactions intentionally, to give themselves more time to crack a newly discovered public key.
Summary
P2PKH/P2SH/P2WPKH/P2WSH output script types can be reasonably secure against a QA if used properly, provided the QA needs a decent amount of processing time (more than an hour) to invert a secp256k1 public key.
The problem is that proper usage is hard. Ava Chow describes the numerous pitfalls which plague keyhashing as a countermeasure against a quantum adversary.
P2TR Outputs
In P2TR addresses, an internal public key
When spending, the bearer can either authenticate directly by signing as the output pubkey
The critical distinction between P2TR and the legacy payto*hash output script types is that taproot encodes a secp256k1 point directly in the output script. This means a quantum adversary (QA) can invert any P2TR output pubkey
This is not a new observation, there has been much discourse and controversy surrounding this property of the taproot upgrade.
 https://freicoin.substack.com/p/whyimagainsttaproot
 https://lists.linuxfoundation.org/pipermail/bitcoindev/2021March/018641.html
 https://bitcoinops.org/en/newsletters/2021/03/24/#discussionofquantumcomputerattacksontaproot
Summary
Against a quantum adversary, P2TR addresses are comparable in security to an alreadyreused keyhash address. The QA has unlimited time to invert the output pubkey and can start attacking any P2TR output from the moment they learn of its output public key
Note on Multisig
P2SH or P2WSH addresses which use OP_CHECKMULTISIG
cause a linear increase in the processing time needed for a QA to fully compromise the address. For an
This slowdown will probably be offset by parallelprocessing across multiple quantum processors, or with parallelized quantum algorithms which invert multiple public keys at once.
P2TR multisig addresses which use key aggregation do not have this property, because the taproot output pubkey
Note on BIP32
Most consumer wallets derive their addresses using BIP32 hierarchicaldeterministic (HD) wallet schemes. This allows a single seed to derive basically unlimited secret keys and corresponding public addresses for any script type. Wallets will sometimes share their extended public keys to avoid the need to communicate many individual child addresses.
To a quantum adversary, a BIP32 extended public key (xpub) is equivalent to its counterpart extended private key (xpriv) given enough time to invert the xpub. Once inverted, the QA can quickly derive all child addresses, and can thereafter monitor the blockchain to steal any funds paid to them.
To comply with BIP44 standards, most wallets derive one xpub/xpriv pair at specific BIP32 paths for each Bitcoin address type.
m/44'/0'/n'
for P2PKHm/49'/0'/n'
for P2SHwrapped P2WPKHm/84'/0'/n'
for native P2WPKHm/86'/0'/n'
for P2TR
Each layer of derivation in these key paths after the master key (m
) is hardened, meaning that deriving that child key involves hashing the parent secret key.
Remember QAs cannot invert a hash function as efficiently as they invert elliptic curve public keys. This means that the BIP32 master key m
, as well as the xprivs at any previously unused key path, are generally safe from the eyes of the QA provided the wallet has not exposed the BIP32 master public key. We will make use of this property in some of the options we discuss later.
QuantumSafe Signatures
The critical question is: What cryptographic mechanism replaces elliptic curve digital signatures?
Whatever mechanism replaces EC signatures must be asymmetric, allowing a user to give payment instructions to a prospective sender, without surrendering control of their money to the sender. This way the receiver can claim that payment later without revealing their signing credentials to anybody (like one would with a password to a bank website). This rules out symmetric cryptographic schemes, such as HMAC, simple hashing, or symmetric encryption algorithms like AES or ChaCha.
We have numerous quantitative metrics by which to judge a replacement algorithm:
 Public key size
 Signature size
 Secret key size
 Key generation time
 Signature computation time
 Signature verification time
We also have qualitative statements we can make about a signing algorithm:
 Statefulness: Does a signer need to maintain state between each signature?
 Reusability: Can a signer reuse their secret key to sign multiple messages?
Today we’re going to explore one genre of signing algorithms which is almost certainly the safest and most conservative candidate, but which comes with some big practical issues: Hashbased signatures, or HBS for short.
Hashbased signature schemes are constructed from a simple oneway cryptographic hash function like SHA256. Secret keys are usually vectors of preimages. Public keys are usually hashes, or vectors of hashes. Signatures are usually vectors of preimages, paired with auxiliary data needed to verify the preimages correspond to a specific static public key. Unlike other candidates for postquantum cryptography, hashbased signatures do not rely on new (possibly flawed) cryptographic assumptions  This is what makes them the conservative option.
I’ll now give a detailed description of several wellknown hashbased signature algorithms, in increasing order of complexity. If I lose you in some of the math, don’t worry  Understanding the internals of the HBS schemes is not critical to understanding how they can be applied to Bitcoin.
Skip through to the final analysis section if you don’t care about the technical details of HBS schemes.
Before we begin, some notation:
Notation  Meaning 

The set of all possible bit strings of length 

Uniform random sampling of an element 
Let
I began studying these hashbased signing protocols only a few weeks ago. Do not take my technical descriptions below as precise and safe for realworld use, because I have probably made typos or omitted stuff. The purpose of these descriptions is to illustrate and convey the essence of the algorithms, not to provide any concrete implementation instructions.
Roll your own crypto at your own peril.
If you are an expert in hashbased signatures and have noticed a typo, please email me or open a pull request to fix it.
Let’s start with the simplest and earliestknown example of an HBS scheme: Lamport Signatures.
Lamport Signatures
We want to sign a single bit of information  0 or 1  using our hash function
We generate two random preimages of
The tuple
Our public key is the tuple
We may generalize this approach to sign message strings of arbitrary bit length
Each
Our public key is made of hashes of every preimage.
To produce a signature
To verify, simply check that the hashed preimages match the public key for every bit
Properties
Lamport Signatures are a onetime signature (OTS) protocol  once the signer reveals a signature for a given public key, they can never use the same signing key again for a different message. If they do, the signer gives observers the ability to forge signatures on new messages they never consented to sign.
For instance, if
Signatures have bit length
Signing is simple, as it consists only of revealing secrets. Verification requires
Modifications
We can modify lamport signatures to improve the amount of space consumed by keys and signatures at the cost of some computation time.
Deterministic keygen: Instead of randomly sampling our secret key preimages, we can derive them from a root secret
This way we only need to store a single 256bit secret preimage for each Lamport OTS key, instead of
Compact public keys: We can reduce the size of public keys from
However, we must now adjust our signature algorithm to supply not only the
Signatures double in size to
Verifiers can verify
Comparisons
The following table shows some concrete examples of time/space tradeoffs for Lamport signatures. In these examples, I’ll set
Algorithm  Signature size  Public key size  Secret key size 

Vanilla Lamport  
Compact Lamport 
Below I note the time complexity of Lamport signatures in terms of the number of invocations of the hash function
Algorithm  Keygen time  Signing time  Verification time 

Vanilla Lamport  
Compact Lamport 
Viability for Bitcoin
I expect the Compact Lamport signature approach would be the most practical flavor of Lamport Signatures, as public keys would be the same size or possibly smaller than a P2TR pubkey is today.
However, even the most spaceefficient Lamport signatures with the lowest viable security levels (
There’s also the matter of key reuse. Lamport signatures are a onetime signature scheme. If a Bitcoin user spends from a hypothetical “paytolamportpublickey” address, they’ll never be able to spend from that address again without giving observers some power to forge signatures.
Power users would not be affected greatly, as the bestpractice touted by most experienced Bitcoiners is to use addresses only once, for a single receive/spend cycle. Yet, as we’ve seen earlier, a huge fraction of bitcoiners by volume have either never heard this advice, or have disregarded it. It will be difficult to convey to these users that address reuse with Lamport signatures will be more than just a privacy nono  It could seriously compromise their security. This would make life especially difficult for coldstorage hardware signing devices, which rely on a semitrusted host machine to prompt them with transactions to sign.
Lamport signatures are stateful, in that a signer should know if he has used his private key to sign a message before to know whether signing again could be dangerous.
Lamport signatures are not backwards compatible with Bitcoin’s consensus protocol as it exists today, although an outlandish scheme has been proposed by Ethan Heilman which make use of OP_SIZE
to Lamportsign the size of an ECDSA signature. Whether this approach is secure is still up for debate. But even with such creative invention, the size of such a signature would prohibit its usage in P2WSH addresses. At least with current knowledge, a softfork would be needed to add Lamport signature support.
Even after such a soft fork, existing addresses with exposed public keys would still be vulnerable to a quantum adversary. Users would need to actively migrate coins to a hypothetical paytolamportpublickey address format.
Winternitz OneTime Signatures (WOTS)
Winternitz signatures rely on a chain of hashes starting from a set of secret preimages. By revealing certain intermediate hashes in that chain, the signer can sign a specific message.
In comparison to the Lamport scheme, WOTS shoulders a higher computational burden in exchange for much shorter signatures. Let’s see how they work.
First, let’s reestablish some parameters:
 Let
be the bitlength of the message we want to sign.  Let
be the “Winternitz parameter” (used for time/space tradeoffs).  Let
be the bitgroup width into which we parse the message.  Let
be the length of the message in digits of base .  Let
be the checksum length in digits of base .  Let
be the overall length of the message plus the checksum in digits of base .
As WOTS relies on hashchains, we need a hashchaining function
So for instance,
Now we’re ready to generate our keys. We start by sampling
To compute the Winternitz public key
To sign a message
We compute a checksum
Because
We append this checksum array
To sign the checksummedmessage
A verifier given the plain message
If this holds for all
Properties
Security. Note the special role played by the checksum. Without it, revealing one set of intermediate hashes should allow an observer to forge signatures on any message in a “higher” position in the hash chain.
For instance, consider the following diagramed example.
If we don’t add a checksum to the twodigit message
Because of the checksum construction, increasing any message digit
Size. Signatures, public keys, and secret keys all have bit length
In case that equation seems unintuitive to you, you’re not alone. I plotted the relationship between the time/space tradeoff parameter
Higher values of
Approaching anywhere near that limit would be wildly impractical though, because by increasing
Runtime. Given a secret key
Public key generation uses the same hashchaining procedure as signing/verifying. To sign or verify a signature, we must compute at worst
To avoid this exponential blowup in computation time, most realworld WOTS instantiations keep
_{Xaxis is , Yaxis is the number of iterations of needed to generate a public key.}
For reference, my weedy little computer can generate a WOTS public key with
Curiously, due to the zerosum nature of the hashchain signature construction, signers and verifiers who are able to select the message they’re signing can also influence the amount of work they and their counterparty must perform. By selecting a message digit
Modifications
Compact public keys: WOTS lends itself well to compacting public keys via hashing. A Winternitz signature gives the verifier everything they need to reconstruct the signer’s public key
This decreases the public key size from
Deterministic keygen: Like with Lamport signatures, WOTS secret keys can be generated from a seed with only
Smaller and more secure signatures: To improve performance and security, one should consider using WOTS+, a variant of WOTS which adjusts the hashchain construction to XOR each of the intermediary hashes in every hash chain with a randomization vector. This odd choice allows the security proof to reduce forgeries to second preimage extraction: If someone can forge a WOTS+ signature, they can also break the secondpreimage resistance of
This means we can get away with using WOTS+ with smaller, faster hash functions which have broken collision resistance but are still believed to be secondpreimage resistant, as long as one can accept the lower security level implied by their shorter output. Or WOTS+ can be instantiated with larger hash functions, and for only a modest increase in signature size and verification complexity, we gain the added security of weaker assumptions.
WOTS+ relies on a set of
Instead of computing the intermediate values of the hashchains as
For instance,
WOTS+ appends the tuple
The compact WOTS+ public key
More efficient signatures using bruteforce compression: This paper suggests modifying the WOTS signing algorithm so that the signer repeatedly hashes the input message
This allows the signer to omit the checksum portion of the WOTS signature, because the checksum is verified to always work out to a fixed static value. Messages without this fixed checksum are not valid, and so the checksum itself does not need to be signed. This approach is called “WOTS with Compression” (WOTS+C).
The effect of this compression is to reduce the overall runtime of the scheme on average across keygen, verification, and signing, while also reducing signature size by removing the
The authors of WOTS+C even propose ways for the signer to further reduce the size of their signature by removing additional chains from their signature, at the cost of additional work to find an appropriate message salt.
Comparisons
The following table shows some concrete examples of time/space tradeoffs for various kinds of Winternitz signatures. In these examples, I’ll set
Algorithm  Signature size  Public key size  Secret key size 

Vanilla WOTS 

Compact WOTS 

Compact WOTS 

Compact WOTS 

Compact WOTS 

…  
Vanilla WOTS+ 

Compact WOTS+ 

Compact WOTS+ 

Compact WOTS+ 

Compact WOTS+ 

…  
Compact WOTS+C 