我们来看一下如何计较多项式 p(x) = x³ – 3x² + 2x。我们前面明晰了，知道一个多项式就是知道它的系数，也就是这个例子中知道：1，-3，2。因为同态加密并不答允再对加密值求幂，所以我们必需要给出 x 的 1 到 3 次幂取加密值：E(x)，E(x²)，E(x³)，那么我们要计较的加密多项式就是：
任意一个由阶数为 d 的多项式构成的等式，最后城市被化简为别的一个阶数至多为 d 的多项式，这是因为等式中没有可以或许用来结构更高阶数的乘法。譬喻：5x³ + 7x² – x + 2 = 3x³ – x² + 2x– 5，简化为 2x³ + 8x² – 3x + 7 = 0。别的代数的根基道理也汇报我们，对付一个阶数为 d 的多项式至多有 d 个解（以下部门将对此举办具体先容），因而也就至多有d 个配合点。
多项式有一个很是好的特性，就是假如我们有两个阶为 d 的不相等多项式，他们相交的点数不会高出 d。譬喻，稍微修改一下本来的多项式为 x³ – 6x² + 10x– 5 （注：请留意这里只修改了多项式的最后一个系数，6改成了5）并在图上用绿色标出：
53 = 6(mod 7)
cnxn + …… + c1x1 + c0x0
这一点微小的修改就发生了变革很大的曲线。事实上，我们不行能找到两条差异的曲线，他们会在某段区域内重合（他们只会相交于一些点）。
3）匿名付出：
换句话说，存在一些多项式 h(x) 可以或许使得 t(x) 与之相乘后便是 p(x)，由此得出， p(x) 中包括 t(x)，所以 p(x) 的根中也包括 t(x) 的所有根，这也就是我们要证明的对象。
这就是为什么接下来我们要先容可以或许使余数不被整除的暗码学道理的原因，尽量这个原始值是有大概被整除的。
我们算出功效2x + 3 和余数7x – 6，即：p(x) = t(x) × (2x+ 3) + 7x – 6。这就意味着 verifier 为了计较出功效他不得不消 余数除以t(x)，
51 = 5(mod 7)
也就是说假如任意一个因式为 0，那么整个等式都为 0，也就是说式子中所有的 as 就是多项式的所有解。
我们再回到同态加密上，利用模运算，譬喻取模 7，我们可以获得：
· verifier 将 x 值给到 prover，并让他计较相关的多项式功效
· verifier 挑选一个随机值 r, 计较 t = t(r) (即，求值) ，然后将 r 发送给 prover。
想象一下我们有一个长度为10 的位数组，此刻要向 verifier（譬喻，措施）证明这样一个告诉：所有的位都被配置成了 1。
2 × 4 = 1 mod 6假设证明者声称他知道一个包括 x=1 和 x=2 两个解的三阶多项式。满意此条件的一个有效的多项式就是 x3 – 3×2+ 2x= 0。因为x= 1: 1 – 3 + 2 = 0，x= 2: 8 – 12 + 4 = 0。
这篇文章的主要孝敬是较量简捷明白的表明白个中相当巨大的技能，这些简朴的表明对付在不具备任何与之相关的先决常识，好比暗码学和高档数学，的前提下领略 zk-SNARK 是很有须要的。文章中并不只仅只表明 zk-SNARK 是如何事情的，还表明白为什么这样就可以事情，以及它是怎么来的。
这是从找多项式配合点要领中得出的性质。假如要查找两个多项式的交点，就要先令它们相等。譬喻，要找到多项式与 x 轴的交点（即 f(x) = 0），我们就要令 x³ – 6x² + 11x – 6 = 0，等式的解就是配合点：x= 1 ，x= 2 和 x= 3。在上面图中也可以很清晰得看出这些解，也就是图上蓝色曲线和 x 轴相交的处所。
(x-a0)(x-a1)…(x-an) = 0
· 证明一小我私家持有地铁月票，而不透露卡号
[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
譬喻，我们把 x 的取值范畴定在 1 到 10⁷⁷, 那么计较功效差异的点的数量，就有 10⁷⁷ – d 个。因而 x 偶尔“撞到”这 d 个功效沟通的点中任意一个的概率就便是（可以认为是险些不行能）：d/10^77
[But17] — Vitalik Buterin. zk-SNARKs: Under the Hood. 2017. url: https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
2）匿名认证：
可是到今朝为止，我们的协议还只是一个很弱的证明，因为协议中并没有采纳任何法子去担保参加方必需凭据协议的法则生成证明，所以参加方只能相互信任。譬喻，prover 并不需要知道多项式，也大概通过其它方法获得正确的谜底。并且，假如 verifier 要验证的多项式的解的取值范畴不足大，好比我们前文说的 10，谁人就可以去猜一个数字，猜对谜底的概率是不行忽略不计的。因而我们必需要办理协议中的这个缺陷，在办理问题之前首先来想一下，知道多项式意味着什么呢？
2 × 1 = 1 mod 6
· prover 代入 x 到多项式计较并将功效给到 verifier
同样，我们也可以令上文华夏始的多项式和修改后的多项式相等，找到它们的交点。
注解
addition: 53 · 52 = 55 = 3(mod 7)
17 年最早打仗 zk-SNARK 开始，就断断续续得进修了一些 zk-SNARK 的常识，但对其道理始终存在诸多狐疑，没有形成一个完整的认识。偶尔一次时机，看到了 Maksym Petkus 的这篇文章。文章从最根基的多项式性质讲起，从一个简朴易懂的证明协议开始，然后像会萃木一样在发明问题，修改问题中慢慢去完善协议，直到最终结构出完整的 zk-SNARK 协议。别的作者这种从问题出发的讲授方法，让读者知其然，也知其所以然 。作为一枚结业多年早把数学常识还给老师的措施媛，读到这篇文章如获至宝，这篇文章读下来的感觉像找到了一个脚手架，将脑海里碎片化的常识逐渐拼凑完整。于是想把它翻译出来（已得到作者授权），一方面加深本身的进修，另一方面也将这份宝藏分享给小同伴们。 上面的曲线对应多项式: f(x) = x³ – 6x² +11x– 6。多项式的阶数取决于 x 的最大指数，当前多项式的阶数是 3。 郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
……
……
55 = 3(mod 7)
· verifier 查抄当地的计较功效和 prover 的计较功效是否相等，假如相等那就说明 prover 的告诉具有较高的可信度
4 × 2 = 2 mod 6
Remark 3.2 这个同态加密模式有一个限制，我们可以把一个加密的值和一个未加密的值相乘，但我们不能将两个加密的值相乘（可能相除），也就是说我们不能对加密值取幂。固然这些性质第一感受看起来很不友好，可是这却组成了 zk-SNARK 的基本。这个限制后头将在“加密值乘法”一节中讲到。
所以通过这些运算，我们就得到了多项式在一些未知数 x 处的加密计较功效。这确实是一个很强大的机制，因为同态的性质，同一个多项式的加密运算在加密空间中始终是沟通的。
注解
参考文献
E(x3)1 · E(x2)-3 · E(x)2 = (gx³)1 · (gx²)-3 ·(gx)2 = g1x³ · (g-3x²)·(gx)2 = g x³-3x²+2x
1 × 3 = 3 mod 6
[email protected]安比尝试室：多项式可以被因式解析成它的根的因式的乘积。这本性质就意味着，假如一个多项式有某些解，那么它被因式解析后的式子中必然包括这些解的因式。
[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
协议并没有对 prover 的多项式阶数举办约束
1）证明关于隐私数据的声明：
[email protected]安比尝试室：操作强同态加密这个东西，结构了一个相对较强的零常识证明协议。可是如上文所述，这里照旧存在一些问题—— 无法验证 prover 是否是真的利用了 verifier 提供的值来结构证明的。
在下一节中，我们将会继承展开接头，并展示如何结构一个完备的多项式的零常识证明协议。
