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

作者：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创建实际的“零知识证明”，还有一个单独的过程来验证别人传给你的证据，但是这些细节超出了本文的范围。

Filecoin将于2021年10月15号进行第二次减产:根据Filecoin官方释放规则，Filecoin将于2021年10月15号迎来第二次减产，SAFT一年期全部线性释放完毕，10月15日FIL12到期后，每天流通到市场的FIL将减少87183枚，FIL每天的流通量预计减少29057枚，每日释放的FIL将减少23.8%。[2021/8/19 22:24:24]

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

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

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

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

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

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

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

第一步：压扁

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

AOFEX交易所完成平台币OT第二次常规解锁:据官方消息，AOFEX交易所已于8月13日15点完成平台币OT的第二次常规解锁。本次解锁是根据用户于8月13日15:00所快照的锁仓OT数量为基准，释放六分之一的数量，完成解锁的OT可用于二级市场自由交易。

A网将持续增加平台币流通场景，打造平台币价值，并保证市场流通量不超过2000万枚。

AOFEX是领先的数字货币金融衍生品交易所，旨在为用户提供优质服务和资产安全保障。[2020/8/13]

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必须满足方程

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)，

动态 | 嘉楠耘智二次更新招股书，前9月收入逾9.5亿元:金色财经报道，11月5日，嘉楠耘智美股招股书预披露第二次更新，计划募资4亿美元。最新数据显示，今年前9月，嘉楠耘智总营收已达9.594亿人民币。同时，嘉楠耘智在2017年、2018年和截至2019年9月30日的9个月里，累计量产了超过1.5亿颗ASIC。此外，该公司目前已经售出逾5万套AI芯片和模组。[2019/11/7]

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

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

第一个门

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=

第三个门

动态 | 加密货币Nano开发者面临第二次集体诉讼:据CCN报道，加密货币Nano开发者及其他各方正面临第二次集体诉讼。上周五，在加州联邦法院提出的诉讼中，对他们的指控包括欺诈和违反《证券法》。该诉讼声称被告了投资者。Nano曾经价值超过50美元，但现在只有1美元左右。[2019/1/7]

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'，可以得到：

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处的多项式，我们就得到第二组向量，以此类推。

动态 | Monero第二次算法更新即将到来 预计升级之后难度会小幅回落:据财经网消息，Monero核心团队成员@fluffypony将名为Cryptonight variant 2的pull request合入了主分支，这意味着Monero的第二次算法更新即将到来。

算法的具体改动总结如下：

1.整个改动只涉及到约500行代码，是一些小改动，并没有改动算法的核心部分，所以之前流传的比如新算法不能用CPU挖或者不能用3G以下显存挖均是谣言；

2.具体升级的区块高度没有包含在这个pull request里，意味着升级时间还没确定；

3.这个改动会让ASIC矿机再次失效（如果有的话），同时可能会让开发新ASIC的难度变高；

按照上一次升级的经验，矿工只需要在升级时间之前，将自己的挖矿软件更新到最新版，同时确保矿池也是最新版本，就可以平滑迁徙。据悉，9月初难度已经开始上升，预计这次升级之后难度会有小幅回落。CoinMarketCap行情显示，Monero（XMR）全球均价现为106.15美元，24小时涨幅6.63%。[2018/9/13]

我们可以用拉格朗日插值来做这个变换。拉格朗日插值法解决的问题是：如果你有一组点(即(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协议变得真正安全。

标签：SYMOUTARKONEsymbiosisfinance币创始人South African TetherMARKS币StoneDAO

火必APP热门资讯