Quantum Threat and Bitcoin's Vulnerability
Bitcoin's standard transactions rely on ECDSA signatures over the secp256k1 curve. A sufficiently powerful quantum computer running Shor's algorithm could theoretically break this system by solving discrete logarithms, allowing attackers to forge signatures and spend funds. Avihu Levy of StarkWare published a paper on April 9 titled 'Quantum-Safe Bitcoin Transactions Without Softforks,' introducing the Quantum Safe Bitcoin (QSB) scheme. The proposal aims to protect transactions from quantum threats while remaining compatible with the existing Bitcoin protocol, avoiding any need for consensus changes or hard forks.
How QSB Works: Hash-to-Signature Puzzles
QSB replaces reliance on elliptic curve security with hash-based assumptions. Instead of trusting ECDSA alone, the scheme uses it as a verification mechanism while shifting security to hash pre-image resistance. This approach draws from earlier work known as Binohash, which embeds one-time signature schemes into Bitcoin Script. At the core of QSB is a 'hash-to-signature' puzzle: the system hashes a transaction-derived public key using RIPEMD-160 and treats the output as a candidate ECDSA signature. Only a small fraction of random hashes meet the strict formatting rules required for valid signatures, creating a proof-of-work condition. The paper estimates the probability of success at about one in ~70.4 trillion attempts.
Because the puzzle depends on hash properties rather than elliptic curve hardness, it remains resistant to Shor's algorithm. A quantum attacker would gain only a quadratic speedup from Grover's algorithm, leaving meaningful security margins. The paper estimates about 118-bit second pre-image resistance under a Shor threat model.
Transaction Process and Engineering Constraints
The transaction process unfolds in three stages:
- Pinning phase: Searches for transaction parameters that produce a valid hash-to-signature output, binding the transaction to a fixed structure.
- Two digest rounds: Select subsets of embedded signatures to generate additional proofs tied to the transaction hash.
- Assembly: The transaction is assembled with all required preimages and verification data.
The construction works within Bitcoin's existing scripting limits, including a cap of 201 opcodes and a maximum script size of 10,000 bytes. It uses legacy script structures and avoids any need for consensus changes or soft forks. However, QSB transactions exceed standard relay policy limits, meaning they would not propagate across the network under default settings. Instead, they require direct submission to miners through services such as Slipstream. The scripts also consume significant space and computational resources.
Cost and Current Status
Despite these constraints, generating a valid transaction appears economically feasible. The paper estimates total compute expenses between $75 and $150 using cloud GPUs, with the workload scaling across parallel hardware. Early testing reports successful puzzle solutions after several hours using multiple GPUs. However, the project remains incomplete. While the paper and script generation tools are finished, parts of the pipeline, including full transaction assembly and broadcast, have not been demonstrated on-chain.
Implications for Bitcoin's Quantum Future
QSB adds to a growing body of research exploring how Bitcoin could adapt to a future with quantum computing. By avoiding protocol changes, QSB presents one path that relies on existing rules rather than consensus upgrades. This direction may shape further debate on long-term network security, especially as quantum computing hardware continues to advance. While QSB is not production-ready, it demonstrates that quantum-safe transactions might be achievable without a contentious hard fork, a possibility that could influence future development priorities.