Quantum Computing and Bitcoin: Understanding the Risks, the Trade-offs, and the Path Forward

Written by Sulaiman Aminu Barkindo

For the past few weeks, I’ve been trying to understand the quantum computer risk and the options Bitcoin has at a technical level. I’ve gone through various sources, from reading post-quantum cryptography articles to following the bitcoin-dev mailing list and Delving Bitcoin.

This article is my way of stating what I’ve learned, where we are right now, what options exist, and why finding the right path forward isn’t as simple as it might first appear.

How Bitcoin's Cryptography Works and Where It Breaks

To understand the struggle for a solution, understanding the problem is very important. Bitcoin's cryptographic foundation has held for over 17 years. The Elliptic Curve Discrete Logarithm Problem (ECDLP) which is the security base for Elliptic Curve Digital Signature Algorithm (ECDSA) that Bitcoin originally uses, and the Schnorr signatures introduced in Taproot, are computationally infeasible to break with classical hardware — the best known attack, called square-root attack, would require computational effort on the order of 2^n/2 operations, which in the case of Bitcoin is 2^256/2 lying far beyond the reach of any general or special (not quantum) purpose computer that could realistically be built. Math is not the problem.

The problem is what happens when the math stops being the hard part.

Bitcoin uses ECDSA, which, unlike RSA that depends on Integer factorisation, ECDSA depends on ECDLP. Even more devastating, quantum computers were estimated to be able to break ECDSA with the same level of security as RSA faster, as it requires fewer qubits.

To mathematically represent the problem, say we have a public key P and a known generator point G on the curve:

With k being the private key scalar, recovering k from P and G is computationally infeasible. Because, for elliptic curve points, there is no division like there is in normal arithmetic. 

The best known attack on ECDLP known as square-root attack, with algorithms such as Pollard's rho and Baby-step Giant-step (BSGS) algorithms that both run in O(√n) complexity, which for Bitcoin's secp256k1 curve means roughly 2√256 which is 2^256/2 operations. Practically infeasible on any current hardware.

However, with Shor's algorithm, ECDLP can be solved in polynomial time. Given a public key P, a quantum computer recovers a private key k directly.

The threat does not target both symmetric and asymmetric crypto algorithms equally. In terms of symmetric algorithms like AES, the quantum threat halves the difficulty of breaking the algorithm, so what needs to be done as a countermeasure is to just increase the key size. For example, AES key size >= 256 should be what is used going forward. 

Looking at asymmetric algorithms, which fall broadly into three categories: integer factorization as used in RSA, the discrete logarithm problem (DLP) over finite fields, and the elliptic curve discrete logarithm problem (ECDLP) which is itself a special case of DLP over elliptic curve groups. Quantum computers' effect is devastating on these, and we need completely different algorithms that are resistant to quantum computing threats, which are called post-quantum cryptography algorithms.

The threat is not unique to ECDLP, For example, RSA, which secures most banking systems and the internet at large, relies on the integer factorization problem. Say n is a large public modulus, computed by multiplying two large primes p and q. 

It is easy to compute but computationally infeasible to reverse. In other words, recovering p and q from n is the hard problem. That is, n is publicly available for all to see, but factoring it to get the two primes that were multiplied to get n is computationally infeasible. The best classical algorithm, the General Number Field Sieve, runs in sub-exponential time but is practically infeasible for very large n.

What if factoring is no longer hard? Once an attacker recovers p and q, Euler's totient (ϕ) can be calculated using the formula:

And from the parameters ϕ(n) and the public exponent e, the decryption key d is easily recovered using modular inverse with the help of Extended Euclidean Algorithm (EEA):

This means, once the integer factorization is solved, the security of RSA collapses.

Interesting to note throughout this discussion is that the method for proving the security of cryptographic schemes is by making them public and having enough smart researchers, cryptanalysts, and organizations to try and fail at breaking them many times and for a long time. Because the assumptions are made public and well-defined, it can be monitored. The moment a meaningful break is discovered and disclosed, what has broken will be known immediately and what needs replacing. So making it public is both a feature and foundation.

What Quantum Computers Do Differently

Unlike classical computers that work with bits (0 or 1), Quantum computers work with quantum bits (qubits), which are capable of representing information in 0, 1, or both at the same time through superposition. It uses interference that manipulates the probability amplitudes of quantum states (superpositions) to amplify correct solutions and cancel out incorrect ones.

This does not mean quantum computers are universally faster. It only means quantum computers are exceptionally faster at solving specific mathematical structures. But for most tasks you will want to use normal classical hardware, as quantum computers are like special-purpose computers that are really good, particularly at breaking mathematical functions underlying integer factorization and discrete logarithm problems.

Why the Threat is Real Before the Machine Exists

A Cryptographically Relevant Quantum Computer (CRQC) that can execute Shor's algorithm at scale does not exist today. Opinions as to the timeline for its existence are divided; some believe it may be available within a decade, others two decades. The point of agreement is that we are traveling at a pace towards its existence.

Bitcoin transactions are public, and a large amount of bitcoin is secured using P2PK with visible public keys on-chain. Also, even with other kinds of outputs that are behind a hash, p2pkh address reuse can make them vulnerable. Because when Bitcoin is spent, the public key is revealed, and if the same address is reused to receive Bitcoin, either through change or external output, the public key for that was known from the first spend, and the Bitcoin in those addresses will be vulnerable to attack. This means the public keys can be collected, stored, and broken once quantum capability arrives. This is also called harvest now, decrypt later.

Major work has been ongoing in regard to standardization and discussions around migration and choice of signature scheme. As most cryptography students know, most of the current cryptographic schemes were standardized by NIST and this threat of quantum computing is no different, as NIST has been working on standardizing post-quantum cryptographic schemes since 2016, and after almost a decade, in 2024, it finalized two signature schemes. One lattice-based published as FIPS 204 and the other hash-based published as FIPS 205. 

The Bitcoin development community is also now more alert about the quantum computing risk and what it will take to perform migration. It is rare to receive an alert from engagements and discussions among developers and cryptographers in Bitcoin forums such as the bitcoin-dev mailing list and devlingbitcoin that does not involve quantum. The engagements have moved from theoretical to active engineering. See bip360 and bip361.

However, Bitcoin has some specific needs, which makes the answer to which scheme Bitcoin should adopt more complicated than it first appears.

What Bitcoin Actually Needs From a Signature Scheme

For us to evaluate any post-quantum scheme, we need to list out the needs of Bitcoin from a signature scheme so that we can evaluate each against these needs. Apart from being mathematically sound, any post-quantum candidate to be adopted by Bitcoin should satisfy the following:

Signature Size

The size of a signature is very important in Bitcoin, as every signature lives on-chain. This means a significant increase in the size of signatures will affect the number of transactions that can be fit in a block; affecting the number of transactions in a block will affect the efficiency of transactions. Since you can only fit in a small number of transactions, then more transactions will have to wait for the block to be confirmed before they are picked next. Currently, this is, on average, after 10 minutes, which is already a bit slow.

With the block only fitting a smaller number of transactions than it currently does, block space will become more expensive as demand for it will be higher. which will affect usage of the blockchain by ordinary users.

Lastly, full nodes will also be affected by demanding more node storage, making it more difficult for ordinary users to run full nodes and be independent.

Signing and Verification Speed

Verification of every transaction in every block is being done by each full node. A significant decrease in speed will affect node performance and create centralization where only highly resourced nodes can do well. This will go against Bitcoin's security model.

In regard to signing speed, it matters a lot, especially for payment channels like in the Lightning Network, which require quick state updates. If the speed decreases, we will experience higher latency in a flow that was built to be almost real-time.

Security Assumptions and Cryptanalytic Maturity

Bitcoin has over a trillion-dollar market cap. Therefore, it makes absolute sense to be conservative in changing anything that, if done wrong, can affect the savings of people that believe in it. This is how changes have been happening in Bitcoin with careful review, well-understood demands, and clear constructions.

Therefore, it is of high importance to ensure the signature scheme being adopted is battle-hardened and has gone through rigorous public scrutiny, and cryptanalysts have had as much time as they need to try and break the scheme, as trust in cryptographic schemes is built through failed attacks over time.

NIST has selected two signature scheme finalists, which means they are credible. The process ran from 2016 to 2024 and went through rigorous public attacks. A lot of early submissions were broken during that process. But we should still be conservative, as Bitcoin, holding over a trillion dollars in value, should be handled carefully.

Constant-Time Implementation

Constant time implementation is a security measure to prevent timing attacks, which are one of the side channel attacks where a system is exploited by measuring how long it takes to perform operations on different inputs.

A constant-time implementation of a post-quantum signature scheme is important, as Bitcoin's signing infrastructure may operate in an adversarial environment, and if the duration of a signing operation leaks information about the private key or even a few bits of the private key, hence the full private key can be recovered through statistical analysis, then the signature scheme being mathematically sound may not be as useful as it should have been. Also nowadays compilers are very smart and silently undo constant-time codes.

The Evaluation Criteria

As we will see, none of the two NIST finalist signature schemes satisfies all six cleanly.

The Candidates: ML-DSA and SLH-DSA

With Bitcoin currently having signature sizes between 64 and 73 bytes and 32 bytes public keys, both NIST signature scheme finalists have some drawbacks compared to Bitcoin's current scheme. The question is which tradeoffs Bitcoin is willing to accept.

ML-DSA (Dilithium)

This is built based on Module Learning With Errors (MLWE) which is a lattice-based assumption considered to be more conservative than NTRU style lattices. It also has a nice feature (rejection sampling over integers), which makes it easier to write constant-time code that protects against side-channel attacks. But the rejection sampling over integers does not mean developers should not be careful in implementation, because the rejection process itself may end up leaking information.

While ML-DSA has nice implementation security, it has a significant drawback in terms of signature size. With approximately 2,420 bytes, it's roughly 38 times larger than a Schnorr signature. Therefore, integrating it as it is on Bitcoin would affect the network's throughput; transaction fees would go up, and hardware requirements for running a full node would increase significantly. This means it may require rethinking Bitcoin's scaling roadmap entirely. 

SLH-DSA (SPHINCS+)

This was standardized by NIST in case of an emergency where some mathematician suddenly identifies a weakness with a lattice-based signature scheme. In that scenario, SLH-DSA will serve as a fallback. It carries the highest cryptanalytic maturity because its security relies entirely on hash functions like SHA-256 or SHAKE, which are some of the oldest primitives in cryptography. Furthermore, due to it being essentially just a massive tree of hashes, achieving constant-time execution is straightforward as there are well-vetted libraries.

With all the nice features and being an old primitive, it's still catastrophic when it comes to signature size, as the SLH-DSA signatures are massive, ranging from approximately 8,000 bytes to over 49,000 bytes. This means a single signature at the small end may be 126 times larger than Schnorr, which shows this is practically incompatible to be used as it is with Bitcoin's current architecture.

Why Neither Candidate Fits Bitcoin as It Stands

When we look at the two finalists together, a clear (maybe fortunate in a way that will make us innovate some more better ways for Bitcoin) pattern shows for Bitcoin: one scheme offers reliable implementation security, and the other offers a very strong mathematical foundation, but they are both destructive to the block size of Bitcoin and other resource constraints we have mentioned.

This is not a failure in research by the cryptography community. It shows the cost that comes with quantum resistance. The mathematical structures used by these schemes produce more massive signatures than classical signature schemes. Bitcoin will need to engineer around that and not expect a direct replace-in scheme.

Where the Research Is Pointing

Hope is not lost as the Bitcoin developer community has been discussing how to use those signature schemes with small to no devastating effect on the Bitcoin network itself. Currently the most promising path seems to be the Zero-Knowledge Proofs (STARKs) to compress the data. A block's worth of post-quantum signatures could be aggregated by miners into a single compact proof. This way, full nodes will not experience a lot of impact, as they will not need to download thousands of multi-kilobyte signatures. Combining this approach with output types like P2MR and the hash-based accumulator Utreexo would enable verifying post-quantum signatures without significantly affecting the block space.

This means also the weight of these signatures might eventually be moved off-chain or into some cryptographic summaries and still preserve Bitcoin's decentralization.

Conclusion

Cryptographically Relevant Quantum Computers do not exist yet. However, there has been a lot of progress in research towards ensuring its existence, and with the harvest now a decrypt-later attack, it becomes important to start working towards approaches and proposals for migrating existing systems that depend on asymmetric cryptographic assumptions of ECDLP and integer factorization. Bitcoin's security depends on the ECDLP which makes it vulnerable to quantum computer attack. Therefore, the question is no longer whether the Bitcoin community should think about post-quantum migration but when and how the migration can happen. 

However, migration of Bitcoin to a post-quantum signature scheme is not straightforward due to Bitcoin's strict limitations on signature size and computation resources. While the two NIST finalists, ML-DSA and SLH-DSA offer resistance to quantum threats, their large size would significantly affect the network under current architecture. 

Current discussions show there is light at the end of the tunnel. With STARK-based aggregation, P2MR and careful protocol upgrades can help reduce the overhead of the post-quantum signature schemes without sacrificing decentralization. The conservative approach to upgrading Bitcoin that kept the network secure for over 17 years should still be observed in updating its cryptographic foundation deliberately, publicly, and before the threat arrives.

References

Shor, P.W. (1994). Algorithms for Quantum Computation: Discrete Logarithms and Factoring. 35th Annual Symposium on Foundations of Computer Science, IEEE. https://arxiv.org/abs/quant-ph/9508027

Brumley, D. & Boneh, D. (2005). Remote Timing Attacks are Practical. Computer Networks, 48(5). https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf

Jancar, J. et al. (2020). Minerva: The Curse of ECDSA Nonces. IACR Transactions on Cryptographic Hardware and Embedded Systems. https://eprint.iacr.org/2020/728

Moghimi, D. et al. (2020). TPM-FAIL: TPM Meets Timing and Lattice Attacks. USENIX Security 2020. https://eprint.iacr.org/2019/1275

NIST (2024). FIPS 204 — ML-DSA, FIPS 205 — SLH-DSA, FIPS 206 Draft — FN-DSA. https://csrc.nist.gov/projects/post-quantum-cryptography

Wuille, P. et al. (2020). BIP-340: Schnorr Signatures, BIP-341: Taproot. https://github.com/bitcoin/bips

BIP-360: Pay to Quantum Resistant Hash (2024), BIP-361: Quantum-Resistant Migration Plan (2025). https://github.com/bitcoin/bips

Osuntokun, O. (2026). Post-Quantum BIP-86 Recovery via zk-STARK Proof of BIP-32 Seed Knowledge. Bitcoin-Dev Mailing List, April 2026. https://groups.google.com/g/bitcoindev/c/Q06piCEJhkI/m/Ly9J23FlAwAJ

Chaincode Labs (2024). Bitcoin and Quantum Computing: Current Status and Future Directions. https://chaincode.com/bitcoin-post-quantum.pdf