Proofs of Useful Work from Arbitrary Matrix Multiplication
Omri Weinstein
Abstract:
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 negligible overhead over T(|x|), ensuring malicious miners cannot “game the system” by fooling the verifier into accepting their work with higher probability. Indeed, 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.
Joint work with Ilan Komargodski and Itamar Schen. Project discussion on X: https://x.com/DesheShai/status/1934583423122788454
Bio:
Omri is an Associate professor in the theoretical computer science group at the Hebrew University (on leave from Columbia University). He is broadly interested in the interplay between data structures, information theory and optimization, especially in understanding the complexity and the role of dynamic data structures in accelerating iterative optimization and high-dimensional search. He obtained his PhD from Princeton University and was a Simons Society Junior Fellow at Courant Institute (NYU).