简介：本文翻译自zcash官方博客，讲解zcash中所使用的zk-SNARKs的原理第一部分，此处是原文链接。友情提示：本系列文章偏技术化，适合对技术和数学非常感兴趣的同学阅读。
zkSNARK是zero-knowledge succint non-interactive arguments of knowledge的简称，意思是：简洁的非交互式的零知识证明。
(本文授权BH好文好报群摘编、转载以及相关转授权推文行为)
正文
要理解zk-SNARKs，需要先理解其他的一些知识点，而要完全理解这些知识点，需要花点时间和耐心。
如果非要我选择一个最重要的知识点，那么我会选择同态隐藏[1]。在这个文章中我将会详细解释同态隐藏，并给出一个例子。
同态隐藏的定义：E(x)是x的函数，该函数满足：
- 通过
E(x)很难推算出x - 不同的
x会得到不同的E(x)值 - 如果知道
E(x)和E(y),那么就可以计算出E(x+y)。
为什么同态隐藏很有用呢？假设Alice想向Bob证明她知道x和y这两个数字，并且x+y=7，可以这么做：
- Alice把
E(x)和E(y)发送给Bob - Bob通过上面两个值，计算出
E(x+y)。(因为E是同态隐藏函数，并且Bob也知道这个函数，所以Bob可以从E(x)和E(y)计算出E(x+y)) - Bob也计算出
E(7),如果E(x+y) == E(7)，那么Bob就承认Alice知道x和y
因为不同的输入，会经由E函数产生不同的结果（由于这个结果相当于隐藏了原来的输入，后面我把这种结果叫做隐藏数），因此Bob仅仅在收到了Alice发送过来的x、y以及x+y的隐藏数之后，才能接受Alice提供的证据。也就是说，Bob不需要知道x,y，他只需要知道它们的隐藏数即可。
现在，我们看看这种隐藏数是如何得到的。常规的整数加法确实没办法，不过我们可以看下有限群。
设n是整数。当我们对整数 A 写下 A mod n 时，我们的意思是在 A 除以 n 后取余数。比如 9 mod 7 = 2，13 mod 12 = 1。我们可以用mod n在集合{0, ..., n-1}上定义一个加法：我们先做常规加法，然后拿结果mod n，那么这个结果也在集合{0, ..., n-1}当中。我们有时会把(mod n)写在右边，这样可以清楚的表示我们在做这种类型的加法。例如: 2+3=1(mod 4)。 我们把这个集合{0, ..., n-1}以及这种加法运算合在一起，称作 群\mathbb{Z}_n。
对于一个质数p，我们也可以使用mod p在{1, ..., p-1}上面定义一个乘法：我们拿常规乘法的结果，做mod p操作，那么他的结果也会在集合{1, ..., p-1}中[2]。例如， 2*4 = 1(mod 7)。
这个集合以及这种乘法运算在一起，被称作 群\mathbb{Z}^{*}_{p}。\mathbb{Z}^{*}_{p}具有如下特性：
- 它是一个循环群；也就是说，在\mathbb{Z}^{*}_{p}中有一些元素可以经过运算生成其他元素，这类元素被成为生成元，其他的元素都可以被写为{g}^{a}，a属于集合
{0, ..., p-2}，同时我们定义 g^0 = 1。 - 在\mathbb{Z}^{*}_{p}中，离散对数问题被认为是比较困难的问题，也就是说，当
p很大时，给定\mathbb{Z}^{*}_{p}中的一个元素h，我们很难找到这样一个a，使得a属于{0, ..., p-2}，并且 g^a = h(mod\ p)。 - 由于“同底的幂的乘积，相当于把幂指数相加”，所以当
a, b属于{0, ..., p-2}时，g^a*g^b=g^{a+b(mod\ p)}。
通过这些特性，我可以构造一个加法的同态隐藏——也就是说，我们可以通过E(x)和E(y)计算出E(x+y)。
我们可以假设x属于\mathbb{Z}^{*}_{p-1}，那么x属于{0, ..., p-2}。我们定义E(x)=g^x，那么E就是一个同态：
- 根据第一条特性，可以得出，在\mathbb{Z}^{*}_{p-1}中，不同的输入
x,得到的隐藏数g^x也是不同的。 - 根据第二条特性，当得到E(x)后，我们很难求出
x - 最后，根据第三条特性，给定
E(x)和E(y)，我们可以这样计算出E(x+y): E(x+y) = g^{(x+y) mod (p-1)} = g^x*g^y=E(x)*E(y)
译者补充：
根据数论知识，当p为质数时，\mathbb{Z}^{*}_p在mod p下的乘法是一个循环群。
早赞声明：为方便早赞、避免乱赞，“BH好文好报群”为点赞者、写作者牵线搭桥，实行“先审后赞、定时发表”的规则，也让作品脱颖而出、速登热门！加群微信：we01230123（天平）。
网友评论