Key Takeaways/TLDR:
- Quantum computing does not doom Bitcoin. It’s a real threat only if the Bitcoin community doesn’t take proactive measures to protect against it.
- Quantum resistance is within reach with proven, existing methods such as STARKs and post-quantum cryptography that can protect Bitcoin.
- Early Bitcoin addresses and exposed public keys are the most vulnerable and should be prioritized when migrating to quantum-secure options as the sector advances.
- Bitcoin and the Bitcoin community (including its developers and users) can lead the rest of the crypto market in terms of how to perceive and address QC fears and threats factually.
For years, Bitcoiners have faced a tsunami of skepticism, each posing the idea that a new critical flaw could soon threaten the network and lead to the collapse of user safety. Today, one of the most discussed threats facing Bitcoin is quantum computing (QC), which purportedly threatens the network’s cryptographic security measures and is even an existential threat.
The reality is more nuanced. QC does pose a serious cryptographic challenge to blockchain networks like Bitcoin, but it is not an existential threat to Bitcoin — at least, not if we take precautionary measures.
Eli is a co-founder and CEO of StarkWare. Earning his PhD in Theoretical Computer Science from Hebrew University in 2001, he has since focused on cryptographic and zero-knowledge proofs of computational integrity. He co-invented the STARK, FRI, and Zerocash protocols and was a Founding Scientist of the Zcash Company. He has held research positions at Princeton’s IAS, Harvard, and MIT, and was a CS professor at Technion before co-founding StarkWare.
Bitcoiners need to take the lead in this conversation; otherwise, critics will frame the debate for us, turning quantum risk into yet another cudgel to bash against everything crypto has fought to become. We should not simply react to noise from alarmists; we should take proactive measures to demonstrate that solutions exist and that Bitcoin’s long-term structures must be prepared to rise to the challenge of QC threats.
I spent decades working on cryptographic proofs before being propelled into crypto at a Bitcoin conference in 2013. My experience has given me an acute sense of the challenge we face as well as an encouraging view of what cryptography can do to ameliorate it.
In this article and its sequel, I will be giving a sense of how those insisting that QC will render cryptography and/or blockchain obsolete are presenting a gross, misleading oversimplification–a view that is normally based on populist materials. Yes, cryptography is facing a new challenge, but we must remember that cryptography is not a static field–it adapts and evolves. It can survive and even excel in the face of QC threats.
Quantum-resistant cryptography is needed: Now
Bitcoin’s cryptography is built on elliptic curve cryptography (ECC), which means that wallets using traditional elliptic curve digital signature algorithm (ECDSA)-based signatures will remain susceptible to quantum attacks once sufficiently powerful QC systems exist. Since Bitcoin wallet private keys are secured through ECDSA, public wallets secured this way are vulnerable to private key extraction.
The potential impact is massive, particularly for addresses that have exposed their public keys–an act completed the day a user signs their first transaction. Early Bitcoin addresses (circa 2009-2010) used a “Pay to Public Key” format that exposed the full public key on the blockchain, making these older coins particularly at risk to QC threats.
Today, QC is progressing at a faster rate than at any previous point in history, and the Bitcoin community must tackle it proactively to effectively protect against it and even incorporate its technological improvements.
As the narrative of these QC threats grows, large entities such as Google, Microsoft, and Amazon Web Services (AWS) have announced the release of their own respective QC chips to support security efforts surrounding QC. Amazon’s “Ocelot” QC chip can reportedly reduce the costs of implementing quantum error correction by up to 90%. Chinese researchers recently created a highly efficient single-photon source (71.2% efficiency) that surpasses the two-thirds threshold, a key milestone for improving error correction in photonic QC. In layman’s terms, these scientists built a light source that can spit out single photons more than 70% of the time—an important development that could enhance error correction in quantum computers that use light, bringing us a step closer to more reliable and powerful quantum machines.
What is the real threat?
Let’s clarify what alarms us about quantum computing. Several algorithms already exist that could wreak havoc on some of the cryptography we depend upon today. However, today, there are no quantum computers powerful enough to run those algorithms..
An analogy: Nuclear fission was invented years before the first atomic bomb was built. These algorithms are the equivalent of nuclear fission–the theoretical potential for epoch-changing innovation. But neither its “good” use (generating electricity) nor its destructive use (nuclear bomb) were possible until a few years afterwards. The theoreticals for quantum computing exist now, but neither its positives for human knowledge nor its negatives for breaking some cryptography have been unleashed yet.
Cryptographers have long been raising concerns about the dawn of quantum computing. They have noted that trying to crack codes is as old as the very existence of codes themselves. Countermeasures to quantum computing started to be seriously discussed in the nineties. 1994 was a key year, when Shor’s Algorithm illustrated that RSA and ECC encryptions could eventually fall to QC attacks.
Shor’s and Grover’s algorithm
Developed by Peter Shor in 1994, this algorithm was intended to factor large integers and solve a mathematical problem, known as the Discrete Log Problem (DLP). Shor’s Algorithm can efficiently break certain public-key cryptography, including ECC-based schemes like Bitcoin.
This algorithm has given rise to widespread fear regarding the vulnerability of an estimated one million Bitcoin held by the cryptocurrency’s creator, Satoshi Nakamoto. Due to its exposed public key, Shor’s algorithm could, in theory, be used to derive Satoshi’s private keys and empty their wallets.
Unlike Shor’s algorithm, Lov Grover’s algorithm—proposed in 1996—doesn’t pose an immediate threat to asymmetric cryptography such as ECC. However, it does impact hash functions–including Bitcoin’s Proof-of-Work (PoW) consensus mechanism.
Asymmetric cryptography, otherwise known as public-key cryptography, is a collection of cryptographic systems that uses two different keys for encryption and decryption: a public key and a private key—ultimately, allowing two parties that have never met to communicate privately and securely.
On the other hand, symmetric cryptography uses the same key for both mechanisms. This means that no secure method is in place to share that key without opening the door to significant vulnerabilities. When it comes to QC, most prevailing public key (asymmetric) cryptographic systems are utterly breakable by it, while most prevailing symmetric systems stay relatively secure, up to a possible minor modification that doubles their size.
Bitcoin mining relies on the computational difficulty of solving SHA-256 puzzles, a symmetric cryptography (and QC-secure) problem. Grover’s algorithm, if implemented through powerful QC, could halve the effective security strength of SHA-256, but no more. This means a quantum miner could solve PoW computational puzzles faster, outperform traditional miners, and increase the risk of 51% attacks if quantum miners outpace non-QC miners.
Grover’s algorithm is more manageable than Shor’s attack on ECDSA and can be mitigated by increasing the SHA-256 size to SHA-512—effectively doubling the hash length and restoring the original level of security. It should also be mentioned that without the right protections in place, Grover’s algorithm can break SHA-256 ASICS, rendering them unusable–or at least reduce the security strength of SHA-256. In contrast, Shor’s algorithm renders asymmetric systems like RSA, ECDSA and Diffie-Hellman utterly broken, with no repair.
Quantum resistance in Layer 2’s
We shouldn’t be alarmed by quantum computing. Yet we shouldn’t bury our heads in the sand. There is no need for alarm as long as we prepare well.
We should be proactive in leading the narrative to secure Bitcoin. Otherwise, the critics will turn QC into another anti-crypto bludgeon. This means exploring practical solutions for Bitcoin. It means that all who are building on top of Bitcoin should use architecture that has a fast pathway to post-quantum security when it is needed.
Layer 2 (L2) solutions, rollups, sidechains, and bridges should not be architected with assumptions that will crumble in 20 years due to technological advancements.
If an L2 supports Bitcoin’s network but relies on cryptographic primitives that QC can break, then it is a short-term fix that comes with an expiry date that must be rethought. We need long-term thinking incorporated into every single layer.
It is for this reason that the zero-knowledge proof (ZKP) family of cryptographic solutions must be central to global efforts to scale Bitcoin, particularly the power of zkSTARKs. QC threats can be mitigated, moreover, by integrating quantum-resistant hash functions such as Stateless hash-based signatures (SPHINCS+) that are resistant to Shor QC attacks and use STARKs to establish scalable security measures.
STARKs, or to use the full name Scalable Transparent Arguments of Knowledge, require robust hash functions but don’t rely on number-theoretic assumptions that are vulnerable to quantum attacks. This means they can scale Bitcoin in the long term without requiring a redesign, as they are inherently capable of withstanding quantum attacks and offsetting QC risks in the future.
There is an elegant analogy to explain how STARKs differ from most cryptography you will know. Your passwords today are akin to needles hidden in a gigantic haystack. Somebody could theoretically find your password by trying huge combinations of numbers, but it’s akin to finding that needle in the haystack. A quantum computer is like a huge magnet that can instantly find that needle.
STARK cryptography is fundamentally different. Your password is no longer a magnetic needle in the haystack but a specific piece of hay in the massive haystack. No magnet will help you, and no quantum computer will find it. Even the modest powerful magnet in the world won’t find that hay and even the most powerful quantum computer won’t crack zkSTARK Proofs.
If a ZK system that offers a better solution than STARKs comes along tomorrow, my message remains the same: Bitcoiners should embrace the very best that ZK cryptography has to take the lead and face the challenge of QC. Bitcoin is a cryptographic system that must endure and to do so we should build for the next century—not just short-term gains and the next bull run.
In part two of this two-part series, I’ll explain actionable measures Bitcoiners can take to counteract the fears of QC, where the vulnerabilities truly lie, and how ZKPs can overcome this misunderstood technological doomsday.
