Verifying an international agreement pausing AI development needs evidence of how compute is used. Cryptography can give protocols that run in software on the chips already installed, without trusted hardware checking each computation. This post is a literature review of one such tool, proof of useful work (PoUW), with which a GPU proves that it did a given amount of work, here typically matrix multiplication. In contrast with inference verification, PoUW has been developed almost exclusively in relation to cryptocurrencies in order to use a more useful computation instead of the useless hashing used in Bitcoin. PoUW could be used to show remotely that chips are kept busy on useless tasks during an emergency shutdown, or, together with a zero-knowledge proof of the workload, that they run only declared inference.
I describe the two existing constructions, by Komargodski and Weinstein for matrices over a finite field, and by Pearl Research for the FP8 format used in AI, verifiable for now only on NVIDIA chips. For the finite-field scheme, a lower bound on the work is proven, but it covers only a fraction of what an honest prover does. The guarantee a treaty needs, at realistic matrix sizes, rests on unproven assumptions in both schemes; for Pearl, the assumption is stated only informally.
PoUW depends on knowledge of the hardware. It gives only a lower bound on work, which means little without a trusted bound on peak chip capacity and a way to tie the work to the declared chips; the floating-point scheme moreover needs a bit-exact model of each chip's arithmetic, and the true cost of the declared workload depends on the GPU it runs on. These hardware questions aside, most of the open problems are mathematical and should be amenable to AI-assisted research.
For full post, see my website.
Verifying an international agreement pausing AI development needs evidence of how compute is used. Cryptography can give protocols that run in software on the chips already installed, without trusted hardware checking each computation. This post is a literature review of one such tool, proof of useful work (PoUW), with which a GPU proves that it did a given amount of work, here typically matrix multiplication. In contrast with inference verification, PoUW has been developed almost exclusively in relation to cryptocurrencies in order to use a more useful computation instead of the useless hashing used in Bitcoin. PoUW could be used to show remotely that chips are kept busy on useless tasks during an emergency shutdown, or, together with a zero-knowledge proof of the workload, that they run only declared inference.
I describe the two existing constructions, by Komargodski and Weinstein for matrices over a finite field, and by Pearl Research for the FP8 format used in AI, verifiable for now only on NVIDIA chips. For the finite-field scheme, a lower bound on the work is proven, but it covers only a fraction of what an honest prover does. The guarantee a treaty needs, at realistic matrix sizes, rests on unproven assumptions in both schemes; for Pearl, the assumption is stated only informally.
PoUW depends on knowledge of the hardware. It gives only a lower bound on work, which means little without a trusted bound on peak chip capacity and a way to tie the work to the declared chips; the floating-point scheme moreover needs a bit-exact model of each chip's arithmetic, and the true cost of the declared workload depends on the GPU it runs on. These hardware questions aside, most of the open problems are mathematical and should be amenable to AI-assisted research.