Quantum-safe Bitcoin transactions proposed without fork, using hash-based signatures

A proposal from StarkWare researcher Avihu Mordechai Levy outlines a way to make Bitcoin transactions resistant to future quantum attacks without changing the network’s core protocol. The design is intended to work within Bitcoin’s existing scripting rules, avoiding a soft fork or other upgrade.

How the proposal aims to address quantum risk

Levy’s paper describes a “Quantum-Safe Bitcoin” (QSB) transaction scheme designed to remain secure even if quantum computers break the elliptic-curve cryptography used in today’s Bitcoin signatures. The approach replaces elliptic-curve assumptions with hash-based cryptography and Lamport signatures, which are considered resistant to quantum attacks.

Levy argues that because Lamport signatures are post-quantum secure and sign a cryptographically strong identifier of the transaction, altering a transaction would require producing a new Lamport signature that an attacker cannot forge, even with quantum computing capabilities.

Core mechanism: a pre-broadcast cryptographic puzzle

At the center of QSB 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.

Unlike Bitcoin mining, where computation is performed to earn block rewards, the QSB computation occurs off-chain before the transaction reaches the network. Users perform the work 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.

Fitting within Bitcoin’s scripting limits

The scheme is designed to operate within Bitcoin’s scripting constraints of 201 opcodes and 10,000 bytes. The paper notes these limits are highly restrictive because every opcode counts toward the total, even if it appears in an unused script branch.

To meet those constraints, 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.

Scalability limits and operational trade-offs

Levy describes QSB as a “last-resort” measure rather than a scalable fix. The paper says neither the off-chain computational cost nor the on-chain transaction size would scale to Bitcoin’s target throughput or to the needs of most users.

Transaction creation is also more complex than standard Bitcoin usage and may be considered non-standard under current relay policies. As a result, transactions could face propagation issues and may need to be submitted directly to mining pools rather than broadcast through the public mempool.

Security considerations

The proposal is designed to avoid attacks based on Shor’s algorithm, which threatens elliptic-curve signatures. However, Levy notes that Grover’s algorithm could still provide a quadratic speedup for quantum attackers.

Levy also emphasizes that, if the quantum threat is real, Bitcoin still needs ongoing research and implementation of the best possible solution—ideally one that is maximally efficient and user-friendly through protocol-level changes.

Context within broader quantum-resistant proposals

Levy’s paper adds to a set of proposals aimed at transitioning Bitcoin to quantum-resistant cryptography, including BIP-360. BIP-360 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, with a stated 2029 deadline to transition their systems to post-quantum cryptography.