22期：零知识证明详解二：多项式的盲式计算

简介：本文翻译自zcash官方博客，讲解zcash中所使用的zk-SNARKs的原理第二部分，此处是原文链接。友情提示：本文偏技术化，适合对技术和数学非常感兴趣的同学阅读。
zkSNARK是zero-knowledge succint non-interactive arguments of knowledge的简称，意思是：简洁的非交互的零知识证明
(本文授权BH好文好报群摘编、转载以及相关转授权推文行为)

正文

在本章中，我们将回忆一下中学课文中学到的多项式，并解释一下“盲式计算”，以及如何用同态隐藏函数(之后将简写为HH)来实现它。在之后的章节中，我们将会发现盲式计算是构造SNARK的核心工具。

我们用\mathbb{F}_p来表示大小为p的域，它代表，\mathbb{F}_p中的元素是{0, ..., p-1}，其元素的加法和乘法都会执行 mod p，这在第一章有讲过。

多项式和线性组合

定义一个d次多项式P：
P(X) = a_0 + a_1*X + a_2 * X^2 + ... + a_d * X^d, a_0, ..., a_d \in \mathbb{F}_p

我们可以这样在 s \in \mathbb{F}_p 点上计算 P，让 s 代替 X，并计算总和:

P(s) = a_0 + a_1*s + a_2 * s^2 + ... + a_d * s^d。
由上面的式子可以看出，P(s) 实际上也是1, s, ..., s^d这些值的线性组合，或者说成是加权和，他们的权重依次是a_0, ..., a_d。

在前一章中，我们看到HH E是这么来定义的： E(x) = g^x，g是一个具有难离散对数问题的生成元。另外，这个HH还支持加法，也就是说，我们可以通过E(x)和E(y)计算出E(x+y)。我们需要注意的是，它其实也支持线性组合，也就是说，给定a, b, E(x), E(y)，我们可以计算出E(ax+by)。这是因为：
E(ax+by) = g^{ax+by} = g^{ax} * g^{by} = (g^x)^a * (g^y)^b = E(x)^a * E(y)^b

多项式的盲式计算

假设Alice有一个d次多项式P，Bob有一个随机的点s, s \in \mathbb{F}_p。如果Bob想要得出E(P(s))，那么他可以采用如下两种办法：

1. Alice把P发送给Bob，然后由Bob自己计算出E(P(s))
2. Bob发送s给Alice，她在计算出E(P(s))之后把结果发给Bob

然后，在盲式计算中，我们想让Bob在无法得知P的情况下得知到E(P(s)) —— 这就否定了第一种办法；但同时，更重要地，我们也不想让Alice得知s，这样也否定了第二种办法^[1]。

不过，我们可以用HH进行盲式计算，具体可以这样做：

1. Bob把隐藏数E(1),E(s),...,E(S^d)发送给Alice
2. Alice通过上面的隐藏数计算出E(P(s))，然后把结果发送给Bob(Alice之所以可以这么做，是因为E支持线性组合，而P(s)就是1, s, ..., s^d的线性组合)

你看，我们只发送隐藏数就可以了，Alice不需要得知s^[2]，Bob也不需要得知P。

为什么这很有用？

后面的文章，我们会深入到盲式计算中，看它在SNARKs中是怎么运用的。这个简单的出发点是，验证者Bob在不知道那个多项式的情况下，如何去检验另外一个人Alice是否知道它。我们通过Alice在一些随机的点上进行盲式计算，如果她不知道那个隐藏多项式，那么她很可能会给出错误的结果。这，反过来，也依赖于Schwartz-Zippel定理：不同的多项式在大多数点上的值都是不同的。

早赞声明：为方便早赞、避免乱赞，“BH好文好报群”为点赞者、写作者牵线搭桥，实行“先审后赞、定时发表”的规则，也让作品脱颖而出、速登热门！加群微信：we01230123（天平）。

---

1. 我们不发送P给Bob的一个主要原因是，它太大了——有(d+1)个元素，例如，当前Zchash协议中使用的是d~2000000。 ↩

2. 实际上，这个隐藏特性智能保证E(s)可以隐藏s，但是，对于E(s), ..., E(s^d)就可能不一样了，后者关于s包含了更多信息。这就涉及到d次Diffe-Hellman假设了，在SNARKs的安全证明中会用到。 ↩