Proofs of useful work for capacity accounting

How it works

Proofs of work. A proof of work gives confidence that some declared amount of computation took place. In cryptocurrency mining, workers hash variants of a message until one hash meets a target, and a verifier can check it quickly ⁸. Scher and Thiergart note that applying proof of work "could verify that compute declared to be doing crypto mining is indeed doing it", as one way to check that known compute is not used for a large training run ⁸.

Proofs of useful work. A proof of useful work (PoUW) makes that computation serve another purpose. Ball et al. first presented proofs of work based on Orthogonal Vectors, 3SUM and All-Pairs Shortest Path as useful ⁷. Their revised version, published at CRYPTO 2018, drops that claim, because reviewers pointed out that a naive construction already meets the paper's definition of useful work ^{1 7}. Komargodski and Weinstein give a PoUW for arbitrary matrix multiplication, which lets the miner choose its own matrices ¹. Their protocol works in three steps ¹:

1. Low-rank random "noise" matrices are derived from public randomness and added to the inputs.
2. The noised product is computed in blocks, and the transcript of intermediate blocks is hashed.
3. A hash below a difficulty threshold is a winning proof.

The noise can then be subtracted cheaply to recover the useful product ¹. Hardness rests on the transcript rather than the output, so choosing trivial matrices gives no shortcut ¹.

Pearl's variant. Pearl's floating-point specification adapts this to FP8 matrix multiplication on GPUs ²:

• quantising after the noise is added lets output tiles be hashed directly;
• the verifier "checks one tile of the matmul, never the whole product", recomputing it bit for bit ².

Use for capacity accounting. Attestable proposes proof-of-work accounting to bound compute available for unmonitored activity ⁶. In its motivating case, every inference proof from a datacenter is correct, yet the operator could still be using spare capacity "to run an unauthorized training job" ⁶. In its scheme, "Useful, approved inference contributes to the required work budget". When demand falls short, "additional protocol-defined work fills the shortfall" ⁶.

Memory analogues.

• Proofs of space require dedicating "a significant amount of disk space" ¹¹.
• A verification system design proposes filling device memory with incompressible noise and challenging random samples ¹⁰ (see Memory wiping and proofs of secure erasure).

What it establishes

What it can establish.

• A winning proof shows that the checked computation was performed on inputs committed through the noise derivation. Total work is estimated statistically from the win rate ^{1 2}.
• If the verifier knows the capacity of declared hardware, a sustained rate of such proofs could bound the capacity left for other work. This is Attestable's proposal ⁶, and it bears on whether declared hardware runs inference, not training.
• The useful-work total must approach the available capacity over the same interval. For one covert reinforcement-learning strategy, a March 2026 Alignment Forum post by joshc lists proof of work or memory that accounts for more than 95% of computation as one of three alternative countermeasures. That threshold is a scenario estimate, not a measured result ⁹.

What it cannot establish.

• Undeclared hardware. Attestable states that a proof "cannot discover a datacenter that was never declared" ⁶.
• What the work was for. The proof does not show which AI workload, if any, the matrices came from. In Komargodski and Weinstein's construction the miner chooses the matrices ¹. On Pearl's network, an independent study found that verification "does not check whether the matrices originate from an AI model" ⁵. Attestable proposes pairing work accounting with proofs of inference for that ⁶.

Threat model

The adversary is a miner who tries to produce accepted proofs faster than honest work would allow ¹. Security holds in the random-oracle model under a "direct-product" hardness assumption about intermediate values of multiplying random low-rank matrices ¹. Pearl's variant assumes that computing quantised products of noised matrices "is not substantially easier" than computing quantised products of matrices with generic random rows ². For bit-exact verification it reproduces the GPU's arithmetic off the GPU with the technique of Badash et al. ².

For capacity bounding, the verifier also needs "a credible estimate of the compute available" to the actor ⁶.