Shor's Algorithm, Meet Your Match: StarkWare Proposes Fork-Free Quantum Shield for Bitcoin

Quantum computers haven't broken Bitcoin yet—but somewhere, a physicist in a lab coat is probably debugging a cryogenic processor and muttering about elliptic curves. Now, a proposal from StarkWare researcher Avihu Mordechai Levy suggests Bitcoin transactions could be made resistant to future quantum attacks without touching the network's sacred core protocol. In a recent paper, Levy describes a "Quantum-Safe Bitcoin" transaction scheme designed to remain secure even if quantum computers smash through today's elliptic-curve cryptography like a sledgehammer through wet tissue. The method works within Bitcoin's existing scripting rules and would not require a soft fork or other network upgrade—because apparently, getting the Bitcoin protocol to agree on anything is harder than solving the quantum problem itself.

"We present QSB, a Quantum Safe Bitcoin transaction scheme that requires no changes to the Bitcoin protocol and remains secure even in the presence of Shor's algorithm," Levy wrote. Shor's algorithm, for the uninitiated, is the quantum boogeyman that could theoretically factor large numbers and break the cryptography protecting every Bitcoin wallet on the planet. It's been lurking in academic papers for years like a plot twist everyone saw coming.

The proposal replaces elliptic-curve signatures with hash-based cryptography and Lamport signatures—an early signature scheme from 1979 that your cryptography professor probably mentioned once before moving to something more exciting. Lamport signatures are considered resistant to quantum attacks, probably because they're so old that even quantum computers need a moment to recognize them. "Since Lamport signatures are post-quantum secure, and they sign a cryptographically strong identifier of the transaction, it is not possible to modify the transaction without producing a new Lamport signature—which the attacker cannot forge, even with quantum computing capabilities," Levy wrote. Basically, it's like changing your password to something quantum computers can't even read.

At the center of the design is a cryptographic puzzle that must be solved before a transaction is broadcast. The paper estimates that finding a valid solution would require about 70 trillion attempts—because why solve one hard problem when you can make users solve 70 trillion of them? Unlike Bitcoin mining, the computation happens before the transaction reaches the network. Users perform the work off-chain and submit a transaction that already includes proof that the puzzle was solved. Levy estimates the puzzle could be solved using commodity hardware such as GPUs at a cost of a few hundred dollars per transaction. That's right, folks: pre-mining your transaction for the low, low price of a used Honda Civic.

The scheme is designed to operate within Bitcoin's scripting limits of 201 opcodes and 10,000 bytes. The paper notes these limits are extremely restrictive because every opcode counts toward the total, even if it appears in an unused script branch—think of it like being charged for every word in a manuscript you never wrote. To fit within those limits, the system combines Lamport signatures with hash-based puzzles in a layered transaction structure. It also introduces "transaction pinning," which requires anyone attempting to modify the transaction to solve the puzzle again. That's not a feature; it's a hostage situation.

Levy describes the system as a "last-resort" measure rather than a scalable fix. The paper says both the off-chain computational cost and the on-chain transaction size would not scale to Bitcoin's target throughput or the needs of most users. Translation: this thing works, but using it daily would be like driving a Formula 1 car to the grocery store—technically possible, technically overkill, and you're going to cause a scene. Transaction creation is also more complex than standard Bitcoin usage, and may be considered non-standard under current relay policies, meaning they could face propagation issues and may need to be submitted directly to mining pools rather than broadcast through the public mempool. Good luck explaining that one to your wallet provider.

The proposal also carries security trade-offs. While it avoids attacks based on Shor's algorithm that threaten elliptic-curve signatures, Grover's algorithm could still provide a quadratic speedup for quantum attackers. It's like installing a titanium door but leaving the windows open—sure, the quantum burglar has to work harder, but they're still getting in eventually. "To the extent that the quantum threat is believed to be real, it remains necessary to continue the ongoing effort to research and implement the best possible solution for Bitcoin–one that is maximally efficient, user-friendly, and answers Bitcoin's needs, through protocol-level changes," Levy wrote. In other words, this is a band-aid, not a cure.

Levy's paper joins several proposals that have emerged outlining how Bitcoin could transition to quantum-resistant cryptography, including BIP-360, which introduces a Pay-to-Merkle-Root address format designed to support quantum-safe signatures. While the quantum threat to Bitcoin remains theoretical, companies including Google and Cloudflare are already preparing for it, setting a 2029 deadline to transition their systems to post-quantum. So by 2029, your coffee shop's TLS certificates might be more quantum-resistant than your Bitcoin. Sleep soundly tonight.