We revisit the longstanding open problem of implementing Bitcoin'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.

Our main result is a PoUW for the task of Matrix Multiplication 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, this primitive intertwines energy (compute) , information (data) and money (security incentives) into an *atomic* way, defining a new unit of economics.

I will discuss the mechanism, it's potential economic implications, and its inspiration from Mark's influential work in the intersection of Information Theory, Economics and distributed computing.

Joint work with Ilan Komargodski and Itamar Schen.