美文网首页
23期:零知识证明详解三:系数测试及其假设

23期:零知识证明详解三:系数测试及其假设

作者: 鹏飞_3870 | 来源:发表于2018-07-24 22:17 被阅读0次

    本文翻译自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 表示 ag之和。

    系数知识测试

    对于\alpha \in \mathbb{F}^*_p [1], 我们定义一个二元组:(a, b), a \in G, b \in G。如果a, b \neq 0b = \alpha*a,那么我就称这个二元组为 \alpha二元组。

    这个KC测试的过程是这样的:

    1. Bob随机选择\alpha \in \mathbb{F}^*_pa \in G。然后计算出b = \alpha*a
    2. 他把这个二元组(a, b)发给Alice,向Alice发起挑战。注意,(a, b)是一个\alpha二元组
    3. Alice必须回应一个不同的\alpha二元组(a', b')
    4. 只有当(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通过这种情况来回应挑战,那么她就知道了aa'之间的比值,也就是说,她知道这么一个系数\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(天平)。


    1. \mathbb{F}^*_p代表\mathbb{F}_p的所有非零元素,它等同于我们在第一部分中所说的\mathbb{Z}^*_p

    相关文章

      网友评论

          本文标题:23期:零知识证明详解三:系数测试及其假设

          本文链接:https://www.haomeiwen.com/subject/eddemftx.html