SYM:二次算术程序：关于零知识证明的论述

作者：VitalikButerin

原标题：《QuadraticArithmeticPrograms:fromZerotoHero》

发表时间：2016年12月10日

最近人们对zk-SNARKs背后的技术有很多兴趣，人们越来越多地试图去揭开一些被许多人称为“月球数学”的东西的神秘面纱，因为人们认为它的复杂性非常难以理解。zk-SNARKs的理解确实相当具有挑战性，尤其是由于整个系统需要组装起来才能工作的移动部件太多，但如果我们把这项技术一件一件地分解，那么理解起来就会变得更简单。

这篇文章的目的不是用于完整的介绍zk-SNARKs，它假定您具有以下背景知识：

1-你知道zk-SNARKs和他的大致原理；

2-你有足够的数学知识，能理解一些基本的多项式知识。(如ifP(x)+Q(x)=(P+Q)(x)，P和Q代表多项式，如果你对这类多项式表述方式已经非常熟悉，说明你符合继续阅读的要求)。

zk-SNARK知识管道图，EranTromer绘制

如上图，可以将以上零知识证明分为由上至下的两个阶段。首先，zk-SNARK不能直接应用于任何计算问题；相反，您必须将问题转换为操作的正确“形式”。这种形式被称为“二次算术程序”(QAP)，将函数的代码转换成这些代码本身就非常重要。与将函数代码转换为QAP的过程一起运行的还有另一个过程，这样，如果对代码有输入，就可以创建相应的解决方案(有时称为QAP的“见证”)。这就是本文需要讲述的内容。

在此之后，还有另一个相当复杂的过程来为这个QAP创建实际的“零知识证明”，还有一个单独的过程来验证别人传给你的证据，但是这些细节超出了本文的范围。

Gitcoin将与联合国儿童基金会合作启动Grants Protocol二次方融资试点:11月22日消息，Gitcoin宣布与联合国儿童基金会（UNICEF）创新办公室建立合作关系，将于12月9日至12月16日在Gitcoin新赠款协议Grants Protocol中推出二次方融资（QF round）试点，为来自世界各地（包括尼泊尔、肯尼亚、阿根廷、巴西和菲律宾）的12个创新项目提供二次方资助。

Gitcoin表示，此次捐赠轮标志着Gitcoin过渡到去中心化协议的开端，Grants Protocol将允许任何社区协调自己的赠款资金。[2022/11/22 7:56:51]

在下面示例中，我们将选择一个非常简单的问题：

求一个三次方程的解:x**3+x+5==35(提示:答案是3)。

这个问题很简单，但是重要的，你可以由此案例看到所有的功能是如何发挥作用的。

用编程语言描述以上方程如下：

defqeval(x):??y=x**3??returnx+y+5我们在这里使用的简单编程语言支持基本的算术(+、-、、/)、恒等幂指数(x7，但不是x*y)和变量赋值，这足够强大到理论上可以在其中进行任何计算(只要计算步骤的数量是有界的;不允许循环)。注意模(%)和比较运算符(<、>、≤≥)不支持,因为没有有效的方法做模或直接比较有限循环群算法(感谢;如果有任何一种方法可以做到这一点，那么椭圆曲线密码破环的速度将超过“二分查找”和“中国剩余定理”)。

您可以通过位分解来将语言扩展到模和比较，不过请注意，条件的两个“路径”都需要执行，如果您有许多嵌套的条件，那么这会导致大量开销。

BCA CMO Susan Bai：IP赋能社群二次创作，打造可持续发展的元宇宙:9月3日消息，BCA CMO Susan Bai在《HyperPay 焦点》第20期，主题为“《走进元宇宙》系列：IP 如何助力NFT出圈“专场AMA中提到：NFT真正的魅力和魔力在于来源于社群自发的共识度，和IP给社群赋能二次创作的应用场景。玩家们可以真正的利用IP满足他们在虚拟和现实世界的真实需求。这样的IP创作才是真正符合区块链文化以及更加可持续发展的方向。如果还能将NFT赋能一些真实的效用，能够满足用户在虚拟和现实世界的社交需求，甚至能衍生出一个元宇宙来承载NFT的成长线。[2021/9/3 22:58:01]

现在让我们一步一步地经历这个过程。如果你想自己做任何代码，我在这里用Python实现了一段代码

第一步：压扁

第一步是一个“压扁”的过程，我们把原来的代码分解为最简单的表达式，这种表达式有两种形式:

1-x=y（y可以是变量或数字)2-x=y(op)z(op可以+,-,*,/，y和z可以是变量，数字或子表达式)。

你可以把这些表述看成是电路中的逻辑门。上述表达式x**3+x+5的扁平化过程结果如下:

sym_1=x*xy=sym_1*x//相当于实现了幂函数y=x**3sym_2=y+x~out=sym_2+5

你可以认为上述的每一行声明都是一个电路中的逻辑门，与原始代码相比，这里我们引入了两个中间变量sym_1和sym_2，还有一个表示输出的冗余变量~out，不难看出“压扁”后的声明序列和原始代码是等价的。

第二步：转为R1CS

现在，我们把它转换成一个称为R1CS的东西。R1CS是由三个向量(a,b,c)组成的序列，R1CS的解是一个向量s，其中s必须满足方程

Filecoin Plus完成第二次公证人选举:据Filecoin基金会消息，Filecoin Plus社区最近举行了自成立以来的第二次公证人选举。在本届选举中，要求更改为允许在北美、欧洲和中国至少有五名公证人。这样做是为了响应这些地区增加的DataCap应用和更高的Filecoin Plus社区参与度。由于对资源的需求不断增加，现在每个地区最多可以有七名公证人，以满足DataCap的预期分配。迄今为止，公证人已向所有地区的客户授予了大约800 TB的DataCap，这些客户已在Filecoin网络上使用DataCap存储了超过250 TB的数据。通过这一轮公证人选举，已授予5.3 PB的新DataCap，比上次选举周期显著增加，上次选举周期将1.9 PB的DataCap授予公证人。[2021/6/30 0:16:00]

s.a*s.b-s.c=0

其中.代表内积运算。

例如，以下是一个令人满意的R1CS：

a=(5,0,0,0,0,1)，b=(1,0,0,0,0,0)，c=(0,0,1,0,0,0)，s=(1,3,35,9,27,30)，

上述例子只是一个约束，接下来我们要将每个逻辑门转化成一个约束，转化的方法取决于声明是什么运算(+,-,*,/)和声明的参数是变量还是数字。在我们这个例子中，除了“压扁”后的五个变量('x','~out','sym_1','y','sym_2')外，还需要在第一个分量位置处引入一个冗余变量~one来表示数字1，就我们这个系统而言，一个向量所对应的6个分量是(可以是其他顺序，只要对应起来即可)：

'~one','x','~out','sym_1','y','sym_2'

动态 | 美德克萨斯州相关执法部门二次整顿当地加密货币投资产品:美国德克萨斯州证券专员Travis J. Iles已三次下达紧急禁令，禁止从事加密货币相关欺诈性投资的发起人通过Facebook的“在家办公”论坛招揽德克萨斯居民。 这些指令源自州证券委员会执法部门的一项举措。在比特币价格在过去三个月价格暴涨之后，该部门上周开始对可疑的加密货币产品展开全面调查。这是该执法部门对加密货币投资产品的第二次监管整顿。[2019/6/30]

第一个门

sym_1=x*x，即x*x-sym_1=0

我们可以得到如下向量组：

a=b=c=

如果解向量s的第二个标量是3，第四个标量是9，无论其他标量是多少，都成立，因为：a=3*1,b=3*1,c=9*1，即a*b=c。同样，如果s的第二个标量是7，第四个标量是49，也会通过检查，第一次检查仅仅是为了验证第一个门的输入和输出的一致性。

第二个门

y=sym_1*x，即sym_1*x-y=0可以得到以下向量组：

a=b=c=

第三个门

sym_2=y+x，加法门需要转换为：(x+y)*1-sym_2=0得到以下向量组：

a=b=对应常量1，用~one位c=

第四个门

~out=sym_2+5，即(sym_2+5)*1-~out=0得到以下向量组：

a=b=c=

现在，我们假设x=3，根据第一个门，得到sym_1=9，根据第二个门得到y=27，根据第三个门，得到sym_2=30，根据第四个门得到~out=35，因此，根据：'~one','x','~out','sym_1','y','sym_2'，可以得到：

动态 | 火币大学方军：区块链是互联网二次革命:据参考经济网消息，火币大学顾问合伙人方军在火币大学主办的“区块链赋能实体”沙龙中发表演讲中称，区块链就是互联网二次革命。区块链这个新技术将重构互联网平台，它有潜力改变我们的经济模型，改变我们的商业模式，改变我们的组织方式。技术在实体经济的应用，也将从“互联网+”走向“区块链+”。[2018/11/6]

s=

如果假设不同的x，都可以得到不同的s，但所有s都可以用来验证(a,b,c)

现在我们得到了四个约束的R1CS，完整的R1CS如下：

A

B

C

第三步：从R1CS到QAP

下一步是将这个R1CS转换成QAP形式，它实现了完全相同的逻辑，只是使用多项式而不是内积。我们是这样做的：从4组长度为6的3个向量到6组长度为3度的多项式，在每个x坐标处求多项式代表一个约束条件。也就是说，如果我们求出x=1处的多项式，我们就得到了第一组向量，如果我们求出x=2处的多项式，我们就得到第二组向量，以此类推。

我们可以用拉格朗日插值来做这个变换。拉格朗日插值法解决的问题是：如果你有一组点(即(x,y)坐标对），然后对这些点做拉格朗日插值得到一个经过所有这些点的多项式。我们通过分解问题：对于每个x坐标,我们创建一个多项式,所需的y坐标的x坐标和y坐标0在所有其他的x坐标我们感兴趣，然后让最终结果我们一起添加所有的多项式。

让我们做一个例子。假设我们想要一个多项式经过(1,3),(2,2)和(3,4)。我们首先做一个多项式，经过(1,3)(2,0)和(3,0)。事实证明,一个多项式,“伸出”x=1和0的其他的兴趣点是很容易的，我们只要做以下多项式即可：

y=(x-2)*(x-3)

如下图：

然后，在y轴方向“拉伸”，使用如下方程：

y=(x-2)*(x-3)*3/((1-2)*(1-3))

经整理，得到：

y=1.5*x**2-7.5*x+9

满足同时经过(1,3)(2,0)和(3,0)三个点，如下图：

将(2,2)和(3,4)两点代入上式，可以得到：

y=1.5*x**2-5.5*x+7

就是我们想要的坐标方程。上述算法需要O(n3)时间，因为有n个点，每个点都需要O(n2)时间将多项式相乘。稍微思考一下，这就可以减少到O(n**2)的时间，再多思考一下，使用快速的傅里叶变换算法等等，它可以进一步减少——这是一个关键的优化，当在zk-spuks中使用的函数通常有成千上万个门时。

在这里我直接给出拉格朗日插值公式：

通过n个点(x1,y1),(x2,y2),(x3,y3),...,(xn,yn)的n-1阶多项式为：

例如上例中，通过点(1,3),(2,2),(3,4)的多项式为：

学会使用这个公式后可以继续我们的步骤了。现在我们要将四个长度为六的三向量组转化为六组多项式，每组多项式包括三个三阶多项式，我们在每个x点处来评估不同的约束，在这里，我们共有四个约束，因此我们分别用多项式在x=1,2,3,4处来评估这四个向量组。

现在我们使用拉格朗日差值公式来将R1CS转化为QAP形式。我们先求出四个约束所对应的每个a向量的第一个值的多项式，也就是说使用拉格朗日插值定理求过点(1,0),(2,0),(3,0),(4,0)的多项式，类似的我们可以求出其余的四个约束所对应的每个向量的第i个值的多项式。

这里，直接给出答案：

Apolynomials

Bpolynomials

Cpolynomials

这些系数是升序排序的，例如上述第一个多项式是0.833*x**3-5*x**2+9.166*x-5.如果我们将x=1带入上述十八个多项式，可以得到第一个约束的三个向量

(0,1,0,0,0,0),(0,1,0,0,0,0),?(0,0,0,1,0,0),...类似的我们将x=2,3,4带入上述多项式可以恢复出R1CS的剩余部分。

第四步：检查QAP

通过将R1CS转换成QAP我们可以通过多项式的内积运算来同时检查所有的约束而不是像R1CS那样单独的检查每一个约束。如下图所示：

因为在这种情况下，点积检验是一系列多项式的加法和乘法，结果本身就是一个多项式。如果得到的多项式，在我们上面用来表示逻辑门的每一个x坐标处的值，等于0，那就意味着所有的检查都通过了；如果结果多项式至少有一个非零值，那么这就意味着进出逻辑门的值是不一致的。

值得注意的是，得到的多项式本身不一定是零，事实上在大多数情况下不是;它可以在不符合任何逻辑门的点上有任何行为，只要在所有符合某些门的点上结果是零。为了验证正确性，我们不计算多项式t=A.s*B.s-C.s在每一点对应一个门；相反，我们把t除以另一个多项式Z，然后检查Z是否均匀地除t，也就是说，除法t/Z没有余数。

Z定义为(x-1)*(x-2)*(x-3)…-最简单的多项式，在所有对应逻辑门的点上都等于0。这是代数的一个基本事实任何多项式在所有这些点上等于零都必须是这个最小多项式的倍数，如果一个多项式是Z的倍数那么它在任何这些点上的值都是零；这种对等使我们的工作容易得多。

现在，让我们用上面的多项式做内积检验。

首先，我们得到中间多项式：

A.s=B.s=C.s=（译者注：以上计算过程：43.0=-5*1+8*3+0*35-6*9+4*27-1*30，-73.333=9.166*1-11.333*3+0*35+9.5*9-7*27+1.833*30,...-3=3*1-2*3+0*35+0*9+0*27+0*30...)

以上多项式经过：A.s*B.s-C.s计算后得到：

t=（译者注：计算过程：A.s==-5.166*x3+38.5*x2-73.333*x+43,B.s==0.666*x3-5*x2+10.333*x-3.0,C.s==2.833*x3-24.5*x2+71.666*x-41.0A.s*B.s-C.s就是上面多项式的计算，计算后，按幂从低到高排列系数，得到：

点击这里查看计算过程

最小多项式为：

Z=(x-1)*(x-2)*(x-3)*(x-4)

即：

Z=

以上计算过程点击这里查看

现在计算多项式相除：

h=t/Z=

h必须是没有任何余数的整除。

可以点这里查看到过来验证。

我们有了QAP的解。如果我们试图伪造R1CS中的变量，而这个R1CS推导出了QAP解决方案——比如,将s的最后一个数字设为31，而不是30，我们将得到一个t多项式失败的检查(在特定情况下,在x=3=1而不是0),而且不会是Z的倍数;相反，除以t/Z会得到的余数。

注意，以上只是一个非常简单的示例；在现实世界中，加减乘除运算通常伴随着非常规的数字，所以所有的我们知道并且爱戴的代数定律还是有用的，但是，所有答案是一些——的尺寸的元素，通常是从0到n-1范围内的整数n。例如，如果n=13,然后1/2=7(7*2=1),3*5=2,等等。使用有限域算法消除了对舍入误差的担心，并允许系统与椭圆曲线很好地工作，这最终对使zk-SNARK协议变得真正安全。

标签：SYMCOICOINOINSYM价格EVCOIN价格BCOIN价格coinbase中文叫什么交易所

比特币交易热门资讯