{"content":{"title":"zk-SNARK  系列  - #1 SNARK介绍 & 证明媒介","body":">- 原文链接：https://medium.com/@imolfar/why-and-how-zk-snark-works-1-introduction-the-medium-of-a-proof-d946e931160\r\n>- 译者：[AI翻译官](https://learnblockchain.cn/people/19584)，校对：[翻译小组](https://learnblockchain.cn/people/412)\r\n>- 本文永久链接：[learnblockchain.cn/article…](https://learnblockchain.cn/article/8829)\r\n    \r\n# 为什么和如何 zk-SNARK 工作 1：介绍与证明的媒介\r\n\r\n> _本文是_ [_PDF 版本_](https://arxiv.org/abs/1906.07221)_的改编._\r\n\r\n尽管关于 _zk-SNARK_ 构造的资源很多，从原始论文 \\[[Bit+11](#d914); [Par+13](#4d29)\\] 到解释文章 \\[[Rei16](#eabb); [But16](#91fa); [But17](#3df0); [Gab17](#d309)\\]，由于涉及的部分众多，这个主题对许多人来说仍然是一个黑箱。虽然提供了一些拼图，但没有缺失的部分就无法看到完整的图景。\r\n\r\n作者第一次发现这些部分如何完美契合时，被数学的美丽所震撼，随着更多维度的揭示，这种惊奇感不断增强。因此，本工作的重点是通过基于示例的直接和清晰的方法来分享这一经验，并在此过程中回答许多为什么，以便更多的人能够欣赏这项尖端技术、其创新者以及最终的数学之美。\r\n\r\n本工作的贡献是以足够的复杂性进行简化的阐述，必要的复杂性足以理解 _zk-SNARK_，无需任何先决知识、密码学或高级数学。主要目标不仅是解释它如何工作，还要解释它为什么工作以及它是如何形成的。\r\n\r\n## 前言\r\n\r\n虽然最初计划简短，但现在工作已经扩展到几十页，然而它需要的先决知识非常少，可以自由跳过熟悉的部分。\r\n\r\n如果你不熟悉一些使用的数学符号，不必担心，这些符号很少，并且会逐步引入，一次一个。\r\n\r\n## 介绍\r\n\r\n_零知识_ _简洁非交互知识论证_ (_zk-SNARK_) 是一种真正巧妙的方法，可以在不透露任何其他信息的情况下证明某事是真实的，然而，为什么它首先有用呢？\r\n\r\n_零知识证明_ 在许多应用中具有优势，包括：\r\n\r\n1) 证明私人数据的声明：\r\n\r\n*   人 _A_ 的银行账户中有超过 _X_\r\n*   去年，某银行没有与实体 _Y_ 进行交易\r\n*   匹配 DNA 而不透露完整的 DNA\r\n*   某人的信用评分高于 _Z_\r\n\r\n2) 匿名授权：\r\n\r\n*   证明请求者 _R_ 有权访问网站的受限区域而不透露其身份（例如，登录名、密码）\r\n*   证明某人来自允许的国家/州列表而不透露具体来自哪个国家/州\r\n*   证明某人拥有地铁/地铁的月票而不透露卡的 ID\r\n\r\n3) 匿名支付：\r\n\r\n*   完全脱离任何身份的支付 \\[[Ben+14](#4c0c)\\]\r\n*   在不透露收入的情况下缴税\r\n\r\n4) 外包计算：\r\n\r\n*   外包昂贵的计算并验证结果是否正确而不重新执行；它开启了一个无信任计算的类别\r\n*   将区块链模型从每个人都计算相同的内容更改为一个人计算，所有人验证\r\n\r\n尽管表面上听起来很棒，但其底层方法是数学和密码学的“奇迹”，自 1985 年在主要工作“交互式证明系统的知识复杂性” \\[[GMR85](#41b6)\\] 中引入以来，已经研究了四个十年，随后引入了非交互式证明 \\[[BFM88](#1bde)\\]，这在区块链的背景下尤为重要。\r\n\r\n在任何 _零知识证明_ 系统中，有一个 _证明者_ 想要说服一个 _验证者_ 某个 _声明_ 是真实的而不透露任何其他信息，例如，_验证者_ 了解到 _证明者_ 的银行账户中有超过 _X_，但没有其他信息（即实际金额未披露）。协议应满足三个属性：\r\n\r\n*   完整性 — 如果 _声明_ 是真实的，那么 _证明者_ 可以说服 _验证者_\r\n*   可靠性 — 欺骗的 _证明者_ 不能说服 _验证者_ 一个虚假的 _声明_\r\n*   零知识 — 交互只揭示 _声明_ 是否真实，其他任何信息都不透露\r\n\r\n_zk-SNARK_ 术语本身在 \\[[Bit+11](#d914)\\] 中引入，基于 \\[[Gro10](#e2e7)\\]，随后是 Pinocchio 协议 \\[[Gen+12](#7f22); [Par+13](#4d29)\\]，使其适用于通用计算。\r\n\r\n## 证明的媒介\r\n\r\n让我们从简单的开始，尝试证明一些东西，而不考虑零知识、非交互性、其形式和适用性。\r\n\r\n假设我们有一个长度为 10 的位数组，我们想向验证者（例如程序）证明所有这些位都设置为 1。\r\n\r\n![](https://img.learnblockchain.cn/attachments/migrate/1721891547529)\r\n\r\n验证者只能一次检查（即读取）一个元素。为了验证声明，可以通过以某种任意顺序读取元素并检查它是否确实等于 1 来进行，如果是，则对该声明的信心在第一次检查后为 ⅒= 10%，或者如果该位等于 0，则声明完全无效。验证者必须继续下一轮，直到达到足够的信心。在某些情况下，可能信任证明者并只需要 50%的信心，这意味着必须执行 5 次检查，在其他需要 95%信心的情况下，必须检查所有单元。显然，这种证明协议的缺点是必须进行与元素数量成比例的检查次数，如果我们处理的是数百万个元素的数组，这是不切实际的。\r\n\r\n让我们考虑多项式，它可以在图表上可视化为曲线，由数学方程式形成：\r\n\r\n![](https://img.learnblockchain.cn/attachments/migrate/1721891547525)\r\n\r\n上述曲线对应于多项式：$ f(x) = x³ – 6x² + 11x – 6 $。多项式的次数由其最大的 _x_ 指数决定，在这种情况下是 3。\r\n\r\n多项式具有一个有利的属性，即如果**我们有两个不相等的次数最多为 _d_ 的多项式，它们最多只能在 _d_ 个点相交**。例如，让我们稍微修改原始多项式 $x³ – 6x² + 10x – 5$ 并用绿色可视化它：\r\n\r\n![](https://img.learnblockchain.cn/attachments/migrate/1721891547518)\r\n\r\n如此微小的变化会产生截然不同的结果。事实上，不可能找到两个不相等的多项式，它们共享一段连续的曲线（不包括单点段的情况）。\r\n\r\n这种属性源于寻找共享点的方法。如果我们想找到两个多项式的交点，我们需要将它们等同。例如，要找到多项式穿过  _x_ 轴的点（即，f(x) = 0），我们将 $x³ – 6x² + 11x – 6 = 0$，并且这种方程的解将是那些共享点：x= 1, x = 2 和 x = 3，你也可以清楚地看到这在前面的图表中是正确的，蓝色曲线穿过 x-轴线。\r\n\r\n同样，我们可以将原始和修改版本的多项式等同以找到它们的交点。\r\n\r\n![](https://img.learnblockchain.cn/attachments/migrate/1721891547599)\r\n\r\n结果多项式的次数为 1，显然的，解是 _x_ \\= 1。因此只有一个交点：\r\n\r\n![](https://img.learnblockchain.cn/attachments/migrate/1721891547615)\r\n\r\n任意次数 _d_ 多项式的这种**方程**的结果总是另一个次数最多为 _d_ 的**多项式**，因为没有乘法产生更高的次数。例如：$5x³ + 7x² – x+ 2 = 3x³ – x² + 2x – 5$，简化为 $2x³ + 8x² – 3x + 7 = 0$。代数学基本定理告诉我们，次数为 _d_ 的多项式最多可以有 _d_ 个解（在后续部分中会详细介绍），因此最多有 _d_ 个共享点。因此，我们可以得出结论，在任意点对多项式进行求值（更多关于多项式求值的信息：\\[[Pik13](#489a)\\]）类似于其唯一身份的表示。让我们在 _x_ \\= 10 处对我们的示例多项式进行求值。\r\n\r\n![](https://img.learnblockchain.cn/attachments/migrate/1721891548455)\r\n\r\n实际上，在所有选择的 _x_ 中，只有最多 3 个选择在这些多项式中的求值是相等的，其他所有选择都会有所不同。\r\n\r\n这就是为什么如果证明者声称知道某个多项式（无论其次数多大），而验证者也知道，他们可以遵循一个简单的协议：\r\n\r\n* 验证者选择一个随机值 _x_ 并在本地对多项式进行求值\r\n* 验证者将 _x_ 给证明者并要求对该多项式进行求值\r\n* 证明者在 _x_ 处对他的多项式进行求值并将结果给验证者\r\n* 验证者检查本地结果是否等于证明者的结果，如果是，则该声明以高置信度被证明\r\n\r\n例如，如果我们考虑 _x_ 从 1 到 10⁷⁷ 的整数范围，不同求值的点数是 10⁷⁷ – _d_。因此，_x_ 意外“击中”任何 _d_ 个共享点的概率等于（被认为是可以忽略的）：\r\n\r\n![](https://img.learnblockchain.cn/attachments/migrate/1721891548464)\r\n\r\n> 注意：新协议只需要一轮，并且在声明中的置信度极高（假设 d  远小于范围的上限）相比低效的位检查协议。\r\n\r\n这就是为什么多项式是 _zk-SNARK_ 的核心，尽管可能还存在其他证明媒介。\r\n\r\n[继续阅读第二部分](https://medium.com/@imolfar/why-and-how-zk-snark-works-2-proving-knowledge-of-a-polynomial-f817760e2805)…\r\n\r\n## 参考文献\r\n\r\n\\[Bit+11\\] — Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. _From Extractable_ _Collision Resistance to Succinct Non-Interactive Arguments of_ _Knowledge, and Back Again_. Cryptology ePrint Archive, Report 2011/443. [https://eprint.iacr.org/2011/443](https://eprint.iacr.org/2011/443). 2011\r\n\r\n\\[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](https://eprint.iacr.org/2013/279). 2013\r\n\r\n\\[Rei16\\] — Christian Reitwiessner. _zkSNARKs in a Nutshell_. 2016. url: [https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/](https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/) (visited on 2018–05–01)\r\n\r\n\\[But16\\] — Vitalik Buterin. _Quadratic Arithmetic Programs: from Zero to_ _Hero_. 2016. url: [https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649](/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649) (visited on 2018–05–01)\r\n\r\n\\[But17\\] — Vitalik Buterin. _zk-SNARKs: Under the Hood_. 2017. url: [https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6](/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6) (visited on 2018–05–01)\r\n\r\n\\[Gab17\\] — Ariel Gabizon. _Explaining SNARKs_. 2017. url: [https://z.cash/blog/snark-explain/](https://z.cash/blog/snark-explain/) (visited on 2018–05–01)\r\n\r\n\\[Ben+14\\] — Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. _Zerocash: Decentralized_ _Anonymous Payments from Bitcoin_. Cryptology ePrint Archive, Report 2014/349. [https://eprint.iacr.org/2014/349](https://eprint.iacr.org/2014/349). 2014\r\n\r\n\\[GMR85\\] — S Goldwasser, S Micali, and C Rackoff. “The Knowledge Complexity of Interactive Proof-systems”. In: _Proceedings of the Seventeenth Annual ACM_ _Symposium on Theory of Computing_. STOC ’85. Providence, Rhode Island, USA: ACM, 1985, pp. 291–304. isbn: 0–89791–151–2. doi: [10.1145/22145.22178](https://doi.org/10.1145/22145.22178). url: [http://doi.acm.org/10.1145/22145.22178](http://doi.acm.org/10.1145/22145.22178)\r\n\r\n\\[BFM88\\] — Manuel Blum, Paul Feldman, and Silvio Micali. “Non-interactive Zero-knowledge and Its Applications”. In: _Proceedings of the Twentieth Annual ACM_ _Symposium on Theory of Computing_. STOC ’88. Chicago, Illinois, USA: ACM, 1988, pp. 103–112. isbn: 0–89791–264–0. doi: [10.1145/62212.62222](https://doi.org/10.1145/62212.62222). url: [http://doi.acm.org/10.1145/62212.62222](http://doi.acm.org/10.1145/62212.62222)\r\n\r\n\\[Gro10\\] — Jens Groth. “Short pairing-based non-interactive zero-knowledge arguments”. In: _International Conference on the Theory and Application of Cryptology and_ _Information Security_. Springer. 2010, pp. 321–340\r\n\r\n\\[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](https://eprint.iacr.org/2012/215). 2012\r\n\r\n\\[Pik13\\] — Scott Pike. _Evaluating Polynomial Functions_. 2013. url: [http://www.mesacc.edu/~scotz47781/mat120/notes/polynomials/evaluating/evaluating.html](http://www.mesacc.edu/~scotz47781/mat120/notes/polynomials/evaluating/evaluating.html) (visited on 2018–05–01)\r\n\r\n> 我是 [AI 翻译官](https://learnblockchain.cn/people/19584)，为大家转译优秀英文文章，如有翻译不通的地方，在[这里](https://github.com/lbc-team/Pioneer/blob/main/translations/8829.md)修改，还请包涵～"},"author":{"user":"https://learnblockchain.cn/people/21874","address":null},"history":"bafkreihbyyqwg26d6zld63d5o3m22l2z62jdyg4b6hufc7rxbtwdchmfqu","timestamp":1723014491,"version":1}