你check 过你的 sum 吗？

引言

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

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

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

在nn个变量中，一项多项式pp被称为多线性，如果每个变量xixi的度数在每一项中最多为1。例如，p1(x1,x2,x3,x4)=x1+2x2+x1x2x4x3是一个多线性多项式，因为每个xixi的幂在每一项中都要么为0，要么为1。多项式p2(x1,x2)=x1x22不是，因为x2的度数为2。多线性多项式的总度数是项（单项式）中所有幂的最大和。对于p1来说，这个值是4。对于多线性多项式，最大度数最多为mm。

我们现在将限制在定义在集合D=0,1m上的多项式内。给定定义在DD上的函数ff，我们可以定义一个多线性多项式p(x1,x2,...,xm)，使得pp与DD上的ff一致，即对于每个x∈D，有p(x)=f(x)。由于这个多项式是唯一的，因此这个多项式pp被称为ff的多线性扩展。

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

f(0,0,0,0,0,0,0,0)=v0

f(0,0,0,0,0,0,0,1)=v1

f(0,0,0,0,0,0,1,0)=v2

f(0,0,0,0,0,0,1,1)=v3

⋮

f(1,1,1,1,1,1,1,1)=v255

一般形式中，我们将元组(x0,x1,...xm−1)赋值为索引k对应的值k=x0+2x1+4x2+⋯+2m−1xm−1。然后，我们可以利用存在的ff的多线性扩展，通过拉格朗日插值创建它。例如，

p(x0,x1,...xm−1)=∑x0,...,xm−1f(k)Bk(x0,x1,...,xm−1)

其中Bk是拉格朗日基多项式，当(x0,x1,...,xm−1)对应于k的二进制表示时等于1，否则等于0。如果我们表示k=(k0,k1,...km−1)（请记住每个kiki都是0或1），函数Bk(x0,x1,...,xm−1)具有显式表达式

Bk(x0,x1,...,xm−1)=∏(xiki+(1−xi)(1−ki))

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

B0(x0,x1)=(1−x0)(1−x1)=1−x1−x0+x1x0

B1(x0,x1)=x0(1−x1)=x0−x0x1

B2(x0,x1)=(1−x0)x1=x1−x0x1

B3(x0,x1)=x0x1

并且

p(x0,x1)=2B0+5B1+7B2+8B3

替换所有内容，

p(x0,x1)=2+3x0+5x1−2x0x1

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

sumcheck协议

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

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

∑x∈Hmp(x)=S

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

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

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

qk(x)=∑aj∈H,j≥k+1p(r1,r2,...,rk−1,x,ak+1,...am)

2. 验证者检查∑a1∈Hq1(a1)=S以及∑ak∈Hqk(ak)=qk−1(rk−1)。

3. 如果所有检查都通过，验证者将输出v=qm(rm)和输出r1,r2,...,rm,v。

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

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

a. 完备性。

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

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

为了使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 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～