【第646期】PoUW：基于矩阵乘法的有用功证明方案

Seventy3：借助NotebookLM的能力进行论文解读，专注人工智能、大模型、机器人算法、crypto方向，让大家跟着AI一起进步。

如果你想要解读自己的论文，获得更多曝光度。请联系小助手微信：seventy3_podcast 加群。
合作邮箱：zhiwudazhanjiangshi#gmail.com

今天的主题是：

Proofs of Useful Work from Arbitrary Matrix Multiplication

Summary

我们重新审视了一个长期存在的开放性问题：在矿工自身选择输入 x 的真正无许可（permissionless）环境中，如何基于现实世界中的计算任务 T(x)（而非人为构建的随机哈希）来实现中本聪的共识。设计此类“有功证明”（Proof-of-Useful-Work, PoUW）协议的挑战在于，如何利用 T(x) 的原生计算来生成具有指定难度的证明证书，且该证书相较于 T(⋅) 的最坏情况复杂度而言，其计算开销可以忽略不计——这能确保恶意矿工无法通过欺骗验证器，在消耗同等计算资源的情况下获得比诚实矿工更高的接受概率来“操纵系统”。事实上，对于任何任务 T，获得一个具有 O(1) 倍开销的 PoUW 是轻而易举的，但这也毫无用处。

我们的核心成果是针对矩阵乘法任务 MatMul(A,B)（针对任意矩阵）提出的一种 PoUW 协议。与朴素的 MatMul相比，该协议仅带来 1+o(1) 的乘法开销（即使在存在目前尚不实用的快速矩阵乘法类算法的情况下依然成立）。我们推测我们的协议具有最佳的安全性，即恶意证明者无法获得相比诚实证明者的任何显著优势。该推测基于将我们协议的难度归约至求解一批低秩随机线性方程组的任务，这一任务本身也具有独立的学术价值。

由于矩阵乘法是大模型等 AI 计算以及无数工业级应用的瓶颈，该原语为设计一种全新的 L1 基础层协议提供了具体的方案。它几乎消除了比特币挖矿带来的能源浪费——允许 GPU 用户通过将计算“复用”于区块链共识来换取区块奖励（一举两得），从而降低其 AI 训练和推理成本。该区块链目前正在构建中。

原文链接：https://arxiv.org/abs/2504.09971