Scale-Invariant Economic Security in Sampled-Audit Proof-of-Useful-Work

Abstract

Proof-of-useful-work (PoUW) replaces the wasted computation of proof-of-work with valuable tasks such as machine-learning inference, but has historically failed on the verification asymmetry: useful work is as costly to verify as to perform. Zero-knowledge machine learning (zkML) removes the asymmetry cryptographically, yet proving overheads currently preclude verifying every job. We analyze a sampled-audit design in which each committed job is audited independently with probability p after commitment, escalating from cheap re-execution to a zkML dispute court, with detected fraud slashing a stake S. We prove that economic security reduces to one scale-invariant bound, S > c/p, where c is the cost of one job: the attacker's expected profit from fabricating k results is then strictly decreasing in k, so the optimal attack is a single fabricated job, and it is unprofitable. The bound is invariant to batch size and robust to exit scams, Sybil splitting, and audit-gap hunting; Monte Carlo simulation validates all claims. We further prove exponential fragility under randomness grinding, detection collapses to p g with g candidate seeds, making unbiasable randomness a hard requirement, and derive the cost-optimal sampling rate p * = δ /κ.