PQ provers for P2PKH outputs

In recent research focused on the post-quantum (PQ) security of Bitcoin's Pay to Public Key Hash (P2PKH) addresses, a series of benchmarks were conducted to evaluate the practicality of using current Zero-Knowledge (ZK) proof systems for proving ownership without exposing the public key. This exploration is particularly relevant given the potential threat posed by quantum computing to cryptographic systems where exposure of the public key could compromise the corresponding private key. Specifically, for P2PKH addresses, the public key remains obscured until a transaction occurs, at which point it becomes susceptible once revealed. The proposed solution involves allowing users to prove ownership of a Bitcoin address and cryptographically link it to a PQ address without revealing their public key on the blockchain. This necessitates a ZK proof that the user possesses a public key matching a specific hash (from which the P2PKH address can be derived) and knows a valid ECDSA signature over a predetermined message hash.

The benchmarking exercise tested various proof systems on an Apple M2 Max, covering aspects such as proving and verification time, memory usage, and proof size. Among the findings, STWO-Cairo emerged as the fastest native prover with approximately 8 seconds proving time but was deemed impractical for some environments due to its ~6 GB RAM requirement in its current WASM build. Ligero, notable for its ability to run in a browser via WebGPU, demonstrated a proving time of 22 seconds, highlighting its utility for client-side applications. RISC Zero, tested on mobile hardware, showed promising results with a proof generation time of roughly 6 minutes and a peak RAM usage of ~1.2 GB, suggesting viability for mobile platforms. However, the study highlighted concerns regarding proof sizes, which ranged from 5.6 MB to 10 MB for P2PKH-related proofs, deemed too large for on-chain use but potentially suitable for off-chain registries or future covenant designs.

Additionally, the research extended into PQ signature verification, benchmarking STARK proofs for verifying the validity of PQ signatures within a STARK framework. This aspect of the study examined algorithms such as Falcon-512, ML-DSA-87 (Dilithium), and SPHINCS+-SHAKE256-256f across different systems, revealing varied results in terms of proof generation and verification times, as well as proof sizes. For instance, SP1's implementation of Falcon-512 achieved a 40-second proof generation time with a significantly large proof size for ML-DSA-87 (Dilithium) at 96.3 MB, illustrating the challenges in optimizing these proofs for practical use.

These benchmarks underscore the advancing feasibility of client-side STARK proving for P2PKH ownership in a post-quantum context, while also pinpointing the limitations related to proof sizes and the need for protocol adaptations to facilitate direct on-chain PQ migration. The comprehensive details, including specific benchmark results and source code, are available at BlockstreamResearch/pq-p2pkh.