# Quantum-Resistant Signatures for Bitcoin: A STARK Experiment

*Implementing Blockstream Research's Bitcoin-optimized SPHINCS+ with STARK proving in Cairo*

## The Quantum Threat to Bitcoin

Bitcoin's security relies on ECDSA and Schnorr signatures, both vulnerable to quantum computers running Shor's algorithm. While large-scale quantum computers don't exist today, their timeline remains uncertain, and Bitcoin addresses that have ever spent coins are permanently exposed.

Hash-based signatures offer a solution. Unlike lattice-based schemes (ML-DSA) or code-based schemes, they rely **only on hash functions**, a primitive Bitcoin already trusts. SPHINCS+ (standardized as SLH-DSA in NIST FIPS 205) provides stateless, quantum-resistant signatures using only symmetric cryptography.

But there's a catch: **SPHINCS+ signatures are huge.** Standard parameters produce 7-8 KB signatures versus Bitcoin's current ~70 bytes for ECDSA.

## The Blockstream Breakthrough

Blockstream Research's paper ["Hash-based Signature Schemes for Bitcoin"](https://eprint.iacr.org/2025/2203.pdf) by Kudinov and Nick changes this calculus. Through careful analysis of Bitcoin's specific requirements, they achieved:

**Standard SPHINCS+ 128s:** 7,856 bytes
**Bitcoin-Optimized:** ~3,440 bytes
**Reduction:** **56% smaller**

Here's how they did it.

### 1. WOTS+C: Eliminating Checksum Chains

Standard WOTS uses checksum chains to prevent forgery, about 3 extra chains per signature. WOTS+C takes a different approach:

Instead of checksums, the signer **grinds** (repeatedly hashes with different counters) until finding a message whose base-w encoding satisfies a constraint: the last τ bytes must be zero. The verifier checks this constraint instead of computing checksums.

With w=256 and τ=2, this eliminates 5 chains entirely (2 message chains forced to zero + 3 checksum chains), saving significant space per WOTS signature.

### 2. FORS+C: Predictable Authentication Paths

Standard FORS reveals k leaves from k separate Merkle trees. Each leaf needs an authentication path.

FORS+C grinds until the last tree's leaf index is 0. Since index 0 always takes the same path (all left branches), the verifier can compute this path themselves, no need to include it.

**Result:** Save one full authentication path (224 bytes for a=14, n=16).

### 3. Reduced Signature Count

The killer optimization: **Bitcoin doesn't need 2^64 signatures per key.**

In 200 years, Bitcoin's blockchain can hold at most ~2^35 transactions. Practical wallets rarely sign more than 2^20 times with the same key.

By targeting 2^32 signatures (still astronomically more than any key will ever produce), the hypertree height drops from h=64 to h=32:

| Max Signatures | Hypertree Height | Size Impact |
|----------------|------------------|-------------|
| 2^64 (standard) | h=64 | Baseline |
| 2^32 (Bitcoin) | h=32 | ~50% smaller |

## Why STARK Aggregation Matters

Here's where it gets interesting for Bitcoin scaling.

A single SPHINCS+ BTC signature is ~3.8 KB. A block with 2000 transactions would need ~7.6 MB of quantum-resistant signatures. That's problematic for both bandwidth and verification time.

**STARK proofs change the economics:**

By implementing SPHINCS+ verification in Cairo and proving it with Stwo, we can **aggregate many signatures** into a single proof. A node only needs to verify one STARK proof instead of thousands of individual signatures.

This is signature aggregation without the cryptographic complexity of BLS or Schnorr aggregation, just computational integrity proofs.

## The Cairo Implementation

We implemented the complete Bitcoin-optimized SPHINCS+ verification in Cairo. The core verification logic:

pub fn verify_btc(message: WordSpan, sig: SphincsSignature, pk: SphincsPublicKey) -> bool {
    let SphincsSignature { randomizer, fors_sig, wots_merkle_sig_list } = sig;
    let SphincsPublicKey { pk_seed, pk_root } = pk;

    // Seed the hash function state (reused across all thash calls)
    let ctx = initialize_hash_function(pk_seed);

    // Compute extended message digest: mhash || tree_idx || leaf_idx
    let digest = hash_message_btc(randomizer, pk_seed, pk_root, message, SPX_DGST_BYTES);
    let XMessageDigest { mhash, mut tree_address, mut leaf_idx } = split_xdigest_btc(digest.span());

    // FORS: Compute public key from signature
    let mut root = fors_pk_from_sig(ctx, fors_sig, mhash, @wots_addr);

    // Hypertree: Verify d=4 layers of WOTS+C signatures
    for layer in 0..SPX_D {
        // Derive WOTS+C public key from signature (includes grinding verification)
        let wots_pk = wots_c_pk_from_sig(ctx, wots_sig, root, @wots_addr);

        // Compute leaf and verify Merkle path
        let leaf = thash_btc(ctx, @wots_pk_addr, wots_pk.span());
        root = compute_root(ctx, @tree_addr, leaf, auth_path.span(), leaf_idx, 0);

        // Move up the hypertree
        tree_address >>= 8;
        leaf_idx = tree_address & 0xFF;
    }

    root == pk_root
}

### Why Blake2s Instead of SHA-256?

The Blockstream paper specifies SHA-256, matching Bitcoin's existing hash infrastructure. Our implementation uses **Blake2s** instead. Here's why:

The Stwo prover has **native AIR (Algebraic Intermediate Representation) support for Blake2s**. This means Blake2s operations are proven efficiently with dedicated constraint systems optimized for the algorithm's structure.

SHA-256, by contrast, must be **simulated using generic bitwise operations**. Every AND, XOR, and rotation becomes expensive field arithmetic. The difference is dramatic:

| Hash Function | Cairo Steps | Memory Addresses | Provable? |
|---------------|-------------|------------------|-----------|
| Blake2s | 238K | 238K | Yes |
| SHA-256 | ~195M | ~134M | No* |

*SHA-256 exceeds Stwo's current memory limit of 2^27 addresses.

Blake2s isn't just faster, SHA-256 (emulated in Cairo and not as custom AIR / precompile) at this scale literally cannot be proven with Stwo's current constraints. This is a pragmatic engineering choice: Blake2s provides equivalent security (256-bit hash, truncated to 128 bits for n=16) while being STARK-friendly.

For a Bitcoin soft-fork, the hash function choice would need careful consideration. SHA-256 has the advantage of existing Bitcoin infrastructure, but a dedicated SHA-256 AIR for Stwo could close this gap.

## Benchmarks

Single signature verification on Apple M3:

| Metric | Value |
|--------|-------|
| Cairo Steps | 238,000 |
| Memory Addresses | 238,000 |
| Proof Size | 4.8 MB |
| Prove Time | ~7s |
| Verify Time | <20ms |

### About That Proof Size

4.8 MB sounds large. It is, but context matters:

1. **This is unoptimized.** The Stwo prover is under active development. We're using default parameters with no proof compression. Production deployments typically achieve 10-50x reduction through:
- FRI folding parameter tuning
- Proof composition and recursion
- Domain-specific optimizations

We're confident **~100 KB is achievable** with optimization work.

2. **The size doesn't grow linearly with signatures.** STARK proof size scales with O(log n) where n is the computation size. Verifying 1000 signatures produces a proof maybe 2x larger than verifying 1 signature, not 1000x. In practice, we notice even more efficient results. Also, it's always possible to use recursion to reduce the size even more and have more compression.

3. **Aggregation amortizes everything.** If one 100 KB proof attests to 1000 signatures:
- Per-signature overhead: 100 bytes (vs 3,800 bytes raw)
- Verification: One STARK verify (vs 1000 signature verifies)

The more signatures you aggregate, the better the economics.

## Current Status and Next Steps

**What's implemented:**
- Full WOTS+C verification with grinding constraint checking
- Standard FORS verification (k=10 trees, a=14 height)
- Complete hypertree verification (d=4 layers, h=32 total)
- Blake2s tweakable hash construction
- Python reference signer for test vector generation
- End-to-end STARK proof generation with Stwo

**What's next:**

1. **Aggregation benchmarks.** The real value is proving N signatures in one proof. We need to measure how proving time and proof size scale with N. Theory says O(N) proving time and O(log N) proof size, let's verify it.

2. **FORS+C implementation.** The code exists but isn't integrated into the main flow. This saves 224 bytes per signature.

3. **Proof optimization.** Current 4.8 MB proofs are untuned. Systematic optimization of FRI parameters, proof composition, and potentially recursive proving could get us to ~100 KB.

4. **Custom Stwo AIRs.** Some operations (address encoding, Merkle path computation) could benefit from specialized constraint systems rather than generic Cairo execution.

5. **Proving parallelization.** Stwo supports parallel witness generation. For batch verification, this could significantly reduce wall-clock proving time.

6. **SHA-256 investigation.** Either via a custom AIR, a different prover, or algorithmic improvements to fit within memory constraints.

## Conclusion

Post-quantum Bitcoin is looking increasingly practical. Blockstream's optimizations cut signature size by 56%. STARK proofs enable efficient aggregation. And while there's engineering work ahead, the cryptographic foundations are solid.

The path forward:
- **Short term:** Optimize proof size, implement aggregation, benchmark scaling
- **Medium term:** Production-ready prover integration, SHA-256 support
- **Long term:** Bitcoin soft-fork proposal with concrete parameters

**~3.8 KB signatures. STARK-provable. A step toward quantum-resistant Bitcoin.**

---

*Implementation: <https://github.com/AbdelStark/pq-btc-sig-stark>*
*Paper: [Hash-based Signature Schemes for Bitcoin](https://eprint.iacr.org/2025/2203.pdf)*
*BIP-360: [bip360.org](https://bip360.org/)*

*by Abdel <[e-mail]>*