StarkWare researcher proposes quantum-safe Bitcoin transactions

Avihu Mordechai Levy, a researcher at StarkWare, proposes a way to make individual Bitcoin transactions resistant to future quantum attacks without changing the network protocol. The design, called QSB (Quantum-Safe Bitcoin), replaces elliptic-curve signatures with hash-based puzzles and Lamport signatures and fits within Bitcoin’s existing scripting rules.

Under QSB, the transaction creator solves a cryptographic puzzle off-chain and includes the puzzle solution and a Lamport signature in the transaction. The Lamport signature signs a strong identifier of the final transaction, so any change to the transaction would require a new signature that an attacker could not forge if Shor’s algorithm breaks elliptic-curve cryptography.

Levy’s paper estimates a valid puzzle solution would require about 70 trillion attempts. He writes the computation can run on commodity hardware such as GPUs and could cost a few hundred dollars per solved puzzle. Because the work is done before broadcast, miners and nodes would not need protocol changes to accept QSB transactions.

The proposal fits QSB within Bitcoin’s current limits of 201 opcodes and 10,000 bytes per script by layering Lamport signatures and hash puzzles in a compact structure. The design adds a “transaction pinning” mechanism that forces anyone attempting to alter a broadcast transaction to re-solve the puzzle.

The paper describes QSB as a temporary, last-resort option. Levy notes the approach increases transaction size and requires substantial off-chain work, so it would not scale to routine use. Transaction creation is more complex than standard wallet operations, and under current relay rules QSB scripts may be treated as non-standard and face propagation challenges.

The proposal avoids attacks that rely on Shor’s algorithm, but the paper cautions that Grover’s algorithm could still speed up brute-force searches quadratically. “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. He adds continued research is needed for efficient, user-friendly protocol-level post-quantum solutions.

QSB joins other technical ideas for moving Bitcoin toward post-quantum cryptography, including BIP-360, which defines a Pay-to-Merkle-Root address format to support quantum-safe signatures. Several large technology firms have set internal deadlines to migrate systems to post-quantum algorithms, with some timelines targeting completion by the end of the decade.

Levy’s paper concludes that until an efficient protocol-level upgrade is developed and adopted, ad hoc schemes like QSB could provide a stopgap for users and services with high security needs.