导读
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）外包计算将昂贵的计算外包，并在不重新执行的情况下验证结果是否正确；它打开了一种零信任计算的类别
改进区块链模型，从所有节点做同样的计算，到只需一方计算然后其它节点进行验证
以太坊基金会、AMD、Polkadot 发起 700 万美元竞赛以促进零知识扩展:金色财经报道，ZPrize于4月19日宣布，多个加密货币项目联合起来，为使用零知识（ZK）证明的创新团队提供700万美元的奖金。该竞赛由21个Web3组织支持，包括Polygon、Polkadot、Mina和Ethereum基金会。AMD-Xilinx还将为参赛团队提供高功率的计算设备。ZPrize在一份声明中说，参赛团队将尝试设计 \"新的算法和技术，以实现最好的零知识系统无法比拟的性能指标。\"获奖者必须将其提交的材料开源，以便其他开发者能够将任何突破性的东西整合到他们的工作中。[2022/4/20 14:34:54]
和「零知识证明」这个伟大的名词一样，其背后的方法可以说是数学和密码学的奇迹。自 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。
现在我们来看一下由数学方程式表示的多项式，它可以被画成坐标系上的一条曲线：
Polygon 推出基于STARK零知识证明的扩容方案 Miden，采用Facebook开源技术且兼容EVM:11月16日消息，Polygon宣布推出基于零知识的、与 EVM 兼容的扩容解决方案Miden，同时也将开源其核心组件的早期原型版本Polygon Miden 虚拟机 (VM) 。Polygon Miden 是一个基于 STARK 的 ZK Rollup，Polygon Miden VM 是完全开源的基于 STARK 的虚拟机，它的作用是验证程序执行并为DApp 部署提供增强的尽职调查。Miden VM 通过利用Facebook的Novi开发的STARK证明器/验证器Winterfell 对基于Rust语言编写的零知识虚拟机 Distaff VM进行了扩展。Distaff VM和Winterfell的核心开发人员Bobbin Threadbare将加入 Polygon 作为 Miden Lead，致力于重新整合 Distaff，将 Distaff 和 Winterfell 结合起来，并继续开发 Miden VM 及其周围的生态系统。
除Polygon Miden外，Polygon价值10亿美元的ZK策略资金还孵化Polygon Hermez和Polygon Nightfall。Polygon Hermez是此前收购的Hermez Network，Polygon Nightfall是与安永共同开发构建的以隐私为重点保护的Rollup。[2021/11/17 21:56:06]
多项式有一个非常好的特性，就是如果我们有两个阶为 d 的不相等多项式，他们相交的点数不会超过 d。例如，稍微修改一下原来的多项式为 x3 – 6x2 + 10x– 5（注：请注意这里只修改了多项式的最后一个系数，6 改成了 5）并在图上用绿色标出：
这是从找多项式共同点方法中得出的性质。如果要查找两个多项式的交点，就要先令它们相等。例如，要找到多项式与 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。因而这两个多项式有一个交点。
以太坊ZK Rollup扩容方案Hermez Network正在开源零知识证明模块:据官方消息，以太坊ZK Rollup扩容方案 Hermez Network表示，正在开发一个名为Rapidsnark新的zk-SNARKs零知识证明模块，目前已经发布并开放了源代码。[2021/2/2 18:43:40]
所以我们可以得出结论，任何多项式在任意点的计算结果（更多关于多项式求值参考：[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 的陈述具有较高的可信度
例如，我们把 x 的取值范围定在 1 到 10??, 那么计算结果不同的点的数量，就有 10?? – d 个。因而 x 偶然「撞到」这 d 个结果相同的点中任意一个的概率就等于（可以认为是几乎不可能）：d/10^77
/img/2022811172646/4.jpg">
注意：为了简化起见，后面我们会用多项式的字母变量来代替计算结果值，例如：p = p(r)。
注解even@ 安比实验室：多项式可以被因式分解成它的根的因式的乘积。这个性质就意味着，如果一个多项式有某些解，那么它被因式分解后的式子中一定包含这些解的因式。
有了这个性质，我们就可以愉快地去做一些证明啦。
金色沙龙 | 燕丽：零知识证明对于协调区块链底层扩容也有很大帮助:在今日举行的《隐私计算——区块链信息安全守护者》为主题的金色沙龙中，算力智库创始人燕丽表示，2020年1月1日，中国首部《中华人民共和国密码法》将正式开始实施，而在这之前一直只有一部 2007年4月23日公布的《商用密码产品使用管理规定》和《境外组织和个人在华使用密码产品管理办法》。很多人把这次《密码法》和2019年“1024”中央把区块链技术作为国家战略联系在一起。区块链技术是完全基于密码学技术，所以按照这个逻辑，如果政府要完全掌控未来区块链技术的发展，首先就要完全掌控密码学技术，而这个其中的核心是国家主权范围之间在所有的通信安全和商业行为之间军备竞赛的升级。区块链有大量扩容压力，而为了达到这个操作，必然要牺牲系统处理效能和部分隐私。但矛盾的是，区块链前期的应用场景如虚拟货币，数字金融等，都需要有更好的隐私保护和不容易被恶意攻击的防护。所以若想让区块链技术落地生根，那么提高区块链底层技术来满足对于高安全性(含高完整性和高保密性)、高性能、高广义效率的要求，也许是个稳妥做法。所以隐私计算中的零知识证明等对于协调区块链底层扩容也有很大帮助。[2020/4/15]
利用多项式一致性检查协议我们就可以比较多项式 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, 那么：
我们执行算术运算，结果都将落在这 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 提供的值来构造证明的。
大家可以思考一下，如何解决这个问题？以及这个协议还存在哪些缺陷呢？
在下一节中，我们将会继续展开讨论，并展示如何构造一个完备的多项式的零知识证明协议。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。