基于LWE的可并行委托证明：SPARG构造与应用

### 基于 LWE 的可并行委托证明：SPARG 构造与应用 在计算证明领域，可并行委托证明系统（SPARG）是一个重要的研究方向。它能够在保证证明有效性的同时，显著提高证明的计算效率，尤其适用于资源受限的场景。本文将详细介绍 SPARG 的构造方法及其在不同计算场景下的应用。 #### 1. 相关概念基础 - **PCP 与 IOP**：PCP（概率可检验证明）是一种证明系统，Ben - Sasson 和 Sudan 首次构造了具有准线性开销的 PCP，即对于 t 时间的计算，其 PCP 总大小为 t · polylog(t)。IOP（交互式预言机证明）是 PCP 的多轮扩展，在委托协议中很有用，已有工作得到了线性大小的 IOP，但证明者仍需至少准线性时间运行。 - **证明并行性**：此前的工作引入了在计算的同时并行计算证明的技术，以提高证明者的并行效率。最初应用于可验证延迟函数中的迭代顺序函数，后来有工作将其通用地应用于任意计算，但通用转换需要交互或依赖非交互场景下的 SNARK。 #### 2. SPARG 构造概述 我们的构造基于 RAM 计算模型。RAM 机器 M 可以随机访问内存中的字符串 D，并维护一个小的本地状态。在每个计算步骤中，M 读取或写入内存位置并更新本地状态。当 M 的初始内存包含 x 时，若经过 t 步后本地状态有特殊停止符号且 y 被写入内存，则称 M(x) 在 t 步内输出 y。RAM 机器在任何计算步骤的配置 cf 由其内存和本地状态组成，能完全描述该点的计算。 #### 3. 基于 LWE 的 SPARGs 构造 ##### 3.1 SPARK 构造 SPARK 构造（EFKP 构造）依赖于 NP 的 SNARK。为证明 M(x) = y 在 t 步内成立，目标是让 SPARK 证明者在最多 t + polylog t 时间内运行。EFKP 的高层方法是将计算拆分为子计算，并在计算和证明后续步骤的同时，为每个子计算并行给出 SNARK 证明。 例如，若底层 SNARK 需要 2k 时间来证明 k 步的 RAM 计算，那么在时间 t 内可计算和证明的最大计算部分是 k = t/3。可以用 t/3 时间计算这些步骤，再用 2t/3 时间证明其正确性，从而在时间 t 得到前 t/3 步的证明 π1。这个想法可以递归应用，最终完整的 SPARK 证明由 O(log t) 个 SNARK 证明组成，所有证明都在时间 t 内完成。 然而，该方法仅适用于有界内存大小的计算。因为它需要对 RAM 计算的中间状态进行证明，而中间状态的大小与内存大小相关，所以 SNARK 证明这些陈述的时间也会依赖于内存大小。 为解决这个问题，EFKP 提出证明者可以维护一个可更新的摘要 rt 来表示任意时间步的配置，并证明存在根据 M 对 rt 进行的 k 次更新，最终得到 rt′。摘要对应于基于抗碰撞哈希函数的每一步内存的 Merkle 树，每次 M 读写内存时，对 Merkle 树进行相应更新。在计算结束时，证明者可以根据最终摘要打开输出 y 的位，验证者可以高效检查。 ##### 3.2 从 SPARK 到 SPARG 的转换 EFKP 构造依赖于底层的知识论证，而构造 SPARG 的自然方法是将底层的 SNARK 替换为 SNARG，并尝试证明 P 中计算的正确性。 假设存在一个对手 A 成功说服验证者接受一个错误陈述 (M, x, t, y)，其中 M(x) ≠ y。按照 EFKP 构造，A 输出子证明 π1, …, πm，第 i 个子证明证明 M 从摘要 rti - 1 到摘要 rti 在若干步内转换。理想情况下，如果陈述本身错误，那么必然有一个子证明对应错误陈述，从而破坏底层 SNARG 的正确性。但实际情况并非如此，因为如果其中一个子证明的哈希函数存在碰撞，所有子证明都可能对应正确陈述。 此前的证明依赖于 SNARK 的可提取性来证明如果所有子陈述都正确，那么对手 A 必然能在计算分叉点产生哈希碰撞，这与事实矛盾。但如果仅依赖 SNARG，我们无法提取碰撞来得出矛盾。 不过，我们只需要证明确定性计算的正确性，这是相对于 EFKP 方法的一个优势。给定 M 和 x，我们可以在多项式时间内计算出真正的更新序列，从而确定计算在哪个子证明中分叉。 这种证明正确性的方法成功的关键在于底层 SNARG 满足以下性质：没有多项式时间概率对手 A 能产生证明 π、M 的计算记录、摘要 rt、rt′和若干步骤 k，使得 (a) 验证者接受 π 作为 (M, rt, rt′, k) 的证明，(b) rt 是计算开始时的正确摘要，但 (c) rt′不是 k 步后正确的结果摘要。这个定义实际上是 RAM 委托方案的正确性概念。 ##### 3.3 从 RAM 委托到 SPAR