VER:零知识证明之zk-SNARK（一）多项式的性质与证明

导读

17 年最早接触 zk-SNARK 开始，就断断续续得学习了一些 zk-SNARK 的知识，但对其原理始终存在诸多困惑，没有形成一个完整的认识。偶然一次机会，看到了 Maksym Petkus 的这篇文章。文章从最基本的多项式性质讲起，从一个简单易懂的证明协议开始，然后像堆积木一样在发现问题，修改问题中逐步去完善协议，直到最终构造出完整的 zk-SNARK 协议。另外作者这种从问题出发的讲解方式，让读者知其然，也知其所以然。作为一枚毕业多年早把数学知识还给老师的程序媛，读到这篇文章如获至宝，这篇文章读下来的感受像找到了一个脚手架，将脑海里碎片化的知识逐渐拼凑完整。于是想把它翻译出来（已获得作者授权），一方面加深自己的学习，另一方面也将这份宝藏分享给小伙伴们。文章翻译存在不足之处，欢迎纠正，补充，指导。

——even@ 安比实验室

Maksym（作者）：不管是原始的论文 [Bit+11]; [Par+13] 还是原理讲解 [Rei16]; [But16]; [But17]; [Gab17]，其实市面上已经有大量关于 zk-SNARK 的学习资源了。zk-SNARK 由大量的可变模块组成，所以对很多人来说它依然像一个黑盒子一样很难懂。这些资料对 zk-SNARK 中的一些技术难题部分做出了解释，但由于缺少了对应的其它环节的解释，大家还是很难通过这些资料了解到 zk-SNARK 的全貌。当我第一次了解到 zk-SNARK 技术是如何将这些东西完美地融合在一起的时候，就被数学之美震撼到了，并且随着我发现的维度越多，好奇心就越强烈。在这篇文章中，我主要就基于一些实例简洁明了地阐明 zk-SNARK，并对这里面的很多问题做出了解释，并利用这种方式分享了我的经验，进而让更多人也能够欣赏到这项最先进的技术以及它的创新之处，最终欣赏到数学之美。这篇文章的主要贡献是比较简洁明了的解释了其中相当复杂的技术，这些简单的解释对于在不具备任何与之相关的先决知识，比如密码学和高等数学，的前提下理解 zk-SNARK 是很有必要的。文章中并不仅仅只解释 zk-SNARK 是如何工作的，还解释了为什么这样就可以工作，以及它是怎么来的。序言和介绍尽管最初计划写短一些，但现在已经写了几十页了，不过这篇文章读起来几乎不需要什么预备知识，并且你也可以随意跳过熟悉的部分。如果你不熟悉文中使用的某些数学符号也不需要担心，文中将会对这些符号逐个进行介绍。

Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK) 确实是一种非常精妙的方法，它可以在不揭示任何信息的前提下证明某个论断为真。但首要问题是，它为什么有用？

其实零知识证明在无数的应用中都具备优势，包括：

2）匿名认证：在不揭露身份的情况下（比如登录密码），证明请求者 R 有权访问网站的受限区域证明一个人来自一组被允许的国家/地区列表中的某个国家/地区，但不暴露具体是哪个证明一个人持有地铁月票，而不透露卡号

3）匿名支付：付款完全脱离任何一种身份纳税而不透露收入

4）外包计算将昂贵的计算外包，并在不重新执行的情况下验证结果是否正确；它打开了一种零信任计算的类别

改进区块链模型，从所有节点做同样的计算，到只需一方计算然后其它节点进行验证

零知识证明Layer 2 CryptoGPT完成1000万美元融资:金色财经报道，零知识证明 Layer 2 CryptoGPT 以 2.5 亿美元估值融资 1000 万美元，DWF Labs 领投。新资金将用于在全球范围内发展其开发团队，并在亚洲市场建立区域影响力。[2023/4/11 13:55:25]

和「零知识证明」这个伟大的名词一样，其背后的方法可以说是数学和密码学的奇迹。自 1985 年，零知识证明这个概念在「交互式证明系统的知识复杂性」[GMR85] 一文中被引入，还有随后的非交互式零知识证明 [[BFM88] 以来（在区块链环境中尤其重要），至今已经进入到第四个十年的研究。

在任意的「零知识证明」系统中，都有一个 prover 在不泄漏任何额外信息的前提下要让 verifier 确信某些陈述（Statement）是正确的。例如 verifier 仅能知道 prover 的银行账户金额超过 X（也就是不披露实际金额）。协议应当满足下面三个性质：

完整性——只要「陈述」是正确的，prover 就可以让 verifier 确信可靠性——如果「陈述」是错误的，那么作弊的 prover 就没有办法让 verifier 相信零知识——协议的交互仅仅揭露「陈述」是否正确而不泄漏任何其它的信息

zk-SNARK 这个术语本身是在 [Bit+11] 中引入的，它在 [Gro10] 的基础上，又遵循了匹诺曹协议 [Gen+12; Par+13] 使其能够适用于通用的计算。证明的媒介这里我们先不要去管零知识，非交互性，其形式和适用性这些概念，就从尝试证明一些简单的东西开始。

想象一下我们有一个长度为 10 的位数组，现在要向 verifier（例如，程序）证明这样一个陈述：所有的位都被设置成了 1。

verifier 一次只能检查（即，读）一位。为了验证这个陈述，我们以某种任意的顺序读取元素并检查其是否确实等于 1。如果第一次抽样检查的结果是 1，就设置「陈述」的可信度为 ?= 10％，否则，如果等于 0，就说明「陈述」是错误的。验证者继续进行下一轮验证，直到获得足够的可信度为止。假如在一些场景下要信任 prover 需要至少 50% 的可信度，那就意味着必须执行 5 次校验。但假如在其它一些场景下需要 95% 的可信度，就需要检查所有的元素。很明显这个证明协议的缺点是必须要根据元素的数量进行检查，如果我们处理数百万个元素的数组，这么做是不现实的。

现在我们来看一下由数学方程式表示的多项式，它可以被画成坐标系上的一条曲线：

上面的曲线对应多项式: f(x) = x3 – 6x2 +11x– 6。多项式的阶数取决于 x 的最大指数，当前多项式的阶数是 3。

多项式有一个非常好的特性，就是如果我们有两个阶为 d 的不相等多项式，他们相交的点数不会超过 d。例如，稍微修改一下原来的多项式为 x3 – 6x2 + 10x– 5（注：请注意这里只修改了多项式的最后一个系数，6 改成了 5）并在图上用绿色标出：

Dora Grant DAO第二轮零知识投票环节结束:2月17日消息，Dora Grant DAO已于北京时间11月15日23:59在开发者激励平台DoraHacks.io关闭第二轮零知识投票通道。投票最终结果和对投票结果的零知识证明将于18日公布，第二期100,000美金资助的分配将由社区投票和入围项目尽职调查结果决定。

Dora Grant DAO计划旨在持续支持在以下三个领域的多链Web3开源极客团队: Dora Factory / DoraHacks生态延伸基础设施，多链Web3核心基础设施和工具, 加密-前沿科技交叉领域。[2023/2/17 12:12:38]

这一点微小的修改就产生了变化很大的曲线。事实上，我们不可能找到两条不同的曲线，他们会在某段区域内重合（他们只会相交于一些点）。

这是从找多项式共同点方法中得出的性质。如果要查找两个多项式的交点，就要先令它们相等。例如，要找到多项式与 x 轴的交点（即 f(x) = 0），我们就要令 x3 – 6x2 + 11x – 6 = 0，等式的解就是共同点：x= 1，x= 2 和 x= 3。在上面图中也可以很清晰得看出这些解，也就是图上蓝色曲线和 x 轴相交的地方。

同样，我们也可以令上文中原始的多项式和修改后的多项式相等，找到它们的交点。x3 – 6x2 + 11x – 6 =x3 – 6x2 + 10x – 5x-1=0多项式化简后的结果阶数为 1，它有一个很明显的解 x = 1。因而这两个多项式有一个交点。任意一个由阶数为 d 的多项式组成的等式，最后都会被化简为另外一个阶数至多为 d 的多项式，这是因为等式中没有能够用来构造更高阶数的乘法。例如：5x3 + 7x2 – x + 2 = 3x3 – x2 + 2x– 5，简化为 2x3 + 8x2 – 3x + 7 = 0。另外代数的基本原理也告诉我们，对于一个阶数为 d 的多项式至多有 d 个解（以下部分将对此进行详细介绍），因而也就至多有 d 个共同点。

所以我们可以得出结论，任何多项式在任意点的计算结果（更多关于多项式求值参考：[Pik13]）都可以看做是其唯一身份的表示。我们来计算一下当 x = 10 时，示例多项式的结果。

x3 – 6x2 +11x - 6 = 504x3 – 6x2 +10x - 5 = 495

事实上，在 x 可以选择的所有值中，至多只有三个值能够使这些多项式相等，其它的值都是不相等的。

这也是为什么如果一个 prover 声称他知道一些 verifier 也知道的多项式（无论多项式的阶数有多大）时，他们就可以按照一个简单的协议去验证：

verifier 选择一个随机值 x 并在本地计算多项式结果verifier 将 x 值给到 prover，并让他计算相关的多项式结果prover 代入 x 到多项式计算并将结果给到 verifierverifier 检查本地的计算结果和 prover 的计算结果是否相等，如果相等那就说明 prover 的陈述具有较高的可信度

Polygon Zero宣布其零知识验证系统Plonky2已开源:8月17日消息，Polygon 旗下零知识技术开发商 Polygon Zero（原 Mir）在其社交平台宣布其零知识验证系统 Plonky2 已开源。

此前报道，1 月 11 日，Polygon Zero 宣布推出递归 SNARK 解决方案 Plonky2，并可与以太坊兼容。官方介绍，使用 Plonky2，用户可以在笔记本电脑上仅 0.17 秒内生成递归零知识证明，比目前的速度快了近 100 倍。[2022/8/17 12:30:17]

例如，我们把 x 的取值范围定在 1 到 10??, 那么计算结果不同的点的数量，就有 10?? – d 个。因而 x 偶然「撞到」这 d 个结果相同的点中任意一个的概率就等于（可以认为是几乎不可能）：d/10^77

/img/2022811172646/4.jpg" />

注意：为了简化起见，后面我们会用多项式的字母变量来代替计算结果值，例如：p = p(r)。

注解even@ 安比实验室：多项式可以被因式分解成它的根的因式的乘积。这个性质就意味着，如果一个多项式有某些解，那么它被因式分解后的式子中一定包含这些解的因式。

有了这个性质，我们就可以愉快地去做一些证明啦。

利用多项式一致性检查协议我们就可以比较多项式 p(x) 和 t(x) ? h(x)：verifier 挑选一个随机值 r, 计算 t = t(r) (即，求值)，然后将 r 发送给 prover。prover 计算 h(x) =p(x) / t(x)，并对 p(r) 和 h(r) 进行求值，将计算结果 p, h 提供给 verifier。verifier 验证 p= t?h，如果多项式相等，就意味着 t(x) 是 p(x) 的因式。

实践一下，用下面的例子来执行这个协议：verifier 选一个随机数 23，并计算 t = t(23) = (23 – 1)(23 – 2) = 462，然后将 23 发给 proverprover 计算 h(x) =p(x) / t(x) = x, 并对 p(r) 和 h(r) 进行求值，p= p(23) = 10626，h= h(23) = 23，将 p 和 h 提供给 verifierverifier 再验证 p= t?h：10626 = 462 ? 23 是正确的，这样陈述就被证明了。

相反，如果 prover 使用一个不同的 p′(x)，它并不包含必要的因式，例如 p′(x) = 2x3 – 3x2 + 2x, 那么：

/img/2022811172646/6.jpg" />现在我们看一下数字八应该在哪里。打个比方，我们可以把它看成一条长度为 8 的绳子。

如果我们将绳子固定在圆圈的开头

然后用绳子缠绕圆圈，我们在缠完一圈后还剩下一部分的绳子。然后我们继续缠绕，这根绳子将在刻度 2 的地方终止。

这就是模运算操作的结果。无论这根绳子多长，它最终都会在圆圈一个刻度处终止。因而模运算结果将保持在一定范围内（例子中是 0 到 5）。长度为 15 的绳子将会在刻度 3 的地方终止，即 6 + 6 + 3（缠 2 个完整的圈并剩下 3 个单位长的部分）。负数运算类似，唯一不同的地方就是它是沿相反方向缠绕的，如 -8 的取模结果是 4。

我们执行算术运算，结果都将落在这 n 的范围内。现在开始我们将用符号「mod n」来表示这个范围内的数。

3 × 5 = 3 mod 65 + 2 = 1 mod 6

另外，模运算最重要的性质就是运算顺序无所谓。例如，我们可以先做完所有的操作，然后再取模，或者每操作完一步都去取模。例如 (2 × 4 – 1) × 3 = 3 (mod 6) 就等于：

2 × 4 = 1 mod 62 - 1 = 1 mod 61 × 3 = 3 mod 6

那么模运算到底有什么用呢？就是如果我们使用模运算，从运算结果再回到原始值并不容易，因为很多不同的组合会产生一个同样的运算结果：

5 × 4 = 2 mod 64 × 2 = 2 mod 62 × 1 = 1 mod 6……

没有模运算的话，计算结果的大小会给找出原始值提供一些线索。除非这里既能把信息隐藏起来，又可以保留常见的算术属性。

强同态加密我们再回到同态加密上，使用模运算，例如取模 7，我们可以得到：51 = 5(mod 7)52 = 4(mod 7)53 = 6(mod 7)……不同指数下运算得到了同样的结果：55 = 3(mod 7)511 = 3(mod 7)517 = 3(mod 7)……这样就很难知道指数是多少了。事实上，如果模取得相当大，从运算结果倒推指数运算就不可行了；现代密码学很大程度上就是基于这个问题的「困难」。

方案中所有的同态性质都在模运算中保留了下来：

encryption: 53 = 6 (mod 7)multiplication: 62 = (53)2 = 56 = 1 (mod 7)addition: 53 · 52 = 55 = 3(mod 7)

注意：模相除有点难已经超出范围了。我们来明确地说明一下加密函数：E(v) = gv(mod n)这里 v 就是我们要加密的值。Remark 3.2 这个同态加密模式有一个限制，我们可以把一个加密的值和一个未加密的值相乘，但我们不能将两个加密的值相乘（或者相除），也就是说我们不能对加密值取幂。虽然这些性质第一感觉看起来很不友好，但是这却构成了 zk-SNARK 的基础。这个限制后面将在「加密值乘法」一节中讲到。

注解even@ 安比实验室：通过模运算形成的集合被称为「有限域」，而通过计算指数再进行模运算形成的集合构成「循环群」。常见的同态加密方式除了整数幂取模之外，还有椭圆曲线上的倍乘。加密多项式配合这些工具，我们现在就可以在加密的随机数 x 上做运算并相应地修改零知识 协议了。我们来看一下如何计算多项式 p(x) = x3 – 3x2 + 2x。我们前面明确了，知道一个多项式就是知道它的系数，也就是这个例子中知道：1，-3，2。因为同态加密并不允许再对加密值求幂，所以我们必须要给出 x 的 1 到 3 次幂取加密值：E(x)，E(x2)，E(x3)，那么我们要计算的加密多项式就是：E(x3)1 · E(x2)-3 · E(x)2 = (gx3)1 · (gx2)-3 ·(gx)2 = g1x3 · (g-3x2)·(gx)2 = g x3-3x2+2x所以通过这些运算，我们就获得了多项式在一些未知数 x 处的加密计算结果。这确实是一个很强大的机制，因为同态的性质，同一个多项式的加密运算在加密空间中始终是相同的。

我们现在就可以更新前面版本的协议了，比如对于阶数为 d 的多项式：

Verifier取一个随机数 s，也就是秘密值指数 i 取值为 0，1，…，d 时分别计算出 s 的 i 次幂的加密结果，即：代入 s 计算未加密的目标多项式：t(s)将对 s 的幂的加密值提供给 prover：E(s0)，E(s1)，，E(sd)

Prover计算多项式 h(x) = p(x)/t(x)使用加密值，，…，和系数，，…，计算 g^p(s)然后同样计算 E(h(s)) =gh(s)将结果 gp 和 gh 提供给 verifier

Verifier最后一步是 verifier 去校验 p = t(s) ·h: gp = (gh)t(s) => gp = gt(s)·h注意：因为证明者并不知道跟 s 相关的任何信息，这就使得他很难提出不合法但是能够匹配验证的计算结果。

尽管这个协议中 prover 的灵活性有限，他依然可以在实际不使用 verifier 所提供的加密值进行计算，而是通过其它的方式来伪造证明。例如，如果 prover 声称有一个满足条件的多项式它只使用了 2 个求幂值 s3 和 s1，这个在当前协议中是不能验证的。

注解even@ 安比实验室：利用强同态加密这个工具，构造了一个相对较强的零知识证明协议。但是如上文所述，这里还是存在一些问题——无法验证 prover 是否是真的使用了 verifier 提供的值来构造证明的。

大家可以思考一下，如何解决这个问题？以及这个协议还存在哪些缺陷呢？

在下一节中，我们将会继续展开讨论，并展示如何构造一个完备的多项式的零知识证明协议。

标签：VERPROROVERRIFPEPVERSProspectors GoldAdroverseWrapped Centrifuge

以太坊价格今日行情热门资讯