bip32-pq-zkp

KO | EN

gitlite — search

#javascript #react #go #rust #deep-learning #linux #docker #java #windows #awesome #kubernetes #awesome-list #openai #open-source

(★ 15)

BIP32 to Taproot zk proof demo on risc0

bip32-pq-zkp Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# bip32-pq-zkp

`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:

```math
\mathcal{R} = \left\lbrace\;
(\overbrace{K,\, C}^{\textsf{public}} ;\; \underbrace{s,\, \mathbf{p}}_{\textsf{witness}})
\;\middle|\;
\begin{aligned}
  K &= \textsf{BIP86Taproot}\bigl(\textsf{BIP32Derive}(s,\, \mathbf{p})\bigr) \\
  C &= \textsf{SHA256}\bigl(\texttt{"bip32-pq-zkp:path:v1"} \;\|\; \mathbf{p}\bigr)
\end{aligned}
\;\right\rbrace
```

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.

## Background

The idea comes from Sattath and Wyborski's paper ["Protecting Quantum
Procrastinators with Signature
Lifting"](https://eprint.iacr.org/2023/362). 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.

## How It Works

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.

```mermaid
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
```

## Verifier Artifacts

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.

## What This Repo Contains

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`](https://github.com/roasbeef/go-zkvm) repo.

## Expected Sibling Layout

```text
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:

```bash
export GO_GOROOT=/path/to/go1.24.4
```

## Quick Start

Build the deterministic platform archive from the sibling `risc0` repo:

```bash
make platform-standalone
```

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

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

Generate the canonical verifier artifacts:

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

Verify the emitted receipt + claim pair:

```bash
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:

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

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

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

## Artifacts

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.

## Current Verified Result

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

| Field | Value |
|-------|-------|
| Taproot output key | `00324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f07f992b288ee6` |
| Path commitment | `4c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b` |
| Journal size | 72 bytes |
| Image ID | `8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077cbe70907a690` |
| Composite proof seal size | 1,797,880 bytes |
| Composite receipt size on disk | 1,799,256 bytes |
| Composite prove time | 49.32s |
| Composite verify time | 0.10s |
| Succinct proof seal size | 222,668 bytes |
| Succinct receipt size on disk | 223,319 bytes |
| Succinct prove time | 64.30s |
| Succinct verify time | 0.03s |
| Composite peak RSS | 11.91 GB |

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.

## Reduced Proof Variants

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.

| Lane | Statement | Composite seal | Prove time | Succinct seal | Prove time |
|------|-----------|---------------|------------|---------------|------------|
| Full Taproot | seed + path to Taproot output key | 1,797,880 B | 49.32s | 222,668 B | 64.30s |
| Hardened xpub | parent xpriv to child compressed pubkey | 513,680 B | 14.63s | 222,668 B | 17.29s |
| Hardened xpriv | single hardened CKDpriv step | 234,568 B | 1.98s | 222,668 B | 2.84s |

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:

```bash
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
```

## Batch Aggregation

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:

| N | Kind | Receipt bytes | Seal bytes | Claim JSON | Inclusion JSON | Prove sec |
|---|------|---------------|------------|------------|----------------|-----------|
| 2 | composite | 681,214 | 679,904 | 755 | 456 | 2.06 |
| 2 | succinct  | 223,343 | 222,668 | 755 | 456 | 5.35 |
| 4 | composite | 1,138,062 | 1,135,864 | 756 | 528 | 3.66 |
| 4 | succinct  | 223,343 | 222,668 | 755 | 528 | 9.44 |
| 8 | composite | 2,042,158 | 2,038,184 | 756 | 600 | 7.31 |
| 8 | succinct  | 223,343 | 222,668 | 755 | 600 | 17.74 |
| 16 | composite | 4,072,409 | 4,064,720 | 757 | 673 | 11.24 |
| 16 | succinct  | 223,343 | 222,668 | 756 | 673 | 33.80 |

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:

| N | `N` separate succinct leaf receipts | Final succinct batch + claim + inclusion |
|---|-------------------------------------|------------------------------------------|
| 2 | 446,638 B | 224,554 B |
| 4 | 893,276 B | 224,626 B |
| 8 | 1,786,552 B | 224,698 B |
| 16 | 3,573,104 B | 224,772 B |

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:

| N | Final kind | Flat prove | Flat peak RSS | Nested total prove | Nested peak RSS | Flat verifier artifact | Nested verifier artifact |
|---|------------|------------|---------------|--------------------|-----------------|------------------------|--------------------------|
| 8 | composite | 7.27s | 11.21 GiB | 24.79s | 5.75 GiB | 2,043,514 B | 1,139,980 B |
| 8 | succinct | 17.74s | 11.20 GiB | 30.69s | 5.74 GiB | 224,698 B | 225,260 B |
| 16 | composite | 11.24s | 11.25 GiB | 45.25s | 5.75 GiB | 4,073,839 B | 1,140,056 B |
| 16 | succinct | 33.80s | 11.26 GiB | 51.82s | 5.75 GiB | 224,772 B | 225,337 B |

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:

```bash
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.

## Policy

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.

## Future Work

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

## Documentation

- `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

bip32-pq-zkp

bip32-pq-zkp Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

bip32-pq-zkp

bip32-pq-zkp Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README