Proofs of Useful Work from Arbitrary Matrix Multiplication with Omri Weinstein скачать в хорошем качестве

Proofs of Useful Work from Arbitrary Matrix Multiplication with Omri Weinstein

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/ Read more of our work: a16zcrypto.com