本文翻译自zcash官方博客,讲解zcash中所使用的zk-SNARKs的原理第三部分,此处是原文链接。友情提示:本文偏技术化,适合对技术和数学非常感兴趣的同学阅读。
zkSNARK是zero-knowledge succint non-interactive arguments of knowledge的简称,意思是:简洁的非交互的零知识证
(本文授权BH好文好报群摘编、转载以及相关转授权推文行为)
在第二部分,我们看到了Alice是如何通过自己的d次多项式P
,在属于Bob的s
点上盲式计算出E(P(s))
的。我们之所以称之为盲式计算,是因为Alice在整个过程中都无需知道s
。
然而,在那个协议中,我们忽略了一件事:Alice能计算出E(P(x))
并不代表它会发送正确的E(P(x))
给Bob,她可能会发送一些完全无关的数值。
因此,我们需要一种 “强制” Alice 正确地遵从协议的方式。我们将会在第四部分中解释我们如何做到这一点。在本章中,我们先解释一个实现这一功能需要用到的基础工具——我们称之为系数知识测试(KC)。
如同往常一样,我们把通过生成元g
生产的群记作G
,它的阶|G| = p
,群G
是一个具有“离散对数难解问题”的群。为了方便,我们用 a \in \mathbb{F}_p, a*g 表示 a
个g
之和。
系数知识测试
对于\alpha \in \mathbb{F}^*_p [1], 我们定义一个二元组:(a, b), a \in G, b \in G。如果a, b \neq 0且b = \alpha*a,那么我就称这个二元组为 \alpha二元组。
这个KC测试的过程是这样的:
- Bob随机选择\alpha \in \mathbb{F}^*_p和a \in G。然后计算出b = \alpha*a
- 他把这个二元组(a, b)发给Alice,向Alice发起挑战。注意,(a, b)是一个\alpha二元组
- Alice必须回应一个不同的\alpha二元组(a', b')
- 只有当(a', b')确实是一个\alpha 二元组时,Bob才接受Alice
现在,我们来思考一下,Alice应该如何回应这个挑战。我们先随便假设一下,如果Alice知道\alpha,那么他就可以在G里面任意选择一个a',然后计算出b'=\alpha*a',并发送(a', b')。
然而,关于\alpha她唯一知道的只是\alpha * a,而G是具有离散对数难解问题的群,所以我们无法通过b = \alpha * a计算出\alpha.
那么,在不知道\alpha的情况下,她如何才能正确地回应这个挑战呢?
有一个简单的办法:Alice只需要选择一个\gamma \in \mathbb{F}^*_p, 然后回应(a', b') = (\gamma * a, \gamma * b)
因此,我们有:
b' = \gamma * b = \gamma \alpha * b = \alpha(\gamma*a)= \alpha * a'
所以,(a', b')确实是一个\alpha二元组,符合要求。
需要注意的是,如果Alice通过这种情况来回应挑战,那么她就知道了a和a'之间的比值,也就是说,她知道这么一个系数\gamma,满足a'=\gamma*a。
正如系数知识假设(KCA)所指出的那样,这是不可避免的,也就是说:
KCA: 如果Alice针对Bob的挑战(a, b)给予了一个正确的回应(a', b'),那么她就知道这样一个\gamma,满足a'=\gamma*a。
Alice知道到底是什么意思
你可能会问,如何用数学语言准确的描述KCA?具体地,我们如何精确的给"Alice知道\gamma"下个数学定义?
这个可以简单的解释如下:假设我们有一个第三方,我们可以把它称为Alice提取者,Alice提取者可以获取Alice的内部状态。
这样我们就可以形式化KCA:无论Alice如何正确的回应一个\alpha二元组(a', b'),Alice提取者都能输出\gamma,满足a' = \gamma * a
早赞声明:为方便早赞、避免乱赞,“BH好文好报群”为点赞者、写作者牵线搭桥,实行“先审后赞、定时发表”的规则,也让作品脱颖而出、速登热门!加群微信:we01230123(天平)。
-
\mathbb{F}^*_p代表\mathbb{F}_p的所有非零元素,它等同于我们在第一部分中所说的\mathbb{Z}^*_p。 ↩
网友评论