0x00 Abstract
在将计算委托给服务提供商时，我们寻求一些保证，即输出正确、完整。 Y et 重新计算输出是低效和昂贵的，甚至不可能在本地存储所有数据。因此，我们的对流（次线性空间）用户可以验证他们感兴趣的是什么，他们不能存储完整的输入或执行完整的计算。我们在这项工作中的目标是促进最近关于证明系统的工作，其中服务提供商向用户证明其输出的正确性。目标是最小化双方在生成和检查证明方面的时间和空间成本。到目前为止，这些系统的功能非常有限，直到最近才试图实现这能非常有限
在这里，我们的方法是双重的。首先，由于 Goldwasser、Kalai 和 Rothblum [19]我们描述了精心挑选的最有效的通用结构之一，用于任意计算（流动或其他方法）。这了将方法从理论结果转化为实际可能性，需要一些新的见解和改进。我们的主要贡献是实现一个 O(S(n) log S(n)) 时间内运行的证明器，包括 S(n) 是计算感兴趣函数的算术电路的大小；这与 [19] 承诺的证明人 poly(S(n)) 与运行相比是有利的。我们的实验结果表明，用于验证计算的实用通用协议可能比以前更接近现实
其次，我们描述了一组可以微调针对流和数据库处理中特定重要问题的协议的技术，以实现真正的可扩展性。我们特别关注从矩阵向量乘法到两点完美匹配的非交互协议，我们以前的工作 [8, 15] 在通信成本和用户工作记忆的基础上，实现了几乎线性时间运行的证明器。现有技术需要(基本上)证明者的超线性时间。最后，我们基于最初的原因 Shen [34] 线性化技术为特定问题开发了改进的交互协议。我们认为，即使通用方法得到改进，微调协议在现实世界的关键问题环境中仍然很有价值，因此需要特别注意具体问题。
1 Introduction
云计算解决方案的一个明显障碍是信任问题。在本文中，我们特别关注对外包计算完整性的信任。如果我们使用服务提供商存储大型数据集，并要求他们计算数据集，提供商如何说服我们正确执行计算？即使假设一个非恶意的服务提供商，错误的算法实现、磁盘故障或内存读取错误也并不少见，特别是在处理大量数据时
理论界特别关注的自然方法是要求服务提供商提供证明和查询答案。使用证明系统术语[2]，我们将用户视为验证者 V，他想成为证人 P 的服务提供者的帮助下解决问题。在 P 回答后，双方就符合下列属性的既定协议进行对话：诚实的证人总是说服证人接受结果，而任何不诚实或错误的证人几乎肯定会被证人拒绝。该模型在有关交互式证明的大量文献中产生了许多有趣的理论技术。然而，该领域的大部分基础工作都假设验证人有能力花费多种时间和资源来验证证明人声称解决了一个问题（例如 NP 完全问题)。在我们的设置中，这太多了：相反，认证人应该是高效的，理想的输入尺寸接近线性，认证人应该是轻量级的，数据尺寸的努力是次线性的
为此，我们还关注验证器在流模型中运行的结果，单次传输输入并使用少量空间。这自然适用于云设置，因为当数据上传到云时，验证者可以执行此流传输。例如，考虑到零售商，他在每笔交易发生时都会增加转发。我们将数据建模得太大，用户甚至无法将其存储在内存中，因此在收集数据时需要使用云来存储数据。以后，用户可能会要求云计算数据。然后，云作为证明者，向用户发送答案和完整性证明，记住用户的空间限制
我们认为，这种机制对于扩大云计算服务的商业可行性至关重要，允许用户和服务提供商之间的信任但验证关系。事实上，即使每个计算都没有明确的检查，只有检查计算的能力才能刺激用户使用云计算解决方案。因此，在本文中，我们关注流量验证协议的实用性
这种协议有很多相关成本。在流式设置中，主要关注验证者使用的空间和空间 P 和 V 通信量之间。其他重要成本包括证明人的空间和时间成本、验证人的运行时间和双方交换的消息总数。如果这些成本中的任何一个过高，该协议在现实世界的外包场景中都可能无用
在这项工作中，我们采取了双管齐下的方法。理想情况下，我们希望有一种通用的方法，允许我们为任何计算建立有效的协议。因此，由于 Goldwasser、Kalai 和 Rothblum 我们研究了交互式证明文献中已知最有效的通用协议之一的成本。我们描述了该协议的一个有效例子，证人比以前的工作要快得多，并提出了我们需要的一些修改，以使我们的实现可扩展。我们相信，我们实施协议的成功表明，任意计算委托的可靠、完全实用的方法比以前更接近现实
虽然令人鼓舞，但我们的一般实现对日常使用并不实用。因此，我们的第二条攻击线是通过专门协议改进一般结构，以解决许多重要问题。在这里，我们特别描述了两种技术，它们产生了比以前已知的更可扩展的协议。首先，我们展示了如何使用一些快速的傅立叶转换来获得适合当今实践的高度可扩展的非互动协议；这些协议需要
只需要从 P 到 V 没有反向通信通信的消息。其次，我们描述了如何使用多种线性方法来改进某些问题的交互协议。我们所有的工作都得到了基于我们的经验评估的支持
根据所讨论的技术和问题，我们可以看到经验结果在证明者成本方面的速度发生了变化。因此，我们认为，即使通用方法得到改进，针对关键问题的微调协议在现实世界中仍然很有价值，特别是因为它们可以用作更通用结构的原始语言。因此，具体问题需要特别注意。其他提供证明的成本是可以接受的。对于许多问题，即使输入包含数 TB 对于数据，我们的方法最多需要几兆字节的空间和通信，有些则使用较少；此外，P 和 V 时间成本与输入大小呈线性或几乎呈线性。我们的大多数协议都需要 P 和 V 多对数消息之间，但有些是非交互式的，只发送一条消息
总之，我们认为本文的贡献如下：
? [19] 精心设计的电路检查结构的一般实现和协议的一些扩展。我们相信，我们的结果表明，任意计算的实际委托协议比以前更接近现实
? 为了获得针对主要类别问题的实用专项协议，开发了强大而广泛的应用方法。经验证明，这些技术很容易扩展到数十亿更新流。
1.1 前期工作
交互式证明的概念是在大约20年前的一次活动中引入的 [3, 20, 25, 33, 34]。这最终导致了 Shamir [33] 一个著名的结果表明，具有高效互动证明的问题集是可以在多个空间中计算的问题集
然而，这些结果主要被视为关于计算复杂性的理论陈述，并没有导致实现。最近，在涉及计算委托的实际应用程序的推动下，人们对证明云正在正确运行产生了相当大的兴趣
例如，一项工作考虑了证明数据被云等外部源无误存储的方法，例如[22]
在我们的设置中，我们将验证人建模为只能通过单流传输访问数据
在此限制下，数据库社区一直致力于确保基于分组和计数的简单功能的正确执行；见[37]和参考文献。其他类似的例子包括使用 Merkle 树 [24] 验证滑动窗口数据流的查询和对流数据的连续查询 [29]
与我们最相关的是验证更复杂、更一般的输入功能。 Chakrabarti 当流验证者的概念形式化时，他必须先读取输入，然后在空间限制下读取证明。 [8] 本作者在 [15] 扩展。这些作品允许证人只向证人发送消息而不反向通信
出于类似的动机，Goldwasser 等人。 [19] 虽然他们没有在流量设置中明确显示他们的协议，但该协议实现了多种时间证明器和高效验证器来解决一个主要问题。随后，已经注意到验证器所需的信息可以通过单个初始流传递来收集，因此对于一大类统一计算，验证器仅使用多对数空间和时间进行操作。最后，Cormode 等人。 [17] 通过允许多轮交互，引入了流式交互证明的概念 [8] 在模型证明者和验证者之间。它们提出了比较 [8, 15] 单信息模型中可能的协议要便宜得多，用于解决数据库和流处理中的各种核心问题
另一项工作使用完全同态加密，以确保委托计算的完整性、隐私和可重用性 [18,12,11]。 Chung、Kalai、Liu 和 Raz [11] 他们的工作特别相关，因为他们专注于相关。他们的结果比我们强，因为他们实现了可重用的通用协议(即使是 P 知道 V 是否接受或拒绝每个证书)，但它们的可靠性保证取决于计算假设，以及由于完全相同的使用而导致的大量费用加密意味着这些协议远不实用
直到最近，人们才继续努力使用来自复杂性和密码学世界的技术来验证计算。 Bhattacharyya 实现了某些 PCP 它们可能接近实用性 [4]。在这项工作的同时，Setty 等人。 [31, 32] 可以检查证明概率 (PCP) 调查结果由初始调查结果实施 Ishai 等人提出的结构。 [21]。尽管他们的工作代表了 PCP 但我们的方法和实施取得了显著进展 [31, 32] 有几个优点。例如，我们的协议为验证人节省了空间和时间，即使在外包单独计算时， [31, 32] 只有在一次批处理数十个计算并在批处理中分摊验证者的成本时才为验证者节省时间。此外，即使我们的协议对抗计算无限的对手，也是无条件和安全的 Ishai 等人的建设。依靠密码假设获得安全保障。 Canetti 等人提出了另一种实用的方法。 [7]。他们的实现将计算委托给两个独立的证明者，并玩他们：如果他们在输出上存在差异，协议将确定他们的执行差异，并支持下一步正确遵循程序的方法，以确保任何安全保证。
1.2 预赛
定义。我们首先正式定义一个有效的协议。在这里，我们密切关注以前的工作，比如 [17] 和 [8]。
定义 1.1 考虑证人 P 和验证者 V，他们都观察流 A 并希望计算函数 f(A)。观察到流后，P 和 V 交换一系列新闻。给定证明者 P 和 V 的随机位 R 使用 out(V, A, R, P) 表示 V 在输入 A 上的输出。如果 V 不相信 P 主张是有效的，然后 V 可以输出 ⊥。
若对所有流动 A，P 是关于 V 有效证明者，
至少有一个关于 V 有效证明者 P，我们称 V 为 f 有效的验证者和所有的证明者 P0 和所有流 A，
本质上，这一定义表明，确遵循协议的证明者总是会说服 V，而如果 P 犯了任何错误或虚假声明，那么这将以至少恒定的概率被检测到
事实上，对于我们的协议，这种“误报”概率可以很容易地任意小.由于我们在流设置中首先关注的是验证者的空间需求以及协议的通信成本，因此我们做出以下定义。
定义 1.2 我们说 f 拥有一个 r-message (h, v) 协议，如果对于 f 存在一个有效的验证者 V 使得：
1. V 只能访问 O(v) 个工作记忆单词
2. V有一个有效的证明者P，使得P和V总共最多交换r条消息，所有消息的长度之和为O(h)个单词。
我们将单消息协议称为非交互式协议。我们说 r-message 协议有 dr/2e 轮。
许多证明系统中的一个关键步骤是评估某些数据在多个点上的低度扩展。也就是说，数据被解释为隐含地定义了一个多项式函数，该多项式函数与范围 1 上的数据一致。 . . n，并且也可以在此范围之外的点处进行评估作为检查。流式验证器的存在依赖于这样一个事实，即随着数据的呈现[17]，可以在任何给定位置逐步评估这种低度扩展。
输入表示。本文介绍的所有协议都可以处理以非常通用的数据流形式指定的输入。流的每个元素都是一个元组 (i, δ)，其中 i ∈ [n] 并且 δ 是一个整数（可能为负数，从而对删除进行建模）。数据流隐式定义了一个频率向量 a，其中 ai 是流中与 i 相关的所有 δ 值的总和，目标是计算 a 的函数。请注意，要计算的 a 函数可能会将 a 解释为向量以外的对象，例如矩阵或字符串
例如，在下面描述的 MVMULT 问题中，a 定义了一个矩阵和一个要相乘的向量，并且在第 2 节中被视为扩展的一些图问题中，a 定义了一个图的邻接矩阵
在第 2 节和第 3 节中，我们描述协议的方式似乎假设数据流已经预先聚合到频率向量 a 中（例如，在第 3 节中，我们应用了 Goldwasser 等人的协议 [19 ] 到第 i 个输入线的值为 ai) 的算术电路。因此需要强调的是，实际上本文中的所有协议都可以在上一段的输入模型中执行，其中 V 只看到原始（未聚合的）流而不是聚合的频率向量 a，并且没有原始流和聚合向量之间的显式转换这是从 [8, 17] 中的观察得出的，为了完整性，我们在此对其进行描述。
关键的观察是，在我们所有的协议中，V 必须从数据流中提取的唯一信息是评估 a 在随机点 r 处的低度扩展，我们用 LDEa(r) 表示，这个值当原始流呈现给 V 时，可以使用 O(1) 个内存字由 V 增量计算。至关重要的是，这是可能的，因为对于固定 r，函数是线性的，因此它很简单让 V 计算每次更新 (i, δ) 对 LDEa(r) 的贡献
更准确地说，我们可以写出 ，其中 χi 是一个仅依赖于 i 的 (Lagrange) 多项式。因此，V 可以通过初始化 LDEa(r) ← 0 从原始流中增量计算 LDEa(r)，并通过以下方式处理每个更新 (i, δ)：
V 只需要存储 LDEa(r) 和 r，这需要 O(1) 个内存字。此外，对于任何 i，χi(r) 可以在 O(log n) 场操作中计算，因此 V 可以使用 O(1) 个空间字和 log n 一次通过原始流计算 LDEa(r)每次更新的外地行动
问题。为了集中讨论和实验研究，我们描述了捕捉计算不同方面的四个关键问题：数据分组和聚合、线性代数和模式匹配。我们将研究如何为这些问题中的每一个构建有效的协议。在整个过程中，让 [n] = {0, . . . , n - 1} 表示从中提取数据元素的域。
F2：给定来自 [n] 的 m 个元素的流，计算 P i∈[n] a2i，其中 ai 是流中 i 的出现次数。这也称为第二频矩，是第 k 个频矩的特例 Fk = P i∈[n] aki
F0：给定来自 [n] 的 m 个元素的流，计算不同元素的数量，即 ai > 0 的 i 的数量，其中 ai 是流中 i 的出现次数
MVMULT：给定一个定义 n × n 整数矩阵 A 和向量 x, b ∈ Zn 的流，确定是否 Ax = b。更一般地说，我们对 P 提供一个向量 b 的情况感兴趣，该向量 b 被称为 Ax。这很容易被我们的协议处理，因为 V 可以将提供的 b 视为输入的一部分，即使它可能在输入的其余部分之后到达
PMWW：给定一个表示文本 T = (t0, . . . , tn−1) ∈ [n]n 和模式 P = (p0, . . . , pq−1) ∈ [n]q 的流，模式 P 是如果对于 P 中的每个位置 j，pj = ti+j 或 pj 和 ti+j 中的至少一个是通配符 *，则表示发生在 t 中的位置 i。通配符的模式匹配问题是确定 P 在 T 中出现的位置数量。
F2：给定来自 [n] 的 m 个元素的流，计算 P i∈[n] a2i，其中 ai 是流中 i 的出现次数。这也称为第二频矩，是第 k 个频矩的特例 Fk = P i∈[n] aki
F0：给定来自 [n] 的 m 个元素的流，计算不同元素的数量，即 ai > 0 的 i 的数量，其中 ai 是流中 i 的出现次数
MVMULT：给定一个定义 n × n 整数矩阵 A 和向量 x, b ∈ Zn 的流，确定是否 Ax = b。更一般地说，我们对 P 提供一个向量 b 的情况感兴趣，该向量 b 被称为 Ax。这很容易被我们的协议处理，因为 V 可以将提供的 b 视为输入的一部分，即使它可能在输入的其余部分之后到达
PMWW：给定一个表示文本 T = (t0, . . . , tn−1) ∈ [n]n 和模式 P = (p0, . . . , pq−1) ∈ [n]q 的流，模式 P 是如果对于 P 中的每个位置 j，pj = ti+j 或 pj 和 ti+j 中的至少一个是通配符 *，则表示发生在 t 中的位置 i。通配符的模式匹配问题是确定 P 在 T 中出现的位置数量。
为简单起见，我们假设流长度 n 和宇宙大小 m 处于同一数量级，即 m = Θ(n)
所有四个问题都需要流模型中的线性空间来精确解决（尽管前三个 [28] 有空间高效的近似算法）
非交互式与多轮协议。可靠委托的协议分为两类： 非交互的，其中单个消息从证明者发送到验证者，并且不发生反向通信；和多轮，两方持续对话，可能跨越数百轮或更多。各有优缺点
— 非交互的优点：非交互模型具有理想的属性，即证明者可以计算证明并将其发送给验证者（通过电子邮件或发布在网站上），以便 V 在空闲时检索和验证。相比之下，多轮案例需要P和V在线交互。由于往返延迟，多轮协议的时间成本会变得很高；此外，P 可能必须在每条消息之后进行大量计算。这可能涉及维护消息之间的状态，以及对数据执行多次传递。一个不太明显的优势是非交互式协议可以针对不同的实例重复（例如在 PMWW 中搜索不同的模式），而不需要 V 使用新的随机性。这允许验证者在许多查询中分摊其大部分时间成本，从而可能实现每个查询的次线性时间成本。这可能的原因是在非交互式协议的过程中，P 对 V 的私有随机性一无所知（假设 P 不知道 V 是接受还是拒绝证明），因此我们可以使用联合绑定来绑定概率多个实例的错误
相反，在多轮情况下，V 必须在协议过程中将其大部分私有随机位泄露给 P
— 多轮优势：多轮协议的总体成本可以更低，因为大多数非交互式协议需要 V 使用大量空间并读取大型证明。事实上，先前的工作 [8, 15] 表明，对于大多数非交互式协议 [8]，空间或通信必须是 Ω(√n)。尽管如此，即使是 TB 字节的数据流，这些成本通常也仅转化为几兆字节的空间和通信，这在许多应用程序中是可以容忍的。更令人担忧的是，在已知的非交互式协议中，证明者的时间成本通常比交互式情况下要高得多，尽管这种差距不知道是固有的。我们在第 2 节中在缩小证明者运行时间方面取得了实质性进展，但这仍然在实践中留下了一个数量级的差异（第 5 节）。
1.3 概要和贡献
我们首先考虑非交互协议，其次考虑交互协议。首先，我们在第 2 节中描述了如何使用快速傅立叶变换方法将 P 在 [8] 的 F2 协议中的运行时间从 O(n3/2) 降低到接近线性时间。 F2 协议是一个关键目标，因为（正如我们所描述的）有几个协议直接建立在它之上。我们在第 5 节中展示了这会导致每秒数十万次更新的加速，从而将这个协议以及那些建立在它之上的协议从理论带到实践
转向交互式协议，在第 2.1 节中，我们描述了 [19] 的通用构造的有效实例化。在这里，我们还基于将我们的实现应用于精心挑选的电路，描述了针对特定问题（包括 F0 和 PMWW）的有效协议。后一种协议支持在云中进行可验证的搜索（即使使用通配符），并补充了在云中搜索加密数据的工作（例如 [5]）。我们在本节的最后贡献是证明使用更通用的算术门来增强 [19] 的基本协议允许我们在实践中显着减少这两种协议的证明者时间、通信成本和消息成本
在第 4 节中，我们基于称为线性化的技术为重要的特定问题提供了替代交互协议；我们在第 5 节中展示了线性化为 F0 生成了一个协议，其中 P 的运行速度比该问题的所有其他已知协议快近两个数量级
最后，我们描述了我们对实现这些不同方法的观察，包括我们精心设计的强大通用结构的实现 [19]
2 通过快速傅立叶变换的快速非交互式证明在本节中，我们将描述如何为一大类专门的非交互式协议大幅加速 P 的计算。在非交互式证明中，P 经常需要在大量位置评估低度扩展，这可能是瓶颈。在这里，我们展示了如何通过快速傅里叶变换 (FFT) 方法将此步骤的成本降低到接近线性
具体而言，我们在 [8] 中给出的 F2 非交互式协议的上下文中描述了该方法。该协议的初步实验将证明者的运行时间确定为协议中的主要瓶颈 [17]。在这个实现中，P 需要 Θ(n3/2) 时间，因此该实现无法扩展到 n > 107。在这里，我们展示了 FFT 技术可以显着加快证明者的速度，从而产生一种协议，可以轻松扩展到包含以下内容的流数十亿个项目
我们指出 F2 是一个非常有趣的问题，而不仅仅是一个规范的流问题
非交互模型中现有的很多协议都是建立在F2协议之上的，包括求两个向量之间的内积和汉明距离[8]，MVMULT问题，求解一大类线性规划，图测试等问题连通性和识别二部完美匹配[9, 15]。这些协议特别重要，因为它们都在空间和通信成本之间实现了可证明的最佳权衡 [8]。因此，通过为 F2 开发一个可扩展的、实用的协议，我们还为许多重要（且看似无关）问题的协议实现了重大改进
非交互式 F2 和 MVMULT 协议。我们首先概述了 [8, Theorem 4] 中 F2 在 n 维向量上的协议。这种结构为任何 0 ≤ α ≤ 1 产生一个 (nα, n1−α) 协议，即它允许在通信量和 V 使用的空间之间进行权衡；为简洁起见，我们在 α = 1/2 时描述协议
为简单起见，假设 n 是一个完美的正方形。我们将 n 维向量视为 √n × √n 数组a。这意味着在适当大的有限域 Fp 上的二元多项式 f，使得
为了计算 F2，我们希望计算
低度扩展 f 也可以在 [√n] × [√n] 之外的位置进行评估。在协议中，验证者 V 选择一个随机位置 r ∈ Fp，并为每个 y ∈ [√n] 评估 f(r, y)（[8] 展示了 V 如何以常数增量计算任何 f(r, y)空间）。 P 给出的证明是 2(√n - 1) 次多项式 s(X) 的形式，它被称为 P y∈[√n] f(X, y)2。 V 使用 f(r, y) 的值来检查 s(r) = P y∈[√n] f(r, y)2，如果是，则接受 P x∈[√n] s(x) 为正确答案。显然，如果 s 如所声称的那样，V 的检查将通过。有效性的证明遵循 Schwartz-Zippel 引理：如果 s(X) 6= P y∈[√n] f(X, y)2 如 P 所声称的，则
其中 p 是有限域 Fp 的大小。因此，如果 P 完全偏离规定的协议，验证者的检查将很有可能失败
MVMULT 的非交互式协议使用类似的想法。输出中的每个条目是两个向量之间的内积的结果：矩阵 A 和向量 x 的行。可以使用上述协议的变体独立检查输出中的 n 个条目中的每一个，其中平方值被向量条目的乘积替换；这种简单的方法为 MVMULT 生成了一个 (n3/2, n3/2) 协议。 [15] 观察到，因为 x 在所有 n 内积计算中保持不变，所以可以通过让 V 跟踪散列信息而不是完整向量来减少 V 的空间需求。然而，来自 P 的消息不会改变，计算输入数据的低度扩展是主要的可扩展性瓶颈
对于任何 0 ≤ α ≤ 1，这种结构产生一个 1 消息 (n1+α, n1−α) 协议（如定义 1.2 中），并且可以证明这是最优的。
2.1 打破瓶颈
由于 s(X) 的度数最多为 2√n-1，因此它在任意 2√n 个位置由其值唯一指定。我们展示了 P 如何快速评估集合中的所有值
由于 s(X) = P y∈[√n] f(X, y)2，给定集合中的所有值
S 中的所有值都可以在 n 中按时间线性计算。 [17] 的实现独立计算了 T 中的每个值，总共需要 Θ(n3/2) 时间。我们展示了 FFT 技术如何让我们更快地计算 T
计算 T 的任务归结为多项式 f 的多点评估。已知如何在时间 O(t log t) 内对单变量次数 t 多项式执行快速多点评估，并且双变量
如果多项式由其系数 [27] 指定，则在次二次时间中的多项式。但是，将 f 转换为系数表示存在大量开销。通过在足够多的点上指定它们的值，我们可以更有效地直接使用和交换隐式表示中的多项式
表示为卷积。我们给出了位于 [√n] × [√n]“网格”上的所有点的 f 值。我们利用这一事实通过直接应用快速傅里叶变换在几乎线性的时间内有效地计算 T。对于 (x, y) ∈ [√n] × [√n]，f(x, y) 就是 ax,y，P 可以在处理流时显式存储。对于 √n ≤ x < 2√n，还有待计算 (x, y, f(x, y))。对于固定的 y ∈ [√n]，我们可以将 f(X, y) 显式写为
其中 χi 是拉格朗日多项式1
结果 f(j, y) 可以计算为 by 和 g 的循环卷积，按 h(j) 缩放。也就是说，对于一个固定的 y，集合 Ty := {(x, y, f(x, y)) : x ∈ [2√n]} 中的所有值都可以通过计算公式 1 中的卷积得到，然后通过适当的 h(j) 值缩放每个条目
计算卷积。我们在合适的场上用长度为 2√n 的向量表示 by 和 g，并对每个向量进行离散傅里叶变换 (DFT)。卷积是两个变换的内积的逆变换[23，第 5 章]。可以自由选择执行转换的字段。我们可以通过标准技术（例如 Cooley-Tukey 算法 [14]）使用 O(√n log n) 算术运算在复场 C 上计算 fy 和 g 的 DFT，并简单地将最终结果模 p 舍入为最接近的整数。小数点后的对数精度足以获得足够准确的结果。由于我们计算了 O(√n) 个这样的卷积，我们得到以下结果： 定理 2.1 [8，定理 4] 的 F2 协议中的诚实证明者需要对位复杂度 O(log n + logp)。
然而，在实践中，处理 C 语言可能会很慢，并且需要我们处理精度问题。由于原始数据位于某个有限域 Fp 中，并且可以表示为固定精度整数，因此最好还计算同一域上的 DFT。在这里，我们利用这样一个事实，即在设计我们的协议时，我们可以选择在任何足够大的有限域 Fp 上工作
有两个问题需要解决：我们需要对 Fp 中长度为 2√n（或大约）的序列存在 DFT，并且该 DFT 具有相应的（快速）傅里叶变换算法。我们可以使用 Fp [6] 中 DFT 的素因子算法 (PFA) 解决这两个问题。 “教科书”Cooley-Turkey FFT 算法对长度为 2 的幂的序列进行运算。相反，PFA 处理长度为 N = N1 × N2 × 的序列。 . . × Nk，其中 Ni 是成对互质的。转换的时间成本为 O((P i Ni)N)。该算法通常应用于复数，但也适用于 Fp：它通过将大型 DFT 分解为一系列较小的 DFT 来工作，每个 DFT 的大小为 Ni 对应一些 i。只要在 Fp 中存在原始的第 Ni 单位根，这些长度为 Ni 的序列的基本 DFT 就存在于 Fp 中。当 Ni 是 p-1 的除数时就是这种情况。所以只要 p-1 有许多不同的质因数，我们的状态就很好
在这里，我们使用我们的自由来固定 p，并选择 p = 261 - 1.2 注意 261 - 2 = 2 × 32 × 52 × 7 × 13 × 31 × 41 × 61 × 151 × 331 × 1321，所以有很多这样的除数 Ni 在工作于 Fp 时可供选择。如果 2√n 不等于 p - 1 的因子，我们可以简单地填充向量 fy 和 g 使得它们的长度是 261 - 2 的因子。由于 261 - 2 有许多小因子，我们不必也使用大量填充：我们计算出我们永远不需要将长度为 100 ≤ N ≤ 109（适用于 n 到 1018）的任何序列填充超过其长度的 16%。这比 Cooley-Tukey 方法要好，其中 padding 可以使序列的长度加倍
例如，我们可以使用长度 N = 2 × 5 × 7 × 9 × 11 × 13 = 90090，足以满足大小为 n = (N/2)2，超过 109 的输入。成本比例为 ( 2 + 5 + 7 + 9 + 11 + 13)N = 47N。因此，PFA 方法对 Fp 中的朴素卷积提供了实质性改进，这需要时间 Θ(N 2)
并行化。该协议非常适合并行化。观察到 P 对每个长度 O(√n)（矩阵 ax,y 的每一列 y 一个）执行 O(√n) 个独立卷积，然后为结果的每一行 x 计算 Py a2x,y。卷积可以并行完成，一旦完成，每行的平方和也可以并行化。该协议还拥有一个简单的两轮 MapReduce 协议。在第一轮中，我们为矩阵 ax,y 的每一列 y 分配一个唯一的键，并让每个 reducer 对对应的列执行卷积。在第二轮中，我们为每行 x 分配一个唯一的键，并让每个 reducer 为其行 x 计算 P y a2x,y 。
2.2 影响
正如我们在第 5 节中通过实验证明的那样，本节的结果使实用成为大多数已知非交互式协议的基本构建块。事实上，通过将定理 2.1 与 [8, 15] 中的协议相结合，我们得到了以下直接推论。对于所有考虑的图问题，n 是图中的节点数，m 是边数
推论2.2 1.（扩展[8，定理4.3]）F或任意h·v≥n，有一个（h，v）协议用于计算两个n维向量的内积和汉明距离，其中V运行在时间 O(n) 和 P 在时间 O(n log n) 中运行。 P 之前已知的最佳运行时间是 O(h2v)。
2. (扩展 [15, Theorem 4]) F 或任何 h·v ≥ n，有一个 (mh, v) 协议用于 m× n 整数矩阵向量乘法 (MVMULT)，其中 V 运行时间为 O(mn)，并且P 运行时间 O(mn log n)
P 之前已知的最佳运行时间是 O(mh2v)
3.（扩展[15，推论3]）F或任何h·v≥n，有一个O（nh，v）协议用于求解具有n（整数）约束和多项式大小的子行列式的n个变量的线性程序，其中 V 运行时间为 O(n2)，P 运行时间为 O(t(n) + n2 log n)，其中 t(n) 是求解线性规划及其对偶所需的时间。 P 之前已知的最佳运行时间是 O(t(n) + nh2v)
4.（扩展[8，定理5.4]）F或任何h·v≥n3，有一个（h，v）协议用于计算图中三角形的数量，其中V运行时间为O（mn）和P运行时间 O(n3 log n)。 P 之前已知的最佳运行时间是 O(h2v)
5.（扩展[9，定理6.6]）F或任何h·v≥n2，h≥n，有一个（h，v）协议用于图连接，其中P运行时间为O（n2 log n）和V运行时间 O(m)。 P 之前已知的最佳运行时间是 O(nh2v)
6.（扩展[9，定理6.5]）F或任何h·v≥n2，h≥n，有一个（h，v）协议用于二分完美匹配，其中V运行时间为O（m），P运行在时间 O(t(n) + n2 log n) 中，其中 t(n) 是找到完美匹配（如果存在完美匹配）或找到反例（通过霍尔定理）所需的时间。 P 之前已知的最佳运行时间是 O(t(n) + h2v)
在我们选择 h = v 的常见情况下，这表示 P 运行时的多项式加速
例如，对于 MVMULT 问题，证明者的成本从之前工作中的 O(mn3/2) 降低到 O(mn log n)
在推论 2.2 的大多数情况下，V 以线性时间运行，而 P 以接近线性时间运行密集输入，加上首先解决问题所需的时间 t(n)，这可能是超线性的。因此，与以不可验证的方式解决问题相比，P 在“可验证地”解决问题时最多支付对数因子开销。
3 通用方法：通过电路检查的多轮协议
在本节中，我们研究交互式协议，并描述如何有效地实例化由 Goldwasser、Kalai 和 Rothblum 提供的强大框架，用于验证任意计算3
理论文献中开发的验证计算的标准方法是验证计算所需函数的电路的属性[18,19,31]。其中最有希望的一个要归功于 Goldwasser 等人，它证明了以下结果： 定理 3.1 [19] 令 f 是任意域 F 上的函数，该函数可以由 O(log S(n ))-扇入 2、大小 S(n) 和深度 d(n) 的空间均匀算术电路（在 F 上）。然后，假设在 F 中传输或存储一个值的单位成本，f 拥有一个 (log S(n), d(n) log S(n)) 协议，需要 O(d(n) log S(n)) 轮. V 在时间上运行 (n + d(n)) polylog (S(n)) 并且 P 在时间上运行 poly(S(n))
在这里，域 F 上的算术电路类似于布尔电路，不同之处在于输入是 F 的元素而不是布尔值，并且电路的门计算 F 上的加法和乘法。我们讨论如何实现定理 3.1 有效。具体来说，我们展示了三个
技术成果。前两个结果，定理 3.2 和 3.3，表明对于任何对数空间均匀电路，可以使定理 3.1 协议中的诚实证明者在电路大小上几乎线性运行，流式验证者仅使用 O(log S(n)) 个内存字。因此，这些结果保证了高效的证明者和节省空间的验证者。在流式环境中，V 的空间受限多于时间受限，这可能是可以接受的。此外，定理 3.3 指出 V 可以在与数据无关的非交互式预处理阶段执行其计算的耗时部分，这可以在观察流之前离线发生
我们的第三个结果，定理 3.4 做了一个稍强的假设，但产生了一个更强的结果：它表明在电路上非常温和的条件下，我们可以实现一个在时间上运行的证明者几乎与电路大小呈线性关系，而一个验证者的既节省空间又节省时间
在陈述我们的定理之前，我们概述了实现有效实现所需的主要技术，完整的细节在附录 A 中。我们还将感兴趣的读者引导到我们实现的源代码 [16]。本节的其余部分旨在让熟悉 sum-check 协议 [33, 25] 但不一定熟悉 [19] 协议的读者可以合理地访问
3.1 设计一个高效的证明者 在[19]的协议中，V 和 P 首先在一个深度 d 的门电路 C 上达成一致，该电路具有扇入 2，用于计算感兴趣的函数； C 被假定为分层形式（这个假设最多将电路的大小扩大了 d 倍，我们认为它在实践中是不受限制的，因为我们所有四个激励问题的自然电路都是分层的，以及附录 A 中描述的各种其他问题）
P 首先声明电路输出门的值。然后，该协议从 C 的输出层迭代到输入层，每一层迭代一次。出于演示目的，假设电路的所有层都有 n 个门，并且让 v = log n
在高层次上，在迭代 1 中，V 将验证输出门的声明值简化为计算随机点 r(1) ∈ F3v 处的某个 3v 变量多项式 f1 的值。然后迭代在每一层门上进行归纳：在迭代 i > 1 中，V 将某个 3v 变量多项式 fi-1 的计算 fi-1(r(i-1)) 简化为计算 fi(r(i))对于随机点 r(i) ∈ F3vp 。最后，在迭代 d 中，V 必须计算 fd(r(d))。这恰好是输入的一个函数（具体来说，它是对输入的低度扩展的评估），并且 V 可以在没有帮助的情况下以流方式计算这个值，即使只允许访问原始（未聚合的）数据流，如第 1.2 节所述。如果值一致，则 V 确信输出的正确性
我们抽象了“连线谓词”的概念，它编码了来自第 i-1 层的哪些线对连接到第 i 层的给定门。每次迭代 i 都包含标准和校验协议 [25, 33] 对基于连线谓词的 3v 变量多项式 fi 的应用。选择要使用的特定多项式 fi 有一定的灵活性。这是因为fi的定义涉及到电路连线谓词的低度扩展，而这样的低度扩展有很多可供选择
如果多项式在每个变量中的次数最多为一个，则称该多项式是多线性的。本节的结果主要依赖于这样的观察，即如果我们使用电路布线谓词的多线性扩展，诚实证明者在 [19] 的协议中的计算可以大大简化。4 这个观察的细节如下
如前所述，在 [19] 的协议的迭代 i 中，sum-check 协议应用于 3v 变量多项式 fi。在这个 sum-check 协议的第 j 轮中，需要 P 发送单变量多项式
定义 gj 的总和涉及多达 n3 项，因此 P 的简单实现将需要每次协议迭代的 Ω(n3) 时间。然而，我们观察到，如果在 fi 的定义中使用了电路布线谓词的多线性扩展，则第 i-1 层的每个门都对定义 gj 的总和有一个项，就像第 i 层的每个门一样。因此，多项式 gj 可以通过单次通过第 i-1 层的门和单次通过第 i 层的门来计算。由于求和校验协议要求电路的每一层都需要 O(v) = O(log S(n)) 消息，因此 P 需要在电路的每一层上总共以对数方式多次通过
应用上述观察的一个复杂之处在于，V 必须处理电路，以便提取有关其结构的信息，以检查 P 消息的有效性。具体来说，sum-check 协议的每个应用程序都需要 V 来评估电路的布线谓词在随机点的多线性扩展。定理 3.2 来自以下事实：对于任何对数空间均匀电路，V 可以使用空间 O(log S(n)) 在任何点评估布线谓词的多线性扩展。我们在附录 A 中给出了以下定理的详细证明和讨论
定理 3.2 F 或任何大小为 S(n) 的对数空间均匀电路，P 需要 O(S(n) log S(n)) 时间来在整个执行过程中实现定理 3.1 的协议，而 V 需要空间 O(日志 S(n))
此外，由于电路的连线谓词与输入无关，我们可以将 V 的计算分为在看到数据流之前发生的离线非交互预处理阶段和在 P 和 V 都看到之后发生的在线交互阶段输入。这类似于 [19，定理 4]，并确保 V 在离线阶段是空间高效的（但可能需要时间 poly(S(n))），并且 V 在离线阶段是时间和空间高效的在线互动阶段。为了确定使用哪个电路，V 确实需要知道（上限）预处理阶段输入的长度
定理 3.3 F 或任何大小为 S(n)、P 的对数空间统一电路需要 O(S(n) log S(n)) 时间来在整个执行过程中实现定理 3.1 的协议。 V 在非交互、数据无关的预处理阶段需要空间 O(d(n) log S(n)) 和时间 O(poly(S(n)))，并且只需要空间 O(d(n) log S(n)) 和在线交互阶段的时间 O(n log n+d(n) log S(n))，其中 O(n log n) 项是由于评估低度所需的时间输入点的扩展
最后，定理 3.4 假设 V 可以快速评估连线谓词的多线性扩展。定理 3.4 的正式陈述在附录 A 中。我们认为定理 3.4 的假设非常温和，我们在附录 A 中详细讨论了这一点，确定了适用于定理 3.4 的各种电路。此外，我们在 F2、F0 和 PMWW 的电路检查实验中采用的解决方案对应于定理 3.4，并且对于验证者来说既节省空间又节省时间
定理 3.4（非正式） 设 C 是大小为 S(n) 和深度为 d(n) 的任何对数空间均匀电路，并假设存在一个 O(log S(n))-空间，poly(log S(n) )-time 算法，用于评估 C 的连线谓词在某个点的多线性扩展。那么为了实现应用于 C 的定理 3.1 的协议，P 需要 O(S(n) log S(n)) 时间，V 需要空间 O(log S(n)) 和时间 O(n log n + d(n)poly(log S(n)))，其中 O(n log n) 项是由于评估输入在某个点的低度扩展所需的时间。
3.2 电路设计问题 [19] 的协议描述了带有加法（+）和乘法门（×）的算术电路。这足以证明该系统的强大功能，因为布尔输入上的任何可有效计算的布尔函数都可以通过（渐近的）小型算术电路进行计算。通常，此类算术电路是通过为函数构造一个布尔电路（带有 AND、OR 和 NOT 门），然后对电路“算术化”[2，第 8 章]来获得的。然而，我们努力的不仅仅是渐近效率，而是真正的实用性，并且所涉及的因素可以快速增长：电路中的每一层（算术）门都为协议增加了 3v 轮交互。因此，我们进一步探索优化和实现问题
加长门。 [19] 的电路检查协议可以用任何计算其输入的低次多项式函数的门进行扩展。如果 g 是 j 次多项式，我们可以使用门计算 g(x)；这将协议的每一轮中的通信复杂度最多增加 j - 2 个字，因为 P 必须发送 j 次多项式，而不是 2 次多项式
我们用来计算感兴趣函数（特别是 F0 和 PMWW）的低深度电路利用函数 f(x) = xp−1。仅使用 + 和 × 门，它们需要大约 log2 p 的深度。如果我们还使用门计算 g(x, y) = xjyj 来计算小的 j，我们可以将电路的深度减少到大约 log2j p；由于 [19] 协议中的轮数线性地取决于电路的深度，这将轮数减少了大约 log2 p/ log2j p = 1/ log2j 2 的因子。同时这增加了每一轮的通信成本乘以（最多）j - 2 倍。我们可以优化 j 的选择。在我们的实验中，我们使用 j = 4 (所以 g(x, x) 是 x8) 和 j = 8 (g(x, x) = x16) 来同时将消息数量减少 3 倍，并且通信成本和证明人运行时间也受到重要因素的影响
另一种优化是可能的。我们考虑的所有四个具体问题，F2、F0、PMWW 和 MVMULT，最终都会计算大量值的总和。令 f 为要求和的值的低度扩展。对于这种形式的函数，V 可以使用单个 sum-check 协议 [2，第 8 章] 将求和的计算简化为计算随机点 r 的 f(r)。 V 然后可以使用 [19] 的协议将 f(r) 的计算委托给 P。从概念上讲，这种优化对应于用具有大扇入的单个 ⊕ 门替换算术电路 C 中的加法门的二叉树，它总结了它的所有输入。这种优化可以减少通信成本和协议所需的消息数量
通用电路设计。电路检查方法可以与现有的编译器相结合，例如 Fairplay 系统 [26] 中的编译器，它将高级编程语言中的程序作为输入并输出相应的布尔电路。然后可以通过我们的实现对这个布尔电路进行算术运算和“验证”；这产生了一个完整的系统，实现了统计安全的可验证计算
然而，即使可以使证明器 P 在与算术电路的大小成线性的时间上运行，该系统也可能仍然不切实际。例如，在大多数硬件中，可以用一条指令计算两个 32 位整数 x 和 y 的和。但是，当将此操作编码为布尔电路时，尚不清楚如何在深度小于 32 的情况下执行此操作。在每个电路层 3 log n 轮时，对于合理的参数，单次加法可以变成数千轮
3.3 节中的协议通过避免布尔电路来避免这种情况，而是直接将输入视为 Fp 上的元素。例如，如果输入是一个 32 位整数的数组，那么我们将数组的每个元素视为 Fp 的值，计算两个整数之和需要单个深度为 1 的加法门，而不是深度为32 布尔电路。但是，这种方法似乎严重限制了可以实现的功能。例如，我们知道没有紧凑的算术电路来测试 x > y 当
将 x 和 y 视为 Fp 的元素。事实上，如果存在这种功能的电路，我们将获得 F0 和 PMWW 的显着改进的协议
与输入大小相比，电路深度的这种多对数爆炸似乎在任何将计算编码为算术电路的结构中都是固有的。因此，避免这种表示的通用协议的开发仍然是未来工作的重要方向
3.3 针对特定问题的有效协议 通过将定理 3.1 应用于精心挑选的算术电路，我们获得了针对我们感兴趣的问题的交互式协议。在这些电路中，每个门对其输入执行简单的算术运算，例如加法、减法或乘法。对于前三个问题，存在专门的协议；我们在这里描述这些协议的目的是探索一般构造在应用于高度感兴趣的特定功能时如何执行。然而，对于 PMWW，我们在这里描述的协议是同类中的第一个
对于每个问题，我们描述了一个电路，该电路利用了定义它们的有限域的算术结构。对于后三个问题，这涉及到费马小定理的有趣使用。这些电路有助于扩展[19]的基本协议，实现所有成本的量化改进；我们在第 5 节中展示了这些改进的程度
F2 的协议：F2 的算术电路非常简单：第一级计算输入值的平方，然后随后的级将它们成对相加以获得所有平方值的总和。总深度 d 为 O(log n)。这意味着 O(log2 n) 消息 (log2 n, log2 n) 协议（根据定义 1.2）
F0 协议：我们描述了一个计算 F0 的 Fp 上的简洁算术电路。当 p 是大于 n 的素数时，费马小定理 (FLT) 意味着对于 x ∈ Fp，xp−1 = 1 当且仅当 x 6= 0
考虑这样的电路，对于输入向量 a 的每个坐标 i，通过 O(log p) 乘法计算每个 ap-1 i，然后对结果求和。该电路的总尺寸为 O(n log p)，深度为 O(log p)。将[19]的协议应用于该电路，我们得到一个（log n log p，log n）协议，其中P运行时间为O（n log n log p）
MVMULT 协议：电路的第一层计算所有 i、j 的 Aijxi，随后的层将这些相加得到 P j Aijxi。然后我们使用 FLT 来确保 P j Aijxi = bi 对于所有 i，通过
如果电路的最终输出为 0（即它计算 b 的不正确条目的数量），则输入如所声称的那样。该电路的深度为 O(log p)，大小为 O(n2 log p)，因此我们获得了一个 (n + log p log n, log n) 协议，需要 O(log p log n) 轮次，其中 P 运行在时间 O(n2 log p log n)
PMWW 协议：为了处理 T（长度为 n）和 P（长度为 q）中的通配符，我们将每次出现的通配符替换为 0； [13] 注意到模式出现在 T 的位置 i 当且仅当
因此，通过 FLT，计算 Pn i=0 Ip-1 i 就足够了，这可以通过大小为 O(nq + n log p) 和深度 O(log p + log q) 的算术电路简单地完成。我们获得了一个 (log n log p, log n) 协议，其中 P 运行时间为 O(n log n(q + log p))。
对于较大的 q，可以进行进一步的优化：向量 I 可以写为恒定数量的循环卷积的总和。这种卷积可以使用傅立叶技术在时间 O(n log q) 内有效计算，重要的是，可以通过算术电路实现适当的 FFT 和逆 FFT 运算。因此，对于大于 log p 的 q，我们可以通过这种方式减少电路大小（从而减少 P 的运行时间），而不是天真地独立计算 I 的每个条目。
4 通过线性化的多轮协议
在本节中，我们将展示线性化技术如何改进第 2.1 节中一些重要函数的一般方法。具体来说，这种技术可以应用于多轮协议，否则这些协议将需要非常高阶的多项式进行通信。我们在 F0 和 PMWW 的新多轮协议的背景下展示了这一点，后来我们凭经验观察到，我们的新协议比现有的 F0 协议实现了两个数量级的加速，以及通信方面的一个数量级改进成本
多轮设置中 F0 的现有方法基于对 F2 [17] 的多轮协议的推广。如 [17] 中所述，直接应用这种方法是有问题的：F0 中的中心函数将非零频率映射到 1，同时将零频率保持为零。表示为多项式，该函数的度数为 m（任何项目的频率的上限），这转化为所需的通信和时间成本 P 的 m 的因子。但是，这个成本可以减少到 F∞ ，其中 F∞ 表示任何项目在流中出现的最大次数。此外，如果 P 和 V 都保留 b 个输入项的缓冲区，则它们可以消除缓冲区内的重复项，从而确保 F∞ ≤ m/b。这导致了一个 O(log n) 消息，(log n, F∞ log n) 多轮协议，其中 P 的运行时间为 O(F 2∞n log n) [17]。与上面第 3.3 节中概述的协议相比，该协议以增加的通信换取所需通信轮数的二次改进。
4.1 线性化设置 在本节中，我们描述了一个新的 F0 多轮协议，稍后解释如何为 PMWW 修改它。该协议具有与第 3.3 节中获得的相似的渐近成本，但实际上在 P 的运行时间上实现了接近两个数量级的改进。核心思想是将数据表示为一个大的二进制向量，指示每个项目何时出现在流中。该协议模拟逐步将时间范围合并在一起，以指示在该范围内发生了哪些项目。直接验证此计算将遇到上述相同的障碍：使用多项式来检查这将导致多项式的高度，从而主导成本。因此，我们使用“线性化”技术，以确保所需多项式的次数保持在较低水平，但代价是需要更多轮次的交互。这使用了 [2，第 8 章] 中提出的沉 [34] 的想法
像往常一样，我们在一个有 p 个元素 Fp 的有限域上工作。输入隐式定义了一个 n × m 矩阵 A 使得如果流的第 j 项等于 i，则 Ai,j = 1，否则 Ai,j = 0
在布尔超立方体上工作。关键的第一步是定义一个基于 d 维布尔超立方体的索引结构，因此每个输入点都由一个 d 位二进制字符串索引，这是一个 log n 位字符串 i 和一个 log m 位的（二进制）连接字符串 j。我们将 A 视为通过 (x1, ..., xd) 7→ A(x1,...,xd) 从 {0, 1}d 到 {0, 1} 的函数。令 f 是 d 个变量中的唯一多元线性多项式，使得 f(x1, . . . , xd) = A(x1,...,xd) 对于所有 (x1, . . . , xd) ∈ {0, 1} d，即 f 是 A 隐含的函数在 {0, 1}d 上的多线性扩展。
验证者 V 需要跟踪的唯一信息是随机点的 f 值。也就是说，V 选择一个随机向量 r = (r1, . . . , rd) ∈ Fdp。当 V 观察定义 A（以及 f）的流时，V 计算 f(r) 是有效的：当第 j 个更新是项目 i 时，这转换为向量 v = (i, j) ∈ {0 , 1}d.必要的更新是 f(r) ← f(r) + χv(r) 的形式，其中 χv 是唯一多项式，在 v 处为 1，在 {0, 1}d 中的其他处为 0。为此，V 只需要存储 r 和 f(r) 的当前值
线性化和算术化布尔运算符。我们在多项式 g 上使用三个运算符 q、Π 和 L，定义如下：
q 和 Π 分别概括了熟悉的“OR”和“AND”运算符。因此，如果 g 是每个变量中最多为 j 次的 k 变量多项式，则 qk(g) 和 Πk(g) 是每个变量中最多为 2j 次的 k-1 变量多项式。他们概括了布尔运算符，即如果 g(X1, . . . , Xk−1, 0) = x 和 g(X1, . . . , Xk−1, 1) = y 并且 x, y 都为 0或 1，然后
L 是线性化算子。如果 g 是一个 k 变量多项式，则 Li(g) 是一个在变量 Xi 中是线性的 k 变量多项式。 Li 运算用于控制在我们的协议执行过程中出现的多项式的次数。由于 xj = x 对于所有 j ≥ 1，x ∈ {0, 1}，Li(g) 在 {0, 1}k 中的所有值上与 g(·) 一致
在整个过程中，当对多项式应用一系列操作以获得新的多项式时，这些操作是“从右到左”应用的。例如，我们写出 k - 1 变量多项式
重写 F0 和 PMWW。对于 F2 和 MVMULT，几乎不需要线性化：生成的多项式仍然是低阶的，因此 [17、15] 中描述的多轮协议已经足够了。但是线性化可以帮助 F0 和 PMWW
将输入视为上面定义的矩阵 A，我们可以通过重复对相邻列对进行按列或运算得到一个向量来计算 F0，该向量指示项目 i 是否出现在流中，然后重复对相邻条目求和以获得不同元素的数量。当将这些操作表示为多项式时，我们会额外使用线性化操作来控制出现的多项式的次数。使用上述操作 q 和 Li 的性质并根据超立方体重写，可以看出
因为这个表达式只涉及 {0, 1} 中的变量和值。这个表达式的大小是 3d2+3d 2 = O(log2 n)
PMWW 的情况类似。现在假设模式长度 q 是 2 的幂（如果不是，它可以用尾随通配符填充）。我们现在考虑输入定义一个大小为 2n×qn 的矩阵 A，如果流的第 j 个项目等于 i，则 A2i,qj+k(q−1) = 1，对于所有 0 ≤ k ≤ q - 1，如果模式的第 k 个字符等于 i，则 A2i−1,qj+2k = 1，对于所有 0 ≤ j ≤ n−1。模式或文本中的通配符被视为字母表中所有字符在该位置的出现。通过首先对相邻列进行逐列“与”运算，在矩阵 A 上解决了该问题：在文本字符与特定偏移量的模式匹配的地方留下 1。然后，我们对相邻列进行 log n 次的按列“或”：这会折叠字母表。如果模式出现在文本中的位置 i，则对相邻行进行 log q 次的逐行“与”会留下一个指示向量，其第 i 个条目为 1。对这个向量中的条目求和提供了所需的答案。使用线性化来限制 q 和 Π 运算符的度数，我们再次获得大小为 O(log2 n) 的表达式。
4.2 使用线性化的协议给定（2）形式的表达式，我们现在给出协议的归纳描述。从概念上讲，每一轮我们都要求证明者“剥离”表达式中最左边的剩余操作。在这个过程中，我们将 P 对旧表达式的声明简化为对新的、更短的表达式的声明 最终，V 在随机点（特别是在 r 处）得到关于 f 值的声明，V 可以对照她对 f(r) 的独立评估进行检查 更具体地说，假设对于某个多项式 g(X1, . . . . , Xj)，证明者可以让验证者相信 g(a1, a2, . . . , aj) = C 对于任何 (a1, a2, . . . , aj, C) 这是真的，并且概率小于 ?当它是假的。令 U(X1, X2, . . . , Xl) 是 l 个变量上的任意多项式，得到如下
其中，对于某个变量 i，O 是 P1 xi=0、Π1xi=0、q1xi=0 或 Li 之一。 （因此 l 在前三种情况下为 j-1，在最后三种情况下为 j）。令 m 为 U 相对于 Xi 的度数的上限（验证者已知）。在我们的例子中，m ≤ 2 因为在每个 q 和 Π 操作之间包含了 Li 操作。我们展示了 P 如何让 V 相信 U(a1, a2, . . . . , al) = C0 对于任何 (a1, a2, . . . , aj, C0) 的概率为 1，并且概率最多为? + d/p 当它为假时。必要时通过重命名变量，假设 i = 1。验证者的检查如下
情况 1：O = P1 x1=0。 P 提供了一个 1 次多项式 s(X1)，它应该是 g(X1, a2, ..., aj)
V 检查 s(0) + s(1) = C0 是否。如果不是，V 拒绝。如果是这样，V 选择一个随机值 a ∈ Fp 并要求 P 证明 s(a) = g(a, a2, . . . , aj)。如果是最后d轮之一，V选择a作为r的对应入口
情况 2：O = q1x1=0X 或 O = Π1x1=1X。我们做与案例 1 相同的操作，但在 q 的情况下将 s(0) + s(1) 替换为 s(0) + s(1) - s(0)s(1) 或 s(0) s(1) 在 Π 的情况下
情况 3：O = L1。 P 希望证明 U(a1, a2, . . . . , ak) = C0。 P 提供了一个 2 次多项式 s(X1)，它应该是 g(X1,a2,...,ak)。我们将此称为“解除绑定变量”，因为之前 X1 被“绑定”到值 a1，但现在 X1 是自由的。 V 检查 a1s(0) + (1 − a1)s(1) = C0。如果不是，V 拒绝。如果是这样，V 选择随机 a ∈ Fp 并要求 P 证明 s(a) = g(a, a2, . . . , ak)（或者如果这是最后一轮，V 只需检查 s(a) = f (r))
正确性的证明通过使用以下观察来证明：如果 s(X1) 不是正确的多项式，则概率为 1 - m/p，P 必须在下一轮证明不正确的陈述（这是
Schwartz-Zippel 多项式等式测试程序 [30]）。错误的总概率由每轮概率的联合边界给出，O(log2 n/p)
协议成本分析。回想一下，F0 和 PMWW 都可以写成大小为 O(log2 n) 的运算符的表达式，其中线性化限制了任何变量的度数。在上述过程中，验证者只需要存储 r、f(r)、任何“绑定”变量的当前值以及 s(a) 的最新值。总的来说，这需要空间 O(log n)。有 O(log2 n) 轮，在每一轮中，从 P 到 V 发送一个次数最多为 2 的多项式。这样的多项式最多可以用 3 个单词表示，因此总通信量为 O(log2 n)。因此我们获得了 F0 和 PMWW 的 (log2 n, log n)-protocols
在处理流时，验证者必须更新 f(r)。更新非常简单，处理每次更新需要 O(d) = O(log n) 时间。 PMWW 中有一点开销，其中流中的每个更新都需要验证者将 q 更新传播到 f（假设 q 的上限是预先固定的），花费 O(q) 时间。然而，这些成本可以进一步优化似乎是合理的
证明者必须存储流的描述，这可以在空间 O(n) 中完成。证明者可以实现为需要 O(n log2 n) 时间：本质上，每一轮证明最多需要一次通过流数据来计算所需的函数。为简洁起见，我们省略了实现的详细描述，其源代码可在 [16] 获得
定理 4.1 F 或任何可以写成从 P、Π 和 q 在大小为 n 的输入上提取的 log n（二元）运算符串联的函数，有一个 log2 n 轮（log2 n，log n）协议，其中 P需要时间 O(n log2 n)，V 需要时间 O(log2 n) 来运行协议，计算输入的 LDE
因此，我们可以为 F0 和 PMWW 调用这个定理，获得两者的 log2 n 轮 (log2 n, log n) 协议。
5 实验评价
我们进行了彻底的实验研究，以评估现有协议和我们的新协议的潜在实际有效性。我们将我们的发现总结如下
• 我们实现第 3 节中描述的通用电路检查协议的成本极具吸引力，除了 P 的运行时间。证明者需要几分钟来操作
输入大小约为 105：理想情况下，这需要几秒钟。我们对 [19] 的基本协议提出的扩展（例如额外类型的门）为我们的基准问题带来了显着的量化改进。我们对进一步增强和并行化的前景持乐观态度，以使实用的通用验证成为现实
• 针对特定问题的微调协议可以比一般方法提高几个数量级。具体来说，我们发现非常实用的每秒处理数十万更新的非交互式协议对于非常大的一类问题是可以实现的，但只能通过使用第 2 节中描述的方法。我们还发现线性化技术可以显着与更通用的电路检查方法相比，改进了 F0 的交互式协议
• 最后，我们证明了非交互式协议非常适合并行化，我们相信这使它们成为实用的有吸引力的选择
在我们所有的实验中，验证者需要的空间比没有证明者解决问题所需的空间要少得多，并且如果给定足够快的内存来存储整个输入，则需要的时间与没有证明者解决问题所需的时间大致相同。事实上，我们发现在我们所有的协议中，内存访问都是 V 的计算和在没有证明者的情况下解决问题所需的计算中的速度瓶颈
此外，我们的电路检查结果表明，如果我们要在需要超线性时间来解决的问题上运行我们的实现，那么 V 将节省大量时间和空间（与在没有证明者的情况下解决问题相比）。实际上，除了具有非常高（即线性）深度的电路之外，V 在我们的电路检查实现中的运行时间很大程度上取决于通过输入上的单个流传递执行 LDE 计算所需的时间。验证时间，不包括这个成本，基本上可以忽略不计
5.1 实现细节所有实现都是用C++完成的：我们模拟了双方的计算，并测量了协议消耗的时间和资源。我们的程序是使用 -O3 优化标志使用 g++ 编译的。对于数据，我们生成了合成流，其中每个项目都是从宇宙中均匀随机选取的，或者每个项目的频率是在 [0, 1000] 范围内均匀随机选取的。数据的选择不会影响运行时，它仅取决于数据量而不是其内容。同样，安全保证不依赖于数据，而是依赖于验证者的随机选择。所有计算都在大小 p = 261 - 1 的范围内，这意味着验证者被不诚实的证明者愚弄的概率非常低
我们在具有 64 位 AMD Opteron 处理器和 32 GB 可用内存的多核机器上评估了这些协议。我们的可扩展性结果主要使用单核，但我们也展示了并行操作的结果。大量的内存使我们能够对数十亿大小的宇宙进行实验，证明者能够将全部数据存储在内存中。我们测量了 V 从流中计算检查信息、P 生成证明以及 V 验证证明的时间。我们还测量了 V 所需的空间，以及 P 提供的证明的大小
字段大小的选择。虽然我们实现的所有协议都在任意有限域上工作，但我们选择的 Fp = 261 - 1 证明是工程实际协议的理想选择。首先，场大小足以提供极小的错误概率（与 1/p 成正比），但又足够小，任何场
元素可以用单个 64 位数据类型表示。通过使用本机类型，我们实现了几个因素的加速。其次，减少模 p 可以通过位移、按位与运算和加法来完成 [35]。通过切换到这种专门的“mod”操作而不是在 C++ 中使用“% p”操作，我们体验到了近一个数量级的加速。最后，这个特定字段的使用允许我们应用 FFT 技术，如第 2 节所述（回忆 261 - 2 有许多小的素因数）
协议的正确性。在我们研究的协议中，验证者对证明者声明的检查总是很容易实现：在许多情况下，每次检查都需要一行代码来确保之前的消息与新的消息一致5。因此，以无错误的方式实现验证者并不困难，一旦出现这种情况，验证者的实现将作为对证明者实现的独立检查。这是因为验证者（以高概率）检测到与规定协议的任何偏差，特别是 V 检测到由于不正确的证明者造成的偏差。因此，我们对实现的正确性充满信心。更一般地说，此属性可以帮助测试和调试未来的实现。
5.2 电路检查协议 在我们实现第 2.1 节中描述的电路检查方法时，我们投入了大量精力来优化证明者的运行时间，实现了 P 所花费的时间几乎与电路大小呈线性关系的实现。尽管如此，这一成本仍然是实施的主要限制
我们对我们感兴趣的三个功能的电路实现进行了试验：F2、F0 和 PMWW。我们将 MVMULT 的电路留给未来的工作。结果总结在表 1 中。自始至终，当我们在交互式协议中提到 P 的运行时时，我们指的是协议所有轮次的总时间。每个门的速度可能非常高：在几分钟内处理数千万门的 P 电路。例如，我们的基本实现在 9 分钟内处理了具有近 1600 万个门的 F0 电路，或每秒接近 30,000 个门。然而，由于电路的大小比绘制输入的宇宙大 100 多倍，这意味着每秒只有大约 300 个项目。产生的其他费用非常低。验证者的空间使用和通信成本永远不会超过几十千字节，并且验证者在所有流长度上每秒处理近三千万次更新。与计算所需的输入低度扩展的（已经很短的）时间相比，V 运行协议的时间可以忽略不计。
在 3.2 节中，我们讨论了添加额外的门类型如何降低电路检查的成本。我们通过实验证明，添加计算其输入的 8 次方 (^8) 或 16 次方 (^16) 的门可以显着减小所需电路的尺寸。对于 F0，这将轮数减少了近三倍，证明者时间减