Proofs of Useful Work from Arbitrary Matrix Multiplication

我们重新探讨了一个长期悬而未决的开放性问题，即在真正无需许可（permissionless）的环境中，基于现实世界的计算任务 \( T(x) \)（而不是人工随机哈希）实现中本聪的工作量证明（PoW）共识机制，其中矿工本身可以选择输入 \( x \)。设计这样一种有用工作量证明（Proof-of-Useful-Work, PoUW）协议的主要挑战在于，利用 \( T(x) \) 的原生计算生成一个具有规定难度的工作量证明证书，同时确保其计算开销仅比 \( T(\cdot) \) 的最坏情况复杂度高出可忽略不计的程度——这保证了恶意矿工无法通过欺骗验证者以更高概率接受其证明来“操纵系统”（同时使用相似的计算资源）。实际上，对于任何任务 \( T \)，获得一个具有 \( O(1) \)-factor 开销的 PoUW 是微不足道的，但也是无用的。 我们的主要成果是一种针对任意矩阵乘法任务 \( MatMul(A,B) \) 的 PoUW 协议，其计算开销仅比朴素矩阵乘法高出 \( 1+o(1) \) 倍（即使存在目前尚不实用的快速矩阵乘法算法）。我们推测，我们的协议在安全性上是最佳的，即恶意证明者无法相对于诚实证明者获得任何显著优势。这一推测基于将协议的难度归约到求解一批低秩随机线性方程组的任务，该任务本身具有独立的研究价值。 由于矩阵乘法是人工智能计算以及无数行业规模应用的瓶颈，这一原语提出了一种新型 L1 基础层协议的具体设计方案，几乎可以消除比特币挖矿带来的能源浪费——允许 GPU 用户通过“复用”其计算能力来进行区块链共识，从而降低他们的 AI 训练和推理成本，并以区块奖励作为回报（一举两得）。这条区块链目前正在建设中。

论文试图解决将Nakamoto共识机制中的工作量证明（PoW）替换为基于实际计算任务的有用工作量证明（PoUW）的问题，特别是在矩阵乘法任务MatMul(A,B)中实现这一目标。这是一个长期开放的问题，旨在减少比特币等区块链系统的能源浪费，并使计算资源能够用于实际应用，例如AI训练。

论文提出了一种针对矩阵乘法任务的PoUW协议，其计算开销仅比直接执行矩阵乘法高出1+o(1)倍。这种协议不仅保留了传统PoW的安全性，还确保恶意矿工无法通过额外优化获得显著优势。关键在于将协议安全性归结为求解一批低秩随机线性方程组的难度问题，从而提供理论保障。

论文的核心贡献在于实现了接近最优的计算开销，并且适用于任意矩阵乘法任务。此外，作者强调该协议在AI计算和工业级应用中的潜力，可以大幅降低GPU用户的训练和推理成本。实验部分未明确提及具体数据集或开源代码，但提出了一个值得深入研究的方向：如何进一步验证恶意矿工的优势限制以及扩展到其他计算密集型任务。未来可以探索更多实际场景下的部署效果。

相关研究包括早期的PoUW设计尝试，例如Filecoin（存储证明）和Primecoin（寻找素数链）。此外，近期的研究如《Proofs of Useful Work over Blockchains》探讨了更广泛的计算任务作为PoW基础的可能性。关于矩阵乘法优化的研究，如Strassen算法和Coppersmith-Winograd算法，虽然理论上提供了更快的方法，但在实践中尚未广泛应用。其他类似的工作还包括《Useful Proof-of-Work for Blockchains via Function Inversion》和《Verifiable Delay Functions from Matrix Multiplication》。