We sift through the news so you don’t have to
Editor’s note: In this regular news segment, we focus on the signal vs. the noise across various media sources — traditional media outlets, industry announcements, and debates online — to help you
AI systems are breaking an internet that was designed at human-scale — by making it cheaper than ever to coordinate, transact, and generate voice, video, and text that are increasingly indistinguishable from human activity. We’re already beset w
Omri Weinstein (Hebrew University) revisits 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”). Omri briefly discusses 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.
About the presenter
Omri is an Associate Professor in the theoretical computer science group at the Hebrew 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).
About a16z crypto research
a16z crypto research is a multidisciplinary lab that works closely with our portfolio companies and others toward solving the important problems in the space, and toward advancing the science and technology of the next generation of the internet.
More about us: a16z.com/2022/04/21/announcing-a16z-crypto-research
More from the a16z crypto team
Subscribe to our ‘web3 weekly newsletter’: a16zcrypto.substack.com
Listen to our ‘web3 with a16z’ podcast: a16zcrypto.com/web3-with-a16z-podcast/
