Verifiably Buy Solutions to NP Problems with Bitcoin

Zero Knowledge Contingent Payments (ZKCP) allow buyers to verifiably purchase solutions to NP-complete problems over Bitcoin's Lightning Network using zero-knowledge proofs. By combining HTLCs with ZKPs (preferably STARKs to avoid trusted setup issues), a seller can prove arbitrary properties of a Lightning preimage without revealing it — for example, that a preimage is also a secp256k1 private key. An optimization using Schnorr signatures reduces proof time from 47 minutes to ~20 seconds. The approach generalizes to purchasing any NP-complete solution (Sudoku, prime factorization, neural networks, etc.) by encrypting the solution with the preimage as key and proving validity in zero knowledge. Trade-offs include slow proving times, large proof sizes for STARKs, and immature ZKP implementations. The technique also serves as a bridge to PTLC-like functionality on today's Lightning Network without requiring protocol upgrades.