原文标题：《从零开始学习 zk-SNARK（四）——多项式的约束》
原文来源： 安比实验室 作者：Maksym Petkus
导读
even@ 安比实验室: 上一篇文章中我们学习了如何将程序转换为多项式进行证明。到这里似乎已经有点晕了，本文将对协议执行进一步的约束，并对协议展开优化。
作者：Maksym Petkus
翻译 & 注解：even@ 安比实验室（[email protected]）
校对：valuka@ 安比实验室
本系列文章已获作者中文翻译授权。
回顾
【零知识证明】zk-SNARK（一）——多项式的性质与证明
【零知识证明】zk-SNARK（二）——多项式非交互式零知识证明
【零知识证明】zk-SNARK（三）——从程序到多项式的构造
结构性质
上文中的修改额外带来了一些其它有用的性质。
静态系数
在上文的构造中，我们通过对 未赋值的变量多项式 的计算得到 0 或者 1，以此表示在运算中是否要用到这个变量。自然地想，我们也可以使用其它系数值，包括负数值，因为我们可以插值 计算出经过任何必要的点（前提是没有两个计算使用了同一个 x）的多项式。如下是这种运算的一些例子：
其中下标 l，r 和 o 表示变量在运算中的位置。
注意：在不同的运算和操作数/输出中，同一个变量的常量系数可以是不同的。
没有成本的做加法
看一下这个新结构，很显然在多项式的表示中，每一个不同 x 所要代表的操作数都是所有操作数变量多项式 的总和，其中只有一个被用到的变量是非零值而其它都为 0，下图就很好得表达了这个意思：
我们可以利用这一个结构，加任何数量必要的变量 到每一个运算的操作符/输出中。例如在第一个运算中，我们可以首先做加法 a+c，然后就只需要用别的操作数与之相乘了，即 (a+ c) × b = r，可以表示为下图：
因而也可以将这些变量中任意个，对它们先乘以任意的系数再一并加入到一起作为单个操作数中，以此来根据相应程序的需要构造一个操作数值。这个特性实际上就允许将运算结构改为：
注意 ：每一个运算的操作数都有自己的一组系数 c。
注解
even@ 安比实验室：乘法运算是关键，而加法运算都可以被合并到一个更大的乘法运算里面。
加法，减法和除法
到目前为止，我们一直专注于乘法操作。但是为了能够执行通用计算，真实环境下的程序也需要加法，加法和除法。
加法 在前面的章节中，我们已经确定了可以在单个操作数的内容中将变量加起来，然后和另一个操作数相乘，即 (3a + b) × d = r，但是如果我们只是想做加法，没有乘法，例如一个程序中需要做 a + b 的计算，我们可以按照下面的方式来表示：(a+b) × 1 = r
@Maksym（作者）：因为我们的结构中对于每一个操作数我们既需要常量系数也需要变量 (c ? v)，1 这个值可以表示为 c? ? v?，其中 c? = 1 可以被「硬编码」到对应的多项式中，v? 是一个变量可以给它分配任何值，那么我们就必须通过一些约束来限制 v? 的值，这个在后面的章节中将会讲到。
减法 减法与加法几乎一致，唯一的不同就是负系数，a-b 也就是：
@Maksym（作者）：运算的结构也称为「约束」，因为多项式结构代表的运算，并非是为了计算出结果，而是在 prover 已经知晓的变量赋值的情况下，检验这个运算的过程是否正确。换句话说，即约束 prover 必须提供一致的值，无论这些值是什么。
所有的算术计算（加减乘除）都已经有了，于是运算结构不再需要修改。
注解
even@ 安比实验室: 约束和运算有一定的关联性。算术电路的目的是为了实现「计算的验证」，而非「计算的过程」。
上一篇文章中，我们提出了一种方法：把构造多项式的工作交给 setup 环节，prover 只要填上对应的数值就可以了。这个方法不仅解决了同一个操作数运算符中不一致的问题，同时还带来了额外的便利：
1）允许执行计算的表达式中包含静态系数。
2）虽然 l(x)·r(x)=o(x) 的关系中只有乘法，但利用这个方法也可以轻松的执行加法操作，继而也就解决了减法和除法的问题。
计算示例
有了一组通用的运算结构，我们就可以将我们原始的程序（上一篇文章中的例子）转换成一组运算，然后再转换成多项式的形式。我们先来想一下算法的数学形式（用变量 v 表示运算结果）：
要了解为什么 w 只能为 0 或者 1，我们可以把等式表示为 w? – w = 0，也就是 (w – 0)(w – 1) = 0 这里 0 和 1 是唯一解。
现在一共有 5 个变量，以及 2 个左操作符，4 个右操作符和 5 个输出。操作符多项式为：
绘制出来就是：
我们准备通过多项式去证明计算，首先，选择函数的输入值，例如：w = 1, a = 3, b= 2。其次，计算过程中的中间变量值为：
m=a × b =6
v = w(m-a-b)+a+b=6
然后，我们把所有计算结果中的值赋值到 变量多项式 中，然后相加得到操作数或者输出多项式的形式：
在图中就表示为：
把他们相加成对应运算中的操作数和输出值：
我们需要去证明 L(x) × R(x) – O(x) = t(x)h(x)，因而我们先找出 h(x)：
以图的形式表示为：
这里很明显多项式 L(x) × R(x) – O(x) 的解为 x= 1，x= 2 和 x= 3，因而 t(x) 是它的因式，假如使用了和它不一致的变量值，情况就不是这样了。
这就是一组能够正确计算的变量值，如何在多项式层面上证明出来的。下面 prover 还要再继续处理协议的密码学部分。
可验证计算协议
我们基于前文中多项式知识协议 做了很多重要的修改使它变得更通用，我们再来看一下它现在的定义。假定函数 f(*) 是要证明的问题中的计算结果，其中操作数的数量为 d，变量的数量 n，以及它们对应的系数为：
对于 i ∈ {1, …, n} 所有变量多项式 {l?(x), r?(x), o?(x)} 和目标多项式 t(x) 的设置被称为一个二元算术程序 (QAP，在 [Gen+12[1]] 中有介绍)。
虽然协议足够健壮，可以进行常规的计算验证，但这里依然还有两个安全考虑需要去解决。
操作数和输出的不可交换性
因为在 变量多项式约束检查 中的所有操作数上我们使用了同一个 α，所以就没有办法阻止 prover 做下面的欺骗行为：
使用其它的操作数中的可变多项式，即 L′(s) = o?(s) + r?(s) + r?(s) + …
完全交换 操作数多项式，也就是把 O(s) 和 L(s) 换成 O(s) × R(s) = L(s)
复用相同的操作数多项式，即 L(s) × L(s) = O(s)
可交换性就是指 prover 可以修改计算过程，并有效证明一些其它无关的计算结果。防止这种行为的一个很显然的方式就是在不同的操作数上使用不同的 αs，具体协议就可以修改为：
注解
even@ 安比实验室: 这里通过对 l(x),r(x) 和 o(x) 进行分开 KEA 检查，就解决了上篇文章中提出的第二个缺陷问题——由于 prover 生成的证明中只有计算结果，左操作数，右操作数，输出在计算中混用也不会被发现。
同样下面一节也解决了上篇文章中提出的第三个缺陷问题——由于左操作数，右操作数，输出是分开表示的，互相之间的关系无法进行约束。
跨操作数的变量一致性
对于任意的变量 v?，我们都必须将它的值分配 到每个相应操作数中的一个与之对应的变量多项式上，即：
注解
even@ 安比实验室: 回忆一下，上文中我们提出了在 setup 阶段设置数学表达式的约束关系来解决了一些问题，但这里似乎有引入了一个问题：如果保证 prover 构造的证明是用遵循这些约束关系计算出来的呢？
KEA 其实已经解决了这个问题，但似乎并不完美，这就是我们下面要讨论的变量延展性问题。
变量非延展性和变量一致性多项式
变量多项式的延展性
举一个 remark 4.1 有关的例子，看一下下面的两个运算：
注解
even@ 安比实验室：这种能力会危害到协议的可靠性。很显然，加密的 βs 不应该对 Prover 可见。
非延展性
解决延展性问题的一个方法就是，在 setup 阶段将 verification key 中加密的 βs 项与随机秘密值 γ(gamma) 相乘使其与加密值 Z(s) 不兼容：
我们同样也可以通过修饰 αs 项来解决变量多项式 的延展性问题。但是这就没有必要了，因为对于变量多项式 的任何修改，都需要被映射到变量的一致性多项式 中，而一致性多项式是无法修改的。
变量值一致性检查的优化
现在变量值一致性 检查是有效的，但是这里在 verification key 中增加了 4 个昂贵的配对操作和 4 个新的项。文献 [Par+13[2]] 中的 Pinocchio 协议用了一个很聪明的方法优化，通过选择不同的生成元 g，从而对每个操作数实行「移位」：
生成元的这种随机化进一步增加了安全性，使得如 remark 4.1 中描述的可变多项式 延展性无效。因为对于故意的修改，它必须要么是ρl, ρr 或者ρo 原始值的倍数要么就是不可直接用的加密值的倍数（假定, 如上文所述我们不去处理可能曝光加密后的值的 0 阶可变多项式）。
这个优化使得 verification key 减少了两个项，并且去除了 verification 步骤中的两个配对运算。
注意：在 Jens Groth 2016 年的 paper [Gro16[3]] 中有更进一步的改进。
注解
even@ 安比实验室:至此，通用 zk-SNARK 协议的已经几乎构造完成了，
本文可以归纳为以下几点：
协议中是如何增加可变系数的和如何做加减乘除运算的
协议如何保证操作数和输出的不可替代性
协议如何保证跨操作数的可变一致性
协议如何处理非延展性变量和变量一致性
协议中变量值一致性检查优化
原文链接
https://arxiv.org/pdf/1906.07221.pdf
https://medium.com/@imolfar/why-and-how-zk-snark-works-5-variable-polynomials-3b4e06859e30
https://medium.com/@imolfar/why-and-how-zk-snark-works-6-verifiable-computation-protocol-1aa19f95a5cc
参考文献
[Par+13]—Bryan Parno, Craig Gentry, Jon Howell, and Mariana Raykova. Pinocchio: Nearly Practical Verifiable Computation. Cryptology ePrint Archive, Report 2013/279. https://eprint.iacr.org/2013/279. 2013.
[Gen+12]—Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic Span Programs and Succinct NIZKs without PCPs. Cryptology ePrint Archive, Report 2012/215. https://eprint.iacr.org/2012/215. 2012.
[Gro16]—Jens Groth. On the Size of Pairing-based Non-interactive Arguments. Cryptology ePrint Archive, Report 2016/260. https://eprint.iacr.org/2016/260. 2016.
来源链接：weixin.qq.com
区块律动 BlockBeats 提醒，根据银保监会等五部门于 2018 年 8 月发布《关于防范以「虚拟货币」「区块链」名义进行非法集资的风险提示》的文件，请广大公众理性看待区块链，不要盲目相信天花乱坠的承诺，树立正确的货币观念和投资理念，切实提高风险意识；对发现的违法犯罪线索，可积极向有关部门举报反映。
—-
编译者/作者：区块律动BlockBeat
玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。
|
