Welcome to the resource topic for 2025/685
Title:
Proofs of Useful Work from Arbitrary Matrix Multiplication
Authors: ilan komargodski, Itamar Schen, Omri Weinstein
Abstract: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(\cdot) – 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 \mathsf{MatMul}(A,B) of arbitrary matrices with 1+o(1) multiplicative overhead compared to na"ive \mathsf{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 $\mathsf{MatMul}$s 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.
ePrint: https://eprint.iacr.org/2025/685
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .