Skip to content
Encryptorium

PQC

Quantum-safe Bitcoin transactions without a soft fork: what the QSB paper actually says

Andreas Renz · · 11 min read
PQC Bitcoin Post-Quantum Quantum Computing Hash-Based Signatures

TL;DR: A new paper by Avihu Mordechai Levy (StarkWare) describes Quantum-Safe Bitcoin (QSB), a way to spend legacy Bitcoin outputs that would stay secure even if an attacker had a cryptographically relevant quantum computer. It works inside today's Bitcoin Script with no soft fork. Under the paper's Shor-only threat model, its recommended configuration (Config A) achieves roughly 2^118 second-preimage resistance while fitting inside Bitcoin's existing legacy script limits of 201 opcodes and under 10,000 bytes (§4.5, §2.2). The spender pays roughly $75 to $150 in off-chain GPU compute per spend (§4.6), which is not the Bitcoin transaction fee. The construction itself only works in legacy pre-SegWit script execution; SegWit and Taproot cannot host it, and moving funds into a QSB bare-script output still requires a normal quantum-unsafe spend first. It does not relay as a standard transaction. Its own author describes it as a "last-resort measure" (§1.3).

Last week, I wrote about the Google Quantum AI paper that tightened the resource estimate for breaking secp256k1 with Shor's algorithm. That piece was about the threat. This one is about the escape hatch that appeared on April 9, 2026, when Levy posted QSB on GitHub. Read together, the two papers describe the three-piece shape of Bitcoin's post-quantum story: a sharper threat model, a clever last-resort escape for legacy coins, and a still-unfinished protocol-level migration path.

What the QSB paper actually does

QSB takes Robin Linus's Binohash and replaces the one component Shor's algorithm breaks. Binohash is a 2026 construction that lets a spender prove a transaction came from the holder of a pre-SegWit address using only Bitcoin Script primitives, without needing OP_CAT or any soft fork. Its security under quantum attack rested on a proof-of-work puzzle over ECDSA (Elliptic Curve Digital Signature Algorithm) signature sizes, and that puzzle assumed the spender could not find a curve point whose r value was shorter than the known minimum rmin (§2.8.1). Classically, that search is about 2^96 work. Under Shor, it is trivial: compute the discrete log of any shorter r you like, and the puzzle falls apart completely. Levy calls this out as a total break, not a weakening (§2.8.1).

QSB swaps the signature-size puzzle for a hash-to-signature puzzle whose security rests only on RIPEMD-160 preimage resistance (§1.2, §3). Hashes do not fall to Shor, so the quantum adversary loses the advantage that killed Binohash. As a side benefit, the new construction also hardcodes the sighash flag in the locking script, which closes the sighash-flag uncertainty Binohash left open in its own §7.1 (§3.2).

The whole thing fits within Bitcoin's existing consensus: 201 non-push opcodes, 10,000 bytes per script (§4.5, §2.2). No soft fork, no new BIP (Bitcoin Improvement Proposal), no new opcodes. Bitcoin's consensus rules already accept this today, but only as a legacy bare-script construction: SegWit (Segregated Witness) and Taproot cannot host it directly, and funds must first be moved into a QSB output through a normal spend. End-to-end implementation is still in progress in Levy's public repo: the GPU pinning search has found a real DER hit, but the digest search is not yet tested end-to-end with real transaction parameters, and no QSB transaction has been broadcast at the time of writing.

The clever primitive (and who actually invented it)

The core observation behind QSB is not Levy's. It belongs to Robin Linus, who published it in the sha2-ecdsa repo and is cited as reference [8] in the paper (§3.1.1). The paper is careful about this credit, and the post should be too.

The observation: the output of a cryptographic hash function can, with some probability, be a valid DER-encoded ECDSA signature. DER (Distinguished Encoding Rules) signatures follow a rigid layout of length bytes, integer tags, and magnitude constraints on r and s. SCRIPT_VERIFY_STRICTENC is a relay policy rather than a consensus rule, so the sighash byte at the end is unconstrained at the consensus level. That leaves just enough slack in the format for a random 20-byte RIPEMD-160 output to happen to parse as a valid signature. Levy works out the probability as roughly 2^-46 (§3.1.3, with the matching SHA-256 figure of 2^-45.4 derived in §3.1.2).

Grind inputs until RIPEMD-160(input) happens to be a valid DER ECDSA signature. About 2^46 hash evaluations. That is the puzzle. Security depends on preimage resistance, nothing else.

QSB's script construction wires this together in three moves (§3.2, §3.3). A hardcoded sig_nonce with a fixed SIGHASH_ALL byte lives in the locking script. From it, the spender recovers key_nonce = Recover(sig_nonce, z), where z is the sighash of the actual spending transaction, which binds the puzzle to that specific transaction. Then the script checks whether RIPEMD-160(key_nonce) is itself a valid DER signature, verified against a second recovered key key_puzzle via CHECKSIGVERIFY. Transaction pinning costs 5 opcodes, down from Binohash's 13, and digest rounds reuse the FindAndDelete trick from Binohash for subset-selection entropy.

The honest numbers

Configuration A is the one Levy recommends (§4.5). It sets t = 8 + 1b in round one and t = 7 + 2b in round two, where b counts bonus keys that contribute entropy without a full HORS (hash-to-obtain-random-subset) verification (§3.3.2). The numbers:

  • 201 opcodes exactly, fits the script limit
  • Well under the 10,000 byte script limit (§4.1, §4.2)
  • Digest size of 80.4 bits
  • Second-preimage resistance of about 2^118 under Shor (§4.5)
  • Collision resistance of about 2^78 under Shor (§4.5)
  • Roughly one grinding attempt per transaction

The central result is on the Shor column. Shor offers zero advantage against QSB at Config A's parameters (§4.4). An attacker with a full fault-tolerant quantum computer faces the same ~2^118 second-preimage search a classical attacker does. That is the whole point of the construction.

Grover is the interesting column. Under Grover's quadratic speedup, baseline second-preimage resistance drops from about 2^138 classical to about 2^69 (§4.4). Levy notes Grover is hard to parallelize in practice (k machines give a √k speedup, not k) and requires implementing sighash evaluation and ECDSA key recovery as reversible quantum circuits. Grover against 2^46 RIPEMD-160 puzzle targets is much further out than Shor against secp256k1.

Off-chain cost per spend breaks down roughly as $25 to $50 for transaction pinning, $25 to $50 for round one, and $25 to $50 for round two, on commodity cloud GPUs at current spot pricing, for a total of about $75 to $150 per spend (§4.6). The paper's §4.6 table widens this to $75 to $200 to account for implementation uncertainty, and the abstract rounds it to "a few hundred dollars." Two things matter about this number. First, it is roughly 9x the equivalent Binohash work, because the RIPEMD-160 target is fixed at 2^46 while Binohash's OP_SIZE puzzle could be tuned continuously. Second, and more importantly, this is not the Bitcoin transaction fee. It is the off-chain GPU compute that the spender buys before broadcasting. Any coverage that collapses it to "$200 per transaction" is wrong.

The five things the paper does not solve

Levy is unusually direct about what QSB cannot do. From §1.3 and footnote 1 on page 1:

  1. Taproot is worse, not helped. Footnote 1: "Under Taproot, the situation is strictly worse: every Taproot output is spendable via the key path, meaning knowledge of the private key corresponding to the internal public key ... suffices to spend it, regardless of the script conditions in the taptree." Every P2TR (Pay-to-Taproot) UTXO (unspent transaction output) defined by BIP-341 is still a standing target under Shor, as the Google paper's Taproot section warned.
  2. Non-standard relay. §3.5 describes a script that exceeds default relay policy limits. A regular node will not propagate it. The spender has to submit directly to a miner that accepts non-standard transactions, and Levy names Marathon Slipstream as one practical option today. Depending on a mining pool's private mempool service is not a resilient broadcast path.
  3. Off-chain compute per spend. Each spend costs roughly $75 to $150 in GPU time before you ever pay a transaction fee, and that work is per-transaction, not amortizable across a wallet.
  4. Does not scale. Quoting §1.3: "the off-chain computational cost and the on-chain transaction cost do not scale to the full range of users, amounts, and throughput that Bitcoin targets." This is an evacuation route, not a commuter lane.
  5. No Lightning. From the same section: "does not yet cover all Bitcoin use cases (e.g., Lightning Network channels)." Payment channels, multi-party protocols, and anything depending on pre-signed off-chain state are out of scope.

Levy's own framing in §1.3 is that QSB "should be treated as a last-resort measure."

Does this change the migration requirement?

No. A custodian or wallet holder reading this paper and asking "can I skip post-quantum migration now?" should walk away with a direct answer.

QSB is a prophylactic, not a treatment. It protects coins that are already sitting inside a QSB-locked legacy bare script output. Moving coins into that output requires a normal Bitcoin transaction whose spend reveals the source address's pubkey in the mempool, and that migration transaction is itself quantum-unsafe. The paper is about the QSB locking script, not about how coins get into it, but the implication matters for anyone trying to decide whether to use the construction: if a quantum attacker fast enough to forge within a confirmation window already exists when you try to migrate in, the migration transaction is the window they win. QSB only helps holders who act before the quantum threat materializes, which is exactly what Levy's "last-resort measure" language in §1.3 is quietly saying.

QSB also does not create a quantum-safe destination. BIP-360's P2MR (Pay-to-Merkle-Root) is one leading draft path for long-exposure protection (keys stay hidden until spend), but full protection against short-exposure attacks during the broadcast-to-confirmation window may still require post-quantum signature support at the protocol level. And QSB does not scale, does not cover Lightning, and costs $75 to $150 in off-chain compute per spend.

Levy states this directly in §1.3: "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." Protocol-level changes are still necessary, and BIP-360 is the leading draft proposal aimed at that path.

What this tells us about Bitcoin's post-quantum timeline

Three things change, and none of them change by much.

The "we have zero options" argument gets weaker. Before QSB, the honest answer for a legacy pre-SegWit holder in a post-Shor world was "your coins are gone unless the protocol changes." Now there is a well-specified escape path that fits within today's Bitcoin consensus rules, even if a real end-to-end broadcast has not happened yet. It is expensive and awkward, but it exists, and it is the kind of thing a serious exchange or custodian might try to operationalize for an emergency sweep if the remaining pipeline is completed.

The "we need a proper PQ signature at the protocol level" argument gets stronger. QSB is the best anyone has built inside the constraints of legacy Bitcoin Script, and even it costs $75 to $150 of GPU compute per spend, requires direct miner submission, does not touch Taproot, and cannot carry Lightning or normal throughput. If this is what the best-effort hack looks like, the case for a real post-quantum signature type gets louder, not quieter. BIP-360 remains one of the clearest draft proposals for a protocol-level post-quantum output type, but it is not the whole problem. Levy says the same thing in §1.3: the quantum threat still requires protocol-level changes, because in-Script workarounds hit the limits spelled out above.

Taproot remains exposed. QSB does nothing for the approximately 21.68% of 2025 Bitcoin transactions that used P2TR (per Table I of the Google quantum Bitcoin paper, covered in my Apr 2 companion post), and their exposed tweaked public keys remain one of Bitcoin's clearest standing targets once a cryptographically relevant quantum computer exists.

The Apr 2 Google paper sharpened the threat. QSB gives legacy holders a narrow, expensive, last-resort escape hatch. BIP-360 is the proposed migration still working through activation. Threat, escape hatch, migration: that is the three-piece shape of Bitcoin's post-quantum story as of this week.

Sources:

  1. Levy, "Quantum-Safe Bitcoin Transactions Without Softforks," StarkWare, April 2026
  2. Linus, "Binohash," 2026
  3. Linus, sha2-ecdsa repository (origin of the hash-to-signature observation, cited as ref [8] in the QSB paper)
  4. BIP-341 (Taproot), github.com/bitcoin/bips/blob/master/bip-0341.mediawiki
  5. BIP-143 (SegWit sighash, which removed FindAndDelete), github.com/bitcoin/bips/blob/master/bip-0143.mediawiki
  6. BIP-360 (Hunter Beast / cryptoquick), bip360.org
  7. Marathon Slipstream, slipstream.mara.com
  8. Encryptorium, "Google's quantum threat to Bitcoin: what the paper actually says," April 2, 2026