Prof Omri Weinstein - Proofs of Useful Work from Arbitrary Matrix Multiplication

We revisit the longstanding open problem of implementing Nakamoto’s proof-of-work (PoW) consensus using 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 core challenge in designing such a Proof-of-Useful-Work (PoUW) protocol is to use the native computation of T(x) to produce a PoW certificate with minor overhead over T(|x|), ensuring malicious miners cannot “game the system” by fooling the verifier into accepting their work with higher probability. Indeed, obtaining a PoUW with constant-factor (O(1)) overhead is trivial for any task T, but also useless from a security standpoint.

Our main result is a PoUW for the task of matrix multiplication MatMul(A, B) of arbitrary matrices, with only a 1 + o(1) multiplicative overhead compared to naïve matrix multiplication. Since MatMuls are the backbone of AI training and inference, our primitive suggests a concrete blueprint for a new base-layer blockchain protocol that nearly eliminates the energy waste of Bitcoin mining, allowing GPU users to offset AI costs by “re-using” their computations for blockchain consensus—in exchange for block rewards ("2-for-1"). We will briefly discuss the market dynamics of this new decentralized financial system, where both data and compute are required to efficiently mine the network.