24期：零知识证明详解四：可验证的多项式盲式计算

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

这一章建立在第二章和第三章基础之上，我们将研究出一套可验证的多项式盲式计算协议。第五章，我们将看到这套协议在构造SNARKs中的作用，所以大家先忍忍，很快就到SNARKs了。

和第二章一样，我们假设，Alice有一个d次多项式P，Bob选择了一个随机的s \in \mathbb{F}_p。我们想构造这样一个协议，它允许Bob知道E(P(s))，并具有如下特点：

1. 双盲：Alice不能知道s，同时Bob不能知道 P
2. 可验证性：Alice在不知道P的情况下蒙对E(P(s))的概率，必须很小，小到可以忽略

这就是所谓的可验证的多项式盲式计算。在第二章的协议中，我们实现了第一个特性，但没有实现第二个。为了实现可验证性，我们需要一个KCA的扩展版本。关于KCA，第三章有讲解。

可验证性和双盲特性是非常有用的，因为这两个特性，Alice可以决定在不知道s的情况下使用哪个多项式P。同时，可以保证，让Alice在不知道s的情况，会给出一个正确的多项式。这个初心在后面的章节会越发清晰。

一个扩展的KCA

我们在第三章讲的KCA主要是说：如果Bob给了Alice一个\alpha二元组(a, b = \alpha * a)，那么Alice可以生成一个新的\alpha二元组(a', b')，因此她就能知道一个c，使得a' = c * a。换句话说，Alice知道a'和a之间的关系。

现在，假设Bob不是发送了一个二元组，而是发送了多个\alpha二元组(a_1, b_1, ..., (a_d, b_d))(都是同样的\alpha)，那么，在Alice收到这些二元组之后，Alice需要生成另外的二元组(a', b')来完成这个挑战。请记住，Alice必须要能在不知道\alpha的情况下完成这个挑战。

就像我们在第三章看到的一样，很自然地，Alice可以从这多个二元组中选择一个(a_i, b_i)出来，然后乘以某个c， c \in \mathbb{F}_p^*; 如果(a_i, b_i)是\alpha二元组，那么(c* a_i, c*b_i)也一定是一个二元组。不过，Alice有没有别的方法生成\alpha二元组呢？是否可以同时利用几个收到的二元组生成一个新的？

答案是肯定的。例如，Alice可以选择两个值c_1, c_2 \in \mathbb{F}_p，然后计算出一个二元组(a', b') = (c_1*a_1 + c_2*a_2, c_1*b_1 + c_2*b_2)。这个可以进行简单的证明，只要a'不是0，那么这个二元组就是\alpha二元组：

b' = c_1*b_1+c_2 * b_2 = c_1\alpha*a_1 + c_2\alpha*a_2 = \alpha * (c_1*a_1+c_2*a_2) = \alpha * a'

更一般地，Alice可以使用给定的d个二元组的任意线性组合，也就是：对于任意的c_1, ..., c_d \in \mathbb{F}_p，可以定义：
(a', b') = (\sum_{i=1}^d c_ia_i, \sum_{i=1}^dc_ib_i)。

注意，如果Alice用这个方法生成了她的\alpha二元组，她就会知道a'和a_1, ..., a_d之间的线性关系。也就是说，她知道c_1, ..., c_d使得a'=\sum_{i=1}^d c_i*a_i

这个扩展的KCA是指，Alice用这种方法生成二元组时，只要她成功了，她就知道a'和a_1, ..., a_d之间的线性关系。

更正式的表达是，假设G是一个大小为p的循环群，并且它的生成元是g，那么G的d次系数知识假设(d-KCA)可以表述为：

d-KCA： 设Bob随机选择\alpha \in \mathbb{F}_p^*和s \in \mathbb{F}_{p'}，并把如下的\alpha二元组发送给Alice(g, \alpha*g), (s*g, \alpha s*g), ..., (s^d*g, \alpha s^d*g).如果Alice输出了另一组\alpha二元组(a', b')，那么Alice就会得知c_0, ..., c_d \in \mathbb{F}_p使得\sum_{i=0}^d c_is^i*g = a'。

请注意，在d-KCA中，Bob并没有发送任意的\alpha二元组，而是发送了有特定“多项式结构” 的多项式，这对于下面内容有用。

可验证的盲式计算协议

假设我们的HH(同态隐藏函数)是：E(x) = x * g，g是上面循环群G的生成元。

由此，我们拿出我们的协议如下：

1. Bob选择了一个随机的\alpha \in \mathbb{F}_{p'}^*，并把(1, s, ..., s^d)的隐藏数(g, s*g, ..., s^d*g)，以及(\alpha, \alpha s, ..., \alpha s^d)的隐藏数(\alpha*g, \alpha s*g, ..., \alpha s^d *g)发送给Alice
2. Alice通过接收到的元素计算出a = P(s)*g以及b = \alpha P(s)*g，然后把结果发给Bob
3. Bob验证一下b = \alpha * a，如果满足这个等式，则接受Alice

首先，提醒一下，在给定了P的系数之后，P(s)*g是g, s*g, ..., s^d*g的线性组合，\alpha P(s)*g是\alpha * g, \alpha s*g, ..., \alpha s^d *g的线性组合，那么，根据第二章的内容，Alice的确是可以从Bob发送的信息中计算出这些值的。

其次，通过d-KCA我们知道，在这整个过程中，Alice知道c_0, ..., c_d \in \mathbb{F}_p,使得a=\sum_{i=0}^d c_i s^i *g，因为a = P(s) *g，所以Alice知道这么一个多项式P(X) = \sum_{i=0}^d c_i*X^i。也就是说，假如Alice不知道这么个多项式，她瞎蒙一个结果能通过Bob的验证的可能性极小。

总结一下，我们通过d-KCA得了一个可验证的多项式盲式计算协议，后面的章节中，我们将看看如何使用这些知识点构建SNARK。

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