Proofs of Useful Work from Arbitrary Matrix Multiplication

Ilan Komargodski, Omri Weinstein

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 h…