💻 computer science

A Complexity-Theoretic Approach to Proofs of Space

本文提出了一个构建安全空间证明（Proof of Space, PoS）的基础框架，该框架不依赖于随机预言模型，并证明了此类协议可以通过结合标准密码学假设（如抗碰撞哈希函数或 SNARG）与特定的去随机化复杂度假设来构建。

原作者： Marshall Ball, Jiaxin Guan

发布于 2026-08-11

📖 1 分钟阅读☕ 轻松阅读

原作者： Marshall Ball, Jiaxin Guan

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

伟大的数字存储大劫案

想象一个你可以证明自己拥有一座庞大藏书馆，却无需展示任何一页书的世界。这就是**空间证明（Proofs of Space）**的核心概念，它属于密码学和计算机科学领域。这就像一位数字房东，想要确保租客确实有一个装满家具的仓库，而不仅仅是画了一张精巧的家具图。房东（验证者）需要确信租客（证明者）确实使用了大量的持久内存来存储数据，而不是只保存了一张写着“我有家具”的小纸条，然后在被问及时才神奇地变出家具。

多年来，构建这些数字仓库的唯一方法依赖于一个被称为“随机预言机（Random Oracle）”的魔法、虚构工具。把它想象成一个神奇的黑匣子，每当你提问时，它都会吐出完美随机且不可预测的答案。虽然这对理论研究很有用，但这就像是在纯粹的魔法基础上盖房子；我们不知道它在现实世界中是否站得住脚。科学家们面临的大问题是：我们能否仅利用真实的、物理层面的计算法则，而不依赖于魔法盒，来构建一个安全的空间证明？本文正是利用复杂度理论（研究问题解决难度的学科）的工具，深入探讨了这个问题，试图从零开始构建这些证明。

论文的核心思想：“深层”字符串

作者 Marshall Ball 和 Jiaxin Guan 提出了一个新的基础框架，用于构建不依赖魔法的空间证明。他们的主要发现是，如果你拥有两个特定的要素，你就可以创建这些证明：一个密码学假设（例如抗碰撞哈希函数）和一个“去随机化（derandomization）”假设（即关于强大的非确定性机器处理某些计算机问题有多难的信念）。

要理解他们的技巧，想象你需要证明你拥有一大堆乱七八糟的沙子（数据）。旧的方法需要一个魔法盒来保证沙子无法被压缩。作者意识到，在现实世界中，我们不需要沙子是不可能被压缩的；我们只需要它难以被快速压缩。

他们引入了**计算深度（Computational Depth）**的概念。把一段数据字符串想象成一个故事。

设置阶段： 证明者拿取一个微小的种子（一个短篇故事梗概），并花费很长时间（第一阶段）将其扩展成一部宏大且细节丰富的长篇小说（数据）。
陷阱： 验证者随后会要求查看那部小说中的特定页面。
圈套： 如果证明者并没有真正写完整部小说，而只是保留了那个短小的梗概，那么他们就需要从头开始重写这些页面。但验证者给他们的时间非常短暂（第二阶段）。

作者表明，如果我们假设某些难题确实存在（具体来说，是某些问题对于“非确定性”电路来说求解过快），那么就可以创建一个将短种子转化为长字符串的函数。这个字符串是“深层”的：如果你有充足的时间，可以从短种子生成它；但如果你赶时间，就无法从短种子中重建它。这就像一个谜题，解开它需要一年时间，但验证它只需要一分钟；如果你试图在一分钟内解决它，你根本做不到。

证明是如何运作的：“默克尔树”与“魔法咒语”

论文概述了一个用于测试这种“深度”的两步协议。

第一阶段：设置（漫长的等待）
验证者向证明者发送一个随机种子。证明者花费很长时间（例如数小时），使用他们特殊的“深层”函数将该种子转化为一个海量的数据文件。然后，他们在这些数据之上构建一棵默克尔树（Merkle Tree）。把默克尔树想象成整个文件的数字指纹。它就像一棵家族树，每个叶子都是一段数据，而每个分支都是下方两个分支的哈希值（唯一的数字指纹）。在最顶端是一个单一的“根（Root）”哈希，代表了整个文件。证明者存储这个庞大的文件以及这个根哈希。

第二阶段：检查（快速测验）
验证者突然要求提供文件中的特定页面（随机索引）。证明者必须迅速提供这些页面，以及通过默克尔树路径证明这些页面属于原始文件的路径。

在这里，作者的聪明才智得以体现。为了防止证明者尝试绕过协议（即通过只保留短种子并尝试猜测页面），他们添加了一个简洁论证（Succinct Argument）（一个短小的证明）。

选项 A（更强的假设）： 他们使用一种“SNARG”（一种非常短的、非交互式的证明）来证明他们发送的根哈希确实是由该种子生成的。这需要关于存在某些密码学工具的强假设，但它能保持较低的存储开销。
选项 B（更弱的假设）： 他们使用基于抗碰撞哈希函数的“Kilian 式”论证。这是一种更标准、更“安全”的假设，但它会迫使诚实的证明者存储更多的数据（一个“PCP”字符串）来证明默克尔树构建正确。

他们否定了什么，又证明了什么

论文明确反对了认为空间证明必须依赖于随机预言机模型的观点。他们表明，“魔法盒”并不是必需的。相反，他们证明了，如果我们接受“去随机化假设”（即某些问题对于非确定性电路来说很难），那么空间证明是可能的。

他们还针对一种试图绕过协议的具体尝试进行了讨论：如果证明者存储极少量的数据，并试图在运行过程中“压缩”大文件会怎样？作者证明，如果证明者能够说服验证者接受，那么他们必须存储大量的数据。具体而言，他们表明，如果一个试图绕过协议的证明者想要成功，其存储的数据量不能显著低于诚实证明者的存储量（例如，如果诚实证明者存储 $N$ 比特，那么试图绕过协议的证明者所能存储的数据量，取决于所使用的具体构造，也不会比 $N$ 比特少多少）。

总结

本文并不声称已经构建出了今天就能安装在你智能手机上的商业产品。相反，它提供了一个理论蓝图。它证明了这样一个“不可能”的任务——在没有魔法的情况下证明你拥有一个数据仓库——实际上是可能的，只要我们接受关于计算机问题难度的某些标准信念。

他们展示了：

它是有效的： 你可以使用“计算深度”而非魔法来构建这些证明。
它是高效的： 诚实的用户不需要做过于疯狂的事情，尽管他们确实需要存储数据。
它是安全的： 如果有人试图通过存储更少的数据来绕过协议，数学会告诉我们，只要底层的难题依然成立，他们几乎肯定会被抓个正着。

简而言之，Ball 和 Guan 将“空间证明”从魔法黑匣子的领域中带了出来，将其牢牢植根于复杂度理论的土壤之中，向我们展示了只要有了正确的假设，我们可以构建出像计算法则所允许的那样安全的数字仓库。

技术摘要：空间证明（Proofs of Space）的复杂度理论方法

问题陈述
空间证明（PoS）由 Dziembowski 等人 [DFKP15] 提出，是一种两阶段协议，允许证明者（Prover）向高效的验证者（Verifier）证明其分配了大量的持久内存。该协议由一个初始化阶段（持续时间长）和一个执行阶段（持续时间短）组成；在初始化阶段，证明者存储数据；在执行阶段，验证者向证明者发起挑战，以证明数据仍然被存储。

现有 PoS 协议的一个关键局限在于，其安全性证明高度依赖于**随机预言机模型（Random Oracle Model, ROM）**或特设的密码学假设。具体而言，它们依赖于随机预言机查询的同步不可压缩性（incompressibility）与可提取性（extractibility）。迄今为止，尚未发现已知能仅基于标准密码学假设在纯模型（plain model，即不使用随机预言机）下实现安全的构造。目前缺乏关于密码学哈希函数且足以支撑此类构造可证明安全性的、清晰且可证伪的假设。

方法论与框架
本文提出了一个通过结合去随机化假设（derandomization assumptions）与密码学假设（cryptographic assumptions），在纯模型中构建 PoS 的基础框架。核心见解在于，PoS 需要一个字符串 $\sigma$ ，它在逻辑上存在悖论：既可以从一个短描述中（在足够的时间 $T$ 下）被压缩，又无法从任何稍短的描述中（在短时间 $t$ 内）被重建。

作者利用复杂度理论中的**计算深度（computational depth）**概念（由 Antunes 等人 [AFvMV06] 引入）将此进行了形式化。他们寻求一个具有高计算深度的函数 $f$ ：

长时可压缩性： $f(x)$ 可以从短种子 $x$ 在时间 $T$ 内计算得出。
短时不可压缩性： 即便给定 $x$ ，在时间 $t$ 内，无法从任何比 $|f(x)|$ 更短的描述中重建 $f(x)$ 。

该构造过程分为三个步骤：

构造高深度函数：
作者利用了针对非确定性区分器（nondeterministic distinguishers）的种子扩展伪随机生成器（PRGs）。在假设 $E = \text{DTIME}[2^{O(n)}]$ 需要指数级规模的非确定性电路（这是证明 $\text{AM} = \text{NP}$ 的标准假设）的前提下，他们构造了对非确定性电路具有难度的 PRG。
- 为了实现**极高概率（overwhelming probability）的不可压缩性（而非仅仅是显著的误差），他们使用了乘法 PRG（multiplicative PRGs）**来对抗非确定性区分器。这类 PRG 能够保持忽略事件（negligible events）的概率，确保 PRG 的输出以极高概率保持不可压缩。
- 为了处理近似不可压缩性（即对汉明距离误差的韧性），他们将 PRG 与**列表可解码纠错码（list-decodable ECC）**进行组合。这确保了即使对手恢复出一个接近 $f(x)$ 的字符串，原始字符串仍然保持不可压缩。
提取引理（The Extraction Lemma）：
该研究的核心技术贡献是提取引理（Lemma 11）。它指出，如果一个证明者能够维持一个较小的状态 $S$ ，并能以非忽略概率成功回答验证挑战，那么底层的字符串 $y = f(x)$ 则是近似可压缩的。
- 该引理使用**命中集生成器（Hitting Set Generator, HSG）**来确定性地选择一组“有用的”挑战索引，这些索引覆盖了存储字符串的大部分。
- 这使得提取器能够在时间 $t$ 内，从证明者的微小状态中恢复出 $y$ 的大部分比特，从而与 $f$ 的假设不可压缩性相矛盾。
协议实例化：
该框架被实例化为两种特定的 PoS 协议，二者在密码学假设和存储开销上有所不同：
- 构造 1（基于 SNARG）： 使用**半通用非交互式参数（Semi-Universal Non-Interactive Argument, SNARG）**作为 $P$ 。证明者存储 $f(x)$ 的 Merkle 根以及一个证明该根对应于 $f(x)$ 的简洁证明。这依赖于存在针对 $P$ 的 SNARG（一个强假设），但为诚实证明者提供了近乎最优的存储量（ $N$ 比特）。
- 构造 2（基于 Kilian）： 使用基于 PCP 和**碰撞抵抗哈希函数（CRHF）**的 Kilian 交互式参数系统。证明者必须存储计算 $f(x)$ 的 PCP 字符串，这导致了更高的诚实存储需求（ $N + \tilde{O}(T)$ ），但依赖于较弱的密码学假设（CRHF + 去随机化）。

主要结果
本文确立了以下定理（非正式表述）：

定理 1： 假设 $E$ 对指数级规模的非确定性电路是困难的，则存在显式的函数，其对于时间 $t$ 是不可压缩的，大小为 $N - O(\rho N \log(1/\rho))$ 。
定理 2（SNARG 实例化）： 假设 $E$ 对指数级规模的非确定性电路是困难的、存在单向函数，且存在针对 $P$ 的半通用 SNARG，则存在一种 PoS，其中诚实证明者存储 $N$ 比特，且该方案对于使用 $(1-o(1))N$ 比特的任何证明者都是安全的。
定理 3（CRHF 实例化）： 假设 $E$ 对指数级规模的非确定性电路是困难的且存在碰撞抵抗哈希函数，则存在一种 PoS，其中诚实证明者存储 $N$ 比特，且该方案对于使用 $N^{1/c}$ 比特（对于某个常数 $c$ ）的任何证明者都是安全的。

意义与主张
作者强调，他们的工作为在纯模型中实现 PoS 提供了一个具有教学意义的、通用的可行性结果。

打破 ROM 壁垒： 他们证明了无需随机预言机，仅依靠标准的去随机化假设（ $E$ 对非确定性电路的困难性）结合标准密码学原语，即可构造出 PoS。
权衡（Trade-offs）： 论文强调了密码学假设与存储效率之间的权衡。基于 SNARG 的方法最小化了诚实证明者的存储，但需要更强的假设。基于 Kilian 的方法使用了较弱的假设（CRHF），但要求诚实证明者存储计算的 PCP，从而增加了存储量。
局限性： 作者明确表示，他们的重点在于理论上的可行性，而非复杂的威胁模型或实际协议。他们指出，虽然其框架产生了 PoS，但目前尚不清楚如何应用这些想法来构造内存硬函数（Memory-Hard Functions, MHFs）——这是通常由基于 ROM 的 PoS 推导出的相关对象。此外，他们承认，处理组合性（单个证明者与多个验证者的交互）仍需进一步研究，以确保存储成本不会被摊薄。

总而言之，这项工作架起了复杂度理论与密码学协议之间的桥梁，表明实现 Proofs of Space 所需的“硬度”可以从基础的去随机化假设中获得，而非依赖于启发式的随机预言机模型。

伟大的数字存储大劫案

论文的核心思想：“深层”字符串

证明是如何运作的：“默克尔树”与“魔法咒语”

他们否定了什么，又证明了什么

总结

技术摘要：空间证明（Proofs of Space）的复杂度理论方法

类似论文