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. gave constructions for problems such as Orthogonal Vectors, 3SUM and All-Pairs Shortest Path ⁷. 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 valid proof of useful work shows that a stated amount of matrix-multiplication work was performed on inputs committed through the noise derivation ^{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 This compute runs inference, not training, Declared hardware is idle or shut down and There is no undeclared relevant compute for declared hardware.
• The useful-work total must approach the available capacity over the same interval. JoshC argues that more than 95% of computation must be accounted for to constrain one covert reinforcement-learning strategy. 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 ⁶.

Limitations

Verification cost. Komargodski and Weinstein note that plain verification is "relatively expensive on the verifier's side". They suggest that the prover compute a SNARK to lighten it, or a zkSNARK if the matrices must stay private ¹. They also note that storing the transcript takes significant memory ¹.

Known shortcuts. Pearl lists known mining speedups: crafted inputs, precision shortcuts, seed grinding and work reuse. It adds checks to limit them ². It describes faster kernels or hardware as "not an attack on the protocol" ².

Assumptions and scope. Open problems include PoUW from more standard assumptions, and PoUW for tasks beyond matrix multiplication ¹.