你check 过你的 sum 吗？

引言

由于 zk-SNARKs（零知识、简洁、非交互式知识论证）在去中心化私人计算和区块链扩展方面的能力，最近引起了越来越多的关注。这些构造涉及两个方之间的协议，一个是证明者（prover），另一个是验证者（verifier），前者试图说服后者某一给定声明的有效性。有时，证明者试图在不透露敏感信息的情况下完成这个任务。我们希望验证者检查声明所需的工作量显著小于他自己完成这一工作的工作量。例如，我们希望将一个耗时的计算委托给一个不受信任的服务器（我们没有必要的资源）并能够用智能手机验证计算的正确性。零知识属性使我们能够证明某些秘密的拥有（例如私钥或某些哈希的前像），而不将信息提供给验证者。在这些构造的核心，我们使用多项式，可以将声明简化为多项式之间的某种关系。例如，STARKs 使用一元多项式和 FRI 协议来证明给定计算的正确性。包含多个变量的 sumcheck 协议可用于构建 SNARKs。

在这篇文章中，我们将首先描述如何将向量编码为多线性多项式（类似于我们如何将向量编码为一元多项式），以及 sumcheck 协议的工作原理。我们目前正在实现 sumcheck 协议和多线性多项式，作为Sparkling Water Bootcamp 的学习路径的一部分；你可以在Lambdaworks上关注这个开发进展。

将向量编码为多线性多项式

在 $n$ 个变量中，一项多项式 $p$ 被称为多线性，如果每个变量 $x_i$ 的度数在每一项中最多为 1。例如，$p_1(x_1, x_2, x_3, x_4) = x_1 + 2x_2 + x_1x_2x_4x_3$ 是一个多线性多项式，因为每个 $x_i$ 的幂在每一项中都要么为 0，要么为 1。多项式 $p_2(x_1, x_2) = x_1x_2^2$ 不是，因为 $x_2$ 的度数为 2。多线性多项式的总度数是项（单项式）中所有幂的最大和。对于 $p_1$ 来说，这个值是 4。对于多线性多项式，最大度数最多为 $m$。

我们现在将限制在定义在集合 $D = {0, 1}^m$ 上的多项式内。给定定义在 $D$ 上的函数 $f$，我们可以定义一个多线性多项式 $p(x_1, x_2, ..., x_m)$，使得 $p$ 与 $D$ 上的 $f$ 一致，即对于每个 $x \in D$，有 $p(x) = f(x)$。由于这个多项式是唯一的，因此这个多项式 $p$ 被称为 $f$ 的多线性扩展。

我们可以使用多线性扩展来表示包含 $2^m$ 个元素的向量 $v$。假设向量 $v$ 的元素属于某个有限域 $F$。我们首先创建函数 $f: D \rightarrow F$，映射集合 $D$ 中的每个元素到向量 $v$ 中的一个元素。一个简单的方法是以位形式表示向量中位置 $k$。例如，如果向量具有 256 个元素，我们需要 8 个变量（位），并且可以定义映射如下：

$f(0, 0, 0, 0, 0, 0, 0, 0) = v_0$

$f(0, 0, 0, 0, 0, 0, 0, 1) = v_1$

$f(0, 0, 0, 0, 0, 0, 1, 0) = v_2$

$f(0, 0, 0, 0, 0, 0, 1, 1) = v_3$

$\vdots$

$f(1, 1, 1, 1, 1, 1, 1, 1) = v_{255}$

一般形式中，我们将元组 $(x_0, x1, ... x{m-1})$ 赋值为索引 $k$ 对应的值 $k = x_0 + 2x_1 + 4x2 + \cdots + 2^{m-1}x{m-1}$。然后，我们可以利用存在的 $f$ 的多线性扩展，通过拉格朗日插值创建它。例如，

$p(x_0, x1, ... x{m-1}) = \sum_{x0, ..., x{m-1}} f(k)B_k(x_0, x1, ..., x{m-1})$

其中 $B_k$ 是拉格朗日基多项式，当 $(x_0, x1, ..., x{m-1})$ 对应于 $k$ 的二进制表示时等于 1，否则等于 0。如果我们表示 $k = (k_0, k1, ... k{m-1})$（请记住每个 $k_i$ 都是 0 或 1），函数 $B_k(x_0, x1, ..., x{m-1})$ 具有显式表达式

$B_k(x_0, x1, ..., x{m-1}) = \prod (x_ik_i + (1 - x_i)(1 - k_i))$

例如，如果向量 $v = (2, 5, 7, 8)$，我们有四个拉格朗日基多项式：

$B_0(x_0, x_1) = (1 - x_0)(1 - x_1) = 1 - x_1 - x_0 + x_1x_0$

$B_1(x_0, x_1) = x_0(1 - x_1) = x_0 - x_0x_1$

$B_2(x_0, x_1) = (1 - x_0)x_1 = x_1 - x_0x_1$

$B_3(x_0, x_1) = x_0x_1$

并且

$p(x_0, x_1) = 2B_0 + 5B_1 + 7B_2 + 8B_3$

替换所有内容，

$p(x_0, x_1) = 2 + 3x_0 + 5x_1 - 2x_0x_1$

通过这种方式，我们已将向量编码为具有两个变量的多线性多项式。一般来说，我们可以将长度为 $n$ 的向量编码为一个在 $\lceil \log_2(n) \rceil$ 变量中的多项式。然后，我们可以利用这个编码将某些计算的有效性简化为对多项式在所有可能的 $x_0, x_1 ... x_n$ 的值上求和。

sumcheck 协议

sumcheck 协议是一种交互式证明，首次引入于 1992 年，在复杂性理论和密码学的概率证明理论中起着重要作用，从而导致简洁论证的构造。它的一个基本属性是证明者可以在操作次数上线性缩放（即其运行时间是 O(n)），它的渐进复杂性优于基于快速傅里叶变换的算法（O(nlogn)）。它还为离散对数设置中的 Pedersen 承诺折叠技术提供了基础。有关协议的详细解释，请参见证明、论证与零知识和sumcheck 论证及其应用。

sumcheck 协议为以下形式的声明提供了交互式证明：

$\sum_{x \in H^m} p(x) = S$

即某个 $m$ 变量多项式在一个域上的所有评估的总和等于 $S$。证明者被给予多项式 $p(x)$，验证者将从集合 $C$ 中发送给他随机挑战 $r_k$，并收到多项式 $q_k(x)$，这使他可以相信声明是真实的。该协议将验证者的工作量从必须在 $|H|^m$ 上评估 $m$ 变量多项式（例如，如果 $H$ 的大小 $|H|$ 为 2，而我们有 16 个变量，我们需要进行 $2^{16}$ 次评估）减少到在 $F^m$ 中对一个随机点的单次评估，外加一些其他较小的操作。

该协议分轮进行，工作如下：

1. 证明者向验证者发送多项式

$qk(x) = \sum{a_j \in H, j \ge k+1} p(r_1, r2, ..., r{k-1}, x, a_{k+1}, ... a_m)$

2. 验证者检查 $\sum_{a_1 \in H} q_1(a1) = S$ 以及 $\sum{a_k \in H} q_k(ak) = q{k-1}(r_{k-1})$。

3. 如果所有检查都通过，验证者将输出 $v = q_m(r_m)$ 和输出 $r_1, r_2, ..., r_m, v$。

让我们用简单的术语解释一下该协议。在第一轮中，证明者通过对所有其他变量的值求和向验证者发送一个多项式 $q_1(x_1)$。这样，验证者可以通过评估多项式 $q_1(x_1)$ 的各个值来检查和，这比对所有变量求和要快得多。然而，验证者如何知道证明者没有作弊并发送某个伪造的多项式 $q_1(x_1)$ 呢？验证者发送一个随机挑战 $r_1$，证明者用一个新的一元多项式 $q_2(r_1, x_2)$ 响应，该多项式通过固定第一个坐标并对除了 $x_2$ 之外的所有其他变量求和获得。如果我们评估 $q_1(r_1)$，我们应该得到与对所有可能值 $q_2(x_2)$ 求和相同的结果（因为 $q_1$ 是通过对所有值 $x_2$ 求和获得的）。验证者总是需要对一个一元多项式进行一些评估。

如果挑战子集 $C$ 是一个采样子集，则 sumcheck 协议满足：

a. 完备性。

b. 可靠性，其中可靠性错误的上限由 $md/|C|$（变量的数量、多项式中的最大度数和挑战子集中的元素数量）来界定。

在许多情况下，我们希望使用 $H^m = {0, 1}^m$，使得 $x = (x_1, x_2, ..., x_m)$ 成为长度为 $m$ 的所有比特串的集合，我们可以使用向量作为多线性多项式的编码。

为了使 sumcheck 协议具备零知识性，我们需要对多项式进行掩码处理。我们可以通过添加随机多项式来实现这一点。

结论

在这篇文章中，我们讨论了 sumcheck 协议，它是一些 SNARKs 的核心。它允许验证者通过将大部分计算负担委托给证明者，检查某个多变量多项式在一个集合上的评估之和是否等于某个数。该协议所涉及的轮数等于变量的数量，证明者在每一轮发送一个一元多项式，验证者通过发送随机挑战来响应。验证者的最高成本涉及在一个随机点上评估多变量，这显著少于简单验证。在即将发布的文章中，我们将介绍如何从头实现 sumcheck 协议。

引言\ \ 交互式证明是证明者PP与验证者VV之间的一种协议，其中证明者试图说服验证者某一声明的有效性。通过利用随机性和交互，验证者能够比亲自做所有的工作更高效地检查该声明

TL;DR：这篇文章讨论了Pod，一种新的共识概念，通过消除不同副本之间的通信，达到了一个来回旅行（大约200毫秒）的最佳延迟。我们相信这篇论文和Pod Network的工作是突破性的，我们希望其他人能够分享我们对他们工作的热情

1月26日，Starkware通知我们，他们在Cairo VM中发现了一个关键问题，该程序可以在VM中成功执行，但会违反AIR约束。一个修复已经在一个PR中实施、合并，并且已经发布并部署。

• 原文链接： blog.lambdaclass.com/hav...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～