Proving Crypto Ownership After Q-Day

Project Eleven has funded the development of a new post-quantum primitive that could help solve one of crypto's hardest migration problems:

How do you prove ownership of a wallet after quantum computers can forge its signatures?

The answer may be the wallet's own key derivation from seed to address.

Project Eleven and Jim Posen, lead developer of Binius, have built a practical post-quantum zero-knowledge proof that lets a user prove:

• They know key material that sits above their address in the wallet's BIP-32 tree.
• That key material derives, through BIP-32, the private key for the address.
• The proof is bound to a message, so it can authorize a specific migration transaction.

The user proves all of this without revealing any of the key material.

On an M5 MacBook Air, the current implementation generates a proof in 243 ms using four cores, and verifies it in 40 ms. It uses 2.1 GB of memory and no GPU.

Why this matters

Most discussions about the quantum threat to crypto focus on migrating funds before quantum computers become powerful enough to break elliptic-curve cryptography.

That migration will likely involve blockchains introducing post-quantum accounts and giving users a window to move assets into quantum-safe ones.

But some users will miss that window, or be unwilling to execute a migration transaction that reveals their public key, leaving them vulnerable to quantum attack.

After Q-Day, those legacy private keys no longer provide meaningful proof of ownership. If a quantum computer can derive the private key from the public key, both the legitimate owner and the attacker can produce a valid signature. The blockchain cannot tell them apart.

Key derivation is different.

A quantum computer can derive an elliptic curve private key from a public key. It cannot walk up a wallet's derivation tree past a hardened derivation step. A hardened step feeds the parent's private key into HMAC-SHA512, so recovering the parent means inverting a hash. Quantum computers are not good at that: Grover's algorithm only halves the security exponent, so a 256-bit hash still costs 2^128 to invert, and the search parallelises poorly enough that the real cost is even higher.

So an attacker who has broken your address holds the same key you do. They do not hold, and cannot compute, the key it was derived from. Proving knowledge of a key above a hardened derivation step is therefore something only the real owner can do, even after Q-Day.

With this primitive, users could migrate to post-quantum addresses safely without revealing their public key, and after any pre-determined migration window.

What the proof proves

The circuit takes a BIP-32 extended private key as a private input, applies one hardened derivation step and then a two-level non-hardened path, and proves that the resulting compressed public key hashes to a public digest. The verifier turns that digest into the address and checks it matches.

For a standard BIP-44 wallet at m/44'/0'/0'/0/0, the proven statement starts one level above the account, at m/44'/0', and the hardened account step is proved inside the circuit. The steps above it are computed by the wallet, on the user's machine, and never revealed. The circuit does not start from the seed on a BIP-44 path.

This is enough for the migration property described above, as a quantum computer cannot reverse those upper steps.

A potential post-migration recovery path

Any blockchain could choose to implement a recovery mechanism based on this primitive.

A user could generate a post-quantum zero-knowledge proof showing that their wallet's key derivation produces the address containing the unmigrated assets. Because the proof commits to an arbitrary message, that same proof can authorize the move to a new post-quantum address.

This could create a path for legitimate users to recover unmigrated assets before, or after, a post-quantum migration window has closed.

The approach applies to wallets using BIP-32-style hierarchical key derivation, which is supported across modern crypto wallets and many blockchain ecosystems. For chains that use SLIP-0010 (Solana, Sui, Aptos, and others), the same approach can be applied. See our two part series covering this; here and here.

Each chain would need to integrate the verification logic into its own protocol, or deploy a dedicated verifier contract.

More than 15× faster than comparable prior work

The idea of using a wallet's hash-based derivation as a post-quantum proof of ownership comes from Sattath and Wyborski, who called it signature lifting. Olaoluwa Osuntokun, aka Roasbeef, then built the first working implementation of it on the risc0 zkVM, and published benchmarks.

That work demonstrated the concept. Ours demonstrates that it can be fast.

Their implementation offers several versions, which prove different statements at different costs. The one that proves the same statement as ours takes a parent key as a private input and derives the address key from it. It generates a proof in 14.6 seconds, using GPU acceleration.

Ours does the same job in 910 milliseconds, on the CPU alone. That is 16 times faster.

That 910 ms includes everything: building the circuit and the prover (about 630 ms), generating the proof (243 ms), and self-checking it (37 ms). The setup does not depend on the wallet, so a real prover would build it once and reuse it. Counted that way we are nearer 60 times faster. We quote the more conservative figure.

Our proving peaks at 2.1 GB. Their work does not publish a figure for the comparable version, but the versions either side of it need 3.1 GB and 11.9 GB of memory.

Current performance: (Apple M5, 10 cores, 32 GB, CPU only)

Proof generation: 243 ms on 4 cores, 475 ms on one

One-time setup: 600 ms single core, 630 ms on four, witness-independent

Verification: 40 ms, plus 117 ms to build the verifier

Proof size: 358 KiB (366,928 bytes), identical for every address type

Peak memory: 2.1 GB proving, 432 MB verifying

Trusted setup: none

Interestingly, proving is fastest on four threads, not ten: the M5 has four performance cores, and spreading the work onto the efficiency cores makes it slower.

On performance and proof size, prior work looks better at first glance: Osuntokun’s most compact proof is 217 KiB, against our 358 KiB, and it verifies in 30 ms against our 40 ms. But the two figures are not measured at the same security level. RISC Zero reaches that size only under an unproven conjecture about FRI, as its own code notes. Counting only proven security, that 217 KiB configuration provides substantially less than we target. Matching it to our assumptions would, by our estimate, raise their query count from about 50 to 140 and grow the proof by around 180%, past our 358 KiB. So at a comparable, conservative security level, we lead on proving time, on memory, and likely on proof size as well.

The proof is built using Binius64, a post-quantum general-purpose zero-knowledge proof system over binary fields.

What comes next

The current implementation supports three Bitcoin address types: P2PKH, P2WPKH, and P2SH-P2WPKH.

The same architecture could be extended to:

• Rooting the proof in the seed itself, rather than the coin-type key
• Taproot addresses
• Other BIP-32-compatible blockchains
• Multiple addresses or accounts derived from one wallet
• Proofs covering many assets at once
• Wallet, custody, and protocol-level recovery tooling

This is an early prototype and it is unaudited. It does not allow users to recover assets on existing blockchains today. Any real recovery mechanism would require explicit support from the relevant protocol.

But the core result is important:

Quantum computers can extract a private key from a public key. They cannot reverse the hashing that produced it. A wallet's own key derivation may still provide a final, post-quantum proof of ownership.

Previous work showed that this could be built. We now know that it can be built fast enough to use.

We are proud to have funded this work, and we want to thank Jim Posen for his efforts to incorporate this use case into Binius.

You can find the full source code here.

‍