导读
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）外包计算将昂贵的计算外包，并在不重新执行的情况下验证结果是否正确；它打开了一种零信任计算的类别
改进区块链模型，从所有节点做同样的计算，到只需一方计算然后其它节点进行验证
MetisDAO：正结合Optimistic Rollup和零知识证明构建首个混合Rollup:金色财经报道，以太坊扩容解决方案MetisDAO官方宣布，正在通过将Optimistic Rollup架构与零知识证明相结合来构建首个混合Rollup，为以太坊开发人员提供安全、对开发人员友好的第2层，以部署所有类型的去中心化应用程序。[2023/3/3 12:40:27]
和「零知识证明」这个伟大的名词一样，其背后的方法可以说是数学和密码学的奇迹。自 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。
现在我们来看一下由数学方程式表示的多项式，它可以被画成坐标系上的一条曲线：
多项式有一个非常好的特性，就是如果我们有两个阶为 d 的不相等多项式，他们相交的点数不会超过 d。例如，稍微修改一下原来的多项式为 x3 – 6x2 + 10x– 5（注：请注意这里只修改了多项式的最后一个系数，6 改成了 5）并在图上用绿色标出：
DeGate 发布发展蓝图，将优先实现基于零知识证明技术的以太坊二层订单薄交易协议:据官方消息，以太坊二层交易协议 DeGate 发布最新发展蓝图，对原有的发展路线进行了调整，将优先上线订单薄交易，并最终形成订单薄交易、AMM 交易、保证金交易三者并存的产品架构。
DeGate 表示，随着 Layer2、以太坊 2.0 等技术的落地，区块链使用成本将大幅降低，因此更能满足交易者需求、资金利用率更高的订单薄交易有可能产生更大的市场需求。DeGate 的订单簿交易系统将拥有即时挂单撤单、挂单撤单免手续费、maker 交易免手续费、taker 直接交易等功能或优势。[2021/5/26 22:46:41]
这是从找多项式共同点方法中得出的性质。如果要查找两个多项式的交点，就要先令它们相等。例如，要找到多项式与 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。因而这两个多项式有一个交点。
所以我们可以得出结论，任何多项式在任意点的计算结果（更多关于多项式求值参考：[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 的陈述具有较高的可信度
动态 | 三星SDS采用零知识证明增强其企业区块链隐私性:据coindesk消息，三星企业技术部门SDS (Samsung SDS)正在使用零知识证明(zero-knowledge proof, ZKPs)来增强其Nexledger区块链的隐私保护。该公司周四表示，它已与总部位于以色列的QEDIT建立了合作关系，在不披露保密信息的情况下，在一个共享的账簿上记录和验证资产转移。此举突显出采用分布式账本技术的公司面临的挑战之一，向网络广播交易，可能会暴露敏感的客户数据，并向竞争对手泄露信息。[2019/11/14]
例如，我们把 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, 那么：
我们执行算术运算，结果都将落在这 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 提供的值来构造证明的。
大家可以思考一下，如何解决这个问题？以及这个协议还存在哪些缺陷呢？
在下一节中，我们将会继续展开讨论，并展示如何构造一个完备的多项式的零知识证明协议。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。