bip32-pq-zkp is a proof-of-concept for Bitcoin's post-quantum migration path. If a quantum computer eventually breaks the secp256k1 key-spend path, a soft fork could disable raw Schnorr/ECDSA spends and require a zero-knowledge proof of BIP-32 seed knowledge instead. This repo demonstrates that proof: given a Taproot output key on-chain, the owner proves, inside a STARK-based zkVM, that they know the BIP-32 seed and derivation path that produced it, without ever revealing the seed.

The proof relation:

where $K$ is the Taproot output key, $C$ is the path commitment, $s$ is the BIP-32 seed, and $\mathbf{p}$ is the derivation path.

The idea comes from Sattath and Wyborski's paper "Protecting Quantum Procrastinators with Signature Lifting". Their key insight is that BIP-32 HD derivation passes through HMAC-SHA512, a post-quantum one-way function, so the seed-to-key path has structure that survives a quantum break of the elliptic curve. They call this seed lifting and show it can recover HD-derived coins even after the child public key leaks.

Their concrete construction uses Picnic signatures, which requires revealing the master secret key to the verifier. They explicitly leave the harder variant, seed lifting without exposing the master secret, as an open problem.

This repo solves that open problem. Instead of Picnic, we run the full BIP-32 derivation inside a risc0 zkVM guest and produce a STARK proof. The seed and derivation path are private witness data that never leave the prover. The STARK proof system is itself post-quantum secure (transparent, no trusted setup), so the entire construction holds even in a world with large-scale quantum computers.

1. The host builds a private witness containing the BIP-32 seed and derivation path.
2. The host passes the witness to the guest program via stdin.
3. The guest runs the full BIP-32 key derivation and BIP-86 Taproot output-key computation inside the risc0 zkVM.
4. The guest commits a 72-byte public claim (version, flags, output key, path commitment) to the proof journal.
5. The host generates a STARK proof and writes the receipt and claim artifacts.

flowchart TD
    subgraph witness [Private Witness - never revealed]
        Seed[BIP-32 Seed]
        Path[Derivation Path]
    end

    subgraph guest [Guest - inside risc0 zkVM]
        Seed -->|stdin| Read[Read witness]
        Path -->|stdin| Read
        Read --> Derive[BIP-32 CKDpriv]
        Derive --> Taproot[BIP-86 Taproot tweak]
        Taproot --> Commit[Commit 72-byte claim]
    end

    subgraph output [Public Output]
        Commit --> Journal[Journal: key + path commitment]
        Journal --> Receipt[STARK Receipt]
        Receipt --> Verify{Verify}
        Verify -->|valid| OK[Ownership proved]
    end

A prove run emits two files: a binary receipt (the STARK proof) and a human-readable claim.json that names the public fields from the relation above. The intended verification flow is:

1. Load the receipt and claim.json.
2. Compute or pin the expected image ID for the guest binary.
3. Verify the receipt against that image ID.
4. Compare the verified journal output to the claim file.

Direct PUBKEY, PATH_COMMITMENT, or BIP32_PATH flag checks are also supported for callers who want per-field verification without a claim file.

This repo is the demo layer on top of the reusable sibling go-zkvm host and guest plumbing. It contains:

• minimal BIP-32 derivation helpers and ExtendedPrivateKey type (bip32/)
• BIP-86 Taproot output-key derivation helpers
• four TinyGo guest programs:
  • full Taproot lane (guest/): seed + full path to Taproot output key
  • hardened-xpub lane (guest_hardened_xpub/): parent xpriv to child compressed pubkey
  • hardened-xpriv lane (guest_hardened_xpriv/): single hardened CKDpriv step, no EC point multiplication
  • batch aggregation guest (guest_batch/): recursive composition over N leaf receipts into one Merkle-root batch claim
• batch claim and Merkle tree primitives (batchclaim/)
• a demo-specific Go host CLI with thirteen subcommands across all four lanes (cmd/bip32-pq-zkp-host/)
• host-side reference tests against btcd/txscript and btcd/hdkeychain (hostcheck/)
• the root-level bip32pqzkp Go package providing Runner, BuildWitnessStdin, DecodePublicClaim, batch runners, and claim-file helpers for all lanes
• claim specification, aggregation design, and runbook documentation (docs/)

The reusable guest packaging, proving, and verification boundary lives in the sibling go-zkvm repo.

github.com/roasbeef/
├── risc0
├── tinygo-zkvm
├── go-zkvm
└── bip32-pq-zkp

Fresh-clone setup:

• in sibling tinygo-zkvm, run git submodule update --init --recursive
• in sibling risc0, run git lfs pull
• make execute, make prove, and make verify will build the sibling go-zkvm host-ffi shared library if it is missing or stale

If your default go is newer than the TinyGo lane supports, export:

export GO_GOROOT=/path/to/go1.24.4

Build the deterministic platform archive from the sibling risc0 repo:

make platform-standalone

Run the built-in test vector in execute-only mode:

make execute GO_GOROOT=/path/to/go1.24.4

Generate the canonical verifier artifacts:

make prove GO_GOROOT=/path/to/go1.24.4

Verify the emitted receipt + claim pair:

make verify GO_GOROOT=/path/to/go1.24.4

By default:

• make execute and make prove use the built-in BIP-32 test vector
• make verify uses the default artifacts from the prior make prove
• the documented demo lane keeps require_bip86=true
• make prove defaults to RECEIPT_KIND=composite

To generate a smaller recursively compressed receipt instead:

make prove GO_GOROOT=/path/to/go1.24.4 RECEIPT_KIND=succinct

To use an explicit private witness instead of the built-in vector:

make prove GO_GOROOT=/path/to/go1.24.4 \
  PRIV_SEED_HEX=000102030405060708090a0b0c0d0e0f \
  BIP32_PATH="86',0',0',0,0" \
  REQUIRE_BIP86=1

The default prove target writes:

• ./artifacts/bip32-test-vector.receipt
• ./artifacts/bip32-test-vector.claim.json

The receipt is the STARK proof artifact. claim.json is the stable, human-readable description of the public statement being proved.

Built-in test vector result (BIP-32 test vector 1, path m/86'/0'/0'/0/0):

On Apple Silicon, the local proving lane uses Metal GPU acceleration. Guest compilation is normal CPU work; Metal applies to the prover only.

The public claim is identical in both receipt modes. Changing RECEIPT_KIND only changes the receipt representation and proof size/time tradeoff, not the claim semantics or image ID.

In addition to the full Taproot lane, this repo includes two reduced proof variants that trade statement strength for dramatically lower proving cost. The key insight is that once the guest avoids EC point multiplication, the composite receipt is already close to the succinct size floor.

The hardened-xpriv variant is the most efficient: ~2 seconds to prove, ~235 KB composite receipt, and only 3.14 GB peak RAM (vs 11.9 GB for the full lane). It is the natural first leaf proof for the current batch-aggregation lane.

All three lanes share the same BIP-32 derivation core (bip32/) and the same host plumbing pattern. See docs/reduced-variants.md for full benchmarks, execute-only context, and tradeoff analysis.

Quick start for the reduced variants:

make execute-hardened-xpriv GO_GOROOT=/path/to/go1.24.4
make prove-hardened-xpriv GO_GOROOT=/path/to/go1.24.4
make verify-hardened-xpriv GO_GOROOT=/path/to/go1.24.4

The current v1 batch aggregation lane uses risc0's recursive composition to verify N leaf receipts inside one aggregation guest and commit a single Merkle root. The result is one final receipt that proves: "there exist N valid leaf receipts, all from the same guest image, whose ordered journals hash to this root."

The batch guest supports both hardened-xpriv and full Taproot leaf schemas. The first nested layer is also implemented: parent batches can use batch-claim-v1 leaves built from child batch claim.json artifacts. Verifiers can either verify the batch receipt alone, check one disclosed leaf via an ordinary Merkle inclusion proof, or verify one bundled nested inclusion-chain artifact that walks from the top batch down to one disclosed original leaf.

Current hardened-xpriv batch scaling results:

The final succinct batch receipt stayed flat at ~223 KB across the current matrix. The fan-out shows up in the Merkle inclusion layer and the batch claim metadata, not in the final succinct receipt itself.

For sparse disclosure, that gives a much better verifier artifact story than shipping many leaf receipts directly. On the hardened-xpriv lane:

A smaller confirmation matrix on the original full Taproot leaf schema landed very close to the hardened-xpriv numbers:

• N=2
  • composite receipt: 681,214 bytes
  • succinct receipt: 223,343 bytes
• N=8
  • composite receipt: 2,042,158 bytes
  • succinct receipt: 223,343 bytes

That strongly suggests the current aggregation cost is mostly “verify N succinct leaf receipts plus Merkle-hash their journals,” not “re-run the original leaf semantics.”

Current flat-vs-nested comparison on the hardened-xpriv lane:

The current nested design therefore trades more total proving work for much lower peak memory and a smaller composite top-level receipt, while the final succinct artifact stays on the same ~223 KB scale either way.

Quick start:

make prove-hardened-xpriv GO_GOROOT=/path/to/go1.24.4 RECEIPT_KIND=succinct
make prove-batch GO_GOROOT=/path/to/go1.24.4
make derive-batch-inclusion GO_GOROOT=/path/to/go1.24.4
make verify-batch GO_GOROOT=/path/to/go1.24.4 \
  BATCH_INCLUSION=./artifacts/hardened-xpriv-batch.inclusion.json

See docs/batch-aggregation.md for the full architecture and docs/running.md for all batch Makefile targets and variables.

The full Taproot demo lane defaults to BIP-86 path enforcement, but callers can opt out for non-BIP-86 derivations. The design keeps a single guest image per lane: the BIP-86 requirement is a verifier-visible public claim flag, not a separate image identity. The reduced variants use separate guest images with their own image IDs.

The current proofs bind the seed to a derived key but do not yet bind the proof to a specific spending transaction. A production deployment would need to commit to the BIP-341 sighash digest inside the proof so that the receipt cannot be replayed to authorize a different spend. That is the natural next step toward a consensus-ready migration rule. See docs/claim.md for a detailed v2 claim sketch.

Other open directions:

• scaling experiments at larger N for the batch aggregation lane
• deciding whether the disclosed batch leaf format should remain hardened-xpriv or move to xpub/full-Taproot for privacy
• comparing the new heterogeneous parent mode against the homogeneous nested layout at the same total original-leaf count
• deciding whether the current heterogeneous direct-child envelope should stay narrow (hardened-xpriv, taproot, batch_claim_v1) or grow a more general leaf envelope
• deciding whether the one-shot nested wrapper should get a faster path that skips top-level rebuild checks when the caller already knows the guest and host artifacts are current
• spend-bound leaf claims that include outpoint or sighash binding

• docs/README.md: reading order and topic map
• docs/claim.md: claim specification and v2 sketch
• docs/running.md: build, execute, prove, and verify commands
• docs/reduced-variants.md: side-by-side comparison of all three proof lanes
• docs/batch-aggregation.md: batch aggregation design, verifier flow, and scaling results
• docs/nested-batching.md: implemented nested batch-of-batches design, bundled inclusion-chain verification, and current limits
• docs/heterogeneous-parent-plan.md: design rationale behind the now-implemented mixed direct-child parent mode
• docs/nested-wrapper-plan.md: design rationale behind the now-implemented manifest-driven nested wrapper
• docs/batch-future-work.md: post-nested future directions