我们重新探讨了一个长期悬而未决的开放性问题,即在真正无需许可(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 训练和推理成本,并以区块奖励作为回报(一举两得)。这条区块链目前正在建设中。