Quantum Safe Bitcoin Transactions (Part 1)

A visual guide to the Quantum Safe Bitcoin (QSB) transactions paper.

Bitcoin transactions are typically signed with ECDSA. That signature commits to the transaction. If anything in the transaction changes, the signature breaks.

Let's look at how the signature is built.

Look at z: s depends on z, and z depends on the transaction data.

If we change the transaction → z changes → signature becomes invalid. Remember this, it's crucial for everything that follows.

1- The Quantum Attack

Bitcoin is vulnerable to quantum attacks because of Shor's algorithm 1.

That's because a quantum computer can use Shor's algorithm to recover a private key from a public key.

Here's why that's a problem.

Alice wants to send 10 BTC to Bob. She signs the transaction with her private key and broadcasts it.

Eve (attacker) has a quantum computer. She watches the mempool and sees Alice's transaction waiting to be mined.

That transaction reveals: Alice's public key.

Eve runs Shor's algorithm on Alice's public key → recovers Alice's private key.

Now Eve can spend Alice's UTXO however she wants. She builds her own transaction with the same input (same UTXO) but sends the output to herself instead of Bob.

She signs it with Alice's private key and broadcasts it.

If a miner includes Eve's transaction first, Bob never receives the BTC.

2- Using Hashes Instead of ECDSA

If quantum computers can break ECDSA, what can we rely on instead?

Answer: hashes.

Hash functions don't rely on elliptic curves. They rely on pre-image resistance: given an output, it's hard to find an input that produces it.

Shor's algorithm can't reverse a hash.

There is another quantum algorithm, Grover's 2, that does affect hash functions, but only by weakening them. It reduces the amount of time it takes to execute a brute-force search.

With Grover's algorithm, a 256-bit key would have security closer to that of a 128-bit key.

So:

  • SHA-256: 2²⁵⁶ → 2¹²⁸
  • RIPEMD-160: 2¹⁶⁰ → 2⁸⁰
That's weaker, but 2⁸⁰ is still enormous.

3- QSB Strategy

The QSB paper builds on this idea. The strategy is:

Remove all security dependence on elliptic curves. Keep only hash-based security.

4- QSB Idea

Step 1: Derive a fingerprint D of the transaction.

Step 2: Sign D with a Lamport signature (see our last post on Lamport signatures).

Since Lamport signatures are post-quantum, and D binds the whole transaction, an attacker can't swap in a different transaction without forging Lamport.

Why this stops Eve:

If Eve changes the transaction → D changes → needs a new Lamport signature → requires secret hash preimages → Eve doesn't have them ✗

That's the core idea.

Step 2 is the easy part. Step 1 (constructing D) is where all the work happens.

We'll break Step 1 down step by step in the next sections:

  • Transaction pinning
  • Finding D: Round 1
  • Finding D: Round 2

5- Transaction Pinning

In this step, Alice creates a transaction and "pins" it. Meaning: any change to the transaction becomes expensive.

To achieve this, we use two tricks.

Trick 1: Public key recovery

Normally, ECDSA works like this:

private key → public key → signature

But ECDSA also works backward too 3.

If you have:

  • a signature
  • the message hash z
You can recover the public key: signature + message z → public key.

public_key = Recover(signature, z)

(No private key is needed for this step.)

If you like the math:

Q = r⁻¹(s·R − z·G)

Notice: Q depends on z, and z depends on the transaction data.

If we change the transaction → z changes → recovered public key changes.

Trick 2: Fake signature (sig_nonce)

An ECDSA signature has two values: r and s.

When encoded as DER 0, it looks like this:

0x30 <total_len> 0x02 <r_len> <r> 0x02 <s_len> <s> <flag>

The trick: build the smallest possible DER signature with:

  • r = 1 byte
  • s = 1 byte
That gives a 9-byte signature.

This is a hardcoded fake signature. It satisfies DER encoding rules but nobody signed anything. It just has to look like a valid signature.

Let's call this sig_nonce:

sig_nonce = 30 07 02 01 [r] 02 01 [s] 01

This sig_nonce is hardcoded in the locking script.

If the locking script in the diagram looks confusing, don't worry. By the end of this guide you'll be able to read it line by line. For now, the only thing worth noticing is how short it is: just 5 opcodes to pin a transaction (Binohash needed 13*).

Binohash 4 is the scheme this paper builds on top of. We'll cover it in the next guide.

Deriving key_nonce

Now we combine both tricks:

  • Key recovery
  • Fake signature (sig_nonce)

    • We use Recover() on sig_nonce to compute key_nonce:

    key_nonce = Recover(sig_nonce, z)

    Alice computes this off-chain and provides key_nonce in the unlocking script.

    key_nonce is now bound to the transaction. Change anything → z changes → key_nonce changes.

    Where are we?

    Let's zoom out for a second. Remember the goal: build a fingerprint D that's bound to the transaction, so Eve can't swap in a different transaction without breaking the Lamport signature over D.

    To build D, we need two things:

  • A way to tie something to the transaction. Change the transaction → that thing changes.
  • A way to make changing the transaction expensive. So no one can cheaply try millions of variations.

    • We just solved #1. ✓ key_nonce = Recover(sig_nonce, z) is tied to the transaction. Change anything → z changes → key_nonce changes.

    But that's not useful on its own. We still need #2. Let's do that next.

    So what makes it expensive?

    Without pinning, here's what Eve could do.

    She sees Alice's transaction in the mempool and wants to swap it for her own. Each transaction variation she tries gives a different z, which gives a different key_nonce, which gives a different D. So she runs through thousands of variations cheaply, looking for one whose D matches Alice's. Then she can reuse Alice's Lamport signature.

    This is cheap and fast for Eve to do.

    (We'll see exactly how D is built in Part 2. For now, just know that Eve's whole attack depends on cheaply searching through transactions.)

    We need to make every single attempt cost real work. Specifically, ~2⁴⁶ hash operations per attempt.

    That's the hash-to-sig puzzle.

    The hash-to-sig puzzle (sig_puzzle)

    Here's the idea. The script takes key_nonce and hashes it with RIPEMD-160:

    RIPEMD-160(key_nonce) → 20 random-looking bytes

    Let's call those 20 bytes:

    sig_puzzle = RIPEMD-160(key_nonce)

    Now comes the trick: we want those 20 bytes (sig_puzzle) to look like a valid DER-encoded signature. As we saw earlier, a DER signature has this structure:

    30 [len] 02 [r-len] [r] 02 [s-len] [s] [flag]

    The chance to get a string of bytes looking like valid DER is very low ≈ 1 in 2⁴⁶.

    So most attempts fail. But after many tries, RIPEMD-160(key_nonce) produces bytes that look like a valid DER signature.

    That's the puzzle.

    Okay, but how do we check valid DER in Script?

    Use OP_CHECKSIG as a DER validator. We feed sig_puzzle (those 20 bytes) into OP_CHECKSIG as if it were a signature:

    • If CHECKSIG passes → ✓ valid DER → puzzle solved
    • If CHECKSIG fails → ✗ not valid → try again

    Transaction pinning (putting it all together)

    Now we know what we're looking for: a transaction where RIPEMD-160(key_nonce) looks like a valid DER signature.

    But how do we find such a transaction?

    That's where transaction pinning comes in.

    Remember: key_nonce depends on z. And z depends on the transaction data.

    So Alice can tweak transaction fields like:

    • nLocktime
    • nSequence
    • etc.
    Each tweak gives a new transaction → new z → new key_nonce → new RIPEMD-160(key_nonce).

    Most attempts fail. So Alice keeps trying until one output has the DER shape.

    On average, this takes about 2⁴⁶ tries.

    That's pinning.

    Once Alice finds a working transaction, any later change to it means starting over and redoing about 2⁴⁶ work.

    Wait, what about key_puzzle?

    Remember earlier, when Alice's unlocking script was ?

    We told you to ignore key_puzzle for now. Now we can explain it.

    key_puzzle is just another recovered public key, this time for sig_puzzle. Alice computes it off-chain using the same Recover() trick from before:

    key_puzzle = Recover(sig_puzzle, z)

    Script execution

    Remember the pinning script from earlier? Let's run through it step by step.

    Unlocking script:

    <key_puzzle> <key_nonce>

    Locking script:

    <sig_nonce>
OP_OVER
OP_CHECKSIGVERIFY
OP_RIPEMD160
OP_SWAP
OP_CHECKSIGVERIFY

    The script performs two checks:

    • key_nonce is tied to this transaction.
    • RIPEMD-160(key_nonce) works as a signature with key_puzzle.
    Now let's execute the stack step by step.

    In Part 2 we will cover:

    • The SIGHASH_SINGLE bug
    • 150 dummy signatures
    • FindAndDelete
    • Finding the digest D
    • Signing D with HORS

    References

    [0] DER signature and SEC format

    [1] Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. arxiv.org/abs/quant-ph/9508027

    [2] Lov K. Grover, A Fast Quantum Mechanical Algorithm for Database Search. arxiv.org/abs/quant-ph/9605043

    [3] Public key recovery from ECDSA signatures

    [4] Binohash: Transaction Introspection Without Softforks

    ← All posts