Paper 2026/1508

ZKPoSP: Post-Quantum Zero-Knowledge Proofs for Hierarchical Deterministic Wallets

Abstract

Recent advances in quantum hardware, including Google's Willow processor, have substantially narrowed the timeline to cryptographically relevant quantum computers. In the blockchain setting, where addresses and key derivation standards such as BIP32, BIP44, and SLIP-10 are the dominant infrastructure for wallet management, a quantum computer running Shor's algorithm can recover any elliptic-curve private key from the corresponding public key, threatening every wallet in production today. Migrating to post-quantum signature schemes requires changing the public key format and forcing address migration across all participating networks, a significant problem for blockchain communities. We present an orthogonal approach: keep the existing address format entirely unchanged and instead replace the classical signing step with a NIZK proof of knowledge of the seed underlying the existing address, where security against quantum adversaries reduces to the conjectured quantum hardness of the underlying hash functions and the soundness of the NIZK against quantum adversaries, requiring no address migration or key registration. We build on the observation of Baldimtsi et al. that EdDSA's deterministic seed-to-key mapping makes the seed a valid zero-knowledge witness for the public key, and extend their single-level result to the full hierarchical deterministic wallet setting. Starting from BIP32-Ed25519, we replace the classical signing step with a NIZK proof certifying knowledge of the root seed and the full derivation chain, and prove EUF-CMA security for the resulting scheme; post-quantum security is conjectured to hold since all underlying primitives depend only on the hardness of hash functions and the soundness of the NIZK against quantum adversaries. The existing schemes each derive their quantum-safe witness as an incidental artifact of a curve-specific key format, and none provides a single derivation standard that works uniformly across curves. We therefore introduce QBIP32, a new key derivation scheme based on a keyed function HASH768 (instantiated with KMAC256) that produces the signing scalar, an explicit quantum-safe witness, and the chain code in a single call. QBIP32 is defined for any elliptic curve group of prime order with a fixed generator, requiring no structural change to the derivation or proof system across curves: the same construction covers secp256k1, Ed25519, and any future curve used in blockchain infrastructure. This universality stands in contrast to the BIP32-Ed25519 approach, which relies on the Ed25519 extended key format and has no analogue for other curves. We then address the efficiency problem: a monolithic proof of the full derivation chain has cost growing linearly with derivation depth. Our main contribution is ZKPoSP (Zero-Knowledge Proof of Seed Provenance), a signature scheme conjectured secure against quantum adversaries that splits the proof into a derivation proof generated once per key pair and a signing proof generated once per message, reducing per-message proving cost to a constant independent of derivation depth. We further characterise exactly when the derivation proof itself can be shortened to cover only the last step of the derivation rather than the full chain from the root seed, and identify the existence of a private value that is bound to the seed by a one-way function and not recoverable from the public key as the precise criterion. This criterion is met by hardened keys but not by non-hardened keys, a structural distinction common to all schemes: BIP32 secp256k1, SLIP-10/Ed25519, BIP32-Ed25519, and QBIP32 all admit a last-step derivation proof for hardened keys, while non-hardened keys require a proof reaching back to the last hardened ancestor. We exploit this for BIP44 paths to prove only one hardened step plus the non-hardened suffix in a single proof, allowing the root seed to be removed from the proving device once the anchor node is generated, while remaining in secure long-term storage. Before Q-day, separating the derivation and signing proofs already reduces per-transaction cost to a constant independent of derivation depth. After Q-day, once networks reject all non-post-quantum signatures, the leaf scalar can be moved to the public statement, removing all elliptic-curve scalar multiplications from the proof circuit and reducing derivation proving time substantially. We implement all constructions in Rust using RISC Zero as the NIZK backend, instantiate HASH768 with KMAC256, and report benchmarks for monolithic proofs, ZKPoSP across full BIP44 paths, and the post-Q-day variant. Signing proving time is constant at approximately 12-13 seconds and verification time is constant at approximately 9-10 ms across all variants and depths.