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."
Posed by
- Kulp et al. (2024), Hardware-Enabled Governance Mechanisms (RAND WR-A3056-1):
it’s unclear whether privacy-preserving and intellectual property–preserving solutions exist for enough workloads
(Ch. 6, Potential limitations, p.47; L2367–2368) (source states the problem but not the quantity the question asks for)
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
| ID | Sub-question | What the sources report |
|---|---|---|
| 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? | open |
| P090.2 | Is 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
- problems.csv — one row per problem
- problem_status.csv — status, scope and evidence per problem
- problem_sources.csv — the posed-by quote and other documents per problem
- leaves.csv — all sub-questions, including those without a checkable form
- leaf_sources.csv — every source row behind each sub-question