# Proofs of Useful Work from Arbitrary Matrix Multiplication

arXiv: https://arxiv.org/abs/2504.09971 · HTML: https://mlsanity.com/paper/2504.09971/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2025.

## Built on by (most cited first, 1 of 1)

- [SEDULity: A Proof-of-Learning Framework for Distributed and Secure Blockchains with Efficient Useful Work](https://mlsanity.com/paper/2512.13666/) (2025)

## Abstract (arXiv)

We revisit the longstanding open problem of implementing Nakamoto's proof-of-work (PoW) consensus based on a real-world computational task T(x) (as opposed to artificial random hashing), in a truly permissionless setting where the miner itself chooses the input x. The challenge in designing such a Proof-of-Useful-Work (PoUW) protocol, is using the native computation of T(x) to produce a PoW certificate with prescribed hardness and with negligible computational overhead over the worst-case complexity of T(·) -- This ensures malicious miners cannot ``game the system" by fooling the verifier to accept with higher probability compared to honest miners (while using similar computational resources). Indeed, obtaining a PoUW with O(1)-factor overhead is trivial for any task T, but also useless. 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 naive MatMul (even in the presence of Fast Matrix Multiplication-style algorithms, which are currently impractical). We conjecture that our protocol has optimal security in the sense that a malicious prover cannot obtain any significant advantage over an honest prover. This conjecture is based on reducing hardness of our protocol to the task of solving a batch of low-rank random linear equations which is of independent interest. Since MatMuls are the bottleneck of AI compute as well as countless industry-scale applications, this primitive suggests a concrete design of a new L1 base-layer protocol, which nearly eliminates the energy-waste of Bitcoin mining -- allowing GPU consumers to reduce their AI training and inference costs by ``re-using" it for blockchain consensus, in exchange for block rewards (2-for-1). This blockchain is currently under construction.