P090 Proof-of-work and proof of declared non-AI use

Can a verifier confirm privately, at a small fraction of the job's cost, that a cluster ran a declared non-AI or useful workload?

Proof that compute ran a declared non-AI or useful workload.

Terms: MatMul(A, B): multiplying matrix A by matrix B. 1 + o(1) overhead: a cost that approaches that of plain matrix multiplication as the matrices grow (o(1) is a term that shrinks toward zero).

Status

Analyzed A proof-of-useful-work protocol for matrix multiplication over a finite field with near-zero prover overhead; security rests on a new hardness conjecture; no implementation, benchmark or attack evaluation. It proves a lower bound on matmul work done, not that a declared workload ran, and says nothing about privacy or about non-AI scientific workloads (weather, CFD, protein folding), which have no work. The Proofworks proof-of-memory protocol (Reuter & Karvonen 2025, preliminary fingerprint experiments) verifies declared AI workloads generally and is a neighbouring compute-accounting problem.

"Our main result is a PoUW for the task of Matrix Multiplication MatMul(A, B) of arbitrary matrices with 1 + o(1) multiplicative overhead compared to naïve MatMul. We conjecture that our protocol has optimal security in the sense that a malicious prover cannot obtain any significant advantage over an honest prover."
Komargodski & Weinstein (2025), Proofs of Useful Work from Arbitrary Matrix Multiplication (arXiv 2504.09971v4), Abstract (2025-11-13), L17–20

Posed by

Also raised in: Reuel, Bucknall et al. (2025), Open Problems in Technical AI Governance, compute sections; Scher & Thiergart (2024), Mechanisms to Verify International Agreements About AI Development (MIRI); Proofworks, Living Verification Documents.

Sub-questions

IDSub-questionWhat the sources report
P090.1Can a verifier check, at a stated small share of job cost (a target to be agreed) and privately, that a cluster ran a declared non-AI simulation (weather/CFD/protein folding) or other declared use?open
P090.2Is matmul proof-of-useful-work provably secure (Komargodski-Weinstein conjecture), and can PoW/memory protocols give strong guarantees?open

Possibly relevant work found by automated search

Found by AI agents searching for this problem's sub-questions, mostly by keyword and citation in the OpenAlex scholarly database and on the web; a second AI pass reviewed each one, and we spot-checked some by hand. They seemed reasonably related, as far as one can tell from outside each paper's field. Some come from neighbouring fields, such as arms control and financial audit, and bear on the problem by analogy. Not reviewed against the status above; a paper listed here does not change that status. 928 of 1052 quotes checked word for word against the paper's text.

For P090.1: Can a verifier check, at a stated small share of job cost (a target to be agreed) and privately, that a cluster ran a declared non-AI simulation (weather/CFD/protein folding) or other declared use?

For P090.2: Is matmul proof-of-useful-work provably secure (Komargodski-Weinstein conjecture), and can PoW/memory protocols give strong guarantees?

Data