הכנס הארצי למדעי המחשב והמידע

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 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(⋅) — 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 MatMul(A,B) of arbitrary matrices with 1+o(1) multiplicative overhead compared to naive MatMul. We conjecture that our protocol has optimal security in the sense that a malicious prover cannot obtain any significant advantage over an honest prover.

We will discuss two hardness conjectures, based on batch random linear equations, and on SETH. This leads to a new notion of succinct random self-reducibility of functions which may be of independent interest.