No Consensus Changes Needed: Starkware CPO Builds Quantum-Safe Bitcoin Transactions From Existing Rules

Key Takeaways:

QSB replaces the signature-size puzzle with what Levy calls a hash-to-sig puzzle. The spender iterates over transaction parameters until the RIPEMD-160 hash of a transaction-derived public key produces a valid DER-encoded ECDSA signature. That event occurs with probability roughly 1 in 70 trillion. Because the puzzle uses a hardcoded SIGHASH_ALL flag, the sighash vulnerability is eliminated as a side effect.

The spender then runs two digest rounds using a HORS-style Lamport signature structure, selecting subsets of dummy signatures that alter the transaction’s sighash via a legacy Script mechanism called FindAndDelete. Each subset produces a different hash output. The subset that yields a valid DER-encoded signature becomes the digest for that round. Revealing the corresponding pre-images in the witness completes the quantum-safe spend.

The recommended configuration, which Levy calls Config A, fits within the 201-opcode limit and achieves approximately 118-bit pre-image resistance and 78-bit collision resistance. A quantum attacker running Grover’s algorithm against this configuration faces roughly 2 to the 69th power work for a second pre-image attack. Shor’s algorithm provides no advantage at all, since there are no elliptic curve assumptions left to break.

Off-chain computation costs between $75 and $150 in cloud GPU time per transaction at current spot pricing. The work is embarrassingly parallel and completed in hours across multiple GPUs in early tests. The GPU farm only handles public computations, including key recovery and hashing. Private HORS pre-images never leave the spender’s secure device.

“Starkware has some of the best hackers on the planet. It is beautiful to see when hackers use their powers for good.”